Linear Decay Sgd Last Iterate — Linearly Decaying SGD for Sampled Losses
Descriptions may be stale. Consult the linked Lean sources.
Linearly Decaying SGD for Sampled Losses · Lean proof
Linearly Decaying SGD for Sampled Losses
We minimize
The optimization problem is
Our assumptions:
Assumption 1 (Sample convexity and smoothness). For
every
Assumption 2 (Initial distance and noise at a
minimizer). There exists
Queries may be made at any point of
Our result is algorithm-specific: we analyze linearly decaying SGD.
The method chooses a deterministic scale
The output must be measurable under
Proved result
OracleTemplate.Convergence LongTails.Setups.SampledSmoothConvex.spec OracleTemplate.SampledConvex.budgetRelevant previous results
- Benjamin Grimmer. Convergence Rates for
Deterministic and Stochastic Subgradient Methods Without Lipschitz
Continuity. 2019 (publication; preprint v3, 2018; first preprint,
2017). Complexity:
sampled-gradient oracle calls for expected objective gap at most of an averaged SGD iterate. - Othmane Sebbouh, Robert M. Gower, Aaron Defazio. Almost
sure convergence rates for Stochastic Gradient Descent and Stochastic
Heavy Ball. 2021 (publication; initial preprint, 2020). Complexity:
sampled-gradient oracle calls for expected objective gap at most of the stochastic heavy-ball terminal iterate.