← All setups

Strong Growth Mean Squared Lower Bound — Euclidean Strong-Growth Stochastic Minimization

Descriptions may be stale. Consult the linked Lean sources.

Euclidean Strong-Growth Stochastic Minimization · Lean proof

Euclidean Strong-Growth Stochastic Minimization

We consider minimizing a differentiable convex function f:Rd→R, where d is a positive integer. A given point x0∈Rd lies within distance R>0 of a global minimizer x⋆. The stochastic gradient is unbiased, is Lipschitz in mean square with constant L¯>0, and has variance bounded by Γ2∥∇f(x)∥2 at each x, where Γ≥0. Each oracle call returns gradients at two queried points using a shared sample, with independent, identically distributed samples across calls. For ε>0, the goal is a measurable output x¯∈Rd with integrable objective gap satisfying EP[f(x¯)−f(x⋆)]≤ε, where P is the law of the algorithm’s and oracle’s randomness.

The optimization problem is minx∈Rdf(x), where ∥⋅∥ denotes the Euclidean norm. The parameters satisfy L¯>0,Γ≥0,R>0,ε>0,671088641+Γ2ε≤L¯R2,(L¯R21+Γ2ε)3≤d. Let Ω be a measurable sample space containing distinct points a,b whose singletons are measurable. The algorithm receives d, Ω with its measurable structure, L¯, Γ, R, ε, and x0; the objective and the oracle distribution are accessed through oracle replies.

Our assumptions:

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

Assumption 2 (Unbiasedness and strong growth). There exist a probability measure ν on Ω and a jointly measurable map g:Rd×Ω→Rd. For every x∈Rd, the map g(x,⋅) is Bochner integrable, the squared error ∥g(x,⋅)−∇f(x)∥2 is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤Γ2∥∇f(x)∥2.

Assumption 3 (Mean-square smoothness and paired sampling). For every x,y∈Rd, the squared difference ∥g(x,⋅)−g(y,⋅)∥2 is integrable and satisfies Eξ∼ν[∥g(x,ξ)−g(y,ξ)∥2]≤L¯2∥x−y∥2. The oracle uses a sequence (ξk)k≥0 of measurable, independent random variables, each with law ν, independent of the algorithm’s randomness. At call k, a query (xk,yk)∈Rd×Rd returns (g(xk,ξk), g(yk,ξk)). Both components use the same sample, and the pair counts as one oracle call.

Queries may be chosen adaptively anywhere in Rd×Rd. After the allotted paired oracle calls, the output x¯ must be measurable, its objective gap must be integrable under P, and it must satisfy EP[f(x¯)−f(x⋆)]≤ε.

Proved result

⌊(1+Γ2)⋅1+Γ2⋅Lbar⋅R2ε8192⌋+

OracleTemplate.NonConvergence LongTails.Setups.EuclideanStrongGrowthMeanSquared.spec
  LongTails.Theorems.StrongGrowthMeanSquaredLowerBound.budget

Relevant previous results

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