Accelerated Finite Sum 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.AcceleratedFiniteSumConvex.budgetRelevant previous results
- Chaobing Song, Yong Jiang, Yi Ma. Variance
Reduction via Accelerated Dual Averaging for Finite-Sum
Optimization. 2020. Complexity:
component-gradient calls, including initialization and full gradients; VRADA, fixed budget, expected objective gap at most .