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
The optimization problem is
Our assumptions:
Assumption 1 (Quadratic objective and smoothness).
There exist a linear operator
Assumption 2 (Initial distance). There exists
Assumption 3 (Stochastic gradient oracle). Let
Our result is algorithm-specific: we analyze batched SGD with
deterministic step sizes
Let
Results
On a finite-dimensional real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StochasticChebyshevQuadratic (Ours) (review) | |||
| (2) AC-SA (Ghadimi and Lan 2012, Proposition 7) | (1): Matches known rate
on quadratics. Method-specific analysis attains the log-free rate
without momentum, using |
(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)) | (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: