Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent
Donghwa Kim, Jaewook Lee, Chulhee Yun · 2025
Read Provable Benefit of Random Permutations over Uniform Sampling in Stochastic Coordinate Descent by Donghwa Kim, Jaewook Lee, Chulhee Yun (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2505-23152.txt.
Description
Donghwa Kim, Jaewook Lee, and Chulhee Yun settle a 2025 theory question about a training method that updates one part of a model at a time. One variant picks parts at random each step. A second shuffles all parts into a fresh order each round, and in practice it tends to win, though no proof of a gap existed.
For a clean class of curved problems, the team proves the shuffled variant always shrinks error faster than the random one, on every single case. They also argue this class may hold the worst cases for shuffling. If so, the gap would extend to a far wider family of problems.
Catalog record
| CREATOR | Donghwa Kim, Jaewook Lee, Chulhee Yun |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 185 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-23152