mlsanityData to 14 Oct 2026

Sharper bounds for uniformly stable algorithms

arXiv 1910.07833 ↗First posted 17 Oct 2019cs.LG math.PR stat.MLcited by 93

Not on the map. Why?

Abstract (arXiv)

Deriving generalization bounds for stable algorithms is a classical question in learning theory taking its roots in the early works by Vapnik and Chervonenkis (1974) and Rogers and Wagner (1978). In a series of recent breakthrough papers by Feldman and Vondrak (2018, 2019), it was shown that the best known high probability upper bounds for uniformly stable learning algorithms due to Bousquet and Elisseef (2002) are sub-optimal in some natural regimes. To do so, they proved two generalization bounds that significantly outperform the simple generalization bound of Bousquet and Elisseef (2002). Feldman and Vondrak also asked if it is possible to provide sharper bounds and prove corresponding high probability lower bounds. This paper is devoted to these questions: firstly, inspired by the original arguments of Feldman and Vondrak (2019), we provide a short proof of the moment bound that implies the generalization bound stronger than both recent results (Feldman and Vondrak, 2018, 2019). Secondly, we prove general lower bounds, showing that our moment bound is sharp (up to a logarithmic factor) unless some additional properties of the corresponding random variables are used. Our main probabilistic result is a general concentration inequality for weakly correlated random variables, which may be of independent interest.

Key facts. Cited by 93 papers in the map (data through 14 Oct 2026). First posted on arXiv 17 Oct 2019.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2021: 16; 2022: 23; 2023: 15; 2024: 5; 2025: 13; 2026: 21.

93 papers.

Sort:

By area:

  1. 2022AUC Maximization in the Era of Big Data and AI: A Surveycited by 100
  2. 2021Information-Theoretic Generalization Bounds for Stochastic Gradient Descentcited by 84
  3. 2022Neural Networks Efficiently Learn Low-Dimensional Representations with SGDcited by 63
  4. 2021Tighter expected generalization error bounds via Wasserstein distancecited by 43
  5. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  6. 2022On Convergence of FedProx: Local Dissimilarity Invariant Bounds, Non-smoothness and Beyondcited by 38
  7. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  8. 2021Generalization Bounds for Meta-Learning via PAC-Bayes and Uniform Stabilitycited by 30
  9. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  10. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 26
  11. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  12. 2023Explaining Generalization Power of a DNN Using Interactive Conceptscited by 25
38 more
  1. 2023Toward Understanding Generative Data Augmentationcited by 25
  2. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  3. 2023Self-Compatibility: Evaluating Causal Discovery without Ground Truthcited by 22
  4. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  5. 2021Optimal Algorithms for Differentially Private Stochastic Monotone Variational Inequalities and Saddle-Point Problemscited by 17
  6. 2021Algorithmic Instabilities of Accelerated Gradient Descentcited by 16
  7. 2025A Theoretical Perspective: How to Prevent Model Collapse in Self-consuming Training Loopscited by 16
  8. 2023Generalization Bounds with Data-dependent Fractal Dimensionscited by 15
  9. 2022Generalization Error Bounds for Deep Neural Networks Trained by SGDcited by 14
  10. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  11. 2021Information-Theoretic Bounds on the Moments of the Generalization Error of Learning Algorithmscited by 12
  12. 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
  13. 2022Generalization Bounds for Stochastic Gradient Descent via Localized varepsilon-Coverscited by 11
  14. 2022On the generalization of learning algorithms that do not convergecited by 9
  15. 2022Generalisation under gradient descent via deterministic PAC-Bayescited by 9
  16. 2022Stability Based Generalization Bounds for Exponential Family Langevin Dynamicscited by 8
  17. 2022Generalization in Supervised Learning Through Riemannian Contractioncited by 8
  18. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  19. 2026Conformal Risk Control for Non-Monotonic Lossescited by 8
  20. 2022Stability and Risk Bounds of Iterative Hard Thresholdingcited by 7
  21. 2022Generalization bounds for learning under graph-dependence: A surveycited by 6
  22. 2023Sample-Conditioned Hypothesis Stability Sharpens Information-Theoretic Generalization Boundscited by 6
  23. 2026Towards a Theoretical Understanding to the Generalization of RLHFcited by 6
  24. 2021Towards Understanding Generalization via Decomposing Excess Risk Dynamicscited by 5
  25. 2022Generalization Bounds for Gradient Methods via Discrete and Continuous Priorcited by 5
  26. 2022On the Algorithmic Stability and Generalization of Adaptive Optimization Methodscited by 5
  27. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  28. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  29. 2021Stability and Generalization for Randomized Coordinate Descentcited by 4
  30. 2023Sharper Analysis for Minibatch Stochastic Proximal Point Methods: Stability, Smoothness, and Deviationcited by 4
  31. 2023Hypothesis Transfer Learning with Surrogate Classification Losses: Generalization Bounds through Algorithmic Stabilitycited by 4
  32. 2023A Unified Framework for Generative Data Augmentation: A Comprehensive Surveycited by 4
  33. 2024Generalization and Robustness of the Tilted Empirical Riskcited by 4
  34. 2022Towards Data-Algorithm Dependent Generalization: a Case Study on Overparameterized Linear Regressioncited by 3
  35. 2022Sharper Utility Bounds for Differentially Private Modelscited by 3
  36. 2022Boosting the Confidence of Generalization for L2-Stable Randomized Learning Algorithmscited by 3
  37. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  38. 2025Stability and Generalization of Quantum Neural Networkscited by 3

50 most cited of 93 All 93 (JSON)