Online Learning, Stability, and Stochastic Gradient Descent

By Tomaso A. Poggio, Stephen Voinea, Lorenzo Rosasco. 2011

32 citations recorded by the source corpus.

In batch learning, stability together with existence and uniqueness of the solution corresponds to well-posedness of Empirical Risk Minimization (ERM) methods; recently, it was proved that CVloo stability is necessary and sufficient for generalization and consistency of ERM ([2]). In this note, we introduce CVon stability, which plays a similar role in online learning. We show that stochastic gradient descent (SDG) with the usual hypotheses is CVon stable and we then discuss the implications of CVon stability for convergence of SGD.

Subfields: Artificial Intelligence, Computational Mechanics, Management Science and Operations Research

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

1. Ilja Kuzborskij
2. Christoph H. Lampert
3. Vijay Ramaseshan Chandrasekhar
4. Ankan Saha
5. Savitha Ramasamy
6. Ambuj Tewari
7. Prateek Jain
8. Kristen Grauman

In Computational Mechanics

1. Christoph H. Lampert
2. Vijay Ramaseshan Chandrasekhar
3. Ankan Saha
4. Ambuj Tewari
5. Ilja Kuzborskij
6. Prateek Jain
7. Bart Vandereycken
8. Inderjit S. Dhillon

In Management Science and Operations Research

1. Christoph H. Lampert
2. Ankan Saha
3. Ambuj Tewari
4. Ilja Kuzborskij
5. Prateek Jain
6. Ian Osband
7. Benjamin Van Roy
8. Ronald Ortner

Citations in the corpus

• Data-Dependent Stability of Stochastic Gradient Descent (2017, methodology): “Uniform stability was used to analyze many algorithms, including regularized Empirical Risk Minimization (ERM) (Bousquet and Elisseeff, 2002), randomized aggregation schemes (Elisseeff et al., 2005), and recently SGD by Hardt et al. (2016); London (2016), and Poggio et al. (2011).”
• Online Deep Learning: Growing RBM on the fly (2018, background): “The sequential invariance is much like the invariance to permutations in the training set seen with batch learning algorithms [14].”
• Online Learning via the Differential Privacy Lens (2017, unknown): “A few papers that attempt to connect stability and online learning are interestingly all unpublished and only available as preprints [32, 35, 36].”
• The Interplay Between Stability and Regret in Online Learning (2012, background): “9 Conclusion Recent research [20, 16] has sought to establish connections between stability and online learnability.”
• Differentially Private Online Learning (2011, unknown): “In fact, recent results by Ross and Bagnell (2011); Poggio et al. (2011) seem to indicate a close connection between sensitivity and regret for online learning algorithms .”