Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond
This provides near-optimal methods for a broad class of nonconvex optimization problems, which is incremental as it extends known results to more general function classes.
The paper tackles the problem of minimizing smooth nonconvex functions that are strictly unimodal on lines through a minimizer, called smooth quasar-convex functions, by developing an accelerated gradient descent variant that achieves an $\\epsilon$-approximate minimizer with at most $O(\\gamma^{-1} \\epsilon^{-1/2} \\log(\\gamma^{-1} \\epsilon^{-1}))$ function and gradient evaluations, and shows a lower bound of $\\Omega(\\gamma^{-1} \\epsilon^{-1/2})$ for deterministic first-order methods.
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 $γ\in (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 $Ω(γ^{-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.