← All setups

Batched SGD for Convex Quadratics

Descriptions may be stale. Consult the linked Lean sources.

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

Results

On a finite-dimensional real Hilbert space, f(x)=c+∥A(x−u)∥2/2 is convex with L-Lipschitz gradient and a minimizer x⋆ satisfying ∥x0−x⋆∥≤R. IID samples from p give jointly measurable, integrable gradients g with ∫g(x,ω)dp(ω)=∇f(x) and integrable squared error satisfying ∫∥g(x,ω)−∇f(x)∥2dp(ω)≤σ2. Here L,ε>0 and R,σ≥0 are known. The setup restricts algorithms to batched SGD with predetermined nonnegative scalar steps and positive integer batches, returning the last iterate. Target: ∫[f(x^)−f(x⋆)]dP≤ε.

Comparison for StochasticConvexQuadratic.
Result Oracle complexity Novelty Limitations
(1) StochasticChebyshevQuadratic (Ours) (review) O(1+LR2ε+σ2R2ε2)
(2) AC-SA (Ghadimi and Lan 2012, Proposition 7) O(1+LR2ε+σ2R2ε2) (1): Matches known rate on quadratics. Method-specific analysis attains the log-free rate without momentum, using O(T) noise amplification for descending Chebyshev steps. (1): Quadratics only versus general smooth convex objectives; larger constants. Intermediate iterates can grow exponentially.
(3) RSAG (Ghadimi and Lan 2016, Corollary 3(b), (3.22)) O(1+LR2ε+σ2R2ε2) (1): Matches known rate on quadratics; deterministic last index instead of a random index. (2) already provides a fixed-index output. (1): Restricted to quadratics rather than general smooth convex objectives.

Abbr: L: gradient Lipschitz constant; R: initial-distance bound; σ2: variance bound; ε: expected objective accuracy; A: linear map; u,c: quadratic center and offset; T: number of Chebyshev updates; x^: returned point; P: sampling law (including output randomization when used). Costs count individual stochastic-gradient calls, including every batch member.

Ghadimi, Saeed, and Guanghui Lan. 2012. “Optimal Stochastic Approximation Algorithms for Strongly Convex Stochastic Composite Optimization I: A Generic Algorithmic Framework.” SIAM Journal on Optimization 22 (4): 1469–92. https://doi.org/10.1137/110848864.
Ghadimi, Saeed, and Guanghui Lan. 2016. “Accelerated Gradient Methods for Nonconvex Nonlinear and Stochastic Programming.” Mathematical Programming 156: 59–99. https://doi.org/10.1007/s10107-015-0871-8.

Lean setup