← All setups

Accelerated Stochastic Convex — Stochastic Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Stochastic Smooth Convex Minimization · Lean proof

Stochastic Smooth Convex Minimization

We consider minimizing a differentiable convex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, where 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 with variance at most σ2, where σ≥0, using independent samples across calls. For ε>0, the goal is a measurable output x¯∈E with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, where expectation includes both algorithm and oracle randomness.

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

Our assumptions:

Assumption 1 (Convexity). For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y).

Assumption 2 (Smoothness). The function f is Fréchet differentiable everywhere on E, and its gradient satisfies ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

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

Assumption 4 (Stochastic gradients). There exist a probability measure p on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable under p, the squared error ∥g(x,⋅)−∇f(x)∥2 is integrable under p, and Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤σ2. At call k, a query xk∈E receives g(xk,ξk), where (ξk)k≥0 are independent with common law p and are independent of the algorithm’s randomness.

Queries may be made at any point of E and may depend on previous replies. After the allotted oracle calls, the output x¯ must be measurable and its objective gap must be integrable, with EP[f(x¯)−f(x⋆)]≤ε, where P is the joint law of the algorithm’s randomness and the oracle samples.

Proved result

max{1,⌈16⋅L⋅R2ε+64⋅σ2⋅R2ε2⌉+}

OracleTemplate.Convergence LongTails.Setups.StochasticSmoothAndConvex.spec
  OracleTemplate.StochasticGradient.AcceleratedStochasticConvex.budget

Relevant previous results