Global $\mathcal{O}\left(k^{-2}\right)$ Convergence of Multilevel Gradient-Regularized Newton Methods

Nick Tsipinakis; Matthias Voigt

math.OCOct 26, 2026

Global $\mathcal{O}\left(k^{-2}\right)$ Convergence of Multilevel Gradient-Regularized Newton Methods

Authors: Nick Tsipinakis, Matthias Voigt

Organizations: Faculty of Mathematics and Computer Science, UniDistance Suisse, Brig, Switzerland

Abstract

We develop and analyze multilevel gradient-regularized Newton methods for unconstrained convex optimization with Lipschitz-continuous Hessians. By computing Newton corrections in lower-dimensional subspaces, the proposed methods aim to reduce computational costs while preserving the global $\mathcal{O}\left(k^{-2}\right)$ convergence rate in function values of the full-space method. To establish this rate for multilevel methods, we introduce a class of row-nested restriction operators that ensures monotonicity of the reduced-gradient norms across levels. Numerical experiments with row-nested operators demonstrate convergence behavior comparable to full-space gradient-regularized Newton, while offering substantial computational savings on large-scale instances.

Figures & tables

x_{k+1}\coloneqq\begin{cases}x_{k}-P\left(R\nabla^{2}f_{k}P+\sqrt{\frac{\omega^{3}L\left\lVert R\nabla f_{k}\right\rVert}{2}}I_{d}\right)^{-1}R\nabla f_{k},&k\in\mathcal{C},\\ x_{k}-\left(\nabla^{2}f_{k}+\sqrt{\frac{L\left\lVert\nabla f_{k}\right\rVert}{2}}I_{n}\right)^{-1}\nabla f_{k},&k\in\mathcal{F}.\end{cases}

Algorithm 1 Two-Level Regularized Newton (TLRN)

x_{k+1}\coloneqq\begin{cases}x_{k}-P_{i}\left(R_{i}\nabla^{2}f_{k}P_{i}+\sqrt{\dfrac{\omega_{i}^{3}L\left\lVert R_{i}\nabla f_{k}\right\rVert}{2}}\,I_{n_{i}}\right)^{-1}R_{i}\nabla f_{k},&k\in\mathcal{C}_{i},i\in\mathcal{J},\\[8.61108pt] x_{k}-\left(\nabla^{2}f_{k}+\sqrt{\dfrac{L\left\lVert\nabla f_{k}\right\rVert}{2}}\,I_{n}\right)^{-1}\nabla f_{k},&k\in\mathcal{F}^{(\ell)}.\end{cases}

Algorithm 2 MultiLevel Regularized Newton (MLRN)

Panel of Figure 1 — Figure 1: Convergence comparison of MLRN, row-nested MLRN, regularized Newton (RN), and two-level regularized Newton (TLRN) for the log-sum-exp objective with $\gamma\in\{0.05,0.1,0.5\}$ . The left column shows the objective gap $f(x_{k})-f^{*}$ versus iterations, while the right column shows the objective gap versus wall-clock time. Row-nested MLRN and TLRN methods demonstrate comparable convergence behavior to RN.

Panel of Figure 2 — Figure 2: Convergence comparison of MLRN, row-nested MLRN, regularized Newton (RN), and two-level regularized Newton (TLRN) using the large Gisette and Duke datasets for logistic regression. The left column reports the objective gap $f(x_{k})-f^{*}$ versus iterations, while the right column reports the objective gap versus wall-clock time. The multilevel gradient-regularized Newton methods offer substantial computational savings compared to their full-space counterpart.

Panel of Figure 3 — Figure 3: Convergence comparison of MLRN, row-nested MLRN, regularized Newton (RN), and two-level regularized Newton (TLRN) on the a9a, Mushrooms, and w8t datasets for logistic regression. The left column reports the objective gap $f(x_{k})-f^{*}$ versus iterations, while the right column reports the objective gap versus wall-clock time. Row-nested restriction operators significantly improve the convergence behavior of MLRN.

Optimization Convergence Analysis

Optimization convergence analysis studies whether and how quickly iterative algorithms approach solutions, and which assumptions ensure reliable progress.

See all 75 papers

Primal Acceleration of Newton's Method
Aug 21, 2026Nikita DoikovSecond-Order Optimization
School of Operations Research and Information Engineering (ORIE), Cornell University, Ithaca, NY, USA.
Gradient Regularized Newton Boosting Trees with Global Convergence
May 1, 2026Nikita Zozoulenko, Daniel Falkowski, Thomas Cass +1Gradient-Boosted Decision Trees Optimization Convergence Analysis
Department of Mathematics, Imperial College London, UK · Department of Mathematics, Stockholm University, Sweden · School of Computer Science, University of St. Gallen, Switzerland
Randomized Subspace Nesterov Accelerated Gradient
May 1, 2026Gaku Omiya, Pierre-Louis Poirion, Akiko TakedaGradient Descent Randomized Sketching
Department of Mathematical Informatics, The University of Tokyo, Tokyo, Japan · Center for Advanced Intelligence Project, RIKEN, Tokyo, Japan

Aug 21, 2026J/K move · Enter open · S save

Primal Acceleration of Newton's Method

Nikita Doikov

School of Operations Research and Information Engineering (ORIE), Cornell University, Ithaca, NY, USA.

Second-Order Optimization

Open paper AskPDF arXiv

We develop a new direct accelerated Newton method for minimizing convex functions with Lipschitz continuous Hessian. The algorithm uses only primal variables and performs just one linear solve per iteration. With a simple predetermined choice of parameters, it achieves the global convergence rate of

O(1/k^3)

in terms of the functional residual. To the best of our knowledge, this is the first second-order method for this problem class attaining this rate while relying solely on one linear system solve per iteration (without solving auxiliary nonlinear regularized subproblems, such as cubic regularization, performing nonlinear parameter searches, or using dual extragradient corrections). Our method can be implemented in a Hessian-free way, using an inexact linear system solver, while preserving the fast global rate. We further extend our construction to arbitrary geometry through Bregman divergence, and to composite optimization problems.

Abstract

Optimization Convergence Analysis

Explore similar work

Primal Acceleration of Newton's Method

Gradient Regularized Newton Boosting Trees with Global Convergence

Randomized Subspace Nesterov Accelerated Gradient