# A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games

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

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 25 of its 51 references that are in the map.
- First posted on arXiv 23 Mar 2025.

## Builds on (most cited first, 25 of 25)

- [Generative Adversarial Networks](https://mlsanity.com/paper/2203.00667/) (2022)
- [Differentiable Convex Optimization Layers](https://mlsanity.com/paper/1910.12430/) (2019)
- [Identifying and attacking the saddle point problem in high-dimensional non-convex optimization](https://mlsanity.com/paper/1406.2572/) (2014)
- [The Mechanics of n-Player Differentiable Games](https://mlsanity.com/paper/1802.05642/) (2018)
- [The Numerics of GANs](https://mlsanity.com/paper/1705.10461/) (2017)
- [Gaussian Processes for Data-Efficient Learning in Robotics and Control](https://mlsanity.com/paper/1502.02860/) (2015)
- [Reinforcement Learning for Non-Stationary Markov Decision Processes: The Blessing of (More) Optimism](https://mlsanity.com/paper/2006.14389/) (2020)
- [Adversarially Robust Optimization with Gaussian Processes](https://mlsanity.com/paper/1810.10775/) (2018)
- [On Gradient-Based Learning in Continuous Games](https://mlsanity.com/paper/1804.05464/) (2018)
- [On Finding Local Nash Equilibria (and Only Local Nash Equilibria) in Zero-Sum Games](https://mlsanity.com/paper/1901.00838/) (2019)
- [Machine learning for electronically excited states of molecules](https://mlsanity.com/paper/2007.05320/) (2020)
- [Local Saddle Point Optimization: A Curvature Exploitation Approach](https://mlsanity.com/paper/1805.05751/) (2018)
- [Noisy-Input Entropy Search for Efficient Robust Bayesian Optimization](https://mlsanity.com/paper/2002.02820/) (2020)
- [On the Characterization of Local Nash Equilibria in Continuous Games](https://mlsanity.com/paper/1411.2168/) (2014)
- [Zeroth-Order Algorithms for Nonconvex Minimax Problems with Improved Complexities](https://mlsanity.com/paper/2001.07819/) (2020)
- [On the saddle point problem for non-convex optimization](https://mlsanity.com/paper/1405.4604/) (2014)
- [Saddle-point dynamics: conditions for asymptotic stability of saddle points](https://mlsanity.com/paper/1510.02145/) (2015)
- [Zeroth-Order Methods for Convex-Concave Minmax Problems: Applications to Decision-Dependent Risk Minimization](https://mlsanity.com/paper/2106.09082/) (2021)
- [Approximating Nash Equilibria in Normal-Form Games via Stochastic Optimization](https://mlsanity.com/paper/2310.06689/) (2023)
- [Game Theory for Multi-Access Edge Computing: Survey, Use Cases, and Future Trends](https://mlsanity.com/paper/1704.00323/) (2017)
- [Distributed saddle point problems for strongly concave-convex functions](https://mlsanity.com/paper/2202.05812/) (2022)
- [No-Regret Learning of Nash Equilibrium for Black-Box Games via Gaussian Processes](https://mlsanity.com/paper/2405.08318/) (2024)
- [Robust Forecasting for Robotic Control: A Game-Theoretic Approach](https://mlsanity.com/paper/2209.10802/) (2022)
- [Robust Bond Portfolio Construction via Convex-Concave Saddle Point Optimization](https://mlsanity.com/paper/2212.02570/) (2022)
- [Second-Order Algorithms for Finding Local Nash Equilibria in Zero-Sum Games](https://mlsanity.com/paper/2406.03565/) (2024)

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

- [EXOTIC: An Exact, Optimistic, Tree-Based Algorithm for Min-Max Optimization](https://mlsanity.com/paper/2508.12479/) (2025)

## Abstract (arXiv)

Saddle point optimization is a critical problem employed in numerous real-world applications, including portfolio optimization, generative adversarial networks, and robotics. It has been extensively studied in cases where the objective function is known and differentiable. Existing work in black-box settings with unknown objectives that can only be sampled either assumes convexity-concavity in the objective to simplify the problem or operates with noisy gradient estimators. In contrast, we introduce a framework inspired by Bayesian optimization which utilizes Gaussian processes to model the unknown (potentially nonconvex-nonconcave) objective and requires only zeroth-order samples. Our approach frames the saddle point optimization problem as a two-level process which can flexibly integrate existing and novel approaches to this problem. The upper level of our framework produces a model of the objective function by sampling in promising locations, and the lower level of our framework uses the existing model to frame and solve a general-sum game to identify locations to sample. This lower level procedure can be designed in complementary ways, and we demonstrate the flexibility of our approach by introducing variants which appropriately trade off between factors like runtime, the cost of function evaluations, and the number of available initial samples. We experimentally demonstrate these algorithms on synthetic and realistic datasets in black-box nonconvex-nonconcave settings, showcasing their ability to efficiently locate local saddle points in these contexts.