← All setups

Terminal Clipping for Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Terminal Clipping for Convex Minimization

We consider minimizing a measurable convex function f:Rd→R over a closed convex set D, with a given x0∈D within distance R≥0 of a minimizer x⋆. The oracle returns stochastic subgradient estimates g(x,ξ) from independent samples ξ with law ν, or exact projections onto D. Their means are subgradients on D, and Eξ∼ν∥g(x,ξ)∥2≤B2∥x−x0∥2+G2, where B,G>0. Projected clipped updates must return a measurable terminal iterate x¯∈D satisfying f(x¯)−f(x⋆)≤ε with probability at least 1−δ, where ε>0 and δ∈(0,1).

The optimization problem is minx∈Df(x). Here d is a nonnegative integer, and ⟨⋅,⋅⟩ and ∥⋅∥ denote the Euclidean inner product and norm. The algorithm receives d,x0,B,G,δ,R,ε and accesses the objective and constraint set through the oracle.

Our assumptions:

Assumption 1 (Convexity and initial distance). The set D⊆Rd is closed and convex, x0∈D, and f is measurable on Rd. For all x,y∈D and t∈[0,1], f((1−t)x+ty)≤(1−t)f(x)+tf(y). There exists x⋆∈D such that f(x⋆)≤f(x)for every x∈D,∥x0−x⋆∥≤R.

Assumption 2 (Stochastic subgradients). Let ν be a probability measure on a measurable sample space Ω. The map g:Rd×Ω→Rd is jointly measurable. For every x∈D, g(x,⋅) is Bochner integrable and ∥g(x,⋅)∥2 is integrable under ν. Its mean satisfies the subgradient inequality f(x)−f(y)≤⟨Eξ∼ν[g(x,ξ)],x−y⟩,x,y∈D, and its second moment satisfies Eξ∼ν[∥g(x,ξ)∥2]≤B2∥x−x0∥2+G2,x∈D. The oracle samples form a sequence (ξk)k≥0 of measurable, mutually independent random variables, each with law ν. This sequence is independent of the algorithm’s randomness. At call k, a subgradient query at x returns g(x,ξk).

Assumption 3 (Exact projection). A projection query at any z∈Rd returns ΠD(z), where ΠD:Rd→Rd is measurable and satisfies ΠD(z)∈D,⟨z−ΠD(z),u−ΠD(z)⟩≤0,u∈D.

