Descriptions may be stale. Consult the linked Lean sources.
Constant-Step Random
Reshuffling
We consider minimizing on a real
Hilbert space , where and the functions are differentiable and
convex with Lipschitz gradients. A given point satisfies for a minimizer
of , with , where . The oracle returns at . We analyze constant-step random
reshuffling and require its last iterate to satisfy ,
where and the
expectation is over the random permutations.
The optimization problem is The norm is induced by the inner product
on . Fix smoothness bounds . The
algorithm receives , , , , , , , and ; the component functions are accessed
through the oracle.
Our assumptions:
Assumption 1 (Convexity and smoothness). Each is Fréchet differentiable on and satisfies There exist constants such that These conditions hold for every .
Assumption 2 (Initial distance and component
gradients). There exists such that
Our result is algorithm-specific: we analyze constant-step random
reshuffling. The algorithm chooses an integer and a constant step size from the available inputs. It
draws independent, uniformly
distributed permutations of . For every epoch , set to the identity permutation.
Starting from the given , the
updates are Thus each of the first epochs visits every component once in a
fresh random order, and subsequent epochs use the fixed order . The same step size is used
throughout. Each update makes one component-gradient query, which may be
evaluated at any point of .
For an allotted number of
oracle calls, the output is the last iterate , including when the calls end
partway through an epoch. Let be
the law of the sampled permutations. The output must be measurable, its
objective gap must be integrable under , and it must satisfy