← All setups

Stochastic Chebyshev Quadratic — Batched SGD for Convex Quadratics

Descriptions may be stale. Consult the linked Lean sources.

Batched SGD for Convex Quadratics · Lean proof

Batched SGD for Convex Quadratics

We consider minimizing a differentiable convex quadratic f:E→R on a finite-dimensional real Hilbert space E. Its gradient is L-Lipschitz, with L>0, and the given starting point x0∈E is within distance R≥0 of a global minimizer x⋆. Each oracle call returns an independent-sample, unbiased stochastic gradient with variance at most σ2, where σ≥0. We analyze batched stochastic gradient descent (SGD). For ε>0, its last completed iterate x¯ must satisfy E[f(x¯)−f(x⋆)]≤ε, with expectation over the oracle samples.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E. The algorithm receives E, the measurable sample space Ω, L, R, σ, ε, and x0.

Our assumptions:

Assumption 1 (Quadratic objective and smoothness). There exist a linear operator A:E→E, a point u∈E, and a constant c∈R such that f(x)=c+12∥A(x−u)∥2,x∈E. The function f is convex and Fréchet differentiable everywhere, and ∥∇f(x)−∇f(y)∥≤L∥x−y∥,x,y∈E.

Assumption 2 (Initial distance). There exists x⋆∈E such that f(x⋆)≤f(x)for every x∈E,∥x0−x⋆∥≤R.

Assumption 3 (Stochastic gradient oracle). Let p be a probability measure on Ω. The oracle is a jointly measurable map g:E×Ω→E. For every x∈E, the map g(x,⋅) is Bochner integrable, the map ∥g(x,⋅)−∇f(x)∥2 is integrable, and Eξ∼p[g(x,ξ)]=∇f(x),Eξ∼p[∥g(x,ξ)−∇f(x)∥2]≤σ2. Queries may be made at any point of E. Successive calls use independent samples ξ1,ξ2,… with common law p, and a call at x using ξj returns g(x,ξj).

Our result is algorithm-specific: we analyze batched SGD with deterministic step sizes ηi≥0 and positive integer batch sizes bi, chosen from the algorithm inputs. Starting from the given x0, define s0=0 and, for i≥1, si=∑r=1ibr,xi=xi−1−ηibi∑j=1big(xi−1,ξsi−1+j). All queries in batch i are made at xi−1, and the point is updated only after all bi replies have been collected. For an oracle-call budget N∈N0, let T=max{i∈N0:si≤N}. The output is x¯=xT. If sT<N, the remaining N−sT calls belong to an unfinished batch and do not change the output; these calls still count toward the budget.

Let P be the joint law of the independent oracle samples. The output must be measurable, its objective gap must be integrable under P, and the required accuracy is EP[f(x¯)−f(x⋆)]≤ε.

Proved result

3+⌈4⋅L⋅R2ε+65536⋅σ2⋅R2ε2⌉+

OracleTemplate.Convergence LongTails.Setups.StochasticConvexQuadratic.spec
  OracleTemplate.StochasticConvexQuadratic.budget

Relevant previous results