Gradient-Only Generalized Quasar Minimization
Descriptions may be stale. Consult the linked Lean sources.
Gradient-Only Generalized Quasar Minimization
We consider minimizing a continuously differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Generalized smoothness). The function
Assumption 2 (Quasar convexity and initialization).
There exists
Queries may be made at any point of
Results
A finite-dimensional real Hilbert space; continuously differentiable
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) GradientOnlyQuasarHighProbability
(Ours) |
|||
| (2) (Wang and Wibisono 2023), Cor. 1 | (1): at |
(1): substantially larger numerical constant. | |
| (3) (Hinder et al. 2020), Thm. 2 | (1): no values or search;
fewer calls when |
(1): probabilistic
instead of deterministic; more calls when |
|
| (4) GD, (Jin 2020), derived from (12) | (1): saving |
(1): randomized; loses
deterministic accuracy; more calls when |
|
| (5) (Kovalev 2026), Thm. 11; derived bound | (1): logarithmic
confidence instead of |
(1): requires smoothness and exact gradients; (5) also covers nonsmooth stochastic objectives. | |
| (6) (LongTails, n.d.), GeneralizedAcceleratedConvex | (1): scope extends to nonconvex quasar objectives and merely continuous gradients. | (1): confidence factor
|
Abbr: