# Stability and Generalization for Randomized Coordinate Descent

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

## Key facts

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

## Builds on (most cited first, 21 of 21)

- [Train faster, generalize better: Stability of stochastic gradient descent](https://mlsanity.com/paper/1509.01240/) (2015)
- [Stability of Stochastic Gradient Descent on Nonsmooth Convex Losses](https://mlsanity.com/paper/2006.06914/) (2020)
- [Fine-Grained Analysis of Stability and Generalization for Stochastic Gradient Descent](https://mlsanity.com/paper/2006.08157/) (2020)
- [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 and hypothesis complexity](https://mlsanity.com/paper/1702.08712/) (2017)
- [Global Convergence of Block Coordinate Descent in Deep Learning](https://mlsanity.com/paper/1803.00225/) (2018)
- [Distributed Coordinate Descent Method for Learning with Big Data](https://mlsanity.com/paper/1310.2059/) (2013)
- [Differentially Private SGD with Non-Smooth Losses](https://mlsanity.com/paper/2101.08925/) (2021)
- [On the Complexity Analysis of Randomized Block-Coordinate Descent Methods](https://mlsanity.com/paper/1305.4723/) (2013)
- [SDNA: Stochastic Dual Newton Ascent for Empirical Risk Minimization](https://mlsanity.com/paper/1502.02268/) (2015)
- [Asynchronous Coordinate Descent under More Realistic Assumptions](https://mlsanity.com/paper/1705.08494/) (2017)
- [Stochastic Approximation of Smooth and Strongly Convex Functions: Beyond the O(1/T) Convergence Rate](https://mlsanity.com/paper/1901.09344/) (2019)
- [Unregularized Online Learning Algorithms with General Loss Functions](https://mlsanity.com/paper/1503.00623/) (2015)
- [Differentially Private Stochastic Coordinate Descent](https://mlsanity.com/paper/2006.07272/) (2020)
- [DSCOVR: Randomized Primal-Dual Block Coordinate Algorithms for Asynchronous Distributed Optimization](https://mlsanity.com/paper/1710.05080/) (2017)
- [Generalization Error Bounds for Optimization Algorithms via Stability](https://mlsanity.com/paper/1609.08397/) (2016)
- [On the Complexity Analysis of the Primal Solutions for the Accelerated Randomized Dual Coordinate Ascent](https://mlsanity.com/paper/1807.00261/) (2018)
- [Stochastic Parallel Block Coordinate Descent for Large-scale Saddle Point Problems](https://mlsanity.com/paper/1511.07294/) (2015)

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

- [Beyond Lipschitz: Sharp Generalization and Excess Risk Bounds for Full-Batch GD](https://mlsanity.com/paper/2204.12446/) (2022)
- [Select without Fear: Almost All Mini-Batch Schedules Generalize Optimally](https://mlsanity.com/paper/2305.02247/) (2023)
- [Black-Box Generalization: Stability of Zeroth-Order Learning](https://mlsanity.com/paper/2202.06880/) (2022)
- [Stability-based Generalization Analysis of Randomized Coordinate Descent for Pairwise Learning](https://mlsanity.com/paper/2503.01530/) (2025)

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