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
Venue: Accepted by TMLR ()

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 leverage existing general-sum Nash game solvers to solve for saddle points of zero-sum games. 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.

Published in Transactions on Machine Learning Research (06/2025)
A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Box Games
Shubhankar Agarwal'
University of Teros at Austin
somt. agwrwalllliaa wwttamlsttte.a..m.mmm.... edu
Hamzah I. Khan University of Terns at Austin
hamzah@utemas. edu
Sandeep P. Chinchali
University of Teras at Austin
sandeepc@utezas.. edu
David Kril University of Teras at Austin
dfkdutemas. edu
Reviewed on OpenReview: /ttps://openrree
// opwnrevee..........m net/ forum? id- NoRyyPPWCC
Abstract
Saddle point optimization is 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-bor settings with unknown objectives that can only be sampled cither assumes convexity-concavity in the objective to simplify the problem or operales with noisy gradient estimators. In contrast, we introduce a framework inspired by Bayesian optimization which utilizes Gaussian processes model the unknown (potentially nonconvex-nonconean objective and requires only zeroth-order samples. Our approach frames the saddle point optimization problem
two-level process which flexibly leverage existing general-sum Nash game solvers to solve for saddle points of zero-sum games. 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 synthetic and realistic datasets in black-box nonconvex-noncoocany settings, showcasing their ability to efficiently locate local saddle points in these contexts.
1 Introduction
We consider the problem of finding saddle points for smooth two-player zero-sum games of the form
PLAYER 1: min (x,vv
PLAYER 2: min fxx- v) x E RR= y Ty
(1)
with an unknown, nonconvex--onncooee samples f (i.e., sampling does not provide any derivative information) via possibly expensive process given coordinates (ar, y), where x E TR= Ray
objective f. We assume that we can draw noisy zeroth-order
Saddle points are points at which the function f is simultanerusly minimum along the z-coordinate and maximum along the g-coordinate. Such points specialize the well-known Nash equilibrium concept to the
"Equal contribution

---

Published in Transactions on Machine Learning Research (06/2025)
setting of two-player, zero-sum games. Saddle point optimization (ind 2009 is widely used in real-world
applications like economics (Luxenberg et al.] 2022), machine learning [Goodfellow et. al. 2020), robotics
(Agarwal et al. 2023), communications (Moura & Hutchison 2019). chemistry (Henkelman et al. 2000), and more.
Zero-sum games have been widely studied for known and differentiable objective functions. However, this assumption does not encompass numerous real-world situations with nonconvex-nonconeee objectives that may be unknown and can only be sampled. Such objectives are often referred to "black-box." For example, in robust portfolio optimization, the goal is 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 it al. 2007) and communication networks (Qureshi & Khan 2023). Motivated by these real-world examples black-box settings, we present a flexible and extensible framework that seeks to identify a saddle point, (z", y"), such that yg S f(x", .y" S fx, ) for all x, y in its neighborhood.
in nonconvex-noncomee
Most previous research in this area has focused on solving minimax problems (Bogunovic et al. 2018 Fröhlich et al. 2020: Wang et al.) )022), which take the form min, max, fxx v). The difference between minimax and saddle points is subtle: a minimax point achieves the best worst-case outcome for the minimizer (i.e., a Stackelberg equilibrium). In contrast, al a saddle point, the best worst-case and worst best-case outcomes coincide (i.e., a Nash equilibrium). Solutions to minimax problems in general nonconvex-nonconee are not necessarily Nash, and encode a leader-follower hierarchy that is not present for the saddle point concept. In settings like racing, chess, and resource allocation, where rational, adversarial actors make decisions simultancously, equilibria are best described as saddle points.
settings
Many previous works in saddle point optimization assuine convex-concave objectives (v. Neumann 1928 Korpelevich 1976 Tseng 1995; Nemirovski 2004). for which every minimax point is a saddle and vice versa because the best worst-case and worst best-case always coincide. However, this equivalence does not hold settings. Notably, some prior works addressing black-box convex-concave
in general senconvve--noccoeeee settings use zeroth-order samples (Maheshwari et al., 2022).. Tastly, finding global saddle points remains an open problem in general settings, so our work specifically focuses on discovering local saddle points, as detailed in Remark 3.5
In contrast to previous works, we approach this problem in the spirit of bilevel Bayesian optimization: at a high-level, we use Gaussian processes to build surrogate model for the black-box function f(z, 3) by sampling points (z. y) at promising locations, and at a low-level, we identify these sample points by solving generul-sum games defined on the surrogate model. Specifically, the low-level game selects these samples by socking local Nash points (Defn. 3.2 of these two-player general-sum games. The high-level optimizer then aims to ensure that in the limit, these samples converge to local saddle points of the black-box problem. We present our contributions as follows.
1. To the best of our knowledge, our method for saddle point optimization is the first to experimentally demonstrate an approach that (1) finds saddle points in black-box settings, (2) on nonconvex-nonccocaav objectives, and (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-noncooean settings.
2. We use our framework to propose a set of algorithms for the lover-level game, with cach variant catering to a different real-world case based on uncertainty and sampling cost. Thus, our approach allows for versatility in trading off between factors like ease of sampling, exploration and exploitation, and provides template for future work in this area.
3. We experimentally demonstrate our algorithms' effectiveness on a variely of challenging synthetic and realistic datasets. Due to the limitations of extending Gaussian Processes to higher dimensions, we focus our experiments on low-dimensional settings which are amenable to GPs. We discuss this choice further in our experiments.
2

---

Published in Transactions on Machine Learning Research (06/2025)
2
Related Work and Preliminaries
Saddle Point Optimization: Saddle point problems are widely studied in the game theory (Başar & Olsder 1998 Cherukuri et al., 2017), optimization (Duphinn et al.) 2014 Pascanu et al. 2014), and machine learning communities (Benzi et al. 2005 Jin et al. 2021]. We note three previous varieties of algorithms in the area of nonconveex-nnnooneaas saddle point optimization that guarantee convergence to local saddle points rather than stationary points. Of these, [Adolphs et al. (2019) and Gupta et al. (2024) introduce algorithms that solve for saddle points in deterministic settings, and neither approach handles unknown objectives. [azumdar ct al. 2019) introduces local symplectic surgery (LSS), method that, when it convergos, provably does to local saddle point given access to first-order and second-order derivative measurements by the sampler. However, derivative information is not always available in systems of interest. Moreover, while seroth-order samplers can estimate noisy first-order (and sccond-order) derivatives via finite diffcrencing, the extensive sampling requirements for such an approach are prohibitive when sampling is expensive. By contrast, our work proposes an extensible zeroth-order framework for black-box saddle point optimization, and we provide extensive experimental evaluation of several variants tailored to distinct settings.
denoted by GP(M(), E(.)), is set of random variables, such that any finite sub-collection (f(z) Fi is jointly Gaussian with mean ju(x)) = [x)() and covariance Σ = [[; (fz)))(f((;) - x(x;))), vi,j (I.....nI.
Gaussian Process (GP): A GP Rasmussen 2003
GPs are mainly used for regression tasks, where they predict an underlying function, : R. given some previously observed noisy measurements. That is, for any inputs 2 T1...., In E X C R and the corresponding noisy measurements, T' E R, the vector r = [11, .2....,, rn] is modeled as a multivariate Gaussian distribution with mean vector μ (lypically assumed covariance matrix, Σ, is calculated as follows: Σn K ((,,, 2y), j E {l....,nz n), where K(--)) is the kernel function. Typically, it is assumed that errors 2 = r; f(z;) are normally, independently, and identically distributed, L.e. z E o0) At a test point F., we compute the marginal distribution of fxx given r via
be zero), and covariance matrix E E R=x=, The
(x.) ~ Nik ( + K (I., - b ("
- k,),,
(2)
p((x))
(x(x))
where h; = [K (21, K (In, x. A more detailed description of (2) can be found in Rasmussen 2003) For typical (e.g, squared exponential) kernels, the number of samples required for GP regression increases exponentially in the number of dimensions; thus, GPs are appropriate for only relatively low-dimensional spaces. Nevertheless, GPs form a useful tool in addressing many relevant real-world problems. They are well-suited for modeling uncortainty in black-box optimization problems because they predict both the function value and the uncertainty of that prediction, which is crucial for balancing exploration and exploitation in optimization frameworks. Moreover, the smoothness of GP estimates allow for the deployment of standard gradient-based algorithms to estimate solutions to optimization problems.
Bayesian Optimization (BO) with Gaussian Processes: Bayesian Optimization (Močkus 1975 Brochu et al. 2010b Shahriari et aL.) 2016) is a sequential search method for maximizing an unknown objective function F + R with as few evaluations as possible. It starts with initializing a prior over ʃ and uses an acquisition function to select the next point x, given the history of observations, f(x1)...., f( The unknown objective, f, is sampled at Tt, and its observed value f(x:) is used to update the current estimate of f. Typically, is modeled as a GP, and the GP prior is updated with new samples. One common acquisition function, used in the GP-UCB algorithm, is the Upper Confidence Bound UCB, y) 14 (z.z) + 8,0, (z. 3) (defined here to estimate the two-argument zero-sum objectives from (1) ). GP-UCB (Srinivas et al.) 2010)
has been used in a varicty of settings including robotics (Deiscnroth et al. 2013). chemistry (Westermayr &
Marquetand 2021), user modeling (Brochu et al. 2010a),, and reinforcement learning (Cheung el al. 2020). A high Be parameter in UCB, implies a more optimistic maximizer (i.e., favoring exploration) in the presence of uncertainty. The UCB acquisition function combines the estimated mean, (e and the estimated standard deviation, (2 y), of the unknown objective function f at point æ at iteration t. Analogously, we can also define the Lower Confidence Bound (T.CB, (x., y) = pe (x, v) B. (z, v))-
3

---

Published in Transactions on Machine Learning Research (06/2025)
3 Problem Formulation
We consider the two-player, zero-sum game in L and focus the case in which the objective f is an unknown function defined on the domain R x R"v, and can only be realized through (possibly expensive or noisy) evaluations. That is, we query the objective at a point (I, E R x RRy and observe a noisy sample r = f(x,y) + 2, where z ~ (0, of). Although f itself is unknown, we will assume that it is smooth and can be differentiated twice. Our goal is find Local Saddle Points (LSPs) of f.
Problem Setup:
Our proposed framework will consist of two stages: at the lower level, we will solve general-sum game defined a GP surrogate model to identify (local) Nash points, and at the higher level we will sample f at those points and refine the GP surrogale model. Next, we formally define Nash points for general-sum games, the conditions they satisfy, and when such a point coincides with a saddle point for a zero-sum game. For a two-player general-sum game, where player 1 is minimizing function f1, and player 2 is minimizing function f2, a Nash point, (x",y"), is defined as:
Definition 3.1 (Global Nash Point (GNP) for Two- Two-Player General-Sun Game). BBşar & Olsder 1998 Defn. 2.1) Point (x", y*) is a global Nash point of objectives fI, f2 if, for all x, y E R" x R"y
f(*", v"), f2(x", ,,,,","')) S f2(2",
3
At a GNP, variables and y camnot change their respective values without achieving a less favorable outeome. In general, there does not always exist global saddle point, and when it exists, it is not necessarily unique. Finding GNP is computationally intractable in nonconvex scttings (as in global nonconvex optimization), s0 we seek a Local Nash Point (LNP), where this property needs only to hold within a small neighborhood. A LNP is characterized by first- and second-order conditions.
Definition 3.2 (LNP for Two-Player General-Sum Game). (Ratliff et al. 2016 Defn. 1) Let ||- denote a vector norm. A point, (x",y"), is a local Nash point of cost functions fi and fz if there exists a t > 0 such that for any x and y satislying || - x" S and ||y - y"1l S t, we have 43.
Proposition 3.3 (First-order Necessary Condition). (Ratliff al., 2016 f2, a local Nash point (x", satisfies vafi(x", y²) = 0 and vyfe(x"
Prop. 1) For differentiable fi and
= 0.
Proposition 3.4 (Second-order Sufficient Condition).
Ratliff et al.
2016 Defn. 3) For diffe-iiffeeeentiable 0, and (2yl(( > 0, then it is
fi and f2, if (x,y) satisfies the conditions in Prop. 3.3 V2 (z,y) strict local Nush point.
Remark 3.5 (Nash Point is a Saddle Point when f1 = -2). ff - then the point (=*,8") is a global saddle point of f when Defn. 3.1 holds and local saddle point when Defn. 3.2 holds. A local saddle point is characterized by the same first- and sccond-order conditions defined in Prop. 3.3 and Prop. 3.4 respectively. Henceforth, we use the term saddle point to refer to Nash points in zero-sum games and refer Lo Defns, 3.1 and 3.2 and Props.
3.3 and 3.4 for Nash and saddle points.
4 box Algorithms for Finding Local Saddle Points
We present summary of our bilevel framework, which is inspired by Bayesian Optimization, for identifying local saddle points in black-box setting. Let Pt and Σ,, respectively, define mean and covariance functions that estimate the unknown objective f as a Gaussian process based on a dataset S, = {((,,, Hi, r=) where ra E IR is a (potentially noisy) sample of f at point (x,, We define a zero-sum game, which we refer to as the high-level game,
PLAYER 1: x= arg min (4 PLAYER 2:
y" arg (1e
(4)
y
This game has two purposes: primarily, it seeks to solve for a LSP of the original problem 1
Doing requires solving the secondary problem of refining the GP estimate by strategically sampling f to form S = St f2 M441, } at iteration 1+1. To identify promising points, we solve a low-lovel general-sum game
PLAYER
arg min LCB, PLAYER 2: g² min UCB
(5)
4

---

Published in Transactions on Machine Learning Research (06/2025)
Function LLGAME (x,, y, I.C,, UCB)):
Input: So, GP prior (H0.0))
1: To, Uo = 2; y-
1: Start with initial point (Tu. Mo) = arg (z.))), Mi v).
2: while M (2,, Me) 2 c do
2: while Mf (Mr, 3t) 2 do
3:
Get next iterate (Tr-1: Dt+1) using LCB, UCB as shown in
3:
(I++1, M)+1) = LLGAME(Z,, Mt, LCB,, UCB,).
4:
Sample 1 and add to Se+1-
5:
Update (4-1: LC1 LCB UCB
end
6:
(It, = (1441, Vt+1).
4: Return ."
end
End Function
7: Return Saddle point x", v" Algorithm 2: Bayesian Saddle Point (BSP) Algorithm
Algorithm 1: LLGAME
for local Nash point. As h and Σ, are smooth functions, we can solve ( by deploying standard gradient- based algorithms to solve the lower-level game for first-order stationary points. In our work, we solve (5) using a technique (Alg. [ which is based on Newton's method, but the structure of our method allows for any general-sum Nash game solver to be used.
observation about the relationship between this general-sum LNP and the zero-sum LSP (x",y") wish to find. In the limit of infinite samples in the neighborhood of (x", ,e",""), when the GP surrogate converges to J, then the uncertainly converges to zero and LCB, and UCB, converge to the mean Pt, which converges to f and leads problems 44) and (5) to coincide. These games optimize μt, which is an estimate of f, so note that any solutions will be approximate.
Critically, our method relies
4.1 Defining and Solving The Low-Level Game For Local Nash Points
Extending the familiar "optimization in the face of uncertainty" principle from BO (Snoek et al. 2012) and active learning (Yang et. al. 2015), we construct the low-level game in 5 so that each player minimizes a lower bound on its nominal performance index. As in active learning, this design is intended to encourage "cxploration" " of promising regions of the optimization landscape carly on, before "cxploiting" the estimated GP model. These bounds, LCB, and UCB,, are constructed al each iteration of the high-level game.
Finding LNPs is computationally intractable in general; in practice, we seek only points which satisfy the first-order conditions of Prop. 3.3 To find this solution, we introduce a new function, GC v) = x R + BustRy whose rools coincide with these first-order Nash points. The superscripi CB and subscript signify that we are finding the roots with confidence bounds (CB) at iteration t. Specifically, we seek the roots of the following nonlinear system of (algebraic) equations:
GCB v) V a LCB, v)
] =0.
]
(6)
y UCB,
The LLGame Algorithm: In Alg. 1 we present our approach to solving the low-level game, which we refer to as LLGAME. LLGAME utilizes the current confidence bounds, (LCB, UCB:), to determine the local Nash points by finding roots of G using Newton's method. The LLGAME function does not make any new queries of J; instead, it uses the most up-to-date confidence bounds to identify the local Nash points. LLGAME takes an initial point, (I, and current confidence bounds, (LCB,, UCB.), ULC.,, as inputs. Starting from line 2, the algorithm iteratively updates the point, (T,, using 7 discussed below and halts when a merit function, M Wt), and therefore the gradients LB,LCB, (Ze, Yt) and V UCB, (t), are sufficiently small. Ultimately in line 4, the function returns the final point, (x*, """, once discovers a stationary point satisfying first-order Nash conditions as per Prop. 3.3
To gauge the progress towards root of GC (I,z), employ merit function, a scalar-valued function of (x, v), which equals zero at root and grows unbounded far away from a root. Specifically, we use the squared l norm as the merit function, ie.,, MC = [ 1) each LNP of (5) is a global minimizer of M.
Defining Convergence (line 2):
Nonlinear Root-finding with Newton's Method (line 3): To find the roots of G (z. y), our work employs Newton's 's method, which an iterative method that is widely utilized for solving nonlinear systems. The Newton step, px. y), is obtained by linearly approximating the function, GCB with its Jacobian matrix
5

---

Published in Transactions on Machine Learning Research (06/2025)
Je y) at the current estimate (x, v) and identifying the root of that approximation. therefore satisfies:
The step (2.
(((,y)pe(a, = G (a, v), with Je(x,)) = V LCB, UCB,
V J.C.B.BB a.y - UCB,
(7)
Consequently, we update the current point, (z. y), by taking the step Pt to reach the next point. In our experiments, we employ Newton's method with Wolfe linescarch, which is known converge rapidly when initialized near a root, as shown in (Nocedal Wright 2006 Ch. 11). Note that the Jacobian J, requires minimal effort to compute in the lower-dimensional spaces that are classically amenable to black-box optimization. We provide exact implementation details in Appendix B
Adapting LLGame: We note that other optimizers can be used to solve for (first-order) LNPs of (5)- One prevalent example is the gradient ascent-desoent method (discussed by Mescheder et al. (2017) and Balduzzi et al. 20118) among others), which uses gradient steps instead of Newton steps as in our method. Our framework is flexible, and LLGAME can readily be adapted to use these methods to identify local Nash points.
4.2 Solving the High-Level Game: Finding Local Saddle Points with BSP
In the high-level game, we seek to solve the zero-sum game 44h to identify the saddle points of 14- Upon extracting solution to (5) in LLGAME,
sample the objective f around the low-level Nash point (0", W"". The result of this sampling is used to update the mean 24, and uncertainly estimate o, for the GP surrogate of f. Following the design of Sec. 4.1 we seek to identify first-order LSPs of (4] with roots of the function
Gf and global minima of the corresponding merit function M/:
V 2 far
M' 1 1IG'
(z, - v fx,(
(8)
However, as f is unknown, we instead define function G and corresponding merit function M using the GP surrogate model of f by replacing f in (8) with p4. Thus, our method identifies saddle points of f by finding the roots of G and global minima of Mf".
We now present our overall algorithm BSP (Alg. 2). which searches for the local saddle points. As stated carlier, this distinction between the two games allows us confirm if a local Nash point is local saddle point. In Alg. 2 we start by optimizing the hyperparameters of our GP kernel using the initial dataset, So, a standard procedure in BO (Snoek et al. 2012). Upon learning the hyperparametors, an initial GP prior, (Ho,0)) is obtained. Then in line 1, we select a starting point, (Fo, Bo), from the initial dataset, Sp, based on the lowest merit value. From this point, an iterative search for the local saddle point is conducted in the outer while loop (lines 2-6). The LLGAME function is utilized in line 3 to determine the subsequent point (Iz+1, Mt+1), which is a local Nash point of the general-sum game 5.. The point, (I++1, 10+1), only a local Nash point for the given LCB, and UCB,; we will not be sure if it is local saddle point of f until we sample f that point and calculate M to validate the conditions in Prop.
The Bayesian Saddle Point Algorithm:
Consequently, in line 4, the point returned by LLGAME is sampled and added to the current dataset. In line 5, new hyperparameters are learned from dataset S,+1, and Mt+1, 1141,LCCBBB. UCB,41 are updated accordingly[] After sampling at the point (I++1, 1t+1), we have decreased the variance at that point, and thus the mean, Me (1 Me+1), and its gradient Vμu, are better representations of and its gradient Vʃ. After each update the GP surrogate, we check if the merit function value sufficiently small, i.e., Mf (I y1) S e, where e 0 is a user-specified tolerance. Ultimately in line 7, the local first-order saddle point (x", """""" is returned after the completion of the outer loop.
4.3 Convergence
In Lemma demonstrate that Alg. 1 will terminate and converge to point which satisfics Prop. 33 under standard technical assumptions for Newton steps to be descent directions on the merit function.
This is standard procedure in black-box optimization, explained further detail Appendix R.8

---

Published in Transactions on Machine Learning Research (06/2025)
Our experiments in Sec. 5 include cases that both satisfy and violate these assumptions, showcasing the performance of our algorithm under various circumstances. The precise statement of Lemma 4.1 closely follows Theorem 11.6 from Nocedal & Wright (2006), which is standard result on the convergence of Newton methods for identifying roots of nonlinear equations.
Lemma 4.1 (Convergence to Stationary Point Satisfying Prop. 3.3 in LLGAME). Let (x, y) be Lipschitz con- tinuous in a neighborhood D C T X"y surrounding the sublevel set C= {z.y: y: M (z. y) S M, (zo. }o)]. and |.G. (z, u)ll2 have upper bounds in D. Let step lengths ag satisfy the Wolfe conditions [Nocedal & Wright, 2006, Sec. 3.1). If [[ Il2 has an upper bound, then Alg. 1 will converge and relurn rool of G.
Assume that both (1, y)
(x. y) which salisifes Prop. 3.3
Proof. These assumptions match those of Theorem 11.6 of Nocodal & Wright 2006), which can be applicd to find that the Zoutendijk condition holds, that is
cos2 (0x) (I CB (Zk, 91)12 < co, A20
(9)
where Og is the angle between the Newton direction and the gradient of the merit function, VMCB ef. Eq. 11.40 in Nocedal& & Wright (006).. We are assured that cos 0g 2 6 for some 8 > 0 if we take Newton steps at every iteration k. Specifically, recall that [ ys) ll and [|J yr Il2 are bounded above by finile and nonzero B1 Bg E R4, respectively. From these assumptions, we can provide an upper bound on the condition number x(J) = mmax m))x (J)mmi))))) which is the ratio of the largest singular value of J, m (J), and smallest singular value of J, Tmin (J). Since inverting a matrix inverts its singular values, we know that ||/||2 = max S B and that || = maxx = (J)mmn(J) S B2, which further implies that amin 2 1/nz, and produces the desired bound on the condition number, x(J) 2 B, B2. Using Eq. 11.42 of [Ncedal & Wright (2006), we find that cos 02 2 1/x(J) = 5. Lastly, it follows from (9) that limg-+o JT (æk; yk Vx, (x*,, yik) 0, implying that the iterates approach a stationary point of MCB at which C.B = O. Thus, the Newlon iterates converge to a root of GCB which satisfies the first-order necessary Nash conditions (Prop. 3.3
In Alg. 2 we sample / at the LNP returned by Alg. to reduce the variance, oe, in the confidence bounds. This improves the accuracy of the mean function je and its gradient Vpt as estimators for f and its gradient / around the sampled point. Consequently, the merit function, Mf", closely approximates M and thus effectively validates convergence to the local (first-order) saddle point. As estimates improve with iterations, the loop in Alg. 2 is expected to terminate at a local saddle point.
Next, we provide an intuitive explanation of why sampling at local Nash points of coufidence bounds in (5) will lead to local saddle points of f in Q.. As we sample local Nash points, the variance in the confidence bounds at those points will decrease, and LCB/UCH will get closer to each other, as shown by Lemma A.1 and Remark A.2 As we keep sampling, the variance will eventually become the noise variance, Ø2. As such, Vo - 0 and therefore VLCBB, VUCB + Vμ > VJ; and therefore finding local Nash points of the confidence bounds will eventually lead to first-order saddle points of and consequently of f. To confirm that we find a saddle, we verify the sccond-order condition (Prop. 3.4 for the final saddle point returned by Alg. 2 If this point does not satisfy the second-order conditions, we reinitialize our algorithm from a new initial point. We find that, in practice, our algorithms find LSPs on the first initialization more frequently than baseline methods.
4.4 Variants of BSP
BSP Expensive: Our BSP method in Alg. 2 aims to minimize queries of the function f by taking multiple Newton steps per query of f. However, the algorithm may become unstable if the confidence bounds UCB++1, do not accurately approximate f. Additionally, it is possible that querying f can often be inexpensive, for example, in the case of Reinforcement Learning in simulated environments (Sutton & Barto 2018). In this case, we query I during each iteration of Alg. 2 after laking a single Newton step, in cont to the multiple steps taken in Alg. [ (lines 2-3). This approach is referred to as erp-essensive since we make more queries of f, while our original algorithm in Alg. 2 is referred to as BSP-efficient. We demonstrate in our results that this variant can more effectively and efficiently solve complex scenarios than baseline methods under these conditions.
7

---

Published in Transactions on Machine Learning Research (06/2025)
Exploration and Exploitation: In Alg. encourage more exploration by using LCB for minimization and UCB for maximization. Since the value of unexplored regions has high variance and thus a lower L.BB value, the minimization procedure will explore those regions first (vice versa for UCB and maximization). As such, we refer to our original proposed method as BSP-erplore. Alternatively, we can use LCB for maximization and UCB for minimization, thus promoting more exploitation by our algorithm. We will refer to this variant as BSP-erploit. In real-world scenarios, this approach might be suitable when optimizing a well-understood process, finennuning known models, or when domain knowledge allows for confidently focusing exploitation.
5 Experiments
In this section, evaluate the BSP algorithms presented in Alg and Sec. 4.4 across various test environments. We consider four versions: 1) BSP- USSP-effcient-ezplorr (EF-XPLORE), 2) BSP- LSSP-efficient-crrpp exploit (Er-X (EF-XPLOIT), and 4) designed around challenging baseline problems widely recognized in prior work, demonstrate that each algorithm excels in specific settings.
3) BSP-cxpensivve-eplon
(ExP-XPLor) Our experiments,
While GPs are most effective in dimen-immnsional spaces, we evaluate our methods on problems with up 10 dimensions. We acknowledge that our experiments may not fully capture the complexity of high-dimensional real-world applications; however, our primary goal is to establish a foundation for solving these problems. We view this work as a first step and aim to exlend our approach to more complex real-world settings in future research.
1. Decaying Polynomial: In our first experiment, we examine the performance of our algorithms for a nonconvex-nonnconeaay objective laken from Mazumdar et al. (2020) and Gupla el al. (004);
fexp(1, y) = exp (-0.01 (x² +9)) ( ((0.3-- v)² +0.5y² + +))²
(10)
This example is particularly difficult for three reasons: first, multiple TSPs exist. Second, the origin is a spurious saddle point that satisfics first-order conditions but not sccond-order conditions. Third, the function gradients decay to zero further from the origin, meaning that an iterative algorithu straying too far from the origin may "stall," taking smaller and smaller step sizes, but never converging to a fixed point.
2. High-Dimension Polynomial: We consider a sixth-order polynomial from Bertsimas et al. (2110):
Sbertsimas (I, 2x 12.2x 21.22 6.2x 6.4x 4.7x² 1/ + 11y
(11)
43.3g² + 10g 74.8y² 56.9y² + 4.1 0.1
0.4yy 0.4x²
The decision space is within [Tiiin = 0.95, mmx = 3.2) x [ymin
-0.45,, ymax = 4.4]. The objective,
fpoly(z,)) y), is nonconvex-nonconcary and has multiple LSPs (Defn. 3.2 We form a high-dimension (2n)-D
polynomial by letting, for F E R &R" R..
n
Spoly (7. V)
Σ fbertsimas V:).
(12)
We set n = to evaluate how well our proposed algorithms identify LSPs with more dimensions. A 10- dimensional space sufficient for many relevant. applications, though we note that it may constitute a relatively low dimensionality for others.
more realistic zero-sum game involving an ARIMA process that synthesizes discrete time 1D time series of length F, denoted by E RF, for a model predictive controller to track. This setup mirrors real-world systems like that of Stent et. al. (2024), in which an aulonomous system corrects for distracted human driving. We represent the ARIMA process for initial state Sp E R and model parameters a E R, E R: 8p = ARIMA(so a, B)) The MPC takes the ARIMA time series, 8F, as input and returns controller cost. fMPC E R incurred while tracking the given time series. The MPC solves an optimization problem with quadratic costs and linear constraints, encapsulating vehicle dynamics and control limits. The optimization problem is represented
3. ARIMA Tracking Model Predictive Controller (MPC): Finally, test our algorithms
8

---

Published in Transactions on Machine Learning Research (06/2025)
SMPC- MPC(A, B, So, 8p), returning the final overall cost of tracking the ARIMA-generated time series sp, initial state 80, and model dynamics A, B. Further details can be found in Appendix B.6
Zero-Sum Game Pormulation: We formulate the interaction between the ARIMA forecaster and the MPC as a zero-sum game. The antagonist selects the ARIMA parameters a, 3 to generate tifficult-to-trakk time series forecasts, 8p, resulting in a higher MPC cost. fMrC- In many scenarios, we want to find model dynamics that are robust and can effectively handle various tracking signals. As such, the protagonist chooses the MPC model dynamics parameters A, B to accurately track Sp and minimize the controller cost. This competitive scenario is formulated as follows:
SMPC- = MPC( A 80 8F = ARIMA(80, (80,
0,5
))-
(13)
protagonist
antagonist
This game is motivated by real-world scenarios requiring robust controllers for adversarial and out-of- distribution inputs, and it has multiple LSPs (Defn. 3.2
Experimental Setup:
We compare algorithms in two settings. In the first, we initialize our algorithms with a large number of sample points, modcling scenario where the objective is well understood. In the second step, we initialize algorithms with a small number of sample points, modeling scenario where obtaining samples is expensive. In all our experiments, we use a squared exponential kernel, where the kernel value of two data points x; and zj is given by:
1 (x; xz)" (a. xz) of
k (0,, = of oz exp
(14)
2
where oy (signal variance) and 0r (signal length scale) are hyperparameters. We learn these hyperparametens via maximum likelihood to initialize our algorithms. In all experiments, we assume that we observe noisy measurements of the underlying function. To ensure that algorithms are initialized at points with a non-zero gradient in the decaying polynomial example (Lop row of Fig. D we ensure these are selected from the non-flat. regions of the function. All experiments are performed with 20 seeds for each algorithm. For the scenario with a limited number of initially sampled points, we sampled 50 points for the decaying and high-dimensional polynomial objectives, and 10 points for the ARIMA-MPC objective. We present the exact experimental setup for each test case in Appendix B
5.1 Experimental Results
variants of our algorithms for the first two scenarios mentioned above; for results related to EF-XPLOIT and EXP-XPLORE, we refer the reader to Fig. 4 in Appendix C where we report similar results to EX-XPLORE and EXP-XPLOrT, respectively. The middle column of Fig. considers test cases with a large number of initially sampled points, while the right. column considers test cases with a limited number of initially sampled points. We sample 1000 initial points for the decaying polynomial and 500 initial points for the high-dimensional polynomial and for ARIMA-MPC (for which we report results in Fig. 2
Fig. D summarizes the performance of the EF-XPLORE and
We assess the performance of our algorithms using the merit function from Eq. Mr, which is calculated based on the true gradients of the underlying function, rather than the confidence bounds employed in the actual algorithm. As previously mentioned, MI will attain a global minimum (of 0) when the first-order conditions in Prop. 3.3 are satisficd. This evaluation metric directly mcasures the algorithms' offectiveness in identifying local saddle points of the underlying function. We also compute success rates for each algorithm in finding a saddle point (Table 2 We only include run as success if the BSP solution satisfies second- order sufficient conditions (Prop. 3.4/ according to the ground truth derinatives Vf and V² Lastly, we compute rates of convergence, measured in Newton steps, for our algorithms. Overall, our results show that our first-order algorithm finds saddle points at a higher rate than all baselines, even outperforming the success rate of a state-of-the-ar second-order method!
Baselines: We consider multiple baseline algorithms: naive random sampling (RANDOM), gradient descent- ascent with finite differencing (GDA WITH FD), local symplectic surgery (LSS, state-of-the-art baseline
9

---

Published in Transactions on Machine Learning Research (06/2025)
Decaying Polynomial 2D
Ef Eploee (Ours)
Exloxt (Ours)
Random
GDA wi FD
LSS
1.0
1000 initial samples
50 Initial samples
0.8
Real Merit: M
1000
11100
0.6
0.4
23
0.2
10
10
10
y
0.0
30
100
150
200
250
200
Digh-Dimension Polynomial 10D
0.8
500 Initial samples
50 Initial samples
0.00
.00
Real Meric:
0.6
300
-000
0.4
300
0.2
20 40
80 100
0
50 100
100
200
Num. Function Evaluations
Num.
Function Evalustions
Figure 1: Comparisons of selected algorithm variants with baselines: We compare variants of our proposed algorithms with baseline methods across two domains (rows); the decaying and high-dimensional polynomials. Landscapes of each polynomial are shown in the first column. The middle column considers test cases with a large number of initially sampled points, while the right column examines test cases with limited number of initially sampled points. In each case, we report the value of the (real) merit function M vs. the number of underlying function evaluations. Key takeaway: Generally, EF-XPLORE converges faster when there are a large number of initial samples, and it does so by taking multiple Newton steps and exploiting the accurate prior. EXP-XPLOIT exhibits quicker convergence when there are limited initial samples, and it does so by taking single Newton steps to avoid unfavorable regions amid uncertainty. Finally, we find that Er-XPLORE and EXP-XPLORT converge faster than all three baseline methods, indicating the benefit of the GP surrogate in improving convergence compared to baselines, which are often unable to converge.
from Mazumdar et al. 2211)),, and four algorithm variants from Maheshwari et al. (2022) The first three methods assume access to zeroth-, first-, and second-order derivatives, respectively, and the last is a zeroth- order method. In the random sampling bascline, we uniformly sample a fixed number of points (x, y) from the hyperbox {æ. y : I'in S x S Xmax: Ymin S y S ymax), and retain the point with the lowest real merit function value (M In the gradient descent-ascent baseline, we employ finite differencing estimate each player's gradient and use Wolfe linesearch to select step sizes. This approach allows for more directed search compared to random sampling. Approximating the gradient with finite differencing provides fair comparison between our method and first-order approach using zeroth-order samples. For the decaying and high-dimensional polynomial examples, we compare with LSS. LSS requires access to function gradients and Hessians; rather than providing finite differenced estimates (which can be extremely noisy and require excessive function evaluations), we provide oracle access to the true function derivatives and corrupt samples with standard Gaussian noise as explained in Appendix B
We provide an additional set of four baselines (OGDA-RR, OGDA-WR, SGDA-RR, SGDA-WR) from MMaheshwari al. 2022 for the decaying and high-dimension polynomial experiments. These algorithms are designed for and validated on zeroth-order convex-concave problems but can be applied in general settings.
Analysis of a Large Number of Initially Sampled Points: In this setting, we observe that the exploit variants of our proposed algorithms, EF-XPLOIT (blue) and EXP-XPLOR (orange), demonstrate the fastest convergence. This outcome is expected since the accuracy of the confidence bounds higher, reducing the neod for exploration. Overall, XPLOT (blue) achieves the fastest convergence in these experiments due to its ability to take multiple accurate Newton steps. In the decaying polynomial example from Fig. 1 EX-XPLORE
10

---

Published in Transactions on Machine Learning Research (06/2025)
converges quickly, as taking single Newton steps helps the algorithm converge in this particularly complicated landscape. In contrast, the eaplore algorithms have slower convergence, as they prioritize exploration. This general pattern continues to hold in Fig. 2 for the ARIMA-MPC scenario.
Analysis of Limited Number of Initially Sampled Points: In this setting, we observe that the explore variants of our proposed algorithms, EE-XPL.ORE (green) and EXP-XPIORE (red), achieve the best. performance. Notably, the algorithm variant EXP-XPLORE (red) demonstrates fast convergence, which can be attributed to its exploration approach and avoiding multiple incorrect Newton steps in the face of uncertainty. The exploit variants, EF-XPLOIT (blue) and EXP-XPLOIT (orange), exhibit slower convergence, as they rely too heavily on prior information and consequently take incorrect steps. Specifically, the EF-XPLOIT (bluc) variant fails to converge for some seeds since it takes incorrect Newton steps and is unable to explore. Finally, the expensive variants, in general, are more stable in this setting, as they only take single Newton steps and are less likely to reach unfavorable regions. EXP-XPLOTT (orange), for example, converges to a real merit. value M = 0 for both experiments. We note that for the decaying polynomial example, we still see the efficient variants converge faster, and this result reflects the complexity of the objective landscape.
Comparisons with Baselines: RANDOM sampling and GDA WITH FD never converge, though random sampling reduces the merit function value. The noise introduced by finite differencing renders GDA WITH FD ineffective in this problem setting. Despite reaching a low merit function value, we note that LSS fails to converge in many of these scenarios. In the decaying polynomial example, we see LSS iterate outward far from the origin where / becomes very small and no saddle points exist. This behavior is consistent with Mazumdar et al. (2019), which claims only that if LSS converges, it finds a saddle. Our experiments the decaying and high-dimensional polynomials indicate that LSS fails to converge to a saddle point far more often than BSP (Table 2). Furthermore, we find that OGDA-RR, OGDA-WR, SGDA-RR, and SGDA-WR (Maheshwari et al. 2022) always fail to find saddles in the two polynomial settings.
Runtime and Success Rate: We compare the runtimes of each algorithm variant in terms of the total number of Newton steps taken. In Table [ we present the total number of Newton steps taken by each algorithm variant over 10 seeds for scenarios with a limited number of initially sampled points. Neglecting the time to query the underlying function, the efficient variants require 400-500% more time compared to the expensive variants. This outcome is expected, as expensive variants only take one Newton step between cach sample of the underlying function evaluation. Furthermore, as anticipated, the explore variants require more Newton steps due to their exploration approach, but the difference is not substantial.
Domain
Type of steps Explore
Efficient
Expensive
Diln--Dimension Polynomial
2858
1464
Exploit
2613
1381
Decaying Polynomial
Explore
2690
1893
Exploit
3000
3000
ARIMA-MPC
Explore
1033
353
Exploit
815
229
Table 1: Runtime Comparison: In this table, we show the number of Newton steps taken by each algorithm variant over 10 seeds scenarios with a limited number of initially sampled points.
In Table 2 we display the full success rate results for each algorithm variant in scenarios with a limited number of initially sampled points. The results reveal that the explore variants exhibit more reliable convergence to saddle points compared to the exploit variants. This outcome is expected, as explore variants emphasize exploration and, therefore,
more likely to converge. Additionally, the expensive variants demonstrate greater stability in this setting, as they only take single Newton steps and are less prone to reaching unfavorable regions. The EF-XPLOIT variant exhibits the lowest success rate in convergence and did not achieve a 100% success rate in cases with a limited number of initial samples, as it relies on exploitation and takes incorrect Newton steps due to high uncertainty. We note that LSS often fails to converge to a LSP due to algorithmic assumptions (which only guarantee that when LSS converges, finds a saddle) or domain-spocific factors (iterating towards low- gradient regions of the objective landscape). We find that Exp- EXP-XPLOrT, EXLOR,, and EE-X XPLORR find saddle points strictly more often than LSS, and that EE- performs similarly or
11

---

Published in Transactions on Machine Learning Research (06/2025)
Domain
Bf- Xplore
Exp- Xplore
Ef- Xploit
Exp- Xploit
L.SS
SGDA-
SGDA- WR
OGDA-
OGDA- WR
RANDOM
GDA w/ FD
Decaying
Polynomial
60%
60%
30%
50%
15%
0%
0%
0%
0%
0%
0%
High-Dimension
Polyuomial
95%
100%
65%
80%
0%
0%
ARIMA-MPC
90%
95%
75%
86%
Table 2: Success Rate: In this table, we show the percentage of successful seeds (out of total sceds) for each algorithm variant. in scenarios with a limited number of initially sampled points. We show results on our baseline algorithms for two of the experiments. We adapt LSS to the black box setting by providing oracle to sample derivative information. To avoid including spurious saddle points as successos, we report the success rate according to the true second-order conditions, defined in Prop. 3.4 at the first solution BSP finds (i.e., without reinitialization.. The methods proposed by Maheshwari et al. (022 always fail to find saddle points.
better depending on the experiment. Neither of our other baselines (RANDOM and GDA WITH FD) find solutions for these problems. Lastly, none of the algorithms from Maheshwari et al. (2022) (OGDA-RR, OGDA-WR, SGDA-RR, SGDA-WR, ever find a LSP, confirming that methods for convex-concave settings are unable to find solutions for these problems of interest.
Iteration:
Iteration:
Nominal MPC
Robust MPC (Ours)
Trijectory Value
5
4
-088
MPC Cost
3
Iteration: 31
Iteration: 50
2
0.3
Teieetory
0.0
In- Disttribuiion
Time
Time
Figure Saddle Point Optimization with BSP leads Robust MPC on out-of-distee distriiittttion (OoD) data: On the left, we display the MPC tracking of the timeseries generated by the ARIMA model at various iterations for the Er-Xt XPLORE variant. The ARIMA target trajectory is depicted in purple, while the corresponding MPC tracking is illustrated in orange. Initially, MPC performs poorly (iteration 0), but gradually improves its tracking (iteration 17). Consequently. the ARIMA makes tracking more challenging for the MPC (iteration 31), until they both reach oquilibrium (iteration 50). On the right, we compare the final robust MPC parameters (orange), obtained through our algorithm, to the nominal MPC parameters (blue) on in-distribution data (left column) and OoD data (right column). Key takeaway: The Robust MPC successfully identifies robust MPC parameters and achieves 27.6% lower mean MPC cost OoD data compared to nominal MPC, without reducing performance in-distribution data.
Key takcaways from our experimental results: Our experimental results highlight several important insights about our algorithm variants. 1) The efficient variants require fewer underlying function evaluations and will work best when the prior is accurate. 2) The expensive variants offer faster runtimes and will provide more stable convergence when the prior is inaccurate. 3) The explore variants provide a higher success rate when the number of initial samples limited. 4) The exploit variants exhibit faster convergence in the setting with large number of initial samples. These findings suggest that the choice of amgorithm variant.
12

---

Published in Transactions on Machine Learning Research (06/2025)
should depend on the specific characteristics of the problem at hand, such as the number of available initial samples, runtime requirements, and domain knowledge of the underlying objective. Moreover, we find that our methods converge faster than simple baselines based on random sampling and finite differencing, and that they converge faster (and more reliably) than the statc-of-tho-art (second-order) LSS algorithm when it is adapted to the black-box setting. This occurs even though our algorithm uses first-order methods to find critical points and then verifies the result with sccond-order saddle point conditions.
Performance of BSP Variants in ARIMA-MPC Example: In Fig. 2 we evaluate the performance of the MPC parameters found by algorithms. Specifically, we compare the performance of the MPC parameters obtained at the end of the EF-XPLORE variant on both the in-distribution and out-of-distribution (OoD) ARIMA forecasting timeseries datasets. When MPC operates at a LSP, we can expect it to be robust to perturbations in ARIMA parameters, and therefore to OoD time series. Indeed, controller parameters found by our algorithm roughly match in-distribution performance and achieve 27.6% lower mean MPC cost on OoD data, showcasing our algorithm's ability to locate saddle points which correspond to robust performance
OoD data without reducing performance on in-distribution data. We provide the exact. details of this experiment in Appendix B and present full convergence results on the ARIMA-MPC example in Fig. These results mirror those of previous experiments, and we find that the exploit variants converge faster with many initial samples while the efficient variants do so with limited initial samples. Due to the poor performance of the baselines RANDOM, LSS, OGDA-RR, OGDA-WR, SGDA-RR, and SGDA-WR, on the simpler polynomial examples, we do not add them for the ARIMA-MPC experimental setting.
Summary: Our experimental results demonstrate that our proposed BSP algorithms converge faster, sample more efficiently, and produce more robust solutions than existing methods in variety of black-box saddle point optimization problems.
6 Conclusion
We present a BO-inspired framework for identifying local saddle points for an unknown objective function, f, with zeroth-order samples. We frame the problem of finding local saddle points for an unknown objective function as a two-level procedure. A low-level algorithm constructs a general-sum game from a Gaussian process which approximates the unknown function f, and solves for the local Nash points of this game by finding the roots of a system of nonlinear algebraic equations. A high-level algorithm queries the points returned by the low-level algorithm to refine the GP estimate and monitor convergence toward local saddle points of the original problem. We validate the effectiveness of our algorithm through extensive Monte Carlo testing on multiple examples. Our results outperform several approaches, including a state-of-the-ar approach (LSS); our zeroth-order method outperforms LSS despite providing it with a gradient oracle.
Limitations and Future Work: While our proposed framework shows promising results, we plan to address certain limitations in future work. First, we plan to extend our strong experimental efforts with more thorough theoretical guarantees using promising techniques introduced by recent works (Han et al. 2024 Gemp et al. 2024h which propose objective functions using an equivalent definition of Nash equilibria and for which local optima approximate Nash equilibria. Moreover, Han et al. (2024) introduce a Ga-based game solver based on trust-region methods and an associated no-regret proof, which may be relevant for developing future theoretical results. Second, our method currently finds saddle points by solving for first-order critical points, checking that they satisfy second-order conditions, and reinitializing the algorithm with the additional data if not. In future work, we intend explore ways directly incorporate second-order sufficient conditions (Prop. 3.4 to enhance the performance within the general-sum low-level game of our framework. Third, recognize that GPs can become prohibitive in higher dimensions, limiting this method's application to some real-world problems. As such, we plan to identify methods to adapt the framework to increasing dimensionality. Fourth, to further demonstrate our framework's adaptability, we will test our algorithm with other acquisition functions, such as knowledge gradient (Ryzhov et al.) 2012) and entropy search (Hennig & Schuler 2012). Lastly, we plan to apply our method to additional real-world scenarios, including stock market portfolio optimization, online marketplace auctions, and robust dynamic control by extending our MPC example.
13

---

Published in Transactions on Machine Learning Research (06/2025)
Acknowledgments
We thank Kushagra Gupta for his insightful thoughts on prior work and our results, and for his feedback on the presentation of our work. This work was supported by the National Science Foundation (NSF) under Grant No. 2409535, the Office of Naval Research (ONR) under Grant No. Martin AI Center. Any opinions findings expressed in this material those of the authors. They do not necessarily reflect the views of the NSF, ONR, or Lockheed Martin AI Center.
and the Lockhood
References
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the T'wenty-Secont International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 486-495. PMLR, 16-18 Apr 2019. URL htttps://proceednngs mlr gress/v89/adolphnn html
Shubhankar Agarwal, David Pridovich-Kell Keil, and Sandeep P Chinchali. Robust forecasting for robotic control: A theorete approach. In 2023 IEEE International Conference on Robotics and Automation (ICRA), 2023.
A. Agrawal, B. Amos, S. Barratt, S. Boyd, S. Diamond, and Z. Kolter. Differentiable convex optimization layers. In Advances in Neural Information Processing Systems, 2019.
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics of n-player dabee games. In International Conference on Machine Learning, pp. 354-363.
PMLR, 2018.
Tamer Başar and Geert Jan Olsder. Dynamic Noncooperatioe Game Theory, 2nd Edition. Society for Industrial and Applied Mathematics, 1998. doi: 10.1187/199916119911122 URL https:///pubss siam org/doi/ /dd////////////// 10. 1117//1.971111177741
Michele Benzi, Gene H. Golub, and Jörg Liesen. Numerical solution saddle point problems. Acta Numerica, 14:1 137, 2005, doi: 10.0177509924922440222
Dimitris Bertsimas, Omid Nohadani, and Kwong Meng Teo. Robust optimization for unconstrained simulation- based problems. Operalions Research, 58(1):161-174 2010. doi: 10.1287/0pre.1000000 URL https:
//doi wag...rg/110 1t////111.11100111 1287/ ttw./ 0715
llija Bogunovic, Jonathan Scarlett, Stefanie Jegelka, and Volkan Cevher. Adversarially robust optimization with gaussian processes. In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett. (eds.), Advances in Neural Information Processing Systems, volume 31. Curran Associates, Inc., 2018.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milne and Qiao Zhang, JAX: composable transformations of Python+NumPy programs, 2018. URL httt:://gtthu...... com
Eric Brochu, Vlad M. Cora, and Nando de Freitas. A tutorial on bayesian optimization of expensive cost functions, with application to active user modeling and hicrarchical reinforcement learning. ArXie, abs/1012.2599 2010a.
Eric Brochu, Vlad M. Cora, and Nando de Freitas A tutorial on bayesian optimization of expensive cost. functions, with application to active user modeling and hierarchical reinforcement learning, 2010b. URL https://arxiv, wwwg/as/////// 2599
Ashish Cherukuri, Bahman Gharesifard, and Jorge Cortes. Saddle-point dynamics: conditions for asymptotic stability of saddle points. STAM Journal Control and Oplimization, 55(1):486 511, 2017.
14

---

Published in Transactions on Machine Learning Research (06/2025)
Wang Chi Cheung, David Simchi-Levi, and Ruihao Zhu. Reinforcement learning for non-stationary markov decision processes: The blessing of (more) optimism. In International Conference on Machine Learning, pp. 1843 1854. PMLR, 2020.
Yann N Dauphin, Razvan Pascamu, Caglar Gulcehre, Kyunghyum Cho, Surya Ganguli, and Yoshua Bengio. Identifying and attacking the saddle point problem in high-dimensional non-convex optimization. Advances in neural information processing systems, 27, 2014.
Mare Peter Deisenroth, Dieter Fox, and Carl Edward Rasmussen. Gaussian processes for data-efficient learning in robotics and control. IEEE transactions pallern analysis and machine intelligence, 37(2): 408 408-423,11 2013.
John D'Errico.
nearestspd. 12885-nearestsp 2025. Accessed: 2025-04-07.
Lukas Fröhlich, Edgar Klenske, Julia Vinogradska, Christian Daniel, and Melanie Zeilinger. Noisy-input entropy search for efficient robust bayesian optimization. In Silvia Chiappa and Roberto Calandra (cds.), Proceedings of the Twenty Third International Conference on Artificial Intelligence and Statistics, volume 108 of Proceedings of Machine Learning Research, pp. 2262 2272. PMLR, 26 28 Aug 2020. URL https://proceeddngg mlr http:/smmrrrrree//eeeeeeeeeeeeee
html
Tan Gemp, Luke Marris, and Georgios Piliouras. Approximating nash equilibria in normal-form games via stochastic optimization. arXiv preprint 23100669006069,,, 2024.
Ian Goodfellow, Jean Couget-Abadie, Mehdi Mirza, Bing Xu, David Warde Warde-Farley, Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. Commamications of the ACM, 63(11): 139 144, 2020.
Kushagra Gupta, Xinjie Liu, Ufuk Topeu, and David Keilvvich-Keil. Second-order algorithms for finding local nash equilibria in zero-sum games. arXiv preprint arXiv:2406.08560 2024.
Minbiao Han, Fengxue Zhang, and Yuxin Chen. No-regret learning of nash cquilibrium for black-box games via gaussian processes. Proceedings of the 40th Conference Uncertainty in Artificial Intelligence, 2024.
Graeme Henkelman, Blas P. Uberuaga, and Hannes Jónsson. A climbing image nudged elastic band method for finding saddle points and minimum energy paths. The Journal of Chemical Physics, 113(22):9901 9904, 12 2000.
Philipp Hennig and Christian J. Schuler. Entropy search for information-efficien global optimization. J. Mach. Learn. Res., 13(mall):1809-1187 jun 2012. ISSN 1532-4435.
Chi Jin, Praneeth Netrapalli, Rong Ge, Sham M Kakade, and Michael Jordan. On nonconvex optimization for machine learning: Gradients, stochasticity, and saddle points. Journal of the ACM (JACM), 68(2): 1-29, 2021.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. In Ekonomíka Matematicheskie Metody, volume 12, pp. 747-756, 1976.
Daniel Lizotte, Tao Wang, Michael Bowling, and Dale Schuurmans. Automatic gait optimization with gaussian process regression. In Proceedings of the 20th International Joint Conference on Artifical Intelligence, San Francisco, CA, USA, 2007. Morgan Kaufmann Publishers Inc.
IJCAP'7, pp.
Eric Luxenberg, Philipp Schicle, and Stephen Boyd. Robust bond portfolio construction via convex-concave saddle point optimization. Xixiv preprint 211::222 0.5570, 2022.
Chinmay Maheshwari, Chih- Chiu, Eric Mazumdar, Shankar Sastry, and Lillian Ratliff. Zeroth-order methods for Nonvex-concave min-max problems: Applications to docision-dependeed risk minimization. In Gustan Camps-Valle Francisco R. Ruiz, and Isabel Valera (ods.), Proceedings of The 25th International Conference on Artificial Intelligence and Statistics, volume 151 of Proceedings of Machine Learning Research, pp. 6702 6734. PMIRR 28 30 Mar 2022.
15

---

Published in Transactions on Machine Learning Research (06/2025)
Eric Mazumdar, Lillian J Ratliff, and S Shankar Sastry. On madienttbbased learning in continuous games. STAM Journal on Mathemalics of Data Science, 2(1):103-131) 131, 2020.
Eric V. Mazumdar, Michael I. Jordan, and S. Shankar Sastry. On finding local Nash equilibria (and only local Nash equilibria) in zero-sum games. ArXiv, abs/1901 10081990,00888, 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In 1. Guyon, U. Von Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), Advances in Neural Information Processing Systems, volume 30. Curran Associates, Inc., 2017.
J. Močkus. On bayesian methods for seeking the extremum. In G. Marchuk (ed.), Optimization Techniques IFTP Technical Conference Nowosibirsk; July 1 1-7, 1974, pp- 400-404, Berlin, Heidelberg, 1975. Springer Berlin Heidelberg,
José Moura and David Hutchison. Game theory for multi-access odge computing: Survey, use cases, and future trends. IEEE Communicatiins Surveys & Tutorials, 21(1):260 288, 2019. doi: 10.1109/CMMST
Arkadi Nemirovski. Prox-method with rate of convergence o(1/() for variational inequalities with lipschitz contimuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229 251, 2004.
J. Nocedal and S. Wright. Numerical Optimization. Springer Series in Operations Research and Financial Engineering. Springer New York, 2006. ISBN 9780387400655. URL fttttp:://books.ogggle.... www.ooin/oooooooo in/books? id=VDHYoSyelFcQ
FM Nyikosa. Adaptive Bayesian oplimizatiin for dynamic problems. PhD thesis, University of Oxford, 2018.
Razvan Pascanu, Yann N. Dauphin, Surya Ganguli, and Yoshua Bengio. On the saddle point problem for non-convex optimization, 2014. URL httpps://arxt..org// obt/:///////aaaeaeoessssoss 4604
Muhammad I. Qureshi and Usman A. Khan. Distributed saddle point problems for strongly concave-convex functions. IEEE Transactions on Signal and Information Processing over Networks, 9:679-690, 2023. doi: 10.1109/TSIPN (00233317800)
Carl Edward Rasmussen, Gaussian processes in machine learning. In Summer school machine learning, pp. 63-71. Springer, 2003.
Lillian Ratliff, Samuel Burden, and S Shankar Sastry. On the characterization of local nash equilibria in continuous games. IEEE transactions on automatic control, 61(8):2301-230) 2016.
J. Revels, M. Lubin, and T. Papamarkou. Forward-mode automatic differentiation in Julia, arXi::1607.0799 MeS, 2016. URL https: http:://axx.v..or//bb///00/ 17881
Ilya O. Ryzhov, Warren B. Powell, and Peter I. Frazier. The knowledge gradient algorithm for a general class of online learning problems. Operations Research, 60(1):180- 1950 2012.
Bobak Shahriari, Kevin Swersky, Ziyu Wang, Ryan P. Adams, and Nando de Freitas. Taking the human out of the loop: A review of bayesian optimization. Proceedings of the IEEE, 104(1):148 175, 2016. doi:
Jasper Snoek, Hugo Larochelle, and Ryan P Adams. Practical bayesian optimization of machine learning algorithms. In F. Pereira, C.J. Burges, L. Bottou, and K.Q. Weinberger (eds.), Advonces in Neural Information Processing Systems, volume 25. Curran Associates, Inc., 2012.
Niranjan Srinivas, Andreas Krause, Sham Kakade, and Matthias Seeger. Gaussian process optimization in the bandit sctting: No regret and experimental design. In Proceedings of the 27th International Conference on International Conference on Machine Learning, ICML'10 10, pp. 1015-1022 Madison, WI, USA, 2010. Omnipress. ISBN 9781 078169558
16

---

Published in Transactions on Machine Learning Research (06/2025)
Simon Stent, Andrew P. Best, Shabnam Hakimi, Guy Rosman, Emily S. Sumner, and Jonathan DeCastro. Adversarial simulation for developing and testing assistive driving technology, Jul 2024.
Richard Sutton and Andrew G Barto. Reinforcement learning: An introduction, second. Brodford Book, 2018.
Jørgen Tind. Saddle Point. Theory and Optimality Conditionns, pp. 3355 3357. Springer US Boston, MA, 2009. ISBN 978-0-387-74759-00 doi: 978-0-387-74759-00557
574. URL
Paul Tseng. On linear convergence of iterative methods for the variational inequality problem. Journal of Compulational and Applied Malhemalics, 60:237-201 252,, 1995.
J. v. Neumann. Zur theorie der gesellschafttssicll.. Mothematische Annalen, 100(1):295-32, 1928. doi: 110007/BF01488841 URL
Zhongruo Wang, Krishnakumar Balasubramanian, Shiqian Ma, and Meisam Razaviyayn. Zeroth-order algorithms for nonconvex strongly-coneave minimax problems with improved complexities, Journal of Global Optimization, 2022. s 10898-022-01160-0
doi:
URL https:://01.oor/110.10000
Julia Westermayr and Philipp Marquetand. Machine learning for electronically excited states of molecules. Chemical Reviews, (21(1))98873 9926, 08 2021. doi: 10.1021/ acs. www.mee..0000099.... URL https:
org/10. 10. 1021/ wwt.///cccceceeeevvecc
chwmrev www.ceeeeoo00000
Yang, Zhigang Ma, Feiping Nie, Xiaojun Chang, and Alexander G Hauptmann. Multi-class active learning by uncertainty sampling with diversity maximization. International Journal of Computer Vision, 113: 113-127, 2015.
17

---

Published in Transactions on Machine Learning Research (06/2025)
Appendix for A Framework for Finding Local Saddle Points in Two-Player Zero-Sum Black-Bou Games
A Technical Insights
18
A.1 UCB and LCB Approach One Another at Sampled Points
18
A.2 Variance of the Sampled Point
20
B Experimental Details
20
B.1
Newton's Method Implementation Details
20
B.2
Gradient Descent-Ascent. with Finite Dillerencing Imp Implementation Details
21
B.3
Local Symplectic Surgery Implementation Detaiss
21
B.4
Decaying Polynomial Implementation Details
21
B.5
High-Dimension Polynomial Implementation Details
21
3.6
ARIMA Tracking Model Predictive Controller (MPC)
21
3.7
Robust MPC Experimental Details
22
B.8
Updating Hyperparameters
22
C Additional Studies
23
C.1 An Example Unsuccessful Runs using the Gradient Descent-Ascent with Finite Differencing
Baseline
23
C.2 An Analysis Using GDA Solve the Lower Level Game
24
A Technical Insights
In this section, we delve into the convergence properties of our proposed algorithms. As mentioned in Sec. 4.3 when we sample local Nash points obtained by Alg, [ the variance in the confidence bounds at that local Nash point decreases, and LCB/UCB converge towards each other eventually at the local Nash point. Lemma A.1 we demonstrate that with zero observation noise, the confidence bounds at a sampled point are equal, L..,, LCBB UCB. Subsequently, in Remark A.2 we explore the more general case involving non-zero observation noise, positing that we repeatedly sample in close proximity to the same point, the variance of the sampled point becomes predominantly dependent the observation noise, resulting in LCB x UCB. Lastly, in Appendix A.2, we provide experimental evidence to corroborate the decrease in the variance of the sampled point during our algorithm's exccution.
Consequently, these results attest that as we sample the local Nash point, the variance in the GP at that point will decrease, and eventually become the observation noise variance, o?. such, the gradient of the variance, Vo + 0, and therefore VLCB, VUCB Vμ. As stated in Sec. 4.3 since Vμ will become a reliable estimator of the true gradients of the unknown function, Vʃ, finding local Nash points of the confidence bounds will eventually lead to local saddle points of μ and consequently of f. This convergence property is key feature of our proposed algorithms, ensuring that the method converges to solution that represents local saddle point of the underlying unknown function.
A.1 UCB and LCB Approach One Another at Sampled Points
For the ease of the proofs, we will focus on the case when r = =f(x) + 2, where 2 N~ N (O,00)) The proof can easily be generalized for f(, y)
18

---

Published in Transactions on Machine Learning Research (06/2025)
Let (ri, (2,..., be the observed values of f when sampled at points X {21, 22,,; Fn). Next, consider some already-sampled point I. E X. Recall that the predictive variance at x. is:
K (2r, 1 (E(X, x) + kin,
(15)
where k, (K(21,, K(2,, a.), K [x)) and E(X, X) E R"x" given by
K (11, K (2)
K (2))
(16)
K (I)) K (2))
K (In)
Lemma A.1 (Equality of UCB, and LCB, at sampled points under zero observation noise). Consider the upper confidence bound, UCB,, and the lower confidence bound, LCB,, for a given time step t. In the case of zero observation noise, i.e., 2t = O, the confidence bounds become equal for any sampled point a such that UCB,(x)= (z),
Proof. Since 2t = 0, the prodictive variance at the point I.
(x. r, = K (I,, k E-k
(17)
Let the point be some point E X, i.c., = for some s S n. Then, the corresponding kernel vector is given by the i-th column of the covariance matrix Σ(X,X) so k, = K = E. and the kernel value is K( (x), = (Ir,,;;) The variance at the new point v. becomes:
(2,, -( -
(18)
Next, we have:
Σ E- =
(19)
where e, is the i-th standard basis vector. This can be seen from the property of the inverse matrix, ie., EXX,X X)= = I, where I is the identity matrix.
Thus, the variance at the new point v. simplifies to:
axx x.) = x() - EJ = K(x;, Ei,--
(20)
Since v. is previously sampled point, the kernel function K(x1, and Ex, are equal to 1. Thus, the variance at I, is:
(x. X, r,,.) =1 11 0.
(21)
This shows that the variance at previously sampled point æ, is zero in the no observation noise case, for any kernel function.
UCB and LCB at the point v. are given by:
UCB,(xx) ph (xx) + Bror (xx), LCB,(x.) pe (I.) Bior (2x).
(22)
Per the variance o, (x.) = at previously sampled point z.. Then:
UCB.(x.) = (C.)( = u4 (x.)
(23)
7
19

---

Published in Transactions on Machine Learning Research (06/2025)
GP Prior Variance Under
GP Prior Variance Under
Zero Observation Noise
With Observation Noise
1.00
1.0
Points Dist
Points Dist
Variance
Variance
0.75
0.8
Metric
Metrio
0.6
0.50
0.4
0.25
0.2
0.00
20
40
60
80
100
Iterations
Iterations
Figure 3: The variance at the sampled points decreases over time. The x-axis indicates the iteration of our method. The y-axis for the blue line presents the distance between two consccutive points for cach function evaluation. The y-axis for the orange line indicates the variance in the GP prior at the sampled points.
Remark A.2 (Approximate equality of UCB and LCB sampled points under observation noise). Consider the upper confidence bound, UCB,, and the lower confidence bound, LCB,, for a given time step t. In the presence of observation noise, i.c., 2 ~ N (0,o?), when the same point is sampled repeatedly, points are sampled, the predictive variance (x) approaches the observation noise og. This is based on the fact that, after repeated sampling, the only uncertainty left about the sampling point will be due to the observation noise. As such, as the predictive variance becomes smaller due to repeated sampling, the confidence bounds at the sampled point r will have (C) x LCB,(x).
nearby
A.2 Variance of the Sampled Point
In Fig. we demonstrate the reduction in the varianco of the sampled points as we approach the saddle point during the execution our algorithms. We compare cases with and without observation noise for a convex-concave objective function of the form ax² bry - cy²; where coefficients a, h, > O, using 10 seeds. We note that LSPs will be locally convex-concave in their neighborhoods, and these results will apply locally in those scenarios. The blue line represents the distance between two consecutive points for each function evaluation, while the orange line indicates the variance in the GP prior at the sampled points. The primary observation is that as we take smaller Newton steps and sample points close to cach other, the variance at those points decreases, thus increasing the accuracy of the mean function and its gradient Vp4 as estimators for the objective function f and its gradient f around the sampled points.
B Experimental Details
We provide the exact implementation details of all the experiments. All experiments were conducted on a desktop computer equipped with an AMD Ryzen 5900X CPU and 32 GB RAM. No GPUs were required for these experiments.
B.1 Newton's Method Implementation Details
To solve for the Newton step p(z,. yr) in 77, the Jacobian matrix Jizs y1) must be non-singular. Therefore, at cach new iteration, we need verify the invertibility of J(r, We). A common way to ensure invertibility is by adding a constant factor XI to the Jacobian. In this work, we choose the damping factor À by using the T.2 norm of the difference between the Jacobian matrix and its nearest.
1. Invertibility of Jacobian:
20

---

Published in Transactions on Machine Learning Research (06/2025)
symmetric positive semidefinite approximation. We obtain the nearest symmetric positive semidefinite matrix to the Jacobian using the method using D D'Errico (2025).
Newton's method alone (with a unit step length) does not guarantee convergence to the root unless the starting point is sufficiently close to the solution. The problem of nonlinear root-finding NNcedal & Wright, 2006 Ch.11) can be reframed terms of minimizing a merit function which is typically the squared norm of the first-order optimality conditions (Nocedal & Wright 2006 Eq. 11.35). To enhance robustness, employ a Wolfe linescarch to ensure sufficient decrease of the merit function M. Thus, our use of linesearch aligns with standard practice, as discussed and explained in Nocedal & Wright 20066
2. Wolfe Linesearch:
Ch.3).
B.2 Gradient Descent-Ascent with Finite Differencing Implementation Details
We utilize JAX (Bradbury et al. 2018 to compute gradients via finite differencing of function samples.
B.3
Local Symplectic Surgery Implementation Details
For LSS, we utilize the same regularization and parameters described by MMazundar et al. 2019 Sec. 5.1). We use ForwardDiff.jl (Revels et al. 2016) for computing gradients for LSS.
B.4 Decaying Polynomial Implementation Details
This scenario the objective function 10) which has decision variables x; y E R. To ensure that algorithms are initialized at points with non-zero gradient in the decaying polynomial example (top row), select initial points from the non-flat regions of the function (a distance between 9 and 18 units from the origin). The Hessian regularization constant is À = 0.01. The strong Wolfe parameters, according to Nocedal & Wright (2006) Ch.3), are e = 0.01 and C2 = 0.7. We add observation noise ~ N' (0, o =1) to each underlying objective function sample. We utilize JAX (Bradbury et al. 2018 to compute gradients for this example.
B.5 High- High-Dimension Polynomial Implementation Details
This scenario uses the objective function 11 which has decision variables x, E R and a combined decision variable 10 dimensions. The Hessian regularization constant is = 0.01. The strong Wolfe parameters, according to Nocedal & Wright (2006) Ch.3), are 6₁ = 0.01 and 02 = 0.7. We add observation noise 2t A (0, of 0.003) to each underlying objective function sample. We utilize JAX (Bradbury et al. 2018 to compute gradients for this example.
B.6 ARIMA Tracking Model Predictive Controller (MPC)
In this experiment, an ARIMA process synthesizes a discrete-time 1D time series of length F, denoted by SF RF for MPC controller to track. Specifically, the ARTMA process generates the time series St+1 μ ast + fwi-1 + Wt, where / R is the mean, w ~ (0,, R is noise, and R, 8 E R are model parameters. Consequently, we represent the ARIMA process for initial state and model parameters a, B: SF ARIMA(s0, 3).
The MPC controller takes the ARIMA time scries, sp, as input and returns a controller cost fMPC E R to track the given time series. The MPC controller solves the following optimization problem:
min MPC(A, B, 80, 8P) = Σ (8, - 8c) Q (8: Sx) + 0, Ru.-
(24a)
i
subject to: 8, A&,-1 + Bå,-1
(24b)
Umin S 44 S Umax
(24c)
The optimization problem has quadratic costs and linear constraints. The quadratic costs (44a) measure how well the controller tracks the timeseries 8f, and how much controller effort used. The linear constraints in
21

---

Published in Transactions on Machine Learning Research (06/2025)
24bj encapsulate the system dynamics, and A, B E R are controller parameters that describe the dynamics. The MPC has additional control constraints in (24op, which describe the control limits of the controller. As such, we represent the optimization problem of the MPC controller as follows: fMPC = (A, B, sF); which returns the final overall cost of tracking the ARIMA-gencrated time series SF, and initial state, &u-
In our experiment, the decision variables were x; E R2, which resulted in a combined decision variable of four dimensions. We set the Hessian regularization constant to À 0.001. Following the recommendations in Nocedal & Wright (2006) Ch.3), we choose strong Wolfe parameters C₁ 0.01 and C2 0.8. Both the parameters of the ARIMA process (a, and the MPC parameters (A, B) are constrained to lie within the range [-1,1]. By incorporating these constraints and paramcters, we ensure a consistent framework for the oplimization problem while providing sufficient flexibility for the ARIMA process and the MPC to interact in the zero-sum game. We utilize CVXPYLAYERS (Agrawal et al. 2019 for computing gradients.
B.7 Robust MPC Experimental Details
In this section, we provide the details of the Robust MPC experiments. In this experiment, we demonstrate that the MPC parameters found at the end of our zero-sum game between the ARIMA antagonist player and the MPC protagonist player will be more robust to out-of-distrbbution data. Our algorithm converges to a local saddle point of this zero-sum game, where both players will be in equilibrium. The ARIMA antagonist player can not find more adversarial parameters for MPC, while MPC can not get better at tracking ARIMA generated forecasts.
Specifically, for the experiment, we compare a nominal MPC with a robust MPC (found using our method) on in-distribution data and distrriiitti data. To generate in-distribution data, we sample 500 ARIMA time series forecasts, 8F, with a, B E [-1,1]. We choose out-of-distribution ARIMA parameters similar the final ARIMA antagonist player parameters. Although the parameters are constrained to be within [-1, 1] during the actual algorithm, select out-of-distribution parameters a -0.1 and B = 11. and sample 500 ARIMA time series forecasts for these parameters. This choice enables us to evaluate the robustness of the MPC against data that deviates from its original training distribution. Finally, we pick nominal MPC parameters, A, B, by fitting the MPC parameters to in-distribution data using supervised learning, i.e, the best A, B to minimize the MPC tracking cost for the in-distribution data. We choose robust MPC parameters as the final MPC protagonist player at the convergence of the zero-sum game. By comparing the performance of the nominal and robust MPCs on both in-distribution and out-of-distribution data, we aim to demonstrate the effectiveness of our method in finding robust MPC parameters that can handle deviations from the original training data distribution better than the nominal MPC.
In Fig. 2. we compare the MPC tracking costs of both the MPCs on in an-distrbbution data and -istr--distributionn data. As expected, the nominal MPC performs better on in-distribution data since it is trained on this data. However, the robust MPC significantly outperforms the nominal MPC on out-of-distribution data by achieving 27.6% lower mean MPC cost. Additionally, the poor performance of the nominal MPC indicates that the final ARIMA antagonist, player parameters are indeed challenging. These results suggest that our algorithm successfully identifies robust MPC parameters and adversarial ARIMA parameters.
B.8 Updating Hyperparameters
Steps for updating M4+1, 0141, UCB4+1, and LCB(+1:
1. Learn hyperparameters of the kernel function using maximum likelihood estimation, as explained in Section 2.3 of Rasmussen (2003).
2. Using the learned hyperparameter and updated kernel function, construct the pe, og using the current dataset, as explained in Eqs. 2.25 and 2.26 in Rasmussen (2003).
3. Construct the new UCB, and LCB,. This straightforward since:
UCB = 14 + 3 or, I.B,, =44 - - dt-
Collect new samples and repeat the process.
22

---

Published in Transactions on Machine Learning Research (06/2025)
Exp Xplore
Exp Xploit
Ef Xploit
EF Xplore
Decaying Polynomial
DecayingPPolynomiin
High-Dimension Polynomial 10D
ARIMA MPC
1.0
1000 initial samples
initial samples
500 initial samples
0.8
Real Merit: M!
0.6
0.4
0.2
0.0
100
150
200
250
1.0
50 initial samples
50 initial samples
10 initial samples
0.8
Real Merit: M!
0.6
0.4
0.2
100
200
300
50
100
150
200
20
40
60
Iterations
Iterations
Iterations
Figure Comparisons of our proposed algorithm variants: We compare all four variants of our proposed algorithms across the three experiments (separated by column) described in Sec. 5 The horizontal axis denotes the number of underlying function evaluations, while the vertical axis represents the value of the real merit function, M The top row considers test cases with large number of initially sampled points, while the bottom row examines test cases with a limited number of initially sampled points. The key takeaway that generally, exploit variants converge faster with a large mumber of initial samples due effective utilization of accurate priors, while explore variants exhibit quicker convergence with limited samples by prioritizing exploration amid uncertainty. Efficiint variants converge faster with many initial samples by (aking multiple accurate Newton steps, while expensive variants show stable, though often slower, convergence with limited samples, taking single Newton steps to avoid unfavorable regions.
C Additional Studies
We generate full convergence rate results for all of our algorithm variants across the decaying polynomial, high-dimension polynomial, and ARIMA-MPC examples. For full discussion our variants, refer the reader lo Sec. 5
The results in Fig. 4 reveal that the explore variants exhibit more reliable convergence to saddle points compared to the exploit variants. This outcome is expected, as explore variants emphasize exploration and, therefore, are more likely to converge. Additionally, the expensive variants demonstrate greater stability in this setting, as they only take single Newton steps and are less prone reaching unfavorable regions. The EF-XPLOIT variant exhibits the lowest success rate in convergence, as relies on exploitation and may take incorrect Newton steps.
C.1 An Example of Unsuccessful Runs using the Gradient Rescent-Ascent with Finite Differencing Baseline
In Fig. 5 we provide a random sample four runs of the gradient descent-ascent with finite differencing on the high-dimension polynomial example. This baseline never succeeds on this testbed, and these examples indicate few of the reasons, including noisy gradient estimates that prevent convergence point that is not saddle, well as leaving the feasible region and never recovering.
23

---

Published in Transactions on Machine Learning Research (06/2025)
Higher-Orde Order Polynomial Function
Saddle Points
Seed 1
Seed
Seed
Seed
x
Figure 5: A random sample of four runs of GDA WITH FD on the high-dimension polynomial. Three of these runs fail because they leave the feasible region and follow the gradient (of the merit. function) away from it. Another fails to find a saddle point due to noise introduced by finite differencing, resulting in convergence to point that not Nash point. Each seod begins at the circle, and cach arrow indicates the direction of the step.
C.2 An Analysis of Using GDA to Solve the Lower-Level Game
In Fig. 6 replace our Newton-based lower-level game solver with first-order gradient-based method, GDA. Using GDA as the lower-level game solver within our method results in low but nonzero success rates for variants EXP-XPLORE (10% success rate), FR-XPLORE (10% success rate), and EXP-XPI.OT (5% success rate). We see better performance using our method with GDA than with the GDA WITH FD baseline, as it now capable of finding saddles, difference mainly accounted for by noise stemming from finite differencing and our use of GPs estimate the objective. Moreover, using Newton's method is significantly better on these examples than the first-order method. This result could be because Newton's 's method better captures curvature information, which is especially important in complex landscapes; true saddle points satisfy second-order conditions, which incorporate such curvature information.
We highlight again that using GDA with finite differencing does not ever find a saddle point. Once we use GDA within our framework, we subsequently do (albeit rarely) find saddle points, showing that our method makes a difference, and we plan to explore this phenomenon further in future work.
In Fig. 7 provide random sample of four runs of our method using gradient descent-ascent solve the lower-level game with the EXP-XPLOIT variant on the high-dimension polynomial example. While our experiments indicate that this method can succeed, as compared to GDA WITH FD, these seeds allow us to inspect some failure modes. Specifically, we see that sometimes the iterates leave the feasible region (red, blue). The grey iterates fail to find a saddle altogether, and the green iterates appear headed in the right direction but fail to arrive at the saddle point.
24

---

Published in Transactions on Machine Learning Research (06/2025)
Xploit
Random
GDA_Exp Xploxe
GDA_Exp_Xplle
- El Xplore
GDA w/
GDA Ef Xplore
1.0
0.8
Real Merit: Mr
0.6
0.4
0.2
0.0
0
50
100
150
200
Num. Function Evaluations
Figure 6: A convergence plot of two variants of our method using GDA to solve the lower-level game in the high-dimension polynomial setting. We compare these variants with other approaches, including the use of Newton's method to solve the lower-level game. Using Newton's method within method performs significantly better than using GDA, perhaps because first-order method is unable to utilize curvature information. We also note that using GDA within the lower-level game finds some saddles (10% for EXP-XPLORE, 10% for EF-XPLORE, 5% for EXP-XPLOTT), whereas GDA WITH FD does not.
Higher-Order Polynomial Function: Method
GDA_Exp [0A__Exp_ploox Xploit
Saddle Points Seed 1
Seed 2
Seed Seed
X
X
Figure 7: A random sample of four runs of our method using GDA within EXP-XPLOR to solve the lover-level game on the high-dimension polynomial. These runs fail because they cither follow the gradient (of the mcrit function) away from the feasible region or move lowards saddle point but fail to reach it (as with the green seed). Each seed begins at the circle, and each arrow indicates the direction of the step.
25


Reviews:
[{"review_id": "lRq7Ud7T6n", "reviewer": "Reviewer_Dh8p", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths : Multiple experiments and baselines. Only reporting runs when the algorithm converges to saddle points is interesting.\n\nWeakness : Several imprecise statements. The Lemma 4.1 is vague. Details are missing in the experiments and the claims made require additional supporting evidence and theory.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper proposes a study of Bilevel Bayesian optimization for min-max optimization. The framework includes a lower algorithm that optimizes for the saddle point based on function samples obtained using an upper algorithm. Comparisons with existing algorithms in the literature are provided with a focus on obtaining saddle point solutions over just stationary points.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Lemma needs to be made precise. Convergence is not defined. Upper bound on the norm of gradients and Jacobians not defined. \n2. The implication of Theorem 11.6 (Nocedal & Wright, 2006) for Algorithm 1 requires proof. This needs to be added.\n3.  Implementation Details. \na) Details for estimating Jacobian and gradients from function samples are missing. \nb) The details of the regularizer used in Newton's step can be added. The regularizer needs to be carefully chosen for convergence.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "dEzgkUUvC9", "reviewer": "Reviewer_8o3V", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper is overall very well-written. The motivation and development of the proposed method is clearly described. I am not familiar with how Gaussian processes are used for regression tasks, and I find that discussion missing. I believe adding that discussion will further enhance the clarity. The modularity/versatility of the method with varied ways of solving the upper/lower level problems is interesting, allowing for trade-off in problems with different structure.\n\nOn the negative side, my main concern is that the paper essentially has no mathematical guarantees, and the authors have not laid out how such guarantees can be derived in future work. This is rare among optimization papers. Even just for solving the lower level problem, te only math result in the main paper, Lemma 4.1, is not meaningful. Simply invoking a known theorem here does not provide much information here. The important thing is to verify that the assumptions made in the theorem are satisfied and therefore applicable. I do not mean to say that every optimization paper needs to have a theoretical analysis. The analysis is a way for us to understand the performance and reliability of the method. If an analysis is not available, extensive simulations should be carried out. The simulation results on the synthetic problems look good, but are not comprehensive enough for us to draw a conclusion in the absence of mathematical guarantees.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper studies two-player zero-sum games (minimax optimization) with a nonconvex-nonconcave objective, in the black-box setting with zeroth-order samples. The main contribution is to propose a hierarchical approach which alternates between building and optimizing a surrogate objective function by sampling at points $(\\bar x^*,\\bar y^*)$ and identifying the good points to sample at. The method allows for plugging in slightly varied algorithms for solving the upper and lower level problem. The authors show that the proposed method works empirically well on a few small-scale problems.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "I have the following questions that I hope the authors can clarify and incorporate in the paper.\n\n* More discussion on GP. What made the authors consider approximating the objective function using a GP? Does using GP require making distributional assumptions on the objective function? How is GP function approximator updated using $\\mathcal{S}_t$?\n\n* >Ultimately in line 4, the function returns the final point, $(\\bar x^*, \\bar y^*), once it discovers a local Nash point.\n\nThis feels a bit misleading, as the convergence to a local Nash point is not guaranteed.\n\n* >However, our primary goal is to establish a foundation for solving these problems. We view this work as a first step and aim to extend our approach to more complex real-world settings in future research.\n\nIn general I agree with the statement. The authors certainly do not have to do everything in this work, but some discussion on how such extensions are possible should be made.\n\n* Regarding simulation results, I am a bit surprised to see how badly GDA with FD performs and would like to understand the reason. What solution is GDA with FD converging to? Can the authors visualize that in the landscape plot? Regarding the statement, \"Random sampling and GDA with FD never converge, though random sampling reduces the merit function value\" -- this is not clear from the figure. Random certainly does not reduce the merit function as fast as the proposed method, but the curve is still going down at the end of 200 iterations.\n\nMinor comments:\n\n* LCB and UCB as a function of both x and y, first used in Eq.(5) are never defined.\n\n* >To frame this problem formally, we must discuss the relationship between Nash points which solve general-sum games and saddle points which solve zero-sum games. \n\nThis gives the impression that you would discuss how the original minimax problem relate to the lower-level general-sum game. But that discussion is not made in this section.", "broader_impact_concerns": "N/A", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "11yEC3Wr1S", "reviewer": "Reviewer_EvAv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "1. This paper studies a new setting---black-box two-player zero-sum problems with Bayesian optimization.\nThis problem may be interesting and useful.\nIndeed, the authors have included a model predictive controller task as an application.\nBut it would be great if the authors can show more applications.\n\n1. The proposed acquisition function uses Newton's method to solve a two-player general-sum game.\nIt is well-know that Newton's method (without cubic regularization) may converge to arbitrary stationary points.\nHowever, to solve a two-player general-sum game, one needs convergence to local Nash equilibria (a particular type of stationary points).\nThus, I am not sure if using Newton's method is sensible.\nFor this reason, I am very interested in seeing how well do first-order methods perform when optimizing this acquisition function.\n\n1. Some important implementation details are missing.\nIt is unclear to me how Newton's method is implemented, even after reading the appendix.\n    - For one, I am not sure how the Wolfe linear search is implemented for the two-player game, given that the Wolfe condition is typically used in minimization problems.\n    My impression is that the authors use the line search to ensure sufficient decreases in the gradient norm Eq (6).\n    However, this is different from the standard Wolfe condition, which aims for decreases in the objectives.\n    - For another, it is unclear how the damped factor \\\\(\\lambda \\mathbf{I}\\\\) in Newton's method is chosen (which is added to the Jacobian matrix).\n    Note that this is not just about the invertibility of the Jacobian.\n    It also affects the curvature which determines the stationary point that Newton's method converges to.\n\n1. Lemma 4.1 is quite sloppy.\n    - First, Theorem 11.6 of Nocedal and Wright (2006) is a statement for minimization problems, not for two-player games.\n    I am not sure if their theorem applies here at all.\n    A key difference is that the Hessian in minimization problems are always symmetric, whereas Eq (7) in this paper is not.\n    Also, the Wolfe line search implemented in this paper seems to be different from the Wolfe line search for minimization problems.\n    - Second, even if their theorem applies, it only guarantees convergence to stationary points, not local Nash equilibria.\n    So the name of the lemma needs to be changed.\n    - Third, Nocedal and Wright (2006) actually requires an additional technical assumptions to guarantee convergence to stationary points; see (11.41) the condition on the angles \\\\(\\theta_k\\\\) in the book.\n    This one is a minor issue though.\n\n1. The evaluation metric in Figure 1 is somewhat be questionable.\nFigure 1 aims to show faster convergence of the proposed methods.\nHowever, the \\\\(y\\\\)-axis (the merit function) is the gradient norm.\nThus, it only measures how fast those methods converge to stationary points, not local Nash equilibria.\n\n1. I was very confused when reading Table 2.\nBased on the numbers, BSP-efficient-exploit (Ef-Xploit) has the highest success rates in all three tasks.\nHowever, the text seems contradictory.\nCan you clarify this?\n    - \"The results reveal that the explore variants exhibit more reliable convergence to saddle points compared to the exploit variants.\"\n    - \"The Ef-Xploit variant exhibits the lowest success rate in convergence..\"", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "No", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper proposes a Bayesian optimization method for black-box two-player zero-sum games.\nThe authors use a Gaussian process surrogate model and propose a new acquisition function for this new setting.\nThe acquisition function aims to find a local Nash equilibrium of a two-player general-sum game, where the player one minimizes the lower confidence bound and the player two maximizes the upper confidence bound.\nThe two-player general-sum game is solved by Newton's method.\nThe authors present experiments on two synthetic functions and a model predictive control task.", "claims_and_evidence_yn": "No", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "1. Add the implementation details of Newton's method.\n1. Either polish Lemma 4.1 or remove it.", "broader_impact_concerns": "No ethical concerns.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "bbK98tNmWl", "reviewer": "Reviewer_GuHF", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The setting is interesting and the paper is easy to understand\n- Experimentally the algorithm is validated across multiple meaningful full scenarios\n\nWeakness:\n- The theoretical result is not clear (or formal).  ||J(x, y) −1 || , ∥J(x, y)∥ and ∥G CBt (x, y)∥ have upper bounds? Can you give sufficient conditions for this? Does the result hold for any epsilon? Do you need data to be concentrated around Nash Point?    \n- Results are weak; Authors can try to provide convergence rates (regret) which are typical in GPs. Depending on kernels GPs can have good contraction rates which can be used to provide convergence rates. (if authors search for no regret, GP's and Nash equilibrium then there are some work in this direction already)\n- Currently, the result holds if there is infinite data then the algorithm will eventually converge which may not be so practical.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "Yes", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The paper attempts a staddle point optimization problem. Their setting deals with unknown objectives (optimizing with samples from unknown) and focuses on non-convex problems. They propose a bilevel method to solve the problem. The high-level models the unknown function using GP and returns the confidence bounds (conditioned on the data gathered so far) and the low-level solves the corresponding problem with confidence bounds. This solution sets the next query point. The algorithm runs until some merit function is below an epsilon threshold. Authors experimentally validate their algorithm.", "claims_and_evidence_yn": "Yes", "claims_explanation": "", "audience_yn": "Yes", "audience_explanation": "", "requested_changes": "flexibly integrate existing and novel approaches to this problem --> vague \n\nadd an explanation of zeroth-order samples when used the first time.\n\nThere may be two points in which one may not be better than the other. Does there always exist a global saddle point and is it unique? Any comments on this around def 3.1?\n\nHow do you solve (5)? Add a could of sentences around that\n\nIf ||J(x, y) −1 || has an upper bound? --> Where is this required in the lemma (for intuition)", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The reviewers find the contribution of this work meaningful despite many limitations. This paper approaches the two player game from GP perspective, that only is semi-sound for low dimensional setting. This does not address the present challenges in two player games in RL, GANs, control, and many more setting.
Decision: Accept (poster)