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

Shubhankar Agarwal, Hamzah I Khan, Sandeep P. Chinchali, David Fridovich-KeilSubmission to ICLR 2025 · Rejected

Finding saddle points—locations in a mathematical landscape that are simultaneously a minimum for one player and a maximum for another—is a critical challenge in modern machine learning and control. From training Generative Adversarial Networks (GANs) to designing robust controllers for robotics, saddle point optimization is ubiquitous.

While this problem is well-understood for "nice" functions (those that are convex-concave with known derivatives), it becomes remarkably difficult in black-box settings. In these real-world scenarios, the objective function is unknown, non-convex, non-concave, and only accessible through noisy coordinate queries. Existing methods typically stumble here; they either assume too much structural simplicity or rely on noisy gradient estimators that frequently fail to converge.

To bridge this gap, researchers have introduced a novel, Bayesian Optimization-inspired framework that requires only zeroth-order samples (function values) to efficiently locate local saddle points.

The Bayesian Saddle Point (BSP) Framework

The core contribution of this work is the Bayesian Saddle Point (BSP) algorithm, which tackles the optimization problem using a bilevel approach:

  1. The High-Level Surrogate: The algorithm uses a Gaussian Process (GP) to build a probabilistic model of the unknown objective function based on previous samples. This surrogate model provides both a predicted mean and an uncertainty estimate for any given point.
  2. The Low-Level Acquisition: Instead of simply picking the "best" point based on the mean, the algorithm frames the next step as a general-sum game played on the GP surrogate. It uses the Lower Confidence Bound (LCB) for the minimizing player and the Upper Confidence Bound (UCB) for the maximizing player. This mathematically enforces a balance between exploring highly uncertain regions and exploiting known optimal areas.
  3. The Solver: To find the Nash equilibrium of this surrogate game, the algorithm employs Newton’s Method to find the roots of the first-order optimality conditions.

A key insight of this approach is that curvature matters. Unlike standard Gradient Descent-Ascent (GDA), which only evaluates the "slope" of a landscape, using Newton's method on the GP surrogate captures second-order information. This allows the algorithm to distinguish between true saddle points and deceptive "stalling" points. Furthermore, because the GP surrogate provides a smooth estimate of the landscape, this zeroth-order method actually outperforms state-of-the-art second-order methods that rely on noisy, finite-difference gradients.

The researchers also designed several variants of the BSP algorithm to trade off between runtime and evaluation costs, such as an "Efficient" variant that takes multiple Newton steps on the surrogate model before sampling the real function, and an "Expensive" variant that samples after every single step.

Experimental Validation and Key Results

The framework was rigorously evaluated across three distinct environments: a challenging 2D decaying polynomial, a 10-dimensional polynomial, and a realistic ARIMA Tracking Model Predictive Control (MPC) robotics scenario.

The results demonstrate significant improvements over traditional methods:

  • Unprecedented Success Rates: In the 10D polynomial task, the "Explore" variant of the BSP algorithm achieved a 100% success rate in finding a true local saddle point. In stark contrast, baseline methods like GDA with finite differencing or random sampling failed completely (0% success).
  • Robustness to Noise: The BSP variants successfully converged even when function samples were corrupted by noise. Traditional gradient-based methods often wandered off or left the feasible region entirely under the same conditions.
  • Real-World Impact: In the ARIMA-MPC experiment—where a "protagonist" controller tries to track a signal while an "antagonist" process generates difficult-to-track noise—the robust parameters discovered by the BSP algorithm resulted in a 27.6% lower tracking cost on out-of-distribution data compared to a standard nominal controller.
  • Sample Efficiency: The "Efficient" variants of the algorithm required significantly fewer expensive real-world function evaluations to reach convergence.

Limitations and Future Directions

While highly effective, the framework does have limitations. Chief among them is the "curse of dimensionality." Gaussian Processes typically struggle as the number of dimensions scales up. While the authors demonstrated strong success up to 10 dimensions, scaling this exact approach to the hundreds or thousands of dimensions seen in deep learning remains an open challenge.

Additionally, the framework is explicitly designed to find local saddle points; locating the global best saddle point in a highly non-convex landscape remains notoriously difficult. Finally, the current algorithm finds a candidate point and verifies its second-order stability post-hoc. Future work could integrate these second-order constraints directly into the low-level game solver, potentially yielding even greater 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, showcasing their ability to efficiently locate local saddle points in these contexts.
BibTeX
@misc{agarwal2025framework,
  author = {Shubhankar Agarwal and Hamzah I 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