Quasar-Convex Minimization with Lipschitz Hessian
Descriptions may be stale. Consult the linked Lean sources.
Quasar-Convex Minimization with Lipschitz Hessian
We consider minimizing a twice continuously differentiable function
The optimization problem is
Our assumptions:
Assumption 1 (Hessian regularity). The function
Assumption 2 (Quasar convexity and initial
distance). There exists
Queries may be made at any point of
Results
On a finite-dimensional real inner-product space,
| Result | Oracle complexity | Novelty | Limitations |
|---|---|---|---|
| (1) QuasarAcceleratedCubicNewton
(Ours) |
|||
| (2) Cubic Newton (Nesterov and Polyak 2006), Thm. 4 | (1): for |
(1) needs |
|
| (3) (Hinder et al. 2020), Thm. 2 | (1) removes global |
(1) requires Hessians and
|
|
| (4) (Lee and Valiant 2016), Thm. 2.5 | (1): dimension-free cost;
deterministic point accuracy instead of a randomized Gaussian-region
guarantee; also covers |
(1) needs smoothness and Hessians; polynomial rather than polylogarithmic accuracy dependence at fixed dimension. | |
| (5) Accelerated cubic Newton (Nesterov 2005), Thm. 2 | (1) extends scope from
convexity to |
(1) is slower on the
convex overlap: |
Abbr: