Affine Moment Acceleration — Convex Minimization with Affine Moments
Descriptions may be stale. Consult the linked Lean sources.
Convex Minimization with Affine Moments · Lean proof
Convex Minimization with
Affine Moments
We minimize a differentiable convex function on a separable real
Hilbert space . Its gradient is
-Lipschitz, with , and a given point lies within distance of a minimizer . The oracle returns unbiased
stochastic gradients from independent, identically distributed samples,
with error -moment bounded by
at , where
and . For and , the goal is a measurable
output satisfying
,
where is the joint law of
sampling and independent algorithm randomness.
The optimization problem is The norm is induced by the inner product
on , which is equipped with its
Borel sigma-algebra. Let be
a measurable sample space. The algorithm receives , , , , , , , , , and ; the objective is accessed through
the oracle.
Our assumptions:
Assumption 1 (Convexity and smoothness). The
function is Fréchet
differentiable everywhere on . For
every and ,
Assumption 2 (Initial distance). There exists such that
Assumption 3 (Sampling and affine moment bound).
There exist a probability measure on and a jointly measurable map . At the th query , the oracle returns , where the measurable random
variables are
mutually independent with common law , and are independent of the
algorithm’s randomness. For every , the map is
Bochner integrable and is integrable with respect to . They satisfy
Queries may be made at any point of . After the allotted oracle calls, the
output must be measurable
and satisfy the high-probability objective-gap requirement
Proved result
OracleTemplate.Convergence LongTails.Setups.AffineMomentConvex.spec LongTails.Theorems.AffineMomentAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.