Finite-Sum Convex Strong Growth
Descriptions may be stale. Consult the linked Lean sources.
Finite-Sum Convex Strong Growth
We minimize
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity and smoothness).
Each
Assumption 2 (Strong growth). For every
Assumption 3 (Initial distance). There exists
The algorithm may query any component index
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) StrongGrowthConvexFiniteSumAcceleration
(Ours) |
|||
| (2) SNAG (Hermant et al. 2026), Thm. 3, (8) | (1): rate gain |
(1) needs convex smooth
components and finite-sum reuse; adds |
|
| (3) Katyusha + AdaptReg (Allen-Zhu 2018), Cor. 3.5 | (1): rate gain at least
|
(1) needs strong growth;
adds |
|
| (4) Proximal STORM (LongTails 2026) | (1): |
(1) needs convex
components and finite sums. Its accuracy term is worse when |
|
| (5) Derived bound (Novoselov et al. 2026), Thm. 5.1 | (1): for |
(1) needs strong growth and a finite sum; (5) covers general interpolating populations without a strong-growth constant. |
Abbr: