acceptodds
Under review as a conference paper at ICLR 2027

Newton methods beyond Hessian Lipschitz continuity: A nonlinear preconditioning approach

Abstract

Newton-type methods are typically analyzed under Lipschitz continuity of the Hessian, an assumption that can fail for objectives with higher-order or polynomial growth. We introduce a class of nonlinearly preconditioned Newton methods that apply Newton's root-finding scheme to a transformed optimality mapping, thereby extending recent nonlinear preconditioning ideas from first-order methods to the second-order setting. The resulting methods are naturally analyzed under Lipschitz continuity of a preconditioned Hessian, a condition that significantly relaxes the classical Hessian Lipschitz continuity assumption. Under this generalized smoothness model, we establish local superlinear and quadratic convergence guarantees, and develop a globalization strategy for the nonregularized method despite the fact that the preconditioned Newton direction need not be a descent direction. We further propose a regularized variant for isotropic preconditioners, which returns an approximate -second-order stationary point in iterations. An adaptive version removes the need to know the smoothness constant and allows inexact subproblem solutions while preserving the same complexity order.

Primary area:
optimization
Keywords:
Newton methods, generalized smoothness, nonlinear preconditioning

Reviews

Among:
Shape:
1234this paper, Top 15%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 3.00 over 3 reviews, above 85% of the others.
Reviewer_SZhFOpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
2
Read review
Paper summary

This paper studies the Newton methods under Lipschitz continuity of the preconditioned Hessian. Such condition generalizes the Anisotropic smoothness for gradient methods and can be reduced by the (L0,L1)(L_0,L_1)-smoothness of ∇3f(x)\nabla^3 f(x). This paper propose methods with local superlinear convergence rates and global convergence rates for convex and nonconvex settings. The paper is well-motivated.

Critical strengths
  1. The setup studied in this paper is interesting. The generalized smoothness on the preconditioned Hessian is weaker than the classical Hessian smoothness studied in the existing literature. It also covers several important settings. Thus, it is meaningful to develop Newton's methods under this setting.

  2. The convergence analysis is sound. The paper provides convergence guarantees for both strongly-convex, convex, and nonconvex settings.

Critical weaknesses
  1. It remains unclear how to efficiently solve the subproblem for the nonconvex setiing. The current analysis only provide well-definedness of the solution of the subsolver. However, it remains unknown how to solve it. Can the authors present the detailed subroutine of how to solve the problem and the convergence analysis?

  2. Although the quasi-self-concordant (or (L_0,L_1)-smoothness) can lead to the current assumpion, I am wondering if there exists some practical settings that satisfy the current assumption 2.2 but does not satisfy (4)? In addition, I am curious about the cost of computing the H(x) in practice.

Questions for authors

See the weakness part.

2 comments

Dear Reviewer,

Thank you for your review. We are happy to learn that you found our work interesting and sound. Below we address your concerns.

  1. It remains unclear how to efficiently solve the subproblem for the nonconvex setiing.:

The subproblems for the preconditioned Newton methods (Algorithms 2 and 3) can be solved efficiently by applying minor modifications to the standard Lanczos-Krylov techniques for cubic-regularized Newton methods. The high-level idea was already described in Lines 314-323, but we acknowledge that the manuscript would benefit from a more detailed description. For that reason, we have added the new appendix E, which discusses this in detail and highlights the minor modifications needed to handle the preconditioned subproblems.

  1. I am wondering if there exists some practical settings that satisfy the current assumption 2.2 but does not satisfy (4)?:

Condition (4) is a sufficient condition for Assumption 2.2, but not a necessary condition. We have included explicit example for this in the revised manuscript (Example 2.9).

  1. I am curious about the cost of computing the H(x) in practice.

The computational cost of solving the Newton system is discussed in detail in Lines 125-136. In essence, the preconditioned Newton system is equivalent to the original Newton system with a modified right hand side. For the references used in this work (isotropic and separable) this right hand side can be computed efficiently such that the dominant computational cost remains solving a system with the same Hessian ∇2f\nabla^2 f. Overall, this results in a very minor overhead. A similar idea holds for the regularized Newton systems, cf. (5) and (6). Explicitly computing H(x)H(x) is more expensive, but this not required in our algorithms.

We hope this adequately addresses your concerns and would greatly appreciate a reconsideration of our work.

Thank the authors for their response. I will update my score accordingly

