← All setups

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 f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E lies within distance R≥0 of a global minimizer x⋆. At x, the oracle returns an unbiased stochastic gradient g(x,ξ) using independent samples ξ from a probability measure μ on a measurable space Ω. Its noise has pth moment at most ρ∥∇f(x)∥p, where 1<p≤2 and ρ≥0. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, averaging over sampling and algorithm randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which is equipped with its Borel sigma-algebra. The algorithm receives E, Ω, L, R, ρ, p, ε, and x0; access to f is through the stochastic gradient oracle.

Our assumptions:

Assumption 1 (Convexity and smoothness). The function f is Fréchet differentiable everywhere on E. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇f(x)−∇f(y)∥≤L∥x−y∥.

Assumption 2 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 3 (Relative moment and independent sampling). The map g:E×Ω→E is jointly measurable. For each x∈E, the map g(x,⋅) is Bochner integrable under μ, and ∥g(x,⋅)−∇f(x)∥p is integrable under μ. They satisfy Eξ∼μ[g(x,ξ)]=∇f(x),Eξ∼μ[∥g(x,ξ)−∇f(x)∥p]≤ρ∥∇f(x)∥p. The oracle uses a sequence (ξk)k≥0 of measurable, mutually independent random variables, each with distribution μ. At call k, a query x∈E receives g(x,ξk). The algorithm’s randomness is independent of this sample sequence.

Queries may be made at any point of E. Let P denote the joint law of the sample sequence and the algorithm’s randomness. After the allotted oracle calls, the output x¯ must be measurable, its gap f(x¯)−f(x⋆) must be integrable under P, and EP[f(x¯)−f(x⋆)]≤ε.

Proved result

130⋅⌈128⋅max{1,L⋅R2ε}⌉++2⋅⌈(17179869184⋅ρ)1p−1⌉+⋅(130+⌈2⋅log⁡(max{1,L⋅R2ε})⌉+)⋅⌈128⋅(max{1,L⋅R2ε})p3⋅p−2⌉+

OracleTemplate.Convergence LongTails.Setups.HeavyTailedStrongGrowthConvex.spec
  OracleTemplate.SplitRobustHeavyTailedAcceleration.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.