Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence
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.
Cite
Text
Lin et al. "Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence." Neural Information Processing Systems, 2021.Markdown
[Lin et al. "Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence." Neural Information Processing Systems, 2021.](https://mlanthology.org/neurips/2021/lin2021neurips-greedy/)BibTeX
@inproceedings{lin2021neurips-greedy,
title = {{Greedy and Random Quasi-Newton Methods with Faster Explicit Superlinear Convergence}},
author = {Lin, Dachao and Ye, Haishan and Zhang, Zhihua},
booktitle = {Neural Information Processing Systems},
year = {2021},
url = {https://mlanthology.org/neurips/2021/lin2021neurips-greedy/}
}