The Complexity of Constrained Min-Max Optimization

Introduction

Min-Max Optimization has played a central role in the development of Game Theory [vN28], Convex Optimization [Dan51, Adl13], and Online Learning [Bla56, CBL06, SS12, BCB12, SSBD14, Haz16]. In its general constrained form, it can be written down as follows:

The goal in (1.1) is to find a feasible pair $(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$, i.e., $g(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})\leq 0$, that satisfies the following

Unfortunately, our ability to solve Problem (1.1) remains rather poor in settings where our objective function $f$ is not convex-concave. This is emerging as a major challenge in Deep Learning, where min-max optimization has recently found many important applications, such as training Generative Adversarial Networks (see e.g. [GPM+14, ACB17]), and robustifying deep neural network-based models against adversarial attacks (see e.g. [MMS+18]). These applications are indicative of a broader deep learning paradigm wherein robustness properties of a deep learning system are tested and enforced by another deep learning system. In these applications, it is very common to encounter min-max problems with objectives that are nonconvex-nonconcave, and thus evade treatment by the classical algorithmic toolkit targeting convex-concave objectives.

Indeed, the optimization challenges posed by objectives that are nonconvex-nonconcave are not just theoretical frustration. Practical experience with first-order methods is rife with frustration as well. A common experience is that the training dynamics of first-order methods is unstable, oscillatory or divergent, and the quality of the points encountered in the course of training can be poor; see e.g. [Goo16, MPPSD16, DISZ18, MGN18, DP18, MR18, MPP18, ADLH19]. This experience is in stark contrast to minimization (resp. maximization) problems, where even for nonconvex (resp. nonconcave) objectives, first-order methods have been found to efficiently converge to approximate local optima or stationary points (see e.g. [AAZB+17, JGN+17, LPP+19]), while practical methods such Stochastic Gradient Descent, Adagrad, and Adam [DHS11, KB14, RKK18] are driving much of the recent progress in Deep Learning.

The goal of this paper is to shed light on the complexity of min-max optimization problems, and elucidate its difference to minimization and maximization problems—as far as the latter is concerned without loss of generality we focus on minimization problems, as maximization problems behave exactly the same; we will also think of minimization problems in the framework of (1.1), where the variable $\boldsymbol{y}$ is absent, that is $d_{2}=0$. An important driver of our comparison between min-max optimization and minimization is, of course, the nature of the objective. So let us discuss:

$\triangleright$ Convex-Concave Objective. The benign setting for min-max optimization is that where the objective function is convex-concave, while the benign setting for minimization is that where the objective function is convex. In their corresponding benign settings, the two problems behave quite similarly from a computational perspective in that they are amenable to convex programming, as well as first-order methods which only require gradient information about the objective function. Moreover, in their benign settings, both problems have guaranteed existence of a solution under compactness of the constraint set. Finally, it is clear how to define approximate solutions. We just relax the inequalities on the left hand side of (1.2) and (1.3) by some $\varepsilon>0$.

$\triangleright$ Nonconvex-Nonconcave Objective. By contrapositive, the challenging setting for min-max optimization is that where the objective is not convex-concave, while the challenging setting for minimization is that where the objective is not convex. In these challenging settings, the behavior of the two problems diverges significantly. The first difference is that, while a solution to a minimization problem is still guaranteed to exist under compactness of the constraint set even when the objective is not convex, a solution to a min-max problem is not guaranteed to exist when the objective is not convex-concave, even under compactness of the constrained set. A trivial example is this: $\min_{x\in}\max_{y\in}(x-y)^{2}$. Unsurprisingly, we show that checking whether a min-max optimization problem has a solution is $\mathsf{NP}$-hard. In fact, we show that checking whether there is an approximate min-max solution is $\mathsf{NP}$-hard, even when the function is Lispchitz and smooth and the desired approximation error is an absolute constant (see Theorem 10.1).

Since min-max solutions may not exist, what could we plausibly hope to compute? There are two obvious targets:

approximate stationary points of $f$, as considered e.g. by [ALW19]; and

some type of approximate local min-max solution.

Unfortunately, as far as (I) is concerned, it is still possible that (even approximate) stationary points may not exist, and we show that checking if there is one is $\mathsf{NP}$-hard, even when the constraint set is $^{d}$, the objective has Lipschitzness and smoothness polynomial in $d$, and the desired approximation is an absolute constant (Theorem 4.1). So we focus on (II), i.e. (approximate) local min-max solutions. Several kinds of those have been proposed in the literature [DP18, MR18, JNJ19]. We consider a generalization of the concept of local min-max equilibria, proposed in [DP18, MR18], that also accommodates approximation.

Given $f$, $g$ as above, and $\varepsilon,\delta>0$, some point $(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$ is an $(\varepsilon,\delta)$-local min-max solution of (1.1), or a $(\varepsilon,\delta)$-local min-max equilibrium, if it is feasible, i.e. $g(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})\leq 0$, and satisfies:

