Multilevel Newton methods speed up convex optimization with low cost
Global $\mathcal{O}\left(k^{-2}\right)$ Convergence of Multilevel Gradient-Regularized Newton Methods
Machine Learning
Summary
Optimizing functions can take a lot of computer power, especially for big problems. The authors improve a type of optimization method by doing parts of its work in smaller, simpler steps. They prove this still converges quickly to the best solution and show with examples that their method works well while needing less computing time. This helps make solving large optimization problems more practical.
What this means in practice
- •For machine learning engineers: Accelerate training of large models by using faster second-order optimization methods with reduced computational cost.
- •For computational physicists: Solve large-scale convex energy minimization problems more efficiently by applying multilevel Newton corrections.
Authors
Nick Tsipinakis, Matthias Voigt
Abstract
We develop and analyze multilevel gradient-regularized Newton methods for unconstrained convex optimization with Lipschitz-continuous Hessians. By computing Newton corrections in lower-dimensional subspaces, the proposed methods aim to reduce computational costs while preserving the global $\mathcal{O}\left(k^{-2}\right)$ convergence rate in function values of the full-space method. To establish this rate for multilevel methods, we introduce a class of row-nested restriction operators that ensures monotonicity of the reduced-gradient norms across levels. Numerical experiments with row-nested operators demonstrate convergence behavior comparable to full-space gradient-regularized Newton, while offering substantial computational savings on large-scale instances.