betaFeedback

WorksMathematics

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

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 O(k−2)\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.

Key words. multilevel optimization, regularized Newton methods, convex optimization, row-nested restriction operators

MSC codes. 90C25, 90C30, 65K05, 90C06

Introduction

Cubic regularization of Newton’s method [12, 23] is a fundamental second-order approach for smooth, possibly nonconvex optimization, achieving an O(ε−3/2)O(\varepsilon^{-3/2}) complexity for first-order stationarity in nonconvex problems and a global O(k−2)O(k^{-2}) function-value rate for convex objectives with Lipschitz-continuous Hessians. Subsequent developments include accelerated cubic Newton methods attaining an O(k−3)O(k^{-3}) rate [21] and Adaptive Regularization with Cubics (ARC) [6, 7, 8]. However, cubic regularization requires solving a potentially expensive subproblem at each iteration.

Gradient-regularized Newton methods provide a simpler alternative, with iterations of the form

xk+1=xk−(∇2f(xk)+akI)−1∇f(xk),(1)x_{k+1}=x_k-\left(\nabla^2 f(x_k)+a_k I\right)^{-1}\nabla f(x_k), \tag*{(1)}

where ak>0a_k>0. Following the early work of Polyak [24], Mishchenko [19] and Doikov and Nesterov [9] established that choosing aka_k proportional to L∥∇f(xk)∥\sqrt{L\|\nabla f(x_k)\|} yields the global O(k−2)O(k^{-2}) function-value rate for convex objectives with Lipschitz-continuous Hessians, improving upon the O(k−1)O(k^{-1}) rate of standard gradient descent. Nevertheless, computing full-dimensional Hessians and solving the corresponding linear systems can be prohibitively expensive for large-scale problems.

Inspired by classical multigrid methods [4], multilevel optimization reduces these costs by computing corrections in lower-dimensional spaces, replacing full-dimensional Newton systems with smaller ones. Multilevel strategies have been successfully developed for Newton and regularized Newton methods [11, 14, 26, 29], higher-order regularization methods, including ARC [5], as well as line-search, preconditioned, accelerated gradient, and proximal methods [1, 16, 25, 30].

In a foundational work, Gratton, Sartenaer, and Toint [11] introduced recursive multilevel trust-region (RMTR) methods, establishing an O(ε−2)O(\varepsilon^{-2}) worst-case complexity bound for first-order stationarity in possibly nonconvex problems. Their framework permits recursion to a coarser level when

∥Rigi,k∥≥κg∥gi,k∥,∥Rigi,k∥>εi−1g,(2)\|R_i g_{i,k}\| \geq\kappa_g\|g_{i,k}\|,\qquad\|R_i g_{i,k}\|>\varepsilon_{i-1}^{g}, \tag*{(2)}

where gi,kg_{i,k} is the gradient of the current level-dependent model, κg>0\kappa_g > 0 is a prescribed parameter, and Ri∈Rni−1×niR_i \in\mathbb{R}^{n_{i-1}\times n_i} restricts information to the next coarser level. Importantly, this eligibility condition is evaluated before computing a coarse correction, avoiding additional trial steps for level selection.

In general, second- or higher-order multilevel methods need not inherit the fast convergence rates of their full-space counterparts, since coarse corrections exploit only partial second- or higher-order information. Notable results preserving full-space convergence guarantees include RMTR [11] and the high-order multilevel methods of Calandra et al. [5], which attain the O(ε−3/2)O(\varepsilon^{-3/2}) first-order stationarity complexity of cubic regularization for possibly nonconvex problems. More recently, for convex objectives, the multilevel gradient-regularized Newton method [27] was shown to achieve the global O(k−2)O(k^{-2}) function-value rate, while the adaptive multilevel Newton method [28] achieves local quadratic convergence for strongly convex objectives.

However, the deterministic formulations of these last two methods rely on a stronger level-selection criterion, namely

∥Ri∇f(xk)∥≥σ∥∇f(xk)∥,∥Ri∇f(xk+1)∥≥σ∥∇f(xk+1)∥.(3)\lVert R_i\nabla f(x_k)\rVert\ge\sigma\lVert\nabla f(x_k)\rVert,\qquad\lVert R_i\nabla f(x_{k+1})\rVert\ge\sigma\lVert\nabla f(x_{k+1})\rVert. \tag*{(3)}

The second condition requires computing a trial coarse step to evaluate the gradient at the prospective next iterate, potentially increasing the computational cost. In contrast, the classical eligibility criterion (1.2) uses only current-iterate information. To the best of our knowledge, a direct global O(k−2)O(k^{-2}) convergence analysis for deterministic multilevel gradient-regularized Newton methods employing such a pre-step level-selection criterion has remained unavailable. Establishing this rate will provide theoretical justification for employing multilevel methods in convex optimization, combining the fast convergence guarantees of full-space Newton methods with the potential computational savings of lower-dimensional corrections.

Contributions. We develop multilevel gradient-regularized Newton methods for convex objectives with Lipschitz-continuous Hessians, exploiting lower-dimensional subspaces and the classical level-selection criterion (1.2) (cf. [11]). We show that these methods preserve the global O(k−2)O(k^{-2}) function-value rate of their full-space counterpart. For two levels, Theorem 2.5 establishes this rate under arbitrary coarse/fine alternation. For multiple levels with general restriction operators, Theorem 3.3 requires an explicit fine-iteration frequency condition, which is eventually satisfied by the algorithm (Subsection 3.1) but may be restrictive during coarse-dominated phases. To eliminate this condition, we introduce row-nested restriction operators (Subsection 3.2), whose structure guarantees monotonicity of reduced-gradient norms across levels. Exploiting this property, we establish the global O(k−2)O(k^{-2}) rate without imposing any fine-iteration frequency condition (Theorem 3.8).

Our analysis builds on the ideas of [19], but addresses a fundamental difficulty absent from full-space methods: coarse and fine corrections control different gradient norms, whose convergence properties cannot be directly transferred across levels. To overcome this, we introduce a level-dependent weighted gradient measure that provides uniform control across all possible coarse-to-fine, coarse-to-coarse, and fine-to-coarse transitions. This, together with the proposed class of row-nested restriction operators (Definition 3.4), constitutes the main theoretical novelty of our analysis, enabling us to preserve the convergence rate of the full-space method without imposing any condition on the frequency of fine-level iterations.

We support our theoretical analysis with numerical experiments comparing the proposed methods against the full-space gradient-regularized Newton method. The results demonstrate that the two-level and row-nested multilevel methods exhibit convergence behavior comparable to that of their full-dimensional counterpart, while achieving substantial reductions in computational time on large-scale instances. Furthermore, the experiments highlight the importance of the restriction operator structure, with row-nested hierarchies generally exhibiting more favorable convergence behavior than their non-nested counterparts. These findings suggest that row-nested restriction operators can offer an attractive choice from both theoretical and computational perspectives.

Related work

Early multilevel optimization frameworks were developed by Nash [20] and Lewis and Nash [18], including implementations based on truncated-Newton methods. A common feature of subsequent multilevel methods [5, 11, 13, 14] is the use of coarse-level eligibility conditions of the form (1.2). Wen and Goldfarb [30] developed a line-search multigrid method establishing R-linear convergence under strong convexity and suitable conditions on the search directions. Calandra et al. [5] extended higher-order regularization to multilevel optimization. Other multilevel Newton-type methods [14, 26, 29] establish global convergence or fast local rates under specific assumptions. However, unlike our approach, these Newton-type methods do not employ gradient-dependent Hessian regularization to handle potentially singular Hessians, nor do they establish the global O(k−2)O(k^{-2}) function-value rate for general convex objectives.

Tsipinakis and Parpas [27] developed the multilevel gradient-regularized Newton method achieving the global O(k−2)O(k^{-2}) function-value rate for convex objectives. However, unlike the methods proposed in this paper, their method requires the look-ahead condition (1.3), introducing additional computational costs. This condition avoids directly analyzing transitions between coarse and fine gradient measures and thus their proof cannot be applied to our setting. In contrast, our analysis preserves the global O(k−2)O(k^{-2}) rate under classical level selection without requiring look-ahead trial steps.

Nested subspaces are widely used in Krylov-based trust-region methods, reduced-basis approximation, and multilevel optimization [2, 10, 13]. The row-nested restriction operators considered here additionally guarantee monotonicity of the restricted-gradient norms across levels. Moreover, the weighted-gradient analysis is closely related to multiple-Lyapunov-function techniques for switched systems [3, 31]. In our setting, we combine a suitably weighted gradient measure with regularized Newton decrease bounds to establish a global O(k−2)O(k^{-2}) convergence rate in function values under arbitrary coarse/fine alternation.

Main assumptions and notation

We consider the unconstrained optimization problem

min⁡x∈Rnf(x),\min_{x\in\mathbb{R}^{n}} f(x),

where f:Rn→Rf:\mathbb{R}^{n}\to\mathbb{R} is a twice continuously differentiable convex function. Given an initial point x0∈Rnx_0\in\mathbb{R}^{n}, our goal is to develop iterative methods achieving the global O(k−2)O(k^{-2}) convergence rate in function values. Throughout, we impose the following assumptions.

Assumption 1.1. The initial sublevel set L(x0):={x∈Rn:f(x)≤f(x0)}\mathcal{L}(x_0):=\{x\in\mathbb{R}^{n}: f(x)\leq f(x_0)\} is bounded.

Since ff is continuous, L(x0)\mathcal{L}(x_0) is compact, ensuring the existence of a global minimizer x∗∈Rnx^*\in\mathbb{R}^{n}. We denote f∗:=f(x∗)f^*:=f(x^*).

Assumption 1.2. There exists an L>0L > 0 such that

∥∇2f(x)−∇2f(y)∥≤L∥x−y∥∀x,y∈Rn.\lVert\nabla^2 f(x) - \nabla^2 f(y) \rVert\le L \lVert x-y \rVert\qquad\forall x,y \in\mathbb{R}^n.

These assumptions are standard in the analysis of second-order optimization methods; see, e.g., [22]. Throughout, ∥⋅∥\lVert\cdot\rVert denotes the Euclidean norm for vectors and the induced spectral norm for matrices. For convenience, we write

∇fk:=∇f(xk),∇2fk:=∇2f(xk).\nabla f_k := \nabla f(x_k), \qquad\nabla^2 f_k := \nabla^2 f(x_k).

Moreover, by compactness of L(x0)\mathcal{L}(x_0), the constants

H:=sup⁡x∈L(x0)∥∇2f(x)∥,D:=sup⁡x∈L(x0)∥x−x∗∥(4)H := \sup_{x \in\mathcal{L}(x_0)} \lVert\nabla^2 f(x) \rVert, \qquad D := \sup_{x \in\mathcal{L}(x_0)} \lVert x-x^* \rVert \tag*{(4)}

are finite.

Organization. In Section 2, we introduce the two-level gradient-regularized Newton method and establish its convergence rate. In Section 3, we extend the analysis to multiple coarse levels, establishing convergence guarantees under a fine-iteration frequency condition and, alternatively, without this condition using row-nested restriction operators introduced in Subsection 3.2. Numerical experiments comparing the proposed methods with full-space gradient-regularized Newton are presented in Section 4. Finally, Section 5 concludes the paper.

The two-level Newton method with gradient regularization

We consider the Newton method with gradient regularization that alternates between the fine and one coarse level. For the two-level algorithm we consider a single restriction operator that transfers the information from fine to coarse space, i.e., R:Rn→RdR : \mathbb{R}^n \to\mathbb{R}^d, where d<nd < n are the coarse space dimensions. Moreover, the prolongation operator is defined in a standard way, i.e., P:=R⊤P := R^\top. For the operators we take the standard assumptions (see for instance [11, 14]).

Assumption 2.1. Let R∈Rd×nR \in\mathbb{R}^{d \times n} be a full-row-rank restriction operator, with d≤nd \le n, and let P=R⊤P = R^\top be its corresponding prolongation operator. We define

ω:=∥R∥.\omega:= \lVert R \rVert.

Let σ∈(0,min⁡{1,ω})\sigma\in(0,\min\{1,\omega\}) and ε>0\varepsilon> 0. We define the sets of coarse and fine iterations

C:={k∈N:∥R∇fk∥≥σ∥∇fk∥, ∥R∇fk∥≥ε},F:=N∖C.\mathcal{C} := \{k \in\mathbb{N} : \lVert R\nabla f_k \rVert\ge\sigma\lVert\nabla f_k \rVert,\ \lVert R\nabla f_k \rVert\ge\varepsilon\}, \qquad\mathcal{F} := \mathbb{N}\setminus\mathcal{C}.

We can consider C\mathcal{C} as the set of effective coarse iterations and F\mathcal{F} the set of fine iterations. Thus, if m∈Cm \in\mathcal{C} then the algorithm will perform a coarse iteration otherwise a fine iteration. The two-level gradient-regularized Newton algorithm is presented in Algorithm 2.1.

The following result will be needed for the analysis of Algorithm 2.1; it has been proved in [27 Lemma 3.3] and [19 Lemma 3].

Lemma 2.1 ([19, 27]). Suppose that Assumptions 1.2 and 2.1 hold. Let xk∈Rnx_k \in\mathbb{R}^n and suppose that xk+1x_{k+1} is obtained by either the coarse or fine update of Algorithm 2.1, whenever the corresponding update is well-defined. Then

f(xk)−f(xk+1)≥∥R∇fk+1∥28ω3L ∥R∇fk∥/2for a coarse update,(5)f(x_k)-f(x_{k+1}) \ge\frac{\lVert R\nabla f_{k+1}\rVert^2}{8\sqrt{\omega^3 L}\,\lVert R\nabla f_k\rVert/\sqrt{2}} \qquad\text{for a coarse update,} \tag*{(5)}
f(xk)−f(xk+1)≥∥∇fk+1∥26L ∥∇fk∥/2for a fine update.(6)f(x_k)-f(x_{k+1}) \ge\frac{\lVert\nabla f_{k+1}\rVert^2}{6\sqrt{L}\,\lVert\nabla f_k\rVert/\sqrt{2}} \qquad\text{for a fine update.} \tag*{(6)}

