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

arXiv1906.11985MaRDI QIDQ6321188

Author name not available (Why is that?)

Publication date: 27 June 2019

Abstract: 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 $gammain(0,1]$, where $gamma=1$ encompasses the classes of smooth convex and star-convex functions, and smaller values of $gamma$ indicate that the function can be "more nonconvex." We develop a variant of accelerated gradient descent that computes an $epsilon$-approximate minimizer of a smooth $gamma$-quasar-convex function with at most $O(gamm{a}^{-1}epsilo{n}^{-1/2}log(gamm{a}^{-1}epsilo{n}^{-1}))$ total function and gradient evaluations. We also derive a lower bound of $Omega(gamm{a}^{-1}epsilo{n}^{-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.

Has companion code repository: https://github.com/nimz/quasar-convex-acceleration

This page was built for publication: Near-Optimal Methods for Minimizing Star-Convex Functions and Beyond

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6321188)