← All setups

Mean-Squared Hölder Nonconvex Optimization

Descriptions may be stale. Consult the linked Lean sources.

Mean-Squared Hölder Nonconvex Optimization

We consider finding an approximate stationary point of a differentiable, possibly nonconvex 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 satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ≥0. At a pair x,y∈E, the oracle returns unbiased gradient estimates g(x,ξ),g(y,ξ) using one shared sample ξ, with independent samples across calls. Their variance is bounded by σ2, and their mean-squared difference by M∥x−y∥2ν, where σ,M≥0 and ν∈[1/2,1]. For ε>0, the goal is a measurable output x¯∈E with E∥∇f(x¯)∥≤ε, averaging over oracle and independent algorithm randomness.

The underlying optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, the measurable sample space Ω, x0, and all parameters L,M,ν,σ,Δ,ε.

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 (Unbiased stochastic gradients). There exist a probability measure p on Ω and a jointly measurable map g:E×Ω→E. For every x∈E, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−∇f(x)∥2 is integrable under ξ∼p, with Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤σ2.

Assumption 3 (Mean-squared Hölder continuity). For every x,y∈E, the random variable ∥g(x,ξ)−g(y,ξ)∥2 is integrable under ξ∼p, and Eξ∼p[∥g(x,ξ)−g(y,ξ)∥2]≤M∥x−y∥2ν.

At call k≥0, a query (xk,yk)∈E×E receives the pair (g(xk,ξk),g(yk,ξk)). The measurable samples (ξk)k≥0 are mutually independent with common law p, and are independent of the algorithm’s randomness. Both evaluations within a pair use the same sample; one returned pair counts as one oracle call. Queries may depend on preceding replies.

After the allotted 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 second-countable real Hilbert space with its Borel measurable structure, f is differentiable, ∇f is L-Lipschitz, and f(x0)−inff≤Δ. Here L,ε>0, M,σ,Δ≥0, and ν∈[1/2,1]. The jointly measurable oracle g uses IID samples of law p, is unbiased, and satisfies Ep∥g(x,ξ)−∇f(x)∥2≤σ2 and Ep∥g(x,ξ)−g(y,ξ)∥2≤M∥x−y∥2ν, with the stated moments integrable. A pair query evaluates two points using the same sample. The target is a measurable output with ∫∥∇f(xout(ω))∥dP(ω)≤ε, where P is the execution law. Comparisons to cited prior-work statements use E=Rd.

Comparison for MeanSquaredHolderNonconvex.
Result Oracle complexity Novelty Limitations
(1) DyadicVarianceReductionHolder (Ours) (⋆⋆⋆) (review) O(ℓ2[1+LΔ+σ2ε2
+ΔM1/(2ν)σ2−1/νε3]) pair calls
(2) SGD (Ghadimi and Lan 2013), Cor. 2.2 O(1+LΔε2+LΔσ2ε4) single-point calls (1): Leading noise term gains Lσ1/νℓ2M1/(2ν)ε when this exceeds one; total savings require noise dominance, including initialization costs. (1): Needs Hölder regularity, paired access, and M,ν in addition; only first-moment accuracy. Worse noise term when M1/(2ν)ε≳Lσ1/ν.
(3) SPIDER (Fang et al. 2018), Thm. 1; special case ν=1, ε≤σ O(1+σ2ε2+ΔMσε3) pair calls, including refresh batches (1): Scope extends mean-squared Lipschitz regularity to ν∈[1/2,1), including kinked sample losses with bounded conditional density. (1): Extra ℓ2 at ν=1, on the common parameterization L=M.
(4) Derived bound: SPIDER recursion (Fang et al. 2018) under the stated Hölder condition O(1+σ2+LΔε2
+ΔσML1−νε4−ν) pair calls, including refresh batches
(1): Leading-term gain ℓ−2(Lσ1/νM1/(2ν)ε)1−ν when greater than one. At ν=1/2, fixed positive parameters: O(ε−7/2) becomes O(ℓ2ε−3). (1): Extra ℓ2 on the shared initialization terms; no uniform total-cost dominance.
(5) NSGD-MVR (Fradin et al. 2026), Thm. 4.1, p=2, q=1; overlap with 1-WAS only O(1+σ2+L¯Δε2
+L¯Δσ2ε4) pair calls, including initial batch
(1): Ramp overlap, ν=1/2, L¯=2κR2, M=2κR3, σ≍R: O(κR4Δ/ε4) becomes O(ℓ2κR3Δ/ε3) for fixed positive parameters as ε→0. (1): Requires the second-moment Hölder bound. 1-WAS and Hölder classes are incomparable; rates are not comparable outside their overlap.
(6) Adaptive STORM (Cutkosky and Orabona 2020), Thm. 1; sample gradients L¯-Lipschitz and bounded by G>0 Derived total bound:
O(1+G2(H+ℓS)3/2ε2+σε3) pair calls
(1): Scope extends to Hölder sample regularity with ν<1, including kinked sample losses. (1): Needs known σ and anchor batches; (6) needs neither.

Abbr: ℓ=1+log⁡(1+LΔ/ε2); Δ is the initial gap bound, σ2 the variance bound, and (M,ν) the mean-squared Hölder parameters. Pair calls cost two component-gradient evaluations; all batches are counted. 00=1. 1-WAS means Ep∥g(x,ξ)−g(y,ξ)∥≤L¯∥x−y∥. In the ramp example, R bounds the data norm and κ bounds the conditional density. For (6), H=1+(L¯Δ+σ2)/G2 and ℓS=1+log⁡(1+G2H3/2/ε2+σ/ε3); L¯ bounds sample smoothness and G bounds sample-gradient norms.

Cutkosky, Ashok, and Francesco Orabona. 2020. Momentum-Based Variance Reduction in Non-Convex SGD. https://doi.org/10.48550/arXiv.1905.10018.
Fang, Cong, Chris Junchi Li, Zhouchen Lin, and Tong Zhang. 2018. “SPIDER: Near-Optimal Non-Convex Optimization via Stochastic Path-Integrated Differential Estimator.” Advances in Neural Information Processing Systems 31. https://proceedings.neurips.cc/paper_files/paper/2018/hash/1543843a4723ed2ab08e18053ae6dc5b-Abstract.html.
Fradin, Adrien, Abdurakhmon Sadiev, Laurent Condat, and Peter Richtárik. 2026. Tight Lower Bounds and Optimal Algorithms for Stochastic Nonconvex Optimization with Heavy-Tailed Noise. https://doi.org/10.48550/arXiv.2512.18713.
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.

Lean setup