← All setups

Nonconvex Optimization with Curvature-Aligned Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Curvature-Aligned Noise

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a finite-dimensional real inner product space E. The objective admits global quadratic upper models with bounded curvature along its gradient and a bounded initial gap to a lower bound. The oracle returns an unbiased stochastic gradient at each query, using independent, identically distributed samples. Its noise has bounded variance and bounded expected curvature relative to its second moment. For ε>0, the goal is a measurable output x¯∈E with E∥∇f(x¯)∥≤ε, where expectation includes oracle and independent algorithm randomness.

The optimization problem is infx∈Ef(x). Write ⟨⋅,⋅⟩ for the inner product and ∥⋅∥ for its induced norm. Fix a starting point x0∈E and parameters Lg>0,Lξ≥0,σ≥0,Δ≥0,ε>0. The algorithm receives E, the measurable sample space Ω, x0, and all five parameters; the objective and oracle distribution are accessed through oracle replies.

Our assumptions:

Assumption 1 (Quadratic upper models). The function f is Fréchet differentiable everywhere. There exists a family of continuous linear maps Q(x):E→E such that, for every x,u∈E, f(x+u)≤f(x)+⟨∇f(x),u⟩+12⟨Q(x)u,u⟩,⟨Q(x)∇f(x),∇f(x)⟩≤Lg∥∇f(x)∥2.

Assumption 2 (Initial objective gap). There exists flow∈R such that f(x)≥flowfor every x∈E,f(x0)−flow≤Δ.

Assumption 3 (Unbiased curvature-aligned noise). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. Define the noise by ζ(x,ω)=g(x,ω)−∇f(x). For every fixed x∈E, the map g(x,⋅) is Bochner integrable under ν, and both ∥ζ(x,⋅)∥2 and ⟨Q(x)ζ(x,⋅),ζ(x,⋅)⟩ are integrable under ν. For ω∼ν, they satisfy Eω∼ν[g(x,ω)]=∇f(x),Eω∼ν∥ζ(x,ω)∥2≤σ2,Eω∼ν⟨Q(x)ζ(x,ω),ζ(x,ω)⟩≤LξEω∼ν∥ζ(x,ω)∥2. At call k≥0, a query x∈E returns g(x,ξk), where the measurable sample variables (ξk)k≥0 are mutually independent and each has law ν. 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¯ must be measurable, its gradient norm must be integrable, and it must satisfy EP[∥∇f(x¯)∥]≤ε, where P is the joint law of the oracle samples and the algorithm’s randomness.

Results

On a finite-dimensional real inner-product space, f is differentiable, f≥flow, and f(x0)−flow≤Δ. For every x,u, a linear map Q(x) satisfies f(x+u)≤f(x)+⟨∇f(x),u⟩+12⟨Q(x)u,u⟩ and ⟨Q(x)∇f(x),∇f(x)⟩≤Lg∥∇f(x)∥2. The jointly measurable oracle g uses IID samples with law P0, is integrable and unbiased, and has integrable noise moments satisfying EP0∥ζ∥2≤σ2 and EP0⟨Q(x)ζ,ζ⟩≤LξEP0∥ζ∥2. Here Lg>0, Lξ,σ,Δ≥0, ε>0. Target: measurable output with integrable gradient norm and ∫∥∇f(x^)∥dP≤ε. (1) constructs constant-step SGD with a uniformly random iterate; the setup imposes no algorithm restriction. Prior costs are converted from expected squared-gradient accuracy to this target.

Curvature-aligned stochastic nonconvex optimization: CurvatureAlignedNoiseNonconvex.
Result Oracle complexity Novelty Limitations
(1) CurvatureAlignedSgdNonconvex (Ours) (⋆⋆) (review) O(1+LgΔε2+Lξσ2Δε4)
(2) Randomized SGD (Ghadimi and Lan 2013, Cor. 2.2). Special case: L-Lipschitz gradient. O(1+LΔε2+Lσ2Δε4) (1): Lg,Lξ replace L. For Lg,Lξ≤L, noise-dominated costs improve by Ω(L/Lξ) when Lξσ2≥Lgε2 and Lξσ2Δ/ε4≥1. Scope: no Lipschitz-gradient requirement. Accuracy exponents unchanged; formally verified refinement. (1)’s sharper constants require certified global Q and noise alignment; a local Hessian alone is insufficient.
(3) SGD (Liu et al. 2025, Thm. D.3). Special case: ∥∇f(x)−∇f(y)∥D−1≤∥x−y∥D, D=diag(L)>0, Eζi2≤σi2. O(1+∥L∥∞Δε2+∥L∥∞∥σ∥22Δε4), batch size 1. (1): for admissible Q=diag(L), Lg≤∥L∥∞, σ2=∥σ∥22, Lξσ2=S, noise coefficient becomes S. Gain ∥L∥∞∥σ∥22/S when SΔ/ε4≥max{1,∥L∥∞Δ/ε2}, potentially d-fold. Scope: state-dependent, nondiagonal Q.

Abbr: Costs count individual stochastic-gradient calls. ζ=g(x,ω)−∇f(x); P is the execution probability law, including output randomization; Δ bounds the initial objective gap. L=(Li)i=1d, σ=(σi)i=1d, S=∑iLiσi2, ∥v∥D2=v⊤Dv.

Ghadimi, Saeed, and Guanghui Lan. 2013. “Stochastic First- and Zeroth-Order Methods for Nonconvex Stochastic Programming.” SIAM Journal on Optimization 23 (4): 2341–68. https://doi.org/10.1137/120880811.
Liu, Yuxing, Rui Pan, and Tong Zhang. 2025. “AdaGrad Under Anisotropic Smoothness.” The Thirteenth International Conference on Learning Representations. https://openreview.net/forum?id=4GT9uTsAJE.

Lean setup