Quasi-Newton Methods for Saddle Point Problems

This paper introduces the Multiple Greedy Quasi-Newton (MGSR1-SP) method, a novel approach designed to solve strongly-convex-strongly-concave (SCSC) saddle point problems. Our method enhances the approximation of the square of the indefinite Hessian matrix inherent in these problems, significantly improving both the accuracy and efficiency through iterative greedy updates. We provide a thorough theoretical analysis of MGSR1-SP, demonstrating its linear-quadratic convergence properties. Numerical experiments conducted on AUC maximization and adversarial debiasing problems, compared with stateof-the-art algorithms, underscore our method's enhanced convergence rates and superior quality in inverse Hessian estimation. These results affirm the potential of MGSR1-SP to improve performance across a broad spectrum of machine learning applications where efficient and accurate Hessian approximations are crucial.