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

CREATORDonghwa Kim, Jaewook Lee, Chulhee Yun
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE185 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2505-23152

Browse the full library · About the Tower of Babel