In words, $(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$ is an $(\varepsilon,\delta)$-local min-max equilibrium, whenever the min player cannot update $\boldsymbol{x}$ to a feasible point within $\delta$ of $\boldsymbol{x}^{\star}$ to reduce $f$ by at least $\varepsilon$, and symmetrically the max player cannot change $\boldsymbol{y}$ locally to increase $f$ by at least $\varepsilon$.

We show that the existence and complexity of computing such approximate local min-max equilibria depends on the relationship of $\varepsilon$ and $\delta$ with the smoothness, $L$, and the Lipschitzness, $G$, of the objective function $f$. We distinguish the following regimes, also shown in Figure 1 together with a summary of our associated results.

$\blacktriangleright$ Trivial Regime. This occurs when $\delta<\frac{\varepsilon}{G}$. This regime is trivial because the $G$-Lipschitzness of $f$ guarantees that all feasible points are $(\varepsilon,\delta)$-local min-max solutions.

$\blacktriangleright$ Local Regime. This occurs when $\delta<\sqrt{\frac{2\varepsilon}{L}}$, and it represents the interesting regime for min-max optimization. In this regime, we use the smoothness of $f$ to show that $(\varepsilon,\delta)$-local min-max solutions always exist. Indeed, we show (Theorem 5.1) that computing them is computationally equivalent to the following variant of (I) which is more suitable for the constrained setting:

(approximate) fixed points of the projected gradient descent-ascent dynamics (Section 3.3).

We show via an application of Brouwer’s fixed point theorem to the iteration map of the projected gradient descent-ascent dynamics that (I)’ are guaranteed to exist. In fact, not only do they exist, but computing them is in $\mathsf{PPAD}$, as can be shown by bounding the Lipschitzness of the projected gradient descent-ascent dynamics (Theorem 5.2).

$\blacktriangleright$ Global Regime. This occurs when $\delta$ is comparable to the diameter of the constraint set. In this case, the existence of $(\varepsilon,\delta)$-local min-max solutions is not guaranteed, and determining their existence is $\mathsf{NP}$-hard, even if $\varepsilon$ is an absolute constant (Theorem 10.1).

The main results of this paper, summarized in Figure 1, are to characterize the complexity of computing local min-max solutions in the local regime. Our first main theorem is the following:

Computing $(\varepsilon,\delta)$-local min-max solutions of Lipschitz and smooth objectives over convex compact domains in the local regime is $\mathsf{PPAD}$-complete. The hardness holds even when the constraint set is a polytope that is a subset of $^{d}$, the objective takes values in $$and the smoothness, Lipschitzness,$1/\varepsilon$and$1/\delta$are polynomial in the dimension. Equivalently, computing$\alpha$-approximate fixed points of the Projected Gradient Descent-Ascent dynamics on smooth and Lipschitz objectives is$\mathsf{PPAD}$-complete, and the hardness holds even when the the constraint set is a polytope that is a subset of$^{d}$, the objective takes values in$[-d,d]$and smoothness, Lipschitzness, and$1/\alpha$ are polynomial in the dimension.

For the above complexity result we assume that we have “white box” access to the objective function. An important byproduct of our proof, however, is to also establish an unconditional hardness result in the Nemirovsky-Yudin [NY83] oracle optimization model, wherein we are given black-box access to oracles computing the objective function and its gradient. Our second main result is informally stated in Informal Theorem 2.

Assume that we have black-box access to an oracle computing a $G$-Lipschitz and $L$-smooth objective function $f:\mathcal{P}\to$, where $\mathcal{P}\subseteq^{d}$ is a known polytope, and its gradient $\nabla f$. Then, computing an $(\varepsilon,\delta)$-local min-max solution in the local regime (i.e., when $\delta<\sqrt{2\varepsilon/L}$) requires a number of oracle queries that is exponential in at least one of the following: $1/\varepsilon$, $L$, $G$, or $d$. In fact, exponential in $d$-many queries are required even when $L$, $G$, $1/\varepsilon$ and $1/\delta$ are all polynomial in $d$.

Importantly, the above lower bounds, in both the white-box and the black-box setting, come in sharp contrast to minimization problems, given that finding approximate local minima of smooth non-convex objectives ranging in $[-B,B]$ in the local regime can be done using first-order methods using $O(B\cdot L/\varepsilon)$ time/queries (see Section E). Our results are the first to show an exponential separation between these two fundamental problems in optimization in the black-box setting, and a super-polynomial separation in the white-box setting assuming $\mathsf{PPAD}\neq\mathsf{FP}$.

We very briefly outline some of the main ideas for the $\mathsf{PPAD}$-hardness proof that we present in Sections 6 and 7. Our starting point as in many $\mathsf{PPAD}$-hardness results is a discrete analog of the problem of finding Brouwer fixed points of a continuous map. Departing from previous work, however, we do not use Sperner’s lemma as the discrete analog of Brouwer’s fixed point theorem. Instead, we define a new problem, called BiSperner, which is useful for showing our hardness results. BiSperner is closely related to the problem of finding panchromatic simplices guaranteed by Sperner’s lemma except, roughly speaking, that the vertices of the simplicization of a $d$-dimensional hypercube are colored with $2d$ rather than $d+1$ colors, every point of the simplicization is colored with $d$ colors rather than one, and we are seeking a vertex of the simplicization so that the union of colors on the vertices in its neighborhood covers the full set of colors. The first step of our proof is to show that BiSperner is $\mathsf{PPAD}$-hard. This step follows from the hardness of computing Brouwer fixed points.

The step that we describe next is only implicitly done by our proof, but it serves as useful intuition for reading and understanding it. We want to define a discrete two-player zero-sum game whose local equilibrium points correspond to solutions of a given BiSperner instance. Our two players, called “minimizer” and “maximizer,” each choose a vertex of the simplicization of the BiSperner instance. For every pair of strategies in our discrete game, i.e. vertices, chosen by our players, we define a function value and gradient values. Note that, at this point, we treat these values at different vertices of the simplicization as independent choices, i.e. are not defining a function over the continuum whose function values and gradient values are consistent with these choices. It is our intention, however, that in the continuous two-player zero-sum game that we obtain in the next paragraph via our interpolation scheme, wherein the minimizer and maximizer may choose any point in the continuous hypercube, the function value determines the payment of the minimizer to the maximizer, and the gradient value determines the direction of the best-response dynamics of the game. Before getting to that continuous game in the next paragraph, the main technical step of this discrete part of our construction is showing that every local equilibrium of the discrete game corresponds to a solution of the BiSperner instance we are reducing from. In order to achieve this we need to add some constraints to couple the strategies of the minimizer and the maximizer player. This step is the reason that the constraints $g(\boldsymbol{x},\boldsymbol{y})\leq 0$ appear in the final min-max problem that we produce.

The third and quite challenging step of the proof is to show that we can interpolate in a smooth and computationally efficient way the discrete zero-sum game of the previous step. In low dimensions (treated in Section 6) such smooth and efficient interpolation can be done in a relatively simple way using single-dimensional smooth step functions. In high dimensions, however, the smooth and efficient interpolation becomes a challenging problem and to the best of our knowledge no simple solution exists. For this reason we construct our novel smooth and efficient interpolation coefficients of Section 8. These are a technically involved construction that we believe will prove to be very useful for characterizing the complexity of approximate solutions of other optimization problems.

The last part of our proof is to show that all the previous steps can be implemented in an efficient way both with respect to computational but also with respect to query complexity. This part is essential for both our white-box and black-box results. Although this seems like a relatively easy step, it becomes more difficult due to the complicated expressions in our smooth and efficient interpolation coefficients used in our previous step.

Closing this section we mention that all our $\mathsf{NP}$-hardness results are proven using a cute application of Lovász Local Lemma [EL73], which provides a powerful rounding tool that can drive the inapproximability all the way up to an absolute constant.

2 Local Minimization vs Local Min-Max Optimization

Because our proof is convoluted, involving multiple steps, it is difficult to discern from it why finding local min-max solutions is so much harder than finding local minima. For this reason, we illustrate in this section a fundamental difference between local minimization and local min-max optimization. This provides good intuition about why our hardness construction would fail if we tried to apply it to prove hardness results for finding local minima (which we know don’t exist).

Ultimately a key difference between min-min and min-max optimization is that best-response paths in min-max optimization problems can be closed, i.e., can form a cycle, as shown in Figure 2, Panel (b). On the other hand, this is impossible in min-min problems as the function value must monotonically decrease along best-response paths, thus cycles may not exist.

The above discussion offers qualitative differences between min-min and min-max optimization, which lie in the heart of why our computational intractability results are possible to prove for min-max but not min-min problems. For the precise step in our construction that breaks if we were to switch from a min-max to a min-min problem we refer the reader to Remark 6.9.

3 Further Related Work

There is a broad literature on the complexity of equilibrium computation. Virtually all these results are obtained within the computational complexity formalism of total search problems in $\mathsf{NP}$, which was spearheaded by [JPY88, MP89, Pap94b] to capture the complexity of search problems that are guaranteed to have a solution. Some key complexity classes in this landscape are shown in Figure 3. We give a non-exhaustive list of intractability results for equilibrium computation: [FPT04] prove that computing pure Nash equilibria in congestion games is $\mathsf{PLS}$-complete; [DGP09] and later [CDT09] show that computing approximate Nash equilibria in normal-form games is $\mathsf{PPAD}$-complete; [EY10] study the complexity of computing exact Nash equilibria (which may use irrational probabilities), introducing the complexity class $\mathsf{FIXP}$;

[VY11, CPY17] consider the complexity of computing Market equilibria; [Das13, Rub15, Rub16] consider the complexity of computing approximate Nash equilibria of constant approximation; [KM18] establish a connection between approximate Nash equilibrium computation and the SoS hierarchy; [Meh14, DFS20] study the complexity of computing Nash equilibria in specially structured games. A result that is particularly useful for our work is the result of [HPV89] which shows black-box query lower bounds for computing Brouwer fixed points of a continuous function. We use this result in Section 9 as an ingredient for proving our black-box lower bounds for computing approximate local min-max solutions.

Beyond equilibrium computation and its applications to Economics and Game Theory, the study of total search problems has found profound connections to many scientific fields, including continuous optimization [DP11, DTZ18], combinatorial optimization [SY91], query complexity [BCE+95], topology [GH19], topological combinatorics and social choice theory [FG18, FG19, FRHSZ20b, FRHSZ20a], algebraic combinatorics [BIQ+17, GKSZ19], and cryptography [Jeř16, BPR15, SZZ18]. For a more extensive overview of total search problems we refer the reader to the recent survey by Daskalakis [Das18].

As already discussed, min-max optimization has intimate connections to the foundations of Game Theory, Mathematical Programming, Online Learning, Statistics, and several other fields. Recent applications of min-max optimization to Machine Learning, such as Generative Adversarial Networks and Adversarial Training, have motivated a slew of recent work targeting first-order (or other light-weight online learning) methods for solving min-max optimization problems for convex-concave, nonconvex-concave, as well as nonconvex-nonconcave objectives. Work on convex-concave and nonconvex-concave objectives has focused on obtaining online learning methods with improved rates [KM19, LJJ19, TJNO19, NSH+19, LTHC19, OX19, Zha19, ADSG19, AMLJG20, GPDO20, LJJ20] and last-iterate convergence guarantees [DISZ18, DP18, MR18, MPP18, RLLY18, HA18, ADLH19, DP19, LS19, GHP+19, MOP19, ALW19], while work on nonconvex-nonconcave problems has focused on identifying different notions of local min-max solutions [JNJ19, MV20] and studying the existence and (local) convergence properties of learning methods at these points [WZB19, MV20, MSV20].

Preliminaries

We study optimization problems involving real-valued functions, considering two access models to such functions.

Black Box Model. In this model we are given access to an oracle $\mathcal{O}_{f}$ such that given a point $\boldsymbol{x}\in^{d}$ the oracle $\mathcal{O}_{f}$ returns the values $f(\boldsymbol{x})$ and $\nabla f(\boldsymbol{x})$. In this model we assume that we can perform real number arithmetic operations. This is the traditional model used to prove lower bounds in Optimization and Machine Learning [NY83].

Promise Problems. To simplify the exposition of our paper, make the definitions of our computational problems and theorem statements clearer, and make our intractability results stronger, we choose to enforce the following constraints on our function access, $\mathcal{O}_{f}$ or $\mathcal{C}_{f}$, as a promise, rather than enforcing these constraints in some syntactic manner.

Consistency of Function Values and Gradient Values. Given some oracle $\mathcal{O}_{f}$ or Turing machine $\mathcal{C}_{f}$, it is difficult to determine by querying the oracle or examining the description of the Turing machine whether the function and gradient values output on different inputs are consistent with some differentiable function. In all our computational problems, we will only consider instances where this is promised to be the case. Moreover, for all our computational hardness results, the instances of the problems arising from our reductions satisfy these constraints, which are guaranteed syntactically by our reduction.

Lipschitzness, Smoothness and Boundedness. Similarly, given some oracle $\mathcal{O}_{f}$ or Turing machine $\mathcal{C}_{f}$, it is difficult to determine, by querying the oracle or examining the description of the Turing machine, whether the function and gradient values output by $\mathcal{O}_{f}$ or $\mathcal{C}_{f}$ are consistent with some Lipschitz, smooth and bounded function with some prescribed Lipschitzness, smoothness, and bound on its absolute value. In all our computational problems, we only consider instances where the $G$-Lipschitzness, $L$-smoothness and $B$-boundedness of the function are promised to hold for the prescribed, in the input of the problem, parameters $G$, $L$ and $B$. Moreover, for all our computational hardness results, the instances of the problems arising from our reductions satisfy this constraint, which is guaranteed syntactically by our reduction.

In summary, in the rest of this paper, whenever we prove an upper bound for some computational problem, namely an upper bound on the number of steps or queries to the function oracle required to solve the problem in the black-box model, or the containment of the problem in some complexity class in the white-box model, we assume that the afore-described properties are satisfied by the $\mathcal{O}_{f}$ or $\mathcal{C}_{f}$ provided in the input. On the other hand, whenever we prove a lower bound for some computational problem, namely a lower bound on the number of steps/queries required to solve it in the black-box model, or its hardness for some complexity class in the white-box model, the instances arising in our lower bounds are guaranteed to satisfy the above properties syntactically by our constructions. As such, our hardness results will not exploit the difficulty in checking whether $\mathcal{O}_{f}$ or $\mathcal{C}_{f}$ satisfy the above constraints in order to infuse computational complexity into our problems, but will faithfully target the computational problems pertaining to min-max optimization of smooth and Lipschitz objectives that we aim to understand in this paper.

1 Complexity Classes and Reductions

In this section we define the main complexity classes that we use in this paper, namely $\mathsf{NP}$, $\mathsf{FNP}$ and $\mathsf{PPAD}$, as well as the notion of reduction used to show containment or hardness of a problem for one of these complexity classes.

To define the complexity class $\mathsf{PPAD}$ we first define the notion of polynomial-time reductions between search problemsIn this paper we only define and consider Karp-reductions between search problems., and the computational problem End-of-a-LineThis problem is sometimes called End-of-the-Line, but we adopt the nomenclature proposed by [Rub16] since we agree that it describes the problem better..

A search problem $P_{1}$ is polynomial-time reducible to a search problem $P_{2}$ if there exist polynomial-time computable functions $f:\left\{0,1\right\}^{*}\to\left\{0,1\right\}^{*}$ and $g:\left\{0,1\right\}^{*}\times\left\{0,1\right\}^{*}\times\left\{0,1\right\}^{*}\to\left\{0,1\right\}^{*}$ with the following properties: (i) if $\boldsymbol{x}$ is an input to $P_{1}$, then $f(\boldsymbol{x})$ is an input to $P_{2}$; and (ii) if $\boldsymbol{y}$ is a solution to $P_{2}$ on input $f(\boldsymbol{x})$, then $g(\boldsymbol{x},f(\boldsymbol{x}),\boldsymbol{y})$ is a solution to $P_{1}$ on input $\boldsymbol{x}$.

To make sense of the above definition, we envision that the circuits $\mathcal{C}_{S}$ and $\mathcal{C}_{P}$ implicitly define a directed graph, with vertex set $\{0,1\}^{n}$, such that the directed edge $(\boldsymbol{x},\boldsymbol{y})\in\left\{0,1\right\}^{n}\times\left\{0,1\right\}^{n}$ belongs to the graph if and only if $\mathcal{C}_{S}(\boldsymbol{x})=\boldsymbol{y}$ and $\mathcal{C}_{P}(\boldsymbol{y})=\boldsymbol{x}$. As such, all vertices in the implicitly defined graph have in-degree and out-degree at most $1$. The above problem permits an output of $\boldsymbol{0}$ if $\boldsymbol{0}$ has equal in-degree and out-degree in this graph. Otherwise it permits an output $\boldsymbol{x}\neq\boldsymbol{0}$ such that $\boldsymbol{x}$ has in-degree or out-degree equal to . It follows by the parity argument on directed graphs, namely that in every directed graph the sum of in-degrees equals the sum of out-degrees, that End-of-a-Line is a total problem, i.e. that for any possible binary circuits $\mathcal{C}_{S}$ and $\mathcal{C}_{P}$ there exists a solution of the “0.” kind or the “1.” kind in the definition of our problem (or both). Indeed, if $\boldsymbol{0}$ has unequal in- and out-degrees, there must exist another vertex $\boldsymbol{x}\neq\boldsymbol{0}$ with unequal in- and out-degrees, thus one of these degrees must be (as all vertices in the graph have in- and out-degrees bounded by $1$).

We are finally ready to define the complexity class $\mathsf{PPAD}$ introduced by [Pap94b].

The complexity class $\mathsf{PPAD}$ contains all search problems that are polynomial time reducible to the End-of-a-Line problem.

The complexity class $\mathsf{PPAD}$ is of particular importance, since it contains lots of fundamental problems in Game Theory, Economics, Topology and several other fields [DGP09, Das18]. A particularly important $\mathsf{PPAD}$-complete problem is finding fixed points of continuous functions, whose existence is guaranteed by Brouwer’s fixed point theorem.

While not stated exactly in this form, the following is a straightforward implication of the results presented in [CDT09].

Computational Problems of Interest

In this section, we define the computational problems that we study in this paper and discuss our main results, postponing formal statements to Section 4. We start in Section 3.1 by defining the mathematical objects of our study, and proceed in Section 3.2 to define our main computational problems, namely: (1) finding approximate stationary points; (2) finding approximate local minima; and (3) finding approximate local min-max equilibria. In Section 3.3, we present some bonus problems, which are intimately related, as we will see, to problems (2) and (3). As discussed in Section 2, for ease of presentation, we define our problems as promise problems.

We define the concepts of stationary points, local minima, and local min-max equilibria of real valued functions, and make some remarks about their existence, as well as their computational complexity. The formal discussion of the latter is postponed to Sections 3.2 and 4.

Now that we have defined the domain of the real-valued functions that we consider in this paper we are ready to define a notion of approximate stationary points.

It is easy to see that there exist continuously differentiable functions $f$ that do not have any (approximate) stationary points, e.g. linear functions. As we will see later in this paper, deciding whether a given function $f$ has a stationary point is $\mathsf{NP}$-hard and, in fact, it is even $\mathsf{NP}$-hard to decide whether a function has an approximate stationary point of a very gross approximation. At the same time, verifying whether a given point is (approximately) stationary can be done efficiently given access to a polynomial-time Turing machine that computes $\nabla f$, so the problem of deciding whether an (approximate) stationary point exists lies in $\mathsf{NP}$, as long as we can guarantee that, if there is such a point, there will also be one with polynomial bit complexity. We postpone a formal discussion of the computational complexity of finding (approximate) stationary points or deciding their existence until we have formally defined our corresponding computational problem and settled the bit complexity of its solutions.

For the definition of local minima and local min-max equilibria we need the notion of closed $d$-dimensional Euclidean balls.

To be clear, using the term “local minimum” in Definition 3.5 is a bit of a misnomer, since for large enough values of $\delta$ the definition captures global minima as well. As $\delta$ ranges from large to small, our notion of $(\varepsilon,\delta)$-local minimum transitions from being an $\varepsilon$-globally optimal point to being an $\varepsilon$-locally optimal point. Importantly, unlike (approximate) stationary points, a $(\varepsilon,\delta)$-local minimum is guaranteed to exist for all $\varepsilon,\delta>0$ due to the compactness of $^{d}\cap\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ and the continuity of $f$. Thus the problem of finding an $(\varepsilon,\delta)$-local minimum is total for arbitrary values of $\varepsilon$ and $\delta$. On the negative side, for arbitrary values of $\varepsilon$ and $\delta$, there is no polynomial-size and polynomial-time verifiable witness for certifying that a point $\boldsymbol{x}^{\star}$ is an $(\varepsilon,\delta)$-local minimum. Thus the problem of finding an $(\varepsilon,\delta)$-local minimum is not known to lie in $\mathsf{FNP}$. As we will see in Section 4, this issue can be circumvented if we focus on particular settings of $\varepsilon$ and $\delta$, in relationship to the Lipschitzness and smoothness of $f$ and the dimension $d$.

Finally we define $(\varepsilon,\delta)$-local min-max equilibrium as follows, recasting Definition 1.1 to the constraint set $\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$.

$f(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})<f(\boldsymbol{x},\boldsymbol{y}^{\star})+\varepsilon$ for every $\boldsymbol{x}\in\mathsf{B}_{d_{1}}(\delta;\boldsymbol{x}^{\star})$ with $(\boldsymbol{x},\boldsymbol{y}^{\star})\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$; and

$f(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})>f(\boldsymbol{x}^{\star},\boldsymbol{y})-\varepsilon$ for every $\boldsymbol{y}\in\mathsf{B}_{d_{2}}(\delta;\boldsymbol{y}^{\star})$ with $(\boldsymbol{x}^{\star},\boldsymbol{y})\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$.

Similarly to Definition 3.5, for large enough values of $\delta$, Definition 3.6 captures global min-max equilibria as well. As $\delta$ ranges from large to small, our notion of $(\varepsilon,\delta)$-local min-max equilibrium transitions from being an $\varepsilon$-approximate min-max equilibrium to being an $\varepsilon$-approximate local min-max equilibrium. Moreover, in comparison to local minima and stationary points, the problem of finding an $(\varepsilon,\delta)$-local min-max equilibrium is neither total nor can its solutions be verified efficiently for all values of $\varepsilon$ and $\delta$, even when $\mathcal{P}(\boldsymbol{A},\boldsymbol{b})=^{d}$. Again, this issue can be circumvented if we focus on particular settings of $\varepsilon$ and $\delta$ values, as we will see in Section 4.

2 First-Order Local Optimization Computational Problems

In this section, we define the search problems associated with our aforementioned definitions of approximate stationary points, local minima, and local min-max equilibria. We state our problems in terms of white-box access to the function $f$ and its gradient. Switching to the black-box variants of our computational problems amounts to simply replacing the Turing machines provided in the input of the problems with oracle access to the function and its gradient, as discussed in Section 2. As per our discussion in the same section, we define our computational problems as promise problems, the promise being that the Turing machine (or oracle) provided in the input to our problems outputs function values and gradient values that are consistent with a smooth and Lipschitz function with the prescribed in the input smoothness and Lipschitzness. Besides making the presentation cleaner, as we discussed in Section 2, the motivation for doing so is to prevent the possibility that computational complexity is tacked into our problems due to the possibility that the Turing machines/oracles provided in the input do not output function and gradient values that are consistent with a Lipschitz and smooth function. Importantly, all our computational hardness results syntactically guarantee that the Turing machines/oracles provided as input to our constructed hard instances satisfy these constraints.

