Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed SGD under the
PL Condition
We consider minimizing a differentiable, possibly nonconvex function
on a separable
real Hilbert space . Its gradient
is -Lipschitz, and it satisfies
the Polyak–Łojasiewicz condition with constant , where . Write . A
given starting point
satisfies ,
where . The oracle
returns unbiased stochastic gradients from independent, identically
distributed samples, with uniformly bounded second and th noise moments for , allowing heavy tails. For and , scheduled SGD must return
a measurable last iterate
satisfying ,
where is the sample law.
The optimization problem is The norm is induced by the inner product
on . The algorithm receives only
, , , and ; the noise parameters , moment order , initial gap bound , tolerance , and failure probability
may enter the oracle-call
budget but not the step-size schedule.
Our assumptions:
Assumption 1 (Smoothness). The function is Fréchet differentiable everywhere on
, with
Assumption 2 (Polyak–Łojasiewicz condition and
initialization). The function is
bounded below, and
Assumption 3 (Independent sampling and noise
moments). Let be a
measurable space and a
probability measure on . The
measurable sample variables are mutually independent
under , each with distribution
. The oracle is a jointly
measurable map
and returns at the th query . For every fixed , the map is Bochner integrable, and the
scalar maps and are integrable under . They satisfy
Our result is algorithm-specific: we analyze scheduled stochastic
gradient descent (SGD). Starting from the given , the method uses a deterministic
schedule with
and performs The schedule depends only on the
algorithm inputs specified above. After oracle calls, the
output is the last iterate . It must be measurable and
satisfy