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

1. Introduction.

• Full-dimensional Hessians and linear systems can be prohibitively expensive, while multilevel methods replace them with smaller systems through lower-dimensional corrections.The paper’s methods use the classical level-selection criterion, which relies on current-iterate information rather than a trial coarse step.Source: §1 · pp. 1–2
• Prior deterministic convex multilevel Newton methods used a look-ahead condition that requires evaluating the gradient at a prospective next iterate, potentially increasing computational cost.The paper instead analyzes current-iterate level selection.Source: §1 · p. 2
• The proposed methods preserve the full-space global function-value rate for convex objectives with Lipschitz-continuous Hessians, without a fine-iteration frequency condition when restrictions are row-nested.The row-nested structure makes reduced-gradient norms monotone across levels.Source: §1 · p. 2
• Numerical experiments report convergence behavior comparable to full-space gradient-regularized Newton, with substantial computational-time reductions on large-scale instances.Row-nested hierarchies generally have more favorable convergence behavior than non-nested counterparts.Source: §1 · pp. 2–3

1.1. Related work.

• Earlier multilevel gradient-regularized Newton work established a global function-value rate for convex objectives, but required look-ahead; this paper analyzes the classical criterion without trial steps.The related-work discussion connects the analysis to row-nested restrictions and weighted-gradient techniques.Source: §1.1 · p. 3

1.2. Main assumptions and notation.

• The analysis assumes a bounded initial sublevel set, which ensures existence of a global minimizer.The paper also states a Lipschitz-Hessian assumption among its standing assumptions.Source: §1.2 · p. 3

2. The two-level Newton method with gradient regularization.

• The eligibility rule selects coarse iterations using the restricted gradient norm and a threshold; otherwise, the method performs a fine iteration.The method defines effective coarse iterations by the restricted-gradient tests and assigns the remaining iterations to the fine set.Source: §2 · p. 4

2.1. Convergence analysis.

• When every iteration is coarse, the coarse-only scheme also retains the full-space rate because each step controls the same reduced-gradient norm.This consistent quantity allows the estimates to be propagated along the sequence.Source: §2.1 · pp. 5–6
• Coarse and fine iterations control different gradient norms, so a rate for either level alone does not establish convergence for an arbitrary mixture.A coarse correction may increase the full gradient norm, but by at most a uniformly bounded factor.Source: §2.1 · pp. 6–7
• The two-level method retains the full-space global function-value rate under arbitrary switching between coarse and fine iterations.Its analysis uses a level-dependent weighted gradient measure to control transitions between the two levels.Source: §2.1 · pp. 8, 10, 11
• The weighted gradient measure provides uniform control across coarse/fine transitions, contracting on most iterations while bounding its growth on the remaining iterations.This makes uniform stability sufficient; the full gradient need not decrease at every coarse iteration.Source: §2.1 · pp. 8, 9, 11

3. The multilevel Newton method with gradient regularization.

• Algorithm 3.1 produces non-increasing function values, keeps iterates in the initial level set, and performs only finitely many coarse iterations.A coarse correction is also stable with respect to the reduced gradient.Source: §3 · pp. 11–12

3.1. Conditional rate of convergence.

• A quantitative condition on the proportion of fine-level iterations lets Algorithm 3.1 preserve the full-space method’s O(k^-2) function-value rate.Only finitely many coarse iterations can occur, so the method eventually takes only fine-level steps; the condition also limits arbitrarily long coarse-correction sequences before then.Source: §3.1 · p. 14

3.2. Row-nested restriction operators.

• Row-nested restrictions ensure that reduced-gradient norms are monotone across levels, enabling the convergence analysis to compare corrections at different coarse levels.The structure retains lower-level restriction rows at subsequent levels and implies ∥R_i v∥ ≤ ∥R_j v∥ for i < j.Source: §3.2 · p. 15

3.3. Convergence analysis using the row-nested restriction operators.

