High-Dimensional Strong Quasar Minimization
Descriptions may be stale. Consult the linked Lean sources.
High-Dimensional Strong Quasar Minimization
We consider minimizing a differentiable, possibly nonconvex function
The optimization problem is
Our assumptions:
Assumption 1 (Parameter and dimension regime). The
dimension
Assumption 2 (Smoothness). The function
Assumption 3 (Strong quasar convexity and initial
gap). There exists a global minimizer
Queries may be made at any point of
Results
- High Dimensional Strong Quasar Lower Bound · Lean proof
- High Dimensional Strong Quasar Upper Bound · Lean proof
Differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| Lower bound
(necessary) (1) HighDimensionalStrongQuasarLowerBound (Ours) |
|||
| Upper bound
(sufficient) (2) HighDimensionalStrongQuasarUpperBound (Ours) (review) |
|||
| Prior lower bound
(necessary) (3) (Hinder et al. 2023), Remark 4 proof, App. E.3 |
(1): randomized hardness;
necessary budget gains |
(1) needs the stated
small- |
Abbr:
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| Prior upper bounds
(sufficient) (4) (LongTails, n.d.), |
(2): Matches known rate. | (2) restricts the earlier finite-dimensional, relative-error result to exact gradients and the stated parameter/dimension regime. | |
| (5) (Hinder et al. 2023), Theorem 1 | (2) removes |
(2) gives only expected
accuracy, needs |
|
| (6) (Wang and Wibisono 2023), Theorem 2 | (2) matches the rate scale; fixed-call expected gap already appears in (4). | (2) has larger constants and the stated parameter/dimension restrictions. | |
| (7) (Wang and Wibisono 2023), Corollary 2 | (2) matches the rate scale at fixed confidence, with fixed-call expected accuracy. | (2) does not supply this explicit probability guarantee; its parameter/dimension regime is narrower. |
Abbr: