Cyclic Gradient Interpolation — Cyclic Gradient Under Interpolation
Descriptions may be stale. Consult the linked Lean sources.
Cyclic Gradient Under Interpolation · Lean proof
Cyclic Gradient Under Interpolation
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity and smoothness).
Each
Assumption 2 (Interpolation and initial distance).
There exists
The oracle accepts any component index and any point in
Proved result
OracleTemplate.Convergence LongTails.Setups.InterpolatedFiniteSum.spec OracleTemplate.CyclicInterpolation.budgetRelevant previous results
- Julien Mairal. Optimization with
First-Order Surrogate Functions. 2013. Complexity:
fixed component-gradient calls, including initialization; MISO achieves expected average objective gap at most . - Konstantin Mishchenko, Ahmed Khaled, Peter Richtárik. Random
Reshuffling: Simple Analysis with Vast Improvements. 2020.
Complexity:
fixed component-gradient calls under interpolation; deterministic Incremental Gradient achieves average objective gap at most at the average of epoch endpoints. - Sharan Vaswani, Francis Bach, Mark Schmidt. Fast
and Faster Convergence of SGD for Over-Parameterized Models and an
Accelerated Perceptron. 2019. Complexity:
fixed component-gradient calls under interpolation; constant-step SGD achieves expected average objective gap at most at an averaged output.