mlsanityData to 7 Oct 2026

Stability and Generalization for Decentralized Markov SGD

arXiv 2605.01701 ↗First posted 3 May 2026cs.LGcited by 0

Not on the map. Why?

Abstract (arXiv)

Stochastic gradient methods are central to large-scale learning, yet their generalization theory typically relies on independent sampling assumptions. In many practical applications, data are generated by Markov chains and learning is performed in a decentralized manner, which introduces significant analytical challenges. In this work, we investigate the stability and generalization of decentralized stochastic gradient descent (SGD) and stochastic gradient descent ascent (SGDA) under Markov chain sampling. Leveraging a stability-based framework, we characterize how Markovian dependence and decentralized communication jointly influence generalization behavior. Our analysis captures the effects of network topology, Markov chain mixing properties, and primal-dual dynamics. We establish non-asymptotic generalization bounds for both algorithms, extending existing results on Markov stochastic gradient methods to decentralized and minimax settings.

Key facts. No citing papers in the map yet (data through 7 Oct 2026). Builds on 28 of its 47 references that are in the map. First posted on arXiv 3 May 2026.

Builds on

28 of 47 references.

References · 28

  1. 2017Towards Deep Learning Models Resistant to Adversarial Attackscited by 6,326
  2. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  3. 2017Can Decentralized Algorithms Outperform Centralized Algorithms? A Case Study for Decentralized Parallel Stochastic Gradient Descentcited by 496
  4. 2020A Unified Theory of Decentralized SGD with Changing Topology and Local Updatescited by 361
  5. 2018Don't Use Large Mini-Batches, Use Local SGDcited by 201
  6. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  7. 2014EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimizationcited by 160
  8. 2017Asynchronous Decentralized Parallel Stochastic Gradient Descentcited by 159
  9. 2013On the Convergence of Decentralized Gradient Descentcited by 158
  10. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  11. 2018On Markov Chain Gradient Descentcited by 63
  12. 2020Train simultaneously, generalize better: Stability of gradient-based minimax learnerscited by 43
16 more
  1. 2018Multi-Agent Reinforcement Learning via Double Averaging Primal-Dual Optimizationcited by 40
  2. 2022Topology-aware Generalization of Decentralized SGDcited by 37
  3. 2021Stability and Generalization of Stochastic Gradient Methods for Minimax Problemscited by 35
  4. 2022Refined Convergence and Topology Learning for Decentralized SGD with Heterogeneous Datacited by 31
  5. 2018Walkman: A Communication-Efficient Random-Walk Algorithm for Decentralized Optimizationcited by 30
  6. 2021Removing Data Heterogeneity Influence Enhances Network Topology Dependence of Decentralized SGDcited by 28
  7. 2021Simple Stochastic and Online Gradient Descent Algorithms for Pairwise Learningcited by 20
  8. 2017Asymptotic Bias of Stochastic Gradient Searchcited by 19
  9. 2022What is a Good Metric to Study Generalization of Minimax Learners?cited by 16
  10. 2020Convergence Rates of Accelerated Markov Gradient Descent with Applications in Reinforcement Learningcited by 15
  11. 2018Graph-Dependent Implicit Regularisation for Distributed Stochastic Subgradient Descentcited by 14
  12. 2022Stability and Generalization for Markov Chain Stochastic Gradient Methodscited by 14
  13. 2014Dictionary Learning over Distributed Modelscited by 8
  14. 2023Stability and Generalization of the Decentralized Stochastic Gradient Descent Ascent Algorithmcited by 8
  15. 2018Linearly Convergent Asynchronous Distributed ADMM via Markov Samplingcited by 3
  16. 2025Generalization Error Analysis for Attack-Free and Byzantine-Resilient Decentralized Learning with Data Heterogeneitycited by 1

Built on by

Not cited yet.