← All setups

Clipped Subgradients with Heavy-Tailed Noise

Descriptions may be stale. Consult the linked Lean sources.

Clipped Subgradients with Heavy-Tailed Noise

We consider minimizing a possibly nonconvex function f:E→R over a closed convex set D in a finite-dimensional real inner product space E. The function is ρ-weakly convex, with ρ>0, and admits bounded subgradients and a lower bound with controlled gap at a given starting point. The oracle returns unbiased stochastic subgradients with a bounded centered moment of order α∈(1,2], or exact projections onto D. Projected clipped subgradient updates must produce a measurable feasible output x¯ satisfying E[4ρ2∥x¯−p(x¯)∥2]≤ε2, where ε>0, p(x) minimizes f(y)+ρ∥y−x∥2 over y∈D, and expectation averages sampling and algorithm randomness.

The optimization problem is infx∈Df(x). The norm is induced by the inner product on E. Fix parameters ρ>0,G>0,σ≥0,1<α≤2,Δ≥0,ε>0. The algorithm receives E, the measurable sample space Ω, these parameters, and the starting point x0; the objective, feasible set, and sampling distribution are accessed through the oracle.

Our assumptions:

Assumption 1 (Weak convexity and initial gap). The set D⊆E is closed and convex, and x0∈D. There is a map v:E→E such that, for every x,y∈D, f(y)≥f(x)+⟨v(x),y−x⟩−ρ2∥y−x∥2,∥v(x)∥≤G. There is a lower bound ℓ∈R satisfying f(x)≥ℓ(x∈D),f(x0)−ℓ≤Δ.

Assumption 2 (Heavy-tailed stochastic subgradients). There are a probability distribution ν on Ω and a jointly measurable map g:E×Ω→E. For every x∈D, the random vector g(x,ξ) is Bochner integrable and ∥g(x,ξ)−v(x)∥α is integrable under ξ∼ν, with Eξ∼ν[g(x,ξ)]=v(x),Eξ∼ν[∥g(x,ξ)−v(x)∥α]≤σα. Oracle samples (ξk)k≥0 are measurable, mutually independent, and each has law ν. Their joint law is independent of the algorithm’s randomness. At call k, a subgradient query at x returns g(x,ξk).

Assumption 3 (Exact projection). Projection queries at any z∈E return ΠD(z), where ΠD:E→E is measurable and satisfies ΠD(z)∈D,⟨z−ΠD(z),u−ΠD(z)⟩≤0(u∈D).

