Random Reshuffling for Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Random Reshuffling for Convex Minimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity and smoothness).
Each
Assumption 2 (Initial distance and gradients at a
minimizer). There exists
Our result is algorithm-specific: we analyze random reshuffling with
a constant step size within each epoch. The algorithm chooses an integer
The output must be measurable, its objective gap must be integrable
under
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) ReshuffledLinearDecayLastIterate (Ours) (review) | |||
| (2) Constant-step RR
(Liu and Zhou
2024, Thm. 4.4 / C.1) |
(1) removes |
(1) excludes composite
|
|
| (3) Averaged RR (Liu 2026, Thm. 1,
Cor. 1) |
(1) guarantees the last iterate instead of a weighted average; (3) does not imply this output guarantee. | (1) multiplies the
deterministic term by |
|
| (4) Full-gradient GD
(Nesterov
2018, Cor. 2.1.2) |
(1) matches the known
rate when |
(1) has a |
|
| (5) Full-gradient AGD
(Nesterov
2018, Thm. 2.2.2) |
(1): No established improvement. | (1) loses acceleration
( |
Abbr: RR: random reshuffling; GD: gradient descent;
AGD: accelerated gradient descent. Costs count component-gradient calls
(