Quadratic Finite-Sum Minimization
Descriptions may be stale. Consult the linked Lean sources.
Quadratic Finite-Sum Minimization
We consider minimizing
Write the component objectives and their average as
Our assumptions:
Assumption 1 (Component curvature and strong
convexity). For every
Assumption 2 (Initial distance and component
gradients). There exists
At any selected index
Results
On a real Hilbert space with its Borel measurable structure, let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) RandomReshufflingQuadratic (Ours) (review) | |||
| (2) AGD (Bubeck 2015, Thm. 3.18) | (1): No established improvement. | (1): |
|
| (3) Katyusha X (Allen-Zhu 2018,
Cor. 4.4, v1); finite-dimensional restriction, |
(1): Deterministic budget instead of expected cost. Scope: Hilbert-space statement; the dimension extension is formal. | (1): On
finite-dimensional overlap, |
|
| (4) RandomShuffle (Ahn et al. 2020, App. B, Lemmas 6–8, v2); derived bound, finite-dimensional restriction | (1): Method-specific
transient gain |
Abbr: