Katyusha Composite Strongly Convex — Strongly Convex Composite Finite Sums
Descriptions may be stale. Consult the linked Lean sources.
Strongly Convex Composite Finite Sums · Lean proof
Strongly Convex Composite Finite Sums
We minimize
The optimization problem is
Our assumptions:
Assumption 1 (Convex smooth components). Each
Assumption 2 (Strongly convex regularizer and
proximal access). For every
Assumption 3 (Initial objective gap). There exists
A component-gradient query specifies
After the allotted calls, the output
Proved result
OracleTemplate.Convergence LongTails.Setups.CompositeFiniteSumStronglyConvex.spec OracleTemplate.Katyusha.budgetRelevant previous results
- Zeyuan Allen-Zhu. Katyusha: The
First Direct Acceleration of Stochastic Gradient Methods. 2017
(STOC; journal version read: 2018; preprint v1: 2016). Complexity:
exact component-gradient and proximal oracle calls, including full-gradient computations, for in , with fixed cost and ; algorithm: Katyusha. - Xun Qian, Zheng Qu, Peter Richtárik. L-SVRG and
L-Katyusha with Arbitrary Sampling. 2021 (journal version).
Complexity:
expected exact component-gradient and proximal oracle calls, including initialization and full-gradient refreshes, for in , using uniform singleton sampling and refresh probability , with ; algorithm: L-Katyusha.