← All setups

Linearly Decaying SGD for Sampled Losses

Descriptions may be stale. Consult the linked Lean sources.

Linearly Decaying SGD for Sampled Losses

We minimize f(x)=Eξ∼ν[ℓ(ξ,x)] on a separable real Hilbert space E, where ν is a probability law on a measurable sample space Ξ and each sample loss ℓ(ξ,⋅) is convex with L-Lipschitz gradient, L>0. A given starting point x0 lies within distance R≥0 of a minimizer x⋆, where Eξ∼ν∥∇xℓ(ξ,x⋆)∥2≤σ2 for σ≥0. The oracle returns sample gradients using independent samples from ν. We analyze linearly decaying stochastic gradient descent (SGD), seeking a measurable last iterate x¯ with integrable objective gap satisfying E[f(x¯)−f(x⋆)]≤ε, where ε>0 and expectation is over the samples.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, Ξ, L, R, σ, ε, and x0; the distribution ν and sample losses are accessed through the oracle.

Our assumptions:

Assumption 1 (Sample convexity and smoothness). For every ξ∈Ξ, the function ℓ(ξ,⋅):E→R is Fréchet differentiable. Write g(ξ,x)=∇xℓ(ξ,x). For every x,y∈E and t∈[0,1], ℓ(ξ,(1−t)x+ty)≤(1−t)ℓ(ξ,x)+tℓ(ξ,y),∥g(ξ,x)−g(ξ,y)∥≤L∥x−y∥. The map g:Ξ×E→E is jointly measurable, and ℓ(⋅,x) is integrable under ν for every x∈E.

Assumption 2 (Initial distance and noise at a minimizer). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R. The random variable ∥g(ξ,x⋆)∥2 is integrable under ν and satisfies Eξ∼ν[∥g(ξ,x⋆)∥2]≤σ2.

Queries may be made at any point of E. At call k, the oracle returns g(ξk,x) for the queried point x, where (ξk)k≥0 are measurable, mutually independent random variables with common law ν. Let P denote their joint law.

Our result is algorithm-specific: we analyze linearly decaying SGD. The method chooses a deterministic scale η≥0 and an integer T≥0 from the available inputs. Starting from the given x0, it performs ak={η(T−k)/T,T>0,0,T=0,xk+1=xk−akg(ξk,xk),k=0,…,N−1, where N≥0 is the allotted number of oracle calls. The tuning parameter T need not equal N. Each update uses one oracle reply, and the output is the last iterate x¯=xN, with x¯=x0 when N=0.

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

Results

On a separable real Hilbert space, f(x)=∫Fξ(x)dp(ξ), where p is a probability measure, every Fξ is convex with L-Lipschitz gradient, the sample gradient is jointly measurable, and Fξ(x) is integrable for every x. A minimizer x⋆ satisfies ∥x0−x⋆∥≤R and ∫∥∇Fξ(x⋆)∥2dp(ξ)≤σ2. Here L,ε>0 and R,σ≥0. Samples are IID with law p under P. The setup restricts algorithms to linear-decay SGD; (1) uses known L,R,σ,T and guarantees the last-iterate target ∫[f(xT(ω))−f(x⋆)]dP(ω)≤ε. Costs count individual sample-gradient calls.

Sample-gradient complexity for SampledSmoothConvex.
Result Oracle complexity Novelty Limitations
(1) LinearDecaySgdLastIterate (Ours) (review) O(1+LR2ε+σ2R2ε2)
(2) SHB-IMA (Sebbouh et al. 2021, Thm. G.1, Cor. G.2)

O(1+LR2ε+σ2R2ε2)

Finite-dimensional restriction; tuned, known horizon.

(1): Matches known rate and tuning information, using plain SGD instead of momentum; extends Rd to Hilbert space.
(3) Constant-step SGD (Attia et al. 2025, Thm. 2)

O([1+LR2ε+σ2R2ε2]ℓ)

Finite-dimensional restriction; tuned step.

(1): Removes ℓ when LR2/ε+σ2R2/ε2→∞, including interpolation; extends to Hilbert space. Method-specific gain, not improved problem-class complexity.
(4) Constant-step SGD, derived bound (Garrigos et al. 2025, Thm. 3.1)

O([1+LR2ε+σ2R2ε2]ℓ)

Hilbert space; tuned using L,R,σ,T.

(1): Removes ℓ when LR2/ε+σ2R2/ε2→∞, for plain SGD's last iterate under the same assumptions.
(5) Constant-step SGD (Garrigos et al. 2025, Cor. 3.4)

O(1+L2R4ε2+σ4L2ε2ℓ02)

Step 1/(2LT); Hilbert space.

(1): At σ=0 and LR2/ε≫1, reduces O((LR2/ε)2) to O(LR2/ε). (1) needs R,σ in addition to L,T for its steps.
(6) Averaged SGD (Attia et al. 2025, App. B, Thm. 8)

O(1+LR2ε+σ2R2ε2)

Finite-dimensional restriction; tuned step.

(1): Matches known rate with the last iterate instead of an average; extends to Hilbert space.
(7) Linear-decay SGD (Liu and Zhou 2026, Thm. 3.4)

O(1+LR2ε+σu2R2ε2)

Unconstrained smooth specialization in Rd; uniform variance bound σu2.

(1): Replaces σu2 by σ2 on the overlap; factor σu2/σ2 saving when noise dominates each cost. Covers random-design least squares with σu=∞; matches at equal noise. (1) requires per-sample convexity and smoothness; does not cover constraints or composite terms. Classes are incomparable.

Abbr: SGD: stochastic gradient descent; SHB-IMA: stochastic heavy ball in iterate-moving-average form. T: horizon; R: initial-distance bound; σ2: sample-gradient second-moment bound at x⋆; σu2≥supx∫∥∇Fξ(x)−∇f(x)∥2dp(ξ); ℓ=1+log⁡(1+LR2/ε+σ2R2/ε2); ℓ0=1+log⁡(1+σ2/(Lε)).

Attia, Amit, Matan Schliserman, Uri Sherman, and Tomer Koren. 2025. Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime. arXiv:2507.11274v2. https://doi.org/10.48550/arXiv.2507.11274.
Garrigos, Guillaume, Daniel Cortild, Lucas Ketels, and Juan Peypouquet. 2025. Last-Iterate Complexity of SGD for Convex and Smooth Stochastic Problems. arXiv:2507.14122v1. https://doi.org/10.48550/arXiv.2507.14122.
Liu, Zijian, and Zhengyuan Zhou. 2026. Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods. arXiv:2312.08531v4. https://doi.org/10.48550/arXiv.2312.08531.
Sebbouh, Othmane, Robert M. Gower, and Aaron Defazio. 2021. Almost Sure Convergence Rates for Stochastic Gradient Descent and Stochastic Heavy Ball. arXiv:2006.07867v2. https://doi.org/10.48550/arXiv.2006.07867.

Lean setup