Cubic Regularization is the Key! The First Accelerated Quasi-Newton Method with a Global Convergence Rate of O(k^{-2}) for Convex Functions

Authors Dmitry Kamzolov, Klea Ziu, Artem Agafonov, M. Takáč

Publication date 9 February 2023

Abstract: In this paper, we propose the first Quasi-Newton method with a global convergence rate of

O (k^{- 1})

for general convex functions. Quasi-Newton methods, such as BFGS, SR-1, are well-known for their impressive practical performance. However, they may be slower than gradient descent for general convex functions, with the best theoretical rate of

O (k^{- 1 / 3})

. This gap between impressive practical performance and poor theoretical guarantees was an open question for a long period of time. In this paper, we make a significant step to close this gap. We improve upon the existing rate and propose the Cubic Regularized Quasi-Newton Method with a convergence rate of

O (k^{- 1})

. The key to achieving this improvement is to use the Cubic Regularized Newton Method over the Damped Newton Method as an outer method, where the Quasi-Newton update is an inexact Hessian approximation. Using this approach, we propose the first Accelerated Quasi-Newton method with a global convergence rate of

O (k^{- 2})

for general convex functions. In special cases where we can improve the precision of the approximation, we achieve a global convergence rate of

O (k^{- 3})

, which is faster than any first-order method. To make these methods practical, we introduce the Adaptive Inexact Cubic Regularized Newton Method and its accelerated version, which provide real-time control of the approximation error. We show that the proposed methods have impressive practical performance and outperform both first and second-order methods.

This page was built for publication: Cubic Regularization is the Key! The First Accelerated Quasi-Newton Method with a Global Convergence Rate of $O(k^{-2})$ for Convex Functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6426003)