Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates
Abstract
We consider the finite-sum optimization problem, where each component function is strongly convex and has Lipschitz continuous gradient and Hessian. The recently proposed incremental quasi-Newton method is based on BFGS update and achieves a local superlinear convergence rate that is dependent on the condition number of the problem. This paper proposes a more efficient quasi-Newton method by incorporating the symmetric rank-1 update into the incremental framework, which results in the condition-number-free local superlinear convergence rate. Furthermore, we can boost our method by applying the block update on the Hessian approximation, which leads to an even faster local convergence rate. The numerical experiments show the proposed methods significantly outperform the baseline methods.
Cite
Text
Liu et al. "Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates." AAAI Conference on Artificial Intelligence, 2024. doi:10.1609/AAAI.V38I13.29319Markdown
[Liu et al. "Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates." AAAI Conference on Artificial Intelligence, 2024.](https://mlanthology.org/aaai/2024/liu2024aaai-incremental/) doi:10.1609/AAAI.V38I13.29319BibTeX
@inproceedings{liu2024aaai-incremental,
title = {{Incremental Quasi-Newton Methods with Faster Superlinear Convergence Rates}},
author = {Liu, Zhuanghua and Luo, Luo and Low, Bryan Kian Hsiang},
booktitle = {AAAI Conference on Artificial Intelligence},
year = {2024},
pages = {14097-14105},
doi = {10.1609/AAAI.V38I13.29319},
url = {https://mlanthology.org/aaai/2024/liu2024aaai-incremental/}
}