← All setups

Proximal Storm Strong Growth — Strong-Growth Mean-Square Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Strong-Growth Mean-Square Smooth Convex Minimization · Lean proof

Strong-Growth Mean-Square Smooth Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a separable real Hilbert space E. A given point x0∈E lies within distance R≥0 of a global minimizer x⋆. The oracle returns (g(x,ξ),g(y,ξ)) at a pair (x,y)∈E2, using a shared sample ξ from a probability law p on a measurable space Ω, independently across calls. The estimator g:E×Ω→E is unbiased, with variance bounded by Γ2∥∇f(x)∥2, where Γ≥0, and is mean-square Lipschitz with constant L¯>0. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, averaging over oracle 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, ε, and x0; the objective is accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity and initial distance). The function f is Fréchet differentiable everywhere on E, and for every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 2 (Unbiasedness and strong growth). The map g:E×Ω→E is jointly measurable. For every x∈E, g(x,⋅) is Bochner integrable under p, the squared error ∥g(x,⋅)−∇f(x)∥2 is integrable, and Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤Γ2∥∇f(x)∥2.

Assumption 3 (Mean-square smoothness). For every x,y∈E, the squared difference ∥g(x,⋅)−g(y,⋅)∥2 is integrable under p, and Eξ∼p[∥g(x,ξ)−g(y,ξ)∥2]≤L¯2∥x−y∥2.

More precisely, the oracle samples form a sequence (ξk)k≥0 of measurable, mutually independent random variables, each with law p. Algorithm randomness is independent of this sequence. At call k, the algorithm may query any pair (x,y)∈E×E and receives (g(x,ξk),g(y,ξk)). Each paired reply counts as one oracle call; both components use the same sample.

After the allotted oracle calls, the output x¯ must be measurable, its objective gap f(x¯)−f(x⋆) must be integrable, and EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the algorithm randomness and the oracle sample sequence.

Proved result

⌈2⋅Lbar⋅R2(1+Γ)⋅ε⌉+⋅⌈(1+Γ)2⋅(4810+3200⋅log⁡(1+Γ))⌉+

OracleTemplate.Convergence LongTails.Setups.StrongGrowthMeanSquaredSmoothConvex.spec OracleTemplate.ProximalStorm.budget

Relevant previous results

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