Universal heavy-ball method for nonconvex optimization under Hölder continuous Hessians

We propose a new first-order method for minimizing nonconvex functions with Lipschitz continuous gradients and Hölder continuous Hessians. The proposed algorithm is a heavy-ball method equipped with two particular restart mechanisms. It finds a solution where the gradient norm is less than \(\varepsilon \) $\epsilon$ in \(O(H_{\nu }^{\frac{1}{2 + 2 \nu }} \varepsilon ^{- \frac{4 + 3 \nu }{2 + 2 \nu }})\) $O(H_{\nu }^{\frac{1}{2+2\nu }}{\epsilon }^{-\frac{4+3\nu }{2+2\nu }})$ function and gradient evaluations, where \(\nu \in [0, 1]\) $\nu \in [0,1]$ and \(H_{\nu }\) $H_{\nu }$ are the Hölder exponent and constant, respectively. This complexity result covers the classical bound of \(O(\varepsilon ^{-2})\) $O({\epsilon }^{-2})$ for \(\nu = 0\) $\nu =0$ and the state-of-the-art bound of \(O(\varepsilon ^{-7/4})\) $O({\epsilon }^{-7/4})$ for \(\nu = 1\) $\nu =1$ . Our algorithm is \(\nu \) $\nu$ -independent and thus universal; it automatically achieves the above complexity bound with the optimal \(\nu \in [0, 1]\) $\nu \in [0,1]$ without knowledge of \(H_{\nu }\) $H_{\nu }$ . In addition, the algorithm does not require other problem-dependent parameters as input, including the gradient’s Lipschitz constant or the target accuracy \(\varepsilon \) $\epsilon$ . Numerical results illustrate that the proposed method is promising.