Accelerated Coordinate Strongly Convex — Coordinate-Smooth Strongly Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
Coordinate-Smooth Strongly Convex Minimization · Lean proof
Coordinate-Smooth Strongly Convex Minimization
We consider minimizing a differentiable,
The optimization problem is
Our assumptions:
Assumption 1 (Coordinate smoothness). The function
Assumption 2 (Strong convexity). For every
Assumption 3 (Initial objective gap). There exists
Coordinate queries may be made at any point of
Proved result
OracleTemplate.Convergence LongTails.Setups.CoordinateSmoothStronglyConvex.spec
OracleTemplate.AcceleratedCoordinate.budgetRelevant previous results
- Zeyuan Allen-Zhu, Zheng Qu, Peter Richtárik, Yang Yuan. Even Faster Accelerated
Coordinate Descent Using Non-Uniform Sampling. 2016 (ICML; full
preprint v3, May 2016; first preprint December 2015). Complexity:
fixed exact coordinate-gradient oracle calls for , using NU_ACDM, when ; initialization requires no oracle calls, and zero calls suffice when .