Reviewer_FdyrOpenReview ↗
Rating
3
Confidence
4
Informativeness
3
Presentation
3
Soundness
2
Read review
Paper summary

This paper develops Newton methods by applying Newton's root-finding iteration to the transformed optimality mapping. Its central assumption is Lipschitz-continuity of the Jacobian of this mapping. The authors established sufficient conditions which cover phase retrieval and symmetric matrix factorization, characterize local super-linear and quadratic convergence. In addition, they provide a globalization scheme for potentially non-descent Newton directions.

For isotropic reference functions, this draft introduces a regularized method and an adaptive variant allowing inexact subproblem solutions. Both achieve an iteration complexity of O(max⁡ϵg−3/2,ϵH−3)O(\max{\epsilon_{g}^{-3/2}, \epsilon_{H}^{-3}}) in preconditioned stationarity measures. A corollary translates the guarantee to conventional gradient and Hessian measures for a specific reference function. Experiments illustrate the approach on scalar polynomials, PINN training through a preconditioned Levenberg–Marquardt variant, and large-scale symmetric matrix factorization.

Critical strengths
  1. The regularized Newton method has a substantive convergence analysis beyond classical Hessian-Lipschitz-continuity. The main technical contribution is the sufficient-decrease argument for directions generated by the preconditioned system. Note that these directions generally do not minimize a cubic model. The usual cubic-regularization proof does not apply directly. The pathwise argument in Lemma 3.6 addresses this obstacle and supports second-order stationarity guarantees, including adaptive regularization and controlled inexactness. This is the strongest reason for my positive assessment.

  2. This framework connects an interpretable algorithmic construction to concrete objective classes. Applying Newton's method to a transformed gradient makes the proposed iteration easy to understand. The sufficient conditions and application examples show why the transformed Jacobian can remain Lipschitz condition even when the original Hessian does not. This paper also distinguishes the scalar rescaling obtained for unregularized isotropic Newton steps from the nontrivial metric introduced by regularization.

Critical weaknesses

