Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond

In this paper, we provide near-optimal accelerated first-order methods for minimizing a broad class of smooth nonconvex functions that are strictly unimodal on all lines through a minimizer. This function class, which we call the class of smooth quasar-convex functions, is parameterized by a constant γ ∈ (0,1], where γ = 1 encompasses the classes of smooth convex and star-convex functions, and smaller values of γ indicate that the function can be "more nonconvex." We develop a variant of accelerated gradient descent that computes an ε-approximate minimizer of a smooth γ-quasar-convex function with at most O(γ-1 ε-1/2 log(γ-1 ε-1)) total function and gradient evaluations. We also derive a lower bound of Omega(γ-1 ε-1/2) on the worst-case number of gradient evaluations required by any deterministic first-order method, showing that, up to a logarithmic factor, no deterministic first-order method can improve upon ours.