# Multiple Greedy Quasi-Newton Methods for Saddle Point Problems

arXiv: https://arxiv.org/abs/2408.00241 · HTML: https://mlsanity.com/paper/2408.00241/

## Key facts

- Cited by 3 papers in the map (data through 14 Oct 2026).
- Builds on 33 of its 62 references that are in the map.
- First posted on arXiv 1 Aug 2024.

## Builds on (most cited first, 30 of 33)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Minimax Regret Bounds for Reinforcement Learning](https://mlsanity.com/paper/1703.05449/) (2017)
- [Training GANs with Optimism](https://mlsanity.com/paper/1711.00141/) (2017)
- [Model-Based Reinforcement Learning with a Generative Model is Minimax Optimal](https://mlsanity.com/paper/1906.03804/) (2019)
- [Reducing Noise in GAN Training with Variance Reduced Extragradient](https://mlsanity.com/paper/1904.08598/) (2019)
- [Stochastic Variance Reduction Methods for Saddle-Point Problems](https://mlsanity.com/paper/1605.06398/) (2016)
- [Nearly Minimax Optimal Reinforcement Learning for Linear Markov Decision Processes](https://mlsanity.com/paper/2212.06132/) (2022)
- [Stochastic Variance Reduction for Variational Inequality Methods](https://mlsanity.com/paper/2102.08352/) (2021)
- [Greedy Quasi-Newton Methods with Explicit Superlinear Convergence](https://mlsanity.com/paper/2002.00657/) (2020)
- [Non-asymptotic Superlinear Convergence of Standard Quasi-Newton Methods](https://mlsanity.com/paper/2003.13607/) (2020)
- [Higher-order methods for convex-concave min-max optimization and monotone variational inequalities](https://mlsanity.com/paper/2007.04528/) (2020)
- [Near Optimal Stochastic Algorithms for Finite-Sum Unbalanced Convex-Concave Minimax Optimization](https://mlsanity.com/paper/2106.01761/) (2021)
- [Generalized Optimistic Methods for Convex-Concave Saddle Point Problems](https://mlsanity.com/paper/2202.09674/) (2022)
- [Minimax AUC Fairness: Efficient Algorithm with Provable Convergence](https://mlsanity.com/paper/2208.10451/) (2022)
- [New Results on Superlinear Convergence of Classical Quasi-Newton Methods](https://mlsanity.com/paper/2004.14866/) (2020)
- [Rates of superlinear convergence for classical quasi-Newton methods](https://mlsanity.com/paper/2003.09174/) (2020)
- [On Accelerated Methods for Saddle-Point Problems with Composite Structure](https://mlsanity.com/paper/2103.09344/) (2021)
- [Efficient Algorithms for Empirical Group Distributionally Robust Optimization and Beyond](https://mlsanity.com/paper/2403.03562/) (2024)
- [Quasi-Newton Methods for Saddle Point Problems and Beyond](https://mlsanity.com/paper/2111.02708/) (2021)
- [Optimal Methods for Higher-Order Smooth Monotone Variational Inequalities](https://mlsanity.com/paper/2205.06167/) (2022)
- [Near-Minimax-Optimal Distributional Reinforcement Learning with a Generative Model](https://mlsanity.com/paper/2402.07598/) (2024)
- [A Stochastic Proximal Point Algorithm for Saddle-Point Problems](https://mlsanity.com/paper/1909.06946/) (2019)
- [Universal Tensor Methods for Monotone Variational Inequalities](https://mlsanity.com/paper/2212.07824/) (2022)
- [Explicit Convergence Rates of Greedy and Random Quasi-Newton Methods](https://mlsanity.com/paper/2104.08764/) (2021)
- [Perseus: A Simple and Optimal High-Order Method for Variational Inequalities](https://mlsanity.com/paper/2205.03202/) (2022)
- [A Distributed Quasi-Newton Algorithm for Empirical Risk Minimization with Nonsmooth Regularization](https://mlsanity.com/paper/1803.01370/) (2018)
- [Fairness-aware Regression Robust to Adversarial Attacks](https://mlsanity.com/paper/2211.04449/) (2022)
- [Explicit Superlinear Convergence Rates of The SR1 Algorithm](https://mlsanity.com/paper/2105.07162/) (2021)
- [A structured L-BFGS method and its application to inverse problems](https://mlsanity.com/paper/2310.07296/) (2023)
- [An implicit gradient-descent procedure for minimax problems](https://mlsanity.com/paper/1906.00233/) (2019)

## Built on by (most cited first, 3 of 3)

- [Adaptive Self-Supervised Learning Strategies for Dynamic On-Device LLM Personalization](https://mlsanity.com/paper/2409.16973/) (2024)
- [Electroencephalogram Emotion Recognition via AUC Maximization](https://mlsanity.com/paper/2408.08979/) (2024)
- [Structural shifts in institutional participation and collaboration within the AI arXiv preprint research ecosystem](https://mlsanity.com/paper/2602.03969/) (2026)

## Abstract (arXiv)

This paper introduces the Multiple Greedy Quasi-Newton (MGSR1-SP) method, a novel approach to solving strongly-convex-strongly-concave (SCSC) saddle point problems. Our method enhances the approximation of the squared indefinite Hessian matrix inherent in these problems, significantly improving both stability and efficiency through iterative greedy updates. We provide a thorough theoretical analysis of MGSR1-SP, demonstrating its linear-quadratic convergence rate. Numerical experiments conducted on AUC maximization and adversarial debiasing problems, compared with state-of-the-art algorithms, underscore our method's enhanced convergence rate. 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.