Interpolated Generalized Smooth Finite Sums
Descriptions may be stale. Consult the linked Lean sources.
Interpolated Generalized Smooth Finite Sums
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Component convexity and
differentiability). Each
Assumption 2 (Generalized smoothness). For every
Assumption 3 (Interpolation and initial distance).
There exists
Queries may select any component
Results
Let
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) AcceleratedInterpolatedGeneralizedFiniteSum
(Ours) |
|||
| (2) |
Uniform random iterate; telescoping and Markov conversion to probability |
(1): |
(1): extra |
| (3) (Tyurin 2026, v2, Eq. (8)); full gradients | Special-case overlap: |
(1): up to |
(1): probability |
| (4) (Tyurin 2026, v2, Thm. 4.3); full gradients | Special-case overlap: |
(1): scope extends to higher dimensions without mean smoothness; those rates are not comparable without that assumption. | (1): loses deterministic accuracy; (4) sharpens the curvature term using an initial-gap bound. |
| (5) VARAG (Lan et al. 2019, Thm. 1) | Special case |
(1): scope extends to
|
(1): at |
Abbr: