Quasi-Newton Methods for Saddle Point Problems

We propose random Broyden family updates, which have explicit local superlinear convergence rate of {\mathcal O}\big(\big(1-1/(d\varkappa 2)\big) {k(k-1)/2}\big), where d is the dimension of the problem, \varkappa 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\big(\big(1-1/d\big) {k(k-1)/2}\big) . Our numerical experiments show proposed algorithms outperform classical first-order methods.