mlsanityData to 7 Oct 2026

Algorithmic stability and hypothesis complexity

arXiv 1702.08712 ↗First posted 28 Feb 2017stat.ML cs.LGcited by 39

Not on the map. Why?

Abstract (arXiv)

We introduce a notion of algorithmic stability of learning algorithms---that we term argument stability---that captures stability of the hypothesis output by the learning algorithm in the normed space of functions from which hypotheses are selected. The main result of the paper bounds the generalization error of any learning algorithm in terms of its argument stability. The bounds are based on martingale inequalities in the Banach space to which the hypotheses belong. We apply the general bounds to bound the performance of some learning algorithms based on empirical risk minimization and stochastic gradient descent.

Key facts. Cited by 39 papers in the map (data through 7 Oct 2026). First posted on arXiv 28 Feb 2017.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 10; 2022: 9; 2023: 6; 2024: 7; 2025: 1; 2026: 6.

39 papers.

Sort:

By area:

  1. 2021Stability and Deviation Optimal Risk Bounds with Convergence Rate O(1/n)cited by 42
  2. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  3. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  4. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  5. 2021Deep Active Learning by Leveraging Training Dynamicscited by 32
  6. 2021Estimating Instance-dependent Bayes-label Transition Matrix using a Deep Neural Networkcited by 30
  7. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
  8. 2023Toward Understanding Generative Data Augmentationcited by 25
  9. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  10. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  11. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  12. 2022Two Facets of SDE Under an Information-Theoretic Lens: Generalization of SGD via Training Trajectories and via Terminal Statescited by 11
27 more
  1. 2024Can DPO Learn Diverse Human Values? A Theoretical Scaling Lawcited by 7
  2. 2023Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descentcited by 6
  3. 2022On the Algorithmic Stability and Generalization of Adaptive Optimization Methodscited by 5
  4. 2021Local and Global Uniform Convexity Conditionscited by 4
  5. 2021Stability and Generalization for Randomized Coordinate Descentcited by 4
  6. 2023A Unified Framework for Generative Data Augmentation: A Comprehensive Surveycited by 4
  7. 2024On Uncertainty Quantification for Near-Bayes Optimal Algorithmscited by 3
  8. 2026Fine-grained Analysis of Stability and Generalization for Stochastic Bilevel Optimizationcited by 3
  9. 2021Towards Sharper Utility Bounds for Differentially Private Pairwise Learningcited by 2
  10. 2022Stability and Generalization of Differentially Private Minimax Problemscited by 2
  11. 2023On the Stability and Generalization of Triplet Learningcited by 2
  12. 2024Stability and Sharper Risk Bounds with Convergence Rate tildeO(1/n2)cited by 2
  13. 2022Super-model ecosystem: A domain-adaptation perspectivecited by 1
  14. 2022On Stability and Generalization of Bilevel Optimization Problemcited by 1
  15. 2023Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learningcited by 1
  16. 2023Generalization error bounds for iterative learning algorithms with bounded updatescited by 1
  17. 2024On Sensitivity of Learning with Limited Labelled Data to the Effects of Randomness: Impact of Interactions and Systematic Choicescited by 1
  18. 2026Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Momentscited by 1
  19. 2021Improved Learning Rates for Stochastic Optimizationcited by 0
  20. 2024Bootstrap SGD: Algorithmic Stability and Robustnesscited by 0
  21. 2024Towards Sharper Risk Bounds for Minimax Problemscited by 0
  22. 2024Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimizationcited by 0
  23. 2025Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learningcited by 0
  24. 2026Sequential Subspace Noise Injection Prevents Accuracy Collapse in Certified Unlearningcited by 0
  25. 2026Stability and Generalization of Stochastic Nonconvex Optimization under Heavy-Tailed Noise: From Gradient Norm to Goldstein Stationaritycited by 0
  26. 2026On the Stability and Generalization of First-order Bilevel Minimax Optimizationcited by 0
  27. 2026Learning Theory of the SVRG: Generalization and Convergence Analysiscited by 0