← All setups

Stationarity with Affine Gradient Variance

Descriptions may be stale. Consult the linked Lean sources.

Stationarity with Affine Gradient Variance

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is Lipschitz, and its objective gap from a given point is bounded. Stochastic gradients are unbiased, have variance bounded by an affine function of the squared gradient norm, and satisfy mean-squared Lipschitz continuity. At queried points x,y∈E, the oracle returns (g(x,ξ),g(y,ξ)), where g is the stochastic gradient map and ξ is a fresh sample shared within the pair. For ε>0, the goal is a measurable output x¯∈E with EP∥∇f(x¯)∥≤ε, where P is the joint law of algorithm and oracle randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, which carries its Borel sigma-algebra. Let Ω be a measurable sample space. The algorithm receives E, Ω, the given point x0∈E, and the parameters L>0,L―,Γ,Λ,Δ≥0,ε>0. It accesses the objective through the oracle described below.

Our assumptions:

Assumption 1 (Smoothness and initial gap). The function f is Fréchet differentiable everywhere on E. For every x,y∈E, ∥∇f(x)−∇f(y)∥≤L∥x−y∥,f(x0)−f(x)≤Δ.

Assumption 2 (Unbiasedness and affine variance). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. For each x∈E, the map g(x,⋅) is Bochner integrable under ν, and ∥g(x,⋅)−∇f(x)∥2 is integrable under ν. They satisfy Eξ∼ν[g(x,ξ)]=∇f(x),Eξ∼ν[∥g(x,ξ)−∇f(x)∥2]≤Γ2∥∇f(x)∥2+Λ2.

Assumption 3 (Mean-squared smoothness). For every x,y∈E, the function ∥g(x,⋅)−g(y,⋅)∥2 is integrable under ν, and Eξ∼ν[∥g(x,ξ)−g(y,ξ)∥2]≤L―2∥x−y∥2.

The oracle uses a sequence (ξk)k≥0 of measurable, independent samples, each with law ν, independent of the algorithm’s randomness. On call k, a query (x,y)∈E×E receives (g(x,ξk),g(y,ξk)). Each such paired reply counts as one oracle call; both evaluations use the same sample. Queries may be chosen adaptively anywhere in E×E.

After the allotted oracle calls, the output x¯ must be measurable, its gradient norm must be integrable under P, and it must satisfy EP[∥∇f(x¯)∥]≤ε.

Results

On a separable real Hilbert space, f is differentiable with L-Lipschitz gradient and f(x0)−inff≤Δ. The jointly measurable, unbiased oracle uses IID samples from p and satisfies Ep∥g(x,ξ)−∇f(x)∥2≤Γ2∥∇f(x)∥2+Λ2 and Ep∥g(x,ξ)−g(y,ξ)∥2≤L¯2∥x−y∥2, with the corresponding integrability assumptions. Here L,ε>0 and L¯,Γ,Λ,Δ≥0. Target: ∫∥∇f(xout(ω))∥dP(ω)≤ε. The setup permits any algorithm using same-sample pair queries.

Affine-variance stochastic optimization with mean-squared smoothness (AffineVarianceMeanSquaredSmooth).
Result Oracle complexity Novelty Limitations
(1) RecursiveMomentumAffineVariance (Ours) (⋆⋆⋆) (review) O(1+Γ4+Λ2/ε2+(L+L¯)(1+Γ)Δ/ε2+(L+L¯)ΛΔ/ε3) pair calls, including initialization.
(2) SGD (Khaled and Richtárik 2020), Cor. 1; A=0, B=1+Γ2, C=Λ2. O(1+(1+Γ2)LΔε2+LΛ2Δε4) gradient calls. Euclidean specialization; no MSS required. (1): for L≤L¯, Λ=0, ΓL≫L¯, Γ3ε2≲L¯Δ, speedup ≍ΓL/L¯. For fixed Λ>0, ε−4→ε−3 as ε→0; crossover ε≲LΛ/L¯. (1) needs MSS and paired evaluations; adds Γ4. Its ε−2 coefficient is worse by ≍(1+Γ)L¯/((1+Γ2)L) when L≤L¯ and L¯≳ΓL.
(3) SPIDER (Chen et al. 2023), Thm. 4, L1→0; derived bound. O(1+Γ2+Λ2/ε2+(1+Γ2)L¯Δ/ε2+(1+Γ)L¯ΛΔ/ε3) pair calls. Euclidean stochastic-gradient specialization; sufficiently small ε with remaining parameters fixed. (1): for L≤L¯, replaces 1+Γ2 by 1+Γ and removes 1+Γ from the ε−3 coefficient. At Γ=0, matches known rate. (1) adds Γ4, absorbed when Γ3ε2≲L¯Δ; coefficient gains need not dominate total cost.
(4) Minibatched SPIDER (Chen et al. 2023), Thm. 4; derived bound, Γ≥1, b≍Γ2. O(1+Γ2+Λ2/ε2+(Γ2L+ΓL¯)Δ/ε2+(ΓL+L¯)ΛΔ/ε3) primitive pair calls, counting every batch; same specialization and small-ε regime as (3). (1): for L≤L¯, ε−3 coefficient gains (ΓL+L¯)/L¯. At Λ=0, speedup ≍ΓL/L¯ if ΓL≫L¯ and Γ3ε2≲L¯Δ; no ε−2 gain when ΓL≲L¯. (1) pays Γ4 instead of Γ2 initialization.

Abbr: MSS: mean-squared smoothness; L¯: its constant; Γ: relative-noise parameter; Λ: additive-noise parameter; Δ: initial objective-gap bound. A pair call evaluates g at two points using one sample (at most two primitive gradient evaluations). P is the execution law, including output randomization. ≲ and ≍ suppress universal factors. In (2), A,B,C are the second-moment coefficients; in (3), L1 is the generalized-smoothness coefficient. In (4), b is the batch size, with effective parameters Γb≤1, Λb=Λ/Γ, L¯b≤L+L¯/Γ up to universal factors.

Chen, Ziyi, Yi Zhou, Yingbin Liang, and Zhaosong Lu. 2023. “Generalized-Smooth Nonconvex Optimization Is as Efficient as Smooth Nonconvex Optimization.” Proceedings of the 40th International Conference on Machine Learning, Proceedings of machine learning research, vol. 202: 5396–427. https://proceedings.mlr.press/v202/chen23ar.html.
Khaled, Ahmed, and Peter Richtárik. 2020. Better Theory for SGD in the Nonconvex World. https://doi.org/10.48550/arXiv.2002.03329.

Lean setup