Algorithm 2.1 Two-Level Regularized Newton (TLRN)

Inputs: x0∈Rnx_0 \in\mathbb{R}^n, R:Rn→RdR:\mathbb{R}^n \to\mathbb{R}^d, σ∈(0,min⁡{1,ω})\sigma\in(0,\min\{1,\omega\}), ε>0\varepsilon> 0.

Outputs: Sequence of iterates (x0,x1,x2,…)(x_0,x_1,x_2,\ldots).

for k=0,1,…k=0,1,\ldots do

&nbsp;&nbsp;&nbsp;&nbsp;if ∇fk=0\nabla f_k=0 then

&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stop

&nbsp;&nbsp;&nbsp;&nbsp;end if

&nbsp;&nbsp;&nbsp;&nbsp;Set

xk+1:={xk−P(R∇2fkP+ω3L∥R∇fk∥2Id)−1R∇fk,k∈C,xk−(∇2fk+L∥∇fk∥2In)−1∇fk,k∈F.x_{k+1}:= \begin{cases} x_k-P\left(R\nabla^2 f_kP+\sqrt{\frac{\omega^3L\|R\nabla f_k\|}{2}}I_d\right)^{-1}R\nabla f_k, & k\in\mathcal{C},\\ x_k-\left(\nabla^2 f_k+\sqrt{\frac{L\|\nabla f_k\|}{2}}I_n\right)^{-1}\nabla f_k, & k\in\mathcal{F}. \end{cases}

end for

Corollary 2.2. Suppose that Assumptions 1.2 and 2.1 hold and that the sequence (xk)k∈N(x_k)_{k\in\mathbb{N}} is generated by Algorithm 2.1. Then the sequence of function values (f(xk))k∈N(f(x_k))_{k\in\mathbb{N}} is non-increasing, i.e.,

f(xk+1)≤f(xk),k∈N.f(x_{k+1})\leq f(x_k),\qquad k\in\mathbb{N}.

The following stability estimates for the coarse and fine corrections were also established in [27] and [19], and hold for all coarse and fine updates, respectively:

∥R∇fk+1∥≤2∥R∇fk∥for a coarse update,(7)\|R\nabla f_{k+1}\|\leq2\|R\nabla f_k\|\qquad\text{for a coarse update,} \tag*{(7)}
∥∇fk+1∥≤2∥∇fk∥for a fine update.(8)\|\nabla f_{k+1}\|\leq2\|\nabla f_k\|\qquad\text{for a fine update.} \tag*{(8)}

Convergence analysis

When C=∅\mathcal{C}=\emptyset, then Algorithm 2.1 coincides with the gradient regularization of Newton’s method (see [9, 19]) which converges with the fast O(k−2)O(k^{-2}) rate. In what follows we show that this rate can be attained when the sequence (xk)k∈N(x_k)_{k\in\mathbb{N}} is always generated from the coarse space, i.e.,

xk+1=xk−P(R∇2fkP+ω3L∥R∇fk∥2Id)−1R∇fk.x_{k+1}=x_k-P\left(R\nabla^2 f_kP+\sqrt{\frac{\omega^3L\|R\nabla f_k\|}{2}}I_d\right)^{-1}R\nabla f_k.

For the purposes of this result, the condition ∥R∇fk∥≥ε\|R\nabla f_k\|\geq\varepsilon is therefore not imposed.

Proposition 2.3. Suppose that Assumptions 1.1 and 1.2 hold, and let (xk)k∈N(x_k)_{k\in\mathbb{N}} be generated by applying the coarse update of Algorithm 2.1 at every iteration. Assume that

∥R∇fk∥≥σ∥∇fk∥,k∈N.\|R\nabla f_k\|\geq\sigma\|\nabla f_k\|,\qquad k\in\mathbb{N}.

Then

f(xk)−f∗=O(k−2).f(x_k)-f^*=O(k^{-2}).

Moreover, the constant in the polynomial bound is proportional to σ−3\sigma^{-3}.

Proof. Fix k∈Nk\in\mathbb{N} and set Ik:={m∈{0,…,k−1}:∥R∇fm+1∥>14∥R∇fm∥}I^k:=\{m\in\{0,\ldots,k-1\}:\|R\nabla f_{m+1}\|>\frac{1}{4}\|R\nabla f_m\|\}. We distinguish two cases. Case I: ∣Ik∣≤k/2|I^k| \le k/2. By the definition of IkI^k and (7),

∥R∇fm+1∥≤{14∥R∇fm∥,m∉Ik,2∥R∇fm∥,m∈Ik.\lVert R\nabla f_{m+1}\rVert\le \begin{cases} \frac{1}{4}\lVert R\nabla f_m\rVert, & m \notin I^k,\\ 2\lVert R\nabla f_m\rVert, & m \in I^k. \end{cases}

Therefore,

∥R∇fk∥≤2∣Ik∣4k−∣Ik∣∥R∇f0∥≤2−k/2∥R∇f0∥.\lVert R\nabla f_k\rVert\le\frac{2^{|I^k|}}{4^{k-|I^k|}}\lVert R\nabla f_0\rVert\le2^{-k/2}\lVert R\nabla f_0\rVert.

Using convexity and the coarse-level condition,

f(xk)−f∗≤D∥∇fk∥≤Dσ∥R∇fk∥≤ωDσ2−k/2∥∇f0∥.f(x_k)-f^* \le D\lVert\nabla f_k\rVert\le\frac{D}{\sigma}\lVert R\nabla f_k\rVert\le\frac{\omega D}{\sigma}2^{-k/2}\lVert\nabla f_0\rVert.

Thus, in this case the function value gap decreases geometrically and, in particular, is O(k−2)O(k^{-2}).

Case II: ∣Ik∣>k/2|I^k| > k/2. Let τ:=∣Ik∣\tau:= |I^k|, enumerate Ik={k0,…,kτ−1}I^k=\{k_0,\ldots,k_{\tau-1}\}, k0<⋯<kτ−1<kk_0<\cdots<k_{\tau-1}<k, and set kτ:=kk_\tau:=k. By (2.1) and the definition of IkI^k, for ℓ=0,…,τ−1\ell=0,\ldots,\tau-1,

f(xkℓ)−f(xkℓ+1)≥∥R∇fkℓ+1∥28(ω3L∥R∇fkℓ∥/2)1/2≥∥R∇fkℓ∥3/2128(ω3L/2)1/2≥σ3/2∥∇fkℓ∥3/2128(ω3L/2)1/2.f(x_{k_\ell})-f(x_{k_{\ell+1}}) \ge\frac{\lVert R\nabla f_{k_{\ell+1}}\rVert^2}{8(\omega^3L\lVert R\nabla f_{k_\ell}\rVert/2)^{1/2}} \ge\frac{\lVert R\nabla f_{k_\ell}\rVert^{3/2}}{128(\omega^3L/2)^{1/2}} \ge\frac{\sigma^{3/2}\lVert\nabla f_{k_\ell}\rVert^{3/2}}{128(\omega^3L/2)^{1/2}}.

Since Ik⊆{0,…,k−1}I^k\subseteq\{0,\ldots,k-1\}, it follows that kℓ+1≤kℓ+1k_\ell+1\le k_{\ell+1} for ℓ=0,…,τ−1\ell=0,\ldots,\tau-1. Moreover, by (2.1), the sequence (f(xj))j∈N(f(x_j))_{j\in\mathbb{N}} is non-increasing. Hence,

f(xkℓ)−f(xkℓ+1)≥σ3/2128(ω3L/2)1/2∥∇fkℓ∥3/2.f(x_{k_\ell})-f(x_{k_{\ell+1}}) \ge\frac{\sigma^{3/2}}{128(\omega^3L/2)^{1/2}}\lVert\nabla f_{k_\ell}\rVert^{3/2}.

Combining this with convexity, i.e., f(xkℓ)−f∗≤⟨∇fkℓ,xkℓ−x∗⟩≤D∥∇fkℓ∥f(x_{k_\ell})-f^*\le\langle\nabla f_{k_\ell},x_{k_\ell}-x^*\rangle\le D\lVert\nabla f_{k_\ell}\rVert, we obtain

f(xkℓ+1)−f∗≤f(xkℓ)−f∗−CC(f(xkℓ)−f∗)3/2,f(x_{k_{\ell+1}})-f^* \le f(x_{k_\ell})-f^*-C_C(f(x_{k_\ell})-f^*)^{3/2},

where

CC:=σ3/2128(D3ω3L/2)1/2.C_C:=\frac{\sigma^{3/2}}{128(D^3\omega^3L/2)^{1/2}}.

Hence, Proposition A.1 yields

f(xk)−f∗≤1CC2(1+τ/2)2≤1CC2(1+k/4)2=O(1σ3k2).f(x_k)-f^* \le\frac{1}{C_C^2(1+\tau/2)^2}\le\frac{1}{C_C^2(1+k/4)^2}=O\left(\frac{1}{\sigma^3 k^2}\right).

Combining the two cases proves the result.

Proposition 2.3 analyzes the limiting case in which only coarse corrections are performed and shows that the coarse-only iteration retains the O(k−2)O(k^{-2}) rate of the full-space regularized Newton method. Its proof adapts the strategy of [19 Theorem 1] to the reduced-gradient setting. A key feature of this analysis is that every iteration controls the same quantity, namely ∥R∇fk∥\lVert R\nabla f_k\rVert, so the corresponding estimates can be propagated consistently along the sequence.

The situation is fundamentally different for Algorithm 2.1. Coarse iterations naturally control ∥R∇fk∥\lVert R\nabla f_k\rVert, whereas fine iterations control ∥∇fk∥\lVert\nabla f_k\rVert, and neither of these quantities is necessarily contractive when the algorithm switches to the other level. Thus, the fact that both the coarse-only and fine-only schemes achieve an O(k−2)O(k^{-2}) rate does not by itself imply convergence, or the same rate, for an arbitrary mixture of the two iteration types. The main difficulty is therefore not the behavior within either level, but the transitions between them.

The following lemma provides the cross-level stability estimate needed to bridge this mismatch: although a coarse correction need not decrease the full gradient norm, it can increase it by at most a uniform factor.

Lemma 2.4. Suppose that Assumptions 1.1, 1.2, and 2.1 hold and that (xk)k∈N(x_k)_{k\in\mathbb{N}} is generated by Algorithm 2.1. Let

MC:=1+H2ωLε.M_{\mathcal{C}} := 1 + \frac{H\sqrt{2\omega}}{\sqrt{L\varepsilon}}.

where HH is defined in (1.4). Then, for any k∈Ck \in\mathcal{C} we have

∥∇fk+1∥≤MC∥∇fk∥\lVert\nabla f_{k+1}\rVert\le M_{\mathcal{C}}\lVert\nabla f_k\rVert

Proof. Denote

αk:=ω3L∥R∇fk∥2.\alpha_k := \sqrt{\frac{\omega^3 L\lVert R\nabla f_k\rVert}{2}}.

Next, we have

∇f(xk+1)−∇f(xk)=∫01∇2f(xk+t(xk+1−xk))(xk+1−xk) dt.\nabla f(x_{k+1})-\nabla f(x_k)=\int_0^1 \nabla^2 f\bigl(x_k+t(x_{k+1}-x_k)\bigr)(x_{k+1}-x_k)\,\mathrm{d}t.

By Corollary 2.2, xk,xk+1∈L(x0)x_k,x_{k+1}\in\mathcal{L}(x_0). Since ff is convex, L(x0)\mathcal{L}(x_0) is convex, and hence xk+t(xk+1−xk)∈L(x0)x_k+t(x_{k+1}-x_k)\in\mathcal{L}(x_0) for every t∈[0,1]t\in[0,1]. Therefore,

∥∇f(xk+1)−∇f(xk)∥≤H∥xk+1−xk∥.(9)\lVert\nabla f(x_{k+1})-\nabla f(x_k)\rVert\le H\lVert x_{k+1}-x_k\rVert. \tag*{(9)}

Then, by using the definitions of ω\omega and αk\alpha_k as well as k∈Ck\in\mathcal{C} and the symmetric positive semi-definiteness of R∇2fkPR\nabla^2 f_kP, we obtain

∥∇fk+1∥≤∥∇fk+1−∇fk∥+∥∇fk∥≤H∥P(R∇2fkP+ω3L∥R∇fk∥2Id)−1R∇fk∥+∥∇fk∥≤Hω∥(R∇2fkP+ω3L∥R∇fk∥2Id)−1R∇fk∥+∥∇fk∥≤Hω∥R∇fk∥αk+∥∇fk∥≤Hω2ω3Lε∥R∇fk∥+∥∇fk∥≤(1+H2ωLε)∥∇fk∥.\begin{aligned} \lVert\nabla f_{k+1}\rVert &\le\lVert\nabla f_{k+1}-\nabla f_k\rVert+\lVert\nabla f_k\rVert\\ &\le H\left\|P\left(R\nabla^2 f_kP+\sqrt{\frac{\omega^3L\lVert R\nabla f_k\rVert}{2}}I_d\right)^{-1}R\nabla f_k\right\|+\lVert\nabla f_k\rVert\\ &\le H\omega\left\|\left(R\nabla^2 f_kP+\sqrt{\frac{\omega^3L\lVert R\nabla f_k\rVert}{2}}I_d\right)^{-1}R\nabla f_k\right\|+\lVert\nabla f_k\rVert\\ &\le H\omega\frac{\lVert R\nabla f_k\rVert}{\alpha_k}+\lVert\nabla f_k\rVert\\ &\le H\omega\frac{\sqrt{2}}{\sqrt{\omega^3L\varepsilon}}\lVert R\nabla f_k\rVert+\lVert\nabla f_k\rVert\\ &\le\left(1+\frac{H\sqrt{2\omega}}{\sqrt{L\varepsilon}}\right)\lVert\nabla f_k\rVert. \end{aligned}

Lemma 2.4 shows that a coarse correction is stable with respect to the full gradient, in the sense that the gradient norm can increase by at most a uniformly bounded factor. Together with the level-specific stability estimates (2.1) and (6), this bound will allow us to construct a level-dependent weighted gradient measure that controls transitions between the two levels.

Theorem 2.5. Let ff be convex and suppose that Assumptions 1.1, 1.2, and 2.1 hold. Then the sequence generated by Algorithm 2.1 satisfies

f(xk)−f∗=O(1k2).f(x_k)-f^*=\mathcal{O}\left(\frac{1}{k^2}\right).

Proof. To compare the reduced and full gradient norms across changes of level, we introduce a level-dependent weighted gradient measure. The weights are chosen so that all four possible coarse/fine transitions admit uniform contraction or stability bounds. Choose

a>0,ρ∈(0,σωMC),t∈(ρω,σMC),a>0,\qquad\rho\in\left(0,\frac{\sigma}{\omega M_C}\right),\qquad t\in\left(\rho\omega,\frac{\sigma}{M_C}\right),

and set b:=atb:=at. Since ∥R∥∥∇fk∥≥∥R∇fk∥≥σ∥∇fk∥\lVert R\rVert\lVert\nabla f_k\rVert\ge\lVert R\nabla f_k\rVert\ge\sigma\lVert\nabla f_k\rVert implies ω≥σ\omega\ge\sigma, we get

q:=max⁡{ρ,tMCσ,ωρt}<1.q:=\max\left\{\rho,\frac{tM_C}{\sigma},\frac{\omega\rho}{t}\right\}<1.

Moreover, define the scalar

B:=max⁡{2,2ωt,tMCσ},B:=\max\left\{2,\frac{2\omega}{t},\frac{tM_C}{\sigma}\right\},

and the sets

Ck:=C∩{0,…,k−1},Fk:=F∩{0,…,k−1},\mathcal{C}^k:=\mathcal{C}\cap\{0,\ldots,k-1\},\qquad \mathcal{F}^k:=\mathcal{F}\cap\{0,\ldots,k-1\},
TCk(ρ):={m∈C∩{0,…,k−1}:∥R∇fm+1∥>ρ∥R∇fm∥},\mathcal{T}_{\mathcal{C}}^k(\rho):=\{m\in\mathcal{C}\cap\{0,\ldots,k-1\}:\lVert R\nabla f_{m+1}\rVert>\rho\lVert R\nabla f_m\rVert\},
TFk(ρ):={m∈F∩{0,…,k−1}:∥∇fm+1∥>ρ∥∇fm∥}.\mathcal{T}_{\mathcal{F}}^k(\rho):=\{m\in\mathcal{F}\cap\{0,\ldots,k-1\}:\lVert\nabla f_{m+1}\rVert>\rho\lVert\nabla f_m\rVert\}.

We set

Tk(ρ):=TCk(ρ)∪TFk(ρ).\mathcal{T}^k(\rho):=\mathcal{T}_{\mathcal{C}}^k(\rho)\cup\mathcal{T}_{\mathcal{F}}^k(\rho).

Now, choose θ∈(0,−ln⁡qln⁡B−ln⁡q)\theta\in\left(0,\frac{-\ln q}{\ln B-\ln q}\right) and fix a k∈Nk\in\mathbb{N}. We distinguish two cases.

Case I: ∣Tk(ρ)∣≤θk\lvert\mathcal{T}^k(\rho)\rvert\le\theta k. Define

Vk:={a∥R∇fk∥,k∈C,b∥∇fk∥,k∈F.V_k:= \begin{cases} a\lVert R\nabla f_k\rVert,& k\in\mathcal{C},\\ b\lVert\nabla f_k\rVert,& k\in\mathcal{F}. \end{cases}

For m∈(Tk(ρ))c:={0,…,k−1}∖Tk(ρ)=(Ck∖TCk(ρ))∪(Fk∖TFk(ρ))m\in\bigl(\mathcal{T}^k(\rho)\bigr)^c:=\{0,\ldots,k-1\}\setminus\mathcal{T}^k(\rho)=(\mathcal{C}^k\setminus\mathcal{T}_{\mathcal{C}}^k(\rho))\cup(\mathcal{F}^k\setminus\mathcal{T}_{\mathcal{F}}^k(\rho)), we show that Vm+1≤qVmV_{m+1}\le qV_m. Let m∈(Tk(ρ))cm\in\bigl(\mathcal{T}^k(\rho)\bigr)^c. Then, for mm and m+1m+1 we have four possibilities:

(a) m∈Ck∖TCk(ρ)m\in\mathcal{C}^k\setminus\mathcal{T}_{\mathcal{C}}^k(\rho), m+1∈Cm+1\in\mathcal{C}. Then,

Vm+1=m+1∈Ca∥R∇fm+1∥≤m∈C∖TCk(ρ)aρ∥R∇fm∥=m∈CρVm.V_{m+1}\underset{m+1\in\mathcal{C}}{=}a\lVert R\nabla f_{m+1}\rVert \underset{m\in\mathcal{C}\setminus\mathcal{T}_{\mathcal{C}}^k(\rho)}{\le}a\rho\lVert R\nabla f_m\rVert \underset{m\in\mathcal{C}}{=}\rho V_m.

(b) m∈Ck∖TCk(ρ)m\in\mathcal{C}^k\setminus\mathcal{T}_{\mathcal{C}}^k(\rho), m+1∈Fm+1\in\mathcal{F}. Then, with similar arguments we obtain

Vm+1=m+1∈Fb∥∇fm+1∥≤Lem. 2.4bMC∥∇fm∥≤m∈CbMCσ∥R∇fm∥≤m∈CtMCσVm.V_{m+1}\underset{m+1\in\mathcal{F}}{=}b\lVert\nabla f_{m+1}\rVert \underset{\text{Lem. 2.4}}{\le}bM_C\lVert\nabla f_m\rVert \underset{m\in\mathcal{C}}{\le}\frac{bM_C}{\sigma}\lVert R\nabla f_m\rVert \underset{m\in\mathcal{C}}{\le}\frac{tM_C}{\sigma}V_m.

(c) m∈Fk∖IFk(ρ)m \in\mathcal{F}^{k} \setminus\mathcal{I}_{\mathcal{F}}^{k}(\rho), m+1∈Fm+1 \in\mathcal{F}. Then,

Vm+1=m+1∈Fb∥∇fm+1∥≤m∈F∖IFk(ρ)bρ∥∇fm∥=m∈FρVm.V_{m+1} \overset{m+1\in\mathcal{F}}{=} b\lVert\nabla f_{m+1}\rVert\overset{m\in\mathcal{F}\setminus\mathcal{I}_{\mathcal{F}}^{k}(\rho)}{\leq} b\rho\lVert\nabla f_m\rVert\overset{m\in\mathcal{F}}{=} \rho V_m.

(d) m∈Fk∖IFk(ρ)m \in\mathcal{F}^{k} \setminus\mathcal{I}_{\mathcal{F}}^{k}(\rho), m+1∈Cm+1 \in\mathcal{C}. Then,

Vm+1=m+1∈Ca∥R∇fm+1∥≤aω∥∇fm+1∥≤m∈F∖IFk(ρ)aωρ∥∇fm∥=m∈FωρtVm.V_{m+1} \overset{m+1\in\mathcal{C}}{=} a\lVert R\nabla f_{m+1}\rVert\leq a\omega\lVert\nabla f_{m+1}\rVert\overset{m\in\mathcal{F}\setminus\mathcal{I}_{\mathcal{F}}^{k}(\rho)}{\leq} a\omega\rho\lVert\nabla f_m\rVert\overset{m\in\mathcal{F}}{=} \frac{\omega\rho}{t}V_m.

Hence,

Vm+1≤qVmfor any m∈Ik(ρ)c.(10)V_{m+1} \leq qV_m \quad\text{for any } m\in\mathcal{I}^{k}(\rho)^{c}. \tag*{(10)}

Now let m∈Ik(ρ)m \in\mathcal{I}^{k}(\rho). We again consider four cases as above:

(a) m∈ICk(ρ)m \in\mathcal{I}_{\mathcal{C}}^{k}(\rho), m+1∈Cm+1 \in\mathcal{C}. Then,

Vm+1=a∥R∇fm+1∥≤(2.3)2Vm.V_{m+1}=a\lVert R\nabla f_{m+1}\rVert\overset{(2.3)}{\leq} 2V_m.

(b) m∈ICk(ρ)m \in\mathcal{I}_{\mathcal{C}}^{k}(\rho), m+1∈Fm+1 \in\mathcal{F}. Then,

Vm+1≤tMCσVm.V_{m+1}\leq\frac{tM_{\mathcal{C}}}{\sigma}V_m.

(c) m∈IFk(ρ)m \in\mathcal{I}_{\mathcal{F}}^{k}(\rho), m+1∈Fm+1 \in\mathcal{F}. Then,

Vm+1=b∥∇fm+1∥≤(2.4)2Vm.V_{m+1}=b\lVert\nabla f_{m+1}\rVert\overset{(2.4)}{\leq} 2V_m.

(d) m∈IFk(ρ)m \in\mathcal{I}_{\mathcal{F}}^{k}(\rho), m+1∈Cm+1 \in\mathcal{C}. Then,

Vm+1≤2ωtVm.V_{m+1}\leq\frac{2\omega}{t}V_m.

As a result,

Vm+1≤BVmfor any m∈Ik(ρ).(11)V_{m+1}\leq BV_m \quad\text{for any } m\in\mathcal{I}^{k}(\rho). \tag*{(11)}

Let η:=q1−θBθ\eta:= q^{1-\theta}B^{\theta}. Thus, we have

ln⁡(q1−θBθ)=(1−θ)ln⁡q+θln⁡B=ln⁡q+θ(ln⁡B−ln⁡q),\ln\left(q^{1-\theta}B^{\theta}\right)=(1-\theta)\ln q+\theta\ln B=\ln q+\theta(\ln B-\ln q),

and hence, by the definition of θ\theta, η<1\eta<1. Combining now (2.6) and (2.7) we obtain

Vk≤qk−∣Ik(ρ)∣B∣Ik(ρ)∣V0≤ηkV0.(12)V_k\leq q^{k-\lvert\mathcal{I}^{k}(\rho)\rvert}B^{\lvert\mathcal{I}^{k}(\rho)\rvert}V_0\leq\eta^kV_0. \tag*{(12)}

Furthermore, for any k∈Nk\in\mathbb{N}, we have that

∥∇fk∥≤AVk,A:=max⁡{1aσ,1b}.(13)\lVert\nabla f_k\rVert\leq AV_k,\qquad A:=\max\left\{\frac{1}{a\sigma},\frac{1}{b}\right\}. \tag*{(13)}

Then, by convexity and Assumption 1.1, we obtain

f(xk)−f∗≤D∥∇fk∥≤(2.8),(2.9)ηkADV0=O(1k2),(14)f(x_k)-f^*\leq D\lVert\nabla f_k\rVert\overset{(2.8),(2.9)}{\leq} \eta^kADV_0=O\left(\frac{1}{k^2}\right), \tag*{(14)}

and thus the desired rate of convergence is established when ∣Ik(ρ)∣≤θk\lvert\mathcal{I}^{k}(\rho)\rvert\le\theta k.

Case II: ∣Ik(ρ)∣>θk\lvert\mathcal{I}^{k}(\rho)\rvert> \theta k. Let τ:=∣Ik(ρ)∣\tau:= \lvert\mathcal{I}^{k}(\rho)\rvert and enumerate Ik(ρ)={k0,…,kτ−1}\mathcal{I}^{k}(\rho) = \{k_0,\ldots,k_{\tau-1}\}, with k0<k1<⋯<kτ−1<kk_0 < k_1 < \cdots< k_{\tau-1} < k, kτ:=kk_\tau:= k. Let ℓ∈{0,…,τ−1}\ell\in\{0,\ldots,\tau-1\}. Thus, kℓ∈Ik(ρ)k_\ell\in\mathcal{I}^{k}(\rho). If kℓ∈ICk(ρ)k_\ell\in\mathcal{I}^{k}_{C}(\rho), then

f(xkℓ)−f(xkℓ+1)≥∥R∇fkℓ+1∥28(ω3L/2∥R∇fkℓ∥)1/2≥ρ2∥R∇fkℓ∥3/28(ω3L/2)1/2≥(σω)3/2ρ2∥∇fkℓ∥3/28L/2.(15)\begin{aligned} f(x_{k_\ell}) - f(x_{k_\ell+1}) &\ge\frac{\lVert R\nabla f_{k_\ell+1}\rVert^2}{8(\omega^3L/2\lVert R\nabla f_{k_\ell}\rVert)^{1/2}} \\ &\ge\frac{\rho^2\lVert R\nabla f_{k_\ell}\rVert^{3/2}}{8(\omega^3L/2)^{1/2}} \\ &\ge\left(\frac{\sigma}{\omega}\right)^{3/2}\frac{\rho^2\lVert\nabla f_{k_\ell}\rVert^{3/2}}{8\sqrt{L/2}}. \tag*{(15)} \end{aligned}

Using similar arguments, if kℓ∈IFk(ρ)k_\ell\in\mathcal{I}^{k}_{F}(\rho), then

f(xkℓ)−f(xkℓ+1)≥ρ2∥∇fkℓ∥3/26L/2,f(x_{k_\ell}) - f(x_{k_\ell+1}) \ge\frac{\rho^2\lVert\nabla f_{k_\ell}\rVert^{3/2}}{6\sqrt{L/2}},

and thus, since σ≤ω\sigma\le\omega, we get

f(xkℓ)−f(xkℓ+1)≥min⁡{(σω)3/2ρ28L/2,ρ26L/2}∥∇fkℓ∥3/2=(σω)3/2ρ2∥∇fkℓ∥3/28L/2.\begin{aligned} f(x_{k_\ell}) - f(x_{k_\ell+1}) &\ge\min\left\{\left(\frac{\sigma}{\omega}\right)^{3/2}\frac{\rho^2}{8\sqrt{L/2}},\frac{\rho^2}{6\sqrt{L/2}}\right\}\lVert\nabla f_{k_\ell}\rVert^{3/2} \\ &= \left(\frac{\sigma}{\omega}\right)^{3/2}\frac{\rho^2\lVert\nabla f_{k_\ell}\rVert^{3/2}}{8\sqrt{L/2}}. \end{aligned}

for all ℓ∈{0,…,τ−1}\ell\in\{0,\ldots,\tau-1\}. Since Ik(ρ)⊂{0,…,k−1}\mathcal{I}^{k}(\rho) \subset\{0,\ldots,k-1\}, it follows that kℓ+1≤kℓ+1k_\ell+1 \le k_{\ell+1} for ℓ=0,…,τ−1\ell= 0,\ldots,\tau-1. Following the same argument as in Case II of Proposition 2.3, monotonicity of the function values and convexity yield

Δℓ+1≤Δℓ−CΔℓ3/2,Δℓ:=f(xkℓ)−f∗,\Delta_{\ell+1} \le\Delta_\ell- C\Delta_\ell^{3/2}, \qquad\Delta_\ell:= f(x_{k_\ell}) - f^*,

where

C:=2ρ28L(σωD)3/2.C := \frac{\sqrt{2}\rho^2}{8\sqrt{L}}\left(\frac{\sigma}{\omega D}\right)^{3/2}.

Hence, Proposition A.1 and τ>θk\tau> \theta k give

f(xk)−f∗=Δτ≤1C2(1+τ/2)2≤1C2(1+θk/2)2=O(k−2),f(x_k) - f^* = \Delta_\tau\le\frac{1}{C^2(1+\tau/2)^2} \le\frac{1}{C^2(1+\theta k/2)^2} = O(k^{-2}),

which completes the proof of Case II. Combining now the results of the two cases we have

f(xk)−f∗≤max⁡{ADV0ηk,1C2(1+θk/2)2}=O(k−2),f(x_k) - f^* \le\max\left\{ADV_0\eta^k,\frac{1}{C^2(1+\theta k/2)^2}\right\} = O(k^{-2}),

as required.

Theorem 2.5 shows that the use of coarse corrections does not deteriorate the global convergence rate of the regularized Newton method. In particular, Algorithm 2.1 achieves the O(k−2)O(k^{-2}) rate in function values while allowing arbitrary switching between coarse and fine iterations according to the level-selection criterion. A key feature of the analysis is that coarse and fine iterations naturally control different quantities, namely ∥R∇fk∥\lVert R\nabla f_k\rVert and ∥∇fk∥\lVert\nabla f_k\rVert, respectively. The proof resolves this mismatch through a level-dependent weighted gradient measure that provides uniform control across all possible coarse/fine transitions: it contracts on iterations outside Tk(ρ)T^k(\rho), while its growth on the remaining iterations is uniformly bounded. Consequently, the analysis does not require the full gradient norm to decrease at every coarse iteration; uniform stability of the coarse corrections is sufficient. This provides a mechanism for preserving convergence rates in multilevel schemes even when different iteration types control different measures of stationarity.

The multilevel Newton method with gradient regularization

In this section we consider the gradient regularization of Newton’s method that alternates between ℓ\ell coarse levels (plus the fine level) when generating the updates. In particular, we consider ℓ\ell restriction operators as in [11], but unlike their recursive framework, our operators map directly between each coarse level and the full space, allowing coarse corrections to be transferred directly to the fine level. More precisely, for each i∈J:={1,…,ℓ}i \in\mathcal{J} := \{1,\ldots,\ell\}, let Ri:Rn→RniR_i:\mathbb{R}^{n} \to\mathbb{R}^{n_i} be a restriction operator, where n1<⋯<nℓ<nn_1 < \cdots< n_\ell< n. Further, Pi:=RiTP_i := R_i^{\mathsf{T}} is the prolongation operator at level i∈Ji \in\mathcal{J}. We will see that this nonrecursive formulation simplifies both the algorithm and its convergence analysis while retaining the same O(ni2+ni3)O(n_i^2+n_i^3) computational cost at the iith coarse level.

Accordingly, Assumption 2.1 is now replaced by the following assumption.

Assumption 3.1. For each i∈Ji \in\mathcal{J}, let Ri∈Rni×nR_i \in\mathbb{R}^{n_i\times n} be a full-row-rank restriction operator, with ni≤nn_i \le n, and let Pi=RiTP_i=R_i^{\mathsf{T}} be its corresponding prolongation operator. We define

ωi:=∥Ri∥,ζ:=max⁡i∈Jωi.\omega_i := \lVert R_i\rVert,\qquad\zeta:= \max_{i\in\mathcal{J}}\omega_i.

Let σ∈(0,min⁡{1,min⁡i∈Jωi})\sigma\in(0,\min\{1,\min_{i\in\mathcal{J}}\omega_i\}) and ε>0\varepsilon>0. For each i∈Ji\in\mathcal{J}, the sets of coarse and fine iterations are now defined as follows. First define the eligible sets

Ei:={k∈N:∥Ri∇fk∥≥σ∥∇fk∥, ∥Ri∇fk∥≥ε}.\mathcal{E}_i := \{k\in\mathbb{N}:\lVert R_i\nabla f_k\rVert\ge\sigma\lVert\nabla f_k\rVert,\ \lVert R_i\nabla f_k\rVert\ge\varepsilon\}.

The set Ei\mathcal{E}_i contains the iterations for which level ii is eligible. For the multilevel method to become efficient, we need to select the lowest-dimensional eligible level

Ci:=Ei∖⋃j<iEj,i∈J.\mathcal{C}_i := \mathcal{E}_i\setminus\bigcup_{j<i}\mathcal{E}_j,\qquad i\in\mathcal{J}.

Then the sets Ci\mathcal{C}_i are pairwise disjoint and, whenever {i∈J:k∈Ei}≠∅\{i\in\mathcal{J}:k\in\mathcal{E}_i\}\ne\varnothing,

k∈Ci⟺i=i∗(k):=min⁡{j∈J:k∈Ej}.k\in\mathcal{C}_i\quad\Longleftrightarrow\quad i=i^*(k):=\min\{j\in\mathcal{J}:k\in\mathcal{E}_j\}.

Moreover, we set

F(ℓ):=N∖C(ℓ),C(ℓ):=⋃i∈JCi.\mathcal{F}^{(\ell)}:=\mathbb{N}\setminus\mathcal{C}^{(\ell)},\qquad\mathcal{C}^{(\ell)}:=\bigcup_{i\in\mathcal{J}}\mathcal{C}_i.

The multilevel gradient-regularized Newton method is presented in Algorithm 3.1.

The next lemma shows that Algorithm 3.1 generates a non-increasing sequence of function values. It also shows that it guarantees the reduced-gradient stability of a coarse correction step. These results arise by [27].

Lemma 3.1. Suppose that Assumptions 1.2 and 3.1 hold, and let (xk)k∈N(x_k)_{k\in\mathbb{N}} be generated by Algorithm 3.1. Then, for any k∈Cik\in\mathcal{C}_i, i∈Ji\in\mathcal{J},

f(xk)−f(xk+1)≥∥Ri∇fk+1∥28ωi3L∥Ri∇fk∥2.(16)f(x_k)-f(x_{k+1})\ge\frac{\lVert R_i\nabla f_{k+1}\rVert^2}{8\omega_i^3L\lVert R_i\nabla f_k\rVert^2}. \tag*{(16)}
∥Ri∇fk+1∥≤2∥Ri∇fk∥.(17)\lVert R_i\nabla f_{k+1}\rVert\le2\lVert R_i\nabla f_k\rVert. \tag*{(17)}

Algorithm 3.1 MultiLevel Regularized Newton (MLRN)

Inputs: x0∈Rnx_0 \in\mathbb{R}^n, ℓ∈N\ell\in\mathbb{N}, Ri:Rn→RniR_i:\mathbb{R}^n \to\mathbb{R}^{n_i} for i∈Ji \in\mathcal{J}, σ∈(0,min⁡{1,min⁡i∈Jωi})\sigma\in(0,\min\{1,\min_{i\in\mathcal{J}}\omega_i\}), ε>0\varepsilon> 0.

Outputs: Sequence of iterates (x0,x1,x2,…)(x_0,x_1,x_2,\ldots).

for k=0,1,…k=0,1,\ldots do

if ∇fk=0\nabla f_k=0 then

stop

end if

Set

xk+1:={xk−Pi(Ri∇2fkPi+ωi3L∥Ri∇fk∥2 Ini)−1Ri∇fk,k∈Ci,i∈J,xk−(∇2fk+L∥∇fk∥2 In)−1∇fk,k∈F(ℓ).x_{k+1}:= \begin{cases} x_k-P_i\left(R_i\nabla^2 f_kP_i+\sqrt{\frac{\omega_i^3L\lVert R_i\nabla f_k\rVert}{2}}\,I_{n_i}\right)^{-1}R_i\nabla f_k, & k\in C_i,i\in\mathcal{J},\\ x_k-\left(\nabla^2 f_k+\sqrt{\frac{L\lVert\nabla f_k\rVert}{2}}\,I_n\right)^{-1}\nabla f_k, & k\in\mathcal{F}^{(\ell)}. \end{cases}

end for

Proof. The proof is outlined in Subsection A.1.

Lemma 3.1 guarantees that f(xk+1)≤f(xk)f(x_{k+1})\leq f(x_k), k∈Cik\in C_i, and by (2.4), (f(xk))k∈N(f(x_k))_{k\in\mathbb{N}} is non-increasing. In particular, this means that the multilevel iterates stay in L(x0)\mathcal{L}(x_0). Finally, in Lemma A.2 we show that Algorithm 3.1 performs only finitely many coarse iterations.

Conditional rate of convergence

Let ρ∈(0,1)\rho\in(0,1). Similar to the analysis of the two-level method, we will need the following definitions,

Cik:=Ci∩{0,…,k−1},C(ℓ),k:=⋃i∈JCik,C_i^k:=C_i\cap\{0,\ldots,k-1\},\qquad C^{(\ell),k}:=\bigcup_{i\in\mathcal{J}}C_i^k,
F(ℓ),k:=F(ℓ)∩{0,…,k−1},\mathcal{F}^{(\ell),k}:=\mathcal{F}^{(\ell)}\cap\{0,\ldots,k-1\},
ICik(ρ):={m∈Cik:∥Ri∇fm+1∥>ρ∥Ri∇fm∥},\mathcal{I}_{C_i}^k(\rho):=\{m\in C_i^k:\lVert R_i\nabla f_{m+1}\rVert>\rho\lVert R_i\nabla f_m\rVert\},
IF(ℓ)k(ρ):={m∈F(ℓ),k:∥∇fm+1∥>ρ∥∇fm∥},\mathcal{I}_{\mathcal{F}^{(\ell)}}^k(\rho):=\{m\in\mathcal{F}^{(\ell),k}:\lVert\nabla f_{m+1}\rVert>\rho\lVert\nabla f_m\rVert\},

where i∈Ji\in\mathcal{J}. We further set

Iℓk(ρ):=(⋃i∈JICik(ρ))∪IF(ℓ)k(ρ).\mathcal{I}_{\ell}^k(\rho):=\left(\bigcup_{i\in\mathcal{J}}\mathcal{I}_{C_i}^k(\rho)\right)\cup\mathcal{I}_{\mathcal{F}^{(\ell)}}^k(\rho).

Hence, the disjointness of the sets CiC_i, i∈Ji\in\mathcal{J}, and F(ℓ)\mathcal{F}^{(\ell)} gives

∣Iℓk(ρ)∣=∑i=1ℓ∣ICik(ρ)∣+∣IF(ℓ)k(ρ)∣.\left|\mathcal{I}_{\ell}^k(\rho)\right|=\sum_{i=1}^{\ell}\left|\mathcal{I}_{C_i}^k(\rho)\right|+\left|\mathcal{I}_{\mathcal{F}^{(\ell)}}^k(\rho)\right|.

The following lemma shows the O(k−2)\mathcal{O}(k^{-2}) rate of Algorithm 3.1 when ∣Iℓk(ρ)∣\left|\mathcal{I}_{\ell}^k(\rho)\right| is sufficiently large.

Lemma 3.2. Suppose that Assumptions 1.1, 1.2, and 3.1 hold. Let k∈Nk\in\mathbb{N} and θ,ρ∈(0,1)\theta,\rho\in(0,1). If ∣Tℓk(ρ)∣>θk|\mathcal{T}_{\ell}^{k}(\rho)|>\theta k, then the sequence generated by Algorithm 3.1 satisfies

f(xk)−f∗≤1Cℓ2(1+θk2)2,Cℓ:=ρ4σ332Lζ3D3.f(x_k)-f^* \le\frac{1}{C_{\ell}^{2}\left(1+\frac{\theta k}{2}\right)^2}, \qquad C_{\ell}:=\sqrt{\frac{\rho^4\sigma^3}{32L\zeta^3\mathcal{D}^3}}.

Proof. The proof is given in Subsection A.2. □

Further, the coarse correction is also stable with respect to the full gradient. In particular, by Lemma 2.4 there exist MCi∈(0,∞)M_{\mathcal{C}_i}\in(0,\infty), i∈Ji\in\mathcal{J}, such that

∥∇fk+1∥≤MCi∥∇fk∥,k∈Ci.\|\nabla f_{k+1}\|\le M_{\mathcal{C}_i}\|\nabla f_k\|,\qquad k\in\mathcal{C}_i.

In what follows we show that Algorithm 3.1 converges with O(k−2)O(k^{-2}) when it performs a sufficiently large numbersufficiently of fine steps.

Theorem 3.3. Suppose that Assumptions 1.1, 1.2, and 3.1 hold. Let

MC(ℓ):=max⁡{1,max⁡i∈JMCi},h:=log⁡2MC(ℓ).M_{\mathcal{C}(\ell)}:=\max\left\{1,\max_{i\in\mathcal{J}}M_{\mathcal{C}_i}\right\},\qquad h:=\log_2 M_{\mathcal{C}(\ell)}.

Let θ∈(0,2/3)\theta\in(0,2/3) and choose

a∈(h+3θh+2,1).a\in\left(\frac{h+3\theta}{h+2},1\right).

Suppose also that, for all sufficiently large kk,

∣F(ℓ),k∣≥ak.|\mathcal{F}^{(\ell),k}|\ge ak.

Then the sequence generated by Algorithm 3.1 satisfies

f(xk)−f∗=O(k−2).f(x_k)-f^*=O(k^{-2}).

Proof. Fix a sufficiently large k∈Nk\in\mathbb{N} such that ∣F(ℓ),k∣≥ak|\mathcal{F}^{(\ell),k}|\ge ak, and set Tℓk:=Tℓk(1/4)\mathcal{T}_{\ell}^{k}:=\mathcal{T}_{\ell}^{k}(1/4), TF(ℓ)k:=Tℓk(1/4)\mathcal{T}_{\mathcal{F}(\ell)}^{k}:=\mathcal{T}_{\ell}^{k}(1/4). If ∣Tℓk∣>θk|\mathcal{T}_{\ell}^{k}|>\theta k, then Lemma 3.2 yields

f(xk)−f∗=O(k−2).f(x_k)-f^*=O(k^{-2}).

It remains to consider the case ∣Tℓk∣≤θk|\mathcal{T}_{\ell}^{k}|\le\theta k. For every m∈{0,…,k−1}m\in\{0,\ldots,k-1\}, exactly one of the following possibilities occurs:

(a) If m∈C(ℓ),km\in\mathcal{C}^{(\ell),k}, then ∥∇fm+1∥≤MC(ℓ)∥∇fm∥\|\nabla f_{m+1}\|\le M_{\mathcal{C}(\ell)}\|\nabla f_m\|.

(b) If m∈TF(ℓ)km\in\mathcal{T}_{\mathcal{F}(\ell)}^{k}, then ∥∇fm+1∥≤12∥∇fm∥\|\nabla f_{m+1}\|\le\frac{1}{2}\|\nabla f_m\|.

(c) If m∈F(ℓ),k∖TF(ℓ)km\in\mathcal{F}^{(\ell),k}\setminus\mathcal{T}_{\mathcal{F}(\ell)}^{k}, then ∥∇fm+1∥≤14∥∇fm∥\|\nabla f_{m+1}\|\le\frac{1}{4}\|\nabla f_m\|.

Since ∣C(ℓ),k∣+∣F(ℓ),k∣=k|\mathcal{C}^{(\ell),k}|+|\mathcal{F}^{(\ell),k}|=k, iterating these bounds gives

∥∇fk∥≤MC(ℓ)k−∣F(ℓ),k∣2∣F(ℓ),k∣(14)∣F(ℓ),k∣−∣TF(ℓ)k∣∥∇f0∥=MC(ℓ)k−∣F(ℓ),k∣2−2∣F(ℓ),k∣+3∣TF(ℓ)k∣∥∇f0∥.\begin{aligned} \|\nabla f_k\|\le M_{\mathcal{C}(\ell)}^{k-|\mathcal{F}^{(\ell),k}|}2^{|\mathcal{F}^{(\ell),k}|}\left(\frac{1}{4}\right)^{|\mathcal{F}^{(\ell),k}|-|\mathcal{T}_{\mathcal{F}(\ell)}^{k}|}\|\nabla f_0\| \\ &=M_{\mathcal{C}(\ell)}^{k-|\mathcal{F}^{(\ell),k}|}2^{-2|\mathcal{F}^{(\ell),k}|+3|\mathcal{T}_{\mathcal{F}(\ell)}^{k}|}\|\nabla f_0\|. \end{aligned}

Since ∣F(ℓ),k∣≥ak|\mathcal{F}^{(\ell),k}|\ge ak and ∣TF(ℓ)k∣≤∣Tℓk∣≤θk|\mathcal{T}_{\mathcal{F}(\ell)}^{k}|\le|\mathcal{T}_{\ell}^{k}|\le\theta k, we obtain

∥∇fk∥≤βk∥∇f0∥,\|\nabla f_k\|\le\beta^k\|\nabla f_0\|,

where

β:=M1−a2−2a+3θC(ℓ).\beta:= \frac{M_1^{-a}2^{-2a+3\theta}}{C^{(\ell)}}.

Moreover,

log⁡2β=h+3θ−a(h+2)<0\log_2 \beta= h + 3\theta- a(h + 2) < 0

by the choice of aa, and hence β<1\beta< 1.

Therefore, by convexity and Assumption 1.1,

f(xk)−f∗≤D∥∇fk∥≤Dβk∥∇f0∥=O(βk)=O(k−2).f(x_k)-f^* \le D\|\nabla f_k\| \le D\beta^k\|\nabla f_0\| = \mathcal{O}(\beta^k)=\mathcal{O}(k^{-2}).

Combining the two cases proves the result.

Theorem 3.3 provides a quantitative condition under which the multilevel scheme retains the convergence rate of the underlying full-space method. Although this rate need not be inherited by an arbitrary multilevel realization, the theorem shows that the O(k−2)\mathcal{O}(k^{-2}) rate is preserved whenever a sufficiently large fraction of the iterations is performed on the fine level. Such preservation of complexity has also been established for other multilevel high-order regularization frameworks; see, e.g., [5] for the multilevel ARC method and possibly non-convex functions. To the best of our knowledge, Theorem 3.3 is the first result showing that a classical multilevel gradient-regularized Newton method can retain the global O(k−2)\mathcal{O}(k^{-2}) function value rate of the full-space method. This is possible to achieve under an explicit quantitative condition on the proportion of fine-level iterations.

We emphasize that the fine-iteration frequency condition is not restrictive. Indeed, the eligibility condition ∥Ri∇fk∥≥ε\|R_i\nabla f_k\|\ge\varepsilon implies that only finitely many coarse iterations can occur, see Lemma A.2 for details. Consequently, the algorithm eventually performs exclusively fine-level iterations, and the required frequency condition is automatically satisfied for all sufficiently large kk. Nevertheless, this condition is not computationally irrelevant. For instance, for large kk and θ=0.1\theta=0.1, MC(ε)=2M_{C(\varepsilon)}=2 and MC(ε)=2000M_{C(\varepsilon)}=2000 yield approximately a>0.44a>0.44 and a>0.87a>0.87, respectively. This indicates that arbitrarily long sequences of coarse corrections cannot not occur before the algorithm enters the fine-only regime. In Subsection 3.3 we develop analysis establishing an explicit convergence bound valid at every iteration, without relying on the eventual transition to the fine-only regime, and which also allows the method to perform arbitrarily long sequences of coarse corrections.

Row-nested restriction operators

In the previous subsection, we established an O(k−2)\mathcal{O}(k^{-2}) convergence rate under the condition that a sufficiently large fraction of the iterations is performed on the fine level. Such a condition may lead to a large number of computationally expensive fine-level iterations before Algorithm 3.1 enters its fine-level regime. Here we introduce an additional structure on the restriction operators and discuss its most important properties. This new structure will, later, allow us to show a global O(k−2)\mathcal{O}(k^{-2}) rate for Algorithm 3.1 without this condition.

Definition 3.4 (Row-nested restriction operators). Let Ri∈Rni×nR_i\in\mathbb{R}^{n_i\times n}, i∈Ji\in\mathcal{J}, with

n1<n2<⋯<nℓ<n.n_1<n_2<\cdots<n_\ell<n.

The family (Ri)i=1ℓ(R_i)_{i=1}^{\ell} is said to be row-nested if, for every i=1,…,ℓ−1i=1,\ldots,\ell-1, there exists

R^i∈R(ni+1−ni)×n\widehat{R}_i\in\mathbb{R}^{(n_{i+1}-n_i)\times n}

such that

Ri+1=[RiR^i].R_{i+1}= \begin{bmatrix} R_i\\ \widehat{R}_i \end{bmatrix}.

Nested hierarchies of coarse spaces are standard in multigrid and have also been employed in multilevel optimization; see, e.g., [13, 17]. Here we impose a more specific algebraic structure: all restriction operators act on the same fine space, and the rows defining a lower-dimensional restriction are retained at every subsequent level. This row-nested construction yields the monotonicity ∥Riv∥≤∥Rjv∥\lVert R_i v\rVert\le\lVert R_j v\rVert for i<ji<j, which will play a central role in our convergence analysis.

For every i<ji<j there exists R^ij∈R(nj−ni)×n\widehat{R}_{ij} \in\mathbb{R}^{(n_j-n_i)\times n} such that

Rj=[RiR^ij]R_j = \begin{bmatrix} R_i \\ \widehat{R}_{ij} \end{bmatrix}

Consequently, for every v∈Rnv \in\mathbb{R}^n,

∥Rjv∥2=∥Riv∥2+∥R^ijv∥2,\lVert R_jv\rVert^2 = \lVert R_iv\rVert^2 + \lVert\widehat{R}_{ij}v\rVert^2,

and therefore,

∥Riv∥≤∥Rjv∥,1≤i<j≤ℓ.(18)\lVert R_iv\rVert\le\lVert R_jv\rVert,\qquad1\le i<j\le\ell. \tag*{(18)}

Further, Definition 3.4 implies nestedness in multilevel spaces. By the definition of RjR_j we have

Pj=RjT=[PiR^ijT].P_j = R_j^{\mathsf T} = \begin{bmatrix} P_i & \widehat{R}_{ij}^{\mathsf T} \end{bmatrix}.

Therefore, since ni<njn_i<n_j,

range⁡(Pi)⊂range⁡(Pj),i<j,(19)\operatorname{range}(P_i) \subset\operatorname{range}(P_j),\qquad i<j, \tag*{(19)}

and thus, as in classical multilevel methods with nested subspaces, each successive level enriches the previous coarse correction space with additional directions. However, the stronger row-nested structure additionally implies the norm monotonicity (3.3). There also is a corresponding reverse nesting of null spaces, namely

ker⁡(Rj)⊂ker⁡(Ri),i<j,\operatorname{ker}(R_j) \subset\operatorname{ker}(R_i),\qquad i<j,

where the inclusion is strict since dim⁡ker⁡(Rj)=n−nj<n−ni=dim⁡ker⁡(Ri)\dim\operatorname{ker}(R_j)=n-n_j<n-n_i=\dim\operatorname{ker}(R_i). Thus, larger coarse levels miss fewer directions of the fine-space gradient.

Definition 3.4 yields properties that significantly simplify the multilevel algorithm and provides us with further insights. In particular,

ω1≤ω2≤⋯≤ωℓ=ζ,\omega_1\le\omega_2\le\cdots\le\omega_\ell=\zeta,

and the admissible range for σ\sigma simplifies to σ∈(0,min⁡{1,ω1})\sigma\in(0,\min\{1,\omega_1\}). Moreover, (3.3) implies that the eligible sets satisfy

E1⊆E2⊆⋯⊆Eℓ,⋃j<iEj=Ei−1,i=2,…,ℓ.\mathcal{E}_1\subseteq\mathcal{E}_2\subseteq\cdots\subseteq\mathcal{E}_\ell,\qquad\bigcup_{j<i}\mathcal{E}_j=\mathcal{E}_{i-1},\qquad i=2,\ldots,\ell.

Hence,

C1=E1,Ci=Ei∖Ei−1,i=2,…,ℓ,\mathcal{C}_1=\mathcal{E}_1,\qquad\mathcal{C}_i=\mathcal{E}_i\setminus\mathcal{E}_{i-1},\qquad i=2,\ldots,\ell,

and,

C(ℓ)=⋃i=1ℓCi=Eℓ,F(ℓ)=N∖Eℓ.\mathcal{C}^{(\ell)}=\bigcup_{i=1}^{\ell}\mathcal{C}_i=\mathcal{E}_\ell,\qquad\mathcal{F}^{(\ell)}=\mathcal{N}\setminus\mathcal{E}_\ell.

Therefore, k∈Cik\in\mathcal{C}_i means that level ii is the lowest-dimensional level satisfying the eligibility criterion at iteration kk. Every level j>ij>i is then automatically eligible, whereas no level j<ij<i is.

Remark 3.5. The nested structure also induces a hierarchy of reduced Hessian matrices. Indeed, for i<ji<j,

Rj∇2f(x)Pj=[Ri∇2f(x)PiRi∇2f(x)R^ijTR^ij∇2f(x)PiR^ij∇2f(x)R^ijT].R_j\nabla^2 f(x)P_j = \begin{bmatrix} R_i\nabla^2 f(x)P_i & R_i\nabla^2 f(x)\widehat{R}_{ij}^{\mathsf{T}} \\ \widehat{R}_{ij}\nabla^2 f(x)P_i & \widehat{R}_{ij}\nabla^2 f(x)\widehat{R}_{ij}^{\mathsf{T}} \end{bmatrix}.

Hence, Ri∇2f(x)PiR_i\nabla^2 f(x)P_i is a principal submatrix of Rj∇2f(x)PjR_j\nabla^2 f(x)P_j. Consequently, by the Cauchy interlacing theorem [15], their eigenvalues satisfy

λr(Rj∇2f(x)Pj)≤λr(Ri∇2f(x)Pi)≤λr+nj−ni(Rj∇2f(x)Pj),\lambda_r\left(R_j\nabla^2 f(x)P_j\right) \le\lambda_r\left(R_i\nabla^2 f(x)P_i\right) \le\lambda_{r+n_j-n_i}\left(R_j\nabla^2 f(x)P_j\right),

for r=1,…,nir=1,\ldots,n_i, where the eigenvalues are ordered increasingly. Moreover, if ff is convex, then

Ri∇2f(x)Pi⪰0,i∈J,R_i\nabla^2 f(x)P_i \succeq0,\qquad i\in\mathcal{J},

while ∇2f(x)≻0\nabla^2 f(x)\succ0 together with the full row rank of RiR_i implies

Ri∇2f(x)Pi≻0.R_i\nabla^2 f(x)P_i \succ0.

Thus, increasing the level enriches the reduced model while retaining the curvature information contained in the preceding levels. However, note that the principal-submatrix relation concerns the unregularized reduced Hessians; the regularized matrices need not be nested because the regularization parameter depends on the level.

Remark 3.6. An important special case of Definition 3.4 arises when the restriction operators have orthonormal rows, i.e.,

RiRiT=Ini,i∈J.R_iR_i^{\mathsf{T}}=I_{n_i},\qquad i\in\mathcal{J}.

Then

Qi:=PiRi=RiTRiQ_i:=P_iR_i=R_i^{\mathsf{T}}R_i

is the orthogonal projector onto range⁡(Pi)\operatorname{range}(P_i). Moreover, (3.4) implies

QiQj=QjQi=Qi,Qi⪯Qj,i<j.Q_iQ_j=Q_jQ_i=Q_i,\qquad Q_i\preceq Q_j,\qquad i<j.

Thus, increasing the level enlarges the projected subspace while retaining all directions represented at the preceding levels.

A simple and computationally efficient construction satisfying Assumption 3.1, Definition 3.4, and the orthonormal-row condition considered above is obtained by selecting nested subsets of the rows of the identity matrix. Specifically, let S1⊂⋯⊂Sℓ⊂{1,…,n}S_1\subset\cdots\subset S_\ell\subset\{1,\ldots,n\} with ∣Si∣=ni|S_i|=n_i, and let RiR_i consist of the rows of InI_n indexed by SiS_i. For each i=1,…,ℓ−1i=1,\ldots,\ell-1, choosing R^i\widehat{R}_i as the rows of InI_n indexed by Si+1∖SiS_{i+1}\setminus S_i yields

Ri+1=[RiR^i].R_{i+1}= \begin{bmatrix} R_i\\ \widehat{R}_i \end{bmatrix}.

Since the selected rows are distinct standard basis vectors, RiRiT=IniR_iR_i^{\mathsf{T}}=I_{n_i} for every i∈Ji\in\mathcal{J}. Thus, Assumption 3.1 is satisfied with ωi=1\omega_i=1, i∈Ji\in\mathcal{J}, and further σ∈(0,1)\sigma\in(0,1).

Remark 3.7. A general construction satisfying both Assumption 3.1 and Definition 3.4 is obtained by choosing any full row-rank restriction operator Rℓ∈Rnℓ×nR_\ell\in\mathbb{R}^{n_\ell\times n} and defining RiR_i as its first nin_i rows, for i=1,…,ℓ−1i=1,\ldots,\ell-1. Indeed, the full row-rank of RℓR_\ell guarantees that rank⁡(Ri)=ni\operatorname{rank}(R_i)=n_i, while the construction yields Ri+1=[RiTR^iT]TR_{i+1}=\begin{bmatrix}R_i^{\mathsf{T}} & \widehat{R}_i^{\mathsf{T}}\end{bmatrix}^{\mathsf{T}}, where R^i\widehat{R}_i consists of rows ni+1,…,ni+1n_i+1,\ldots,n_{i+1} of RℓR_\ell. This construction accommodates, for instance, Gaussian matrices, suitable sparse sketching matrices, and coordinate restrictions.

Convergence analysis using the row-nested restriction operators

We now establish an O(k−2)O(k^{-2}) convergence rate for Algorithm 3.1 under the row-nested structure of Definition 3.4, without imposing any condition on the frequency of fine-level iterations. The analysis extends the weighted-gradient argument developed for the two-level method. An additional difficulty arises from transitions between different coarse levels, since the corresponding updates control distinct reduced-gradient norms ∥Ri∇fk∥\lVert R_i\nabla f_k\rVert. For general restriction operators, these quantities need not be comparable across levels. The row-nested structure provides the necessary norm comparisons, which, together with suitable level-dependent weights, allow us to control transitions among all coarse and fine levels.

Theorem 3.8. Let ff be convex and suppose that Assumptions 1.1 and 1.2 hold. If the sequence (xk)k∈N(x_k)_{k\in\mathbb{N}} is generated by Algorithm 3.1 with row-nested operators for which Assumption 3.1 hold, then

f(xk)−f∗=O(k−2).f(x_k)-f^*=O(k^{-2}).

Proof. The proof makes use of the set Iℓk(ρ)\mathcal{I}_{\ell}^{k}(\rho) and as previously we split the analysis into two cases, according to the magnitude of Iℓk(ρ)\mathcal{I}_{\ell}^{k}(\rho).

Recall that, due to the row-nestedness, ζ=ωℓ\zeta=\omega_\ell, and define ωˉ:=max⁡{1,ωℓ}\bar{\omega}:=\max\{1,\omega_\ell\}. We choose

θ∈(0,11+ℓ),r∈(0,min⁡{1Λ,B}),ρ∈(0,Λωˉr1+ℓ),\theta\in\left(0,\frac{1}{1+\ell}\right),\qquad r\in\left(0,\min\left\{\frac{1}{\Lambda},B\right\}\right),\qquad\rho\in\left(0,\frac{\Lambda}{\bar{\omega}}r^{1+\ell}\right),

where

Λ:=ωˉMC(ℓ)σ,B:=exp⁡(−(1−θ)ln⁡(Λ)+θln⁡(2ωˉ)1−(1+ℓ)θ),\Lambda:=\frac{\bar{\omega}M C_{(\ell)}}{\sigma},\qquad B:=\exp\left(-\frac{(1-\theta)\ln(\Lambda)+\theta\ln(2\bar{\omega})}{1-(1+\ell)\theta}\right),

and note that Λ≥1\Lambda\ge1 and B,r,ρ∈(0,1)B,r,\rho\in(0,1). Moreover, for i∈Ji\in\mathcal{J}, we define

ai:=ri−1,b:=rℓ,a_i:=r^{i-1},\qquad b:=r^\ell,

therefore 1=a1>⋯>aℓ>01=a_1>\cdots>a_\ell>0, and note also that ajai=rj−i>1\frac{a_j}{a_i}=r^{j-i}>1, if j<ij<i, and rj−i<1r^{j-i}<1, if j>ij>i.

Let us fix a k∈Nk\in\mathbb{N}. If ∣Iℓk(ρ)∣>θk\lvert\mathcal{I}_{\ell}^{k}(\rho)\rvert>\theta k, then Lemma 3.2 provides the desired rate of convergence. Assume now that ∣Iℓk(ρ)∣≤θk\lvert\mathcal{I}_{\ell}^{k}(\rho)\rvert\le\theta k. Define the weight gradient measure for ℓ\ell coarse levels

Vk:={ai∥Ri∇fk∥,k∈Ci, i∈J,b∥∇fk∥,k∈F(ℓ).V_k:=\begin{cases} a_i\lVert R_i\nabla f_k\rVert, & k\in\mathcal{C}_i,\ i\in\mathcal{J},\\ b\lVert\nabla f_k\rVert, & k\in\mathcal{F}^{(\ell)}. \end{cases}

Thus, by the definition of aia_i and VkV_k,

∥∇fk∥≤max⁡{1a1σ,…,1aℓσ,1b}Vk=max⁡{1aℓσ,1b}Vk.(20)\lVert\nabla f_k\rVert\le\max\left\{\frac{1}{a_1\sigma},\ldots,\frac{1}{a_\ell\sigma},\frac{1}{b}\right\}V_k=\max\left\{\frac{1}{a_\ell\sigma},\frac{1}{b}\right\}V_k. \tag*{(20)}

Next, it holds

(Iℓk(ρ))c={0,1,…,k−1}∖Iℓk(ρ)=(⋃i∈JCik∖ICik(ρ))∪(F(ℓ),k∖IF(ℓ)k(ρ)).\left(\mathcal{I}_{\ell}^{k}(\rho)\right)^{c}=\{0,1,\ldots,k-1\}\setminus\mathcal{I}_{\ell}^{k}(\rho)=\left(\bigcup_{i\in\mathcal{J}}C_{i}^{k}\setminus\mathcal{I}_{C_{i}}^{k}(\rho)\right)\cup\left(\mathcal{F}^{(\ell),k}\setminus\mathcal{I}_{\mathcal{F}^{(\ell)}}^{k}(\rho)\right).

We first examine the case m∈(Iℓk(ρ))cm\in\left(\mathcal{I}_{\ell}^{k}(\rho)\right)^{c}, where, in particular, we will show that VkV_{k} is a contraction. To achieve this, in comparison to the proof of Theorem 2.5, we need to examine an extra case which concerns the transitions between the ℓ\ell coarse levels:

  1. m∈Cik∖ICikm\in C_{i}^{k}\setminus\mathcal{I}_{C_{i}}^{k}, m+1∈Cjm+1\in C_{j}. We analyze this case by splitting into additional three subcases according to the ordering of the coarse levels:

(a) j<ij<i. Then, by the row-nestedness (3.3), we have

Vm+1=aj∥Rj∇fm+1∥≤aj∥Ri∇fm+1∥≤∑k∉ICikρaj∥Ri∇fm∥=rj−iρVk≤r1−ℓρVk,\begin{aligned} V_{m+1}=a_{j}\left\|R_{j}\nabla f_{m+1}\right\|\leq a_{j}\left\|R_{i}\nabla f_{m+1}\right\| \\ &\leq\sum_{k\notin\mathcal{I}_{C_{i}}^{k}}\rho a_{j}\left\|R_{i}\nabla f_{m}\right\|=r^{j-i}\rho V_{k}\leq r^{1-\ell}\rho V_{k}, \end{aligned}

where the last inequality uses the fact that x↦rxx\mapsto r^{x} is non-increasing for r∈(0,1)r\in(0,1).

(b) i<ji<j. Then,

Vm+1=aj∥Rj∇fm+1∥≤ajωˉ∥∇fm+1∥≤ajωˉMC(ℓ)∥∇fm∥≤∑k∈CikΛrj−iVm≤ΛrVm,\begin{aligned} V_{m+1}=a_{j}\left\|R_{j}\nabla f_{m+1}\right\|\leq a_{j}\bar{\omega}\left\|\nabla f_{m+1}\right\| \\ &\leq a_{j}\bar{\omega}M_{C(\ell)}\left\|\nabla f_{m}\right\|\leq\sum_{k\in C_{i}^{k}} \Lambda r^{j-i}V_{m}\leq\Lambda rV_{m}, \end{aligned}

where we have use the uniform stability of the coarse corrections, i.e., ∥∇fk+1∥≤MC(ℓ)∥∇fk∥\left\|\nabla f_{k+1}\right\|\leq M_{C(\ell)}\left\|\nabla f_{k}\right\| with MC(ℓ)M_{C(\ell)} defined in Theorem 3.3.

(c) i=ji=j. Then we immediately have

Vm+1≤ρVm.V_{m+1}\leq\rho V_{m}.

Combining the above subcases yields

Vm+1≤max⁡{ρ,Λr,r1−ℓρ}Vm=ΛrVm,V_{m+1}\leq\max\left\{\rho,\Lambda r,r^{1-\ell}\rho\right\}V_{m}=\Lambda rV_{m},

where the last equality hold by the choice on ρ\rho. This concludes the first case of arbitrary transitions between coarse spaces.

  1. m∈Cik∖ICikm\in C_{i}^{k}\setminus\mathcal{I}_{C_{i}}^{k}, m+1∈F(ℓ)m+1\in\mathcal{F}^{(\ell)}. Then

Vm+1≤b∥∇fm+1∥≤bMC(ℓ)∥∇fm∥≤∑k∈Cikrℓ−i+1MC(ℓ)σ∥∇fm∥≤ΛrVm.V_{m+1}\leq b\left\|\nabla f_{m+1}\right\|\leq bM_{C(\ell)}\left\|\nabla f_{m}\right\|\leq\sum_{k\in C_{i}^{k}}r^{\ell-i+1}\frac{M_{C(\ell)}}{\sigma}\left\|\nabla f_{m}\right\|\leq\Lambda rV_{m}.
  1. m∈F(ℓ),k∖IF(ℓ)k(ρ)m\in\mathcal{F}^{(\ell),k}\setminus\mathcal{I}_{\mathcal{F}^{(\ell)}}^{k}(\rho), m+1∈Cim+1\in C_{i}. Then,

Vm+1=ai∥Ri∇fm+1∥≤aiωˉρ∥∇fm∥=ωˉρrℓ−i+1Vm≤ωˉρrℓVm.V_{m+1}=a_{i}\left\|R_{i}\nabla f_{m+1}\right\|\leq a_{i}\bar{\omega}\rho\left\|\nabla f_{m}\right\|=\frac{\bar{\omega}\rho}{r^{\ell-i+1}}V_{m}\leq\frac{\bar{\omega}\rho}{r^{\ell}}V_{m}.
  1. m∈F(ℓ),k∖IF(ℓ)k(ρ)m\in\mathcal{F}^{(\ell),k}\setminus\mathcal{I}_{\mathcal{F}^{(\ell)}}^{k}(\rho), m+1∈F(ℓ)m+1\in\mathcal{F}^{(\ell)}, then we directly obtain

Vm+1≤ρVm.V_{m+1}\leq\rho V_{m}.

Therefore, by the definition of ρ\rho,

Vm+1≤{ρ,Λr,ωˉrℓ}Vm=ΛrVm<Vm,m∈(Iℓk(ρ))c.(21)V_{m+1} \le\left\{\rho,\Lambda r,\frac{\bar{\omega}}{r^{\ell}}\right\}V_m=\Lambda rV_m<V_m,\qquad m\in\left(\mathcal{I}_{\ell}^{k}(\rho)\right)^{\mathrm{c}}. \tag*{(21)}

which shows that VkV_k is a contraction for elements of (Iℓk(ρ))c\left(\mathcal{I}_{\ell}^{k}(\rho)\right)^{\mathrm{c}}.

Assume now that m∈Iℓk(ρ)m\in\mathcal{I}_{\ell}^{k}(\rho). Similarly, we split our arguments into four cases, to obtain a recurrent relation for VkV_k. However, since Iℓk(ρ)\mathcal{I}_{\ell}^{k}(\rho) contains a few elements only, VkV_k is not required to be a contraction.

  1. m∈Cik,m+1∈Cjm\in C_i^k,m+1\in C_j. Then,

Vm+1=aj∥Rj∇fm+1∥≤ajω~MC(ℓ)∥∇fm∥≤Λrj−iVm≤r−ℓVm.V_{m+1}=a_j\left\|R_j\nabla f_{m+1}\right\|\leq a_j\widetilde{\omega}M_{C(\ell)}\left\|\nabla f_m\right\|\leq\Lambda r^{j-i}V_m\leq r^{-\ell}V_m.

where the last inequality uses the monotonicity of x↦rxx\mapsto r^x, r∈(0,1)r\in(0,1).

  1. m∈Cik,m+1∈F(ℓ)m\in C_i^k,m+1\in\mathcal{F}^{(\ell)}. Then,

Vm+1≤rℓMC(ℓ)∥∇fm∥≤rℓ−i+1ΛVm≤Vm.V_{m+1}\leq r^\ell M_{C(\ell)}\left\|\nabla f_m\right\|\leq r^{\ell-i+1}\Lambda V_m\leq V_m.
  1. m,∈F(ℓ),k,m+1∈F(ℓ)m,\in\mathcal{F}^{(\ell),k},m+1\in\mathcal{F}^{(\ell)}. Then, by (8),

Vm+1≤2Vm.V_{m+1}\leq2V_m.
  1. m∈F(ℓ),k,m+1∈Cim\in\mathcal{F}^{(\ell),k},m+1\in C_i. Then,

Vm+1≤ai∥Ri∇fm+1∥≤2aiω~∥∇fm∥≤2r−ℓω~Vm.V_{m+1}\leq a_i\left\|R_i\nabla f_{m+1}\right\|\leq2a_i\widetilde{\omega}\left\|\nabla f_m\right\|\leq2r^{-\ell}\widetilde{\omega}V_m.

As a result, the above four cases imply

Vm+1≤2ω~r−ℓVm,m∈Iℓk(ρ).(22)V_{m+1}\leq2\widetilde{\omega}r^{-\ell}V_m,\qquad m\in\mathcal{I}_{\ell}^{k}(\rho). \tag*{(22)}

Let us denote

η:=r1−(1+ℓ)θΛ1−θ(2ω~)θ.\eta:=r^{1-(1+\ell)\theta}\Lambda^{1-\theta}(2\widetilde{\omega})^\theta.

By the choices of θ\theta and ρ\rho it easy to see that r1−(1+ℓ)θ<1r^{1-(1+\ell)\theta}<1 and since r<Br<B we have η<1\eta<1. Hence, by (21) and (22), we obtain

Vk≤(Λr)k−∣Iℓk(ρ)∣(2r−ℓω~)∣Iℓk(ρ)∣V0≤ηkV0,V_k\leq(\Lambda r)^{k-\left|\mathcal{I}_{\ell}^{k}(\rho)\right|}\left(2r^{-\ell}\widetilde{\omega}\right)^{\left|\mathcal{I}_{\ell}^{k}(\rho)\right|}V_0 \leq\eta^kV_0,

which shows that VkV_k is a contraction. Now the desired result follows from the last inequality, convexity, and (20) as follows. Let

Aℓ=max⁡{1σrℓ−1,1rℓ}.A_\ell=\max\left\{\frac{1}{\sigma r^{\ell-1}},\frac{1}{r^\ell}\right\}.

Then

f(xk)−f∗≤D∥∇fk∥≤DAℓVk≤DAℓV0ηkf(x_k)-f^*\leq D\left\|\nabla f_k\right\|\leq DA_\ell V_k\leq DA_\ell V_0\eta^k

which shows exponential rate for the case ∣Iℓk(ρ)∣≤θk\left|\mathcal{I}_{\ell}^{k}(\rho)\right|\leq\theta k. Hence the two cases imply

f(xk)−f∗≤max⁡{DAℓV0ηk,1Cℓ2(1+θk/2)2},f(x_k)-f^*\leq\max\left\{DA_\ell V_0\eta^k,\frac{1}{C_\ell^2(1+\theta k/2)^2}\right\},

which concludes the proof.

Theorem 3.8 establishes a direct O(k−2)O(k^{-2}) convergence bound for the multilevel method with row-nested restriction operators, without imposing any condition on the frequency of fine-level iterations. Although the asymptotic rate also follows for general restriction operators from the eventual fine-only behavior, the present analysis controls the convergence rate throughout the entire sequence, including coarse-dominated phases. In particular, the resulting bound does not depend on the iteration at which the method enters the fine-only regime.

The main difficulty for achieving this result is that a coarse correction at level ii controls ∥Ri∇fk+1∥\lVert R_i\nabla f_{k+1}\rVert, but not necessarily the reduced gradient at the subsequently selected level. Row-nestedness resolves this mismatch through monotonicity of the reduced-gradient norms, which, together with level-dependent weights and uniform full-gradient stability, allows us to control arbitrary transitions between levels. The resulting weighted gradient measure contracts outside a set of non-ρ\rho-contracting iterations, while its growth remains uniformly bounded otherwise. When non-ρ\rho-contracting iterations are sufficiently frequent, the function-value decrease estimates instead yield the O(k−2)O(k^{-2}) rate. Thus, the analysis accommodates arbitrarily long sequences of coarse corrections without requiring a prescribed frequency of fine iterations or a decrease of the full gradient at every coarse step.

Experiments

In this section, we present numerical experiments to support our theoretical findings. In particular, we compare the performance of the two-level regularized Newton (TLRN), multilevel regularized Newton (MLRN), and row-nested multilevel regularized Newton (MLRN nested) methods with that of the full-space gradient-regularized Newton method (RN) [19]. Although our methods retain the O(k−2)O(k^{-2}) convergence rate of RN, the constants in their complexity bounds depend on σ<1\sigma< 1, see Lemma 3.2, potentially leading to less favorable theoretical bounds. Nevertheless, since the multilevel methods compute some of their updates in lower-dimensional spaces, they may offer significant computational savings. Our experiments aim to illustrate that the multilevel methods exhibit convergence behavior comparable to RN while potentially reducing the overall computational time.

The restriction operators for MLRN are constructed by selecting rows of the identity matrix as in [28], whereas for the row-nested method we use the construction described in Theorem 3.6. We consider ℓ=5\ell= 5 coarse levels with dimensions n1=0.1nn_1 = 0.1n, n2=0.3nn_2 = 0.3n, n3=0.5nn_3 = 0.5n, n4=0.7nn_4 = 0.7n, and n5=0.9nn_5 = 0.9n, whereas for TLRN we select d=0.5nd = 0.5n.

Since the Hessian’s Lipschitz constant LL is generally unknown, we employ an adaptive line-search procedure, following the approach of [22 Section 4.1.4.2] and [19]. At each iteration, the estimate LkL_k is increased until the corresponding sufficient-decrease and gradient-stability conditions are satisfied. We set ε=10−10\varepsilon= 10^{-10} and terminate the algorithms when f(xk)−f∗≤εff(x_k) - f^* \leq\varepsilon_f or ∥∇f(xk)∥≤εg\lVert\nabla f(x_k)\rVert\leq\varepsilon_g, where εf=10−8\varepsilon_f = 10^{-8} and εg=ε\varepsilon_g = \varepsilon. We use L-BFGS to compute a numerical approximation of the optimal objective value f∗f^*. We set σ=0.5\sigma= 0.5, balancing the frequency of coarse corrections against their effectiveness (note that larger values of σ\sigma yield more favorable convergence constants but impose a stricter coarse-level eligibility condition, potentially resulting in more fine-level iterations). All experiments are initialized at the origin.

Log-sum-exp

Given data a1,…,am∈Rna_1,\ldots,a_m \in\mathbb{R}^n and b1,…,bm∈Rb_1,\ldots,b_m \in\mathbb{R}, we consider minimizing the log-sum-exp function

fγ(x)=γln⁡(∑i=1mexp⁡(aiTx−biγ)),γ>0.f_\gamma(x) = \gamma\ln\left(\sum_{i=1}^{m}\exp\left(\frac{a_i^{\mathsf{T}}x-b_i}{\gamma}\right)\right), \qquad\gamma> 0.

Experiments

The parameter γ\gamma controls the smoothing of the log-sum-exp objective. We generate a random dataset with m=1000m = 1000 observations and n=800n = 800 variables and consider three values of this parameter, namely γ∈{0.05,0.1,0.5}\gamma\in\{0.05, 0.1, 0.5\}, to investigate the sensitivity of the algorithms to different degrees of smoothing.

The results are presented in Figure 1. For all three values of γ\gamma, row-nested MLRN and TLRN exhibit convergence behavior comparable to that of RN, both in terms of iterations and computational time. In contrast, the non-nested MLRN method converges substantially more slowly. We suspect that this difference may be related to the fine-iteration frequency condition in Theorem 3.3, which need not be satisfied during the observed iterations. Nevertheless, these findings suggest that row-nested restriction operators can be an attractive choice from both theoretical and computational perspectives.

Convergence plots comparing MLRN, row-nested MLRN, regularized Newton, and two-level regularized Newton

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 γ∈{0.05,0.1,0.5}\gamma\in\{0.05, 0.1, 0.5\}. The left column shows the objective gap f(xk)−f∗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.

Logistic regression

In the second experiment, we consider logistic regression problems using real-world datasets. The objective function is given by

f(x)=1m∑i=1mln⁡(1+exp⁡(−biaiTx))+λ22∥x∥2(23)f(x)=\frac{1}{m}\sum_{i=1}^{m}\ln\left(1+\exp\left(-b_i a_i^{\mathsf{T}}x\right)\right)+\frac{\lambda_2}{2}\lVert x\rVert^2 \tag*{(23)}

where bi∈{−1,1}b_i \in\{-1,1\} and we set λ2=10−10\lambda_2=10^{-10} to make the problem ill-conditioned. The results are presented in Figure 2 and Figure 3.

Convergence comparison plots for Gisette and Duke datasets

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(xk)−f∗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.

Convergence comparison plots for MLRN, row-nested MLRN, RN, and TLRN

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(xk)−f∗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.

Across the considered datasets, nested MLRN and TLRN exhibit convergence behavior comparable to that of the full-space RN method. Moreover, as shown in Figure 2, when applied to large datasets, both methods achieve substantial reductions in computational time, illustrating the benefits of performing corrections in lower-dimensional spaces. In contrast, non-row-nested MLRN exhibits slower convergence on some instances, particularly those shown in Figure 3, which may prevent the method from converging faster than RN in computational time. These observations suggest that the structure of the restriction operators, particularly row-nestedness, can play an important role in the practical performance of multilevel gradient-regularized Newton methods. Overall, the results demonstrate that row-nested restriction operators can yield computationally efficient multilevel methods, complementing the theoretical convergence guarantees established in this paper.

Conclusions

We developed and analyzed multilevel gradient-regularized Newton methods for unconstrained convex optimization, establishing a global O(k−2)\mathcal{O}(k^{-2}) convergence rate in function values. Among our results, the proof of Theorem 3.8 is of particular interest as it combines a weighted gradient measure with row-nestedness, a special structure of the restriction operators introduced in Subsection 3.2 for the purposes of this analysis. These ideas are new in multilevel optimization theory and we believe that they could prove useful for establishing fast convergence rates for other multilevel methods, such as cubic-regularized Newton and higher-order methods.

Code and data availability. The code for reproducing the numerical results is available at

https://github.com/Ntsip/Multilevel-Gradient-Regularized-Newton-Method.

It is authored by Nick Tsipinakis and published under the MIT license. The benchmark data used in the experiments is taken from

https://www.csie.ntu.edu.tw/~cjlin/libsvmtools/datasets/.

CRediT author statement. Nick Tsipinakis: Conceptualization, Methodology, Software, Formal Analysis, Investigation, Writing — Original Draft, Visualization; Matthias Voigt: Writing — Review & Editing, Visualization, Supervision.

Acknowledgments. The authors used AI tools to assist with language and figure editing, mathematical proof verification, and the development and debugging of numerical implementations. All mathematical results, algorithms, and computational experiments were reviewed and validated by the authors. The authors assume responsibility for all content.

Background and proofs of auxiliary results

Proposition A.1. Let (Δℓ)ℓ=0τ(\Delta_\ell)_{\ell=0}^{\tau} be a tuple of nonnegative numbers satisfying

Δℓ+1≤Δℓ−CΔℓ3/2,ℓ=0,…,τ−1,\Delta_{\ell+1} \le\Delta_\ell- C\Delta_\ell^{3/2}, \qquad\ell= 0,\ldots,\tau-1,

for some C>0C > 0 and τ≥1\tau\ge1. Then

Δτ≤1C2(1+τ/2)2.\Delta_\tau\le\frac{1}{C^2(1+\tau/2)^2}.

Proof. If Δℓ=0\Delta_\ell= 0 for some ℓ\ell, the recurrence and nonnegativity imply Δj=0\Delta_j = 0 for all j≥ℓj \ge\ell, so the result follows immediately. Otherwise, nonnegativity implies CΔℓ<1C\sqrt{\Delta_\ell} < 1, and hence

1Δℓ+1≥1Δℓ1−CΔℓ≥1Δℓ+C2,\frac{1}{\sqrt{\Delta_{\ell+1}}} \ge\frac{1}{\sqrt{\Delta_\ell}\sqrt{1-C\sqrt{\Delta_\ell}}} \ge\frac{1}{\sqrt{\Delta_\ell}}+\frac{C}{2},

where we used (1−s)−1/2≥1+s/2(1-s)^{-1/2} \ge1+s/2 for s∈[0,1)s \in[0,1). Summing 1Δℓ+1−1Δℓ\frac{1}{\sqrt{\Delta_{\ell+1}}}-\frac{1}{\sqrt{\Delta_\ell}} over ℓ=0,…,τ−1\ell=0,\ldots,\tau-1, exploiting the telescoping property, and using 1Δ0≥C\frac{1}{\sqrt{\Delta_0}}\ge C gives

1Δτ≥C(1+τ2),\frac{1}{\sqrt{\Delta_\tau}} \ge C\left(1+\frac{\tau}{2}\right),

which proves the claim.

We also refer to [22 Theorem 4.1.4] for a related recurrence estimate.

Lemma A.2. Suppose that Assumptions 1.1, 1.2, and 3.1 hold. Then Algorithm 3.1 performs only finitely many coarse iterations.

Proof of lemma:multilevel-coarse-estimates

Proof. Let k∈Cik \in\mathcal{C}_i for some i∈Ji \in\mathcal{J}, and define

αi,k:=ωi3L∥Ri∇fk∥2,di,k:=−(Ri∇2fkPi+αi,kIni)−1Ri∇fk.\alpha_{i,k}:=\sqrt{\frac{\omega_i^3 L\lVert R_i\nabla f_k\rVert}{2}}, \qquad d_{i,k}:=-\left(R_i\nabla^2 f_kP_i+\alpha_{i,k}I_{n_i}\right)^{-1}R_i\nabla f_k.

By the coarse-level eligibility condition,

αi,k≥ωi3Lε2>0.\alpha_{i,k}\ge\sqrt{\frac{\omega_i^3 L\varepsilon}{2}}>0.

Moreover, since the iterates remain in the compact set L(x0)\mathcal{L}(x_0), there exists

G:=max⁡x∈L(x0)∥∇f(x)∥<∞.G:=\max_{x\in\mathcal{L}(x_0)}\lVert\nabla f(x)\rVert<\infty.

Consequently,

αi,k≤αˉi:=ωi2LG2.\alpha_{i,k}\le\bar{\alpha}_i:=\omega_i^2\sqrt{\frac{LG}{2}}.

Using the definition of di,kd_{i,k}, we obtain

ε≤∥Ri∇fk∥≤(ωi2H+αi,k)∥di,k∥≤(ωi2H+αˉi)∥di,k∥.\varepsilon\le\lVert R_i\nabla f_k\rVert\le\left(\omega_i^2H+\alpha_{i,k}\right)\lVert d_{i,k}\rVert\le\left(\omega_i^2H+\bar{\alpha}_i\right)\lVert d_{i,k}\rVert.

Hence,

∥di,k∥≥εωi2H+αˉi.\lVert d_{i,k}\rVert\ge\frac{\varepsilon}{\omega_i^2H+\bar{\alpha}_i}.

By the descent estimate in [27 Lemma 3.3], the coarse update satisfies

f(xk)−f(xk+1)≥αi,k2∥di,k∥2.f(x_k)-f(x_{k+1})\ge\frac{\alpha_{i,k}}{2}\lVert d_{i,k}\rVert^2.

Combining the preceding estimates yields

f(xk)−f(xk+1)≥12ωi3Lε2(εωi2H+αˉi)2(εωi2H+αˉi)2⏟=:δi>0.f(x_k)-f(x_{k+1})\ge\frac{1}{2}\sqrt{\frac{\omega_i^3L\varepsilon}{2}}\left(\frac{\varepsilon}{\omega_i^2H+\bar{\alpha}_i}\right)^2 \underset{=:\delta_i>0}{\underbrace{\vphantom{\left(\frac{\varepsilon}{\omega_i^2H+\bar{\alpha}_i}\right)^2}}}.

Since the number of coarse levels is finite, δ:=min⁡i∈Jδi>0\delta:=\min_{i\in\mathcal{J}}\delta_i>0. Therefore, every coarse iteration decreases the objective function by at least δ\delta. By monotonicity of the function values and their lower boundedness by f∗f^*,

∣C(ℓ)∣δ≤f(x0)−f∗.\lvert\mathcal{C}^{(\ell)}\rvert\delta\le f(x_0)-f^*.

Thus, ∣C(ℓ)∣<∞\lvert\mathcal{C}^{(\ell)}\rvert<\infty, proving the result.

Proof of Lemma 3.1.

Proof. The result follows from the analysis in [27 Lemma 3.2 and Corollary 3.4], which allows the restriction operator to vary with the iteration. Indeed, at an iteration k∈Cik\in\mathcal{C}_i, applying the corresponding estimates with Rk=RiR_k=R_i and ωi=∥Ri∥\omega_i=\lVert R_i\rVert yields

∥Ri∇fk+1∥≤2αk∥di,k∥,∥di,k∥≤∥Ri∇fk∥αk.\lVert R_i\nabla f_{k+1}\rVert\le2\alpha_k\lVert d_{i,k}\rVert,\qquad\lVert d_{i,k}\rVert\le\frac{\lVert R_i\nabla f_k\rVert}{\alpha_k}.

where

αk=ωi3L∥Ri∇fk∥2,di,k:=−(Ri∇2fkPi+αkIni)−1Ri∇fk.\alpha_k=\sqrt{\frac{\omega_i^3L\lVert R_i\nabla f_k\rVert}{2}},\qquad d_{i,k}:=-\left(R_i\nabla^2 f_kP_i+\alpha_kI_{n_i}\right)^{-1}R_i\nabla f_k.

These inequalities yield (17), while the proof of [27 Corollary 3.4] gives (16).

Proof of lemma:case-II

Proof. The proof of Case II in Theorem 2.5 extends naturally to ℓ\ell coarse levels. Thus, below, only the main steps of the proof will be discussed. Let τ:=∣Iℓk(ρ)∣\tau:= \lvert\mathcal{I}^{k}_{\ell}(\rho) \rvert and enumerate Iℓk(ρ)={k0,…,kτ−1}\mathcal{I}^{k}_{\ell}(\rho) = \{k_0,\ldots,k_{\tau-1}\} increasingly, with kτ:=kk_\tau:= k. If kj∈ICik(ρ)k_j \in\mathcal{I}^{k}_{C_i}(\rho) for some i∈Ji \in\mathcal{J}, then, using the coarse decrease estimate ωi≤ζ\omega_i \le\zeta and ∥Ri∇fkj∥≥σ∥∇fkj∥\lVert R_i \nabla f_{k_j}\rVert\ge\sigma\lVert\nabla f_{k_j}\rVert, we obtain

f(xkj)−f(xkj+1)≥2ρ28L(σζ)3/2∥∇fkj∥3/2.f(x_{k_j}) - f(x_{k_{j+1}}) \ge\frac{\sqrt{2}\rho^2}{8\sqrt{L}}\left(\frac{\sigma}{\zeta}\right)^{3/2}\lVert\nabla f_{k_j}\rVert^{3/2}.

The same bound holds for kj∈IF(ℓ)k(ρ)k_j \in\mathcal{I}^{k}_{F(\ell)}(\rho) by the fine-level decrease estimate. Hence, arguing as in Case II of Theorem 2.5,

Δj+1≤Δj−CℓΔj3/2,Δj:=f(xkj)−f∗.\Delta_{j+1} \le\Delta_j - C_\ell\Delta_j^{3/2}, \qquad\Delta_j := f(x_{k_j}) - f^*.

Since τ>θk\tau> \theta k, Proposition A.1 yields

f(xk)−f∗≤1Cℓ2(1+θk/2)2.f(x_k) - f^* \le\frac{1}{C_\ell^2(1+\theta k/2)^2}.

References

  1. [1]A. Ang, H. De Sterck, and S. Vavasis, MGProx: A nonsmooth multigrid proximal gradient method with adaptive restriction for strongly convex optimization, SIAM J. Optim., 34 (2024), pp. 2788–2820, https://doi.org/10.1137/23M1552140.
  2. [2]P. Binev, A. Cohen, W. Dahmen, R. DeVore, G. Petrova, and P. Wojtaszczyk, Convergence rates for greedy algorithms in reduced basis methods, SIAM J. Math. Anal., 43 (2011), pp. 1457–1472, https://doi.org/10.1137/100795772.
  3. [3]M. S. Branicky, Multiple Lyapunov functions and other analysis tools for switched and hybrid systems, IEEE Trans. Automat. Control, 43 (1998), pp. 475–482, https://doi.org/10.1109/9.664150.
  4. [4]W. L. Briggs, V. E. Henson, and S. F. McCormick, A Multigrid Tutorial, SIAM, Philadelphia, PA, 2nd ed., 2000, https://doi.org/10.1137/1.9780898719505.
  5. [5]H. Calandra, S. Gratton, E. Riccietti, and X. Vasseur, On high-order multilevel optimization strategies, SIAM J. Optim., 31 (2021), pp. 307–330, https://doi.org/10.1137/19M1255355.
  6. [6]C. Cartis, N. I. M. Gould, and P. L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part I: Motivation, convergence and numerical results, Math. Program., 127 (2011), pp. 245–295, https://doi.org/10.1007/s10107-009-0286-5.
  7. [7]C. Cartis, N. I. M. Gould, and P. L. Toint, Adaptive cubic regularisation methods for unconstrained optimization. Part II: Worst-case function- and derivative-evaluation complexity, Math. Program., 130 (2011), pp. 295–319, https://doi.org/10.1007/s10107-009-0337-y.
  8. [8]C. Cartis, N. I. M. Gould, and P. L. Toint, Evaluation complexity of adaptive cubic regularization methods for convex unconstrained optimization, Optim. Methods Softw., 27 (2012), pp. 197–219, https://doi.org/10.1080/10556788.2011.602076.
  9. [9]N. Doikov and Y. Nesterov, Gradient regularization of Newton method with Bregman distances, Math. Program., 204 (2024), pp. 1–25, https://doi.org/10.1007/s10107-023-01943-7.
  10. [10]N. I. M. Gould, S. Lucidi, M. Roma, and P. L. Toint, Solving the trust-region subproblem using the Lanczos method, SIAM J. Optim., 9 (1999), pp. 504–525, https://doi.org/10.1137/S1052623497322735.
  11. [11]S. Gratton, A. Sartenaer, and P. L. Toint, Recursive trust-region methods for multiscale nonlinear optimization, SIAM J. Optim., 19 (2008), pp. 414–444, https://doi.org/10.1137/050263012.
  12. [12]A. Griewank, The modification of Newton’s method for unconstrained optimization by bounding cubic terms, Technical Report NA/12, Department of Applied Mathematics and Theoretical Physics, University of Cambridge, Cambridge, 1981.
  13. [13]C. Gross and R. Krause, On the convergence of recursive trust-region methods for multiscale nonlinear optimization and applications to nonlinear mechanics, SIAM J. Numer. Anal., 47 (2009), pp. 3044–3069, https://doi.org/10.1137/08071819X.
  14. [14]C. P. Ho, M. Kočvara, and P. Parpas, Newton-type multilevel optimization method, Optim. Methods Softw., 37 (2022), pp. 45–78, https://doi.org/10.1080/10556788.2019.1700256.
  15. [15]R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, Cambridge, 2nd ed., 2012, https://doi.org/10.1017/CBO9780511808187.
  16. [16]V. Hovhannisyan, P. Parpas, and S. Zafeiriou, MAGMA: Multilevel accelerated gradient mirror descent algorithm for large-scale convex composite minimization, SIAM J. Imaging Sci., 9 (2016), pp. 1829–1857, https://doi.org/10.1137/15M104013X, https://doi.org/10.1137/15M104013X.
  17. [17]M. Kočvara and S. Mohammed, A first-order multigrid method for bound-constrained convex optimization, Optim. Methods Softw., 31 (2016), pp. 622–644, https://doi.org/10.1080/10556788.2016.1146267.
  18. [18]R. M. Lewis and S. G. Nash, Model problems for the multigrid optimization of systems governed by differential equations, SIAM J. Sci. Comput., 26 (2005), pp. 1811–1837, https://doi.org/10.1137/S1064827502407792.
  19. [19]K. Mishchenko, Regularized Newton method with global O(1/k²) convergence, SIAM J. Optim., 33 (2023), pp. 1440–1462, https://doi.org/10.1137/22M1488752.
  20. [20]S. G. Nash, A multigrid approach to discretized optimization problems, Optim. Methods Softw., 14 (2000), pp. 99–116, https://doi.org/10.1080/10556780008805795.
  21. [21]Y. Nesterov, Accelerating the cubic regularization of Newton’s method on convex problems, Math. Program., 112 (2008), pp. 159–181, https://doi.org/10.1007/s10107-006-0089-x.
  22. [22]Y. Nesterov, Lectures on Convex Optimization, vol. 137 of Springer Optim. Appl., Springer, Cham, 2nd ed., 2018, https://doi.org/10.1007/978-3-319-91578-4.
  23. [23]Y. Nesterov and B. T. Polyak, Cubic regularization of Newton method and its global performance, Math. Program., 108 (2006), pp. 177–205, https://doi.org/10.1007/s10107-006-0706-8.
  24. [24]R. A. Polyak, Regularized Newton method for unconstrained convex optimization, Math. Program., 120 (2009), pp. 125–145, https://doi.org/10.1007/s10107-007-0143-3.
  25. [25]N. Tsipinakis and P. Parpas, SIMBA: A scalable bilevel preconditioned gradient method for fast evasion of flat areas and saddle points, arXiv preprint arXiv:2309.05309, 2023, https://doi.org/10.48550/arXiv.2309.05309.
  26. [26]N. Tsipinakis and P. Parpas, A multilevel method for self-concordant minimization, J. Optim. Theory Appl., 203 (2024), pp. 2509–2559, https://doi.org/10.1007/s10957-024-02509-z.
  27. [27]N. Tsipinakis and P. Parpas, Multilevel regularized Newton methods with fast convergence rates, SIAM J. Sci. Comput., (2025), pp. S232–S257, https://doi.org/10.1137/24M1677307.
  28. [28]N. Tsipinakis, P. Parpas, and M. Voigt, Adaptive Multilevel Newton: A quadratically convergent optimization method, arXiv preprint arXiv:2510.24967, 2025, https://doi.org/10.48550/arXiv.2510.24967.
  29. [29]N. Tsipinakis, P. Tigas, and P. Parpas, A multilevel low-rank Newton method with super-linear convergence rate and its application to non-convex problems, Trans. Mach. Learn. Res., (2026), https://openreview.net/forum?id=PKakPzVVja.
  30. [30]Z. Wen and D. Goldfarb, A line search multigrid method for large-scale nonlinear optimization, SIAM J. Optim., 20 (2009), pp. 1478–1503, https://doi.org/10.1137/08071524X.
  31. [31]X. Zhao, P. Shi, Y. Yin, and S. K. Nguang, New results on stability of slowly switched systems: A multiple discontinuous Lyapunov function approach, IEEE Trans. Automat. Control, 62 (2017), pp. 3502–3509, https://doi.org/10.1109/TAC.2016.2614911.

Paper details

vlnc:W_bzvcc9f2
Version
v2 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 7

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

AI tools

View statement
Looking for related papers…
Contents