← All setups

Weakly Convex Clipped Subgradient — Clipped Subgradients with Heavy-Tailed Noise

Descriptions may be stale. Consult the linked Lean sources.

Clipped Subgradients with Heavy-Tailed Noise · Lean proof

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.

Proved result

2⋅⌈288⋅ρ⋅Δ⋅(G2+σα⋅(4⋅G+4⋅σ⋅(4⋅σε)1α−1)2−α)ε4⌉+

OracleTemplate.Convergence LongTails.Setups.WeaklyConvexHeavyTailed.spec OracleTemplate.WeaklyConvexHeavyTailed.budget

Relevant previous results

No qualifying prior reference verified; this is not a proof of novelty.