A Fast Newton Method Under Local Lipschitz Smoothness
S. Gratton, S. Jerad and Ph. L. Toint · 2025
Read A Fast Newton Method Under Local Lipschitz Smoothness by S. Gratton, S. Jerad and Ph. L. Toint (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-2505-04807.txt.
Introduction
Serge Gratton, Sadok Jerad, and Philippe Toint propose a faster Newton method for optimization problems. Newton methods use curve data to take smart steps toward a low point. Classic proofs need a strong global claim about how smooth that curve data are, which many real problems fail.
The new method needs only a local smoothness claim near the path it takes. It still reaches near optimal speed for finding points where the slope is near zero. Steps use an exact Newton move when the curve bends up, and a curve aware move when it bends down. Low cost inexact versions use iterative linear solvers. Early tests show the method holds its own against strong rivals.
Catalog record
| CREATOR | S. Gratton, S. Jerad and Ph. L. Toint |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 86 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2505-04807
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
A Fast Newton Method Under Local Lipschitz Smoothness S. Gratton, S. Jerad and Ph. L. Toint Abstract A new, fast second-order method is proposed that achieves the optimal 𝒪 ( | log ( ϵ ) | ϵ − 3 / 2 ) \mathcal{O}\left(|\log(\epsilon)|\epsilon^{-3/2}\right) complexity to obtain first-order ϵ \epsilon -stationary points. Crucially, this is deduced without assuming the standard global Lipschitz Hessian continuity condition, but only using an appropriate local smoothness requirement. The algorithm exploits Hessian information to compute a Newton step and a negative curvature step when needed, in an approach similar to that of [ 18 ] . Inexact versions of the Newton step and negative curvature are proposed in order to reduce the cost of evaluating second-order information. Details are given of such an iterative implementation using Krylov subspaces. An extended algorithm for finding second-order critical points is also developed and its complexity is again shown to be within a log factor of the optimal one. Initial numerical experiments are discussed for both factorised and Krylov variants, which demonstrate the competitiveness of the proposed algorithm. Standard nonlinear optimization algorithms such as gradient descent or Newton’s method are widely used in a vast array of applications. However their theoretical analysis typically uses the somewhat restrictive assumptions that gradients or higher derivatives are globally Lipschitz continuous [ 6 ] . Unfortunately, this assumption does not hold in simple cases such as polynomials or exponentials. While it can be argued that the assumption is only necessary on the “tree of iterates” (that is the union of all segments defined by algorithm’s steps (see [ 6 , Notes p.47] for instance), it remains desirable to relax it more significantly. Some progress in this direction has been made in [ 24 , 37 ] , where only local Lipschitz smoothness is assumed, but it only applies to the convex case. In the nonconvex case, motivated by the geometry of the loss-landscape in modern deep learning problems and the success of normalized gradient descent in this context, [ 38 ] proposed a new smoothness condition for the analysis of this latter method, called (L_{0},L_{1}) smoothness, which assumes that there exist constants L_{0}\geq 0 and L_{1}>0 , such that, \|\nabla_{x}^{2}f(x)\|\leq L_{0}+L_{1}\|\nabla_{x}^{1}f(x)\|. (0.1) This new assumption was shown to be more relevant in practice as it covers univariate polynomial functions of all degrees, for instance. We refer the reader to [ 38 , 36 ] for additional motivation for the study of first-order method under ( 0.1 ) and for a complexity analysis in both the deterministic and stochastic cases. This proposal generated a new interest in the analysis of nonconvex gradient descent. New classes of smoothness and refinements of the initial analysis have been proposed in [ 21 , 36 , 22 , 7 ] both in the exact and stochastic case. Extensions to other classes of problems or different update rules have been proposed, such as adaptive-gradient methods [ 15 , 23 ] , variance reduction [ 28 ] and variational problems [ 30 ] to name just a few. Note also that ( 0.1 ) can be rephrased as \|\nabla_{x}^{1}f(x)-\nabla_{x}^{1}f(y)\|\leq(L_{0}+L_{1}\|\nabla_{x}^{1}f(x)\|),\;\;\mbox{ if }\;\;\|x-y\|\leq\frac{1}{L_{1}}, (0.2) to avoid the use of second-order derivatives (see [ 28 , 36 ] for further discussions on the equivalence between ( 0.1 ) and ( 0.2 )). Extending the approach to second-order methods for optimization is thus of interest, in order to enlarge the applicability of such results beyond what is used for standard approaches [ 6 ] . To the best of our knowledge, only [ 33 ] has so far proposed an optimal trust-region method under a Lipschitz smoothness assumptions similar to ( 0.2 ). However, the proposed algorithm unrealistically requires the knowledge of the problem’s Lipschitz constant, uses a trust region with a fixed radius, and computes an exact solution of the trust-region subproblem, thus requiring intensive numerical linear algebra to compute the step at each iteration. On the other hand, a vast array of work [ 29 , 35 , 39 , 18 ] has been proposed in order to develop fast regularized Newton methods with a complexity guarantee close to {\cal O}\left(\epsilon^{-3/2}\right) evaluations to find an \epsilon -first order stationary point. Among this work, some required the knowledge of the criticality threshold [ 29 , 35 ] to achieve the bound {\cal O}\left(\epsilon^{-3/2}\right) . This requirement was bypassed in [ 18 ] by alternating carefully between regularized Newton step and negative curvature and utilizing the current gradient norm to regularize the Newton system. However, this approach incurs an additional |\log(\epsilon)| in the complexity. Recently, [ 39 ] combined the regularization proposed in [ 18 ] with the capped-CG analysis developed in [ 29 ] and reduced the extra cost of not knowing the criticality threshold \epsilon to |\log(\log(\frac{1}{\epsilon}))| which is better than the |\log(\epsilon)| of [ 18 ] . In the present paper, inspired by the new Hessian Lipschitz smoothness condition proposed in [ 33 ] , we develop an adaptive Newton’s method that requires at most {\cal O}\left(|\log(\epsilon)|\epsilon^{-3/2}\right) evaluations to find an \epsilon -first order stationary point. The met hod proposed is in spirit of [ 18 ] as it alternates between Newton directions and directions of negative curvature and also uses negative-curvature information to regularize the Newton step. Beyond requiring significantly weaker smoothness, it however differs from the proposal in this reference in crucial aspects, such as the power of regularization and the mechanism to accept or reject trial steps. The new method is fully adaptive and knowledge of the problem’s geometry is not assumed. Two implementations are proposed, the first requiring exact negative curvature computation and exact linear-system solves, and the second allowing more inexactness and exploiting the structure of nested Krylov subspaces. The paper is organized as follows. Section 1 starts by stating our new Lipschitz smoothness condition, describes the general algorithmic framework, compares it with closely related work on second-order methods and states properties on the computed step. Section 2 derives a bound on its worst-case complexity for finding first-order critical points. Section 3 details an algorithmic enhancement for the search for a second-order critical point, with its associated complexity proof discussed in Appendix B . Section 4 describes proposed procedures to compute the step and the incorporation of preconditionning. The numerical behaviour of the proposed algorithms is considered in Section 5 and some conclusions and perspectives are discussed in Section 6 . Notations Let n\geq 1 . The symbol \|\cdot\| denotes the Euclidean norm for vectors in \hbox{I\hskip-2.0ptR}^{n} and its associated subordinate norm for matrices. \lambda_{\min}(M) and \lambda_{\max}(M) denote the minimum and maximum eigenvalues of a symmetric matrix M , while I_{n} is the identity matrix in \hbox{I\hskip-2.0ptR}^{n\times n} . For x\in\hbox{I\hskip-2.0ptR} , we define [x]_{+}=\max(x,0) . For two vectors x,y\in\hbox{I\hskip-2.0ptR}^{n} , x^{\intercal}y denotes their inner product. The i -th column of I_{n} is denoted by e_{i} . 1 Adaptive Newton with Negative Curvature using Local Smoothness We consider the problem of finding approximate first-order critical points of the smooth unconstrained nonconvex optimization problem \min_{x\in\hbox{I\hskip-2.0ptR}^{n}}f(x) (1.1) under the following set of assumptions. AS.1 The function f is two times continuously differentiable in \hbox{I\hskip-2.0ptR}^{n} . AS.2 There exists a constant f_{\rm low} such that f(x)\geq f_{\rm low} for all