Global Optimality Characterizations and Algorithms for Minimizing Quartically-Regularized Third-Order Taylor Polynomials

Coralia Cartis and, Wenqi Zhu · 2025

Read Global Optimality Characterizations and Algorithms for Minimizing Quartically-Regularized Third-Order Taylor Polynomials by Coralia Cartis and, Wenqi Zhu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2504-20259.txt.

Introduction

Wenqi Zhu and Coralia Cartis characterize global optima for cubic models wrapped in quartic regularization, a core step in high-order optimization. Such methods use Taylor models to move faster. Knowing the true best point of each subproblem is essential.

They state when a point is globally best, with proof both ways. Older quadratic results fall out as special cases. Low-rank and diagonal tensor cases simplify nicely. A bound on the penalty links criteria to convexification. Sum-of-squares tools enter through that same door. A diagonal tensor method is built on the theory. It targets the regularized cubic subproblem directly. The work firms up adaptive regularization methods.

Catalog record

CREATORCoralia Cartis and, Wenqi Zhu
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE112 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2504-20259

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Global Optimality Characterizations and Algorithms for Minimizing Quartically-Regularized Third-Order Taylor Polynomials Coralia Cartis and, Wenqi Zhu Abstract High-order methods for convex and nonconvex optimization, particularly p p th-order Adaptive Regularization Methods (AR p p ), have attracted significant research interest by naturally incorporating high-order Taylor models into adaptive regularization frameworks, resulting in algorithms with better worst-case global evaluation complexity and faster local convergence rates than first- and second-order methods. However, for p ≥ 3 p\geq 3 , characterizing global optimality and efficiently minimizing high-order Taylor models with regularization terms remains an open question. This paper establishes global optimality conditions for general, nonconvex cubic polynomials with quartic regularization. These criteria generalise existing results, recovering the optimality results for regularized quadratic polynomials, and can be further simplified in the low-rank and diagonal tensor cases. Under suitable assumptions on the Taylor polynomial, we derive a lower bound for the regularization parameter such that the necessary and sufficient criteria coincide, establishing a connection between this bound and the subproblem’s convexification and sum-of-squares (SoS) convexification techniques. Leveraging the optimality characterization, we develop a Diagonal Tensor Method (DTM) for minimizing quartically-regularized cubic Taylor polynomials by iteratively minimizing a sequence of local models that incorporate both diagonal cubic terms and quartic regularization (DTM model). We prove that the DTM algorithm is convergent, with a global evaluation complexity of 𝒪 ( ϵ − 3 / 2 ) \mathcal{O}(\epsilon^{-3/2}) . Furthermore, when a special structure is present (such as low rank or diagonal), DTM can exactly solve the given problem (in one iteration). In our numerical experiments, we propose practical DTM variants that exploit local problem information for model construction, which we then show to be competitive with cubic regularization and other subproblem solvers, with superior performance on problems with special structure. 1 Introduction and Problem Set-up Recent works show that p th-order Adaptive Regularization Methods (AR p , with p\geq 3 ), which incorporate higher-order derivatives into adaptive regularization frameworks, achieve faster global and local convergence rates than first- and second-order methods, both in theory and in numerical experiments [ 8 , 18 , 19 , 28 ] . The minimization of regularized polynomials lies at the core of regularization-based high-order optimization methods. Given the unconstrained nonconvex optimization problem \min_{x\in\mathbb{R}^{n}}f(x), where f:\mathbb{R}^{n}\rightarrow\mathbb{R} is p -times continuously differentiable and bounded below, with p\geq 1 . The AR p framework is constructed as such, use a local (p+1) -degree polynomial model \displaystyle\min_{s\in\mathbb{R}^{n}}m_{p}(x_{k},s)=T_{p}(x_{k},s)+\frac{\sigma_{k}}{p+1}\|s\|^{p+1}, (1) to approximate f(x_{k}+s) , where T_{p}(x_{k},s) is the p th-order Taylor expansion of f(x_{k}+s) at x_{k} . Here \sigma_{k}>0 is a regularization parameter that ensures the model is bounded below; it is adjusted adaptively to ensure progress toward optimality across iterations. At each iteration, x_{k} is updated via s_{k}\approx\arg\min_{s\in\mathbb{R}^{n}}m_{p}(x_{k},s), x_{k+1}:=x_{k}+s_{k}, whenever sufficient objective decrease is achieved. This process continues until an approximate local minimizer of f is obtained, satisfying \|\nabla f(x_{k})\|\leq\epsilon_{g} . It is shown in [ 14 , 16 ] that the AR p algorithm needs at most \mathcal{O}(\epsilon_{g}^{-\frac{p+1}{p}}) evaluations of f and its derivatives to obtain a point with \|\nabla f(x_{k})\|\leq\epsilon_{g} , and this bound is optimal for this function class. This result demonstrates that as we increase the order p , the evaluation complexity bound improves, which is a key motivation for implementing this method. When p=1 , minimizing ( 1 ) leads to variants of the steepest-descent algorithm. The case p=2 corresponds to Newton-type algorithms, yielding adaptive cubic regularization (AR2/ARC) variants [ 16 ] . In this paper, we focus on the case p=3 and ( 1 ) becomes the minimization of nonconvex cubic polynomials with quartic regularization m_{3}(x_{k},s)=f(x_{k})+\nabla_{x}f(x_{k})^{T}s+\frac{1}{2}\nabla_{x}^{2}f(x_{k})[s]^{2}+\frac{1}{6}\nabla_{x}^{3}f(x_{k})[s]^{3}+\frac{\sigma_{k}}{4}\|s\|_{W}^{4} (AR 3 Model) where \nabla^{j}f(x_{k})[s]^{j} is the j th-order derivative of f at x_{k} along s\in\mathbb{R}^{n} for j=2,3 . \nabla_{x}^{2}f(x_{k}) is a symmetric matrix, \nabla_{x}^{3}f(x_{k})\in\mathbb{R}^{n\times n\times n} is a symmetric third-order tensor 1 1 1 A symmetric tensor means that the entries are invariant under any permutation of its indices, and W is a symmetric, positive-definite matrix with norm 2 2 2 Unless otherwise stated, \|\cdot\| denotes the Euclidean norm in this paper. \|v\|_{W}:=\sqrt{v^{T}Wv} . Note that typically the regularization term uses the Euclidean norm. Here, we use the W norm for generality, which is particularly useful when applying a change of basis. One of the most critical challenges for higher-order methods is the efficient minimization of the p th-order subproblem for p\geq 3 . Developing effective algorithms for minimizing the AR 3 subproblem remains an active area of research. Schnabel et al. [ 23 , 47 ] were among the first to explore third-order tensor models for unconstrained optimization without regularization terms. Following that, for convex m_{3} , Nesterov proposed a series of methods tailored for its minimization [ 40 , 41 , 42 , 43 , 44 , 39 ] . These methods leverage convex optimization techniques, including Bregman gradient approaches, high-order proximal operators, and iterative convex quadratic models with quartic regularization. In the nonconvex setting, recent works by Cartis and Zhu introduced several efficient algorithms and proved their convergence, such as the Quadratic Quartic Regularization (QQR), Cubic Quartic Regularization (CQR), and Sums-of-Squares Taylor (SoS) methods [ 53 , 54 , 21 , 55 ] . Subsequently, numerical implementation and adaptive regularization techniques are provided in [ 20 ] . There is also a body of literature on polynomial optimization that focuses on the (global) minimization of certain quartic polynomials, using tools like SoS techniques, SDP relaxation, and the Lasserre hierarchy [ 1 , 33 , 34 , 35 ] . However, traditionally, these works were not associated with Taylor models and adaptive regularization frameworks. Lately, [ 1 ] proposed a high-order Newton’s method incorporating an SoS-convex approximation of the AR 3 subproblem, and a global convergence rate for SoS-based approximations within nonconvex adaptive regularization was established in [ 55 ] . Despite advancements in these methods, the key question of global optimality characterization for this subproblem remains unresolved. This paper addresses this key research gap by characterizing the global optimality of the AR 3 subproblem. The paper makes the following key contributions. 1. To the best of our knowledge, we are the first to establish necessary and sufficient global optimality condition for a generally nonconvex cubic polynomial with quartic regularization. Unlike quadratic polynomials with regularization, in ( AR 3 Model ), our necessary and sufficient global optimality conditions do not generally coincide. Interestingly, we find that under suitable assumptions for the Taylor polynomial, when the regularization parameter \sigma_{k} is large enough, the necessary and sufficient criteria coincide, and global optimality can be fully characterized. We provide a lower bound for \sigma_{k} and discover that this bound is closely related to the convexification and SoS-convexification of the resulting polynomial. Specifically, the size of the regularization parameter required to close the gap between the necessary and sufficient conditions differs by a constant from that required for SoS-convexification. This provides insight into how the convex and SoS-convex quartically-regularized polynomials are related. 2. We show our global optimality conditions can be seen as a generalization of optimality conditions for various forms of quadratic polynomials with simpler tensor terms or alternative regularization norms. For instance, our results recover the optimality conditions established by Cartis et al [ 16 , Thm 8.2.8] for quadratic polynomials with quartic

Read the complete text