Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence
Dachao Lin, Haishan Ye, Zhihua Zhang
Abstract
In this paper, we follow Rodomanov and Nesterov’s work to study quasi-Newton methods. We focus on the common SR1 and BFGS quasi-Newton methods to establish better explicit (local) superlinear convergence rates. First, based on the greedy quasi-Newton update which greedily selects the direction to maximize a certain measure of progress, we improve the convergence rate to a condition-number-free superlinear convergence rate. Second, based on the random quasi-Newton update that selects the direction randomly from a spherically symmetric distribution, we show the same superlinear convergence rate established as above. Our analysis is closely related to the approximation of a given Hessian matrix, unconstrained quadratic objective, as well as the general strongly convex, smooth, and strongly self-concordant functions.
BibTeX
@inproceedings{
lin2021greedy,
title={Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence},
author={Dachao Lin and Haishan Ye and Zhihua Zhang},
booktitle={Advances in Neural Information Processing Systems},
editor={A. Beygelzimer and Y. Dauphin and P. Liang and J. Wortman Vaughan},
year={2021},
url={https://openreview.net/forum?id=cI4c6OpwIKq}
}