mlsanityData to 14 Oct 2026

Stability and Generalization for Markov Chain Stochastic Gradient Methods

arXiv 2209.08005 ↗First posted 16 Sep 2022stat.ML cs.LGcited by 14

Not on the map. Why?

Abstract (arXiv)

Recently there is a large amount of work devoted to the study of Markov chain stochastic gradient methods (MC-SGMs) which mainly focus on their convergence analysis for solving minimization problems. In this paper, we provide a comprehensive generalization analysis of MC-SGMs for both minimization and minimax problems through the lens of algorithmic stability in the framework of statistical learning theory. For empirical risk minimization (ERM) problems, we establish the optimal excess population risk bounds for both smooth and non-smooth cases by introducing on-average argument stability. For minimax problems, we develop a quantitative connection between on-average argument stability and generalization error which extends the existing results for uniform stability citelei2021stability. We further develop the first nearly optimal convergence rates for convex-concave problems both in expectation and with high probability, which, combined with our stability results, show that the optimal generalization bounds can be attained for both smooth and non-smooth cases. To the best of our knowledge, this is the first generalization analysis of SGMs when the gradients are sampled from a Markov process.

Key facts. Cited by 14 papers in the map (data through 14 Oct 2026). Builds on 44 of its 95 references that are in the map. First posted on arXiv 16 Sep 2022.

Builds on

44 of 95 references.

References · 44

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,415
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 552
  3. 2019Agnostic Federated Learningcited by 456
  4. 2019Fair Resource Allocation in Federated Learningcited by 394
  5. 2019On Gradient Descent Ascent for Nonconvex-Concave Minimax Problemscited by 270
  6. 2019Private Stochastic Convex Optimization with Optimal Ratescited by 186
  7. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 173
  8. 2018On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizescited by 156
  9. 2020Private Stochastic Convex Optimization: Optimal Rates in Linear Timecited by 153
  10. 2020Minimax Pareto Fairness: A Multi Objective Perspectivecited by 153
  11. 2018Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptroncited by 143
  12. 2021Machine Unlearning via Algorithmic Stabilitycited by 130
32 more
  1. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 119
  2. 2013Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)cited by 111
  3. 2016Identity Matters in Deep Learningcited by 109
  4. 2017Stability and Generalization of Learning Algorithms that Converge to Global Optimacited by 100
  5. 2019High probability generalization bounds for uniformly stable algorithms with nearly optimal ratecited by 98
  6. 2019Sharper bounds for uniformly stable algorithmscited by 93
  7. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 92
  8. 2015Algorithmic Stability for Adaptive Data Analysiscited by 88
  9. 2018On Markov Chain Gradient Descentcited by 63
  10. 2018Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learningcited by 63
  11. 2019Stochastic AUC Maximization with Deep Neural Networkscited by 61
  12. 2017Stochastic Variance Reduction Methods for Policy Evaluationcited by 58
  13. 2018Generalization Bounds for Uniformly Stable Algorithmscited by 56
  14. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 44
  15. 2013One-Pass AUC Optimizationcited by 42
  16. 2017Algorithmic stability and hypothesis complexitycited by 39
  17. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 36
  18. 2018Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimizationcited by 31
  19. 2020Generalization Bounds for Stochastic Saddle Point Problemscited by 28
  20. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  21. 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
  22. 2017Asymptotic Bias of Stochastic Gradient Searchcited by 19
  23. 2020Finite-Time Analysis of Stochastic Gradient Descent under Markov Randomnesscited by 18
  24. 2020Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learningcited by 15
  25. 2018Generalization Error Bounds with Probabilistic Guarantee for SGD in Nonconvex Optimizationcited by 14
  26. 2020Private Weighted Random Walk Stochastic Gradient Descentcited by 14
  27. 2014Dictionary Learning over Distributed Modelscited by 8
  28. 2016Optimal Rates for Multi-pass Stochastic Gradient Methodscited by 8
  29. 2019Stability and Optimization Error of Stochastic Gradient Descent for Pairwise Learningcited by 8
  30. 2013On Stochastic Subgradient Mirror-Descent Algorithm with Weighted Averagingcited by 5
  31. 2018Linearly Convergent Asynchronous Distributed ADMM via Markov Samplingcited by 3
  32. 2019Decentralized Markov Chain Gradient Descentcited by 3

Built on by

Cited by year (2026 to 14 Oct)

Citing papers per year: 2023: 6; 2024: 3; 2025: 1; 2026: 4.

14 papers.

Sort:

By area:

  1. 2023Stochastic Gradient Descent under Markovian Sampling Schemescited by 38
  2. 2023First Order Methods with Markovian Noise: from Acceleration to Variational Inequalitiescited by 14
  3. 2023Stability and Generalization of Stochastic Compositional Gradient Descent Algorithmscited by 3
  4. 2024Uniformly Stable Algorithms for Adversarial Training and Beyondcited by 2
  5. 2023Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learningcited by 1
  6. 2023Markov Chain Mirror Descent On Data Federationcited by 1
  7. 2025Stability and Generalization for Bellman Residualscited by 1
  8. 2026Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Momentscited by 1
  9. 2023A Novel Black Box Process Quality Optimization Approach based on Hit Ratecited by 0
  10. 2024Stochastic optimization with arbitrary recurrent data samplingcited by 0
  11. 2024Markov Chain Gradient Descent in Hilbert Spacescited by 0
  12. 2026Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networkscited by 0
2 more
  1. 2026Stability and Generalization for Decentralized Markov SGDcited by 0
  2. 2026Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimizationcited by 0