← All setups

Nonconvex Optimization with Symmetric Noise

Descriptions may be stale. Consult the linked Lean sources.

Nonconvex Optimization with Symmetric Noise

We consider minimizing a differentiable, possibly nonconvex function f:E→R on a separable real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and a given point x0∈E satisfies f(x0)−infx∈Ef(x)≤Δ, where Δ≥0. The oracle returns g(x,ξ)∈E, with symmetric noise having tail radius r≥0 and relative-energy regularity parameter κ≥0. Consecutive pairs of calls share a sample ξ, independently across pairs. For ε>0, the goal is a measurable output x¯∈E satisfying E∥∇f(x¯)∥≤ε, where expectation includes sampling and independent algorithm randomness.

The optimization problem is infx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, equipped with its Borel sigma-algebra. Let Ω be a measurable sample space. The algorithm receives E, Ω, L, κ, r, Δ, ε, and x0; it accesses f through the oracle described below.

Our assumptions:

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

Assumption 2 (Symmetry and tail radius). There exist a probability measure ν on Ω and a jointly measurable map g:E×Ω→E. Define the noise by e(x,ω)=g(x,ω)−∇f(x). For every x∈E, under ξ∼ν, e(x,ξ)=d−e(x,ξ),Pξ∼ν(∥e(x,ξ)∥>r)≤164. Here equality in distribution is equality of the induced probability measures on E.

Assumption 3 (Relative-energy regularity). For every x,y∈E, the noise evaluated with the same sample satisfies Eξ∼ν[(∥e(x,ξ)−e(y,ξ)∥r+∥e(x,ξ)∥+∥e(y,ξ)∥)2]≤κ2∥x−y∥2. The ratio is defined to be zero when its denominator is zero.

Oracle queries may be made at any point of E. Let (ξj)j≥0 be measurable, mutually independent sample variables, each with law ν, and independent of the algorithm’s randomness. Index calls starting at zero. At query xk∈E, call k returns g(xk,ξ⌊k/2⌋). Thus calls 2j and 2j+1 use the same sample, including when the second query depends on the first reply.

After the allotted oracle calls, the output x¯ must be measurable and satisfy EP∥∇f(x¯)∥≤ε,∥∇f(x¯)∥∈L1(P), where P is the joint law of the samples and the algorithm’s independent randomness.

Results

On a separable real Hilbert space with its Borel structure, f is differentiable, ∇f is L-Lipschitz, and f(x0)−inff≤Δ. The jointly measurable oracle g(x,ξ) has marginally symmetric noise ζx=g(x,ξ)−∇f(x) with Pr(∥ζx∥>r)≤1/64 and E[(∥ζx−ζy∥/(r+∥ζx∥+∥ζy∥))2]≤κ2∥x−y∥2. Samples are IID across query pairs, with a shared sample within each pair; no noise moments are assumed. Here L,ε>0 and r,κ,Δ≥0. The target is a measurable output x^ with integrable gradient norm and ∫∥∇f(x^(ω))∥dP(ω)≤ε, for the execution law P.

Comparison for RelativeEnergySymmetricNonconvex.
Result Oracle complexity Novelty Limitations
(1) FairRelativeEnergyNonconvex (Ours) (⋆⋆⋆) (review) O((1+log⁡A)[A+min{κε,L}(r+ε)2Δε4])
(2) NSGD-MVR (Fradin et al. 2026, Thm. 4.2, v2), 1<p<2, q=2 O(1+(σpε)p/(p−1)+(L+δ)Δε2
+δΔε2(σpε)p/[2(p−1)]). Special case: Rd, unbiased p-moment noise and mean-square similarity δ.
(1): On symmetric overlap, σp≫ε, initialization and tracking powers become 2 and 1, up to logs. At p=3/2, fixed positive L,Δ,δ,σp: O(ε−7/2) becomes O(ε−3log⁡(1/ε)). Scope: momentless noise via robust-location coupling. (1) needs exact symmetry; choose r=max{641/pσp,ε}, κ=δ/r on the overlap. Fair-root computation is noncomputable and uncounted.
(3) NSGD-MVR (Fradin et al. 2026, Thm. 4.2, v2), p=q=2 O(1+σ22+(L+δ)Δε2+δσ2Δε3). Special case: Rd, unbiased finite-variance noise and mean-square similarity δ. (1): Matches polynomial rate on symmetric overlap for σ2≥ε; extends to noise with undefined means using a central quantile and relative energy. (1) needs symmetry and pays an extra 1+log⁡A; overlap: r=max{8σ2,ε}, κ=δ/r. Large universal budget constant.
(4) N-SGD (Armacki et al. 2026, Thm. 1, v2); derived bound O(Dρ2ε4[1+log(Dρε2)]2) fresh calls, 0<ε≤1; Pr(mink≤N∥∇f(xk)∥≤ε)≥1−ρ. Special case: Rd, symmetric conditional densities uniformly positive near zero; bounded joint clipping or normalization, with admissible a/t+1 steps. (1): No density condition. Rates are not comparable in (r,κ); the density constants in (4) have no established conversion. (1) needs shared-sample pairs and relative-energy regularity; guarantees expectation rather than high probability.

Abbr: The relative-energy ratio is zero when its denominator is zero. A=((r+ε)2+LΔ)/ε2; σpp bounds E∥ζx∥p; mean-square similarity means E∥ζx−ζy∥2≤δ2∥x−y∥2. Costs count individual oracle replies, including batches, paired replies and unused refresh replies. For (4), ρ∈(0,1) is failure probability, C bounds the nonlinearity Ψ, and the density-dependent β1,β2>0 satisfy ⟨EΨ(y+ζx),y⟩≥min{β1∥y∥,β2∥y∥2}; β=min{β1,β2}, a=min{1,β2/(8C2),β1/[16C2(LC+2LΔ/2)]}, and Dρ=1+(Δ+log⁡(1/ρ))/(aβ)+aLC2/β.

Armacki, Aleksandar, Dragana Bajović, Dušan Jakovetić, and Soummya Kar. 2026. Sharp High-Probability Rates for Nonlinear SGD Under Heavy-Tailed Noise via Symmetrization. https://doi.org/10.48550/arXiv.2507.09093.
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.

Lean setup