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

Shubhankar Agarwal, Hamzah Khan, Sandeep P. Chinchali, David Fridovich-Keil

Abstract

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.

Introduction

Saddle point optimization is a cornerstone of modern machine learning and control, underpinning applications from Generative Adversarial Networks (GANs) to robust robotics and financial portfolio management. In these two-player zero-sum games, the goal is to find a state where neither player can improve their position—a saddle point. However, traditional optimization techniques often rely on two restrictive assumptions: the objective function must be convex-concave, and its gradients must be accessible.

In many real-world "black-box" scenarios, the underlying function is unknown, non-convex, and non-concave, and we can only observe noisy samples of its output. Researchers from UT Austin have introduced the Bayesian Saddle Point (BSP) framework to address these challenges, identifying stable equilibria in complex environments using only noisy function samples—no gradients required.

Methodology: The Bayesian Saddle Point (BSP) Framework

The BSP algorithm treats the optimization problem as a bilevel process designed to navigate unknown landscapes efficiently:

  • High-Level Surrogate Modeling: The algorithm employs Gaussian Processes (GPs) to construct a probabilistic model of the unknown black-box function. This surrogate model provides both a predicted value and a measure of uncertainty (variance) across the strategy space.
  • Low-Level Search Strategy: Instead of simple random sampling, the algorithm identifies the next sample point by solving a surrogate general-sum game. By allowing each player to optimize their own confidence bound—the Lower Confidence Bound (LCB) for the minimizer and the Upper Confidence Bound (UCB) for the maximizer—the framework naturally balances exploration (reducing uncertainty) and exploitation (refining candidate equilibria).
  • Root-Finding: Candidate saddle points are identified within the surrogate model using a modified Newton’s method to locate points where the gradients of the surrogate vanish, effectively identifying candidate Local Saddle Points (LSPs).

Experimental Evaluation

The authors evaluated the BSP framework across three diverse benchmarks:

  1. Decaying Polynomial (2D): A synthetic landscape designed to trap standard algorithms in "spurious" saddle points. This test demonstrated that while gradient-based methods stall as slopes become flat, the GP-based approach maintains a global view.
  2. High-Dimension Polynomial (10D): A complex sixth-order polynomial used to test scalability in higher dimensions.
  3. ARIMA Tracking MPC (4D): A robotics scenario involving a Model Predictive Controller (MPC) tracking a signal against an adversarial forecaster.

Key Results and Insights

The BSP framework demonstrated significant improvements over existing methods in both success rate and robustness:

  • Superior Success Rates: In the 10D polynomial task, the "Efficient-Exploit" variant achieved a 100% success rate in locating the saddle point. Remarkably, it outperformed Local Symplectic Surgery (LSS), a state-of-the-art method that requires gradient access, which BSP does not.
  • Robustness in Control: In the ARIMA-MPC robotics experiment, the parameters identified by BSP resulted in a controller with a 27.6% lower mean cost on out-of-distribution data compared to a nominal controller.
  • Uncertainty as a Guide: The framework highlights that in black-box settings, the most valuable point to sample is often the one that most effectively reduces uncertainty surrounding the equilibrium, rather than just the current predicted optimum.

Conclusion and Future Work

The BSP framework provides a robust, derivative-free approach to finding local saddle points in complex black-box environments. While Gaussian Processes face scaling challenges in very high-dimensional spaces (the "curse of dimensionality"), the integration of uncertainty-guided search offers a powerful tool for robust optimization. Future work will explore scaling to higher dimensions and directly incorporating second-order sufficient conditions into the search process to further enhance stability and efficiency.

Summary updated

Abstract

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.
BibTeX
@misc{agarwal2025framework,
  author = {Shubhankar Agarwal and Hamzah Khan and Sandeep P. Chinchali and David Fridovich-Keil},
  title = {{A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games}},
  year = {2025},
  eprint = {2503.18224},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2503.18224},
}
Figure