← All setups

Clipped Bg Last Iterate — Terminal Clipping for Convex Minimization

Descriptions may be stale. Consult the linked Lean sources.

Terminal Clipping for Convex Minimization · Lean proof

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.

Proved result

2⋅max{1,⌈240⋅(B⋅R2+G2B)2⋅(log⁡(8δ))2ε2⌉+}

OracleTemplate.Convergence LongTails.Setups.TerminalClippingConvex.spec OracleTemplate.TerminalClipping.budget

Relevant previous results