Strong Growth Finite-Sum Minimization
Descriptions may be stale. Consult the linked Lean sources.
Strong Growth Finite-Sum Minimization
We minimize
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity and smoothness).
Each
Assumption 2 (Strong convexity). For every
Assumption 3 (Strong growth). The component
gradients satisfy
Assumption 4 (Initial distance). There exists
Queries may select any component index
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StrongGrowthFiniteSumAcceleration
(Ours) |
|||
| (2) Restarted Katyusha, derived bound (Allen-Zhu 2018, Thm. 4.1) | (1): replaces |
(1) requires global
strong growth; loses |
|
| (3) SNAG (Hermant et al. 2026, Thm. 3) | (1): for |
(1) needs convex, smooth
components and a finite sum; loses when |
Abbr: