mlsanityData to 7 Oct 2026

Stability and Convergence Trade-off of Iterative Optimization Algorithms

arXiv 1804.01619 ↗First posted 4 Apr 2018stat.ML cs.LG math.STcited by 53

Not on the map. Why?

Abstract (arXiv)

The overall performance or expected excess risk of an iterative machine learning algorithm can be decomposed into training error and generalization error. While the former is controlled by its convergence analysis, the latter can be tightly handled by algorithmic stability. The machine learning community has a rich history investigating convergence and stability separately. However, the question about the trade-off between these two quantities remains open. In this paper, we show that for any iterative algorithm at any iteration, the overall performance is lower bounded by the minimax statistical error over an appropriately chosen loss function class. This implies an important trade-off between convergence and stability of the algorithm -- a faster converging algorithm has to be less stable, and vice versa. As a direct consequence of this fundamental tradeoff, new convergence lower bounds can be derived for classes of algorithms constrained with different stability bounds. In particular, when the loss function is convex (or strongly convex) and smooth, we discuss the stability upper bounds of gradient descent (GD) and stochastic gradient descent and their variants with decreasing step sizes. For Nesterov's accelerated gradient descent (NAG) and heavy ball method (HB), we provide stability upper bounds for the quadratic loss function. Applying existing stability upper bounds for the gradient methods in our trade-off framework, we obtain lower bounds matching the well-established convergence upper bounds up to constants for these algorithms and conjecture similar lower bounds for NAG and HB. Finally, we numerically demonstrate the tightness of our stability bounds in terms of exponents in the rate and also illustrate via a simulated logistic regression problem that our stability bounds reflect the generalization errors better than the simple uniform convergence bounds for GD and NAG.

Key facts. Cited by 53 papers in the map (data through 7 Oct 2026). First posted on arXiv 4 Apr 2018.

Builds on

No reference list yet.

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2021: 13; 2022: 16; 2023: 8; 2024: 7; 2025: 5; 2026: 4.

53 papers.

Sort:

  1. 2022Benign Overfitting in Two-layer Convolutional Neural Networkscited by 90
  2. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  3. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  4. 2023Benign Overfitting for Two-layer ReLU Convolutional Neural Networkscited by 34
  5. 2021Stability of SGD: Tightness Analysis and Improved Boundscited by 33
  6. 2021On the Generalization of Models Trained with SGD: Information-Theoretic Bounds and Implicationscited by 31
  7. 2022Stability Analysis and Generalization Bounds of Adversarial Trainingcited by 30
  8. 2022Stability vs Implicit Bias of Gradient Methods on Separable Data and Beyondcited by 29
  9. 2021Time-independent Generalization Bounds for SGLD in Non-convex Settingscited by 27
  10. 2023Understanding Generalization of Federated Learning via Stability: Heterogeneity Matterscited by 27
  11. 2021Stability & Generalisation of Gradient Descent for Shallow Neural Networks without the Neural Tangent Kernelcited by 25
  12. 2022Stability and Generalization of Stochastic Optimization with Nonconvex and Nonsmooth Problemscited by 25
38 more
  1. 2021The Three Stages of Learning Dynamics in High-Dimensional Kernel Methodscited by 21
  2. 2022Stability and Generalization Analysis of Gradient Methods for Shallow Neural Networkscited by 21
  3. 2021Learning with Gradient Descent and Weakly Convex Lossescited by 16
  4. 2021Algorithmic Instabilities of Accelerated Gradient Descentcited by 16
  5. 2021Acceleration via Fractal Learning Rate Schedulescited by 13
  6. 2022Algorithmic Stability of Heavy-Tailed Stochastic Gradient Descent on Least Squarescited by 12
  7. 2023Differentially Private Algorithms for the Stochastic Saddle Point Problem with Optimal Rates for the Strong Gapcited by 11
  8. 2022Generalization in Supervised Learning Through Riemannian Contractioncited by 8
  9. 2022Risk Bounds of Multi-Pass SGD for Least Squares in the Interpolation Regimecited by 8
  10. 2022Uniform Stability for First-Order Empirical Risk Minimizationcited by 8
  11. 2022Exploring the Algorithm-Dependent Generalization of AUPRC Optimization with List Stabilitycited by 8
  12. 2023Uniform-in-Time Wasserstein Stability Bounds for (Noisy) Stochastic Gradient Descentcited by 6
  13. 2022Generalization Bounds for Gradient Methods via Discrete and Continuous Priorcited by 5
  14. 2022On the Algorithmic Stability and Generalization of Adaptive Optimization Methodscited by 5
  15. 2023Minibatch and Local SGD: Algorithmic Stability and Linear Speedup in Generalizationcited by 5
  16. 2021From inexact optimization to learning via gradient concentrationcited by 4
  17. 2024Generalization Error Matters in Decentralized Learning Under Byzantine Attackscited by 4
  18. 2024Generalization and Robustness of the Tilted Empirical Riskcited by 4
  19. 2023Optimal Guarantees for Algorithmic Reproducibility and Gradient Complexity in Convex Optimizationcited by 3
  20. 2023Cyclic and Randomized Stepsizes Invoke Heavier Tails in SGD than Constant Stepsizecited by 2
  21. 2023On the Stability and Generalization of Triplet Learningcited by 2
  22. 2024Federated Fairness without Access to Sensitive Groupscited by 2
  23. 2024Uniformly Stable Algorithms for Adversarial Training and Beyondcited by 2
  24. 2025Understanding Generalization in Transformers: Error Bounds and Training Dynamics Under Benign and Harmful Overfittingcited by 2
  25. 2021Noisy Truncated SGD: Optimization and Generalizationcited by 1
  26. 2022Benefit of Interpolation in Nearest Neighbor Algorithmscited by 1
  27. 2022Super-model ecosystem: A domain-adaptation perspectivecited by 1
  28. 2024Exploring the Generalization Capabilities of AID-based Bi-level Optimizationcited by 1
  29. 2025Stability, Complexity and Data-Dependent Worst-Case Generalization Boundscited by 1
  30. 2025Development of Deep Learning Optimizers: Approaches, Concepts, and Update Rulescited by 1
  31. 2026A Unified Lyapunov-IQC Framework for Uniform Stability of Smooth Quadratic First-Order Accelerated Optimizerscited by 1
  32. 2021On the Generalization of Stochastic Gradient Descent with Momentumcited by 0
  33. 2021Improved Learning Rates for Stochastic Optimizationcited by 0
  34. 2022Accelerated Gradient Flow: Risk, Stability, and Implicit Regularizationcited by 0
  35. 2024On the stability of gradient descent with second order dynamics for time-varying cost functionscited by 0
  36. 2024Understanding Generalization of Federated Learning: the Trade-off between Model Stability and Optimizationcited by 0
  37. 2025Fractal basin geometry and the limits to predictability and reproducibility in deep learningcited by 0
  38. 2025Stable Coresets via Posterior Sampling: Aligning Induced and Full Loss Landscapescited by 0

50 most cited of 53 All 53 (JSON)