Strong Growth Restarted Agd — Stationarity Under Strong Growth
Descriptions may be stale. Consult the linked Lean sources.
Stationarity Under Strong Growth · Lean proof
Stationarity Under Strong
Growth
We consider minimizing a possibly nonconvex, twice continuously
differentiable function on a finite-dimensional
real inner product space . Its
gradient and Hessian are Lipschitz with constants and , and a given point satisfies , where
. The oracle returns
unbiased stochastic gradients with independent, identically distributed
samples and mean squared error at most , where . The goal is a measurable
output with , where satisfies .
The optimization problem is The norm is induced by the inner product
on , and denotes the
induced operator norm. The algorithm receives , the measurable sample space , , , , , , and .
Our assumptions:
Assumption 1 (Gradient and Hessian regularity). The
function belongs to , and, for all , Here is the derivative of the gradient.
Assumption 2 (Initial objective gap). The given
point satisfies
Assumption 3 (Strong-growth stochastic oracle).
There is a probability measure
on and a jointly measurable
map . For every
, the random vector is Bochner integrable and is integrable
for , with The samples are measurable, mutually
independent, and each has law
under a 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,
its gradient norm must be integrable, and it must satisfy where is the joint law of the algorithm’s
randomness and the oracle samples.
Proved result
OracleTemplate.Convergence LongTails.Setups.StrongGrowthHessianLipschitz.spec
OracleTemplate.StrongGrowthRestartedAgd.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.