Universal heavy-ball method for nonconvex optimization under H"older continuous Hessians

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 ε in O(Hnu^frac12 + 2 nu ε^- frac4 + 3 nu2 + 2 nu) function and gradient evaluations, where nu ∈ [0, 1] and Hnu 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 ∈ [0, 1] without knowledge of Hnu. In addition, the algorithm does not require other problem-dependent parameters as input, including the gradient's Lipschitz constant or the target accuracy ε. Numerical results illustrate that the proposed method is promising.