Quasi-Newton Methods for Saddle Point Problems

This paper studies quasi-Newton methods for strongly-convex-strongly-concave saddle point problems. We propose random Broyden family updates, which have explicit local superlinear convergence rate of O((1 -1/(dκ 2 )) k(k-1)/2 ), where d is the dimension of the problem, κ 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 O((1 -1/d) k(k-1)/2 ). Our numerical experiments show proposed algorithms outperform classical first-order methods.