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
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
Proved result
OracleTemplate.Convergence LongTails.Setups.StochasticConvexQuadratic.spec
OracleTemplate.StochasticConvexQuadratic.budgetRelevant previous results
- Guanghui Lan. Efficient
Methods for Stochastic Composite Optimization. 2008 (June 21
preprint; journal version published online 2011, issue 2012).
Complexity:
stochastic-gradient oracle calls using AC-SA on a Euclidean ball of radius , for expected objective gap at most . - Saeed Ghadimi and Guanghui Lan. Optimal
Stochastic Approximation Algorithms for Strongly Convex Stochastic
Composite Optimization I: A Generic Algorithmic Framework. 2012
(June 15 revised preprint; original preprint 2010). Complexity:
stochastic-gradient oracle calls using AC-SA, including its general convex case, for expected objective gap at most .