← All setups

Stochastic Generalized Accelerated Convex — Stochastic Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Generalized Smooth Convex Minimization · Lean proof

Stochastic Generalized Smooth Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a separable real Hilbert space E. The function f is (L0,L1)-smooth, with L0>0 and L1≥0. A given point x0∈E has distance at most R>0 and objective gap at most Δ>0 from a global minimizer x⋆. The oracle returns unbiased stochastic gradients with variance at most σ2 and an exponential squared-error bound, where σ≥0, using independent identically distributed samples. Given ε>0 and δ∈(0,1), the goal is a measurable output x¯ satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ over oracle and algorithm randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. Let Ω be the measurable sample space. The algorithm receives E, Ω, x0, L0, L1, R, Δ, σ, ε, and δ; the objective and sampling distribution are accessed through the oracle.

Our assumptions:

Assumption 1 (Convexity and generalized smoothness). The function f is Fréchet differentiable everywhere, its gradient is Fréchet differentiable, and for every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y),∥∇2f(x)∥op≤L0+L1∥∇f(x)∥. Here ∇2f(x):E→E is the derivative of the gradient.

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

Assumption 3 (Light-tailed stochastic gradients). There are a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable, its squared error is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2. When σ>0, the exponential below is integrable and satisfies, for every x∈E, Eξ∼ν[exp⁡(∥g(x,ξ)−∇f(x)∥2σ2)]≤e. When σ=0, the variance condition gives g(x,ξ)=∇f(x) for ν-almost every ξ, for each fixed x.

The samples (ξk)k≥0 are measurable, mutually independent random variables with common law ν under a joint probability law Q. At call k, a query x∈E receives g(x,ξk). The algorithm’s randomness is independent of the entire sample sequence.

Queries may be made at any point of E. After the allotted oracle calls, the output x¯∈E must be measurable and satisfy P(f(x¯)−f(x⋆)>ε)≤δ, where P is the joint law of the algorithm’s randomness and the oracle samples with law Q.

Proved result

{0Δ≤ε2⋅⌈16384⋅(1+L0⋅R2ε+min{⌈(L1⋅R)23⌉+⋅log⁡(4+4⋅Δε),log⁡(4+4⋅Δε)+(L1⋅R⋅log⁡(4+4⋅Δε))23})⌉++⌈1073741824⋅σ2⋅R2⋅log⁡(exp⁡(1)δ)ε2⌉+otherwise

OracleTemplate.Convergence LongTails.Setups.StochasticGeneralizedSmoothAndConvex.spec
  OracleTemplate.StochasticGeneralized.budget

Relevant previous results

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