← All setups

Nonconvex Optimization with Hölder Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Hölder Noise

We consider a differentiable, possibly nonconvex function f:Rd→R with L-Lipschitz gradient, where d≥1 and L>0. A given point x0 satisfies f(x0)−infxf(x)≤Δ, where Δ≥0. Each oracle call at (x,y) returns (g(x,ξ),g(y,ξ)) using a fresh independent binary sample ξ. The estimator g is unbiased, with variance at most σ2 and centered increments of mean square at most M∥x−y∥2ν, where σ,M≥0, 0<ν≤1, and ∥⋅∥ is the Euclidean norm. For ε>0, the goal is a measurable output x¯ satisfying EP∥∇f(x¯)∥≤ε, where P is the joint law of sampling and independent algorithm randomness.

The underlying optimization problem is infx∈Rdf(x). The algorithm receives d,L,M,ν,σ,Δ,ε, and x0∈Rd. We restrict these parameters further to 64ε2≤LΔ,d≥⌈230(1+LΔε2)3(1+σ2ε2)⌉.

Our assumptions:

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

Assumption 2 (Unbiased gradients and Hölder noise). There exist a probability distribution p on {0,1} and a jointly measurable map g:Rd×{0,1}→Rd. Define the centered error by e(x,ξ)=g(x,ξ)−∇f(x). For every x,y∈Rd, Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p∥e(x,ξ)∥2≤σ2,Eξ∼p∥e(x,ξ)−e(y,ξ)∥2≤M∥x−y∥2ν. Here g(x,⋅) is Bochner integrable, and both squared norms in these expectations are integrable under p.

The sample sequence (ξk)k≥0 consists of measurable, mutually independent random variables with common law p, independent of the algorithm’s randomness. On call k, the algorithm may query any pair (xk,yk)∈Rd×Rd, based on its randomness and previous replies. The oracle returns (g(xk,ξk), g(yk,ξk)). Thus the two replies share a sample, and each such pair counts as one oracle call.

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

Results

On Rd, f is differentiable with L-Lipschitz gradient and f(x0)−inff≤Δ. Here L,ε>0, M,σ,Δ≥0, 0<ν≤1, LΔ≥64ε2, and d≥⌈230(1+LΔ/ε2)3(1+σ2/ε2)⌉. A call returns (g(x,ω),g(y,ω)) with a fresh IID sample ω∈{0,1} of law p. The jointly measurable oracle satisfies ∫g(x,ω)dp=∇f(x), ∫∥e(x,ω)∥2dp≤σ2, and ∫∥e(x,ω)−e(y,ω)∥2dp≤M∥x−y∥2ν, with the corresponding integrability assumptions. The target is a measurable output with integrable gradient norm and ∫∥∇f(x^)∥dP≤ε. All randomized algorithms are allowed; the hard instance may depend on the algorithm and budget, but not its realized seed.

Lower bounds (necessary budgets) for HolderNoiseNonconvexLower.
Result Oracle complexity Novelty Limitations
(1) HolderNoiseMinimaxLowerBound (Ours) (⋆⋆) (review) Lower bound; failure through pair-call budget O(LΔ+σ2ε2+min{LΔσ2ε4,ΔHνε3}).
(2) (Arjevani et al. 2023), Thm. 3, (24); mean-squared-smooth special case Lower bound; failure through O(ΔL¯σ/ε3+σ2/ε2) pair calls (K=2). Requires ∫∥g(x)−g(y)∥2dp≤L¯2∥x−y∥2 and ε≤c′L¯Δ. (1): extends hardness to every 0<ν≤1. For fixed positive parameters: ε−(4−2ν) when ν<1/2, ε−3 otherwise. Matches stochastic terms at ν=1, M≍L¯2, L≥L¯ε/σ. (1): larger dimension requirement versus O~(Δ2L¯2/ε4); 2−80 hardness factor.
(3) (Arjevani et al. 2023), Thm. 3, (23); bounded-variance superclass Lower bound; failure through O(LΔσ2/ε4) pair calls (K=2). No spatial regularity; L,Δ,σ>0, ε≤c′LΔ. (1): re-establishes hardness inside the Hölder subclass; recovers the LΔσ2/ε4 branch for sufficiently large M. Superclass hardness does not imply subclass hardness; rates are not directly comparable.
(4) (Jin 2026), Thm. 4.1; bounded-error, single-point model Lower bound; failure through O(LΔ/ε2+LΔσ2/ε4) single-point calls. Requires ∥e(x,ω)∥≤σ almost surely, L,Δ,σ>0, ε≤2−20min{σ,LΔ}; worst case over finite dimensions. (1): proves Hölder-class hardness despite paired queries. (4) uses discontinuous noise and one point per fresh sample; rates are not comparable.

Abbr: e(x,ω)=g(x,ω)−∇f(x); P is the execution law, including algorithm randomness; Hν=max{M(L/ε)1−2ν,M1/(2ν)σ2−1/ν}. Real powers use the setup’s convention 0a=0 for a≠0. A displayed O(B) failure budget means failure through ⌊cB⌋ for a universal c>0, hence a necessary Ω(B) budget; c=2−80 in (1). Constants c′>0 are universal; O~ suppresses logarithms; L¯ bounds raw mean-squared gradient increments; K is points per common sample.

Arjevani, Yossi, Yair Carmon, John C. Duchi, Dylan J. Foster, Nathan Srebro, and Blake Woodworth. 2023. “Lower Bounds for Non-Convex Stochastic Optimization.” Mathematical Programming 199: 165–214. https://doi.org/10.1007/s10107-022-01822-7.
Jin, Jikai. 2026. A Tight Lower Bound for Smooth Nonconvex Stochastic Optimization with Bounded Gradient Noise. https://doi.org/10.48550/arXiv.2608.09004.

Lean setup