Learning Management
Universal Rates for Active Learning
In this work we study the problem of actively learning binary classifiers from a given concept class, i.e., learning by utilizing unlabeled data and submitting targeted queries about their labels to a domain expert. We evaluate the quality of our solutions by considering the learning curves they induce, i.e., the rate of
Riemannian Projection-free Online Learning
In Euclidean space, OCO boasts a robust theoretical foundation and numerous real-world applications, such as online load balancing (Molinaro, 2017), optimal control (Li et al., 2019), revenue maximization (Lin et al., 2019), and portfolio management (Jézéquel et al., 2022).
Universal Online Learning with Gradient Variations: A Multi-layer Online Ensemble Approach
In this paper, we propose an online convex optimization approach with two different levels of adaptivity. On a higher level, our approach is agnostic to the unknown types and curvatures of the online functions, while at a lower level, it can exploit the unknown niceness of the environments and attain problem-dependent guarantees.
Online Learning via the Differential Privacy Lens
Jacob D. Abernethy, Young Hun Jung, Chansoo Lee, Audra McMillan, Ambuj Tewari
Neural Information Processing Systems http://nips.cc/
High-Probability Minimax Adaptive Estimation in Besov Spaces via Online-to-Batch
Liautaud, Paul, Gaillard, Pierre, Wintenberger, Olivier
We study nonparametric regression over Besov spaces from noisy observations under sub-exponential noise, aiming to achieve minimax-optimal guarantees on the integrated squared error that hold with high probability and adapt to the unknown noise level. To this end, we propose a wavelet-based online learning algorithm that dynamically adjusts to the observed gradient noise by adaptively clipping it at an appropriate level, eliminating the need to tune parameters such as the noise variance or gradient bounds. As a by-product of our analysis, we derive high-probability adaptive regret bounds that scale with the $\ell_1$-norm of the competitor. Finally, in the batch statistical setting, we obtain adaptive and minimax-optimal estimation rates for Besov spaces via a refined online-to-batch conversion. This approach carefully exploits the structure of the squared loss in combination with self-normalized concentration inequalities.
Private Learning Implies Online Learning: An Efficient Reduction
Alon Gonen, Elad Hazan, Shay Moran
Neural Information Processing Systems http://nips.cc/
Learning on the Edge: Online Learning with Stochastic Feedback Graphs
The framework of feedback graphs is a generalizationof sequential decisionmaking with bandit or full information feedback. In this work, we study an extension where the directed feedback graph is stochastic, following a distribution similar to the classical Erdős-Rényi model. Specifically, in each round every edge in the graph is either realized or not with a distinct probability for each edge.