Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Donghwa Kim, Jaewook Lee, Chulhee Yun
Abstract
We analyze the convergence rates of two popular variants of coordinate descent (CD): random CD (RCD), in which the coordinates are sampled uniformly at random, and random-permutation CD (RPCD), in which random permutations are used to select the update indices. Despite abundant empirical evidence that RPCD outperforms RCD in various tasks, the theoretical gap between the two algorithms' performance has remained elusive. Even for the benign case of positivedefinite quadratic functions with permutationinvariant Hessians, previous efforts have failed to demonstrate a provable performance gap between RCD and RPCD. To this end, we present novel results showing that, for a class of quadratics with permutation-invariant structures, the contraction rate upper bound for RPCD is always strictly smaller than the contraction rate lower bound for RCD for every individual problem instance. Furthermore, we conjecture that this function class contains the worst-case examples of RPCD among all positive-definite quadratics. Combined with our RCD lower bound, this conjecture extends our results to the general class of positive-definite quadratic functions.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
2 top-tier papers have cited it since. Know what they found before your reviewers do.
Lune can draw on
the full paper · the top-tier papers that cite it · related work
Free to start. No credit card required.
Lineage
- Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond cites Random Reshuffling: Simple Analysis with Vast Improvements
- Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond cites SGD with shuffling: optimal rates without component convexity and large epoch requirements
- Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond cites Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
- Random Reshuffling: Simple Analysis with Vast Improvements cites SGD with shuffling: optimal rates without component convexity and large epoch requirements
- SGD with shuffling: optimal rates without component convexity and large epoch requirements cites Random Reshuffling: Simple Analysis with Vast Improvements
- Proximal and Federated Random Reshuffling cites SGD with shuffling: optimal rates without component convexity and large epoch requirements
- Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond cites Random Reshuffling: Simple Analysis with Vast Improvements
- Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond cites Proximal and Federated Random Reshuffling
- Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond cites SGD with shuffling: optimal rates without component convexity and large epoch requirements
- A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond cites Tighter Lower Bounds for Shuffling SGD: Random Permutations and Beyond
- A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond cites SGD with shuffling: optimal rates without component convexity and large epoch requirements
- A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and Beyond cites Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and Beyond
Cited by top-tier papers2
- A Unified Analysis of Stochastic Gradient Descent with Arbitrary Data Permutations and BeyondYipeng Li, Xinchen Lyu, Zhenyu LiuNeurIPS 2025
- The benefits of full data shuffle, now with optimal I/O cost: -wise independence and matrix transposition to the rescuePeyman Afshani, Rezaul Chowdhury, Mayank Goswami, Jens Kristian R Schou et al.ICML 2026
Builds on9
- Random Reshuffling: Simple Analysis with Vast ImprovementsKonstantin Mishchenko, Ahmed Khaled, Peter RichtárikNeurIPS 2020 · 172 citations
- SGD with shuffling: optimal rates without component convexity and large epoch requirementsKwangjun Ahn, Chulhee Yun, Suvrit SraNeurIPS 2020 · 83 citations
- Minibatch vs Local SGD with Shuffling: Tight Convergence Bounds and BeyondChulhee Yun, Shashank Rajput, Suvrit SraICLR 2022 · 47 citations
- Proximal and Federated Random ReshufflingKonstantin Mishchenko, Ahmed Khaled, Peter RichtárikICML 2022 · 39 citations
- Tighter Lower Bounds for Shuffling SGD: Random Permutations and BeyondJaeyoung Cha, Jaewook Lee, Chulhee YunICML 2023 · 26 citations
Related papers
- Permutation-Based SGD: Is Random Optimal?Shashank Rajput, Kangwook Lee, Dimitris S. PapailiopoulosICLR 2022 · 15 citations
- Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned ProblemsYujun Kim, Jaeyoung Cha, Chulhee YunICML 2025
- Random Shuffling Beats SGD Only After Many Epochs on Ill-Conditioned ProblemsItay Safran, Ohad ShamirNeurIPS 2021 · 24 citations
- Tighter Convergence Bounds for Shuffled SGD via Primal-Dual PerspectiveXufeng Cai, Cheuk Yin Lin, Jelena DiakonikolasNeurIPS 2024 · 9 citations
- A General Analysis of Example-Selection for Stochastic Gradient DescentYucheng Lu, Si Yi Meng, Christopher De SaICLR 2022 · 23 citations
