← All setups

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 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 minimizer x⋆. The oracle returns unbiased stochastic gradients from independent, identically distributed samples, with error α-moment bounded by σ0α+σα∥∇f(x)∥α at x, where 1<α≤2 and σ0,σ≥0. For ε>0 and δ∈(0,1), the goal is a measurable output x¯∈E satisfying P{f(x¯)−f(x⋆)>ε}≤δ, where P is the joint law of sampling and independent 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. Let Ω be a measurable sample space. The algorithm receives E, Ω, L, R, σ, σ0, α, ε, δ, and x0; the objective is accessed through the 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 (Sampling and affine moment bound). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. At the kth query x∈E, the oracle returns g(x,ξk), where the measurable random variables (ξk)k≥0 are mutually independent with common law ν, and are independent of the algorithm’s randomness. For every x∈E, the map g(x,⋅) is Bochner integrable and ∥g(x,⋅)−∇f(x)∥α is integrable with respect to ν. They satisfy Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥α]≤σ0α+σα∥∇f(x)∥α.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯ must be measurable and satisfy the high-probability objective-gap requirement P{f(x¯)−f(x⋆)>ε}≤δ.

Proved result

⌈2256⋅αα−1⋅((1+σ)αα−1⋅(4+L⋅R2ε)α3⋅α−2+(σ0⋅(4L⋅R+Rε))αα−1)⋅(log⁡(20+αα−1+L⋅R2ε+1δ))αα−1+1⌉+

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.