Svrg Convex — Smooth Convex Finite-Sum Minimization
Descriptions may be stale. Consult the linked Lean sources.
Smooth Convex Finite-Sum Minimization · Lean proof
Smooth Convex Finite-Sum Minimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity). For every
Assumption 2 (Component smoothness). Each
Assumption 3 (Initial distance). There exists
Queries may select any component
Proved result
OracleTemplate.Convergence LongTails.Setups.FiniteSumSmoothAndConvex.spec OracleTemplate.FiniteSum.SvrgConvex.budgetRelevant previous results
- Zeyuan Allen-Zhu, Yang Yuan. Improved SVRG
for Non-Strongly-Convex or Sum-of-Non-Convex Objectives. 2016.
Complexity:
component-gradient calls, including full gradients; SVRG++, fixed budget, expected objective gap at most , for . - Pooria Joulani, András György, Csaba Szepesvári. A modular
analysis of adaptive (non-)convex optimization: Optimism, composite
objectives, variance reduction, and variational bounds. 2020 (online
publication 2019). Complexity:
component-gradient calls, including full gradients; generic SVRG with doubled epochs, fixed budget, expected objective gap at most , for .