Non-asymptotic superlinear convergence of standard quasi-Newton methods

DOI10.1007/S10107-022-01887-4MaRDI QIDQ6044985zbMATH OpenOpenAlexWikidataFDO

Authors Qiujiang Jin, Aryan Mokhtari

Publication date 25 May 2023

Published in Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/2003.13607

zbMATH Keywords

quasi-Newton methodBFGS algorithmsuperlinear convergence rateDFP algorithmnon-asymptotic analysis

Mathematics Subject Classification ID

Convex programming (90C25) Methods of quasi-Newton type (90C53)

Abstract: In this paper, we study and prove the non-asymptotic superlinear convergence rate of the Broyden class of quasi-Newton algorithms which includes the Davidon--Fletcher--Powell (DFP) method and the Broyden--Fletcher--Goldfarb--Shanno (BFGS) method. The asymptotic superlinear convergence rate of these quasi-Newton methods has been extensively studied in the literature, but their explicit finite-time local convergence rate is not fully investigated. In this paper, we provide a finite-time (non-asymptotic) convergence analysis for Broyden quasi-Newton algorithms under the assumptions that the objective function is strongly convex, its gradient is Lipschitz continuous, and its Hessian is Lipschitz continuous at the optimal solution. We show that in a local neighborhood of the optimal solution, the iterates generated by both DFP and BFGS converge to the optimal solution at a superlinear rate of $(1/k{)}^{k/2}$, where $k$ is the number of iterations. We also prove a similar local superlinear convergence result holds for the case that the objective function is self-concordant. Numerical experiments on several datasets confirm our explicit convergence rate bounds. Our theoretical guarantee is one of the first results that provide a non-asymptotic superlinear convergence rate for quasi-Newton methods.

Recommendations

• On superlinear convergence of quasi-Newton methods for nonsmooth equations
• Superlinear convergence of smoothing quasi-Newton methods for nonsmooth equations
• scientific article; zbMATH DE number 799618
• New results on superlinear convergence of classical quasi-Newton methods
• Rates of superlinear convergence for classical quasi-Newton methods
• LOCAL AND SUPERLINEAR CONVERGENCE OF STRUCTURED QUASI-NEWTON METHODS FOR NONLINEAR OPTIMIZATION
• Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions
• Publication:4937582
• scientific article; zbMATH DE number 943285

Cites work

• scientific article; zbMATH DE number 3790208 (Why is no real title available?)
• scientific article; zbMATH DE number 729680 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• scientific article; zbMATH DE number 5060482 (Why is no real title available?)
• scientific article; zbMATH DE number 3381785 (Why is no real title available?)
• A Characterization of Superlinear Convergence and Its Application to Quasi-Newton Methods
• A Class of Methods for Solving Nonlinear Simultaneous Equations
• A Family of Variable-Metric Methods Derived by Variational Means
• A Globally and Superlinearly Convergent Gauss--Newton-Based BFGS Method for Symmetric Nonlinear Equations
• A Modified BFGS Algorithm for Unconstrained Optimization
• A Rapidly Convergent Descent Method for Minimization
• A new approach to variable metric algorithms
• Conditioning of Quasi-Newton Methods for Function Minimization
• Convergence of quasi-Newton matrices generated by the symmetric rank one update
• Convergence theory for the structured BFGS secant method with an application to nonlinear least squares
• Cubic regularization of Newton method and its global performance
• Global Convergence of a Cass of Quasi-Newton Methods on Convex Problems
• Global and superlinear convergence of a restricted class of self-scaling methods with inexact line searches, for convex functions
• Greedy quasi-Newton methods with explicit superlinear convergence
• IQN: an incremental quasi-Newton method with local superlinear convergence rate
• Introductory lectures on convex optimization. A basic course.
• Local and superlinear convergence of quasi-Newton methods based on modified secant conditions
• Local convergence analysis for partitioned quasi-Newton updates
• New results on superlinear convergence of classical quasi-Newton methods
• On the Convergence of the Variable Metric Algorithm
• On the Global Convergence of Broyden's Method
• On the Local and Superlinear Convergence of Quasi-Newton Methods
• On the limited memory BFGS method for large scale optimization
• Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions
• Rates of superlinear convergence for classical quasi-Newton methods
• Some Convergence Properties of Broyden’s Method
• The Convergence of Single-Rank Quasi-Newton Methods
• Trust Region Methods
• Updating Quasi-Newton Matrices with Limited Storage
• Variable Metric Method for Minimization

Cited in

(8)

• On the Characterization of q-Superlinear Convergence of Quasi-Newton Methods for Constrained Optimization
• Greedy quasi-Newton methods with explicit superlinear convergence
• Quasi-Newton methods: superlinear convergence without line searches for self-concordant functions
• New results on superlinear convergence of classical quasi-Newton methods
• Towards explicit superlinear convergence rate for SR1
• An approach for analyzing the global rate of convergence of quasi-Newton and truncated-Newton methods
• Rates of superlinear convergence for classical quasi-Newton methods
• Hessian averaging in stochastic Newton methods achieves superlinear convergence

This page was built for publication: Non-asymptotic superlinear convergence of standard quasi-Newton methods

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