# Second-order methods for quartically-regularised cubic polynomials, with applications to high-order tensor methods

arXiv: https://arxiv.org/abs/2308.15336 · HTML: https://mlsanity.com/paper/2308.15336/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Aug 2023.

## Built on by (most cited first, 1 of 1)

- [Higher-Order Newton Methods with Polynomial Work per Iteration](https://mlsanity.com/paper/2311.06374/) (2023)

## Abstract (arXiv)

There has been growing interest in high-order tensor methods for nonconvex optimization, with adaptive regularization, as they possess better/optimal worst-case evaluation complexity globally and faster convergence asymptotically. These algorithms crucially rely on repeatedly minimizing nonconvex multivariate Taylor-based polynomial sub-problems, at least locally. Finding efficient techniques for the solution of these sub-problems, beyond the second-order case, has been an open question. This paper proposes a second-order method, Quadratic Quartic Regularisation (QQR), for efficiently minimizing nonconvex quartically-regularized cubic polynomials, such as the ARp sub-problem [3] with p=3. Inspired by [35], QQR approximates the third-order tensor term by a linear combination of quadratic and quartic terms, yielding (possibly nonconvex) local models that are solvable to global optimality. In order to achieve accuracy ε in the first-order criticality of the sub-problem in finitely many iterations, we show that the error in the QQR method decreases either linearly or by at least O(ε4/3) for locally convex iterations, while in the nonconvex case, by at least O(ε); thus improving, on these types of iterations, the general cubic-regularization bound. Preliminary numerical experiments indicate that two QQR variants perform competitively with state-of-the-art approaches such as ARC (also known as ARp with p=2), achieving either a lower objective value or iteration counts.