Non-asymptotic superlinear convergence of standard quasi-Newton methods

DOI10.1007/S10107-022-01887-4zbMATH Open1519.90171arXiv2003.13607OpenAlexW3013599873WikidataQ114228402 ScholiaQ114228402MaRDI QIDQ6044985FDOQ6044985

Authors: Qiujiang Jin, Aryan Mokhtari 

Publication date: 25 May 2023

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

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.

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

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

zbMATH Keywords

quasi-Newton methodBFGS algorithmsuperlinear convergence rateDFP algorithmnon-asymptotic analysis

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (8)

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

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)