← All setups

Stochastic Smooth Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

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.

Results

Convex differentiable f:E→R on a second-countable real Hilbert space with its Borel σ-algebra; ∇f is L-Lipschitz and a global minimizer x⋆ satisfies ∥x0−x⋆∥≤R. Here L,ε>0 and R,σ≥0. The jointly measurable oracle g has integrable values and squared errors, with ∫g(x,ω)dp(ω)=∇f(x) and ∫∥g(x,ω)−∇f(x)∥2dp(ω)≤σ2 for a probability law p. Samples are IID, P=p⊗N. The target is measurable output x^ with integrable gap and ∫[f(x^)−f(x⋆)]dP≤ε. The setup imposes no algorithm restriction.

Stochastic smooth convex minimization: StochasticSmoothAndConvex.
Result Oracle complexity Novelty Limitations
(1) AcceleratedStochasticConvex (Ours) (review) O(1+LR2ε+σ2R2ε2)
(2) SgdConvex (Ours) (review) O(1+LR2ε+σ2R2ε2)
(3) AC-SA (Ghadimi and Lan 2012), Prop. 7, (4.10)–(4.11). Unconstrained Euclidean specialization. O(1+LR2ε+σ2R2ε2) (1): Matches known rate; Lean formalization in Hilbert space of a dimension-free analysis. (2): Matches when σ2≥Lε. (2): At σ=0, LR2/ε≥1, costs O(LR2/ε) versus O(LR2/ε).
(4) Smooth SGD (Bubeck 2015), Thm. 6.3 proof. Derived bound: unconstrained Euclidean quadratic mirror map. O(1+LR2ε+σ2R2ε2) (2): Matches known rate; Lean formalization. Step omits R, but stopping still needs it; no reduction in required information.
(5) AC-SA (Ghadimi and Lan 2012), Prop. 7, (4.5), (4.10)–(4.12). Bounded convex X⊂Rd. O(1+LR2ε+σ2(R2+DX2)ℓ2ε2) stochastic gradients and projections onto X; Pr{f(x^)−minXf≤ε}≥1−δ. Requires DX<∞, σ>0, and ∫exp⁡(∥g−∇f∥2/σ2)dp≤e at every x∈X. (1), (2): No established improvement for this probability target. Different domain and accuracy guarantees prevent direct rate comparison. (1), (2): Expectation only; no corresponding high-probability guarantee.

Abbr: Costs count individual stochastic-gradient calls; in (5) each call also uses one projection. R bounds initial distance to the relevant minimizer; σ2 is the variance bound; ε is objective-gap accuracy. In (5), DX=supx∈X∥x−x⋆∥, δ∈(0,1), ℓ=1+log⁡(1/δ). Euclidean specializations use V(u,v)=∥u−v∥2/2 and zero composite term; (4) uses initial Bregman distance rather than domain diameter.

Bubeck, Sébastien. 2015. “Convex Optimization: Algorithms and Complexity.” Foundations and Trends in Machine Learning 8 (3–4): 231–358. https://doi.org/10.1561/2200000050.
Ghadimi, Saeed, and Guanghui Lan. 2012. “Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework.” SIAM Journal on Optimization 22 (4): 1469–92. https://doi.org/10.1137/110848864.

Lean setup