Constant-Step Random Reshuffling
Descriptions may be stale. Consult the linked Lean sources.
Constant-Step Random Reshuffling
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Convexity and smoothness). Each
Assumption 2 (Initial distance and component
gradients). There exists
Our result is algorithm-specific: we analyze constant-step random
reshuffling. The algorithm chooses an integer
For an allotted number
Results
On a real Hilbert space with its Borel measurable structure, let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) ReshuffledConstantStepLastIterate (Ours) (review) | |||
| (2) VRADA (Song et al. 2021, Theorem 1); unregularized case | (1): |
(1) needs |
|
| (3) IID SGD (Attia et al. 2025, Theorem 2); uniform component sampling | (1): No established improvement over this raw-last-iterate guarantee. | (1) pays a full-epoch
cost |
|
| (4) RR (Liu and Zhou 2024,
Theorem 4.4, Appendix C.1); |
(1): deterministic-term
saving at least |
(1) loses |
|
| (5) RR (Liu 2026, Theorem 1, Corollary 1); averaged output | (1): raw last iterate instead of averaging all inner iterates; a multi-epoch constant-step RR guarantee. | (1) pays factor |
Abbr: RR: random reshuffling; IID: independent
identically distributed;