Online Learning, Stability, and Stochastic Gradient Descent

2011/05/24 by Tomaso Poggio, Poggio, Tomaso, Stephen Voinea +3 · 2 citations
Computer Science · Decision Sciences · Engineering · #Advanced Bandit Algorithms Research #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning and Algorithms #Sparse and Compressive Sensing Techniques

paper · pdf · doi:10.48550/arxiv.1105.4701

openalex publication_date 2011/05/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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 CV_loo stability is necessary and sufficient for generalization and consistency of ERM. In this note, we introduce CV_on stability, which plays a similar note in online learning. We show that stochastic gradient descent (SDG) with the usual hypotheses is CVon stable and we then discuss the implications of CV_on stability for convergence of SGD.

Cited by

• In-Context Learning can Perform Continual Learning Like Humans
• Lock in Feedback in Sequential Experiments

Related

• Stability Conditions for Online Learnability
• Stability and Generalization for Markov Chain Stochastic Gradient Methods
• Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent
• Train faster, generalize better: Stability of stochastic gradient descent
• Generalization Bounds for Dependent Data using Online-to-Batch Conversion