Towards explicit superlinear convergence rate for SR1

DOI10.1007/S10107-022-01865-WzbMATH Open1518.90126arXiv2105.07162OpenAlexW4290068894WikidataQ114228476 ScholiaQ114228476MaRDI QIDQ6038671FDOQ6038671

Authors: Haishan Ye, Dachao Lin, Xiangyu Chang, Zhihua Zhang 

Publication date: 2 May 2023

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

Abstract: We study the convergence rate of the famous Symmetric Rank-1 (SR1) algorithm which has wide applications in different scenarios. Although it has been extensively investigated, SR1 still lacks a non-asymptotic superlinear rate compared with other quasi-Newton methods such as DFP and BFGS. In this paper we address this problem. Inspired by the recent work on explicit convergence analysis of quasi-Newton methods, we obtain the first explicit non-asymptotic rates of superlinear convergence for the vanilla SR1 methods with correction strategy to achieve the numerical stability. Specifically, the vanilla SR1 with the correction strategy achieves the rates of the form $left(frac4nln(ekappa)kight{)}^{k/2}$ for general smooth strongly-convex functions where $k$ is the iteration counter, $kappa$ is the condition number of the objective function and $n$ is the dimension of the problem. For the quadratic function, the vanilla SR1 algorithm can find the optima of the objective function at most $n$ steps.

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

Recommendations

• Rates of superlinear convergence for classical quasi-Newton methods
• Convergence of Symmetric Rank-One method based on Modified Quasi-Newton equation
• A Theoretical and Experimental Study of the Symmetric Rank-One Update
• Non-asymptotic superlinear convergence of standard quasi-Newton methods
• New results on superlinear convergence of classical quasi-Newton methods

zbMATH Keywords

quasi-Newtonsymmetric rank-oneexplicit superlinear convergence rate

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Nonlinear programming (90C30) Methods of quasi-Newton type (90C53)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• A stochastic quasi-Newton method for large-scale optimization
• A Family of Variable-Metric Methods Derived by Variational Means
• The Convergence of a Class of Double-rank Minimization Algorithms
• A new approach to variable metric algorithms
• Conditioning of Quasi-Newton Methods for Function Minimization
• The Convergence of a Class of Double-rank Minimization Algorithms 1. General Considerations
• Convergence of quasi-Newton matrices generated by the symmetric rank one update
• On the Local and Superlinear Convergence of Quasi-Newton Methods
• The superlinear convergence of a modified BFGS-type method for unconstrained optimization
• Global Convergence of a Cass of Quasi-Newton Methods on Convex Problems
• A Tool for the Analysis of Quasi-Newton Methods with Application to Unconstrained Minimization
• A stochastic quasi-Newton method for simulation response optimization
• Quasi-Newton methods for solving multiobjective optimization
• Analysis of a Symmetric Rank-One Trust Region Method
• Quasi Newton techniques generate identical points II: The proofs of four new theorems
• On the Behavior of Broyden’s Class of Quasi-Newton Methods
• Quasi-newton algorithms generate identical points
• On the Convergence of the Variable Metric Algorithm
• Randomized quasi-Newton updates are linearly convergent matrix inversion algorithms
• New results on superlinear convergence of classical quasi-Newton methods
• Rates of superlinear convergence for classical quasi-Newton methods
• Greedy quasi-Newton methods with explicit superlinear convergence
• Quasi-Newton methods for machine learning: forget the past, just sample

Cited In (3)

• Convergence of Symmetric Rank-One method based on Modified Quasi-Newton equation
• Rates of superlinear convergence for classical quasi-Newton methods
• The strict superlinear order can be faster than the infinite order

This page was built for publication: Towards explicit superlinear convergence rate for SR1

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