Our formulation is algorithm-specific: we analyze terminal clipping with projected stochastic subgradient updates. For a nonnegative threshold C, define clipC(v)={v,∥v∥≤C,C∥v∥v,∥v∥>C. The method starts at the given x0, with initial output x0 and first query a subgradient query at x0. It alternates subgradient and projection queries. Before receiving the subgradient reply at iteration t, it selects a step size ηt≥0 and threshold Ct≥0 using its available history and internal randomness. The updates are gt=g(xt,ξ2t),zt=xt−ηtclipCt(gt),xt+1=ΠD(zt). The output remains xt after the subgradient reply and becomes xt+1 after the projection reply; the next query is a subgradient query at xt+1. Both query types count toward a single total oracle-call budget. Thus each completed update uses two calls. With a budget of N≥0 calls, the terminal output is x¯=x⌊N/2⌋; an unmatched final subgradient call leaves it unchanged.

The required output is measurable and belongs to D for every realization. Its accuracy requirement is PP(f(x¯)−f(x⋆)>ε)≤δ, where P is the joint law of the oracle samples and the independent algorithm randomness.

Results

Measurable f is convex on closed convex X⊆Rd; x0,x⋆∈X, x⋆∈arg⁡minXf, and ∥x0−x⋆∥≤R. IID samples have law ν and joint law P. The jointly measurable oracle satisfies ∫g(x,ω)dν(ω)∈∂Xf(x) and ∫∥g(x,ω)∥2dν(ω)≤B2∥x−x0∥2+G2 on X; exact measurable projection onto X is available. Here B,G,ε>0, R≥0, 0<δ<1. The setup restricts algorithms to projected clipped subgradient updates with the current iterate as output. Target: P{f(xT)−f(x⋆)>ε}≤δ.

High-probability convex optimization under distance-growing second moments: TerminalClippingConvex.
Result Oracle complexity Novelty Limitations
(1) ClippedBgLastIterate (Ours) (⋆⋆⋆) (review) O(1+(BR2+G2/B)2ℓ2ε2)
(2) Projected Halpern (Alacaoglu et al. 2026, Thm. 3.6); derived bound via Markov O(1+A2ε2δ2[1+log(1+Aεδ)]2) (1): On the same moment class, logarithmic instead of polynomial confidence cost; removes the accuracy logarithm at fixed confidence. Comparison is specifically with Markov conversion. (1) needs a fixed horizon instead of an anytime schedule; substantially larger proved numerical constants.
(3) Clipped SGD (Liu and Zhou 2023, Thm. 3), p=2

O(1+(β+R2/β)2(M2+σ2)ℓ2ε2)

Special case: M-bounded subgradients, uniform variance σ2; β>0, known σ, fixed horizon.

(1): Matches this rate for G2=M2+σ2, B=G/β, with last iterate instead of averaging. Scope: allows non-Lipschitz objectives and growing moments. (1): The G4/(B2ε2) term diverges as B↓0; bounded-moment tuning B=G/R needs R>0 known.
(4) Distance-adaptive clipped SGD (Liu and Zhou 2023, Thm. 6), p=2

O(h+aMℓε+z2[1+log⁡(1+z)]2)

Special case: M-bounded subgradients, known uniform variance bound σ2; r>0, wt=1+log2⁡t.

(1): Last iterate instead of a selected weighted average; extends to non-Lipschitz objectives with growing moments. (1) is not distance-adaptive: (β+R2/β)2 mismatch when B=G/β. Loses anytime tuning.

Abbr: ∂Xf(x)={v:f(y)≥f(x)+⟨v,y−x⟩ ∀y∈X}; ℓ=1+log⁡(1/δ); A=BR2+G2/B. Costs count subgradient calls plus projection calls (one of each per update); on X=Rd projection is the identity. M bounds deterministic subgradients; σ is the central-noise scale; L is gradient Lipschitzness; p,α are central moment orders. In (4), h=1+log⁡(1+R/r), a=(r+R)h, z=aM2+σ2ℓ/ε. In (6), D=max{Rσ,L1/5R6/5σ4/5,L1/3R4/3σ2/3} and ℓs=1+log⁡((1+LR2/ε+D3/ε3)/δ).

TerminalClippingConvex (continued).
Result Oracle complexity Novelty Limitations
(5) SGD (Liu and Zhou 2026, Thm. 3.5)

O(1+(M2+σ2ℓ)R2ε2)

Special case: M-Lipschitz objective, sub-Gaussian noise of scale σ; R-tuned.

(1): Extends the high-probability last-iterate guarantee to finite second moments and non-Lipschitz objectives with growing moments. On the overlap, G2=M2+σ2, B=G/R, R>0: (1) costs O(1+(M2+σ2)R2ℓ2ε2), losing up to ℓ2.
(6) Clipped SGD (Chezhegov et al. 2026, Thm. 1, Cor. 1), α=2

O(1+LR2ℓs2ε+D3ℓs6ε3)

Special case: X=Rd, L-smooth, uniform variance σ2; L,R,σ>0.

(1): With B=2L, G2=2L2R2+σ2, costs O(1+(LR2+σ2/L)2ℓ2ε2); improves the accuracy dependence when ε≤min{σ3/(L2R),L2R3/σ}. Scope: no smoothness needed. Updates can use supplied G2≥2∥∇f(x0)∥2+σ2 instead of R. (1) loses anytime tuning and coverage of α<2; worse deterministic term: L2R4/ε2 instead of LR2/ε, apart from logarithms.

Abbr: ∂Xf(x)={v:f(y)≥f(x)+⟨v,y−x⟩ ∀y∈X}; ℓ=1+log⁡(1/δ); A=BR2+G2/B. Costs count subgradient calls plus projection calls (one of each per update); on X=Rd projection is the identity. M bounds deterministic subgradients; σ is the central-noise scale; L is gradient Lipschitzness; p,α are central moment orders. In (4), h=1+log⁡(1+R/r), a=(r+R)h, z=aM2+σ2ℓ/ε. In (6), D=max{Rσ,L1/5R6/5σ4/5,L1/3R4/3σ2/3} and ℓs=1+log⁡((1+LR2/ε+D3/ε3)/δ).

Alacaoglu, Ahmet, Yura Malitsky, and Stephen J. Wright. 2026. Towards Weaker Variance Assumptions for Stochastic Optimization. https://doi.org/10.48550/arXiv.2504.09951.
Chezhegov, Savelii, Daniela Angela Parletta, Andrea Paudice, and Eduard Gorbunov. 2026. “High-Probability Bounds for the Last Iterate of Clipped SGD.” International Conference on Learning Representations. https://proceedings.iclr.cc/paper_files/paper/2026/hash/03382840834c7fbdc1e882fac11904d6-Abstract-Conference.html.
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.
Liu, Zijian, and Zhengyuan Zhou. 2026. Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods. https://doi.org/10.48550/arXiv.2312.08531.

Lean setup