Descriptions may be stale. Consult the linked Lean sources.
Random Reshuffling for
Convex Minimization
We consider minimizing on a real
Hilbert space , where and the functions are differentiable and
convex. Their gradient Lipschitz constants have prescribed average and
maximum bounds. A global minimizer satisfies prescribed bounds on
its distance from the given starting point and on the mean squared
component-gradient norm there. The oracle returns at . Random reshuffling uses
independent uniform permutations for a chosen number of epochs, then the
identity order. For , its final iterate must satisfy ,
where is the law of these
permutations.
The optimization problem is The norm is induced by the inner product
on . The parameters satisfy The
algorithm receives , , , , , , , and ; the component functions are accessed
through the oracle.
Our assumptions:
Assumption 1 (Component convexity and smoothness).
Each is Fréchet differentiable
on , and for every and ,
There exist constants such that
Assumption 2 (Initial distance and gradients at a
minimizer). There exists such that
Our result is algorithm-specific: we analyze random reshuffling with
a constant step size within each epoch. The algorithm chooses an integer
and a deterministic sequence
of real step
sizes from its inputs. The setup imposes no sign or magnitude
restriction on . For , let be independent uniform permutations
of ; for , set to the identity. Starting from the
given , the iterates satisfy
Queries may use any component
index and any point in . Each
update uses one component-gradient query. After an allotted number of queries, the output is the last
iterate , including when
ends within an epoch.
The output must be measurable, its objective gap must be integrable
under , and it must satisfy