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

MaRDI QIDQ6509016arXivFDO

Authors Naoki Marumo, Akiko Takeda

Published in arXiv

Has companion code repository https://github.com/n-marumo/restarted-hb

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Nonconvex programming, global optimization (90C26) Nonlinear programming (90C30)

Abstract: 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_u^{frac12+2u}epsilo{n}^{-frac4+3u2+2u})$ function and gradient evaluations, where $uin[0,1]$ and $H_u$ are the H"older exponent and constant, respectively. Our algorithm is $u$-independent and thus universal; it automatically achieves the above complexity bound with the optimal $uin[0,1]$ without knowledge of $H_u$. 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.

This page was built for publication: "Universal heavy-ball method for nonconvex optimization under H\""older continuous Hessians"

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