# Stability and Generalization for Markov Chain Stochastic Gradient Methods

arXiv: https://arxiv.org/abs/2209.08005 · HTML: https://mlsanity.com/paper/2209.08005/

## 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 (most cited first, 30 of 44)

- [Towards Deep Learning Models Resistant to Adversarial Attacks](https://mlsanity.com/paper/1706.06083/) (2017)
- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Agnostic Federated Learning](https://mlsanity.com/paper/1902.00146/) (2019)
- [Fair Resource Allocation in Federated Learning](https://mlsanity.com/paper/1905.10497/) (2019)
- [On Gradient Descent Ascent for Nonconvex-Concave Minimax Problems](https://mlsanity.com/paper/1906.00331/) (2019)
- [Private Stochastic Convex Optimization with Optimal Rates](https://mlsanity.com/paper/1908.09970/) (2019)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [On the Convergence of Stochastic Gradient Descent with Adaptive Stepsizes](https://mlsanity.com/paper/1805.08114/) (2018)
- [Private Stochastic Convex Optimization: Optimal Rates in Linear Time](https://mlsanity.com/paper/2005.04763/) (2020)
- [Minimax Pareto Fairness: A Multi Objective Perspective](https://mlsanity.com/paper/2011.01821/) (2020)
- [Fast and Faster Convergence of SGD for Over-Parameterized Models and an Accelerated Perceptron](https://mlsanity.com/paper/1810.07288/) (2018)
- [Machine Unlearning via Algorithmic Stability](https://mlsanity.com/paper/2102.13179/) (2021)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [Non-strongly-convex smooth stochastic approximation with convergence rate O(1/n)](https://mlsanity.com/paper/1306.2119/) (2013)
- [Identity Matters in Deep Learning](https://mlsanity.com/paper/1611.04231/) (2016)
- [Stability and Generalization of Learning Algorithms that Converge to Global Optima](https://mlsanity.com/paper/1710.08402/) (2017)
- [High probability generalization bounds for uniformly stable algorithms with nearly optimal rate](https://mlsanity.com/paper/1902.10710/) (2019)
- [Sharper bounds for uniformly stable algorithms](https://mlsanity.com/paper/1910.07833/) (2019)
- [Data-Dependent Stability of Stochastic Gradient Descent](https://mlsanity.com/paper/1703.01678/) (2017)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [On Markov Chain Gradient Descent](https://mlsanity.com/paper/1809.04216/) (2018)
- [Weakly-Convex Concave Min-Max Optimization: Provable Algorithms and Applications in Machine Learning](https://mlsanity.com/paper/1810.02060/) (2018)
- [Stochastic AUC Maximization with Deep Neural Networks](https://mlsanity.com/paper/1908.10831/) (2019)
- [Stochastic Variance Reduction Methods for Policy Evaluation](https://mlsanity.com/paper/1702.07944/) (2017)
- [Generalization Bounds for Uniformly Stable Algorithms](https://mlsanity.com/paper/1812.09859/) (2018)
- [Train simultaneously, generalize better: Stability of gradient-based minimax learners](https://mlsanity.com/paper/2010.12561/) (2020)
- [One-Pass AUC Optimization](https://mlsanity.com/paper/1305.1363/) (2013)
- [Algorithmic stability and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Stability and Generalization of Stochastic Gradient Methods for Minimax Problems](https://mlsanity.com/paper/2105.03793/) (2021)
- [Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimization](https://mlsanity.com/paper/1804.06568/) (2018)

## Built on by (most cited first, 14 of 14)

- [Stochastic Gradient Descent under Markovian Sampling Schemes](https://mlsanity.com/paper/2302.14428/) (2023)
- [First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities](https://mlsanity.com/paper/2305.15938/) (2023)
- [Stability and Generalization of Stochastic Compositional Gradient Descent Algorithms](https://mlsanity.com/paper/2307.03357/) (2023)
- [Uniformly Stable Algorithms for Adversarial Training and Beyond](https://mlsanity.com/paper/2405.01817/) (2024)
- [Stability-based Generalization Analysis for Mixtures of Pointwise and Pairwise Learning](https://mlsanity.com/paper/2302.09967/) (2023)
- [Markov Chain Mirror Descent On Data Federation](https://mlsanity.com/paper/2309.14775/) (2023)
- [Stability and Generalization for Bellman Residuals](https://mlsanity.com/paper/2508.18741/) (2025)
- [Stability beyond Bounded Differences: Sharp Generalization Bounds under Finite Lp Moments](https://mlsanity.com/paper/2606.06855/) (2026)
- [A Novel Black Box Process Quality Optimization Approach based on Hit Rate](https://mlsanity.com/paper/2305.20003/) (2023)
- [Stochastic optimization with arbitrary recurrent data sampling](https://mlsanity.com/paper/2401.07694/) (2024)
- [Markov Chain Gradient Descent in Hilbert Spaces](https://mlsanity.com/paper/2410.08361/) (2024)
- [Generalization Bounds of Stochastic Gradient Descent in Homogeneous Neural Networks](https://mlsanity.com/paper/2602.22936/) (2026)
- [Stability and Generalization for Decentralized Markov SGD](https://mlsanity.com/paper/2605.01701/) (2026)
- [Variance-Reduced Conditional Gradient Methods under Markovian Sampling for Nonconvex Composite Optimization](https://mlsanity.com/paper/2607.25785/) (2026)

## 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.