Multilevel regularized Newton methods with fast convergence rates
File(s)
Accepted version
Author(s)
Tsipinakis, Nick
Parpas, Panos
Type
Journal Article
Abstract
We introduce new multilevel methods for solving large-scale unconstrained optimization problems. Specifically, the philosophy of multilevel methods is applied to Newton-type methods that regularize the Newton subproblem using second-order information from a coarse (low dimensional) subproblem. The new regularized multilevel methods provably converge from any initialization point and enjoy faster convergence rates than gradient descent. In particular, for arbitrary functions with Lipschitz continuous Hessians, we show that their convergence rate interpolates between the rate of gradient descent and that of the cubic Newton method. If, additionally, the objective function is assumed to be convex, then the proposed method converges with the fast O(𝑘−2) rate. Hence, since the updates are generated using a coarse model in low dimensions, the theoretical results of this paper significantly speed up the convergence of Newton-type or preconditioned gradient methods in practical applications. Preliminary numerical results suggest that the proposed multilevel algorithms are significantly faster than current state-of-the-art methods.
Date Issued
2025-09-01
Date Acceptance
2025-04-02
Citation
SIAM Journal on Scientific Computing, 2025, SPECIAL SECTION Copper Mountain 2024, pp.S232-S257
ISSN
1064-8275
Publisher
Society for Industrial and Applied Mathematics
Start Page
S232
End Page
S257
Journal / Book Title
SIAM Journal on Scientific Computing
Volume
SPECIAL SECTION Copper Mountain 2024
Copyright Statement
Copyright © 2025 Society for Industrial and Applied Mathematics. This is the author’s accepted manuscript made available under a CC-BY licence in accordance with Imperial’s Research Publications Open Access policy (www.imperial.ac.uk/oa-policy)
License URL
Publication Status
Published
Date Publish Online
2025-08-13