mlsanityData to 7 Oct 2026

Stability and Generalization for Randomized Coordinate Descent

arXiv 2108.07414 ↗First posted 17 Aug 2021cs.LGcited by 4

Not on the map. Why?

Abstract (arXiv)

Randomized coordinate descent (RCD) is a popular optimization algorithm with wide applications in solving various machine learning problems, which motivates a lot of theoretical analysis on its convergence behavior. As a comparison, there is no work studying how the models trained by RCD would generalize to test examples. In this paper, we initialize the generalization analysis of RCD by leveraging the powerful tool of algorithmic stability. We establish argument stability bounds of RCD for both convex and strongly convex objectives, from which we develop optimal generalization bounds by showing how to early-stop the algorithm to tradeoff the estimation and optimization. Our analysis shows that RCD enjoys better stability as compared to stochastic gradient descent.

Key facts. Cited by 4 papers in the map (data through 7 Oct 2026). Builds on 21 of its 41 references that are in the map. First posted on arXiv 17 Aug 2021.

Builds on

21 of 41 references.

References · 21

  1. 2015Train faster, generalize better: Stability of stochastic gradient descentcited by 547
  2. 2020Stability of Stochastic Gradient Descent on Nonsmooth Convex Lossescited by 172
  3. 2020Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descentcited by 118
  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 97
  6. 2019Sharper bounds for uniformly stable algorithmscited by 91
  7. 2017Data-Dependent Stability of Stochastic Gradient Descentcited by 90
  8. 2017Algorithmic stability and hypothesis complexitycited by 39
  9. 2018Global Convergence of Block Coordinate Descent in Deep Learningcited by 38
  10. 2013Distributed Coordinate Descent Method for Learning with Big Datacited by 23
  11. 2021Differentially Private SGD with Non-Smooth Lossescited by 22
  12. 2013On the Complexity Analysis of Randomized Block-Coordinate Descent Methodscited by 21
9 more
  1. 2015SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimizationcited by 18
  2. 2017Asynchronous Coordinate Descent under More Realistic Assumptionscited by 14
  3. 2019Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Ratecited by 14
  4. 2015Unregularized Online Learning Algorithms with General Loss Functionscited by 11
  5. 2020Differentially Private Stochastic Coordinate Descentcited by 8
  6. 2017DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimizationcited by 7
  7. 2016Generalization Error Bounds for Optimization Algorithms via Stabilitycited by 3
  8. 2018On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascentcited by 2
  9. 2015Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problemscited by 1

Built on by

Cited by year

Citing papers per year: 2022: 2; 2023: 1; 2024: 0; 2025: 1.

4 papers.

  1. 2022Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GDcited by 19
  2. 2023Select without Fear: Almost All Mini-Batch Schedules Generalize Optimallycited by 5
  3. 2022Black-Box Generalization: Stability of Zeroth-Order Learningcited by 1
  4. 2025Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learningcited by 0