Before stating our main computational problems below, we note that, for each problem, the dimension $d$ (in unary representation) is also an implicit input, as the description of the Turing machine $\mathcal{C}_{f}$ (or the interface to the oracle $\mathcal{O}_{f}$ in the black-box counterpart of each problem below) has size at least linear in $d$. We also refer to Remark 2.6 for how we may formally study complexity problems that take a polynomial-time Turing Machine in their input.

It is easy to see that StationaryPoint lies in $\mathsf{FNP}$. Indeed, if there exists some point $\boldsymbol{x}\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ such that $\left\|\nabla f(\boldsymbol{x})\right\|_{2}<\varepsilon/2$, then by the $L$-smoothness of $f$ there must exist some point $\boldsymbol{x}^{\star}\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ of bit complexity polynomial in the size of the input such that $\left\|\nabla f(\boldsymbol{x}^{\star})\right\|_{2}<\varepsilon$. On the other hand, it is clear that no such point exists if for all $\boldsymbol{x}\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$, $\left\|\nabla f(\boldsymbol{x})\right\|_{2}>\varepsilon$. We note that the looseness of the output requirement in our problem for functions $f$ that do not have points $x\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ such that $\left\|\nabla f(\boldsymbol{x})\right\|_{2}<\varepsilon/2$ but do have points $x\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ such that $\left\|\nabla f(\boldsymbol{x})\right\|_{2}\leq\varepsilon$ is introduced for the sole purpose of making the problem lie in $\mathsf{FNP}$, as otherwise we would not be able to guarantee that the solutions to our search problem have polynomial bit complexity. As we show in Section 4, StationaryPoint is also $\mathsf{FNP}$-hard, even when $\varepsilon$ is a constant, the constraint set is very simple, namely $\mathcal{P}(\boldsymbol{A},\boldsymbol{b})=^{d}$, and $G,L$ are both polynomial in $d$.

Next, we define the computational problems associated with local minimum and local min-max equilibrium. Recall that the first is guaranteed to have a solution, because, in particular, a global minimum exists due to the continuity of $f$ and the compactness of $\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$.

3 Bonus Problems: Fixed Points of Gradient Descent/Gradient Descent-Ascent

Next we present a couple of bonus problems, GDFixedPoint and GDAFixedPoint, which respectively capture the computation of fixed points of the (projected) gradient descent and the (projected) gradient descent-ascent dynamics, with learning rate $=1$. As we see in Section 5, these problems are intimately related, indeed equivalent under polynomial-time reductions, to problems LocalMin and LocalMinMax respectively, in certain regimes of the approximation parameters. Before stating problems GDFixedPoint and GDAFixedPoint, we define the mappings $F_{GD}$ and $F_{GDA}$ whose fixed points these problems are targeting.

for all $(\boldsymbol{x},\boldsymbol{y})\in K$, where $K(\boldsymbol{y})=\{\boldsymbol{x}^{\prime}\mid(\boldsymbol{x}^{\prime},\boldsymbol{y})\in K\}$ and $K(\boldsymbol{x})=\{\boldsymbol{y}^{\prime}\mid(\boldsymbol{x},\boldsymbol{y}^{\prime})\in K\}$.

Note that $F_{GDA}$ is called “unsafe” because the projection happens individually for $\boldsymbol{x}-\nabla_{\boldsymbol{x}}f(\boldsymbol{x},\boldsymbol{y})$ and $\boldsymbol{y}+\nabla_{\boldsymbol{y}}f(\boldsymbol{x},\boldsymbol{y})$, thus $F_{GDA}(\boldsymbol{x},\boldsymbol{y})$ may not lie in $K$. We also define the “safe” version $F_{sGDA}$, which projects the pair $(\boldsymbol{x}-\nabla_{\boldsymbol{x}}f(\boldsymbol{x},\boldsymbol{y}),\boldsymbol{y}+\nabla_{\boldsymbol{y}}f(\boldsymbol{x},\boldsymbol{y}))$ jointly onto $K$. As we show in Section 5 (in particular inside the proof of Theorem 5.2), computing fixed points of $F_{GDA}$ and $F_{sGDA}$ are computationally equivalent so we stick to $F_{GDA}$ which makes the presentation slightly cleaner.

We are now ready to define GDFixedPoint and GDAFixedPoint. As per earlier discussions, we define these computational problems as promise problems, the promise being that the Turing machine provided in the input to these problems outputs function values and gradient values that are consistent with a smooth and Lipschitz function with the prescribed, in the input to these problems, smoothness and Lipschitzness.

Summary of Results

In this section we summarize our results for the optimization problems that we defined in the previous section. We start with our theorem about the complexity of finding approximate stationary points, which we show to be $\mathsf{FNP}$-complete even for large values of the approximation.

The computational problem StationaryPoint is $\mathsf{FNP}$-complete, even when $\varepsilon$ is set to any value $\leq 1/24$, and even when $\mathcal{P}(\boldsymbol{A},\boldsymbol{b})=^{d}$, $G=\sqrt{d}$, $L=d$, and $B=1$.

The complexity of LocalMin and LocalMinMax is more difficult to characterize, as the nature of these problems changes drastically depending on the relationship of $\delta$ with with $\varepsilon$, $G$, $L$ and $d$, which determines whether these problems ask for a globally vs locally approximately optimal solution. In particular, there are two regimes wherein the complexity of both problems is simple to characterize.

Global Regime. When $\delta\geq\sqrt{d}$ then both LocalMin and LocalMinMax ask for a globally optimal solution. In this regime it is not difficult to see that both problems are $\mathsf{FNP}$-hard to solve even when $\varepsilon=\Theta(1)$ and $G$, $L$ are $O(d)$ (see Section 10).

Trivial Regime. When $\delta$ satisfies $\delta<\varepsilon/G$, then for every point $\boldsymbol{z}\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ it holds that $\left|f(\boldsymbol{z})-f(\boldsymbol{z}^{\prime})\right|<\varepsilon$ for every $\boldsymbol{z}^{\prime}\in\mathsf{B}_{d}(\delta;\boldsymbol{z})$ with $\boldsymbol{z}^{\prime}\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$. Thus, every point $\boldsymbol{z}$ in the domain $\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ is a solution to both LocalMin and LocalMinMax.

It is clear from our discussion above, and in earlier sections, that, to really capture the complexity of finding local as opposed to global minima/min-max equilibria, we should restrict the value of $\delta$. We identify the following regime, which we call the “local regime.” As we argue shortly, this regime is markedly different from the global regime identified above in that (i) a solution is guaranteed to exist for both our problems of interest, where in the global regime only LocalMin is guaranteed to have a solution; and (ii) their computational complexity transitions to lower complexity classes.

Local Regime. Our main focus in this paper is the regime defined by $\delta<\sqrt{2\varepsilon/L}$. In this regime it is well known that Projected Gradient Descent can solve LocalMin in time $O(B\cdot L/\varepsilon)$ (see Appendix E). Our main interest is understanding the complexity of LocalMinMax, which is not well understood in this regime. We note that the use of the constant $2$ in the constraint $\delta<\sqrt{2\varepsilon/L}$ which defines the local regime has a natural motivation: consider a point $\boldsymbol{z}$ where a $L$-smooth function $f$ has $\nabla f(\boldsymbol{z})=0$; it follows from the definition of smoothness that $\boldsymbol{z}$ is both an $(\varepsilon,\delta)$-local min and an $(\varepsilon,\delta)$-local min-max equilibrium, as long as $\delta<\sqrt{2\varepsilon/L}$.

The following theorems provide tight upper and lower bounds on the computational complexity of solving LocalMinMax in the local regime. For compactness, we define the following problem:

We define the local-regime local min-max equilibrium computation problem, in short LR-LocalMinMax, to be the search problem LocalMinMax restricted to instances in the local regime, i.e. satisfying $\delta<\sqrt{2\varepsilon/L}$.

The computational problem LR-LocalMinMax belongs to $\mathsf{PPAD}$. As a byproduct, if some function $f$ is $G$-Lipschitz and $L$-smooth, then an $(\varepsilon,\delta)$-local min-max equilibrium is guaranteed to exist when $\delta<\sqrt{2\varepsilon/L}$, i.e. in the local regime.

An important property of our reduction in the proof of Theorem 4.4 is that it is a black-box reduction. We can hence prove the following unconditional lower bound in the black-box model.

Our main goal in the rest of the paper is to provide the proofs of Theorems 4.3, 4.4 and 4.5. In Section 5, we show how to use Brouwer’s fixed point theorem to prove the existence of approximate local min-max equilibrium in the local regime. Moreover, we establish an equivalence between LocalMinMax and GDAFixedPoint, in the local regime, and show that both belong to $\mathsf{PPAD}$. In Sections 6 and 7, we provide a detailed proof of our main result, i.e. Theorem 4.4. Finally, in Section 9, we show how our proof from Section 7 produces as a byproduct the black-box, unconditional lower bound of Theorem 4.5. In Section 8, we outline a useful interpolation technique which allows as to interpolate a function given its values and the values of its gradient on a hypergrid, so as to enforce the Lipschitzness and smoothness of the interpolating function. We make heavy use of this technically involved result in all our hardness proofs.

Existence of Approximate Local Min-Max Equilibrium

In this section, we establish the totality of LR-LocalMinMax, i.e. LocalMinMax for instances satisfying $\delta<\sqrt{2\varepsilon/L}$ as defined in Definition 4.2. In particular, we prove that every $G$-Lipschitz and $L$-smooth function admits an $(\varepsilon,\delta)$-local min-max equilibrium, as long as $\delta<\sqrt{2\varepsilon/L}$. A byproduct of our proof is in fact that LR-LocalMinMax lies inside $\mathsf{PPAD}$. Specifically the main tool that we use to prove our result is a computational equivalence between the problem of finding fixed points of the Gradient Descent/Ascent dynamic, i.e. GDAFixedPoint, and the problem LR-LocalMinMax. A similar equivalence between GDFixedPoint and LocalMin also holds, but the details of that are left to the reader as a simple exercise. Next, we first present the equivalence between GDAFixedPoint and LR-LocalMinMax, and we then show that GDAFixedPoint is in $\mathsf{PPAD}$, which then also establishes that LR-LocalMinMax is in $\mathsf{PPAD}$.

For arbitrary $\varepsilon>0$ and $0<\delta<\sqrt{2\varepsilon/L}$, suppose that $(\boldsymbol{x}^{\ast},\boldsymbol{y}^{\ast})\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ is an $\alpha$-approximate fixed point of $F_{GDA}$, i.e., $\left\|(\boldsymbol{x}^{\ast},\boldsymbol{y}^{\ast})-F_{GDA}(\boldsymbol{x}^{\ast},\boldsymbol{y}^{\ast})\right\|_{2}<\alpha$, where $\alpha\leq\frac{\sqrt{(G+\delta)^{2}+4(\varepsilon-\frac{L}{2}\delta^{2})}-(G+\delta)}{2}$. Then $(\boldsymbol{x}^{\ast},\boldsymbol{y}^{\ast})$ is also a $(\varepsilon,\delta)$-local min-max equilibrium of $f$.

For arbitary $\alpha>0$, suppose that $(\boldsymbol{x}^{\ast},\boldsymbol{y}^{\ast})$ is an $(\varepsilon,\delta)$-local min-max equilibrium of $f$ for $\varepsilon=\frac{\alpha^{2}\cdot L}{(5L+2)^{2}}$ and $\delta=\sqrt{\varepsilon/L}$. Then $(\boldsymbol{x}^{\ast},\boldsymbol{y}^{\ast})$ is also an $\alpha$-approximate fixed point of $F_{GDA}$.

The proof of Theorem 5.1 is presented in Appendix B.1. As already discussed, we use GDAFixedPoint as an intermediate step to establish the totality of LR-LocalMinMax and to show its inclusion in $\mathsf{PPAD}$. This leads to the following theorem.

The computational problems GDAFixedPoint and LR-LocalMinMax are both total search problems and they both lie in $\mathsf{PPAD}$.

Observe that Theorem 4.3 is implied by Theorem 5.2 whose proof is presented in Appendix B.2.

Hardness of Local Min-Max Equilibrium – Four-Dimensions

In Section 5, we established that LR-LocalMinMax belongs to $\mathsf{PPAD}$. Our proof is via the intermediate problem GDAFixedPoint which we showed that it is computationally equivalent to LR-LocalMinMax. Our next step is to prove the $\mathsf{PPAD}$-hardness of LR-LocalMinMax using again GDAFixedPoint as an intermediate problem.

The problem GDAFixedPoint is $\mathsf{PPAD}$-complete even in dimension $d=4$ and $B=2$. Therefore, LR-LocalMinMax is $\mathsf{PPAD}$-complete even in dimension $d=4$ and $B=2$.

The first color of every vertex is either $1^{-}$ or $1^{+}$ and the second color is either $2^{-}$ or $2^{+}$.

The first color of all vertices on the left boundary of the grid is $1^{+}$.

The first color of all vertices on the right boundary of the grid is $1^{-}$.

The second color of all vertices on the bottom boundary of the grid is $2^{+}$.

The second color of all vertices on the top boundary of the grid is $2^{-}$.

Consider the function $g(\boldsymbol{x})=M(\boldsymbol{x})-\boldsymbol{x}$. Since $M$ is $L$-Lipschitz, the function $g:^{2}\to^{2}$ is also $(L+1)$-Lipschitz. Additionally $g$ can be easily computed via a polynomial-time Turing machine $\mathcal{C}_{g}$ that uses $\mathcal{C}_{M}$ as a subroutine. We construct a proper coloring of a fine grid of $^{2}$ using the signs of the outputs of $g$. Namely we set $n=\mathop{\left\lceil\log(L/\gamma)+2\right\rceil}$ and this defines a $2^{n}\times 2^{n}$ grid over $^{2}$ that is indexed by $\{0,1\}^{n}\times\{0,1\}^{n}$. Let $g_{\eta}:^{2}\to^{2}$ be the function that the Turing Machine $\mathcal{C}_{g}$ evaluate when the requested accuracy is $\eta>0$. Now we can define the circuit $\mathcal{C}_{l}$ as follows, We remind that we abuse the notation and we use a coordinate $i\in\{0,1\}^{n}$ both as a binary string and as a number in $\left(\left[2^{n}-1\right]-1\right)$ and it is clear from the context which of the two we use.

Let $\eta=\frac{\gamma}{2\sqrt{2}}$, there exists $\boldsymbol{x}\in R$ such that $\left|g_{1}(\boldsymbol{x})\right|\leq\frac{\gamma}{2\sqrt{2}}$ and $\boldsymbol{y}\in R$ such that $\left|g_{2}(\boldsymbol{y})\right|\leq\frac{\gamma}{2\sqrt{2}}$.

We will prove the existence of $\boldsymbol{x}$ and the existence of $\boldsymbol{y}$ follows using an identical argument. If there exists a corner $\boldsymbol{x}$ of $R$ such that $g_{1}(\boldsymbol{x})$ is in the range $[-\eta,\eta]$ then the claim follows. Suppose not. Using this together with the fact that the first color of one of the corners of $R$ is $1^{-}$ and also the first color of one of the corners of $R$ is $1^{+}$ we conclude that there exist points $\boldsymbol{x},\boldsymbol{x}^{\prime}$ such that $g_{\eta,1}(\boldsymbol{x})\geq 0$ and $g_{\eta,1}(\boldsymbol{x}^{\prime})\leq 0$ The latter is inaccurate for the cases where the vertex $(0,j)$ belongs to either facets $i=0$ or $i=2^{n}-1$. Notice that the coloring in such vertices does not depend on the value of $g_{\eta}$. However in case where the color of such a corner is not consistent with the value of $g_{\eta}$, i.e. $g_{\eta,1}(0,j)<0$ and $\mathcal{C}_{l}^{1}(0,j)=1$ then this means that $|g_{1}(0,j)|\leq\eta$. This is due to the fact that $g_{1}(0,j)\geq 0$ and $|g_{1}(0,j)-g_{1,\eta}(0,j)|\leq\eta$.. But we have that $\left\|g_{\eta}-g\right\|_{2}\leq\eta$. This together with the fact that $g_{1}(\boldsymbol{x})\not\in[-\eta,\eta]$ and $g_{1}(\boldsymbol{x}^{\prime})\not\in[-\eta,\eta]$ implies that $g_{1}(\boldsymbol{x})\geq 0$ and also $g_{1}(\boldsymbol{x}^{\prime})\leq 0$. But because of the $L$-Lipschitzness of $g$ and because the distance between $\boldsymbol{x}$ and $\boldsymbol{x}^{\prime}$ is at most $\sqrt{2}\frac{\gamma}{4L}$ we conclude that $\left|g_{1}(\boldsymbol{x})-g_{1}(\boldsymbol{x}^{\prime})\right|\leq\frac{\gamma}{2\sqrt{2}}$. Hence due to the signs of $g_{1}(\boldsymbol{x})$ and $g_{1}(\boldsymbol{x}^{\prime})$ we conclude that $\left|g_{1}(\boldsymbol{x})\right|\leq\frac{\gamma}{2\sqrt{2}}$. The same way we can prove that $\left|g_{1}(\boldsymbol{y})\right|\leq\frac{\gamma}{2\sqrt{2}}$ and the claim follows. ∎

Using the Claim 6.3 and the $L$-Lipschitzness of $g$ we get that for every $\boldsymbol{z}\in R$

where we have used also the fact that for any two points $\boldsymbol{z},\boldsymbol{w}$ it holds that $\left\|\boldsymbol{z}-\boldsymbol{w}\right\|_{2}\leq\sqrt{2}\frac{\gamma}{4L}$ which follows from the definition of the size of the grid. Therefore we have that $\left\|g(\boldsymbol{z})\right\|_{2}\leq\gamma$ and hence $\left\|M(\boldsymbol{z})-\boldsymbol{z}\right\|_{2}\leq\gamma$ which implies that any point $\boldsymbol{z}\in R$ is a $\gamma$-approximate fixed point of $M$ and the lemma follows. ∎

2 From 2D Bi-Sperner to Fixed Points of Gradient Descent/Ascent

The simplest way to achieve this is to define the function $f$ locally close to $(\boldsymbol{x},\boldsymbol{y})$ to be equal to

Similarly, if $\boldsymbol{x}$ is on a vertex of the $N\times N$ grid, and the coloring of this vertex is $(1^{-},2^{-})$, i.e. the output of $\mathcal{C}_{l}$ on this vertex is $(-1,-1)$, then we would like to have

The simplest way to achieve this is to define the function $f$ locally close to $(\boldsymbol{x},\boldsymbol{y})$ to be equal to

In Figure 5 we show pictorially the correspondence of the colors of the vertices of the grid with the gradient of the function $f$ that we design. As shown in the figure, any set of vertices that share at least one of the colors $1^{+}$, $1^{-}$, $2^{+}$, $2^{-}$, agree on the direction of the gradient with respect the horizontal or the vertical axis. This observation is one of the main ingredients in the proof of correctness of our reduction that we present later in this section.

When $\boldsymbol{x}$ is not on a vertex of the $N\times N$ grid then our goal is to define $f$ via interpolating the functions corresponding to the corners of the cell in which $\boldsymbol{x}$ belongs. The reason that this interpolation is challenging is that we need to make sure the following properties are satisfied

the resulting function $f$ is both Lipschitz and smooth inside every cell,

