← All setups

Proximal Linear-Decay SGD

Descriptions may be stale. Consult the linked Lean sources.

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⋆)]≤ε.

Results

Minimize Φ=f+ψ on a closed convex set Q in a second-countable real Hilbert space, with f(x)=∫Fξ(x)dp(ξ). Each integrable sample loss is convex and globally L-smooth; sample gradients are jointly measurable. The real-valued ψ is lower semicontinuous and convex on Q; its constrained prox is exact. IID samples have law p. A minimizer x⋆∈Q satisfies ∥x0−x⋆∥≤R, Φ(x0)−Φ(x⋆)≤Δ, and ∫∥∇Fξ(x⋆)−∇f(x⋆)∥2dp(ξ)≤σ2. Here x0∈Q, L,R,ε>0, Δ,σ≥0. The setup restricts the algorithm to proximal SGD with linear decay and last-iterate output xT; the target is ∫[Φ(xT(ω))−Φ(x⋆)]dP(ω)≤ε for the IID trajectory law P.

Comparison for SampledCompositeSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) ProximalLinearDecayLastIterate (Ours) (⋆⋆) (review) O(1+LR2ε+σ2R2ε2+Δε)
(2) Proximal SGD (Vaidyan et al. 2026, Theorem 3.1); finite-dimensional O(1+(LR2ε)2+Δε
+(σ⋆2Lε)2log2(2+σ⋆2Lε))
(1): No larger order on the overlap; variance replaces second moment. For σ⋆=0, Δ=O(LR2), LR2≫ε: O((LR2/ε)2)→O(LR2/ε). Log-free proximal-SGD guarantee; deterministic regularization can have σ=0<σ⋆. (1) needs R,σ for steps; Δ for stopping. Requires finite ψ on closed Q, excluding barrier regularizers.
(3) Derived bound: averaged proximal SGD (Garrigos and Gower 2024, Theorem 12.5); finite-dimensional finite sum, components bounded below; tuned constant step O(1+LR2ε+Δε
+σ2R2ε2+σ2ΔLε2)
(1) removes σ2Δ/(Lε2), dominant when Δ≫LR2, σ2≫Lε; last iterate replaces averaging. Scope: general sample laws. (1) requires finite ψ on closed Q.
(4) Linear-decay proximal SGD (Liu and Zhou 2026, Theorems 3.4/C.3); finite-dimensional, uniformly bounded variance O(1+LR2ε+σu2R2ε2) (1) needs variance only at x⋆, covering regularized random-design least squares with σu=∞. Scope extension, not a rate improvement at equal noise. (1) needs samplewise convexity and smoothness; adds Δ/ε; lacks Bregman geometry. Assumption classes are incomparable.
(5) SAGD (Ilandarideva et al. 2024, Corollary 1, (3.6)); ψ=0 on Q, finite-dimensional, unit batches O(1+LR2ε+σ2R2ε2) (1) extends scope to nonzero ψ using proximal SGD. On the overlap, matches order if Δ=O(LR2+σ2R2/ε). (1) is worse when Δ≫LR2+σ2R2/ε.

Abbr: Costs count sample-gradient and exact constrained-prox calls (one each per iteration; projection when ψ=0). σ⋆2=σ2+∥∇f(x⋆)∥2 bounds the gradient second moment at x⋆. σu2 bounds gradient variance uniformly. In (5), the state-dependent variance parameters specialize to L=4L and noise 2σ2. T is the iteration horizon; SGD denotes stochastic gradient descent.

Garrigos, Guillaume, and Robert M. Gower. 2024. Handbook of Convergence Theorems for (Stochastic) Gradient Methods. https://doi.org/10.48550/arXiv.2301.11235.
Ilandarideva, Sasila, Anatoli Juditsky, Guanghui Lan, and Tianjiao Li. 2024. Accelerated Stochastic Approximation with State-Dependent Noise. https://doi.org/10.48550/arXiv.2307.01497.
Liu, Zijian, and Zhengyuan Zhou. 2026. Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods. https://doi.org/10.48550/arXiv.2312.08531.
Vaidyan, Kevin Kurian Thomas, Michael P. Friedlander, and Ahmet Alacaoglu. 2026. Convergence Rate of the Last Iterate of Stochastic Proximal Algorithms. https://doi.org/10.48550/arXiv.2602.05489.

Lean setup