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

Abstract

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 $\epsilon$ in $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]$ and $H_{\nu }$ are the Hölder exponent and constant, respectively. Our algorithm is $\nu$-independent and thus universal; it automatically achieves the above complexity bound with the optimal $\nu \in [0,1]$ without knowledge of $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 $\epsilon$. Numerical results illustrate that the proposed method is promising.

References in corpus (1)

• Tensor Methods for Minimizing Convex Functions with Hölder Continuous Higher-Order Derivatives