mlsanityData to 7 Oct 2026

Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Covers

arXiv 2209.08951 ↗First posted 19 Sep 2022stat.ML cs.LGcited by 11

Not on the map. Why?

Abstract (arXiv)

In this paper, we propose a new covering technique localized for the trajectories of SGD. This localization provides an algorithm-specific complexity measured by the covering number, which can have dimension-independent cardinality in contrast to standard uniform covering arguments that result in exponential dimension dependency. Based on this localized construction, we show that if the objective function is a finite perturbation of a piecewise strongly convex and smooth function with P pieces, i.e. non-convex and non-smooth in general, the generalization error can be upper bounded by O(√(log nlog(nP))/n), where n is the number of data samples. In particular, this rate is independent of dimension and does not require early stopping and decaying step size. Finally, we employ these results in various contexts and derive generalization bounds for multi-index linear models, multi-class support vector machines, and K-means clustering for both hard and soft label setups, improving the known state-of-the-art rates.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 26 of its 52 references that are in the map. First posted on arXiv 19 Sep 2022.

Builds on

26 of 52 references.

References · 26

  1. 2017The Implicit Bias of Gradient Descent on Separable Datacited by 649
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2017Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysiscited by 242
  4. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  5. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  6. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 97
  7. 2019Sharper bounds for uniformly stable algorithmscited by 91
  8. 2017Bridging the Gap between Constant Step Size Stochastic Gradient Descent and Markov Chainscited by 84
  9. 2020A Unifying View on Implicit Bias in Training Linear Neural Networkscited by 74
  10. 2020Hausdorff Dimension, Heavy Tails, and Generalization in Neural Networkscited by 62
  11. 2019On Generalization Error Bounds of Noisy Gradient Methods for Non-Convex Learningcited by 57
  12. 2020On the Convergence of Langevin Monte Carlo: The Interplay between Tail Growth and Smoothnesscited by 55
14 more
  1. 2020An Analysis of Constant Step Size SGD in the Non-convex Regime: Asymptotic Normality and Biascited by 45
  2. 2018Global Non-convex Optimization with Discretized Diffusionscited by 44
  3. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 43
  4. 2021SGD Generalizes Better Than GD (And Regularization Doesn't Help)cited by 38
  5. 2016Generalization of ERM in Stochastic Convex Optimization: The Dimension Strikes Backcited by 37
  6. 2020Provable Memorization via Deep Neural Networks using Sub-linear Parameterscited by 34
  7. 2017A PAC-Bayesian Analysis of Randomized Learning with Application to Stochastic Gradient Descentcited by 29
  8. 2021Fractal Structure and Generalization Properties of Stochastic Optimization Algorithmscited by 23
  9. 2015Multi-class SVMs: From Tighter Data-Dependent Generalization Bounds to Novel Algorithmscited by 14
  10. 2018Piecewise Strong Convexity of Neural Networkscited by 13
  11. 2019Minimizing Uniformly Convex Functions by Cubic Regularization of Newton Methodcited by 12
  12. 2016Convergence rate of stochastic k-meanscited by 8
  13. 2022Generalization in Supervised Learning Through Riemannian Contractioncited by 8
  14. 2015Convergence of the k-Means Minimization Problem using Gamma-Convergencecited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 2; 2025: 0; 2026: 2.

11 papers.

  1. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 61
  2. 2023Gradient-Based Feature Learning under Structured Datacited by 32
  3. 2023Algorithmic Stability of Heavy-Tailed SGD with General Loss Functionscited by 15
  4. 2023Lessons from Generalization Error Analysis of Federated Learning: You May Communicate Less Often!cited by 8
  5. 2024The Surprising Harmfulness of Benign Overfitting for Adversarial Robustnesscited by 7
  6. 2023Learning Trajectories are Generalization Indicatorscited by 5
  7. 2023Generalization Guarantees via Algorithm-dependent Rademacher Complexitycited by 4
  8. 2023Advocating for the Silent: Enhancing Federated Generalization for Non-Participating Clientscited by 1
  9. 2024Convex SGD: Generalization Without Early Stoppingcited by 1
  10. 2026Generalization error bounds for two-layer neural networks with Lipschitz loss functioncited by 0
  11. 2026Trust, but Verify: Peeling Low-Bit Transformer Networks for Training Monitoringcited by 0