Symmetric Rank-k Methods

2023/03/28 by Chengchang Liu, Cheng Chen, Liu, Chengchang +3 · 1 citation
Computer Science · Engineering · Mathematics · #Advanced Optimization Algorithms Research #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques #math.OC

paper · pdf · doi:10.48550/arxiv.2303.16188

openalex publication_date 2023/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper proposes a novel class of block quasi-Newton methods for convex optimization which we call symmetric rank-k (SR-k) methods. Each iteration of SR-k incorporates the curvature information with~k Hessian-vector products achieved from the greedy or random strategy. We prove that SR-k methods have the local superlinear convergence rate of O((1-k/d)^t(t-1)/2) for minimizing smooth and strongly convex function, where d is the problem dimension and t is the iteration counter. This is the first explicit superlinear convergence rate for block quasi-Newton methods, and it successfully explains why block quasi-Newton methods converge faster than ordinary quasi-Newton methods in practice. We also leverage the idea of SR-k methods to study the block BFGS and block DFP methods, showing their superior convergence rates.

Citations

• On the limited memory BFGS method for large scale optimization
• Conditioning of quasi-Newton methods for function minimization

Cited by

• Explicit Global Convergence Rates of BFGS without Line Search

Related

• Explicit Superlinear Convergence Rates of The SR1 Algorithm
• Simple Stepsize for Quasi-Newton Methods with Global Convergence Guarantees
• Explicit Convergence Rates of Greedy and Random Quasi-Newton Methods
• Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates
• Quasi-Newton Methods: Superlinear Convergence Without Line Searches for Self-Concordant Functions