Gradient Regularized Newton Methods

This direction is merged into another direction: Hessian regularization. Its last version stays readable and citable here.

Version 1 of 121 papers29 conceptsfrozen 2026-10-04

Newton’s method is the "gold standard" for optimization because of its local quadratic convergence: if you are close enough to a minimum, it finds the solution almost instantly. However, it is notoriously fragile. If the Hessian is singular, poorly conditioned, or if the function is non-convex, the standard Newton step can explode or head in the wrong direction.

To fix this, researchers have traditionally turned to Cubic Regularization, which adds a third-order term to the model. While theoretically perfect, cubic regularization is computationally expensive because it requires solving a complex sub-problem at every iteration.

A new wave of research suggests a simpler, more elegant alternative: Gradient-Normalized Regularization. By adding a term proportional to the norm of the gradient directly to the Hessian, we can achieve the global stability of cubic methods with the computational simplicity of a single linear solve.

The Intuition of Gradient Damping

The core idea is to modify the Hessian $H(x)$ by adding a regularization term $\lambda I$. The breakthrough lies in how we choose $\lambda$. Instead of a constant or a manually tuned schedule, we set $\lambda$ to be proportional to a power of the current gradient norm, $\|\nabla f(x)\|^p$.

Nikita Doikov demonstrates in Minimizing Quasi-Self-Concordant Functions by Gradient Regularization of Newton Method that this simple modification ensures global convergence for a broad class of functions. The mechanism works through a natural "phasing" of the optimization:

  1. Far from the optimum: The gradient norm $\|\nabla f(x)\|$ is large. The regularization term dominates the Hessian, making the update behave like a stable, small-step Gradient Descent.
  2. Approaching the optimum: As the gradient vanishes, the regularization term $\lambda$ automatically shrinks to zero. The algorithm "morphs" back into a pure Newton method, capturing that signature high-speed local convergence.

This approach, which Andrei Semenov, Martin Jaggi, and Nikita Doikov call Gradient-Normalized Smoothness (GNS), allows the optimizer to adapt to the local curvature without needing to know the global smoothness constants of the function beforehand.

Choosing the Right Power

The choice of the power $p$ in $\|\nabla f(x)\|^p$ determines the theoretical properties of the algorithm:

  • The Square Root ($p=1/2$): In Yet another fast variant of Newton's method for nonconvex optimization, Serge Gratton, Sadok Jerad, and Philippe L. Toint show that using the square root of the gradient norm achieves near-optimal complexity for non-convex problems. This specific scaling mimics the behavior of cubic regularization but only requires solving a single linear system per step.
  • The First Power ($p=1$): This is the standard for GNS and "Faithful-Newton" frameworks. Alexander Lim argues in the Faithful-Newton Framework that this scaling is the most robust for general convex landscapes, particularly when the Hessian might be singular.

Stability in the Face of Approximation

In modern machine learning, we rarely have the exact Hessian. We use approximations like the Fisher matrix, sub-sampled Hessians, or Quasi-Newton updates (BFGS). Gradient regularization is particularly powerful here because it masks the "noise" in these approximations.

Andrei Semenov and colleagues show in Gradient-Normalized Smoothness for Optimization with Approximate Hessians that as long as your approximate Hessian is "good enough," the gradient regularization term will bridge the gap, maintaining global convergence rates that were previously only possible with the exact Hessian.

This principle extends to stochastic settings. Aryan Mokhtari and Alejandro Ribeiro developed the Regularized Stochastic BFGS (RES) algorithm, which uses eigenvalue-based regularization to prevent the numerical instability that usually kills second-order methods in noisy environments. By enforcing a lower bound on the Hessian's eigenvalues—effectively a form of ridge regularization—they ensure the algorithm doesn't overfit to the noise in the stochastic gradient.

Why It Works: Spectral Stabilization

Beyond just "damping" the step, regularization acts as a spectral filter. In Convergence rates of sub-sampled Newton methods, Murat A. Erdogdu explains that when we sub-sample data to estimate a Hessian, the "flat" directions (small eigenvalues) are dominated by sampling noise.

By applying spectral thresholding—replacing small eigenvalues with a constant or gradient-dependent threshold—we preserve the high-curvature information (the "signal") while ignoring the noisy, flat directions. This prevents the optimizer from taking massive, erratic steps in directions where the data provides no clear guidance.

Summary

The shift from complex trust-regions and cubic sub-problems toward Gradient Regularized Newton Methods represents a move toward "Newtonian" speed with "Gradient Descent" simplicity. By using the gradient norm as a dynamic regularizer, these methods:

  1. Simplify computation to a single linear solve.
  2. Guarantee global convergence by automatically damping steps far from the optimum.
  3. Enable approximate Hessians to perform as well as exact ones in practice.

Papers in this version

History & citationVersion 1 · 2026-10-04

Merged into another direction · Permanent link

View frozen version 1

Cite this direction

Latest version (a living page):

@misc{lacuna_gradient_regularized_newton_methods_3868a518,
  title = {Gradient Regularized Newton Methods},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/gradient-regularized-newton-methods/rdr_3868a518311c46d7b8a77021c58ef6ae},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-22},
}

This exact version (version 1, frozen text):

@misc{lacuna_gradient_regularized_newton_methods_3868a518_v1,
  title = {Gradient Regularized Newton Methods},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/gradient-regularized-newton-methods/rdr_3868a518311c46d7b8a77021c58ef6ae/v/1},
  note = {Version 1, frozen 2026-10-04. Accessed 2026-11-22},
}