We propose a new first-order method for minimizing nonconvex functions with Lipschitz continuous gradients and H\"older 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\"older 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.
Categories: math.OC