Online Learning, Stability, and Stochastic Gradient Descent

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.

• Publication year

  2011

• Venue

  arXiv.org

• Publication date

  2011-05-24

• Fields of study

  Mathematics, Computer Science

• Identifiers
  arXiv 1105.4701
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Learning and Smoothed Analysis

  2009cited by this paper
• Sufficient Conditions for Uniform Stability of Regularization Algorithms

  2009cited by this paper
• Learning theory: stability is sufficient for generalization and necessary and sufficient for consistency of empirical risk minimization

  2006cited by this paper
• STABILITY RESULTS IN LEARNING THEORY

  2005cited by this paper
• A Central Limit Theorem for Robbins Monro Algorithms with Projections

  2005cited by this paper
• General conditions for predictivity in learning theory

  2004cited by this paper
• Stability and Generalization

  2002cited by this paper
• Random iterative models

  1996cited by this paper
• Scale-sensitive dimensions, uniform convergence, and learnability

  1993cited by this paper

• In-Context Learning can Perform Continual Learning Like Humans

  2025cites this paper
• Fusing Multiple Algorithms for Heterogeneous Online Learning

  2023cites this paper
• Communication-Efficient and Model-Heterogeneous Personalized Federated Learning via Clustered Knowledge Transfer

  2023cites this paper
• Research on Learning Resource Recommendation Algorithm Based on User Demand Evolution

  2022cites this paper
• An effective cost-sensitive sparse online learning framework for imbalanced streaming data classification and its application to online anomaly detection

  2022cites this paper
• Personalized Federated Learning for Heterogeneous Clients with Clustered Knowledge Transfer

  2021cites this paper
• Understanding Estimation and Generalization Error of Generative Adversarial Networks

  2021cites this paper
• Recursive Least-Squares Estimator-Aided Online Learning for Visual Tracking

  2020cites this paper
• Attentive Matrix Factorization for Recommender System

  2020cites this paper
• Attentional Autoencoder for Course Recommendation in MOOC with Course Relevance

  2020cites this paper
• Online RBM: Growing Restricted Boltzmann Machine on the fly for unsupervised representation

  2020cites this paper
• Intelligent Fuzzy Kinetic Control for an Under-Actuated Autonomous Surface Vehicle via Stochastic Gradient Descent

  2019cites this paper
• Distributed SGD Generalizes Well Under Asynchrony

  2019cites this paper
• Understanding generalization error of SGD in nonconvex optimization

  2019cites this paper
• Deep Learning application to learn models in Cognitive Robotics

  2019influential citation
• Maximum likelihood estimation of a finite mixture of logistic regression models in a continuous data stream

  2018influential citation
• Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimization

  2018cites this paper
• Theory and Algorithms for Hypothesis Transfer Learning

  2018cites this paper
• Deep Learning : Growing RBM on the fly

  2018cites this paper
• Online Deep Learning: Growing RBM on the fly

  2018cites this paper
• Online Learning via the Differential Privacy Lens

  2017cites this paper
• Data-Dependent Stability of Stochastic Gradient Descent

  2017cites this paper
• Online Learning via Differential Privacy

  2017cites this paper
• Tracking the decoy: maximizing the decoy effect through sequential experimentation

  2016cites this paper
• To Drop or Not to Drop: Robustness, Consistency and Differential Privacy Properties of Dropout

  2015cites this paper
• Lock in Feedback in Sequential Experiment

  2015cites this paper
• Lock in Feedback in Sequential Experiments

  2015cites this paper
• Online Learning in Reproducing Kernel Hilbert Spaces

  2014cites this paper
• Thompson sampling with the online bootstrap

  2014cites this paper
• Optimization methods in machine learning: theory and applications

  2013cites this paper
• The Interplay Between Stability and Regret in Online Learning

  2012cites this paper