← All setups

Linear Decay Sgd Last Iterate — Linearly Decaying SGD for Sampled Losses

Descriptions may be stale. Consult the linked Lean sources.

Linearly Decaying SGD for Sampled Losses · Lean proof

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

Proved result

⌈48⋅L⋅R2ε+324⋅σ2⋅R2ε2⌉+

OracleTemplate.Convergence LongTails.Setups.SampledSmoothConvex.spec OracleTemplate.SampledConvex.budget

Relevant previous results