← All setups

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 f:E→R on a finite-dimensional real inner product space E. For γ∈(0,1], the function is γ-quasar-convex relative to a global minimizer x⋆, with ∥x0−x⋆∥≤R for a given starting point x0∈E and radius R>0. Its Hessian is H-Lipschitz, where H>0, and has operator norm at most L0≥0 at x0. The oracle returns f(x), ∇f(x), and ∇2f(x) at x. For ε>0, the goal is an output x¯∈E satisfying f(x¯)−f(x⋆)≤ε almost surely under P, the law of the algorithm’s randomness.

The optimization problem is minx∈Ef(x). The norm ∥⋅∥ is induced by the inner product on E, and ∥⋅∥op denotes the induced operator norm. The Hessian ∇2f(x):E→E is the derivative of the gradient at x. The algorithm receives E, x0, H, γ, R, L0, and ε.

Our assumptions:

Assumption 1 (Hessian regularity). The function f is twice continuously Fréchet differentiable on E, and ∥∇2f(x)−∇2f(y)∥op≤H∥x−y∥for all x,y∈E,∥∇2f(x0)∥op≤L0.

Assumption 2 (Quasar convexity and initial distance). There exists x⋆∈E such that, for every x∈E, f(x⋆)≤f(x),γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩, and ∥x0−x⋆∥≤R.

Queries may be made at any point of E, and each oracle reply is the exact triple (f(x),∇f(x),∇2f(x)). After the allotted oracle calls, the output must satisfy f(x¯)−f(x⋆)≤εP-a.s. Here x⋆ is a fixed global minimizer; all global minimizers have the same objective value.

Results

On a finite-dimensional real inner-product space, f∈C2 has H-Lipschitz Hessian and a global minimizer x⋆ satisfying γ(f(x)−f(x⋆))≤⟨∇f(x),x−x⋆⟩ for every x. Assume H,R,ε>0, 0<γ≤1, ∥x0−x⋆∥≤R, and ∥∇2f(x0)∥≤L0 with L0≥0. Exact queries return (f,∇f,∇2f). Result (1) uses known H,γ,R,L0,ε and constructs an accelerated cubic Newton output x^ with deterministic accuracy f(x^)−f(x⋆)≤ε; the setup imposes no algorithm restriction.

Comparison for QuasarConvexHessianLipschitz.
Result Oracle complexity Novelty Limitations
(1) QuasarAcceleratedCubicNewton (Ours) (⋆⋆⋆) (review) O((1+γ−3/2T3/8)ℓ) triple calls, including coupling-search queries.
(2) Cubic Newton (Nesterov and Polyak 2006), Thm. 4 O(1+(HD3/ε)1/2) triple calls. Star-convex (γ=1); bounded convex neighborhood of the initial sublevel set, diameter D. (1): for D≍R, T3/8ℓ instead of T1/2 as T→∞. Scope: removes bounded-sublevel-set requirement and allows γ<1. (1) needs γ,L0 and a fixed horizon; much worse constants. Reported crossover only around T≳1037 for γ=1,D=R.
(3) (Hinder et al. 2020), Thm. 2 O((1+γ−1RL/ε)ℓL) function/gradient calls, including search. Special case: globally L-smooth. (1) removes global L-smoothness. On the overlap, fewer raw calls for sufficiently small ε (crossover ε≈γ4L4/(H3R), ignoring logarithms); different oracle costs. (1) requires Hessians and H; leading γ−3/2 instead of γ−1.
(4) (Lee and Valiant 2016), Thm. 2.5 O(poly(n,δ−1,log+⁡(1/ε),log+⁡(1/F),log+⁡R,log+⁡B)) weak sampling value calls. Star-convex; |f|≤B within 10nR of x0. Returns a Gaussian with (1−δ) good mass, with probability 1−F. (1): dimension-free cost; deterministic point accuracy instead of a randomized Gaussian-region guarantee; also covers γ<1. Rates and outputs are not directly comparable. (1) needs smoothness and Hessians; polynomial rather than polylogarithmic accuracy dependence at fixed dimension.
(5) Accelerated cubic Newton (Nesterov 2005), Thm. 2 O(1+T1/3) triple calls. Special case: convex (γ=1); cited 2005 preprint. (1) extends scope from convexity to γ-quasar-convexity. (1) is slower on the convex overlap: T3/8ℓ instead of T1/3 for T≫1.

Abbr: T=HR3/ε; ℓ=log⁡(2+T+L0/(HR)+γ−1); ℓL=1+log⁡(1+γ−1RL/ε); log+⁡a=1+max{0,log⁡a}. D is the neighborhood diameter in (2); L is the global gradient Lipschitz constant in (3); n=dim⁡E, δ,F∈(0,1) are mass-error and failure tolerances, and B>0 is the local absolute-value bound in (4). Triple calls return (f,∇f,∇2f); weak sampling value calls evaluate at Gaussian-sampled points. poly denotes an unspecified fixed polynomial.

Hinder, Oliver, Aaron Sidford, and Nimit Sohoni. 2020. “Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond.” Proceedings of Thirty Third Conference on Learning Theory, Proceedings of machine learning research, vol. 125: 1894–938. https://proceedings.mlr.press/v125/hinder20a.html.
Lee, Jasper C. H., and Paul Valiant. 2016. Optimizing Star-Convex Functions. https://doi.org/10.48550/arXiv.1511.04466.
Nesterov, Yurii. 2005. Accelerating the Cubic Regularization of Newton’s Method on Convex Problems. CORE discussion paper 2005/68. https://webdoc.sub.gwdg.de/ebook/serien/e/CORE/dp2005_68.pdf.
Nesterov, Yurii, and Boris T. Polyak. 2006. “Cubic Regularization of Newton Method and Its Global Performance.” Mathematical Programming 108 (1): 177–205. https://doi.org/10.1007/s10107-006-0706-8.

Lean setup