← All setups

Proximal Linear Decay Last Iterate — Proximal Linear-Decay SGD

Descriptions may be stale. Consult the linked Lean sources.

Proximal Linear-Decay SGD · Lean proof

Proximal Linear-Decay SGD

We consider minimizing F(x)=Eξ∼ν[ℓ(ξ,x)]+ψ(x) over a closed convex set Q in a separable real Hilbert space E, where ν is a probability law on a measurable sample space Ξ. Each sample loss ℓ(ξ,⋅) is convex with an L-Lipschitz gradient, L>0, and ψ:E→R is lower semicontinuous and convex on Q. A given starting point has bounded distance and objective gap to a minimizer x⋆, where gradient variance is bounded. The oracle returns independent sampled gradients or exact proximal minimizers. Proximal SGD with linearly decaying steps must return a measurable output x¯ with integrable gap satisfying E[F(x¯)−F(x⋆)]≤ε, where ε>0 and expectation is over the samples.

Write f(x)=Eξ∼ν[ℓ(ξ,x)],F(x)=f(x)+ψ(x). The optimization problem is minx∈QF(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, Ξ, the starting point x0, and the parameters L>0,R>0,Δ≥0,σ≥0,ε>0. The model consists of ν, ℓ, its sample gradient g:Ξ×E→E, ψ, Q, and a proximal map P:R×E×E→E; access to it is through the oracle below.

Our assumptions:

Assumption 1 (Sample losses). The map (ξ,x)↦g(ξ,x) is jointly measurable. For every ξ∈Ξ, the function ℓ(ξ,⋅) is convex and Fréchet differentiable on E, with g(ξ,x)=∇xℓ(ξ,x),∥g(ξ,x)−g(ξ,y)∥≤L∥x−y∥,x,y∈E. For every x∈E, the function ξ↦ℓ(ξ,x) is integrable under ν.

Assumption 2 (Composite structure and proximal access). The set Q⊆E is closed and convex, and x0∈Q. The function ψ:E→R is lower semicontinuous on E and convex on Q. For every a>0 and z,h∈E, the oracle’s proximal map satisfies P(a,z,h)∈argminu∈Q{∥u−z∥22a+⟨h,u−z⟩+ψ(u)}. The map is defined for all real a, but this minimization property is required only for a>0.

Assumption 3 (Initialization and variance at a minimizer). There exists x⋆∈Q such that F(x⋆)≤F(x)for every x∈Q,∥x0−x⋆∥≤R,F(x0)−F(x⋆)≤Δ. The random vector g(ξ,x⋆) is Bochner integrable under ν. Define its mean by m⋆=Eξ∼ν[g(ξ,x⋆)]. The squared centered norm is integrable and satisfies Eξ∼ν[∥g(ξ,x⋆)−m⋆∥2]≤σ2.

Let (ξj)j≥0 be measurable, mutually independent samples, each with law ν, and let P denote their joint law. At call j, a gradient query x∈E returns g(ξj,x), while a proximal query (a,z,h)∈R×E×E returns P(a,z,h). Both query types count toward one shared oracle-call budget; proximal replies do not depend on the sample at that call.

Our formulation is algorithm-specific: we analyze proximal SGD with linear step-size decay. The algorithm chooses η≥0 and an integer T≥0 from its inputs and starts at the given x0. It alternates a gradient query and a proximal query according to ak=ηT−kT,hk=g(ξ2k,xk),xk+1=P(ak,xk,hk),k=0,1,…. When T=0, the step-size formula is interpreted as ak=0. The parameter T specifies the decay schedule; termination is determined by the allotted number of calls. For a budget of N≥0 calls, the output is the last completed proximal iterate, x¯=x⌊N/2⌋. Thus each completed update uses two calls, and an additional gradient call does not change the output.

The output must be measurable under P, and its objective gap must be integrable and satisfy EP[F(x¯)−F(x⋆)]≤ε.

Proved result

2⋅⌈72⋅L⋅R2ε+900⋅σ2⋅R2ε2+6⋅Δε⌉+

OracleTemplate.Convergence LongTails.Setups.SampledCompositeSmoothConvex.spec OracleTemplate.SampledComposite.budget

Relevant previous results