Split Robust Heavy Tailed Acceleration — Heavy-Tailed Strong-Growth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Heavy-Tailed Strong-Growth Convex Minimization · Lean proof
Heavy-Tailed
Strong-Growth Convex Minimization
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 global minimizer . At , the oracle returns an unbiased
stochastic gradient using
independent samples from a
probability measure on a
measurable space . Its noise
has th moment at most , where and . For , the goal is a
measurable output with
integrable objective gap satisfying ,
averaging over sampling and algorithm randomness.
The optimization problem is The norm is induced by the inner product
on , which is equipped with its
Borel sigma-algebra. The algorithm receives , , , , , , , and ; access to is through the stochastic gradient
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 (Relative moment and independent
sampling). The map is jointly measurable. For each , the map is Bochner integrable under
, and is
integrable under . They satisfy
The oracle uses a sequence of measurable, mutually
independent random variables, each with distribution . At call , a query receives . The algorithm’s randomness is
independent of this sample sequence.
Queries may be made at any point of . Let denote the joint law of the sample
sequence and the algorithm’s randomness. After the allotted oracle
calls, the output must be
measurable, its gap must be integrable
under , and
Proved result
OracleTemplate.Convergence LongTails.Setups.HeavyTailedStrongGrowthConvex.spec
OracleTemplate.SplitRobustHeavyTailedAcceleration.budget
Relevant previous results
No qualifying prior reference verified; this is not a proof of novelty.