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 (Birgin et al. Math Program 163:359–368, 2017) with <InlineEquation ID="IEq1"> <EquationSource Format="TEX">$p=3$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>=</mo> <mn>3</mn> </mrow> </math></EquationSource> </InlineEquation>. Inspired by Nesterov (Quartic regularity, 2022), 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 <InlineEquation ID="IEq2"> <EquationSource Format="TEX">$\epsilon $</EquationSource> <EquationSource Format="MATHML"><math> <mi>ϵ</mi> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq3"> <EquationSource Format="TEX">$\mathcal {O}(\epsilon ^{4/3})$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <msup> <mi>ϵ</mi> <mrow> <mn>4</mn> <mo stretchy="false">/</mo> <mn>3</mn> </mrow> </msup> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation> for locally convex iterations, while in the nonconvex case, by at least <InlineEquation ID="IEq4"> <EquationSource Format="TEX">$\mathcal {O}(\epsilon )$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi mathvariant="script">O</mi> <mo stretchy="false">(</mo> <mi>ϵ</mi> <mo stretchy="false">)</mo> </mrow> </math></EquationSource> </InlineEquation>; 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 <InlineEquation ID="IEq5"> <EquationSource Format="TEX">$p=2$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>p</mi> <mo>=</mo> <mn>2</mn> </mrow> </math></EquationSource> </InlineEquation>), achieving either lower objective value or iteration counts.

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

期刊论文
出版模式：

开放获取
发表日期：

2025年7月31日

查看全文

Coralia Cartis,
Wenqi Zhu

摘要

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 (Birgin et al. Math Program 163:359–368, 2017) with $p=3$ $p = 3$ . Inspired by Nesterov (Quartic regularity, 2022), 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 $\epsilon $ $ϵ$ 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 $\mathcal {O}(\epsilon ^{4/3})$ $O (ϵ^{4 / 3})$ for locally convex iterations, while in the nonconvex case, by at least $\mathcal {O}(\epsilon )$ $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$ $p = 2$ ), achieving either lower objective value or iteration counts.