Accelerated Adaptive Cubic Regularized Quasi-Newton Methods

Dmitry Kamzolov (), Klea Ziu (), Artem Agafonov () and Martin Takáč ()
Additional contact information
Dmitry Kamzolov: MBZUAI (Mohamed bin Zayed University of Artificial Intelligence)
Klea Ziu: MBZUAI (Mohamed bin Zayed University of Artificial Intelligence)
Artem Agafonov: MBZUAI (Mohamed bin Zayed University of Artificial Intelligence)
Martin Takáč: MBZUAI (Mohamed bin Zayed University of Artificial Intelligence)

Journal of Optimization Theory and Applications, 2026, vol. 208, issue 1, No 27, 46 pages

Abstract: Abstract In this paper, we propose the first Quasi-Newton method with a global convergence rate of $$O(k^{-1})$$ O ( k - 1 ) for general convex functions. Quasi-Newton methods, such as BFGS and SR-1, are well-known for their impressive practical performance. However, they are theoretically slower than gradient descent for general convex functions. 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}})$$ 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}})$$ O ( k - 2 ) for general convex functions. In special cases where we have access to additional computations, for example, Hessian-vector products, we can improve the inexact Hessian approximation and achieve a global convergence rate of $$O({k^{-3}})$$ O ( k - 3 ) , which makes it intermediate second-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.

Keywords: Quasi-Newton Methods; Second-order methods; Optimization; Cubic Newton Method; High-order methods; BFGS; 90C25; 90C53; 90C06; 65K05; 49M15 (search for similar items in EconPapers)
Date: 2026
References: Add references at CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10957-025-02804-3 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:joptap:v:208:y:2026:i:1:d:10.1007_s10957-025-02804-3

Ordering information: This journal article can be ordered from
http://www.springer. ... cs/journal/10957/PS2

DOI: 10.1007/s10957-025-02804-3

Access Statistics for this article

Journal of Optimization Theory and Applications is currently edited by Franco Giannessi and David G. Hull

More articles in Journal of Optimization Theory and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().