Quasi-Newton Methods for Saddle Point Problems and Beyond

Abstract

This paper studies quasi-Newton methods for solving strongly-convex-strongly-concave saddle point problems (SPP). We propose greedy and random Broyden family updates for SPP, which have explicit local superlinear convergence rate of $\mathcal{O}\left(\right(1-\frac{1}{n{\kappa }^2}{)}^{k(k-1)/2})$, where $n$ is dimensions of the problem, $\kappa$ is the condition number and $k$ is the number of iterations. The design and analysis of proposed algorithm are based on estimating the square of indefinite Hessian matrix, which is different from classical quasi-Newton methods in convex optimization. We also present two specific Broyden family algorithms with BFGS-type and SR1-type updates, which enjoy the faster local convergence rate of $\mathcal{O}\left(\right(1-\frac{1}{n}{)}^{k(k-1)/2})$. Additionally, we extend our algorithms to solve general nonlinear equations and prove it enjoys the similar convergence rate.

We use ${\lambda }_k=\Vert \nabla f({\mathbf{z}}_k)\Vert$ as the measure for the convergence analysis in this version and fix some mistakes in the original analysis. The modification does not change the convergence rates shown in the last version.

References in corpus (4)

• Explicit Convergence Rates of Greedy and Random Quasi-Newton Methods
• Explicit Superlinear Convergence Rates of The SR1 Algorithm
• Explicit Superlinear Convergence Rates of Broyden's Methods in Nonlinear Equations
• Greedy and Random Broyden's Methods with Explicit Superlinear Convergence Rates in Nonlinear Equations