Coordinate-Smooth Strongly Convex Minimization
Descriptions may be stale. Consult the linked Lean sources.
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
Results
Differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedCoordinateStronglyConvex (Ours) (review) | |||
| (2) NU_ACDM (Allen-Zhu et al.
2016, arXiv v3, Theorem 5.1, |
(1): Matches known rate; Lean formalization. The coordinate upper model gives no scope extension; tuning knowledge and expected last-iterate guarantee are unchanged. | (1): Worse constants from integer-rounded sampling weights and a smaller coupling parameter. |
Abbr: Costs count individual partial-derivative
queries.