Smooth Convex Finite-Sum Minimization
Descriptions may be stale. Consult the linked Lean sources.
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
Results
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedFiniteSumConvex (Ours) (review) | |||
| (2) SvrgConvex (Ours) (review) | |||
| (3) VRADA (Song et al. 2021,
Thm. 1, (9)–(11)). |
(1): Matches known rate;
Lean formalization on Hilbert spaces. (2): Smaller
startup when |
(2): |
|
| (4) ANITA (Li 2022, Thm. 1,
Cor. 1). |
Expected call count. |
(1):
Intermediate-accuracy savings for |
(1): At |
| (5) SVRG++ (Allen-Zhu and
Yuan 2016, Thm. 4.1). |
(1): At |
(1), (2) omit the composite term supported by (5). | |
| (6) SVRG++ (Allen-Zhu and
Yuan 2016, Thm. 4.1). |
(2): Matches known rate
when |
(2): Uses |
|
| (7) Katyusha + AdaptReg
(Allen-Zhu 2018,
Cor. 3.5). |
(2): No established improvement. | (2): |
Abbr: