Min-Max Optimization Requires Exponentially Many Queries
arXiv:2605.13806v1 [cs.DS] 13 May 2026
Martino Bernasconi∗
Matteo Castiglioni†
Bocconi University
Politecnico di Milano
Andrea Celli∗
Alexandros Hollender
Bocconi University
University of Oxford
Abstract We study the query complexity of min-max optimization of a nonconvex-nonconcave function f over [0, 1]d × [0, 1]d . We show that, given oracle access to f and to its gradient ∇f , any algorithm that finds an ε-approximate stationary point must make a number of queries that is exponential in 1/ε or d.
∗ Martino Bernasconi and Andrea Celli were supported by an ERC grant (Project 101165466 — PLA-STEER). † Matteo Castiglioni was supported by the FAIR (Future Artificial Intelligence Research) project PE0000013, funded by the NextGenerationEU program within the PNRRPE-AI scheme (M4C2, Investment 1.3, Line on Artificial Intelligence), and by the EU Horizon project ELIAS (European Lighthouse of AI for Sustainability, No. 101120237).
1
1
Introduction
In this paper, we consider the following constrained min-max optimization problem min max f (x, y)
x∈X y∈Y
(1)
where X, Y ⊂ Rd are compact convex sets, and f : X × Y → R is continuously differentiable with Lipschitzcontinuous gradient ∇f .1 This problem has wide practical relevance, as it is a fundamental component in optimization and machine learning applications such as generative adversarial networks [Goo+14], robustness to adversarial attacks [Mad+18; Raz+20], and, most recently, large language model [Swa+24; Liu+24; Mun+24; Sun+25; Pau+25] (see also Daskalakis [Das22] for a broader discussion on the importance of this problem in optimization and machine learning). The problem can be solved efficiently in the case where f is convex-concave, i.e., when x 7→ f (x, y) is convex for all y ∈ Y , and y 7→ f (x, y) is concave for all x ∈ X. Namely, an ε-approximate (global) optimal solution of (1) can be identified using at most poly(d, log(1/ε)) queries to f and ∇f [RN23; Ana+25]. However, as soon as we let the function f be only nonconvex-concave (or, analogously, convex-nonconcave), the problem already becomes harder to solve. Indeed, it is easy to see that it is at least as hard as a constrained nonconvex minimization problem of the form min g(x) (2) x∈X
where g is continuously differentiable with Lipschitz-continuous gradient ∇g. This is immediate by setting f (x, y) := g(x). Importantly, since g can be nonconvex, it is known that we cannot hope to efficiently locate the approximate position of a global minimum, or even a point with an objective function value close to that of a global minimum [Vav95]. Instead, a more tractable solution concept for the optimization problem (2) is an approximate local minimum, or, more precisely, an approximate constrained first-order stationary point. This is also called an approximate Karush-Kuhn-Tucker (KKT) point, and corresponds to an ε-approximate fixed point of the projected gradient descent operator. It is well known that such a point can be found with at most O(1/ε2 ) first-order queries, for example, by projected gradient descent. Moreover, this dependence on ε is unavoidable in the worst case: no algorithm can find an ε-approximate KKT point of (2) with fewer than poly(1/ε) queries [Vav93; Car+20]. A similar picture holds for the nonconvex-concave case of the min-max problem (1). In this setting, one can still compute an appropriate local solution using at most poly(d, 1/ε) first-order queries [Nou+19; LJJ20; OLR21]. Thus, in both nonconvex minimization and nonconvex-concave min-max optimization, local solution concepts remain algorithmically tractable, although the dependence on the accuracy is necessarily polynomial. Unfortunately, in most practical applications the function f (x, y) is neither convex in x, nor concave in y. Also in this setting, the focus shifts toward the less ambitious goal of finding local solutions to problem (1). Many notions of local solutions have been proposed for the problem (1), see, e.g., Jin, Netrapalli, and Jordan [JNJ20] for an overview. In this work, we focus on ε-approximate (constrained) stationary points, namely a tuple (x, y) ∈ X × Y such that −∇fx (x, y)⊤ (x′ − x) ≤ ε
and ∇fy (x, y)⊤ (y ′ − y) ≤ ε ∀(x′ , y ′ ) ∈ X × Y.
This is a weak first-order condition: it merely requires that neither player has a feasible first-order improving direction larger than ε. This notion is very weak in the sense that it is necessary for the standard local optimality notions considered in the min-max literature, including local min-max points and local saddle points.2 This is favorable in our case, since we will provide lower bounds, thereby strengthening our results. First-order stationary points can also be viewed as fixed points of the projected gradient descent-ascent map, 1 Here, and in the rest of this discussion, we assume that both f and ∇f are 1-Lipschitz continuous. This is without loss of generality, as it can be achieved by a simple rescaling of the function. Similarly, we also assume that X, Y ⊆ [0, 1]d , which can also be ensured by rescaling the domain. This will allow us to express bounds solely in terms of the approximation error and the dimension d. 2 Unfortunately, the terminology for these solution concepts is not fully standardized across the literature.
2
just as KKT points of a minimization problem are fixed points of projected gradient descent. However, in contrast to minimization problems, it is well known that gradient descent-ascent dynamics exhibit cycling behavior and thus do not yield an algorithm guaranteed to find such solutions [MPP18; DP18]. This contrast naturally leads to the following question: When f is nonconvex-nonconcave, can an ε-approximate first-order stationary point of the min-max problem (1) be found using at most poly(d, 1/ε) queries? In this paper, we answer this question in the negative. Namely, we show that any algorithm finding an ε-approximate solution must make a number of queries that is exponential in d or in 1/ε. This shows that finding approximate stationary points of (1) is significantly harder than in the corresponding minimization problem (2). In particular, our result implies that nonconvex-nonconcave min-max optimization does not admit an efficient gradient-descent-type algorithm. A negative result of this form was already known for the more general case of joint constraints, i.e., min max f (x, y)
x∈Rd y∈Rd
s.t.
(x, y) ∈ P
(3)
where P is a convex polytope. Daskalakis, Skoulakis, and Zampetakis [DSZ21] proved that any algorithm that finds an ε-approximate solution of (3) must make a number of queries that is exponential in d or in 1/ε. Note that problem (3) is more general than (1), because it allows joint constraints between x and y, meaning that P cannot be decomposed as a product P = X × Y . As discussed by Bernasconi, Castiglioni, Celli, and Farina [Ber+24], the joint constraints are used in a crucial way in the work of Daskalakis et al. [DSZ21].3 Therefore, their result does not apply to the more natural setting of problem (1), i.e., when we have product constraints (meaning that the feasible choices of x and y are independent at the level of the constraint set). Determining the query complexity under product constraints (i.e., our main open question stated above) remains a major open problem, as recently discussed in a column in the SIAM Activity Group on Optimization newsletter [Dia25]. A very recent result of Bernasconi and Castiglioni [BC26] established that finding approximate first-order stationary points of problem (1), i.e., nonconvex-nonconcave min-max optimization with product constraints, is PPAD-hard. This means that when the function f and its gradient ∇f are provided as arithmetic circuits or Turing machines, then the problem cannot be solved in polynomial time, unless PPAD = P. Importantly, as mentioned in Bernasconi and Castiglioni [BC26, Section 8], their result does not imply a query lower bound for the problem, because their reduction is not black-box : it reduces from a purely white-box problem called PureCircuit [Del+24]. They ask the question of whether it is possible to improve their reduction so as to also obtain a query lower bound for the problem. In this work, we show that this is indeed possible. Our improved reduction resolves the main open question stated above. Our Contribution. We consider the min-max optimization problem (1) with the simple domain X = Y = [0, 1]d and show that any algorithm that finds an ε-approximate first-order stationary point must make a number of queries to f and ∇f that is exponential in 1/ε or d. To be more precise, we prove the following theorem.4 Theorem 1.1 (Informal version of Theorem 6.1). Any algorithm that outputs an ε-approximate stationary point for problem (1), must make at least a number of queries to f or ∇f that is exponential in d, even when ε is inversely polynomial in d. This provides an unconditional lower bound for the problem, as opposed to the conditional time-complexity lower bound of Bernasconi and Castiglioni [BC26], which only holds if PPAD ̸= P. Furthermore, our lower 3 In fact, the lower bound proved by Daskalakis et al. [DSZ21] for joint constraints even applies to the setting where f is nonconvex-concave. Since such problems can be solved using poly(d, 1/ε) queries under product constraints, this shows that the hardness result in [DSZ21] fundamentally relies on joint constraints. 4We use the term “exponential in x” in the weak sense, i.e., to mean 2Ω(xc ) for some absolute c > 0, as opposed to 2Ω(x) .
3
bound even rules out algorithms that are allowed to perform unbounded computation between queries. Chen, Li, and Yannakakis [CLY24] recently gave such a query-efficient but time-inefficient algorithm for the problem of computing a fixed point of a contraction map. Theorem 1.1 shows that no such algorithm exists for nonconvex-nonconcave min-max optimization. Our Techniques. As mentioned above, the main obstacle to obtaining a query lower bound from the construction of Bernasconi and Castiglioni [BC26] is the usage of the PureCircuit problem in their reduction. The PureCircuit problem was introduced by Deligkas, Fearnley, Hollender, and Melissourgos [Del+24] as a tool for proving very strong inapproximability results in the context of PPAD. Importantly, it is a purely white-box problem, meaning there is no oracle in the problem definition and the algorithm has full knowledge of the instance. Thus, it cannot be used to prove a query lower bound for our min-max problem. The natural thing to do is to try to replace the PureCircuit problem in the reduction by some other Brouwer-like problem. The issue with this is that the reduction of Bernasconi and Castiglioni [BC26] heavily relies on the fact that the gates of the PureCircuit problem are very flexible and allow for a lot of error without breaking. This fact is also precisely why PureCircuit has been so useful in proving PPAD-hardness for various approximation problems in game theory and beyond. Unfortunately, black-box Brouwer-like problems, for which query lower bounds are known, do not offer this flexibility. We resolve this issue by introducing a black-box version of the PureCircuit problem, which we call OraclePureCircuit. The definition of this new problem is identical to PureCircuit, except that the problem has been augmented with one additional type of gate, which we call an oracle gate. The OraclePureCircuit problem allows us to achieve our two desiderata: (i) keeping the simplicity and flexibility of PureCircuit, while also (ii) having a problem that has an exponential query lower bound. Indeed, the query lower bound for OraclePureCircuit follows relatively easily by adapting the existing PPAD-hardness proof for PureCircuit from [Del+24], as we show in Section 3. What remains then is modifying the reduction of Bernasconi and Castiglioni [BC26] so that it uses OraclePureCircuit instead of PureCircuit. In particular, this entails implementing the newly introduced oracle gate. Another part of the reduction of Bernasconi and Castiglioni [BC26] breaks when we try to use it to prove query lower bounds. Indeed, they reduce from two different problems: one of which is the PureCircuit discussed above, and the other one is a problem related to linear variational inequalities, which is also not a query-hard problem; however, the modification of this part of the reduction is more standard, and we solve it by defining a smooth version of Brouwer’s fixed point theorem, as detailed in Sections 4 and 5. Finally, the proof culminates in Section 6, where we put everything together to prove Theorem 1.1.
2
Preliminaries
Mathematical Notation. For a function F : [0, 1]d → Rm , we say that F is G-Lipschitz if ∥F (x)−F (x′ )∥ ≤ G∥x − x′ ∥, and L-smooth if ∥JF (x) − JF (x′ )∥2 ≤ L∥x − x′ ∥2 , where JF (x) ∈ Rm×d is the Jacobian and ∥ · ∥ denotes the Euclidean norm for vectors and the spectral norm for matrices. For a matrix A ∈ Rm×n , let ∥A∥max := maxi,j |Aij |. For x ∈ Rd and r ≥ 0, let Br∞ (x) := {y ∈ Rd : ∥x − y∥∞ ≤ r}. For f : Rn → R, we denote by D2 f (x) ∈ Rn×n its Hessian. For g : R → R, let ∥g∥∞ := supx∈R |g(x)|. Finally, [n] := {1, . . . , n}, and C k denotes the class of functions whose partial derivatives up to order k are continuous. The main result of the paper is a query lower bound for the following problem, which concerns finding approximate fixed points of gradient descent-ascent dynamics (GDA). Problem 1 (GDA-FixedPoint). Given ε, L, G, B ∈ R+ , two oracles implementing a G-Lipschitz and L-smooth function f : [0, 1]d × [0, 1]d → [−B, B] and its gradient ∇f : [0, 1]d × [0, 1]d → R2d , find (x⋆ , y ⋆ ) ∈ [0, 1]d × [0, 1]d such that for all i ∈ [d], xi ∈ [0, 1] and yi ∈ [0, 1] −∂xi f (x⋆ , y ⋆ )(xi − x⋆i ) ≤ ε and
∂yi f (x⋆ , y ⋆ )(yi − yi⋆ ) ≤ ε.
As also mentioned in the introduction, the naming of the problem is motivated by the problem being computationally equivalent to finding an approximate fixed-point of the GDA map (x, y) 7→ (Π[0,1]d (x − ∇x f (x, y)), Π[0,1]d (y + ∇y f (x, y))), as shown by Daskalakis et al. [DSZ21]. 4
Our query lower bound ultimately comes from known lower bounds for finding a Brouwer fixed point. Specifically, we will use the following discrete Brouwer-like problem, called StrongSperner.5 Problem 2 (StrongSperner). Given integers M, d, and oracle access to a labeling λ : [M ]d → {−1, +1}d satisfying the following boundary conditions for every i ∈ [d]: xi = 1 =⇒ [λ(x)]i = +1
and xi = M =⇒ [λ(x)]i = −1,
output x(1) , . . . , x(d) ∈ [M ]d such that maxi,j∈[d] ∥x(i) − x(j) ∥∞ ≤ 1, and such that all labels are covered, i.e., for all i ∈ [d] and ℓ ∈ {−1, +1} there exists j ∈ [d] with [λ(x(j) )]i = ℓ. The following query lower bound for StrongSperner easily follows from the seminal query lower bound of Hirsch, Papadimitriou, and Vavasis [HPV89] for finding Brouwer fixed points. Theorem 2.1. There exists a sufficiently large constant integer M such that any algorithm that outputs a solution to StrongSperner with parameters M and d must make 2Ω(d) many queries to the labeling λ. Daskalakis et al. [DSZ21, Corollary 9.2] prove a weaker version of Theorem 2.1 where M is only assumed to be O(d), instead of constant. However, it is not hard to see that the work of Hirsch et al. [HPV89] in fact implies that M can be fixed to a constant. For completeness, we provide a proof of this in section A.
3
The OraclePureCircuit Problem
In this section, we introduce the OraclePureCircuit problem, which is a black-box version of the PureCircuit problem of Deligkas et al. [Del+24], and prove a query lower bound for it. Problem 3 (OraclePureCircuit). An instance of OraclePureCircuit is given by a natural number N , a set of nodes V , three sets of gates GNor , GPurify , and GOracle , and oracle access to a function L : {0, 1}N → {0, 1} (with N ≤ |V |). Each gate is of the form (u1 , u2 , . . .) where ui are distinct nodes in V with the following interpretation: • if (u, v, w) ∈ GNor , then u and v are the inputs of the gate, and w is its output. • if (u, v, w) ∈ GPurify , then u is the input of the gate, and v and w are its outputs. • if (u1 , . . . , uN , v) ∈ GOracle , then u1 , . . . , uN are the inputs of the gate and v its output. Each node is the output of exactly one gate. A solution to an instance of OraclePureCircuit is an assignment b : V → {0, 1, ⊥} that satisfies all the gates, i.e., for each gate we have: • if (u, v, w) ∈ GNor , then b satisfies: b(u) = b(v) = 0 =⇒ b(w) = 1 (b(u) = 1) or (b(v) = 1) =⇒ b(w) = 0, • if (u, v, w) ∈ GPurify , then b satisfies: {b(v), b(w)} ∩ {0, 1} ̸= ∅ b(u) ∈ {0, 1} =⇒ b(v) = b(w) = b(u), • if (u1 , . . . , uN , v) ∈ GOracle , then b satisfies: (b(u1 ), . . . , b(uN )) ∈ {0, 1}N =⇒ b(v) = L(b(u1 ), . . . , b(uN )). 5 This problem was first defined by Daskalakis et al. [DSZ21], where it was called HighD-BiSperner. Later, it was used by Deligkas et al. [Del+24] under the name StrongSperner to prove the PPAD-hardness of PureCircuit.
5
1 5 6
ϕc1 ,c2 (x)
1
0 ( 12 , 1)
2 3
1 2
x2
1
(0, 21 )
1 3 1 6
c1
c2
x
(a) The smooth step function of Lemma 1.
0
(0, 12 )
( 12 , 1)
0
1 1 6
1 3
x1
2 3
5 6
1
(b) Schematic illustration of the interpolation presented in Lemma 2 for N = 2 and ĥ(x1 , x2 ) = XOR(x1 , x2 ).
Figure 1 The PureCircuit problem originally defined by Deligkas et al. [Del+24] is the same as our OraclePureCircuit, but without the oracle gates GOracle . In OraclePureCircuit we have introduced oracle gates in the least constraining way: a gate of type GOracle is only required to be correct when all its inputs are actual bits (i.e., no ⊥). Just like PureCircuit, our version is also always guaranteed to have a solution. This can be proved directly, and it also follows from our reduction to GDA-FixedPoint, which is known to always have a solution [DSZ21]. As mentioned in the introduction, PureCircuit is PPAD-complete, but does not admit a query lower bound, because it is a purely white-box problem. In contrast, for OraclePureCircuit we can show the following. Theorem 3.1. Given an instance of OraclePureCircuit with |V | nodes, any algorithm that has black-box 1/3 oracle access to L and outputs a solution to OraclePureCircuit requires 2Ω(|V | ) queries to L. Proof sketch. The query lower bound is obtained by constructing a reduction from StrongSperner with dimension d, for which a 2Ω(d) query lower bound is known by Theorem 2.1. To do this, we modify the existing reduction from the white-box version of StrongSperner to PureCircuit, provided by Deligkas et al. [Del+24]. Namely, whenever the standard PureCircuit gates are used to implement the Boolean circuit of the white-box version of StrongSperner, we instead use the oracle gate to implement the oracle of the black-box version of StrongSperner. Using the fact that the parameter M of StrongSperner can be assumed to be constant (by Theorem 2.1), we argue that the number of gates in the OraclePureCircuit 1/3 instance is at most O(d3 ), which yields a query lower bound of 2Ω(|V | ) . For the details of the proof, we refer to Section B.
4
Smooth Interpolation of a Boolean-Valued Function
To bridge the gap between discrete Boolean circuits and continuous optimization, we require a mechanism for extending Boolean functions to the continuous domain. Specifically, we seek a C ∞ interpolation over [0, 1]N of a Boolean function defined only on {0, 1}N . In pursuit of this gadget, we first consider a smooth-step function. Namely, given two values c1 , c2 , we use a standard C ∞ non-analytic function ϕc1 ,c2 , which implements a smooth step-function that interpolates the step function that is 0 below c1 and 1 above c2 . Definition 1 (Smooth step function). Let c2 > c1 ≥ 0. The function ϕc1 ,c2 : R → [0, 1] is defined as ϕc1 ,c2 (x) =
η(x − c1 ) , η(x − c1 ) + η(c2 − x)
where η : R → [0, 1] is defined as η(x) = I(x > 0) exp(−1/x).
6
The main properties of ϕc1 ,c2 are summarized in the next lemma. Basically, it guarantees that ϕc1 ,c2 implements a smooth step from c1 to c2 and that its derivative is bounded by a constant (depending on c1 and c2 ). An illustration of such a function can be found in Figure 1a. Lemma 1. Given two c1 < c2 , the function ϕc1 ,c2 is in C ∞ and satisfies: If x ≤ c1 {0} ϕc1 ,c2 (x) ∈ (0, 1) if x ∈ (c1 , c2 ) . {1} if x ≥ c2 2
4
Moreover, ∥ϕ′c1 ,c2 ∥∞ ≤ e c2 −c1 , and ∥ϕ′′c1 ,c2 ∥∞ ≤ 12e c2 −c1 . The main use of the smooth step function in Definition 1 is to extend a Boolean function ĥ defined on the hypercube vertices {0, 1}N to a continuous function h over the domain [0, 1]N . Besides being consistent on the vertices of the hypercube, we require it to be robust: the function h(x) = ĥ(v) whenever x belongs to a “large” neighborhood of the vertex v. Moreover, another critical requirement for this interpolation is query efficiency: the value of the interpolated function at any point x ∈ [0, 1]N must be computable using only a polynomial number of queries to the original function. Lemma 2. Let ĥ : {0, 1}N → {0, 1} be a Boolean function. There exists a smooth C ∞ function h = H(·, ĥ) : [0, 1]N → [0, 1] that satisfies N (i) ĥ(y) = h(x) for all y ∈ {0, 1}N and all x ∈ B1∞ ; /6 (y) ∩ [0, 1]
(ii) h(x) ∈ [0, 1] for all x ∈ [0, 1]N ; (iii) h(x) and ∇h(x) are computable with at most one call to ĥ for all x ∈ [0, 1]N ; 12
(iv) ∥∇h(x)∥∞ ≤ e2 , and ∥D2 h(x)∥max ≤ 6e24 for all x ∈ [0, 1]N . The construction of the interpolating function H(·, ĥ) is explicit and can be found in the proof of Lemma 2. In Figure 1b, we provide an illustrative example. The reason why we need a robust version of the interpolation will be discussed in the next section (and in particular in Remark 2).
5
An Oracle-Efficient Reduction From OraclePureCircuit to SmoothBrouwer
As already mentioned, we will also rely on the following intermediate problem, which concerns the approximation of fixed points of a continuous function. This problem will be used in Section 6, in combination with OraclePureCircuit, to construct a query-hard instance for GDA-FixedPoint. Problem 4 (SmoothBrouwer). Given an approximation ε > 0 and an oracle implementing a Lipschitz and C 1 function F : [0, 1]d → [0, 1]d and its Jacobian JF : [0, 1]d → Rd×d , find a z ∈ [0, 1]d such that ∥F (z) − z∥∞ ≤ ε. The following theorem provides an oracle-efficient reduction from OraclePureCircuit to SmoothBrouwer. In this construction, we rely heavily on the robustness of our interpolation as described in Lemma 2, and on the smooth step function introduced in Definition 1. Theorem 5.1. There is a reduction from an instance of OraclePureCircuit (with oracle L) to Smooth1 Brouwer with approximation ε = 12 , such that: • C ∞ ∋ F : [0, 1]d → [0, 1]d where d = |V | is the number of nodes of OraclePureCircuit; 7
• any query to F or JF can be simulated with at most d = |V | queries to L; • we can efficiently recover a OraclePureCircuit solution from any SmoothBrouwer one; • the function F is (e12 d)-Lipschitz and (12e24 d2 )-smooth, and |∂zj Fi (z)| ≤ e12 for all i, j ∈ [d]. As a corollary, since the oracles of SmoothBrouwer can be simulated with poly(d) queries to the oracle L of OraclePureCircuit, and we can recover a solution of OraclePureCircuit from any solution of SmoothBrouwer, we obtain an exponential lower bound on the number of queries required by SmoothBrouwer, recovering a similar result to that of Hirsch et al. [HPV89]. 1 Corollary 1 (Exponential query-lower bound for SmoothBrouwer). For ε = 12 , SmoothBrouwer Ω(dc ) requires at least 2 queries to the F and JF oracles for some constant c > 0.
It is important to make two comments regarding this result. Remark 1. We need such a stronger result on the query complexity of SmoothBrouwer, since the historical version of Hirsch, Papadimitriou, and Vavasis [HPV89] only produces functions F that are Lipschitz but not C 1 . Indeed, in our final GDA-FixedPoint construction, the oracle implementing the gradient ∇f is simulated using JF , so JF must be continuous for f to be smooth. Remark 2. The robustness of the interpolation of Lemma 2 is essential in the reduction from OraclePureCircuit to SmoothBrouwer since approximate fixed points only recover inputs that are close to Boolean vertices rather than exactly Boolean.
6
Exponential Lower Bound for GDA-FixedPoint
In this section, we combine OraclePureCircuit and SmoothBrouwer to provide a query-hard instance of GDA-FixedPoint. Starting from an instance of OraclePureCircuit with oracle L on m = |V | nodes, we first construct, via Theorem 5.1, a SmoothBrouwer instance F : [0, 1]m → [0, 1]m , where m = |V |. We then build a GDA-FixedPoint instance in the spirit of Bernasconi and Castiglioni [BC26], using many copies of SmoothBrouwer placed inside nodes of the OraclePureCircuit instance. The major difference with respect to the proof of Bernasconi and Castiglioni [BC26] is that we replaced the linear variational inequality used there with the SmoothBrouwer map F as the inner problem. 1 Let m be the size of the SmoothBrouwer map, i.e. F : [0, 1]m → [0, 1]m , and let ρ = 12 the approximation error. Recall that by Theorem 5.1 it holds m = |V |. We construct the GDA-FixedPoint instance based on the following parameters: 4
ρ δ = 400m 2 e26 ,
n=
213 e13 m4 δ3
,
and
ε = min
δ δ2 n , m4 24 e14
.
u For each u ∈ V , i ∈ [n], j ∈ [m], our instance includes variables xui,j and yi,j , so the dimension 2 12 v of each player is d = |V |nm = nm = O(m ). Moreover we abbreviate xi = (xvi,j )j∈[m] ∈ Rm and xv := (xvi,j )i∈[n],j∈[m] ∈ Rmn (and similarly with yiv ∈ Rm and y v ∈ Rmn ). Before defining the objective f , it is useful to define, using F , the gadget: X xv + y v xv + y v i i i Hv (x, y) = F − i , yiv − xvi , 2 2 i∈[n]
and the “thresholded energy function”: Ev (x, y) = ϕ3m,3m+1 (∥xv − y v ∥2 ), that is a smooth step function that is 0 if ∥xv − y v ∥2 is less that 3m and 1 if it is bigger than 3m + 1.
8
Moreover, for each w ∈ V , we define a “signal” function sw (x, y) depending on the (unique) gate type w is output of. To do so, we use specific functions depending of the gate type. Formally, we set g(Eu (x, y) + Ev (x, y)) if (u, v, w) ∈ GNor ℓ(E (x, y) − 1/4) if (u, w, v) ∈ GPurify u sw (x, y) = ℓ(Eu (x, y) + 1/4) if (u, v, w) ∈ GPurify H((Eui (x, y))i∈[N ] , L) if (u1 , . . . , uN , w) ∈ GOracle where g(z) = ϕ1/3,2/3 (1 − z) and ℓ(z) = ϕ5/12,7/12 (z). Finally, we let the objective X
f (x, y) =
sw (x, y) · Hw (x, y) + φ(x, y),
(4)
w∈V
P P w 2 where φ(x, y) = w∈V i∈[n] Mi ∥xw i − yi ∥2 and Mi := δ(i − n/2). Here, it becomes apparent the necessity of a smooth version of a query-hard Brouwer function F , since it is evident that the gradient of f will depend on JF through the derivatives of Hw . Moreover, it is easy to see that, since all components of f have bounded first and second order derivatives, thanks to Lemmas 1 and 2, then ∥f ∥∞ , ∥∇f ∥∞ , ∥D2 f ∥∞ = poly(d) and thus also G, L, B = poly(d). Thus, to complete the proof, we just need to show that: 1. Correctness: given a solution to GDA-FixedPoint, we can recover a solution to either the OraclePureCircuit or the SmoothBrouwer instance, and hence of the OraclePureCircuit one by Theorem 5.1. 2. Oracle Query Complexity: any call to f or ∇f requires at most a polynomial number of calls to the OraclePureCircuit oracle L. Notice that these also include calls to the SmoothBrouwer oracles F and JF , which in turn are implemented through queries to the OraclePureCircuit oracle L by Theorem 5.1. Indeed, if an algorithm solves GDA-FixedPoint in T (d) oracle queries to (f, ∇f ), then this would give an algorithm for OraclePureCircuit with |V | nodes that runs in T (poly(|V |))poly(|V |) queries, but the OraclePureCircuit lower bound of Theorem 3.1 forces this quantity to be exponential in |V | and in turn c implies T (d) = 2Ω(d ) for some constant c > 0. From any solution (x, y) of GDA-FixedPoint and define an assignment b : V → {0, 1, ⊥} as ( Ev (x, y) if Ev (x, y) ∈ {0, 1} b(v) = . (5) ⊥ otherwise Then, we can show the following dichotomy in the same spirit of Bernasconi and Castiglioni [BC26]: either the decoded Boolean signals b : V → {0, 1, ⊥} are consistent with all gate outputs (and thus satisfy the OraclePureCircuit constraints), or one of the replicated blocks (v, i) ∈ V × [n] already yields an approximate fixed point of the SmoothBrouwer instance. Formally: Lemma 3 (Dichotomy). Let (x, y) be a solution to GDA-FixedPoint. Then either there exists i ∈ [n], v ∈ V such that (xvi + yiv )/2 is a solution to SmoothBrouwer, or b : V → {0, 1, ⊥}, as defined in Equation (5), is a solution to OraclePureCircuit. With this lemma, we can easily prove our main result. Theorem 6.1. Any algorithm that has oracle access to f : [0, 1]d × [0, 1]d → [−1, 1] and to its gradient ∇f where f and ∇f are 1-Lipschitz, and outputs a ε-approximate stationary point with ε ≤ poly(1/d), requires Ω(1) at least 2d queries to f or ∇f in the worst case. Proof. We divide the proof into two steps. 9
Correctness. Lemma 3 almost immediately proves the correctness of the reduction, as it shows that we either trivially have a solution to SmoothBrouwer or the OraclePureCircuit constraints are satisfied by b, and ultimately a solution to OraclePureCircuit thanks to Theorem 5.1. Oracle Query Complexity. Now we show that the oracles for f and ∇f can be simulated with only polynomially many queries to the OraclePureCircuit oracle L. First, observe that evaluating f (x, y) for any x, y ∈ [0, 1]d requires only polynomially many queries to the oracle L. Specifically, computing sw (x, y) for each w ∈ V requires at most |V | = poly(d) queries to L thanks to Lemma 2. Moreover, the evaluation of the Hw ’s terms requires at most m2 n = poly(d) queries to Fw (z). Thanks to Theorem 5.1, each evaluation requires at most m queries to L. A similar analysis holds for ∇f , which also requires the evaluation of JF and ∇sw (x, y), for which similar bounds hold. Compared with the proof of Bernasconi and Castiglioni [BC26], the key new ingredient is the treatment of the large-signal regime in the dichotomy argument, i.e., that sv (x, y) = 1 implies that b(v) = 1 or we can find a solution to SmoothBrouwer. The small-signal case follows the previous template, while the large-signal case now has to certify the existence of an approximate SmoothBrouwer fixed point, rather than a solution to the inner problem of Bernasconi and Castiglioni [BC26]—a simpler problem related to linear variational inequalities (see Section E.2 for more details). We modified the inner gadget because the one based on variational inequalities was reduced from polymatrix games [Rub15]. While polymatrix games are computationally intractable from a complexity perspective, they can be solved using polynomially many queries. Remark 3. In contrast to Section 5 (see Remark 2), the decoded gate signals in this reduction are already thresholded to Boolean values. For correctness, we therefore only require that the interpolation matches the function on the Boolean vertices, and we do not need the robust interpolation in Lemma 2. We nevertheless use the same robust interpolation throughout for the sake of uniformity. Remark 4. The construction of our function f only guarantees that G, L, B, 1/ε = poly(d), however, we can easily normalize f by max(G, L, B), by only needing to decrease ε by a polynomial factor.
6.1
Extension to High-Order Oracles
Our main theorem is stated for first-order algorithms, which have access to oracles f and ∇f . However, many algorithms that use second- (or higher-)order information have been proposed for min-max optimization [Let+18; Bal+18; Zha+20; HK22; VB23; CYH24]. However, all either assume an additional special structure or offer weaker guarantees (such as local convergence). Our argument can be extended even to rule out query-efficient algorithms of this sort. Indeed, fix any integer p = O(1) and suppose that the algorithm can query (f, ∇f, D2 f, . . . , Dp f ). Then, our lower bound still applies. The main point is that each oracle can be simulated with polynomially many queries to the underlying OraclePureCircuit oracle L. The objective function f is C ∞ due to its construction from algebraic compositions of C ∞ components. Moreover, Lemma 2 can be strengthened to show that for any fixed p, the derivatives of the interpolation h = H(·, L) can be computed with just one query to L, as h depends on only one vertex of the hypercube. Computing the derivative tensor Dr f for any r ≤ p also requires polynomially many queries to L because f is constructed from smooth step functions and interpolation gadgets through sums, products, and compositions, leading to polynomially many terms in the derivatives. Therefore, if a p-th order algorithm solved the constructed GDA-FixedPoint instance using T oracle queries, then we would obtain an algorithm for OraclePureCircuit using T · poly(d) queries to L. By the query lower bound of Theorem 3.1, we must have that T also grows exponentially.
7
Open Problems
Although our result resolves the query complexity of the problem in the regime where ε = 1/poly(d), the question remains open for constant values of ε > 0. Indeed, our lower bound does not preclude the existence 10
of a poly(d)-query algorithm for every fixed value of ε > 0, e.g., an algorithm making dO(1/ε) many queries. Proving or refuting such a PTAS-type query guarantee remains an interesting open problem. A second question concerns simpler instances. For min-max problems with a degree-2 objective over simplex domains, known enumeration-based techniques (e.g., the one of Lipton, Markakis, and Mehta [LMM03]) can be adapted to establish the existence of quasi-polynomial-time algorithms. It remains open whether this is tight: can one prove quasi-polynomial lower bounds already for degree-2 objectives over simplex domains, analogously to the phenomena of Nash equilibria shown by Rubinstein [Rub17]?
11
A
Proof Omitted from Section 2
Theorem 2.1. There exists a sufficiently large constant integer M such that any algorithm that outputs a solution to StrongSperner with parameters M and d must make 2Ω(d) many queries to the labeling λ. In order to prove this, we will use the following lower bound for finding a Brouwer fixed point. Theorem A.1 (Hirsch et al. [HPV89]). There exists a sufficiently small constant ε > 0 such that any algorithm that has black-box oracle access to a 2-Lipschitz (w.r.t. the ℓ∞ norm) function F : [0, 1]d → [0, 1]d and outputs a point x ∈ [0, 1]d such that ∥F (x) − x∥∞ ≤ ε requires 2Ω(d) queries. Proof of Theorem 2.1. Let ε be a sufficiently small constant for Theorem A.1. Consider any 2-Lipschitz function F : [0, 1]d → [0, 1]d . We show how to reduce the problem of finding an ε-approximate fixed point of F to a StrongSperner instance. Without loss of generality, we can assume that for all i ∈ [d], Fi (x) > 0 when xi = 0, and Fi (x) < 1 when xi = 1. Indeed, if this is not the case, then we can consider the function (1 − ε/2)F + (ε/2)v instead of the function F , where v = (1/2, . . . , 1/2) ∈ [0, 1]d , and look for an (ε/2)-approximate fixed point. Let M := ⌈1 + 3/ε⌉ and define the function ϕ : [M ] → [0, 1], t 7→ (t − 1)/(M − 1). For a vector p ∈ [M ]d , define by a slight abuse of notation ϕ(p) := (ϕ(p1 ), . . . , ϕ(pd )). Note that ϕi (p) = ϕ(pi ). Now define the StrongSperner labeling λ : [M ]d → {−1, +1}d as follows. For any p ∈ [M ]d ( +1 if Fi (ϕ(p)) > ϕi (p) λ(p) := −1 if Fi (ϕ(p)) ≤ ϕi (p) Note that λ satisfies the StrongSperner boundary conditions. Furthermore, any query to λ can be answered by performing at most one query to F . It remains to show that any StrongSperner solution p(1) , . . . , p(d) ∈ [M ]d to λ yields an ε-approximate fixed point of F . Let q := p(1) . We will show that ϕ(q) is an approximate fixed point. Consider any i ∈ [d]. Since p(1) , . . . , p(d) form a StrongSperner solution, there exists q ′ with ∥q − q ′ ∥∞ ≤ 1 such that λi (q ′ ) = −1. This implies that Fi (ϕ(q ′ )) ≤ ϕi (q ′ ). Now we can write Fi (ϕ(q)) ≤ Fi (ϕ(q ′ )) + |Fi (ϕ(q)) − Fi (ϕ(q ′ ))| ≤ ϕi (q ′ ) + 2ε/3 ≤ ϕi (q) + ε where we used the fact that F is 2-Lipschitz and ϕ is (ε/3)-Lipschitz. Using the fact that there exists q ′ with ∥q − q ′ ∥∞ ≤ 1 such that λi (q ′ ) = +1, a similar argument also proves that Fi (ϕ(q)) ≥ ϕi (q) − ε. Since this holds for any i ∈ [d], we have shown that ϕ(q) is an ε-approximate fixed point of F .
B
Proof Omitted from Section 3
Theorem 3.1. Given an instance of OraclePureCircuit with |V | nodes, any algorithm that has black-box 1/3 oracle access to L and outputs a solution to OraclePureCircuit requires 2Ω(|V | ) queries to L. We will follow the reduction from Deligkas et al. [Del+24, Section 3.2] very closely. They provide a polynomial-time reduction from the white-box version of StrongSperner to PureCircuit. In what follows, we describe the modifications that need to be made to their reduction in order to obtain a query-efficient reduction from the black-box version of StrongSperner to OraclePureCircuit. Let λ : [M ]d → {−1, +1}d be a StrongSperner labeling satisfying the boundary conditions, as defined in Problem 2. We use the same notation as in Deligkas et al. [Del+24, Section 3.2], except that we have used d to denote the dimension of the StrongSperner instance, whereas they use N . We assume that the width M of the instance is a sufficiently large constant such that the query lower bound of 2Ω(d) from Theorem 2.1 applies.
12
Construction. The construction of the OraclePureCircuit instance is completely identical to the construction of the PureCircuit instance in Deligkas et al. [Del+24, Section 3.2], except for the “circuit stage”. In that part of the construction, the goal is to simulate the evaluation of the StrongSperner labeling λ on some input. In fact, this needs to be done on K separate occasions, where K := 3dM 2 . Fix some k ∈ [K]. (k) (k) (k) We are given nodes (ui,j )(i,j)∈[d]×[M ] representing a point in [M ]d . Namely, for each i ∈ [d], ui,1 , . . . , ui,M represents an element in [M ] in unary. Our task, or “contract”, is to ensure that some designated output (k) (k) (k) nodes, denoted v1 , . . . , vd , encode the output of λ on the input encoded by (ui,j )(i,j)∈[d]×[M ] . By this (k)
(k)
we mean that if the ith output of λ is +1, then vi = 1, and if the ith output of λ is −1, then vi = 0. Importantly, for any given k ∈ [K], the contract only requires us to ensure this correct output when all inputs (k) (ui,j )(i,j)∈[d]×[M ] are correct bits, i.e., lie in {0, 1}. In the original reduction by Deligkas et al. [Del+24], the contract is enforced by using the PureCircuit gates to simulate the execution of the Boolean circuit computing λ. In our case, λ is a black-box and we are not given a circuit computing it. We will thus need to use the oracle gates to enforce the contract. We let N := M d + d and define the oracle L : {0, 1}N → {0, 1} as follows. On input p ∈ {0, 1}N , decomposed as (z, t) ∈ {0, 1}M d × {0, 1}d : 1. If t ∈ {0, 1}d contains a 1 in exactly one position, and all other entries are 0, then let i denote the entry such that ti = 1, and proceed to the next step. If this is not the case, then the oracle L outputs something arbitrary, say 0. 2. Interpret z ∈ {0, 1}M d as representing a corresponding point z ∈ [M ]d , where each entry is given in unary. Evaluate λi (z) by performing one query to λ. (Recall that i is the index such that ti = 1 from the first step.) 3. If λi (z) = +1, the oracle L outputs 1. If λi (z) = −1, the oracle L outputs 0. Coming back to the contract we have to enforce, we can now use the oracle gate (with oracle L). Namely, (k) for each k ∈ [K] and i ∈ [d], we ensure that vi has the correct value by introducing an oracle gate that has (k) (k) vi as output, and takes as input (uℓ,j )(ℓ,j)∈[d]×[M ] for the first M d bits. The remaining d input bits are hardcoded to be (0, . . . , 0, 1, 0, . . . , 0), where the 1 appears in the ith position. This indicates to the oracle L that we want the ith output of λ. In order to create these hardcoded bits, it suffices to create d nodes that are guaranteed to be 0 in any solution and d nodes that are guaranteed to be 1 in any solution. Then, each time we use an oracle gate, we can pick the corresponding hardcoded bits as input. In Figure 2 we show a constant-size gadget which ensures that a particular node always has value 0. We include a proof of this in Lemma 4 at the end of this section. From this node that always has value 0, a node that always has value 1 can easily be constructed using one Purify and one Nor gate. Correctness. It is now easy to see that the contract is correctly enforced. Indeed, whenever the nodes (k) (uℓ,j )(ℓ,j)∈[d]×[M ] all have values in {0, 1}, the fact that the oracle gate has to be satisfied will imply that (k)
(k)
(k)
the nodes v1 , . . . , vd encode the correct output values. When the nodes (uℓ,j )(ℓ,j)∈[d]×[M ] do not all have values in {0, 1}, then the contract does not require us to enforce anything. As we have fulfilled the “circuit stage” contract, i.e., Lemma 3.3 of Deligkas et al. [Del+24], and the rest of the construction is identical, the correctness of the reduction follows by the exact same arguments as in Deligkas et al. [Del+24, Section 3.2]. Namely, it holds that any solution of the constructed OraclePureCircuit instance yields a solution of the StrongSperner instance. Oracle Query Complexity. First, let us note that in order to answer a query to L we only need to make at most one query to λ. Thus, by Theorem 2.1, we know that at least 2Ω(d) queries to L are required to solve the OraclePureCircuit instance. 1/3 In order to show that this corresponds to a lower bound of 2Ω(|V | ) , where |V | is the number of nodes in the OraclePureCircuit instance, it remains to argue that |V | = O(d3 ). By inspection of the construction in Section 3.2 of Deligkas et al. [Del+24], we have: 13
v2
Purify
v3
Nor
v4
v5
Nor
Purify v6
v1
Purify
v7
Nor
v9
v8
Figure 2: The gadget implementing the constant node b(v9 ) = 0. Assuming that this gadget actually forces b(v9 ) (proven in Lemma 4), we can easily implement a similar one that forces an assignment of 1 to a specific node. Indeed, we could further apply a Purify gate to v9 , with outputs v10 and v11 , and then a further Nor gate with inputs v10 and v11 and output v12 . If b(v9 ) = 0 it is clear that only b(v12 ) = 1 satisfies the additional gates. • The “purification stage” requires O(M dK) = O(d2 M 3 ) nodes, where we used the fact that K = 3dM 2 . • The “circuit stage”, which is the only stage that we modified, requires dK = O(d2 M 2 ) for the oracle output nodes, as well as O(d) nodes to create the hardcoded 0 and 1 bits. • The “sorting stage” requires a sorting network over K elements for each i ∈ [d]. By using a simple sorting network of size O(K 2 ), we thus obtain an upper bound of O(dK 2 ) = O(d3 M 4 ) nodes. • The “selection stage” does not introduce any additional nodes. Putting everything together, we have |V | = O(d3 M 4 ) = O(d3 ), where we used the fact that M is a constant. A subtle point is that the reduction in Section 3.2 of Deligkas et al. [Del+24] also uses gates And, Or, Not, and Copy. However, it is easy to see that each of those gates can be simulated by a constant-size gadget that uses only Nor and Purify gates. Thus, we still have |V | = O(d3 ). This completes the proof of Theorem 3.1. Remark 5. By using a more involved sorting network of size O(K log K), instead of O(K 2 ), one can obtain an √ instance of size |V | = O(d2 log d) [AKS83]. Thus, the lower bound in Theorem 3.1 can be improved to e Ω( |V |) e allows for division by polylogarithmic factors. We leave open whether this lower bound 2 , where Ω can be further improved. Below, we include a lemma which proves the correctness of the gadget that we used to create the hardcoded bits. Lemma 4. In the gadget described in Figure 2, for every assignment b : V → {0, 1, ⊥} that satisfies all gates, it must hold that b(v9 ) = 0. Proof. Let b : V → {0, 1, ⊥} be any assignment that satisfies all gates. First, we will argue that b(v1 ) = ⊥. Assume by contradiction that b(v1 ) = 1, then we would also have b(v2 ) = b(v3 ) = 1 by definition of the Purify gate. Then b(v4 ) = 0 by definition of the Nor constraints. Now the Purify gate, with v4 as input, has a node with a pure bit input, and thus its outputs are both pure and assigned with the same bit, which is 0 = b(v4 ) = b(v5 ) = b(v1 ). Contradicting the fact that b(v1 ) was assumed to be 1. A similar, symmetric situation will occur if we assume b(v1 ) = 0, thus leaving only b(v1 ) = ⊥ as an option. Now we claim that b(v5 ) ∈ {0, 1}. Indeed, the Purify gate with input v4 has as outputs v1 and v5 , but the Purify gate constraints force at least one of the two output bits to be pure, and, since v1 cannot be pure, then v5 must be. Now observe that if b(v5 ) ∈ {0, 1}, then the statement follows. Indeed, if b(v5 ) = 0, then b(v6 ) = b(v7 ) = b(v5 ) = 0 by the constraints of the Purify gate, and b(v8 ) = 1 by the ones on the Nor gate. Then, if b(v5 ) = 0 and b(v8 ) = 1, then the last Nor gate forces b(v9 ) = 0. Symmetrically, if b(v5 ) = 1 then it leads to b(v8 ) = 0 and similarly to before, to b(v9 ) = 0, by the last Nor gate constraints.
14
C
Proofs Omitted from Section 4
Lemma 1. Given two c1 < c2 , the function ϕc1 ,c2 is in C ∞ and satisfies: If x ≤ c1 {0} ϕc1 ,c2 (x) ∈ (0, 1) if x ∈ (c1 , c2 ) . {1} if x ≥ c2 2
4
Moreover, ∥ϕ′c1 ,c2 ∥∞ ≤ e c2 −c1 , and ∥ϕ′′c1 ,c2 ∥∞ ≤ 12e c2 −c1 . Proof. We only show the bounds on the derivatives. Define a := x − c1 and b := c2 − x, and also A = e−1/a , B = e−1/b , S = A + B and ∆ = c2 − c1 . Then we for all x ∈ (c1 , c2 ) we can write ϕc1 ,c2 (x) = A/S. We are only interested in the behavior of ϕc1 ,c2 in x ∈ (c1 , c2 ) since outside this interval ϕ′c1 ,c2 = ϕ′′c1 ,c2 = 0. We can −1/t
observe that A′ = aA2 , B ′ = bB2 , and thus |A′ |, |B ′ | ≤ 1 since e t2 ≤ 1 for t > 0. Moreover, (since at least one between a and b will be at least ∆/2) at least one between A and B is at least e−2/∆ so S ≥ e−2/∆ . ′ ′ ′ ′ +B ′ ) Thus, we can bound the first derivative by observing that ϕ′c1 ,c2 (x) = A (A+B)−A(A = A B−AB , S2 S2 which implies that |A′ |B + A|B ′ | S2 A+B ≤ S2 1 ≤ ≤ e2/∆ . S
|ϕ′c1 ,c2 (x)| ≤
For the second derivative, we can observe that (A′ B − AB ′ )′ S 2 − (S 2 )′ (A′ B − AB ′ ) S4 ′′ ′′ 2 (A B − AB )S − 2S(A′ + B ′ )(A′ B − AB ′ ) = S4 A′′ B − AB ′′ (A′ + B ′ )(A′ B − AB ′ ) = −2 , S2 S3
ϕ′′c1 ,c2 (x) =
−1/t
−1/t
Moreover, we can observe that, for t > 0 we have e t4 ≤ 5 and e t3 ≤ 32 , so that |A′′ | ≤ e−1/a and the same holds for |B ′′ |. Plugging these bound in |ϕ′′c1 ,c2 (x)| we obtain
1 2 a4 + a3
≤8
|A′′ |B + A|B ′′ | (|A′ | + |B ′ |)(|A′ |B + A|B ′ |) +2 2 S S3 8 4 ≤ + 2 S S ≤ 8e−2/∆ + 4e−4/∆
|ϕ′′c1 ,c2 (x)| ≤
≤ 12e−4/∆ , concluding the proof. Lemma 2. Let ĥ : {0, 1}N → {0, 1} be a Boolean function. There exists a smooth C ∞ function h = H(·, ĥ) : [0, 1]N → [0, 1] that satisfies N (i) ĥ(y) = h(x) for all y ∈ {0, 1}N and all x ∈ B1∞ ; /6 (y) ∩ [0, 1]
(ii) h(x) ∈ [0, 1] for all x ∈ [0, 1]N ; 15
(iii) h(x) and ∇h(x) are computable with at most one call to ĥ for all x ∈ [0, 1]N ; 12
(iv) ∥∇h(x)∥∞ ≤ e2 , and ∥D2 h(x)∥max ≤ 6e24 for all x ∈ [0, 1]N . Proof. Let α(t) = 1 − ϕ 16 , 31 (t). and for any vertex y ∈ {0, 1}N define Φy (x) =
Y
α(yi + (1 − 2yi )xi ).
i∈[N ]
Crucially, by Lemma 1, for a vertex y ∈ {0, 1}N , we have that Φy (x) = 1 for all x ∈ B1∞ /6 (y); that Φy (x) = 0 ∞ ∞ ∞ for all x ∈ / B1/3 (y); and that Φy (x) ∈ (0, 1) for all x ∈ B1/3 (y) \ B1/6 (y). ∞ For any x ∈ [0, 1]N we call any vertex y ∈ {0, 1}N active if x ∈ B1/3 (y). Note that, since ℓ∞ -balls of radius 1/3 centered at the vertices of the hypercube are disjoint, at most 1 vertex is active for all x ∈ [0, 1]N . So if there is any coordinate i such that xi ∈ ( 13 , 23 ), then there is no active vertex. Otherwise, we can identify the active vertex y ∗ by rounding every xi ≤ 1/3 to yi∗ = 0 and every xi ≥ 2/3 to yi∗ = 1. Then we define X 1 Φy (x)(ĥ(y) − 12 ) h(x) = + 2 N y∈{0,1}
for all x ∈ [0, 1]N . Since there is at most one active node for all x ∈ [0, 1]N , we have that either Φy (x) = 0 for all y ∈ {0, 1}N or that there is a single active one y ∗ . In the first case, we have h(x) = 12 , in the second ∗ ∗ one we have h(x) = 12 + Φy∗ (x)(ĥ(y ∗ ) − 1/2). Moreover if x ∈ B1∞ /6 (y ) we have that Φy (x) = 1 and thus h(x) = ĥ(y ∗ ). This proves the first and second items of the statement. Note that since we can know what the unique active node (if any) is, we need only one evaluation of ĥ. By direct calculations we have that for all y ∈ {0, 1}N we have: Q • ∂xj Φy (x) = (1 − 2yj )α′ (yj + (1 − 2yj )xj ) i̸=j α(yi + (1 − 2yi )xi ); Q • ∂xj ,xk Φy (x) = (1 − 2yj )α′ (yj + (1 − 2yj )xj )(1 − 2yk )α′ (yk + (1 − 2yk )xk ) i̸=j,k α(yi + (1 − 2yi )xi ) if k ̸= j; Q • ∂xj ,xk Φy (x) = α′′ (yj + (1 − 2yj )xj ) i̸=j α(yi + (1 − 2yi )xi ); which in turn, thanks to Lemma 1 and α(x) = ϕ 1 1 ( 21 − x), implies that for all x ∈ [0, 1]N : 6,3
• |∂xj Φy (x)| ≤ ∥α′ ∥∞ ≤ e12 ; • |∂xj ,xk Φy (x)| ≤ ∥α′ ∥2∞ ≤ e24 if k ̸= j; • |∂xj ,xk Φy (x)| ≤ ∥α′′ ∥∞ ≤ 12e24 . Thus, thanks to the observations above, we can also bound the derivative. A direct calculation shows that ( 0 if no vertex is active, ∂xj h(x) = (ĥ(y) − 21 )∂xj Φy (x) if y is active. and thus, |∂xj h(x)| ≤
1 1 |∂x Φy (x)| ≤ ∥α′ ∥∞ ≤ e12 /2. 2 j 2
Similarly, we can note that ( ∂xj ,xk h(x) =
0 if no vertex is active, (ĥ(y) − 21 )∂xj ,xk Φy (x) if y is active.
and thus, thanks to the previous observations, |∂xj ,xk h(x)| ≤ 6e24 . 16
D
Proof Omitted from Section 5
Theorem 5.1. There is a reduction from an instance of OraclePureCircuit (with oracle L) to Smooth1 Brouwer with approximation ε = 12 , such that: • C ∞ ∋ F : [0, 1]d → [0, 1]d where d = |V | is the number of nodes of OraclePureCircuit; • any query to F or JF can be simulated with at most d = |V | queries to L; • we can efficiently recover a OraclePureCircuit solution from any SmoothBrouwer one; • the function F is (e12 d)-Lipschitz and (12e24 d2 )-smooth, and |∂zj Fi (z)| ≤ e12 for all i, j ∈ [d]. Proof. Given an instance of OraclePureCircuit with vertex set V and oracle L, we build a smooth function F : [0, 1]d → [0, 1]d , where as promised d = |V |. Let ε = 1/12. For every w ∈ V , the w-th component Fw : [0, 1]d → [0, 1] is defined based on the gate type for which w is an output: • If (u, v, w) ∈ GNor , we define Fw (z) = g(zu + zv ), where g(z) = 1 − ϕ 1 2 (z). 3,3
• If (u, v, w) ∈ GPurify , we define Fv (z) = ℓ(zu + 41 ) and Fw (z) = ℓ(zu − 41 ), where ℓ(z) = ϕ 5
7 (z). 12 , 12
• If (u1 , . . . , uN , v) ∈ GOracle , we define Fv (z) = H((zu1 , . . . , zuN ), L) according to Lemma 2. Correctness. Let z ∈ [0, 1]d be any point satisfying ∥F (z) − z∥∞ ≤ ε. We define the assignment b : V → {0, 1, ⊥} as follows: 1 0 if zv ≤ 6 b(v) = ⊥ if zv ∈ ( 16 , 56 ) . 1 if zv ≥ 56 Recall that by Lemma 1, it holds g(z) = 0 if z ≥ 23 , g(z) ∈ (0, 1) if z ∈ ( 13 , 23 ), and g(z) = 1 if z ≤ 31 . 5 7 7 Moreover, ℓ(z) = 0 if z ≤ 75 , ℓ(z) ∈ (0, 1) if z ∈ ( 12 , 12 ), and ℓ(z) = 1 if z ≥ 12 . We prove that b is a valid assignment to OraclePureCircuit since it satisfies all the gate constraints posed by OraclePureCircuit: • Gate (u, v, w) ∈ GNor . If b(v) = b(u) = 0, then by definition zu , zv ≤ 1/6 and zu + zv ≤ 1/3 and thus Fw (z) = g(zu + zv ) = 1. Since z is a solution to SmoothBrouwer it holds that zw ≥ 1 − ε > 5/6 and thus b(w) = 1 as required. Similarly, if b(u) = 1 or b(v) = 1, then we have that zu + zv ≥ 5/6 and thus Fw (z) = g(zu + zv ) = 0, which implies that zw ≤ ε < 1/6 and thus b(w) = 0. In all other cases OraclePureCircuit does not impose any constraints on the Nor gate. • Gate (u, v, w) ∈ GPurify . If b(u) = 0 then zu ≤ 1/6. Thus, Fv (z) = ℓ(zu + 1/4) = 0. Moreover, zu −1/4 ≤ 5/12 and thus also Fw (z) = 0. Thus, since z is a solution to SmoothBrouwer, zv , zw ≤ ε < 1/6 and b(v) = b(w) = 0. Similarly, if b(u) = 1 then zu ≥ 5/6, zu +1/4, zu −1/4 ≥ 7/12 and Fv (z) = Fw (z) = 1. It follows that zv , zw ≥ 1 − ε > 5/6 and b(v) = b(w) = 1. Finally, if b(u) = ⊥ then zu ∈ (1/6, 5/6) and it is easy to see that either zu + 1/4 ≥ 7/12 or zu − 1/4 ≤ 5/12. In the first case, we have Fv (z) = 1 (and thus zv ≥ 1 − ε > 5/6 and b(v) = 1), while in the second case we have Fw (z) = 0 (and thus zw ≤ ε < 1/6 and b(w) = 0). This shows that the Purify constraints are also satisfied.
17
• Gate (u1 , . . . , uN , v) ∈ GORACLE . Assume (b(u1 ), . . . , b(uN )) ∈ {0, 1}N , otherwise there are no constraints. Define z ′ = (b(u1 ), . . . , b(uN )). Note that if zi′ = b(ui ) = 1 then zui ≥ 5/6 and |zi′ − zui | ≤ 1/6. Similarly, ∞ if zi′ = b(ui ) = 0, then zui ≤ 1/6 and |zi′ − zui | ≤ 1/6. Therefore, (zu1 , . . . , zuN ) ∈ B1/6 (z ′ ) and from ′ ′ Lemma 2 this implies that Fv (z) = L(z ) and thus |zv − Fv (z)| ≤ ε. If L(z ) = 1 then zv ≥ 1 − ε > 5/6 and b(v) = 1. If L(z ′ ) = 0 then zv ≤ ε < 1/6 and b(v) = 0. In either case L(z ′ ) = b(v). This shows that the constraints on the Oracle gates are also satisfied. Oracle Query Complexity. We show that any evaluation of F or its Jacobian JF requires at most |V | queries to the oracle L. Only coordinates corresponding to outputs of Oracle gates require access to L. Since there are at most |V | such components, we can compute the value and the Jacobian in at most |V | oracle calls to L, since Lemma 2 shows that each component value and derivative can be obtained via at most one query to L. Bounding the Lipschitzness and smoothness. Each coordinate w ∈ V of Fw , is either the output of g(zu + zv ), ℓ(zu ± 1/4) or H((zu1 , . . . , zuN ), L). Furthermore, by and so by Lemma 1 we can bound ∥∂zu g∥∞ ≤ e6 , ∥∂zu ℓ∥∞ ≤ e12 for all u ∈ V , while Lemma 2 ensures that ∥∂zu H((zu1 , . . .√ , zuN ), L)∥∞ ≤ e12 /2 12 12 for all u ∈ V . In all cases, we have |∂zu Fw (z)| ≤ e , and thus every component is e d-Lipschitz making the function (e12 d)-Lipschitz. Similarly, we can show that F is polynomially smooth. Indeed, by the same reasoning above, we have that ∥∂zu ,zu′ g∥∞ ≤ 12e12 , ∥∂zu ,zu′ ℓ∥∞ ≤ 12e24 for all u, u′ ∈ V by Lemma 1, while ∥∂zu ,zu′ H((zu1 , . . . , zuN ), L)∥∞ ≤ 6e24 for all u, u′ ∈ V by Lemma 2. This lets us conclude that |∂zu ,zu′ Fw (z)| ≤ 12e24 , and thus, that F is (12e24 d2 )-smooth.
E
Proof Omitted from Section 6
We start by computing the partial derivatives of f . To do so, we first need some additional notation. We denote with In(w) ⊆ V the set of nodes that are inputs to the gate to which w is an output, and Out(q) = {w : q ∈ In(w)} is the set of nodes that are outputs of a gate to which q is an input. Moreover, we define the displacement function G(z) = F (z) − z, where F is the function defining the SmoothBrouwer instance. Lemma 5. The partial derivatives of f (defined as per Equation (4)) are q ∂xqi,j f (x, y) = sq (x, y)∂xqi,j Hq (x, y) + 2(Mi + ∆q (x, y))(xqi,j − yi,j )
(6a)
q q q f (x, y) = s (x, y)∂ q H (x, y) − 2(M + ∆ (x, y))(x ∂yi,j q i q yi,j q i,j − yi,j ),
(6b)
where ∆q (x, y) =
X
Hw (x, y)ϕ′3m,3m+1 (∥xq − y q ∥2 )∂Eq (x,y) sw (x, y).
(7)
w∈Out(q)
Proof. We recall the definition of f (x, y) which is: X f (x, y) = sw (x, y) · Hw (x, y) + φ(x, y). w∈V
Since Hw is a local term (i.e., it depends only on the variables xw , y w ), and sw depends only on the nodes that are inputs of w (and in particular q ∈ / In(q)), we have that: ! X X ∂xqi,j sw (x, y) · Hw (x, y) = sq (x, y)∂xqi,j Hq (x, y) + Hw (x, y) · ∂xqi,j sw (x, y). (8) w∈V
w∈Out(q)
18
Then, by chain rule, for every w ∈ Out(q), we have ∂xqi,j sw (x, y) = ∂Eq (x,y) sw (x, y)∂xqi,j Eq (x, y),while for every w ̸∈ Out(q) we have ∂xqi,j sw (x, y) = 0. Note that by definition, Eq (x, y) is a function of only ∥xq −y q ∥2 and in particular Eq (x, y) = ϕ3m,3m+1 (∥xq − q 2 y ∥ ). Thus, for all w ∈ Out(q): q ∂xqi,j sw (x, y) = 2∂Eq (x,y) sw (x, y)ϕ′3m,3m+1 (∥xq − y q ∥2 )(xqi,j − yi,j ).
(9)
Moreover, it is easy to check that: q ∂xqi,j φ(x, y) = 2Mi (xqi,j − yi,j ).
(10)
Combining Equations (8) to (10) with the definition of ∆q (x, y) of Equation (7), we can deduce that: q ∂xqi,j f (x, y) = sq (x, y)∂xqi,j Hq (x, y) + 2 (∆q (x, y) + Mi ) (xqi,j − yi,j ).
Similarly, we get that q q q f (x, y) = s (x, y)∂ q H (x, y) − 2 (∆ (x, y) + M ) (x ∂yi,j q q i yi,j q i,j − yi,j ), q ∥xq − where the only difference comes from the derivative of ∥xq − y q ∥2 , which gives ∂xqi,j ∥xq − y q ∥2 = −∂yi,j q y q ∥2 = 2(xqi,j − yi,j ).
Then, we prove the following technical lemma that will help us compute an upper bound on the partial derivatives of Hq . Lemma 6. For every (i, j, q) ∈ [n] × [m] × V we have q xi + yiq + Ri,j,q (x, y), (11a) ∂xqi,j Hq (x, y) = −Gj 2 q xi + yiq q H (x, y) = G ∂yi,j + Ri,j,q (x, y), (11b) q j 2 q q P x +y q where Ri,j,q (x, y) := 12 k∈[m] (yi,k − xqi,k ) · ∂zj Gk i 2 i and Moreover, it holds that maxi,j,q |Ri,j,q (x, y)| ≤ q H (x, y)|} ≤ me13 . e12 ∥xqi − yiq ∥1 and maxi,j,q {|∂xqi,j Hq (x, y)|, |∂yi,j q
Proof. Recall that we have Hq (x, y) =
X ℓ∈[n]
* + xqℓ + yℓq q q , yℓ − xℓ . G 2
Since xqi,j appears only in the ℓ = i summand we get ∂
xqi,j
q q X q xi + yiq xi + yiq q q + (yi,k − xi,k )∂xi,j Gk Hq (x, y) = −Gj 2 2 k∈[m] q q xi + yiq 1 X q xi + yiq = −Gj + (yi,k − xqi,k )∂zj Gk 2 2 2 k∈[m] q xi + yiq = −Gj + Ri,j,q (x, y). 2
Similarly, we can conclude that q xi + yiq q H (x, y) = G ∂yi,j + Ri,j,q (x, y). q j 2 19
From the bounds of Theorem 5.1 it is clear that q xi + yiq 1 · ∥xqi − yiq ∥1 max |Ri,j,q (x, y)| ≤ max ∂zj Gk i,j,q 2 k∈[m] 2 q xi + yiq 1 = max ∂zj Fk − I(j = k) · ∥xqi − yiq ∥1 2 k∈[m] 2 ≤ e12 ∥xqi − yiq ∥1 . This easily implies also that q H (x, y)|} ≤ G max{|∂xqi,j Hq (x, y)|, |∂yi,j j q
i,j,q
q xi + yiq + |Ri,j,q (x, y)| 2
≤ 1 + e12 ∥xqi − yiq ∥1 ≤ me13 , concluding the proof. Now we show that when the regularizer Mi does not guess correctly the noise term ∆q (x, y), the players are forced to play close to each other, namely: Lemma 7. Consider any solution (x, y) to GDA-FixedPoint and any q ∈ V , i ∈ [n], j ∈ [m]. If Mi + ∆q (x, y) ̸= 0, it holds that: r ε sq (x, y) q + . |xqi,j − yi,j | ≤ me13 |Mi + ∆q (x, y)| |Mi + ∆q (x, y)| q Proof. Consider the optimality conditions of the x-player w.r.t. yi,j and viceversa, i.e. q −∂xqi,j f (x, y)(yi,j − xqi,j ) ≤ ε
(12a)
q q q f (x, y)(x ∂yi,j i,j − yi,j ) ≤ ε.
(12b)
Define A := Mi + ∆q (x, y). If A > 0, substituting the expression of ∂xqi,j f (x, y) of Equation (6a) in Equation (12a), we obtain q q − sq (x, y)∂xqi,j Hq (x, y) + 2(Mi + ∆q (x, y))(xqi,j − yi,j ) (yi,j − xqi,j ) ≤ ε. q f (x, y) of Equation (6b) in Equation (12b) On the other hand, if A < 0, substituting the expression of ∂yi,j we obtain q q q q q H (x, y) − 2(M + ∆ (x, y))(x sq (x, y)∂yi,j q i q i,j − yi,j ) (xi,j − yi,j ) ≤ ε.
q In both cases, rearranging, implies the following quadratic expression in |κ| := |xqi,j − yi,j |:
2κ2 |A| ≤ ε + |κ|Csq (x, y),
(13)
q H (x, y)|} ≤ me13 . Solving Equation (13) where by Lemma 6 we have C := maxi,j,q {|∂xqi,j Hq (x, y)|, |∂yi,j q implies that q Csq (x, y) + C 2 s2q (x, y) + 8|A|ε |κ| ≤ 4|A| r s (x, y) ε q 13 ≤ me + , |Mi + ∆q (x, y)| |Mi + ∆q (x, y)| √ √ √ where in the last inequality we also used that a + b ≤ a + b for a, b ≥ 0.
20
The following lemma shows that, for components i, where the regularizer Mi does not guess correctly, we can upper bound the growth of the inverse errors geometrically. Lemma 8. Define Bτ (x) := {i ∈ [n] : |Mi + x| < τ }, then for all x ∈ R X 1 2 2 nδ . ≤ + log 1 + |Mi + x| τ δ τ i∈[n]\Bτ (x)
Proof. Define ai := Mi + x and observe that ai is an arithmetic progression with difference δ. Let B + := {i ∈ [n] : ai ≥ τ } and B − := {i ∈ [n] : ai ≤ −τ }, and observe that [n] \ Bτ (x) = B + ∪ B − , and that B + ∩ B − = ∅. Thus X X 1 X 1 1 = + . |Mi + x| ai −ai + − i∈[n]\Bτ (x)
i∈B
i∈B
+ + Then, we can re-index the elements of {ai }i∈B + to a set {a+ i }i∈[m] (with m := |B |), such that τ ≤ a1 < + + a2 < . . . < a+ m , and ak ≥ τ + (k − 1)δ, thus m m n−1 X 1 X X X 1 1 1 ≤ ≤ . ≤ + ai τ + (k − 1)δ τ + kδ ak +
i∈B
k=1
k=1
k=0
− − Similarly, for i ∈ B − (now m = |B − |), we can reorder the ai ’s into a− i in reverse order −τ ≥ a1 ≥ a2 ≥ − − . . . ≥ am and ak ≤ −τ − (k − 1)δ so that m
n−1
k=1
k=0
X 1 X 1 1 . ≤ − ≤ −ai τ + kδ −ai −
X i∈B
Finally, we can combine the two to obtain n−1
X i∈[n]\Bτ (x)
X 1 1 2 ≤2 ≤ +2 |Mi + x| τ + kδ τ k=0
Z n−1 0
2 2 δn 1 dt ≤ + log 1 + , τ + δt τ δ τ
which is the desired result. Lemma 9. Assume δ ≤ τ and τ ≤ nδ/8. Then (i) For all x ∈ R we have |Bτ (x)| ≤ 2τ δ ; (ii) and for all x ∈ R such that |x| ≤ nδ/4 it holds that |Bτ (x)| ≥ τδ . Proof. {Mi + x}i∈[n] is an arithmetic progression with difference δ. Thus, since δ ≤ 2τ , every open interval 2τ of size 2τ contains at most ⌈ 2τ δ ⌉ points. This proves that |Bτ (x)| ≤ ⌈ δ ⌉ for every x ∈ R. For the second statement observe that, by the assumption that τ ≤ nδ/8 and |x| ≤ nδ/4, the interval [−x − τ, −x + τ ] is fully contained in the range of the progression (Mi )i∈[n] . Therefore, the number of points τ of the progression lying in the interval [−x − τ, −x + τ ] is at least ⌊ 2τ δ ⌋ ≥ δ. Now we can prove the main technical component, which provides a bound on |Hv (x, y)| of the kind |Hv (x, y)| = O(sv (x, y)poly(m/δ) log(n)), thus showing that the magnitude of |Hv (x, y)| is sublinear in n. This will be used in showing that the noise term |∆q (x, y)| is small enough so that it falls strictly into the range of the regularizer. Lemma 10. For any solution (x, y) to GDA-FixedPoint and any v ∈ V we have: |Hv (x, y)| ≤
√ 16 2 13 m e sv (x, y) log(2nδ) + 2mn ε. δ 21
Proof. Firs notice that our choice of parameters δ, n satisfy the assumptions of Lemma 9 with τ = 1. If i ∈ B1 (∆v (x, y)), then ∥xvi − yiv ∥1 ≤ m, and by Lemma 9 item (i), |B1 (∆v (x, y))| ≤ 1 + 2/δ ≤ 4/δ. Thus, when i ∈ B1 (∆v (x, y)) we get: X
∥xvi − yiv ∥1 ≤
i∈B1 (∆v (x,y))
4m δ
(14)
On other hand, if i ∈ / B1 (∆v (x, y)), then |Mi + ∆v (x, y)| ≥ 1, and we have: X v ∥xvi − yiv ∥1 = |xvi,j − yi,j | j∈[m]
≤ m2 e13
√ sv (x, y) + m ε. |Mi + ∆v (x, y)|
(by Lemma 7)
Moreover, by Lemma 8 with τ = 1, we can sum over these component to obtain: X
X
∥xvi − yiv ∥1 ≤ m2 e13 sv (x, y)
i̸∈B1 (∆v (x,y))
i̸∈B1 (∆v (x,y))
√ 1 + mn ε |Mi + ∆v (x, y)|
√ 4 ≤ m2 e13 sv (x, y) log(2nδ) + mn ε, δ
(15)
where in the last inequality we used that nδ ≥ 1 and 1 = τ ≥ δ.Finally, recalling that Hv (x, y) = v P xv +y v xv i +yi ) − i 2 i , yiv − xvi ⟩ and combining Equation (14) and Equation (15) we get: i∈[n] ⟨F ( 2 |Hv (x, y)| ≤
X i∈[n]
≤2
X
v xi + yiv xv + yiv F − i 2 2
∥xvi − yiv ∥1 ∞
∥xvi − yiv ∥1
i∈[n]
=2
X
X
∥xvi − yiv ∥1
i∈B / 1 (∆v (x,y))
i∈B1 (∆v (x,y))
m ≤8 +2 δ
X
∥xvi − yiv ∥1 + 2 ∥xvi − yiv ∥1
(by Equation (14))
i∈B / 1 (∆v (x,y))
√ m 8 2 13 + m e sv (x, y) log(2nδ) + 2mn ε δ δ √ 16 2 13 ≤ m e sv (x, y) log(2nδ) + 2mn ε, δ ≤8
(by Equation (15))
concluding the proof.
E.1
Small Signal
Lemma 11. Consider a solution (x, y) of GDA-FixedPoint and any node q such that sq (x, y) = 0, then b(q) = 0. Proof. From Lemma 9, we get that |Bδ (∆q (x, y))| ≤ 2 and, trivially, also that for all i ∈ Bδ (∆q (x, y)) we have ∥xqi − yiq ∥2 ≤ m. On the other hand, if i ∈ / Bδ (∆q (x, y)) then we can invoke Lemma 7, with sq (x, y) = 0, which implies that r r ε ε q q |xi,j − yi,j | ≤ ≤ , |Mi + ∆q (x, y)| δ 22
since for the i’s we are considering |Mi + ∆q (x, y)| ≥ δ. This implies that X q q 2 ∥xqi − yiq ∥2 = (xi,j − yi,j ) ≤ mε/δ. j∈[m]
Summing the two cases we get
∥xq − y q ∥2 ≤ 2m + mnε/δ ≤ 3m,
since our choice of parameters guarantees that ε ≤ δ/n. The proof is concluded by the definition of the decoded solution b and the definition of Eq
E.2
Large Signal
Lemma 12. Let (x, y) be a solution to GDA-FixedPoint. Then: |B1 (∆q (x, y)| ≥ 1/δ. Proof. This follows easily from Lemma 10. Indeed from the decomposition of Lemma 5: X |Hw (x, y)| · |ϕ′3m,3m+1 (∥xq − y q ∥2 )| · |∂Eq (x,y) sw (x, y)| |∆q (x, y)| ≤ w∈Out(q) 14
≤ me
√ 16 2 13 m e log(2nδ) + 2mn ε δ
≤
nδ . 4
where we used |Out(q)| ≤ m, ∥ϕ′3m,3m+1 ∥∞ ≤ e2 and ∥s′v ∥∞ ≤ e12 . The proof is then concluded by straightforward application of the second item of Lemma 9. Lemma 13. Consider any q ∈ V such that sq (x, y) = 1, then, if there is no i ∈ [n] such that ρ-approximate solution to SmoothBrouwer, then b(q) = 1. Proof. In this proof, for all i ∈ [n], j ∈ [m] and q ∈ V , it is convenient to define ξiq := q ξi,j :=
q xqi,j +yi,j
2
xqi +yiq 2
xqi +yiq 2
is a
∈ [0, 1]m and
∈ [0, 1]. By Lemma 12, there are at least 1/δ many i ∈ B1 (∆q (x, y)). We now show that for 2
2
q q ρ ρ such i’s we have ∥xqi − yiq ∥1 ≥ 10e 13 . By contradiction, assume that ∥xi − yi ∥1 < 10e13 . Lemma 6 let us write for all j ∈ [m]: q ∂xqi,j Hq (x, y) = −(Fj (ξiq ) − ξi,j ) + Ri,j,q (x, y),
(16)
q q q H (x, y) = F (ξ ) − ξ ∂yi,j q j i i,j + Ri,j,q (x, y),
(17)
and,
12
2
where |Ri,j,q (x, y)| ≤ e2 ∥xqi − yiq ∥1 ≤ ρ10 , where the first inequality is by Lemma 6, while the second inequality holds by contradiction’ assumption. Then consider, any j ∈ [m], and the optimality conditions of the first player together with Equation (16): q q Fj (ξiq ) − ξi,j − Ri,j,q − 2(Mi + ∆q (x, y))(xqi,j − yi,j ) (z − xqi,j ) ≤ ε, for all z ∈ [0, 1] which implies that q q (Fj (ξiq ) − ξi,j )(z − xqi,j ) ≤ ε + (Ri,j,q + 2(Mi + ∆q (x, y))(xqi,j − yi,j ))(z − xqi,j )
ρ2 q + 2|Mi + ∆q (x, y)| · |xqi,j − yi,j | 10 ρ2 ρ2 ≤ε+ +2 ≤ ρ2 . 10 10e13
≤ε+
23
(|z − xqi,j | ≤ 1) (i ∈ B1 (∆q (x, y)))
which can also be written as q (Fj (ξiq ) − ξi,j )(Fj (ξiq ) − xqi,j ) ≤ ρ2 ,
(18)
after specializing it for z = Fj (ξiq ) ∈ [0, 1]. Similarly, considering the optimality condition of the second player together with Equation (17), we get for all z ∈ [0, 1]: q q q Fj (ξiq ) − ξi,j + Ri,j,q − 2(Mi + ∆q (x, y))(xqi,j − yi,j ) (z − yi,j )≤ε which implies that q q q q Fj (ξiq ) − ξi,j (z − yi,j ) ≤ ε + (Ri,j,q − 2(Mi + ∆q (x, y))(xqi,j − yi,j ))(yi,j − z)
≤ε+
ρ2 ρ2 ρ2 q ≤ ρ2 , + 2|xqi,j − yi,j |≤ε+ +2 10 10 10e13
which is q q (Fj (ξiq ) − ξi,j )(Fj (ξiq ) − yi,j ) ≤ ρ2 ,
(19)
after specializing it for z = Fj (ξiq ). By averaging Equation (18) with Equation (19) we get: q 2 q (Fj (ξiq ) − ξi,j ) ≤ ρ2 =⇒ |Fj (ξiq ) − ξi,j |≤ρ
which implies that ξiq =
xqi +yiq 2
∀j ∈ [m].
is a solution to SmoothBrouwer, which is a contradiction. Thus there are 2
ρ at least 1/δ many i such that ∥xqi − yiq ∥1 ≥ 10e 13 , and
X
∥xq − y q ∥2 ≥
∥xqi − yiq ∥2
i∈B1 (∆q (x,y))
≥ ≥
1 m
X
∥xqi − yiq ∥21
i∈B1 (∆q (x,y))
ρ4 = 4m ≥ 3m + 1, 100e26 δm
concluding the proof, since by definition b(q) = Eq (∥xq − y q ∥2 ) = 1.
E.3
Proof of Lemma 3
Lemma 3 (Dichotomy). Let (x, y) be a solution to GDA-FixedPoint. Then either there exists i ∈ [n], v ∈ V such that (xvi + yiv )/2 is a solution to SmoothBrouwer, or b : V → {0, 1, ⊥}, as defined in Equation (5), is a solution to OraclePureCircuit. Proof. By Lemma 13 we have that either there is a (i, q) ∈ [n] × V such that (xqi + yiq )/2 is a solution to SmoothBrouwer, or that for all q ∈ V such that sq (x, y) = 1 then b(q) = 1. On the other hand, Lemma 11 always guarantees that sq (x, y) = 0 implies that b(q) = 0. Thus, we can assume that sv (x, y) = 1 =⇒ b(v) = 1 and sv (x, y) = 0 =⇒ b(v) = 0 for all v ∈ V . Now, we show that in this case, the assignment b satisfies all the gates: • (u, v, w) ∈ GNor . Assume that Eu (x, y) = Ev (x, y) = b(u) = b(v) = 0, then sw (x, y) = g(Eu (x, y) + Ev (x, y)) = g(0) = 1. By assumption, this implies that also b(w) = 1 and thus the gate is satisfied. On the other hand, if either b(u) = 1 or b(v) = 1, then Eu (x, y) + Ev (x, y) ≥ 1 and thus sw (x, y) = 0. By assumption, this implies that b(w) = 0, and thus Nor gates are satisfied. 24
• (u, v, w) ∈ GPurify . If b(u) = 0 then Eu (x, y) = 0 and thus sv (x, y) = sw (x, y) = ℓ(Eu (x, y) ± 1/4) = 0, which by assumption implies that b(v) = b(w) = 0. Similarly, if b(u) = 1 then Eu (x, y) = 1 and sv (x, y) = sw (x, y) = ℓ(Eu (x, y) ± 1/4) = 1, which by assumption implies that b(v) = b(w) = 1. On the other hand, if b(u) = ⊥, then Eu (x, y) ∈ (0, 1) but either Eu (x, y) − 1/4 ≤ 5/12 or Eu (x, y) + 1/4 ≥ 7/12, which implies that either sv (x, y) = 0 or sw (x, y) = 1, thus satisfying the gate’s constraints. • (u1 , . . . , uN , v) ∈ GOracle . Assume that (b(u1 ), . . . , b(uN )) ∈ {0, 1}N . Then Eui (x, y) = b(ui ) for all i ∈ [N ], and sv (x, y) = H((b(ui ))i∈[N ] , L). By Lemma 2, we get that sv (x, y) = L(b(u1 ), . . . , b(uN )) ∈ {0, 1}, which trivially shows that the gate is satisfied. By assumption we have that b(v) = L(b(u1 ), . . . , b(uN )) as desired. This proves that b is a valid assignment to OraclePureCircuit.
References [AKS83]
Miklós Ajtai, János Komlós, and Endre Szemerédi. “An O(n log n) sorting network”. In: Proceedings of the fifteenth annual ACM symposium on Theory of computing. 1983, pp. 1–9.
[Ana+25]
Ioannis Anagnostides, Gabriele Farina, Tuomas Sandholm, and Brian Hu Zhang. “A polynomialtime algorithm for variational inequalities under the Minty condition”. In: arXiv preprint arXiv:2504.03432 (2025).
[Bal+18]
David Balduzzi, Sebastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. “The mechanics of n-player differentiable games”. In: International Conference on Machine Learning. PMLR. 2018, pp. 354–363.
[BC26]
Martino Bernasconi and Matteo Castiglioni. “The Complexity of Min-Max Optimization with Product Constraints”. In: STOC (to appear). 2026.
[Ber+24]
Martino Bernasconi, Matteo Castiglioni, Andrea Celli, and Gabriele Farina. “On the Role of Constraints in the Complexity of Min-Max Optimization”. In: arXiv preprint arXiv:2411.03248 (2024).
[Car+20]
Yair Carmon, John C Duchi, Oliver Hinder, and Aaron Sidford. “Lower bounds for finding stationary points I”. In: Mathematical Programming 184.1 (2020), pp. 71–120.
[CLY24]
Xi Chen, Yuhao Li, and Mihalis Yannakakis. “Computing a Fixed Point of Contraction Maps in Polynomial Queries”. In: Proceedings of the 56th Annual ACM Symposium on Theory of Computing. 2024, pp. 1364–1373.
[CYH24]
Raphael Chinchilla, Guosong Yang, and Joao P Hespanha. “Newton and interior-point methods for (constrained) nonconvex–nonconcave minmax optimization with stability and instability guarantees”. In: Mathematics of Control, Signals, and Systems 36.2 (2024), pp. 381–421.
[Das22]
Constantinos Daskalakis. “Non-concave games: A challenge for game theory’s next 100 years”. In: Cowles Preprints (2022), p. 4.
[Del+24]
Argyrios Deligkas, John Fearnley, Alexandros Hollender, and Themistoklis Melissourgos. “PureCircuit: Tight Inapproximability for PPAD”. In: Journal of the ACM 71.5 (2024), 31:1–31:48.
[Dia25]
Jelena Diakonikolas. “Open Problems in Optimization”. In: SIAG on Optimization Views and News 33.1 (2025), pp. 1–12. url: https://siagoptimization.github.io/assets/views/ ViewsAndNews-33-1.pdf.
[DP18]
Constantinos Daskalakis and Ioannis Panageas. “The limit points of (optimistic) gradient descent in min-max optimization”. In: Advances in neural information processing systems 31 (2018).
[DSZ21]
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. “The complexity of constrained min-max optimization”. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing. 2021, pp. 1466–1478. 25
[Goo+14]
Ian J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. “Generative adversarial nets”. In: Advances in neural information processing systems 27 (2014).
[HK22]
Junsoo Ha and Gunhee Kim. “On convergence of lookahead in smooth games”. In: International Conference on Artificial Intelligence and Statistics. PMLR. 2022, pp. 4659–4684.
[HPV89]
Michael D Hirsch, Christos H Papadimitriou, and Stephen A Vavasis. “Exponential lower bounds for finding Brouwer fixed points”. In: Journal of Complexity 5.4 (1989), pp. 379–416.
[JNJ20]
Chi Jin, Praneeth Netrapalli, and Michael Jordan. “What is local optimality in nonconvexnonconcave minimax optimization?” In: International conference on machine learning. PMLR. 2020, pp. 4880–4889.
[Let+18]
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. “Stable opponent shaping in differentiable games”. In: arXiv preprint arXiv:1811.08469 (2018).
[Liu+24]
Yixin Liu, Argyris Oikonomou, Weiqiang Zheng, Yang Cai, and Arman Cohan. “COMAL: A convergent meta-algorithm for aligning LLMs with general preferences”. In: arXiv preprint arXiv:2410.23223 (2024).
[LJJ20]
Tianyi Lin, Chi Jin, and Michael Jordan. “On gradient descent ascent for nonconvex-concave minimax problems”. In: International conference on machine learning. PMLR. 2020, pp. 6083– 6093.
[LMM03]
Richard J Lipton, Evangelos Markakis, and Aranyak Mehta. “Playing large games using simple strategies”. In: Proceedings of the 4th ACM Conference on Electronic Commerce. 2003, pp. 36–41.
[Mad+18]
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. “Towards Deep Learning Models Resistant to Adversarial Attacks”. In: International Conference on Learning Representations. 2018.
[MPP18]
Panayotis Mertikopoulos, Christos Papadimitriou, and Georgios Piliouras. “Cycles in adversarial regularized learning”. In: Proceedings of the twenty-ninth annual ACM-SIAM symposium on discrete algorithms. SIAM. 2018, pp. 2703–2717.
[Mun+24]
Rémi Munos, Michal Valko, Daniele Calandriello, Mohammad Gheshlaghi Azar, Mark Rowland, Zhaohan Daniel Guo, Yunhao Tang, Matthieu Geist, Thomas Mesnard, Côme Fiegel, et al. “Nash learning from human feedback”. In: Forty-first International Conference on Machine Learning. 2024.
[Nou+19]
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. “Solving a class of non-convex min-max games using iterative first order methods”. In: Advances in Neural Information Processing Systems 32 (2019).
[OLR21]
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. “Efficient search of first-order Nash equilibria in nonconvex-concave smooth min-max problems”. In: SIAM Journal on Optimization 31.4 (2021), pp. 2508–2538.
[Pau+25]
Anselm Paulus, Ilia Kulikov, Brandon Amos, Rémi Munos, Ivan Evtimov, Kamalika Chaudhuri, and Arman Zharmagambetov. “Safety Alignment of LMs via Non-cooperative Games”. In: arXiv preprint arXiv:2512.20806 (2025).
[Raz+20]
Meisam Razaviyayn, Tianjian Huang, Songtao Lu, Maher Nouiehed, Maziar Sanjabi, and Mingyi Hong. “Nonconvex min-max optimization: Applications, challenges, and recent theoretical advances”. In: IEEE Signal Processing Magazine 37.5 (2020), pp. 55–66.
[RN23]
Anton Rodomanov and Yurii Nesterov. “Subgradient ellipsoid method for nonsmooth convex problems”. In: Mathematical Programming 199.1 (2023), pp. 305–341.
[Rub15]
Aviad Rubinstein. “Inapproximability of Nash equilibrium”. In: Proceedings of the forty-seventh annual ACM symposium on Theory of computing. 2015, pp. 409–418. 26
[Rub17]
Aviad Rubinstein. “Settling the complexity of computing approximate two-player Nash equilibria”. In: ACM SIGecom Exchanges 15.2 (2017), pp. 45–49.
[Sun+25]
Haoran Sun, Yusen Wu, Yukun Cheng, and Xu Chu. “Game theory meets large language models: a systematic survey”. In: Proceedings of the Thirty-Fourth International Joint Conference on Artificial Intelligence. 2025, pp. 10669–10677.
[Swa+24]
Gokul Swamy, Christoph Dann, Rahul Kidambi, Steven Wu, and Alekh Agarwal. “A Minimaximalist Approach to Reinforcement Learning from Human Feedback”. In: International Conference on Machine Learning. PMLR. 2024, pp. 47345–47377.
[Vav93]
Stephen A Vavasis. “Black-box complexity of local minimization”. In: SIAM Journal on Optimization 3.1 (1993), pp. 60–80.
[Vav95]
Stephen A Vavasis. “Complexity issues in global optimization: a survey”. In: Handbook of global optimization. Springer, 1995, pp. 27–41.
[VB23]
Abhijeet Vyas and Brian Bullins. “Beyond first-order methods for non-convex non-concave min-max optimization”. In: arXiv preprint arXiv:2304.08389 (2023).
[Zha+20]
Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. “Newton-type methods for minimax optimization”. In: arXiv preprint arXiv:2006.14592 (2020).
27