Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed
Polyak–Łojasiewicz Minimization
We consider minimizing a possibly nonconvex function on a finite-dimensional
real inner product space . The
objective has Lipschitz gradient and Hessian, satisfies a
Polyak–Łojasiewicz inequality, and admits a global minimizer . A given starting point has bounded objective gap. The
oracle returns an unbiased stochastic gradient at each query, using
independent, identically distributed samples with bounded noise moments
of order , allowing heavy
tails. For , the
goal is a measurable output with integrable objective gap satisfying ,
where expectation includes sampling and independent algorithm
randomness.
The optimization problem is Write
for the norm induced by the inner product and for the induced
operator norm. Fix parameters The algorithm
receives , the measurable sample
space , , , , , , , , and .
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function is Fréchet
differentiable everywhere, and its gradient is Fréchet differentiable.
The Hessian is a
linear operator from to . For all ,
Assumption 2 (Polyak–Łojasiewicz inequality and
initialization). There exists such that, for every , and the given starting point satisfies
Assumption 3 (Unbiased oracle with heavy-tailed
noise). There is a probability measure on and a jointly measurable map . For each , the map is Bochner integrable and
is
integrable under , with The samples are measurable, mutually
independent, and each has law
under their joint probability law on . At the th query , the oracle returns . Algorithm randomness is
independent of this sample sequence.
Queries may be made at any point of . After the allotted oracle calls, the
output must be measurable
and have integrable objective gap, with
where is the joint law of the
samples and the algorithm’s randomness.