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

Authors: Shubhankar Agarwal, Hamzah I Khan, Sandeep P. Chinchali, David Fridovich-Keil
Primary area: optimization
Keywords: black box optimization, zero sum games, saddle points, Bayesian optimization

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.

Decision: reject
Reviewer scores: 6, 5, 6

Reviews and discussion:
<thread>
creation date:
1729212865359

thread_type:
official_review

<thread_object>
creator: reviewer_euuw

<content>
summary:
This paper presents a novel framework for finding local saddle points in two-player zero-sum black-box games. The authors propose a bilevel approach that combines Gaussian processes to model the unknown, nonconvex-nonconcave objective and a lower-level game to identify sampling locations.

strengths:
1. The framework innovatively combines ideas from Bayesian optimization with saddle point optimization in a black-box setting. It offers a zeroth-order technique for finding saddle points.
2. The explanation of the bilevel optimization framework is well-organized. 
3. The ability to identify saddle points in nonconvex-nonconcave black-box settings is highly relevant for a wide range of applications, particularly those involving adversarial dynamics and game theory.
4. The experimental results are comprehensive, and the ablation studies have been conducted.

weaknesses:
1. The theoretical guarantees of the algorithm in this paper are somewhat insufficient, with only Lemma 4.1 used to show that the algorithm converges to a local Nash point, and the assumptions made are rather strong.
2. The paper lacks a dedicated "Related Work" section. It appears that the related work has been split into two parts, placed separately in Section 1 and Section 2.

questions:
1. Could you provide more theoretical analysis of the algorithm? The current analysis is somewhat limited, and there is no discussion on the rationale behind the assumptions in Lemma 4.1. Please offer an explanation here.
2. I suggest reorganizing Section 1 and Section 2. The current structure is somewhat disorganized and lacks a systematic introduction to prior work.
3. How to incorporate second-order sufficient conditions to enhance the performance of your approach? Please gives further explanation.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730172336314

thread_type:
official_review

<thread_object>
creator: reviewer_c6cc

<content>
summary:
The paper studies the problem of finding local saddle point in two-player zero-sum games, in which the objective function is unknown and can only be accessed through zeroth-order samples. The authors approach the problem through Bayesian optimization, introducing a bi-level optimization algorithm where the lower-level solves a general-sum game and upper level uses Gaussian processes to build a surrogate model for the objective. The authors illustrate the algorithm performance through numerical simulations.

strengths:
The paper targets an important problem, which is to solve two-player zero-sum games in the general nonconvex-nonconcave setting with only zeroth-order samples. The introduction and description the algorithm makes general sense. The numerical simulation verifies the algorithm performance to a certain extent.

weaknesses:
My main concern is that the authors do not provide sufficient understandings for the proposed algorithm either in theory or through experiments.

The paper lacks rigorous mathematical justification, and the explanation on why the proposed algorithm is expected to work is made in a very hand-wavy manner. Most existing works on two-player zero-sum games come with end-to-end analysis on convergence rate/sample complexity. Rigorous theoretical results allow us to judge algorithms in terms of efficiency, restrictiveness of assumptions, etc. Without such theoretical results, it is hard to compare the proposed algorithm with those in the existing literature and those to be introduced in the future.

Regarding the takeaways highlighted in line 478-510 -- this is a plausible explanation that matches the observation from a few small-scale experiments. Much more extensive experiments need to be conducted to verify the statement. In the absence of theoretical convergence guarantees, systematic numerical simulations are especially important for understanding the algorithm performance, but they are currently missing.

questions:
Minor comments:

1) The phrasing of the abstract and introduction line 043-046 gives the impression that the authors consider $f$ which is not necessarily differentiable. However, it turned out later a second-order differentiability assumption is needed. The abstract and introduction should be revised for better clarity.

2) In Algorithm 1 line 4 and Algorithm 2 line 7, you are not returning $\bar{x}^*,\bar{y}^*$/$x^*,y^*$. You are returning the iterates as an estimate of $\bar{x}^*,\bar{y}^*$/$x^*,y^*$.
</content>
</thread_object>

</thread>
<thread>
creation date:
1730696395004

thread_type:
official_review

<thread_object>
creator: reviewer_gbje

<content>
summary:
This paper proposes a new framework for finding local saddle points in zeroth-order black-box saddle point optimization. 
The authors propose a bilevel framework inspired by Bayesian Optimization (BO) that leverages Gaussian Processes (GPs) to model the unknown objective function. The lower-level game uses confidence bounds from the GP to define a general-sum game, the solution of which (a local Nash point) is used to guide sampling of the objective function. The high-level game updates the GP model with the new samples and iteratively searches for a local saddle point. The empirical results show that BSP variants outperform baseline approaches like naive random sampling and zeroth-order gradient descent-ascent on these problems.

strengths:
This paper addresses a problem that has received limited attention in the literature: the optimization of black-box games. It introduces a novel framework that combines a diverse set of techniques to tackle this challenge, making it a noteworthy contribution.

weaknesses:
- Limitations of modeling with GP: We know that the required number of samples to accurately model the objective function grows exponentially, leading to increased computational complexity and potentially reduced accuracy. Do you plan to address this limitation in future work?
- The experiments are ultimately not convincing: while the experiments on synthetic data successfully achieve the optimal merit function, the real-world examples are less successful compared to the only other baseline and require further improvement.
- Lack of sufficient theoretical guarantees for the method: While Lemma 4.1 demonstrates the convergence of LLGAME to a Local Nash Point (LNP), the paper lacks a theoretical analysis proving the convergence of the overall Bayesian Saddle Point (BSP) algorithm to a Local Saddle Point (LSP). This is particularly important, as the authors acknowledge that the LNP returned by LLGAME might not necessarily be an LSP of the original objective function.

questions:
Did you consider comparing your method with first-order algorithms? Incorporating them as a baseline can provide valuable insights.
</content>
</thread_object>

</thread>
<thread>
creation date:
1731908201417

thread_type:
official_comment

<thread_object>
creator: authors

<content>
title:
Top-Level Comment by Authors - Thank you for your time and effort to help us improve our work!

comment:
We thank the reviewers for their kind words about our work and their time and effort in helping us improve our manuscript with their insightful questions and comments.

We would like to highlight to the reviewers that the primary goal of our work is to recognize an important open problem in the current literature: saddle point optimization in the black-box setting on nonconvex-nonconcave objectives with zeroth-order samples. Our findings show that existing methods are not applicable to this problem, and we propose an initial approach aimed at motivating further research. Our approach demonstrates several key design principles—such as lower- and higher-level game structures—that we believe will be critical for future studies, alongside strong experimental results. We hope that our work inspires further research in these directions, and in particular we acknowledge the importance of establishing theoretical grounding for these design principles. *To the best of our knowledge, this paper is the first to experimentally demonstrate an approach that (1) finds saddle points in black-box settings (2) on nonconvex-nonconcave objectives (3) with zeroth-order samples. Prior work either achieves only one or two of these simultaneously or fails to theoretically and experimentally validate the approach in nonconvex-nonconcave settings.*

We respond directly to reviewers’ comments below. For the purpose of clarifying our changes, we have uploaded an updated version of our manuscript with changes highlighted in pink. A second version responding to the reviewers' second round of comments highlights new changes in orange. We will remove this highlighting in a further update before the review period ends. We look forward to additional feedback, and are happy to make further changes to clarify and improve our work.

Update on November 27, 2024: We have removed the highlighted portions of the text, as there is a deadline that prevents further draft edits after today. To easily identify further changes, we refer reviewers to the "Manuscripts Changes" section of each comment where we highlight changes based on the reviewer's comments.
</content>
</thread_object>

</thread>


Metareview:
metareview:
This paper proposes a method to find local saddle points in black box two-player zero-sum games with potentially non-convex non-concave objective functions.

The strength of this work is that it provides an algorithm to tackle a challenging problem (namely,  black box two-player zero-sum games with potentially non-convex non-concave objective functions). 

The main two weaknesses of this work are:
- The authors do not provide novel theoretical guarantees (Lemma 4.1 is an application of a standard theorem on Newton's method and only regards the inner loop). Even though it has been acknowledged by the authors, it remains a weakness. I believe it would be interesting to get guarantees in a (theoretically) tractable setting such as convex-concave.
- The experiments only deal with toyish low-dimensional problems. 
If we reflect on the motivation for this setting provided by the authors:
> For example, in robust portfolio optimization, the goal is to create portfolios resistant to stock market fluctuations (Nyikosa, 2018), which are inherently random and difficult to model but can be sampled in a black-box fashion through trial and error. Similar problems arise in various physical settings, such as robotics (Lizotte et al., 2007) and communication networks (Qureshi & Khan, 2023)

The experiments provided by the authors do not reflect the ' Motivat[ing] ... real-world examples'  mentioned in the introduction and thus undermine one of the main claim of this work, which is that 'We experimentally demonstrate our algorithms’ effectiveness on a variety of challenging synthetic and realistic datasets.'

In particular, regarding the ARIMA application, the space is 4 dimensional, the noise is Gaussian (thus, it remains a synthetic experiment), and the baseline with random search is not compared.