• Under the row-nested structure, Algorithm 3.1 has a convergence-rate guarantee without imposing any condition on the frequency of fine-level iterations.The analysis uses level-dependent weights and norm comparisons to control transitions among coarse and fine levels, where reduced-gradient norms need not otherwise be comparable.Source: §3.3 · p. 17
• Theorem 3.8 gives a direct convergence bound throughout the sequence, including coarse-dominated phases, independent of when the method enters the fine-only regime.The bound does not impose a condition on the frequency of fine-level iterations.Source: §3.3 · p. 20
• Row-nestedness makes reduced-gradient norms monotone across levels, enabling control of arbitrary level transitions together with level-dependent weights and uniform full-gradient stability.A coarse correction controls the reduced gradient at its current level, but not necessarily at the subsequently selected level.Source: §3.3 · p. 20
• The analysis accommodates arbitrarily long sequences of coarse corrections without prescribed fine-iteration frequency or full-gradient decrease at every coarse step.The weighted gradient measure contracts outside non-ρ-contracting iterations and has uniformly bounded growth otherwise; sufficiently frequent non-ρ-contracting iterations allow function-value decrease estimates to yield the stated rate.Source: §3.3 · p. 20

4. Experiments.

• The experiments use five MLRN coarse levels at dimensions 0.1n to 0.9n, and TLRN uses a subspace of dimension 0.5n.The non-nested MLRN restrictions select identity-matrix rows; row-nested restrictions follow Theorem 3.6.Source: §4 · p. 20

4.1. Log-sum-exp.

• For all three log-sum-exp smoothing values, row-nested MLRN and TLRN converge comparably to RN in iterations and computational time, while non-nested MLRN is substantially slower.The experiment uses a random dataset with 1,000 observations and 800 variables; the authors suggest the fine-iteration frequency condition may explain the non-nested method’s slower convergence.Source: §4.1 · p. 21, Figure 1 · p. 21

4.2. Logistic regression.

• On large Gisette and Duke logistic-regression datasets, nested MLRN and TLRN match RN’s convergence behavior and substantially reduce computational time.The comparisons report objective gap against both iterations and wall-clock time.Source: §4.2 · p. 22, Figure 2 · p. 22
• Across the a9a, Mushrooms, and w8t datasets, row-nested restriction operators significantly improve MLRN’s convergence behavior.Non-row-nested MLRN is slower on some instances and may not beat RN in computational time.Source: §4.2 · p. 22, Figure 3 · p. 23

• The paper develops and analyzes multilevel gradient-regularized Newton methods for unconstrained convex optimization, establishing a global convergence rate in function values.The supplied conclusion passage does not specify the rate’s order.Source: §5 · p. 23
• Theorem 3.8’s proof combines a weighted gradient measure with row-nested restriction operators, a structure introduced for the analysis.The authors describe these ideas as new in multilevel optimization theory.Source: §5 · p. 23
• The authors believe the analysis ideas could help establish fast convergence rates for cubic-regularized Newton and higher-order methods for convex optimization.Source: §5 · p. 24

• The appendix cites a related recurrence estimate from [22, Theorem 4.1.4].Source: Appendix A · p. 26
• Under Assumptions 1.1, 1.2, and 3.1, Algorithm 3.1 performs only finitely many coarse iterations.Source: Appendix A · p. 26
• A finite set of coarse levels gives a positive minimum decrease δ; monotone function values bounded below by f* then imply finitely many coarse iterations.Source: Appendix A · p. 27

• The proof allows the restriction operator to vary with the iteration, applying the estimates with Rk = Ri and ωi = ∥Ri∥.The cited analysis is [27, Lemma 3.2 and Corollary 3.4].Source: §A.1 · p. 27
• For iterations k ∈ Ci, the proof applies the corresponding estimates using the restriction operator Ri and its norm.Source: §A.1 · p. 27
• The resulting inequalities establish (3.2), while the proof of [27, Corollary 3.4] supplies (3.1).Source: §A.1 · p. 27

• The proof extends Case II of Theorem 2.5 to ℓ coarse levels and gives only its main steps.Source: §A.2 · p. 28
• The level indices are listed increasingly as k_0 through k_{τ−1}, with k_τ set to k.Source: §A.2 · p. 28
• For the stated coarse-level case, the argument invokes the coarse decrease estimate ω_i ≤ ζ and the bound ∥R_i∇f_{k_j}∥ ≥ σ∥∇f_{k_j}∥.Source: §A.2 · p. 28
• The proof also invokes the fine-level decrease estimate and proceeds as in Case II of Theorem 2.5.Source: §A.2 · p. 28
• The fragment defines Δ_j as f(x_{k_j}) − f* .Source: §A.2 · p. 28