the resulting function $f$ is both Lipschitz and smooth even at the boundaries of every cell, where two differect cells stick together,

For the low dimensional case, that we explore in this section, satisfying the first two properties is not a very difficult task, whereas for the third property we need to be careful and achieving this property is the main technical contribution of this section. On the contrary, for the high-dimensional case that we explore in Section 7 even achieving the first two properties is very challenging and technical.

As we will see in Section 6.2.1, if we accomplish a construction of a function $f$ with the aforementioned properties, then the fixed points of the projected Gradient Descent/Ascent can only appear inside cells that have all of the colors $\{1^{-},1^{+},2^{-},2^{+}\}$ at their corners. To see this consider a cell that misses some color, e.g. $1^{+}$. Then all the corners of this cell have as first color $1^{-}$. Since $f$ is defined as interpolation of the functions in the corners of the cells, with the aforementioned properties, inside that cell there is always a direction with respect to $x_{1}$ and $y_{1}$ for which the gradient is large enough. Hence any point inside that cell cannot be a fixed point of the projected Gradient Descent/Ascent. Of course this example provides just an intuition of our construction and ignores case where the cell is on the boundary of the grid. We provide a detailed explanation of this case in Section 6.2.1.

The above neat idea needs some technical adjustments in order to work. At first, the interpolation of the function in the interior of the cell must be smooth enough so that the resulting function is both Lipschitz and smooth. In order to satisfy this, we need to choose appropriate coefficients of the interpolation that interpolate smoothly not only the value of the function but also its derivatives. For this purpose we use the following smooth step function of order $1$.

We define $S_{1}:\to$ to be the smooth step function of order $1$ that is equal to $S_{1}(x)=3x^{2}-2x^{3}$. Observe that the following hold $S_{1}(0)=0$, $S_{1}(1)=1$, $S_{1}^{\prime}(0)=0$, and $S_{1}^{\prime}(1)=0$.

As we have discussed, another issue is that since the interpolation coefficients depend on the value of $\boldsymbol{x}$ it could be that the derivatives of these coefficients overpower the derivatives of the functions that we interpolate. In this case we could be potentially creating fixed points of Gradient Descent/Ascent even in non panchromatic squares. As we will see later the magnitude of the derivatives from the interpolation coefficients depends on the differences $x_{1}-y_{1}$ and $x_{2}-y_{2}$. Hence if we ensure that these differences are small then the derivatives of the interpolation coefficients will have to remain small and hence they can never overpower the derivatives from the corners of every cell. This is the place in our reduction where we add the constraints $\boldsymbol{A}\cdot(\boldsymbol{x},\boldsymbol{y})\leq\boldsymbol{b}$ that define the domain of the function $f$ as we describe in Section 3.

Now that we have summarized the main ideas of our construction we are ready for the formal definition of $f$ based on the coloring circuit $\mathcal{C}_{l}$.

where the coefficients $\alpha_{1}(\boldsymbol{x}),\alpha_{2}(\boldsymbol{x})\in$ are defined as follows

where $\delta\triangleq 1/(N-1)=1/(2^{n}-1)$.

In Figure 6 we present an example of the application of Definition 6.5 to a specific cell with some given coloring on the corners.

An important property of the definition of the function $f_{\mathcal{C}_{l}}$ is that the coefficients used in the definition of $\alpha_{i}$ have the following two properties

Hence the function $f_{\mathcal{C}_{l}}$ inside a cell is a smooth convex combination of the functions on the corners of the cell, as is suggested from Figure 6. Of course there are many ways to define such convex combination but in our case we use the smooth step function $S_{1}$ to ensure the Lipschitz continuous gradient of the overall function $f_{\mathcal{C}_{l}}$. We prove this formally in the next lemma.

Let $f_{\mathcal{C}_{l}}$ be the function defined based on a coloring circuit $\mathcal{C}_{l}$, as per Definition 6.5. Then $f_{\mathcal{C}_{l}}$ is continuous and differentiable at any point $(\boldsymbol{x},\boldsymbol{y})\in^{4}$. Moreover, $f_{\mathcal{C}_{l}}$ is $\Theta(1/\delta)$-Lipschitz and $\Theta(1/\delta^{2})$-smooth in the whole 4-dimensional hypercube $^{4}$, where $\delta=1/(N-1)=1/(2^{n}-1)$.

Clearly from Definition 6.5, $f_{\mathcal{C}_{l}}$ is differentiable at any point $(\boldsymbol{x},\boldsymbol{y})\in^{4}$ in which $\boldsymbol{x}$ lies on the strict interior of its respective cell. In this case the derivative with respect to $x_{1}$ is

where for $\partial\alpha_{1}(\boldsymbol{x})/\partial x_{1}$ we have that

Now since $\max_{z\in}\left|S^{\prime}_{1}(z)\right|\leq 6$, we can conclude that $\left|\frac{\partial\alpha_{1}(\boldsymbol{x})}{\partial x_{1}}\right|\leq 24/\delta$. Similarly we can prove that $\left|\frac{\partial\alpha_{2}(\boldsymbol{x})}{\partial x_{1}}\right|\leq 24/\delta$, which combined with $\left|\alpha_{1}(\boldsymbol{x})\right|\leq 1$ implies $\left|\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x},\boldsymbol{y})}{\partial x_{1}}\right|\leq O(1/\delta)$. Using similar reasoning we can prove that $\left|\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x},\boldsymbol{y})}{\partial x_{2}}\right|\leq O(1/\delta)$ and that $\left|\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x},\boldsymbol{y})}{\partial y_{i}}\right|\leq 1$ for $i=1,2$. Hence

The only thing we are missing to prove the Lipschitzness of $f_{\mathcal{C}_{l}}$ is to prove its continuity on the boundaries of the cells of our subdivision. Suppose $\boldsymbol{x}$ lies on the boundary of some cell, e.g. let $\boldsymbol{x}$ lie on edge $(C,D)$ of one cell that is the same as the edge $(A^{\prime},B^{\prime})$ of the cell to the right of that cell. Since $S_{1}(0)=0$, $S^{\prime}_{1}(0)=0$ and $S^{\prime}_{1}(1)=0$ it holds that $\partial\alpha_{1}(\boldsymbol{x})/\partial x_{1}=0$ and the same for $\alpha_{2}$. Therefore the value of $\partial f_{\mathcal{C}_{l}}/\partial x_{1}$ remains the same no matter the cell according to which it was calculated. As a result, $f_{\mathcal{C}_{l}}$ is differentiable with respect to $x_{1}$ even if $\boldsymbol{x}$ belongs in the boundary of its cell. Using the exact same reasoning for the rest of the variables, one can show that the function $f_{\mathcal{C}_{l}}$ is differentiable at any point $(\boldsymbol{x},\boldsymbol{y})\in^{4}$ and because of the aforementioned bound on the gradient $\nabla f_{\mathcal{C}_{l}}$ we can conclude that $f_{\mathcal{C}_{l}}$ is $O(1/\delta)$-Lipschitz.

Using very similar calculations, we can compute the closed formulas of the second derivatives of $f_{\mathcal{C}_{l}}$ and using the bounds $\left|f_{\mathcal{C}_{l}}(\cdot)\right|\leq 2$, $\left|S_{1}(\cdot)\right|\leq 1$, $\left|S^{\prime}_{1}(\cdot)\right|\leq 6$, and $\left|S^{\prime\prime}_{1}(\cdot)\right|\leq 6$, we can prove that each entry of the Hessian $\nabla^{2}f_{\mathcal{C}_{l}}(\boldsymbol{x},\boldsymbol{y})$ is bounded by $O(1/\delta^{2})$ and thus

which implies the $\Theta(1/\delta^{2})$-smoothness of $f_{\mathcal{C}_{l}}$. ∎

$\boldsymbol{(+)}$ Construction of Instance for Fixed Points of Gradient Descent/Ascent.

Our construction can be described via the following properties.

The payoff function is the real-valued function $f_{\mathcal{C}_{l}}(\boldsymbol{x},\boldsymbol{y})$ from the Definition 6.5.

The domain is the polytope $\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$ that we described in Section 3. The matrix $\boldsymbol{A}$ and the vector $\boldsymbol{b}$ have constant size and they are computed so that the following inequalities hold

where $\Delta=\delta/12$ and $\delta=1/(N-1)=1/(2^{n}-1)$.

The parameter $\alpha$ is set to be equal to $\Delta/3$.

The parameters $G$ and $L$ are set to be equal to the upper bounds on the Lipschitzness and the smoothness of $f_{\mathcal{C}_{l}}$ respectively that we derived in Lemma 6.6. Namely we have that $G=O(1/\delta)=O(2^{n})$ and $L=O(1/\delta^{2})=O(2^{2n})$.

We prove this last statement in Lemma 6.8, but before that we need the following technical lemma that will be useful to argue about solution on the boundary of $\mathcal{P}(\boldsymbol{A},\boldsymbol{b})$.

If $x_{i}^{\star}\in(\alpha,1-\alpha)$ and $x_{i}^{\star}\in(y_{i}^{\star}-\Delta+\alpha,y_{i}^{\star}+\Delta-\alpha)$ then $\left|\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial x_{i}}\right|\leq\alpha$.

If $x^{\star}_{i}\leq\alpha$ or $x^{\star}_{i}\leq y^{\star}_{i}-\Delta+\alpha$ then $\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial x_{i}}\geq-\alpha$.

If $x^{\star}_{i}\geq 1-\alpha$ or $x^{\star}_{i}\geq y^{\star}_{i}+\Delta-\alpha$ then $\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial x_{i}}\leq\alpha$.

The symmetric statements for $y_{i}^{\star}$ hold. For $i\in\{1,2\}$:

If $y_{i}^{\star}\in(\alpha,1-\alpha)$ and $y_{i}^{\star}\in(x_{i}^{\star}-\Delta+\alpha,x_{i}^{\star}+\Delta-\alpha)$ then $\left|\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial y_{i}}\right|\leq\alpha$.

If $y^{\star}_{i}\leq\alpha$ or $y^{\star}_{i}\leq x^{\star}_{i}-\Delta+\alpha$ then $\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial y_{i}}\leq\alpha$.

If $y^{\star}_{i}\geq 1-\alpha$ or $y^{\star}_{i}\geq x^{\star}_{i}+\Delta-\alpha$ then $\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial y_{i}}\geq-\alpha$.

For this proof it is convenient to define $\hat{\boldsymbol{x}}=\boldsymbol{x}^{\star}-\nabla_{x}f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$, $K(\boldsymbol{y}^{\star})=\{\boldsymbol{x}\mid(\boldsymbol{x},\boldsymbol{y}^{\star})\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b}))\}$, and $\boldsymbol{z}=\Pi_{K(\boldsymbol{y}^{\star})}\hat{\boldsymbol{x}}$.

For the second case, we assume for the sake of contradiction that $x^{\star}_{i}\leq\alpha$ and $\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial x_{i}}<-\alpha$. These imply that $\hat{x}_{i}>x_{i}^{\star}+\alpha$ and that $z_{i}=\min(y_{i}^{\star}+\Delta,\hat{x}_{i},1)>\min(\Delta,\hat{x}_{i},1)\geq\min(3\alpha,x_{i}^{\star}+\alpha)$. As a result, $\left|x_{i}^{\star}-z_{i}\right|=z_{i}-x_{i}^{\star}>\min(3\alpha,\hat{x}_{i}+\alpha)-x_{i}^{\star}$ which is greater than $\alpha$. The latter is a contradiction with the assumption that $(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$ is a solution to the GDAFixedPoint problem. Also if we assume that $x_{i}^{\star}\leq y_{i}^{\star}-\Delta+\alpha$ using the same reasoning we get that $z_{i}=\min(\hat{x}_{i},y_{i}^{\star}+\Delta-\alpha,1)$. From this we can again prove that $\left|x_{i}^{\star}-z_{i}\right|>\alpha$ which contradicts the fact that $(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$ is a solution to GDAFixedPoint.

The third case can be proved using the same arguments as the second case. Then using the corresponding arguments we can prove the corresponding statements for the $y$ variables. ∎

We are now ready to prove that solutions of GDAFixedPoint can only occur in cells that are either panchromatic or violate the boundary conditions of a proper coloring. For convenience in the rest of this section we define $R(\boldsymbol{x})$ to be the cell of the $2^{n}\times 2^{n}$ grid that contains $\boldsymbol{x}$.

for $i,j$ such that $x_{1}\in\left[\frac{i}{2^{n}-1},\frac{i+1}{2^{n}-1}\right]\text{ and }x_{2}\in\left[\frac{j}{2^{n}-1},\frac{j+1}{2^{n}-1}\right]$ if there are multiple $i$, $j$ that satisfy the above condition then we choose $R(\boldsymbol{x})$ to be the cell that corresponds to the $i$, $j$ such that the pair $(i,j)$ it the lexicographically first such that $i$, $j$ satisfy the above condition. We also define the corners $R_{c}(\boldsymbol{x})$ of $R(\boldsymbol{x})$ as

where $R(\boldsymbol{x})=\left[\frac{i}{2^{n}-1},\frac{i+1}{2^{n}-1}\right]\times\left[\frac{j}{2^{n}-1},\frac{j+1}{2^{n}-1}\right]$.

$x_{1}^{\star}\geq 1/(2^{n}-1)$ and, for all $\boldsymbol{v}\in R_{c}(\boldsymbol{x}^{\star})$, it holds that $\mathcal{C}_{l}^{1}(\boldsymbol{v})=-1$.

$x_{1}^{\star}\leq(2^{n}-2)/(2^{n}-1)$ and, for all $\boldsymbol{v}\in R_{c}(\boldsymbol{x}^{\star})$, it holds that $\mathcal{C}_{l}^{1}(\boldsymbol{v})=+1$.

$x_{2}^{\star}\geq 1/(2^{n}-1)$ and, for all $\boldsymbol{v}\in R_{c}(\boldsymbol{x}^{\star})$, it holds that $\mathcal{C}_{l}^{2}(\boldsymbol{v})=-1$.

$x_{2}^{\star}\leq(2^{n}-2)/(2^{n}-1)$ and, for all $\boldsymbol{v}\in R_{c}(\boldsymbol{x}^{\star})$, it holds that $\mathcal{C}_{l}^{2}(\boldsymbol{v})=+1$.

We prove that there is no solution $(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$ of GDAFixedPoint that satisfies the statement 1. and the fact that $(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$ cannot satisfy the other statements follows similarly. It is convenient for us to define $\hat{\boldsymbol{x}}=\boldsymbol{x}^{\star}-\nabla_{x}f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$, $K(\boldsymbol{y}^{\star})=\{\boldsymbol{x}\mid(\boldsymbol{x},\boldsymbol{y}^{\star})\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b}))\}$, $\boldsymbol{z}=\Pi_{K(\boldsymbol{y}^{\star})}\hat{\boldsymbol{x}}$, and $\hat{\boldsymbol{y}}=\boldsymbol{y}^{\star}+\nabla_{y}f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$, $K(\boldsymbol{x}^{\star})=\{\boldsymbol{y}\mid(\boldsymbol{x}^{\star},\boldsymbol{y})\in\mathcal{P}(\boldsymbol{A},\boldsymbol{b}))\}$, $\boldsymbol{w}=\Pi_{K(\boldsymbol{x}^{\star})}\hat{\boldsymbol{y}}$.

For the sake of contradiction we assume that there exists a solution of $(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})$ such that $x_{1}^{\star}\geq 1/(2^{n}-1)$ and for all $\boldsymbol{v}\in R_{c}(\boldsymbol{x}^{\star})$ it holds that $\mathcal{C}_{l}^{1}(\boldsymbol{v})=-1$. Using the fact that the first color of all the corners of $R(\boldsymbol{x}^{\star})$ is $1^{-}$, we will prove that (1) $\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial x_{1}}\geq 1/2$, and (2) $\frac{\partial f_{\mathcal{C}_{l}}(\boldsymbol{x}^{\star},\boldsymbol{y}^{\star})}{\partial y_{1}}=-1$.