The task is algorithm-specific: we analyze projected clipped subgradient descent with a constant step size and clipping threshold. The algorithm chooses K∈{0,1,2,…}, η>0, and τ>0 from its inputs. Starting from the given x0, it alternates a stochastic subgradient query and a projection query: ht=g(xt,ξ2t),zt=xt−ηclipτ(ht),xt+1=ΠD(zt),clipτ(h)={h,∥h∥≤τ,τ∥h∥h,∥h∥>τ. Each completed update uses two oracle calls, one of each kind, counted together. For a total budget N∈{0,1,2,…}, let m=⌊N/2⌋ be the number of completed updates. Independently of the samples, draw J uniformly from {0,…,K}. The output rule is x¯={xJ,J≤m,x0,J>m. Thus a budget of 2K calls produces a uniformly selected iterate from x0,…,xK. An unpaired final subgradient query does not change the output.

Accuracy is measured by a proximal residual. Success requires the existence of a map p:E→E satisfying, for every x∈E, p(x)∈argminy∈D{f(y)+ρ∥y−x∥2}. The output must be measurable and belong to D for every realization. For every such proximal map p, the squared residual must be integrable and satisfy EP[4ρ2∥x¯−p(x¯)∥2]≤ε2, where P is the joint law of the independent index J and oracle samples.

Results

A finite-dimensional real inner-product space, closed convex X, x0∈X, and a selection v satisfying f(y)≥f(x)+⟨v(x),y−x⟩−ρ∥y−x∥2/2 and ∥v(x)∥≤G on X. Here ρ,G>0, f≥flow on X, and f(x0)−flow≤Δ. The jointly measurable oracle uses IID samples with Eg(x,ξ)=v(x) and E∥g(x,ξ)−v(x)∥α≤σα, 1<α≤2, σ≥0, with these integrals finite; exact projection onto X is available. The setup requires constant-step, constant-threshold projected clipped subgradient iterations. The target is E∥∇ϕ(xJ)∥2≤ε2 for a uniformly sampled iterate, ε>0.

Weakly convex optimization with heavy-tailed noise (WeaklyConvexHeavyTailed).
Result Oracle complexity Novelty Limitations
(1) WeaklyConvexClippedSubgradient (Ours) (⋆⋆) (review) O(1+ρΔ(G2+σαG2−α)ε4+ρΔσα/(α−1)ε(3α−2)/(α−1))
(2) Clip-SGD (Zhu et al. 2025, Thm. 5, Eq. (27)); expectation, η0=1, batch size 1; bounded subgradients on X⊂int(domf) O(1+(Δ+G+ρ)2G2ε4+((Δ+G+ρ)σε2)α/(α−1)) (1): Clip-SGD noise exponent improves for α<2; for σ,Δ>0, smaller noise term when ε(2−α)/(α−1)<(Δ+G+ρ)α/(α−1)/(ρΔ). Fixed positive parameters, α=3/2, ε→0: O(ε−5) instead of O(ε−6). No exponent gain at α=2. (1): tuning needs ρ,Δ,ε in addition to G,σ,α and the horizon.
(3) Clip-SGD (Zhu et al. 2025, Thm. 3, Eq. (22)); probability 1−δ, η0=1, batch size 1; bounded subgradients on X⊂int(domf)

O(1+Cδ2G2ε4+(Cδσε2)α/(α−1))

Guarantees T−1∑t=1T∥∇ϕ(xt)∥2≤ε2 with probability 1−δ.

(1): for fixed positive parameters and confidence, α=3/2, ε→0, expected accuracy costs O(ε−5) versus O(ε−6) for this stronger guarantee. (1) gives expectation only, losing the probability guarantee of (3); needs ρ,Δ for tuning.
(4) Derived bound: proximal point (Davis and Grimmer 2018, sec. 3) with (Liu and Zhou 2023, Thm. 9); X=Rd

O(1+ρΔG2ε4+ρΔσα/(α−1)ε(3α−2)/(α−1))

ε<G, ε2≤ρΔ; all inner calls counted; ball projection is closed-form.

(1): matches known rate on X=Rd in this regime, with one loop instead of nested loops. Scope extends to constrained X using ΠX.
(5) Derived bound: proximal point (Davis and Grimmer 2018, sec. 3) with (Liu and Zhou 2023, Thm. 9); bounded X, diameter D

O(1+ρΔ(G+ρD)2ε4+ρΔσα/(α−1)ε(3α−2)/(α−1))

ε<G, ε2≤ρΔ; all inner calls counted; only ΠX needed.

(1): deterministic term smaller by (1+ρD/G)2 when ρD>G; noise order matches in this regime. Scope: unbounded X with ΠX; this reduction there remains unresolved.

Abbr: ϕ(x)=miny∈X{f(y)+ρ∥y−x∥2}; ∇ϕ(x)=2ρ(x−proxf+IX,1/(2ρ)(x)); IX: convex indicator of X. ΠX: Euclidean projection; D=diamX; δ∈(0,1); Cδ=Δ+(G+ρ)(1+log⁡(1/δ)). Costs count stochastic subgradient and projection calls separately, including every inner iteration; a closed-form projection adds no oracle requirement.

Davis, Damek, and Benjamin Grimmer. 2018. Proximally Guided Stochastic Subgradient Method for Nonsmooth, Nonconvex Problems. https://doi.org/10.48550/arXiv.1707.03505.
Liu, Zijian, and Zhengyuan Zhou. 2023. Stochastic Nonsmooth Convex Optimization with Heavy-Tailed Noises: High-Probability Bound, in-Expectation Rate and Initial Distance Adaptation. https://doi.org/10.48550/arXiv.2303.12277.
Zhu, Tianxi, Yi Xu, and Xiangyang Ji. 2025. Stochastic Weakly Convex Optimization Under Heavy-Tailed Noises. https://doi.org/10.48550/arXiv.2507.13283.

Lean setup