The comparison with the closest generalized-smooth Newton analysis is insufficiently developed. Fang et al. (2026) (https://arxiv.org/abs/2607.10741), which being already cited, obtain conventional second-order stationarity guarantees under a gradient-dependent third-derivative bound. Theorem 2.4 in this draft uses a related bound together with (L0,L1)(L_0, L_1)-smoothness to establish the proposed transformed-Jacobian condition. Although Assumption 2.2 is more general than this sufficient condition, the paper does not clearly explain the quantitative advantage on the shared objective class. Comparing the guarantees in the same stationarity measures would clarify the additional value of nonlinear preconditioning.

Questions for authors

On objective classes satisfying both the sufficient conditions of Theorem 2.4 and the assumptions of Fang et al. (2026), what additional theoretical or algorithmic benefit does the proposed method in the draft provide?

1 comment

Dear Reviewer,

Thank you for the detailed and encouraging feedback. Below we address your remaining questions.

  1. On objective classes satisfying both the sufficient conditions of Theorem 2.4 and the assumptions of Fang et al. (2026), what additional theoretical or algorithmic benefit does the proposed method in the draft provide?

First, we would like to emphasize that Fang et al. (2026) present a conventional cubic-regularized Newton method; the novelty of their work is a sophisticated analysis that leverages the generalized smoothness condition (4) to obtain an interesting worst-case complexity. In contrast, we present a novel class of nonlinearly preconditioned Newton methods where a well-chosen preconditioner may yield improved practical performance.

A key conceptual novelty of our approach is the direct link between smoothness assumption and algorithmic update (through the preconditioner). In order to also showcase the theoretical versatility of our framework, we have established broad sufficient conditions for our smoothness assumptions and proved generalizations of traditional cubic-regularized convergence results. Those results are for generic preconditioners satisfying mild conditions, hence for a broad class of novel algorithms. By leveraging the specific structure of condition (4), the analysis of Fang et al. (2026) yields a similar bound in terms of the tolerance, and a sharper bound in terms of the smoothness constants. In contrast, our analysis was meant to be as general as possible (general smoothness assumption, general preconditioner), and we believe that a sharper bound in terms of the smoothness constants can be obtained by specializing the preconditioners further and leveraging this in the analysis. We have updated the manuscript to state these things more explicitly.

Finally, we believe that these novel preconditioned Newton variants may result in significant improvements in practical performance, whereas Fang et al. analyzed a conventional Newton variant. Prior knowledge, for example about the objective's growth, can be leveraged to design a good preconditioner in a principled manner. We have included additional experiments to further support this claim. We also note that the novel regularization suggested by our theory (based on ∇2ϕ\nabla^2 \phi instead of II), also appears quite beneficial in other Newton variants, as shown by the LM variant for PINN training.

  1. Comparing the guarantees in the same stationarity measures would clarify the additional value of nonlinear preconditioning.:

We have included an explicit comparison with the analysis from Fang et al. (2026) in Lines 390-406.

We hope that we have accurately answered your questions.

Reviewer_t7u7OpenReview ↗
Rating
3(+1)
Confidence
3
Informativeness
2
Presentation
2
Soundness
3
Read review
Paper summary

In this paper, the authors propose a novel approach for preconditioning of second-order methods. The idea is to apply Newton method for root finding to a nonlinearly transformed gradient. The resulting methods (Newton-type and its globalized versions) are analyzed under the assumption of Lipschitz continuity of preconditioned Hessian rather than the Hessian itself. The authors prove local quadratic convergence and globalize Newton scheme using gradient directions achieving GD rate.For isotropic reference functions, they further develop regularized Newton methods, including an adaptive variant with inexact subproblem solutions, achieving an O(max⁡εg−3/2,εH−3)O(\max{\varepsilon_g^{-3/2},\varepsilon_H^{-3}}) iteration complexity.

Critical strengths
  1. The paper presents several interesting and elegant ideas: applying Newton scheme to nonlinearly transformed optimality condition, globalization using regularization, the usage of gradient directions to achieve the global convergence.
  2. The authors provide a solid theoretical analysis of the proposed methods, including local quadratic convergence and global convergence guarantees.
  3. The connection to generalized second-order smoothness and the explicit construction of a preconditioner provide a concrete application of the proposed framework.
Critical weaknesses
  1. Practicality. The paper provides explicit recipes for choosing preconditioners, mainly for two classes of problems: 1D polynomials and functions satisfying generalized (L0,L1)(L_0,L_1)-smoothness with an additional third-order smoothness condition. Therefore, the main concrete application of the framework is a new second-order method under generalized Hessian smoothness. However, a direct comparison with the cubic-regularized Newton method of Fang et al. (2026) is missing, both theoretically and experimentally. It is unclear whether one should prefer constructing a preconditioner (e.g., as in Theorem 2.4) over directly applying existing methods designed for generalized smoothness.

  2. Experiments and implementation. I find the experimental evaluation somewhat disconnected from the proposed theory. The PINN experiments use a modified Levenberg–Marquardt method with a Gauss–Newton approximation, fixed regularization, and Armijo line search, which is not covered by the theoretical results. The large-scale matrix factorization experiment in Appendix E evaluates Algorithm 3 and shows an improvement over ARC. However, the solution of the regularized subproblem is not sufficiently described. Theorem 3.2 establishes existence of a solution, but the paper only briefly mentions Lanczos–Krylov techniques without explaining how the subproblem conditions are enforced in practice.

Questions for authors
  1. Subsection 3.1 establishes the existence of the subproblem solution. But how it can be solved in practice? What is the iteration cost of the proposed regularized scheme.
  2. Does the reference function constructed in Theorem 2.4 guarantee anisotropic smoothness of the objective under the same assumptions? Can Theorem 2.10 be applied with this choice?
  3. Is it possible to establish the convergence of Algorithm 1 to a strong local minimum? As far as I understand, currently, there is no guarantee, that Algorithm 1 will switch from GD rate to local quadratic.
4 comments

Dear Reviewer,

Thank you for your review. We are glad to hear that you found our work interesting and elegant. Below, we address your remaining concerns.

  1. Subsection 3.1 establishes the existence of the subproblem solution. But how it can be solved in practice? What is the iteration cost of the proposed regularized scheme.:

The subproblems for the preconditioned Newton methods (Algorithms 2 and 3) can be solved efficiently by applying minor modifications to the standard Lanczos-Krylov techniques for cubic-regularized Newton methods. The high-level idea was already described in Lines 314-323, but we acknowledge that the manuscript would benefit from a more detailed description. For that reason, we have added the new appendix E, which discusses this in detail and highlights the minor modifications needed to handle the preconditioned subproblems.

The iteration cost of Algorithms 2 and 3 is precisely solving one subproblem, which reduces to the cost of a conventional cubic-regularized Newton subproblem. The dominant cost of this is either an eigendecomposition of the Hessian (if dimension is small enough), or the approximate Lanczos-Krylov procedure discussed in the newly added appendix.

  1. Does the reference function constructed in Theorem 2.4 guarantee anisotropic smoothness of the objective under the same assumptions? Can Theorem 2.10 be applied with this choice?:

The answer is yes to both questions. We have made this explicit in the revised manuscript.

  1. Is it possible to establish the convergence of Algorithm 1 to a strong local minimum? As far as I understand, currently, there is no guarantee, that Algorithm 1 will switch from GD rate to local quadratic.:

If you are referring to unit step acceptance, i.e., τk=1\tau_k = 1, this is explicitly established in Theorem 2.12. In general Newton's method need not converge superlinearly. Take for example f(x)=x4f(x) = x^4, then Newton updates (N) perform xk+1=23xkx^{k+1} = \frac23 x^k, i.e., the iterates converge linearly. The crucial qualification is that the Hessian is non-degenerate at x⋆=0x^\star = 0. Hence the common assumption that the iterates converge to a strong local minimum where ∇2f(x⋆)≻0\nabla^2 f(x^\star) \succ 0.

  1. A direct comparison with the cubic-regularized Newton method of Fang et al. (2026) is missing, both theoretically and experimentally. It is unclear whether one should prefer constructing a preconditioner (e.g., as in Theorem 2.4) over directly applying existing methods designed for generalized smoothness.:

We kindly refer the Reviewer to our reply to Reviewer Fdyr. In the manuscript, we have included a theoretical comparison, as well as additional experiments involving the method of Fang et al. (2026). It should be noted that Fang et al. consider a conventional cubic-regularized method, and their contribution is a sophisticated worst-case analysis under a generalized smoothness condition. In contrast, we present a novel class of preconditioned Newton methods. Our contribution is both theoretical (novel analysis, direct link between assumed smoothness and algorithmic updates through the preconditioner) and practical (a good preconditioner yields better performance). In particular, the novel regularization by ∇2ϕ\nabla^2 \phi instead of II appears useful in practice.

  1. I find the experimental evaluation somewhat disconnected from the proposed theory.:

Besides the existing large-scale factorization experiment, we have included two additional experiments that implement the proposed Algorithm 3 and compare against the conventional cubic-regularized Newton method of Fang et al. (2026). We believe that the PINN experiments are valuable, as they suggest that our novel regularization mechanism also performs well in combination with other Newton variants (LM in this case, which is a common choice in the context of PINNs).

We hope this adequately addresses your concerns and would greatly appreciate a reconsideration of our work.

Thank you for your response. The new experiments and discussions address most of my concerns.

I have one concern and one question remaining.

Concern: In the comparison with Fang et al. on Poisson regression (Figure 2), you use the same initial regularization parameter. How would the performance change if you tuned it separately for each method?

Question 3: No, my question is whether there is any guarantee that, after sufficiently many iterations, the method will switch from the global GD rate of Theorem 2.11 to the local quadratic convergence rate of Theorem 2.12.

Dear Reviewer,

Thank you for your follow-up.

Concern: We have updated the Poisson regression experiment: σ0\sigma_0 is now tuned over a large grid (10−410^{-4} up to 10810^8); the value with the best median runtime over 6 initializations is chosen for comparison on independent initializations. The revised manuscript adds a figure visualizing the sensitivity with respect to different σ0\sigma_0 values. Overall, the previous conclusion still stands: the proposed methods improve both runtime and sensitivity with respect to the initialization.

Question: Thank you for further clarifying your question. Theorem 2.12 made two assumptions: (i) that the iterates converge sequentially to x⋆x^\star, and (ii) that x⋆x^\star is a strong local minimizer of ff.

  • Regarding (ii): in order to switch to fast local convergence, a local growth condition on the objective is needed; this is standard in the literature, it excludes examples like f(x)=x4f(x) = x^4 for which Newton only converges linearly, and it holds for example under local strong convexity of ff around x⋆x^\star.
  • As for (i): this assumption is in fact redundant; full sequence convergence can be proven formally. We have updated the statement of Theorem 2.12 and its proof to reflect this.

We hope this addresses your remaining concern and question.

Thank you for the additional experiments and clarifications. I will increase my score accordingly.

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.