Similar Finite-Sum Quasar Minimization
Descriptions may be stale. Consult the linked Lean sources.
Similar Finite-Sum Quasar Minimization
We consider minimizing
The optimization problem is
Our assumptions:
Assumption 1 (Smoothness and component similarity).
Each
Assumption 2 (Quadratic lower model). For every
Assumption 3 (Strong quasar-convexity and quadratic
growth). There exists a global minimizer
Queries may use any component index
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) CachedSimilarQuasar
(Ours) |
|||
| (2) Nesterov acceleration (Hermant et al. 2026, Theorem 2, v3) | (1): replaces
multiplicative |
(1) needs finite-sum
similarity and knowledge of |
|
| (3) Derived bound: gradient sliding (Kovalev et al. 2022, Theorem 3) | (1): on this overlap,
divides the |
(1) needs |
|
| (4) Quasar acceleration (Hinder et al. 2020, Theorem 1) | (1): on the stated
curvature/similarity subclass, replaces the multiplicative |
(1) needs the lower-curvature bound and similarity; (4) applies without these restrictions. |
Abbr: