On the generalization ability of on-line learning algorithms

By Nicolò Cesa-Bianchi, Alex Conconi, Claudio Gentile. 2001

624 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computer Vision and Pattern Recognition, Scaling & Learning Theory

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computer Vision and Pattern Recognition

In Scaling & Learning Theory

Citations in the corpus

Memory-Efficient Adaptive Optimization for Large-Scale Learning (2019, methodology): “Under convexity assumptions, an online algorithm with vanishing average regret can be converted to a stochastic optimization algorithm for minimizing the population loss L [6].”
A Reduction of Imitation Learning and Structured Prediction to No-Regret Online Learning (2010, methodology): “Our approach is closely related to no regret online learning algorithms (Cesa-Bianchi et al., 2004; Hazan et al., 2006; Kakade and Shalev-Shwartz, 2008) (in particular Follow-The-Leader) but better leverages the expert in our setting.”
Optimization Methods for Large-Scale Machine Learning (2016, background): “ch worse than the best average loss one would have obtained if the optimal parameter w were known in advance. Further assuming that the noise variables are independent and using a martingale argument [34] leads to more traditional results of the form E " 1 K XK k=1 F(w k) # F + O 1 p K : As l”
Practical and Private (Deep) Learning without Sampling or Shuffling (2021, methodology): “Population risk guarantees: In Section 5.3, using the standard online-to-batch conversion [12, 63], we obtain a population risk guarantee for DP-FTRL.”
Differentially Private Meta-Learning (2019, methodology): “The regret of this procedure, when averaged across the users, implies a bound on the expected excess transfer risk of new task from Q when running OGD from a learned initialization (Cesa-Bianchi et al., 2004).”
Adaptive Gradient-Based Meta-Learning Methods (2019, methodology): “[14] only prove the first inequality; the second follows via the same argument but applying the symmetric version of the Azuma-Hoeffding inequality [4].”
Deep learning with Elastic Averaging SGD (2014, background): “[30] Cesa-Bianchi, N, Conconi, A, and Gentile, C.”
Smoothness, Low Noise and Fast Rates (2010, background): “Standard arguments [8] allow us to convert the online regret bound of Theorem 2 to a bound on the excess risk: Corollary 3.”
Introduction to Online Convex Optimization (2016, background): “Tighter and more general bounds were explored in (27; 28; 109).”
Adaptive Gradient Methods with Dynamic Bound of Learning Rate (2019, methodology): “It has been pointed out that an online optimization algorithm with vanishing average regret yields a corresponding stochastic optimization algorithm (Cesa-Bianchi et al., 2002).”
Improving Multi-Step Prediction of Learned Time Series Models (2015, methodology): “Additionally, we can even utilize other online learning methods to achieve the same performance bounds since many are also no-regret (Cesa-Bianchi, Conconi, and Gentile 2004).”
Agnostic System Identification for Model-Based Reinforcement Learning (2012, neutral): “loss on m sampled transitions, we can still obtain good guarantees using martingale inequalities as in online-to-batch (Cesa-Bianchi et al., 2004) techniques.”
Shampoo: Preconditioned Stochastic Tensor Optimization (2018, methodology): “Any regret minimizing algorithm can be converted to a stochastic optimization algorithm with convergence rate O(RT /T) using an online-to-batch conversion technique (Cesa-Bianchi et al., 2004).”
How to Train Your DRAGAN (2017, background): “The celebrated “online-to-batch conversion” [5], now a standard result in online learning theory, implies that Ex,z[gx,z(θ̄T , φ)], for any φ, is no more than the optimal value Ex,z[gx,z(θ∗, φ)] plus an “estimation error” bounded by E [ R1(T )+R2(T ) T ] , where the expectation is taken with respect”
Convergence of Value Aggregation for Imitation Learning (2018, methodology): “, 1998) (as the function is strongly convex) and the O( 1 √ mN ) error is the generalization error (Cesa-Bianchi et al., 2004). descent in O( 1 n ), using AggreVaTe results in a sequence of policies with degrading performance, though the policy class Π includes a globally optimal policy. Now suppose”
On the Generalization Ability of Online Strongly Convex Programming Algorithms (2008, background): “These include cas s which are tailored to general convex functions [Cesa-Bianchi et al., 2004] (whose regret isO( √ T )) and mistake bound settings [CesaBianchi and Gentile, 2008] (where the the regret could beO(1) under separability assumptions).”
The Statistics of Streaming Sparse Regression (2014, methodology): “The standard way to turn cumulative online loss bounds into generalization bounds is using “online-to-batch” conversion [13, 31].”
Aggregation by exponential weighting, sharp PAC-Bayesian bounds and sparsity (2008, result): “Finally, [12, 20] establish some links between the results for cumulative risks proved in the theory of prediction of deterministic sequences and generalization error bounds for the aggregates in the stochastic i.i.d. case.”