mlsanityData to 14 Oct 2026

Generalization Bounds for Label Noise Stochastic Gradient Descent

arXiv 2311.00274 ↗First posted 1 Nov 2023stat.ML cs.LG math.OCcited by 3

Not on the map. Why?

Abstract (arXiv)

We develop generalization error bounds for stochastic gradient descent (SGD) with label noise in non-convex settings under uniform dissipativity and smoothness conditions. Under a suitable choice of semimetric, we establish a contraction in Wasserstein distance of the label noise stochastic gradient flow that depends polynomially on the parameter dimension d. Using the framework of algorithmic stability, we derive time-independent generalisation error bounds for the discretized algorithm with a constant learning rate. The error bound we achieve scales polynomially with d and with the rate of n-2/3, where n is the sample size. This rate is better than the best-known rate of n-1/2 established for stochastic gradient Langevin dynamics (SGLD) -- which employs parameter-independent Gaussian noise -- under similar conditions. Our analysis offers quantitative insights into the effect of label noise.

Key facts. Cited by 3 papers in the map (data through 14 Oct 2026). Builds on 29 of its 60 references that are in the map. First posted on arXiv 1 Nov 2023.

Builds on

29 of 60 references.

References · 29

  1. 2017Accurate, Large Minibatch SGD: Training ImageNet in 1 Hourcited by 1,492
  2. 2016On Large-Batch Training for Deep Learning: Generalization Gap and Sharp Minimacited by 1,352
  3. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  4. 2017Information-theoretic analysis of generalization capability of learning algorithmscited by 303
  5. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 243
  6. 2018Measuring the Effects of Data Parallelism on Neural Network Trainingcited by 193
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  8. 2019Implicit regularization for deep neural networks driven by an Ornstein-Uhlenbeck like processcited by 123
  9. 2021Label Noise SGD Provably Prefers Flat Global Minimizerscited by 121
  10. 2019Information-Theoretic Generalization Bounds for SGLD via Data-Dependent Estimatescited by 119
  11. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  12. 2018Stochastic Modified Equations and Dynamics of Stochastic Gradient Algorithms I: Mathematical Foundationscited by 114
17 more
  1. 2017Stochastic gradient descent performs variational inference, converges to limit cycles for deep networkscited by 109
  2. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  3. 2017Global Convergence of Langevin Dynamics Based Algorithms for Nonconvex Optimizationcited by 97
  4. 2020Shape Matters: Understanding the Implicit Bias of the Noise Covariancecited by 88
  5. 2017Generalization Bounds of SGLD for Non-convex Learning: Two Theoretical Viewpointscited by 82
  6. 2018Generalization Error Bounds for Noisy, Iterative Algorithmscited by 82
  7. 2022The alignment property of SGD noise and how it helps select flat minima: A stability analysiscited by 64
  8. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  9. 2018Global Non-convex Optimization with Discretized Diffusionscited by 44
  10. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 44
  11. 2019Nonasymptotic estimates for Stochastic Gradient Langevin Dynamics under local conditions in nonconvex optimizationcited by 38
  12. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  13. 2022Label noise (stochastic) gradient descent implicitly solves the Lasso for quadratic parametrisationcited by 29
  14. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  15. 2022Generalization in Supervised Learning Through Riemannian Contractioncited by 8
  16. 2023Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descentcited by 6
  17. 2021A Reverse Jensen Inequality Result with Application to Mutual Information Estimationcited by 5

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2024: 1; 2025: 1; 2026: 1.

3 papers.

  1. 2025How Does Label Noise Gradient Descent Improve Generalization in the Low SNR Regime?cited by 4
  2. 2024Impact of Label Noise on Learning Complex Featurescited by 0
  3. 2026On the Learning Dynamics of Two-layer Linear Networks with Label Noise SGDcited by 0