Sgd Convex — Stochastic Smooth Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Stochastic Smooth Convex Minimization · Lean proof
Stochastic Smooth Convex Minimization
We consider minimizing a differentiable convex function
The optimization problem is
Our assumptions:
Assumption 1 (Convexity). For every
Assumption 2 (Smoothness). The function
Assumption 3 (Initial distance). There exists
Assumption 4 (Stochastic gradients). There exist a
probability measure
Queries may be made at any point of
Proved result
OracleTemplate.Convergence LongTails.Setups.StochasticSmoothAndConvex.spec
OracleTemplate.StochasticGradient.SgdConvex.budgetRelevant previous results
- Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving Variational
Inequalities with Stochastic Mirror-Prox Algorithm. 2011 (2 June
2008 author preprint used). Complexity:
stochastic-gradient oracle calls, fixed cost counting both calls per Mirror-Prox iteration, for expected objective gap at most in its convex-minimization specialization on a Euclidean ball of radius . - Guanghui Lan. Efficient
Methods for Stochastic Composite Optimization. 2008 (21 June author
preprint; journal version titled An optimal method for stochastic
composite optimization, 2012, online 2011). Complexity:
stochastic-gradient oracle calls, fixed cost, for expected objective gap at most ; robust mirror-descent stochastic approximation specialized to a Euclidean ball of radius containing a minimizer. - Andrei Kulunchakov and Julien Mairal. Estimate
Sequences for Stochastic Composite Optimization: Variance Reduction,
Acceleration, and Robustness to Noise. 2020. Complexity:
stochastic-gradient oracle calls, fixed cost, for expected objective gap at most ; averaged proximal SGD with a fixed horizon.