← All setups

Finite Variance Generalized Accelerated Convex — Finite-Variance Generalized Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Finite-Variance Generalized Smooth Convex Minimization · Lean proof

Finite-Variance Generalized Smooth Convex Minimization

We consider minimizing a 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 an unbiased stochastic gradient with variance at most σ2, where σ≥0, using independent, identically distributed samples. 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 the samples and independent 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 on E, and its gradient ∇f:E→E is Fréchet differentiable. For every x,y∈E and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). Generalized smoothness means that ∥∇2f(x)∥op≤L0+L1∥∇f(x)∥,x∈E, where ∇2f(x) is a bounded linear operator from E to E.

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 (Finite-variance stochastic gradients). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable under ν, the squared error ∥g(x,⋅)−∇f(x)∥2 is integrable, and Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤σ2. At call k≥0, a query x∈E receives g(x,ξk). The sample variables (ξk)k≥0 are measurable and mutually independent, each with law ν, and their joint law is independent of the algorithm’s randomness.

Queries may be made at any point of E. After the allotted oracle calls, the algorithm must return a measurable output x¯ satisfying P(f(x¯)−f(x⋆)>ε)≤δ.

Proved result

⌈(222⋅(1+L0⋅R2ε+log⁡(4+4⋅Δε)+(L1⋅R⋅log⁡(4+4⋅Δε))23)+247⋅σ2⋅R2⋅(log⁡(exp⁡(1)δ))2ε2)⋅log⁡(exp⁡(1)⋅(1+L0⋅R2ε+L1⋅R+log⁡(4+4⋅Δε))δ)⌉+

OracleTemplate.Convergence LongTails.Setups.FiniteVarianceGeneralizedSmoothAndConvex.spec
  OracleTemplate.RobustGeneralized.FiniteVarianceGeneralizedAcceleratedConvex.budget

Relevant previous results

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