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 (Differentiability and smoothness).
Each
Assumption 2 (Mean-square gradient similarity).
Define
Assumption 3 (Strong quasar-convexity and initial
gap). There exists
Queries may use any component
Results
On a real Hilbert space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) MovementSimilarQuasar
(Ours) |
|||
| (2) ContinuizedSimilarQuasar
(Ours) |
|||
| (3) PAGE (Li et al. 2021), Thm. 5,
Cor. 6. Derived bound on |
(1): no worse polynomial
dependence; extra accuracy logarithm. For |
(1), (2)
require quasar structure; (3) only PL. Extra |
|
| (4) Full-batch
acceleration (Hinder
et al. 2020), Thm. 1; |
(1),
(2): gradients only. At |
(1), (2)
give expected accuracy. (1) loses for |
|
| (5) QASVRG (Fu et al. 2023),
Cor. 3.6, Option I. Special case: |
(1),
(2): scope extends to non-interpolating sums; gradients
only on the overlap. For (2), a rate gain requires
controlling |
Small similarity is needed for a rate
gain. On the overlap, (2) has quadratic |
|
| (6) AccSVRS (Lin et al. 2023),
§3.3, App. E. Special case: |
(1): at |
(1) has worse polynomial
cost at |
Abbr: