Year: 2021

Abstract:
This paper considers minimax optimization minx maxy f(x, y) in the challenging setting where f can be both nonconvex in x and nonconcave in y. Though such optimization problems arise in many machine learning paradigms including training generative adversarial networks (GANs) and adversarially robust models, from a theoretical point of view, two fundamental issues remain: (i) the absence of simple and efficiently computable optimality notions, and (ii) cyclic or diverging behavior of existing algorithms. This paper proposes a new theoretical framework for nonconvex-nonconcave minimax optimization that addresses both of the above issues. The starting point of this paper is the observation that, under a computational budget, the max-player can not fully maximize f(x, ·) since nonconcave maximization is NP-hard in general. So, we propose a new framework, and a corresponding algorithm, for the min-player to play against smooth algorithms deployed by the adversary (i.e., the max-player) instead of against full maximization. Our algorithm is guaranteed to make monotonic progress (thus having no limit cycles or diverging behavior), and to find an appropriate “stationary point” in a polynomial number of iterations. Our framework covers practically relevant settings where the smooth algorithms deployed by the adversary are multi-step stochastic gradient ascent, and its accelerated version. We further present experimental results that confirm our theoretical findings and demonstrate the effectiveness of the proposed approach in practice on simple, conceptual settings.

heading: 1 INTRODUCTION
text: This paper considers minimax optimization minx maxy f(x, y) in the context of two-player zero-sum games, where the min-player (controlling x) tries to minimize objective f assuming a worst-case opponent (controlling y) that acts so as to maximize it. Minimax optimization naturally arises in a variety of important machine learning paradigms, with the most prominent examples being the training of generative adversarial networks (GANs) (Goodfellow et al., 2014) and adversarially robust models (Madry et al., 2018). These applications commonly engage deep neural networks with various techniques such as convolution, recurrent layers, and batch normalization. As a result, the objective function f is highly nonconvex in x and nonconcave in y.
Theoretically, minimax optimization has been extensively studied starting from the seminal work of von Neumann (Neumann, 1928), with many efficient algorithms proposed for solving it (Robinson, 1951; Korpelevich, 1976; Nemirovski, 2004). A majority of these classical results have been focused on convex-concave functions, and heavily rely on the minimax theorem, i.e., minx maxy f(x, y) = maxy minx f(x, y), which no longer holds beyond the convex-concave setting. Recent line of works (Lin et al., 2020a; Nouiehed et al., 2019; Thekumparampil et al., 2019; Lin et al., 2020b; Ostrovskii et al., 2020) address the nonconvex-concave setting where f is nonconvex in x but concave in y by proposing meaningful optimality notions and designing algorithms to find such points. A key property heavily exploited in this setting is that the inner maximization over y given a fixed x can be computed efficiently, which unfortunately does not extend to the nonconvex-nonconcave setting.
Consequently, nonconvex-nonconcave optimization remains challenging, and two of the most fundamental theoretical issues are still unresolved: (i) what is an appropriate notion of optimality that can be computed efficiently? and (ii) can we design algorithms that do not suffer from cycling or diverging behavior? Practitioners often use simple and popular algorithms such as gradient descent
ascent (GDA) and other variants for solving these challenging optimization problems. While these algorithms seem to perform well in terms of producing high quality images in GANs and robust models in adversarial training, they are also highly unstable, particularly in training GANs. Indeed the instability of GDA and other empirically popular methods is not surprising since they are known to not converge even in very simple settings (Daskalakis & Panageas, 2018a; Bailey et al., 2020). This current state of affairs strongly motivates the need to develop a strong theoretical foundation for nonconvex-nonconcave minimax optimization and to design better algorithms for solving them.
This work considers the challenging nonconvex-nonconcave setting. Our framework sprouts from the practical consideration that under a computational budget, the max-player cannot fully maximize f(x, ·) since nonconcave maximization is NP-hard in general. In fact, in both the settings of GAN and adversarial training, in practice, the max-player employs simple gradient based algorithms such as gradient ascent, run for a few steps – on the order of 5 for GAN training and 40 for adversarial training (see, e.g., Arjovsky et al. 2017; Madry et al. 2018) – to estimate argmaxy f(x, y). To capture this aspect, we assume that the max-player has a toolkit of multiple (potentially randomized) algorithmsA1,A2, · · · ,Ak in an attempt to solve the maximization problem given fixed x, and picks the best solution among these algorithms. This motivates us to study the surrogate of the minimax optimization problem as
minx maxi∈[k] f(x,Ai(x)) = minx maxλ∈∆k ∑k i=1 λif(x,Ai(x)), (1)
where ∆k denotes the k-dimensional simplex, and Ai(x) denotes the output of algorithm Ai for a given x. When both the objective function f and the algorithms {Ai}ki=1 are smooth (defined formally in Section 3), we can show that (1) becomes a smooth nonconvex-concave minimax optimization problem, where recent advances can be leveraged in solving such problems.
In particular, given the smooth algorithms deployed by the adversary (i.e. the max-player), this paper proposes two algorithms for solving problems in (1). The first algorithm is based on stochastic gradient descent (SGD), which is guaranteed to find an appropriate notion of “ -approximate stationary point” in O( −4) gradient computations. The second algorithm is based on proximal algorithm, in the case of deterministic adversarial algorithms {Ai}ki=1, this algorithm has an improved gradient complexity O( −3) or Õ(poly(k)/ 2) depending on the choice of subroutine within the algorithm. All our algorithms are guaranteed to make monotonic progress, thus having no limit cycles.
Our second set of results show that, many popular algorithms deployed by the adversary such as multi-step stochastic gradient ascent, and multi-step stochastic Nesterov’s accelerated gradient ascent are in fact smooth. Therefore, our framework readily applies to those settings in practice.
We also present complementing experimental results showing that our theoretical framework and algorithm succeed on simple, conceptual examples of GAN and adversarial training. While more work is needed to scale our approach to large scale benchmarks in GAN and adversarial training, our experimental results serve as a proof of concept demonstration that our algorithm converges to desirable points in practice, at least on simple conceptual examples.

heading: 2 RELATED WORK
text: Due to lack of space, we focus our discussion here on directly related works and present a more detailed overview of related work in Appendix A. Many existing works that propose local optimality notions in nonconvex-nonconcave minimax optimization suffer from nonexistence of such points in general (Ratliff et al., 2013; Ratliff et al., 2016; Jin et al., 2020; Fiez et al., 2020; Zhang et al., 2020a; Farnia & Ozdaglar, 2020). To the best of our knowledge, the only works that propose a relaxed local optimality notion that is shown to exist and be computable in polynomial time is due to Keswani et al. (2020); Mangoubi & Vishnoi (2021). The aforementioned works are similar to this paper in the sense that the min-player faces the max-player with computational restrictions, but are different from ours in terms of the model of the max-player and the algorithms to solve the problem. Concretely, Keswani et al. (2020); Mangoubi & Vishnoi (2021) consider the stationary points of a “smoothed" greedy-max function, which is computed by maximizing along a locally ascending path when fixing the min-player. In contrast, our paper considers the stationary points of a “max" function computed by particular smooth algorithms given their initializations, which is a more faithful surrogate to the objective that the min-player wishes to minimize. Depending on the choice of smooth
algorithms and their initializations, the optimal points of Keswani et al. (2020); Mangoubi & Vishnoi (2021) and the optimal points in our paper can be very different, making them incomparable.

heading: 3 PRELIMINARIES
text: In this section, we present problem formulation and preliminaries. We consider function f satisfying Assumption 1. We denote w = (x, y), and assume f : Rd1 × Rd2 → R is:
(a) B-bounded i.e., |f(w)| ≤ B, (b) G-Lipschitz i.e., |f(w1)− f(w2)| ≤ G‖w1 − w2‖, (c) L-gradient Lipschitz i.e., ‖∇f(w1)−∇f(w2)‖ ≤ L‖w1 − w2‖, (d) ρ-Hessian Lipschitz i.e., ‖∇2f(w1)−∇2f(w2)‖ ≤ ρ‖w1 − w2‖.
where ‖·‖ denotes Euclidean norm for vectors and operator norm for matrices.
We aim to solve minx∈Rd1 maxy∈Rd2 f(x, y). Since maxy∈Rd2 f(x, y) involves non-concave maximization and hence is NP-hard in the worst case, we intend to play against algorithm(s) that y-player uses to compute her strategy. Concretely, given x ∈ Rd1 , we assume that the y-player chooses her (potentially random) strategy ŷz(x) = Ai∗(x)(x, zi∗(x)), where we use shorthand z := (z1, · · · , zk), as i∗(x) = argmaxi∈[k] f(x,Ai(x, zi)), where A1, · · · ,Ak are k deterministic algorithms that take as input x and a random seed zi ∈ R`, where zi are all independent. Note that the framework captures randomized algorithms e.g.,A could be stochastic gradient ascent on f(x, ·), with initialization, minibatching etc. determined by the random seed z. This also incorporates running the same algorithm multiple times, with different seeds and then choosing the best strategy. We now reformulate the minimax objective function to:
minx∈Rd1 g(x) where g(x) := Ez [f(x, ŷz(x))] . (2) For general algorithms Ai, the functions f(x,Ai(x, zi)) need not be continuous even when f satisfies Assumption 1. However, if the algorithms Ai are smooth as defined below, the functions f(x,Ai(x, zi)) behave much more nicely. Definition 1 (Algorithm Smoothness). A randomized algorithm A : Rd1 × R` → Rd2 is:
(a) G-Lipschitz, if ‖A(x1, z)−A(x2, z)‖ ≤ G‖x1 − x2‖ for any z. (b) L-gradient Lipschitz, if ‖DA(x1, z)−DA(x2, z)‖ ≤ L‖x1 − x2‖ for any z.
Here DA(x, z) ∈ Rd1 × Rd2 is the Jacobian of the function A(·, z) for a fixed z. The following lemma tells us that f(x,A(x, z)) behaves nicely whenever A is a Lipschitz and gradient Lipschitz algorithm. For deterministic algorithms, we also use the shortened notation A(x) and DA(x). Lemma 1. Suppose A is G′-Lipschitz and L′-gradient Lipschitz and f satisfies Assumption 1. Then, for a fixed z, function f(·,A(·, z)) is G(1 +G′)-Lipschitz and L(1 +G′)2 +GL′-gradient Lipschitz.
While g(x) defined in (2) is not necessarily gradient Lipschitz, it can be shown to be weakly-convex as defined below. Note that an L-gradient Lipschitz function is L-weakly convex. Definition 2. A function g : Rd1 → R is L-weakly convex if ∀ x, there exists a vector ux satisfying:
g(x′) ≥ g(x) + 〈ux, x′ − x〉 − L2 ‖x ′ − x‖2 ∀ x′. (3)
Any vector ux satisfying this property is called the subgradient of g at x and is denoted by ∇g(x).
An important property of weakly convex function is that the maximum over a finite number of weakly convex function is still a weakly convex function. Lemma 2. Given L-weakly convex functions g1, · · · , gk : Rd → R, the maximum function g(·) := maxi∈[k] gi(·) is also L-weakly convex and the set of subgradients of g(·) at x is given by: ∂g(x) = { ∑ j∈S(x) λj∇gj(x) : λj ≥ 0, ∑ j∈S(x) λj = 1},where S(x) := argmaxi∈[k] gi(x).
Thus, under Assumption 1 and the assumptions Ai are all G′-Lipschitz and L′-gradient Lipschitz, then g(·) defined in (2) is L(1 + G′)2 + GL′-weakly convex. The usual optimality notion for weakly-convex functions is approximate first order stationary points (Davis & Drusvyatskiy, 2018).
Approximate first-order stationary point for weakly convex functions: In order to define approximate stationary points, we also need the notion of Moreau envelope.
Definition 3. The Moreau envelope of a function g : Rd1 → R and parameter λ is:
gλ(x) = minx′∈Rd1 g(x ′) + (2λ) −1 ‖x− x′‖2 . (4)
The following lemma provides useful properties of the Moreau envelope.
Lemma 3. For an L-weakly convex function g : Rd1 → R and λ < 1/L, we have: (a) The minimizer x̂λ(x) = arg minx′∈Rd1 g(x′)+(2λ)−1‖x−x′‖2 is unique and g(x̂λ(x)) ≤
gλ(x) ≤ g(x). Furthermore, arg minx g(x) = arg minx gλ(x). (b) gλ is λ−1(1 + (1− λL)−1)-smooth and thus differentiable, and (c) minu∈∂g(x̂λ(x)) ‖u‖ ≤ λ−1‖x̂λ(x)− x‖ = ‖∇gλ(x)‖.
First order stationary points (FOSP) of a non-smooth nonconvex function are well-defined, i.e., x∗ is a FOSP of a function g(x) if, 0 ∈ ∂f(x∗). However, unlike smooth functions, it is nontrivial to define an approximate FOSP. For example, if we define an ε-FOSP as the point x with minu∈∂g(x) ‖u‖ ≤ ε, where ∂g(x) denotes the subgradients of g at x, there may never exist such a point for sufficiently small ε, unless x is exactly a FOSP. In contrast, by using above properties of the Moreau envelope of a weakly convex function, it’s approximate FOSP can be defined as (Davis & Drusvyatskiy, 2018):
Definition 4. Given an L-weakly convex function g, we say that x∗ is an ε-first order stationary point (ε-FOSP) if, ‖∇g1/2L(x∗)‖ ≤ ε, where g1/2L is the Moreau envelope with parameter 1/2L.
Using Lemma 3, we can show that for any ε-FOSP x∗, there exists x̂ such that ‖x̂− x∗‖ ≤ ε/2L and minu∈∂g(x̂) ‖u‖ ≤ ε. In other words, an ε-FOSP is O(ε) close to a point x̂ which has a subgradient smaller than ε. Other notions of FOSP proposed recently such as in Nouiehed et al. (2019) can be shown to be a strict generalization of the above definition.

heading: 4 MAIN RESULTS
text: In this section, we present our main results. Assuming that the adversary employs Lipschitz and gradient-Lipschitz algorithms (Assumption 2), Section 4.1 shows how to compute (stochastic) subgradients of g(·) (defined in (2)) efficiently. Section 4.2 further shows that stochastic subgradient descent (SGD) on g(·) can find an -FOSP in O ( −4 )
iterations while for the deterministic setting, where the adversary uses only deterministic algorithms, Section 4.3 provides a proximal algorithm that can find an -FOSP faster than SGD. For convenience, we denote gz,i(x) := f(x,Ai(x, zi)) and recall g(x) := Ez [ maxi∈[k] gz,i(x) ] . For deterministic Ai, we drop z and just use gi(x).
4.1 COMPUTING STOCHASTIC SUBGRADIENTS OF g(x)
In this section, we give a characterization of subgradients of g(x) and show how to compute stochastic subgradients efficiently under the following assumption.
Assumption 2. Algorithms Ai in (2) are G′-Lipschitz and L′-gradient Lipschitz as per Definition 1.
Under Assumptions 1 and 2, Lemma 1 tells us that gz,i(x) is a G(1+G′)-Lipschitz and L(1+G′)2 + GL′-gradient Lipschitz function for every i ∈ [k] with
∇gz,i(x) = ∇xf(x,Ai(x, zi)) +DAi(x, zi) · ∇yf(x,Ai(x, zi)), (5)
where we recall that DAi(x, zi) ∈ Rd1×d2 is the Jacobian matrix of Ai(·, zi) : Rd1 → Rd2 at x and ∇xf(x,Ai(x, zi)) denotes the partial derivative of f with respect to the first variable at (x,Ai(x, zi)). While there is no known general recipe for computing DAi(x, zi) for an arbitrary algorithmAi, most algorithms used in practice such as stochastic gradient ascent (SGA), stochastic Nesterov accelerated gradient (SNAG), ADAM, admit efficient ways of computing these derivatives e.g., higher package in PyTorch (Grefenstette et al., 2019). For concreteness, we obtain expression for gradients of SGA and SNAG in Section 5 but the principle behind the derivation holds much more broadly and can be extended to most algorithms used in practice (Grefenstette et al., 2019). In practice, the cost of computing ∇gz,i(x) in (5) is at most twice the cost of evaluating gz,i(x)—it consists a forward pass for evaluating gz,i(x) and a backward pass for evaluating its gradient (Grefenstette et al., 2019).
Algorithm 1: Stochastic subgradient descent (SGD) Input: initial point x0, step size η
1 for s = 0, 1, . . . , S do 2 Sample z1, · · · , zk and compute ∇̂g(xs) according to eq. (6). 3 xs+1 ← xs − η∇̂g(xs). 4 return x̄← xs, where s is uniformly sampled from {0, · · · , S}.
Lemma 2 shows that g(x) := Ez [ maxi∈[k] gz,i(x) ] is a weakly convex function and a stochastic subgradient of g(·) can be computed by generating a random sample of z1, · · · , zk as:
∇̂g(x) = ∑
j∈S(x)
λj∇gz,i(x) for any λ ∈ ∆k, where S(x) := argmax i∈[k] gz,i(x) (6)
Here ∆k is the k-dimensional probability simplex. It can be seen that Ez[∇̂g(x)] ∈ ∂g(x). Furthermore, if all Ai are deterministic algorithms, then the above is indeed a subgradient of g.

heading: 4.2 CONVERGENCE RATE OF SGD
text: The SGD algorithm to solve (2) is given in Algorithm 1. The following theorem shows that Algorithm 1 finds an -FOSP of g(·) in S = O
( −4 )
iterations. Since each iteration of Algorithm 1 requires computing the gradient of gz,i(x) for each i ∈ [k] at a single point xs, this leads to a total of S = O ( −4 ) gradient computations for each gz,i(x).
Theorem 1. Under Assumptions 1 and 2, if S ≥ 16BL̂Ĝ2 −4 and learning rate η = (2B/[L̂Ĝ2(S + 1)])1/2 then output of Algorithm 1 satisfies E[‖∇g1/2L̂(x̄)‖
2] ≤ 2, where L̂ := L(1 +G′)2 +GL′ and Ĝ := G(1 +G′).
Theorem 1 claims that the expected norm squared of the Moreau envelope gradient of the output point satisfies the condition for being an -FOSP. This, together with Markov’s inequality, implies that at least half of x0, · · · , xS are 2 -FOSPs, so that the probability of outputting a 2 -FOSP is at least 0.5. Proposition 1 in Appendix C shows how to use an efficient postprocessing mechanism to output a 2 -FOSP with high probability. Theorem 1 essentially follows from the results of (Davis & Drusvyatskiy, 2018), where the key insight is that, in expectation, the SGD procedure in Algorithm 1 almost monotonically decreases the Moreau envelope evaluated at xs i.e., E [ g1/2L̂(xs) ] is almost monotonically decreasing. This shows that Algorithm 1 makes (almost) monotonic progress in a precise sense and hence does not have limit cycles. In contrast, none of the other existing algorithms for nonconvex-nonconcave minimax optimization enjoy such a guarantee. Note that this claim includes extra-gradient and optimistic gradient methods that have been touted as empirically mitigating cycling behavior; see Appendix F for examples demonstrating nonconvergence of these methods.

heading: 4.3 PROXIMAL ALGORITHM WITH FASTER CONVERGENCE FOR DETERMINISTIC ALGORITHMS
text: While the rate achieved by SGD is the best known for weakly-convex optimization with a stochastic subgradient oracle, faster algorithms exist for functions which can be written as maximum over a finite number of smooth functions with access to exact subgradients of these component functions. These conditions are satisfied when Ai are all deterministic and satisfy Assumption 2. A pseudocode of such a fast proximal algorithm, inspired by Thekumparampil et al. (2019, Algorithm 3), is presented in Algorithm 2. However, in contrast to the results of Thekumparampil et al. (2019), the following theorem provides two alternate ways of implementing Step 3 of Algorithm 2, resulting in two different (and incomparable) convergence rates.
Theorem 2. Under Assumptions 1 and 2, if L̂ := L(1 + G′)2 + GL′ + kG(1 + G′) and S ≥ 200L̂B −2 then Algorithm 2 returns xs satisfying ‖∇g1/2L̂(xs)‖ ≤ . Depending on whether we use (Thekumparampil et al., 2019, Algorithm 1) or cutting plane method (Lee et al., 2015) for
Algorithm 2: Proximal algorithm
Input: initial point x0, target accuracy , smoothness parameter L̂ 1 ̂← 2/(64L̂) 2 for t = 0, 1, . . . , S do 3 Find xs+1 such that
maxi∈[k] gi(xs+1) + L̂‖xs − xs+1‖2 ≤ ( minx maxi∈[k] gi(x) + L̂‖xs − x‖2 ) + ̂/4
4 if maxi∈[k] gi(xs+1) + L̂‖xs − xs+1‖2 ≥ maxi∈[k] gi(xs)− 3̂/4 then 5 return xs
solving Step 3 of Algorithm 2, the total number of gradient computations of each gi is Õ ( L̂2B 3 ) or
O ( L̂B 2 · poly(k) log L̂ ) respectively.
Ignoring the parameters L,G,L′ and G′, the above theorem tells us that Algorithm 2 outputs an -FOSP using O ( k −3 ) or O ( poly(k) −2 log 1 ) gradient queries to each gi depending on whether Thekumparampil et al. (2019, Algorithm 3) or cutting plane method (Lee et al., 2015) was used for implementing Step 3. While the proximal algorithm itself works even when Ai are randomized algorithms, there are no known algorithms that can implement Step (3) with fewer than O ( −2 )
stochastic gradient queries. Hence, this does not improve upon theO ( −4 )
guarantee for Algorithm 1 whenAi are randomized algorithms. The proof of Theorem 2 shows that the iterates xs monotonically decrease the value g(xs), guaranteeing that there are no limit cycles for Algorithm 2 as well.

heading: 5 SMOOTHNESS OF POPULAR ALGORITHMS
text: In this section, we show that two popular algorithms—namely, T -step stochastic gradient ascent (SGA) and T -step stochastic Nesterov’s accelerated gradient ascent (SNAG)—are both Lipschitz and gradient-Lipschitz satisfying Assumption 2 and hence are captured by our results in Section 4. Consider the setting f(x, y) = 1n ∑ j∈[n] fj(x, y). Let z be a random seed that captures the randomness in the initial point as well as minibatch order in SGA and SNAG. We first provide the smoothness results on T -step SGA for different assumptions on the shape of the function f and for T -step SNAG. After giving these results, we make remarks interpreting their significance and the implications.
T -step SGA: For a given x and random seed z, the T -step SGA update is given by: yt+1 = yt + η∇yfσ(t)(x, yt)
where σ : [T ] → [N ] is a sample selection function and η is the stepsize. Observe that with the same randomness z, the initial point does not depend on x i.e., y0(x) = y0(x′), so Dy0 = 0. The following theorems provide the Lipschitz and gradient Lipschitz constants of yT (x) (as generated by T -step SGA) for the general nonconvex-nonconcave setting as well as the settings in which the function f is nonconvex-concave and nonconvex-strongly concave. Theorem 3 (General Case). Suppose for all j ∈ [n], fj satisfies Assumption 1. Then, for any fixed randomness z, T -step SGA is (1 + ηL)T -Lipschitz and 4(ρ/L) · (1 + ηL)2T -gradient Lipschitz. Theorem 4 (Concave Case). Suppose for all j ∈ [n], fj satisfies Assumption 1 and fj(x, ·) is concave for any x. Then, for any fixed randomness z, T -step SGA is ηLT -Lipschitz and (ρ/L) · (1 + ηLT )3- gradient Lipschitz.
Theorem 5 (Strongly-concave Case). Suppose for all j ∈ [n], fj satisfies Assumption 1 and fj(x, ·) is α-strongly concave for any x. Then, for any fixed randomness z, T -step SGA is κ-Lipschitz and 4(ρ/L) · κ3-gradient Lipschitz, where κ = L/α is the condition number.
T -step SNAG: For a given random seed z, the T -step SNAG update is given by: ỹt =yt + (1− θ)(yt − yt−1)
yt+1 =ỹt + η∇y f̂σ(t)(x, ỹt),
where η is the stepsize, θ ∈ [0, 1] is the momentum parameter. The output of the algorithm is given by A(x, z) = yT (x). Furthermore, we have the following guarantee. Theorem 6 (General Case). Suppose for all j ∈ [n], fj satisfies Assumption 1. Then, for any fixed seed z, T -step SNAG is T (1 +ηL/θ)T -Lipschitz and 50(ρ/L) ·T 3(1 +ηL/θ)2T -gradient Lipschitz.
Remarks on the Impact of the Smoothness Results: The Lipschitz and gradient Lipschitz parameters for T -step SGA and T -step SNAG in the setting where f is nonconvex-nonconcave are all exponential in T , the duration of the algorithm. In general, this seems unavoidable in the worst case for the above algorithms and also seems to be the case for most of the other popular algorithms such as ADAM, RMSProp, etc. In contrast, in the nonconvex-concave and nonconvex-strongly concave settings, our results show that the smoothness parameters of T -step SGA are no longer exponential in T . In particular, in the nonconvex-concave the Lipschitz parameter is linear in T and the gradient Lipschitz parameter is polynomial in T while in the nonconvex-strongly concave, the analogous smoothness parameters are no longer dependent on T . We conjecture this is also the case for T -step SNAG, though the proof appears quite tedious and hence, we opted to leave that for future work. For problems of practical importance, however, we believe that the smoothness parameters are rarely exponential in T . Our experimental results confirm this intuition (see Figure 2). Furthermore, note that the function g(x) (2), and its stationary points, vary as one varies T . While in adversarial training, T is essentially determined by the power of adversary against which we wish the model to be robust, in GAN training, T is actually an algorithmic knob that can be tuned to improve the final generator performance. Indeed, larger T does not necessarily lead to better generators and small values of T are of vital interest; as is pointed out in the original paper (Goodfellow et al., 2014), fully optimizing the discriminator can result in overfitting and too strong of a discriminator can limit the ability of the generator to learn. Finally, while we prove the Lipschitz and gradient Lipschitz properties only for SGA and SNAG, we believe that the same techniques could be used to prove similar results for popular algorithms such as ADAM, RMSProp, etc. However, there are other algorithms, particularly those involving projection that are not gradient Lipschitz (see Proposition 3 in Appendix E.5).

heading: 6 EMPIRICAL RESULTS
text: This section presents empirical results evaluating our SGD algorithm (Algorithm 1) for generative adversarial networks (Goodfellow et al., 2014) and adversarial training (Madry et al., 2018). Our results demonstrate that our framework results in stable monotonic improvement during training and converges to desirable solutions in both GAN and adversarial training problems. While optimization through the algorithm of the adversary increases the complexity of each update by a factor of two, our results demonstrate that it also leads to faster convergence. Finally, we show the gradient norms do not grow exponentially in the number of gradient ascent steps T taken by the adversary in practice.
Generative Adversarial Networks. Generative adversarial network formulations can be characterized by the following minimax problem (Nagarajan & Kolter, 2017; Mescheder et al., 2018):
minθ maxω f(θ, ω) = Ex∼pX [`(Dω(x))] + Ez∼pZ [`(−Dω(Gθ(z)))]. (7) In this formulation Gθ : Z → X is the generator network parameterized by θ that maps from the latent space Z to the input space X , Dω : X → R is discriminator network parameterized by ω that maps from the input space X to real-valued logits, and pX and pZ are the distributions over the input and latent spaces. The loss function defines the objective where `(w) = − log(1 + exp(−w)) gives the original “saturating” generative adversarial networks formulation (Goodfellow et al., 2014).
Dirac–GAN. The Dirac-GAN (Mescheder et al., 2018) is a simple and common baseline for evaluating the efficacy of generative adversarial network training methods. In this problem, the generator distribution Gθ(z) = δθ is a Dirac distribution concentrated at θ, the discriminator network Dω(x) = −ωx is linear, and the real data distribution pX = δ0 is a Dirac distribution concentrated at zero. The resulting objective after evaluating (7) with the loss `(w) = − log(1 + exp(−w)) is
minθ maxω f(θ, ω) = `(θω) + `(0) = − log(1 + e−θω)− log(2).
To mimic the real data distribution, the generator parameter θ should converge to θ∗ = 0. Notably, simultaneous and alternating gradient descent-ascent are known to cycle and fail to converge on this problem (see Figure 1). We consider an instantiation of our framework where the discriminator
samples an initialization uniformly between [−0.1, 0.1] and performs T = 10 steps of gradient ascent between each generator update. The learning rates for both the generator and the discriminator are η = 0.01. We present the results in Figure 1. Notably, the generator parameter monotonically converges to the optimal θ∗ = 0 and matches the real data distribution using our training method. We also show the performance when the generator descends using partial gradient∇θf(x,A(θ)) instead of the total gradient ∇f(θ,A(θ)) in Algorithm 1. This method is able to converge to the optimal generator distribution but at a slower rate. Together, this example highlights that our method fixes the usual cycling problem by reinitializing the discriminator and also that optimizing through the discriminator algorithm is key to fast convergence. Additional results are given in Appendix G.
Mixture of Gaussians. We now demonstrate that the insights we developed from the Dirac-GAN (stability and monotonic improvement) carry over to the more complex problem of learning a 2- dimensional mixture of Gaussians. This is a common example and a number of papers (see, e.g., Metz et al. 2017; Mescheder et al. 2017; Balduzzi et al. 2018) show that standard training methods using simultaneous or alternating gradient descent-ascent can fail. The setup for the problem is as follows. The real data distribution consists of 2-dimensional Gaussian distributions with means given by µ = [sin(φ), cos(φ)] for φ ∈ {kπ/4}7k=0 and each with covariance σ2I where σ2 = 0.05. For training, the real data x ∈ R2 is drawn at random from the set of Gaussian distributions and the latent data z ∈ R16 is drawn from a standard normal distribution with batch sizes of 512. The network for the generator and discriminator contain two and one hidden layers respectively, each of which contain 32 neurons and ReLU activation functions. We consider the objective from (7) with `(w) = − log(1 + exp(−w)) which corresponds to the “saturating” generative adversarial networks formulation (Goodfellow et al., 2014). This objective is known to be difficult to train since with typical training methods the generator gradients saturate early in training.
We show results using our framework in Figure 3 where the discriminator performs T = 15 steps of gradient ascent and the initialization between each generator step is obtained by the default network initialization in Pytorch. The generator and discriminator learning rates are both fixed to be η = 0.5. We see that our method has stable improvement during the course of training and recovers close to the real data distribution. We demonstrate in Appendix G that this result is robust by presenting the
final output of 10 runs of the procedure. Notably, the training algorithm recovers all the modes of the distribution in each run. We also show results using Adam for the discriminator in Appendix G.
Adversarial Training. Given a data distribution D over pairs of examples x ∈ Rd and labels y ∈ [k], parameters θ of a neural network, a set S ⊂ Rd of allowable adversarial perturbations, and a loss function `(·, ·, ·) dependent on the network parameters and the data, adversarial training amounts to considering a minmax optimization problem of the form minθ E(x,y)∼D[maxδ∈S `(θ, x+ δ, y)]. In practice (Madry et al., 2018), the inner maximization problem maxδ∈S `(θ, x+ δ, y) is solved using projected gradient ascent. However, as described in Section 5, this is not a smooth algorithm and does not fit our framework. So, we use gradient ascent, without projection, for the inner maximization.
We run an adversarial training experiment with the MNIST dataset, a convolutional neural network, and the cross entropy loss function. We compare Algorithm 1 with usual adversarial training (Madry et al., 2018) which descends ∇θf(θ,A(θ)) instead of ∇f(θ,A(θ)), and a baseline of standard training without adversarial training. For each algorithm, we train for 100 passes over the training set using a batch size of 50. The minimization procedure has a fixed learning rate of η1 = 0.0001 and the maximization procedure runs for T = 10 steps with a fixed learning rate of η2 = 4. We evaluate the test classification accuracy during the course of training against gradient ascent or Adam optimization adversarial attacks. The results are presented in Figure 4 where the mean accuracies are reported over 5 runs and the shaded regions show one standard deviation around the means. We observe that the adversarial training procedure gives a significant boost in robustness compared to standard training. Moreover, consistent with the previous experiments, our algorithm which uses total gradient outperforms standard adversarial training which uses only partial gradient. We present results against more attacks in Appendix G. As suggested in Section 5, we also find that in practice, the gradient norms ‖∇f(θ,A(θ))‖ do not grow exponentially in the number of gradient ascent steps T in the adversary algorithm A (see Figure 2). For further details and additional results see Appendix G.

heading: 7 CONCLUSION
text: Motivated by the facts that (i) nonconcave maximization is NP-hard in the worst case and (ii) in practice, simple gradient based algorithms are used for maximization, this paper presents a new framework for solving nonconvex-nonconcave minimax optimization problems. Assuming that the min player has knowledge of the smooth algorithms being used by max player, we propose new efficient algorithms and verify that these algorithms find desirable solutions in practice on smallscale generative adversarial network and adversarial training problems. Furthermore, the framework proposed in this paper extends naturally to two player non-zero sum games as well. There are several interesting directions for future work (i) scaling our algorithm to large scale, state of the art GAN benchmarks and understanding the quality of solutions found by our algorithm in those settings, (ii) developing new techniques to deal with nonsmooth algorithms such as projected gradient ascent.

heading: A DETAILED RELATED WORK
text: Nonconvex-Nonconcave Zero-Sum Games. The existing work on nonconvex-nonconcave zerosum games has generally focused on (1) defining and characterizing local equilibrium solution concepts and (2) analyzing the local stability and convergence behavior of gradient-based learning algorithms around fixed points of the dynamics. The concentration on local analysis stems from the inherent challenges that arise in nonconvex-nonconcave zero-sum games from both a dynamical systems perspective and a computational perspective. In particular, it is know that broad classes of gradient-based learning dynamics can admit limit cycles and other non-trivial periodic orbits that are antithetical to any type of global convergence guarantee in this class of games (Hsieh et al., 2020; Letcher, 2021). Moreover, on constrained domains, it has been shown that finding even a local equilibrium is computationally intractable (Daskalakis et al., 2021).
A number of local equilibrium notions for nonconvex-nonconcave zero-sum games now exist with characterizations in terms of gradient-based conditions relevant to gradient-based learning. This includes the local Nash (Ratliff et al., 2013; Ratliff et al., 2016) and local minmax (Stackelberg) (Jin et al., 2020; Fiez et al., 2020) equilibrium concepts, which both amount to local refinements and characterizations of historically standard game-theoretic equilibrium notions. In terms of provable guarantees, algorithms incorporating higher-order gradient information have been proposed and analyzed that guarantee local convergence to only local Nash equilibria (Adolphs et al., 2019; Mazumdar et al., 2019) or local convergence to only local minmax equilibria (Wang et al., 2020; Zhang et al., 2020b; Fiez et al., 2020) in nonconvex-nonconcave zero-sum games. Beyond the local Nash and minmax equilibrium, notions including the proximal equilibrium concept (Farnia & Ozdaglar, 2020), which is a class between the set of local Nash and local minmax equilibria, and the local robust equilibrium concept (Zhang et al., 2020a), which includes both local minmax and local maxmin equilibria, have been proposed and studied. It is worth noting that a shortcoming of each of the local equilibrium notions is that may fail to exist on unconstrained domains.
Significant attention has been given to the local stability and convergence of simultaneous gradient descent-ascent in nonconvex-nonconcave zero-sum games. This stems from the fact that it is the natural analogue of learning dynamics for zero-sum game optimization to gradient descent for function optimization. Moreover, simultaneous gradient descent-ascent is know to often perform reasonably well empirically and is ubiquitous in a number of applications such as in training generative adversarial networks and adversarial learning. However, it has been shown that while local Nash are guaranteed to be stable equilibria of simultaneous gradient descent-ascent (Mazumdar et al., 2020; Daskalakis & Panageas, 2018b; Jin et al., 2020), local minmax may not be unless there is sufficient timescale separation between the minimizing and maximizing players (Jin et al., 2020; Fiez & Ratliff, 2021). Specific to generative adversarial networks, it has been shown that simultaneous gradient descent-ascent locally converges to local equilibria under certain assumptions on the generator network and the data distribution (Nagarajan & Kolter, 2017; Mescheder et al., 2018). Later in this section we discuss in further detail learning dynamics studied previously in games which bear resemblance to that which we consider in this paper depending on the model of the maximizing player.
The challenges of nonconvex-nonconcave zero-sum games we have highlighted limit the types of provable guarantees that can be obtained and consequently motivate tractable relaxations including to nonconvex-concave zero-sum games and the general framework we formulate in this work. Before moving on, we mention that from a related perspective, a line of recent work (Keswani et al., 2020; Mangoubi & Vishnoi, 2021) in nonconvex-nonconcave zero-sum games proposes relaxed equilibrium notions that are shown to be computable in polynomial time and are guaranteed to exist. At a high level, the equilibria correspond to a joint strategy at which the maximizing player is at an approximate local maximum of the cost function and the minimizing player is at an approximate local minimum of a smoothed and relaxed best-response function of the maximizing player. The aforementioned works are similar to this paper in the sense that the minimizing player faces a maximizing player with computational restrictions, but diverge in terms of the model of the maximizing player and the algorithms for solving the problem.
Nonconvex-Concave Zero-Sum Games. The past few years has witnessed a significant amount of work on gradient-based dynamics in nonconvex-concave zero-sum games. The focus of existing work on nonconvex-concave zero-sum games has key distinctions from that in nonconvex-nonconcave
zero-sum games. Generally, the work on nonconvex-concave zero-sum games has analyzed dynamics on constrained domains, where typically the strategy space of the maximizing player is constrained to a closed convex set and occasionally the minimizing player also faces a constraint. In contrast, nonconvex-nonconcave zero-sum games have generally been analyzed on unconstrained domains. Moreover, instead of focusing on computing notions of game-theoretic equilibrium as is typical in nonconvex-nonconcave zero-sum games, the body of work on nonconvex-concave zero-sum games has focused on achieving stationarity of the game cost function f(·, ·) or the best-response function Φ(·) = maxy f(·, y). The structure present in nonconvex-concave zero-sum games has been shown to simplify the problem compared to nonconvex-nonconcave zero-sum games so that global finite-time convergence guarantees are achievable. Thus, work in this direction has focused on improving the rates of convergence in terms of the gradient complexity to find –approximate stationary points of f(·, ·) or Φ(·), both with deterministic and stochastic gradients. Guarantees on the former notion of stationarity can be translated to guarantees on the latter notion of stationarity with extra computational cost (Lin et al., 2020a).
For the the class of nonconvex-strongly-concave zero-sum games, a series of works design algorithms that are shown to obtain –approximate stationary points of the functions f(·, ·) or Φ(·) with a gradient complexity of Õ( −2) in terms of in the deterministic setting (Jin et al., 2020; Rafique et al., 2021; Lu et al., 2020; Lin et al., 2020a;b). In the deterministic nonconvex-strongly concave problem, the notions of stationarity are equivalent in terms of the dependence on up to a logarithmic dependence (Lin et al., 2020a). Lower bounds for this problem have also been established (Zhang et al., 2021; Li et al., 2021). In the stochastic nonconvex-strongly-concave problem, existing work has developed algorithms that are shown to obtain –approximate stationary points of the function Φ(·) in gradient complexities of Õ( −4) (Rafique et al., 2021; Jin et al., 2020; Lin et al., 2020a) and Õ( −3) (Luo et al., 2020) in terms of dependence.
In the deterministic nonconvex-concave problem, a number of algorithms with provable guarantees to –approximate stationary points of the function f(·, ·) have been shown with gradient complexities of Õ( −4) (Lu et al., 2020), Õ( −3.5) (Nouiehed et al., 2019), and Õ( −2.5) (Ostrovskii et al., 2020; Lin et al., 2020b). Similarly, in this class of problems, there exist results on algorithms that guarantee convergence to an –approximate stationary points of the function Φ(·) with gradient complexities Õ( −6) (Rafique et al., 2021; Jin et al., 2020; Lin et al., 2020a) and Õ( −3) (Thekumparampil et al., 2019; Zhao, 2020; Kong & Monteiro, 2019; Lin et al., 2020b). Finally, existing results in the stochastic setting for achieving an –approximate stationary point of Φ(·) show gradient complexities of Õ( −6) (Rafique et al., 2021) and Õ( −8) (Lin et al., 2020a).
In this work, we build on the developments for nonconvex-concave problems to obtain our results.
Gradient-Based Learning with Opponent Modeling. A number of gradient-based learning schemes have been derived is various classes of games based on the following idea: if a player knows how the opponents in a game are optimizing their cost functions, then it is natural to account for this behavior in the players own optimization procedure. The simultaneous gradient descent learning dynamics can be viewed as the simplest instantiation of this perspective, where each player is optimizing their own cost function assuming that all other players in the game will remain fixed. In general, the more sophisticated existing learning dynamics based on opponent modeling assume the opponents are doing gradient descent on their cost function and this prediction is incorporated into the objective being optimized in place of the current strategies of opponents. A key conceptual distinction between this approach and our work is that in existing opponent modeling methods the dynamics of the players are always updated simultaneously whereas the procedure we consider is sequential in nature with the opponent initializing again at each interaction. Moreover, the types of guarantees we prove are distinct compared to existing work in this realm.
In this modern literature, gradient-based learning with opponent modeling dates back to the work of Zhang & Lesser (2010). They study simple two-player, two-action, general-sum matrix games, and analyze a set of learning dynamics called iterated descent descent with policy prediction (IGAPP) and show asymptotic convergence to a Nash equilibrium. In this set of learning dynamics, each player assumes the other player is doing gradient descent and this prediction is used in the objective. In particular, each player i has a choice variable xi and a cost function fi(xi, x−i) that after
incorporating the prediction becomes fi(xit, x −i t − γ∇−if−i(xit, x−it )). To optimize the objective, each player takes a first-order Taylor expansion of their cost function to give the augmented objective
fi(x i t, x −i t − γ∇−if−i(xit, x−it )) ≈ fi(xit, x−it )− γ∇−ifi(xti, xt−i)>∇−if−i(xit, x−it ).
Each player in the game simultaneously follows the gradient of their augmented objective which is given by ∇ifi(xit, x−it )− γ∇−i,ifi(xti, xt−i)>∇−if−i(xit, x−it ). This gradient computation is derived based on the fact that the assumed update of the other player ∇−if−i(xit, x−it ) does not depend on the optimization variable. Similar ideas have recently been revisited in more general nonconvex multiplayer games (Foerster et al., 2018; Letcher et al., 2019). In learning with opponent learning awareness (LOLA) (Foerster et al., 2018), players again assume the other players are doing gradient descent and take their objective to be fi(xit, x −i t − γ∇−if−i(xit, x−it )). To derive the learning rule, an augmented objective is again formed by computing a first-order Taylor expansion, but now the term ∇−if−i(xit, x−it ) in the augmented objective is treated as dependent on the optimization variable so that the gradient of the augmented objective is given by
∇ifi(xit, x−it )− γ∇−i,ifi(xti, xt−i)>∇−if−i(xit, x−it )− γ∇−i,if−i(xit, x−it )>∇−ifi(xti, xt−i).
Finally, to arrive at the final gradient update for each player, the middle term in the equation above is removed and each player takes steps along the gradient update
∇ifi(xit, x−it )− γ∇−i,if−i(xit, x−it )>∇−ifi(xti, xt−i).
While no convergence results are given for LOLA, a follow-up work shows local convergence guarantees to stable fixed points for IGA-PP and learning dynamics called stable opponent shaping (SOS) that interpolate between IGA-PP and LOLA (Letcher et al., 2019). A related work derives learning dynamic based on the idea that the opponent selects a best-response to the chosen strategy (Fiez et al., 2020). The resulting learning dynamics can be viewed as LOLA with the opponent selecting a Newton learning rate. For nonconvex-nonconcave zero-sum games, local convergence guarantees to only local Stackelberg equilibrium are given in for this set of learning dynamics (Fiez et al., 2020). It is worth remarking that gradient-based learning with opponent modeling is historically rooted in the general framework of consistent conjectural variations (see, e.g., Başar & Olsder 1998, Chapter 4.6), a concept that is now being explored again and is closely related to the previously mentioned learning dynamics (Chasnov et al., 2020).
Perhaps the closest work on gradient-based learning with opponent modeling to this paper is that of unrolled generative adversarial networks (Metz et al., 2017). In unrolled generative adversarial networks, the generator simulates the discriminator doing a fixed number of gradient steps from the current parameter configurations of the generator and discriminator. The resulting discriminator parameters are then used in place of the current discriminator parameters in the generator objective. The generator then updates following the gradient of this objective, optimizing through the rolled out discriminator update by computing the total derivative. Simultaneously with the generator update, the discriminator updates its parameters by performing a gradient step on its objective. In our framework, for generative adversarial networks when the discriminator is modeled as performing T -steps of gradient ascent, the procedure we propose is similar but an important difference is that when the generator simulates the discriminator unrolling procedure the discriminator parameters are initialized from scratch and there is no explicit discriminator being trained simultaneously with the generator.
Extragradient methods: Starting from the seminal work of Korpelevich (1976), extragradient methods have been studied extensively for solving minimax optimization problems. While such methods have been shown to obtain faster convergence rates (Nemirovski, 2004) and final iterate convergence (Daskalakis et al., 2018; Lei et al., 2021) for convex-concave minimax optimization, there is no result showing that it converges in general nonconvex-nonconcave settings. In fact, in Appendix F we present simple examples demonstrating that the extragradient method as well as another variant called optimistic gradient descent ascent, do not converge for general nonconvexnonconcave minimax optimization.
Games with computationally bounded adversaries: There are also a few works in the game theory literature which consider resource/computationally bounded agents. For example Freund et al. (1995)
considers repeated games between resource bounded agents, (Sandhlom & Lesser, 1997) considers coalition formation between resource bounded agents in cooperative games and Halpern et al. (2014) shows that resource constraints in otherwise rational players might lead to some commonly observed human behaviors while making decisions. However, the settings, models of limited computation and the focus of results considered in all of these prior works are distinct from those of this paper.
Stability of algorithms in numerical analysis: To our knowledge such results on the smoothness of the classes of algorithms we study—i.e., gradient-based updates such as SGA and SNAG—with respect to problem parameters (e.g., in this case, x) have not been shown in the machine learning and optimization literature. This being said, in the study of dynamical systems—more specifically differential equations—the concept of continuity (and Lipschitzness) with respect to parameters and initial data has been studied using a variational approach wherein the continuity of the solution of the differential equation is shown to be continuous with respect to variations in the parameters or initial data by appealing to nonlinear variation of parameters results such as the Bellman-Grownwall inequality or Alekseev’s theorem (see classical references on differential equations such as Coddington & Levinson (1955, Chapter 2) or Hartman (2002, Chapter IV.2)).
In numerical methods, such results on the “smoothness” or continuity of the differential equation with respect to initial data or problem parameters are used to understand stability of particular numerical methods (see, e.g., Atkinson et al. 2011, Chapter 1.2). In particular, a initial value problem is only considered well-posed if there is continuous dependence on initial data. For instance, the simple scalar differential equation
ẏ(t) = −y(t) + 1, 0 ≤ t ≤ T, y(0) = 1
has solution y(t) ≡ 1, yet the perturbed problem,
ẏ (t) = −y (t) + 1, 0 ≤ t ≤ T, y (0) = 1 + ,
has solution y (t) = 1 + e−t so that
|y(t)− y (t)| ≤ | |, 0 ≤ t ≤ T.
If the maximum error ‖y −y‖∞ is (much) larger than then the initial value problem is ill-conditioned and any typical attempt to numerically solve such a problem will lead to large errors in the computed solution. In short, the stability properties of a numerical method (i.e., discretization of the differential equation) are fundamentally connected to the continuity (smoothness) with respect to initial data.
Observe that methods such as gradient ascent can be viewed as a discretization of an differential equation: ẏ(t) = ∇yf(x, y(t)) −→ yk+1 = yk + η∇yf(x, yk). As such, the techniques for showing continuity of the solution of a differential equation with respect to initial data or other problem parameters (e.g., in this case x) can be adopted to show smoothness of the T -step solution of the discretized update. Our approach to showing smoothness, on the other hand, leverages the recursive nature of the discrete time updates defining the classes of algorithms we study. This approach simplifies the analysis by directly going after the smoothness parameters using the update versus solving the difference (or differential) equation for yT (x) and then finding the smoothness parameters which is the method typically used in numerical analysis of differential equations. An interesting direction of future research is to more formally connect the stability analysis from numerical analysis of differential equations to robustness of adversarial learning to initial data and even variations in problem parameters.

heading: B PROOF OF RESULTS IN SECTION 3
text: Proof of Lemma 1. For any fixed z, we note that A(·, z) is a deterministic algorithm. Consequently, it suffices to prove the lemma for a deterministic algorithm A(·). By chain rule, the derivative of f(x,A(x)) is given by:
∇f(x,A(x)) = ∇xf(x,A(x)) +DA(x) · ∇yf(x,A(x)), (8)
where DA(x) ∈ Rd1×d2 is the derivative of A(·) : Rd1 → Rd2 at x and ∇xf(x,A(x)) and ∇yf(x,A(x)) denote the partial derivatives of f with respect to the first and second variables
respectively at (x,A(x)). An easy computation shows that
‖∇f(x,A(x))‖ ≤ ‖∇xf(x,A(x))‖+ ‖DA(x)‖ · ‖∇yf(x,A(x))‖ ≤ G+G′ ·G = (1 +G′)G.
This shows that f(x,A(x)) is (1 +G′)G-Lipschitz. Similarly, we have:
‖∇f(x1,A(x1))−∇f(x2,A(x2))‖ ≤ ‖∇xf(x1,A(x1))−∇xf(x2,A(x2))‖+ ‖DA(x1)∇yf(x1,A(x1))−DA(x2)∇yf(x2,A(x2))‖.
For the first term, we have:
‖∇xf(x1,A(x1))−∇xf(x2,A(x2))‖ ≤ ‖∇xf(x1,A(x1))−∇xf(x2,A(x1))‖+ ‖∇xf(x2,A(x1))−∇xf(x2,A(x2))‖ ≤ L (‖x1 − x2‖+ ‖A(x1)−A(x2)‖) ≤ L (1 +G′) ‖x1 − x2‖.
Similarly, for the second term we have:
‖DA(x1)∇yf(x1,A(x1))−DA(x2)∇yf(x2,A(x2))‖ ≤ ‖DA(x1)‖‖∇yf(x1,A(x1))−∇yf(x2,A(x2))‖+ ‖∇yf(x2,A(x2))‖‖DA(x2)−DA(x1)‖ ≤ (LG′(1 +G′) +GL′) ‖x1 − x2‖.
This proves the lemma. Proof of Lemma 2. Given any x and y, and any λ such that λj ≥ 0 and ∑ j∈S(x) λj = 1, we have:
g(y) = max j∈[k]
gj(y) ≥ ∑
j∈S(x)
λjgj(y) ≥ ∑
j∈S(x)
λj ( gj(x) + 〈∇gj(x), y − x〉 − 1
2L ‖x− y‖2 ) = g(x) + 〈
∑ j∈S(x) λj∇gj(x), y − x〉 − 1 2L ‖x− y‖2,
proving the lemma.
Proof of Lemma 3. We re-write fλ(x) as minimum value of a ( 1λ − L)-strong convex function φλ,x, as g is L-weakly convex (Definition 2) and 12λ‖x− x ′‖2 is differentiable and 1λ -strongly convex,
gλ(x) = min x′∈Rd1
[ φλ,x(x ′) = g(x′) + 1
2λ ‖x− x′‖2
] . (9)
Then first part of (a) follows trivially by the strong convexity. For the second part notice the following,
min x gλ(x) = min x min x′
g(x′) + 1
2λ ‖x− x′‖2
= min x′ min x g(x′) +
1
2λ ‖x− x′‖2
= min x′
g(x′)
Furthermore, we will show that arg minx gλ(x) = arg minx g(x). Consider x∗ ∈ argminx g(x). We have that for any x,
gλ(x) = min x′
g(x′) + 1
2λ ‖x− x′‖2 ≥ g(x∗) ≥ gλ(x∗).
This shows that x∗ ∈ argminx gλ(x) and hence argminx g(x) ⊆ argminx gλ(x). Similarly, for any x∗ ∈ argminx gλ(x), we have:
gλ(x ∗) = g(x̂λ(x ∗)) + 1
2λ ‖x̂λ(x∗)− x∗‖2 ≥ g(x̂λ(x∗)) ≥ gλ(x̂λ(x∗)).
Algorithm 3: Estimating Moreau envelope’s gradient for postprocessing Input: point x, stochastic subgradient oracle for function g, error , failure probability δ
1 Find x̃ such that g(x̃) + L‖x− x̃‖2 ≤ ( minx′ g(x ′) + L‖x− x′‖2 ) + 2
4L using (Harvey et al., 2019, Algorithm 1).
2 return 2L(x− x̃).
Since x∗ ∈ argminx gλ(x), the above inequality is infact an equality and hence x̂λ(x∗) = x∗. So, gλ(x
∗) = g(x∗) and hence x∗ ∈ argminx g(x) implying that argminx gλ(x) ⊆ argminx g(x). Thus arg minx gλ(x) = arg minx g(x). For (b) we can re-write the Moreau envelope gλ as,
gλ(x) = min x′
g(x′) + 1
2λ ‖x− x′‖2
= ‖x‖2 2λ − 1 λ max x′ (xTx′ − λg(x′)− ‖x ′‖2 2 )
= ‖x‖2 2λ − 1 λ
( λg(·) + ‖ · ‖ 2
2
)∗ (x) (10)
where (·)∗ is the Fenchel conjugation operator. Since L < 1/λ, using L-weak convexity of g, it is easy to see that λg(x′) + ‖x
′‖2 2 is (1−λL)-strongly convex, therefore its Fenchel conjugate would be
1 (1−λL) -smooth (Kakade et al., 2009, Theorem 6). This, along with 1 λ -smoothness of first quadratic term implies that gλ(x) is ( 1 λ + 1 λ(1−λL) ) -smooth, and thus differentiable.
For (c) we proceed as follows. Since x̂λ(x) = argminx′ φλ,x(x ′), by first order KKT optimality conditions, we have that x− x̂λ(x) ∈ λ∂g(x). (11) Further, from proof of part (a) we have that φλ,x(x′) (1 − λL)-strongly-convex in x′ and it is quadratic (and thus convex) in x. Danskin’s theorem (Bertsekas, 2009, Section 6.11) thus implies that for gλ(x) = minx′∈Rd1 φλ,x(x′), we have that ∇gλ(x) = (x − x̂λ(x))/λ. Letting ûλ(x) := λ−1(x− x̂λ(x)) ∈ ∂g(x), we have that:
min u∈∂g(x̂λ(x))
‖u‖ ≤ ‖ûλ(x)‖ = λ−1‖x− x̂λ(x)‖ = ‖∇gλ(x)‖.

heading: C PROOFS OF RESULTS IN SECTION 4.2
text: In order to prove convergence of this algorithm, we first recall the following result from (Davis & Drusvyatskiy, 2018). Theorem 7 (Corollary 2.2 from (Davis & Drusvyatskiy, 2018)). Suppose g(·) is L-weakly convex, and Ez1,··· ,zk [ ‖∇̂g(x)‖2 ] ≤ G2. Then, the output x̄ of Algorithm 1 with stepsize η = γ√
S+1
satisfies:
E [ ‖∇g 1
2L (x̄)‖2
] ≤ 2 ·
( g 1
2L (x0)−minx g(x)
) + LG2γ2
γ √ S + 1
.
Proof of Theorem 1. Lemmas 1 and 2 tell us that g(x) is L̂-weakly convex and for any choice of z, the stochastic subgradient ∇̂g(x) is bounded in norm by Ĝ. Consequently, Theorem 7 with the stated choice of S proves Theorem 1.
Proposition 1. Given a point x, an L-weakly convex function g and a G-norm bounded and a stochastic subgradient oracle to g (i.e., given any point x′, which returns a stochastic vector u such that E[u] ∈ ∂g(x′) and ‖u‖ ≤ G), with probability at least 1 − δ, Algorithm 3 returns a vector u satisfying ‖u−∇gλ(x)‖ ≤ with at most O ( G2 log 1δ 2 ) queries to the stochastic subgradient oracle
of g.
Proof of Proposition 1. Let Φ 1 2L (x′, x) := g(x′) + L‖x− x′‖2. Recall the notation of Lemma 3 x̂ 1
2L (x) := argminx′ Φ 12L (x ′, x) and gλ(x) = minx′ Φ 1 2L (x′, x). The proof of Lemma 3 tells us that
∇g 1 2L
(x) = x−x̂ 1 2L (x)
λ and also that ‖x̂ 12L (x)− x‖ ≤ G 2L . Since Φ 12L (·, x) is a L-strongly convex and G Lipschitz function in the domain { x′ : ‖x̂ 1
2L (x)− x‖ ≤ G2L
} , (Harvey et al., 2019, Theorem
3.1) tells us that we can use SGD with O ( G2 log 1δ L̃ ) stochastic gradient oracle queries to implement Step 1 of Algorithm 3 with success probability at least 1 − δ, where ̃ := 2
4L . Simplifying this expression gives us a stochastic gradient oracle complexity of O ( G2 log 1δ
2
) .

heading: D PROOFS OF RESULTS IN SECTION 4.3
text: Proof of Theorem 2. Letting h(x, λ) := ∑ i∈[k] λigi(x), we note that ‖∇xxh(x, λ)‖ =
‖ ∑ i∈[k] λi∇2gi(x)‖ ≤ L(1 +G′)2 +GL′, where we used Lemma 1 and the fact that ∑ i |λi| ≤ 1.
On the other hand, ‖∇xλh(x, λ) = ‖ ∑ i∈[k]∇gi(x)‖‖ ≤ kG(1 + G′), where we again used
Lemma 1. Since ∇λλh(x, λ) = 0, we can conclude that h is an L̂-gradient Lipschitz function with L̂ := L(1 + G′)2 + GL′ + kG(1 + G′). Consequently, g(x) = maxλ∈S h(x, λ), where S := { λ ∈ Rk : λi ≥ 0, ∑ i∈[k] λi = 1 } , is L̂-weakly convex and the Moreau envelope g 1
2L̂ is well
defined.
Denote ĝ(x, xs) := maxi∈[k] gi(x) + L̂‖x− xs‖2. We now divide the analysis of each of iteration of Algorithm 2 into two cases.
Case I, ĝ(xs+1, xs) ≤ maxi∈[k] gi(xs) − 3̂/4: Since maxi∈[k] gi(xs+1) ≤ ĝ(xs+1, xs) ≤ maxi∈[k] gi(xs) − 3̂/4, we see that in this case g(xs) decreases monotonically by at least 3̂/4 in each iteration. Since by Assumption 1, g is bounded by B in magnitude, and the termination condition in Step 4 guarantees monotonic decrease in every iteration, there can only be at most 2B/(3̂/4) = 8B/̂ such iterations in Case I.
Case II, ĝ(xs+1, xs) ≥ maxi∈[k] gi(xs) − 3̂/4: In this case, we claim that xs is an -FOSP of g = maxi∈[k] gi(x). To see this, we first note that
g(xs)− 3̂/4 ≤ ĝ(xs+1, xs) ≤ (min x g(x) + L̂‖x− xs‖2) + ̂/4 =⇒ g(xs) < min x ĝ(x;xs) + ̂.
(12)
Let x∗s := arg minx ĝ(x;xk). Since g is L̂-gradient Lipschitz, we note that ĝ(·;xs) is L̂-strongly convex. We now use this to prove that xs is close to x∗s:
ĝ(x ∗ s ;xs) +
L̂ 2 ‖xs − x∗s‖2 ≤ ĝ(xs;xs) = f(xs) (a) < ĝ(x ∗ k;xs) + ̂ =⇒ ‖xs − x∗s‖ <
√ 2̂
L̂ (13) where (a) uses (12). Now consider any x̂, such that 4 √ ̂/L ≤ ‖x̂− xs‖. Then,
g(x̂) + L‖x̂− xs‖2 = max i∈[k]
gi(x̂) + L‖x̂− xs‖2 = ĝ(x̂;xs) (a) = ĝ(x ∗ s;xs) +
L 2 ‖x̂− x∗s‖2
(b) ≥ f(xs)− ̂+ L̂
2 (‖x̂− xs‖ − ‖xs − x∗s‖)2
(c) ≥ f(xs) + ̂, (14)
where (a) uses uses L̂-strong convexity of ĝ(·;xs) at its minimizer x∗s , (b) uses (12), and (b) and (c) use triangle inequality, (13) and 4 √ ̂/L̂ ≤ ‖x̂− xs‖.
Now consider the Moreau envelope, g 1 2L̂ (x) = minx′ φ 1 2L̂ ,x(x ′) where φ 1 2L̂ ,x(x ′) = g(x′) + L‖x−
x′‖2. Then, we can see that φ 1 2L̂ ,xs(x
′) achieves its minimum in the ball {x′ | ‖x′ − xs‖ ≤ 4 √ ̂/L̂}
by (14) and Lemma 3(a). Then, with Lemma 3(b,c) and ̂ = ε 2
64 L̂ , we get that,
‖∇g 1 2L̂ (xs)‖ ≤ (2L̂)‖xs − x̂ 1 2L̂
(xs)‖ = 8 √ L̂̂ = ε, (15)
i.e., xs is an ε-FOSP of g.
By combining the above two cases, we establish that 8B3̂ “outer” iterations ensure convergence to a ε-FOSP.
We now compute the gradient call complexity of each of these “outer" iterations, where we have two options for implementing Step 3 of Algorithm 2. Note that this step corresponds to solving minx maxλ∈S h(x, λ) up to an accuracy of ̂/4.
Option I, (Thekumparampil et al., 2019, Algorithm 2): Since the minimax optimization problem here is L̂-strongly-convex–concave and 2L̂-gradient Lipschitz, (Thekumparampil et al., 2019, Theorem 1) tells us that this requires at most m gradient calls for each gi where,
6(2L̂)2
Lm2 ≤ ̂ 4 =
ε2
28L̂ =⇒ O
( L̂
ε
) ≤ m (16)
Therefore the number of gradient computations required for each iteration of inner problem is O ( L̂ log 2 (
1 ε
)) .
Option II, Cutting plane method (Lee et al., 2015): Let us consider u(λ) := minx h(x, λ) + L̂‖x− xs‖2, which is a L̂-Lipschitz, concave function of λ. (Lee et al., 2015) tells us that we can use cutting plane algorithms to obtain λ̂ satisfying u(λ̂) ≥ maxλ∈S u(λ)− ̃ usingO ( k log kL̂̃ ) gradient
queries to u and poly(k log L̂̃ ) computation. The gradient of u is given by∇u(λ) = ∇λh(x ∗(λ), λ), where x∗(λ) := argminx h(x, λ) + L̂‖x− xs‖2. Since h(x, λ) + L̂‖x− xs‖2 is a 3L̂-smooth and L̂-strongly convex function in x, x∗(λ) can be computed up to ̃ error using gradient descent in O (
log L̂̃
) iterations. If we choose ̃ = ̂2/poly(k, L̂/µ), then Proposition 2 tells us that x∗(λ̂)
satisfies the requirements of Step (3) of Algorithm 2 and the total number of gradient calls to each gi is at most O ( poly(k) log L̂ ) in each outer iteration of Algorithm 2.
Proposition 2. Suppose h : Rd1 × U → R be such that h(·, λ) is µ-strongly convex for every λ ∈ U , h(x, ·) is concave for every x ∈ Rd1 and h is L-gradient Lipschitz. Let λ̂ be such that minx h(x, λ̂) ≥ maxλ minx h(x, λ) − and let x∗(λ̂) := argminx h(x, λ̂). Then, we have maxλ h(x∗(λ̂), λ) ≤ minx maxλ h(x, λ) + c ( L µ · + LDU√ µ · √ )
, where DU = maxλ1,λ2∈U ‖λ1 − λ2‖ is the diameter of U .
Proof of Proposition 2. From the hypothesis, we have:
≥ h(x∗, λ∗)− h(x∗(λ̂), λ̂) ≥ h(x∗, λ̂)− h(x∗(λ̂), λ̂) ≥ µ 2 ‖x∗ − x∗(λ̂)‖2,
where (x∗, λ∗) is the Nash equilibrium and the second step follows from the fact that λ∗ = argmaxλ h(x
∗, λ) and the third step follows from the fact that x∗(λ̂) = argminx h(x, λ̂). Consequently, we have that ‖x∗ − x∗(λ̂)‖ ≤ √ 2 /µ. Let λ̄ := argmaxλ h(x ∗(λ̂), λ). We now have
that: max λ h(x∗(λ̂), λ)−max λ min x h(x, λ) = h(x∗(λ̂), λ̄)− h(x∗, λ∗)
= h(x∗(λ̂), λ̄)− h(x∗(λ̂), λ∗) + h(x∗(λ̂), λ∗)− h(x∗, λ∗) (ζ1)
≤ 〈∇λh(x∗(λ̂), λ∗), λ̄− λ∗〉+ L
2 ‖x∗(λ̂)− x∗‖2
(ζ2)
≤ ‖∇λh(x∗(λ̂), λ∗)‖‖λ̄− λ∗‖+ L
µ (ζ3) ≤ ( ‖∇λh(x∗, λ∗)‖+ L‖x∗(λ̂)− x∗‖ ) DU + L
µ
≤ LDU √
2 √ µ + L µ ,
where (ζ1) follows from the fact that h(x∗(λ̂), ·) is concave and x∗ = argminx h(x, λ∗), (ζ2) follows from the bound ‖x∗ − x∗(λ̂)‖ ≤ √ 2 /µ, (ζ3) follows from the L-gradient Lipschitz property of h, and the last step follows from the fact that∇λh(x∗, λ∗) = 0. This proves the proposition.

heading: E PROOFS OF RESULTS IN SECTION 5
text: In this appendix, we present the proofs for the lemmas in Section 5. Recall the SGA update: yt+1 = yt + η∇yfσ(t)(x, yt). (17)
Therefore, the Jacobian of the T -step SGA update is given by Dyt+1 = ( I + η∇yyfσ(t)(x, yt) ) Dyt + η∇yxfσ(t)(x, yt), with A(x, z) = yT (x). (18)
E.1 PROOF OF THEOREM 3
Theorem 3 (General Case). Suppose for all j ∈ [n], fj satisfies Assumption 1. Then, for any fixed randomness z, T -step SGA is (1 + ηL)T -Lipschitz and 4(ρ/L) · (1 + ηL)2T -gradient Lipschitz.
Proof. Lipschitz of yt(x). We first show the Lipschitz claim. We have the following bound on the Jacobian of the update equation given in (18):
‖Dyt+1(x)‖ ≤‖(I + η∇2yyf(x, yt(x)))Dyt(x)‖+ η‖∇2yxf(x, yt(x))‖ ≤(1 + ηL)‖Dyt(x)‖+ ηL.
Since Dy0(x) = 0, the above recursion implies that
‖Dyt(x)‖ ≤ ηL t−1∑ τ=0 (1 + ηL)τ ≤ (1 + ηL)t.
Gradient-Lipschitz of yt(x). Next, we show the claimed gradient Lipschitz constant. As above, using the update equation in (18), we have the following bound on the Jacobian: ‖Dyt+1(x1)−Dyt+1(x2)‖ ≤‖(I + η∇2yyf(x1, yt(x1)))(Dyt(x1)−Dyt(x2))‖+ η‖∇2yxf(x1, yt(x1))−∇2yxf(x2, yt(x2))‖
+ η‖[∇2yyf(x1, yt(x1))−∇2yyf(x2, yt(x2))]Dyt(x2)‖ ≤(1 + ηL)‖Dyt(x1)−Dyt(x2)‖+ ηρ(1 + ‖Dyt(x2)‖)(‖x1 − x2‖+ ‖yt(x1)− yt(x2)‖) ≤(1 + ηL)‖Dyt(x1)−Dyt(x2)‖+ 4ηρ(1 + ηL)2t‖x1 − x2‖. The above recursion implies the claimed Lipschitz constant. Indeed,
‖Dyt(x1)−Dyt(x2)‖ ≤ 4ηρ t−1∑ τ=0 (1 + ηL)t+τ−1‖x1 − x2‖ ≤ 4(ρ/L) · (1 + ηL)2t‖x1 − x2‖.
E.2 PROOF OF THEOREM 4
Theorem 4 (Concave Case). Suppose for all j ∈ [n], fj satisfies Assumption 1 and fj(x, ·) is concave for any x. Then, for any fixed randomness z, T -step SGA is ηLT -Lipschitz and (ρ/L) · (1 + ηLT )3- gradient Lipschitz.
Proof. Lipschitz of yt(x). We first show the Lipschitz claim. Using the update equation in (18), we have the following bound on the Jacobian:
‖Dyt+1(x)‖ ≤‖(I + η∇2yyf(x, yt(x)))Dyt(x)‖+ η‖∇2yxf(x, yt(x))‖ ≤‖Dyt(x)‖+ ηL.
Since Dy0(x) = 0, the above recursive implies that ‖Dyt(x)‖ ≤ ηLt. Gradient-Lipschitz of yt(x). Next, we show the claimed gradient Lipschitz constant. Using the update equation in (18):, we have the following bound on the Jacobian:
‖Dyt+1(x1)−Dyt+1(x2)‖ ≤‖(I + η∇2yyf(x1, yt(x1)))(Dyt(x1)−Dyt(x2))‖+ η‖∇2yxf(x1, yt(x1))−∇2yxf(x2, yt(x2))‖
+ η‖[∇2yyf(x1, yt(x1))−∇2yyf(x2, yt(x2))]Dyt(x2)‖ ≤‖Dyt(x1)−Dyt(x2)‖+ ηρ(1 + ‖Dyt(x2)‖)(‖x1 − x2‖+ ‖yt(x1)− yt(x2)‖) ≤‖Dyt(x1)−Dyt(x2)‖+ ηρ(1 + ηLt)2‖x1 − x2‖.
This recursion implies the following gradient Lipschitz constant:
‖Dyt(x1)−Dyt(x2)‖ ≤ ηρ t−1∑ τ=0 (1 + ηLτ)2‖x1 − x2‖ ≤ (ρ/L) · (1 + ηLt)3‖x1 − x2‖.
E.3 PROOF OF THEOREM 5
Theorem 5 (Strongly-concave Case). Suppose for all j ∈ [n], fj satisfies Assumption 1 and fj(x, ·) is α-strongly concave for any x. Then, for any fixed randomness z, T -step SGA is κ-Lipschitz and 4(ρ/L) · κ3-gradient Lipschitz, where κ = L/α is the condition number.
Proof. Denote the condition number κ = L/α.
Lipschitz of yt(x). We first show the claimed Lipschitz constant. Using the update equation in (18), we have that
‖Dyt+1(x)‖ ≤‖(I + η∇2yyf(x, yt(x)))Dyt(x)‖+ η‖∇2yxf(x, yt(x))‖ ≤(1− ηα)‖Dyt(x)‖+ ηL.
Since Dy0(x) = 0, the above recursion gives the following bound:
‖Dyt(x)‖ ≤ ηL t−1∑ τ=0 (1− ηα)τ ≤ κ.
Gradient-Lipschitz of yt(x). Next we show the claimed gradient Lipschitz constant. Again, using the update equation, we have that
‖Dyt+1(x1)−Dyt+1(x2)‖ ≤‖(I + η∇2yyf(x1, yt(x1)))(Dyt(x1)−Dyt(x2))‖+ η‖∇2yxf(x1, yt(x1))−∇2yxf(x2, yt(x2))‖
+ η‖[∇2yyf(x1, yt(x1))−∇2yyf(x2, yt(x2))]Dyt(x2)‖ ≤(1− ηα)‖Dyt(x1)−Dyt(x2)‖+ ηρ(1 + ‖Dyt(x2)‖)(‖x1 − x2‖+ ‖yt(x1)− yt(x2)‖) ≤(1− ηα)‖Dyt(x1)−Dyt(x2)‖+ 4ηρκ2‖x1 − x2‖.
This recursion implies that
‖Dyt(x1)−Dyt(x2)‖ ≤ 4ηρκ2 t−1∑ τ=0 (1− ηα)τ‖x1 − x2‖ ≤ 4(ρ/L) · κ3‖x1 − x2‖.
E.4 PROOF OF THEOREM 6
Theorem 6 (General Case). Suppose for all j ∈ [n], fj satisfies Assumption 1. Then, for any fixed seed z, T -step SNAG is T (1 + ηL/θ)T -Lipschitz and 50(ρ/L) · T 3(1 + ηL/θ)2T -gradient Lipschitz.
Proof. Recall the SNAG update ỹt = yt + (1− θ)(yt − yt−1) (19)
yt+1 = ỹt + η∇yfσ(t)(x, ỹt). (20) Observe that the update equation for T -step SNAG implies that
Dỹt = Dyt + (1− θ)(Dyt −Dyt−1) Dyt+1 = (I + η∇yyfσ(t)(x, ỹt))Dỹt + η∇yxfσ(t)(x, ỹt)
(21)
Lipschitz of yt(x), vt(x). We first show the claimed Lipschitz constant. By the update equations in (21), we have that
Dyt+1 = (I + η∇yyfσ(t)(x, ỹt))(Dyt + (1− θ)(Dyt −Dyt−1)) + η∇yxfσ(t)(x, ỹt). Denote δt = ‖Dyt −Dyt−1‖, and note that Dy0 = Dy−1 = 0 so that δ0 = 0. By the equation above, we have that
δt+1 ≤ηL‖Dyt‖+ (1 + ηL)(1− θ)δt + ηL
≤ηL t∑
τ=1
δτ + (1 + ηL)(1− θ)δt + ηL.
In the following, we use induction to prove that δt ≤ (1 + ηL/θ)t. (22)
It is easy to verify that this is true for the base case δ0 = 0 ≤ 1. Suppose the claim is true for all τ ≤ t, then we have that
δt+1 ≤ηL t∑
τ=1
(1 + ηL/θ)τ + (1 + ηL)(1− θ)(1 + ηL/θ)t + ηL
≤ηL t∑
τ=0
(1 + ηL/θ)τ + (1− θ)(1 + ηL/θ)t+1
=θ[(1 + ηL/θ)t+1 − 1] + (1− θ)(1 + ηL/θ)t+1 ≤ (1 + ηL/θ)t+1. This proves the induction claim. Therefore, by (22), we have the following two bounds:
‖Dyt(x)‖ ≤ t∑
τ=1
δτ ≤ t(1 + ηL/θ)t,
‖Dỹt(x)‖ ≤(2− θ)‖Dyt(x)‖+ (1− θ)‖Dyt−1(x)‖ ≤ 3t(1 + ηL/θ)t.
Gradient-Lipschitz of yt(x). Next, we show the claimed gradient Lipschitz constant. For any fixed x1, x2, denote wt = Dyt(x1)−Dyt(x2), we have wt+1 =(I + η∇yyfσ(t)(x1, ỹt(x1)))(wt + (1− θ)(wt − wt−1))
+ η(∇yxfσ(t)(x1, ỹt(x1))−∇yxfσ(t)(x2, ỹt(x2)))︸ ︷︷ ︸ T1 + η(∇yyfσ(t)(x1, ỹt(x1))−∇yyfσ(t)(x2, ỹt(x2)))(Dyt(x2) + (1− θ)(Dyt(x2)−Dyt−1(x2)))︸ ︷︷ ︸ T2 .
We note that we can upper bound the last two terms above as follows:
T1 + T2 ≤ηρ(‖x1 − x2‖+ ‖ỹt(x1)− ỹt(x2)‖) + ηρ(‖x1 − x2‖+ ‖ỹt(x1)− ỹt(x2)‖)(2‖Dyt(x2)‖+ ‖Dyt−1(x2)‖) ≤24ηρt2(1 + ηL/θ)2t‖x1 − x2‖.
Therefore, let ζt = ‖wt − wt−1‖, and ∆ = ‖x1 − x2‖, we have the following:
ζt+1 ≤ηL‖wt‖+ (1 + ηL)(1− θ)ζt + 24ηρt2(1 + ηL/θ)2t∆
≤ηL t∑
τ=1
ζτ + (1 + ηL)(1− θ)ζt + 24ηρt2(1 + ηL/θ)2t∆.
In the following, we use induction to prove that
ζt ≤ 50(ρ/L) · t2(1 + ηL/θ)2t∆ := ψ(t). (23)
It is easy to verify that this is true for the base case ζ0 = 0. Suppose the claim is true for all τ ≤ t, then we have that
ζt+1 ≤50ηρ t∑
τ=1
τ2(1 + ηL/θ)2τ∆ + (1 + ηL)(1− θ)ψ(t) + 24ηρt2(1 + ηL/θ)2t∆
≤θ(ρ/L) · [50t2 (1 + ηL/θ) 2(t+1) − 1
(1 + ηL/θ)2 − 1 + 24(ηL/θ)t2(1 + ηL/θ)2t]∆ + (1− θ)ψ(t+ 1)
≤θ(ρ/L) · [25t2(1 + ηL/θ)2(t+1) + 24t2(1 + ηL/θ)2(t+1)]∆ + (1− θ)ψ(t+ 1) ≤θ(ρ/L) · [50t2(1 + ηL/θ)2(t+1)]∆ + (1− θ)ψ(t+ 1) ≤ ψ(t+ 1).
This proves the induction claim. Therefore, by (23), we have that
‖Dyt(x1)−Dyt(x2)‖ = ‖wt‖ ≤ t∑
τ=1
ζτ ≤ 50(ρ/L)t3(1 + ηL/θ)2t‖x1 − x2‖.
E.5 PROJECTED GRADIENT ASCENT IS NOT GRADIENT-LIPSCHITZ
Proposition 3. Consider f(x, y) = xy for (x, y) ∈ X × Y , where X = [0, 10] and Y = [0, 1]. 1-step projected gradient ascent given by:
y1(x) = PY(y0 + η∇yf(x, y0)) y0 = 0,
where η > 1/10 is not a gradient-Lipschitz algorithm.
Proof. We see that y1(x) = min(1, ηx) and f(x, y1(x)) = xmin(1, ηx). For η < 1/10, we see that f(x, y1(x)) is not gradient-Lipschitz at x = 1/η ∈ (0, 10).

heading: F ON NONCONVERGENCE OF EXTRAGRADIENT METHOD AND OPTIMISTIC GRADIENT DESCENT ASCENT (OGDA)
text: In this section, we show that there exist nonconvex-nonconcave problems where the extragradient method and OGDA get trapped in limit cycles. While the example we construct is a quadratic function that is not bounded over all of the space, it will be clear from the proof that the same results hold for any function that matches the constructed quadratic locally around origin.
Consider the following two dimensional quadratic function parametrized by a, b ∈ R:
f(x, y) = 1 2 ax2 + bxy − 1 2 ay2 = 1 2 (x y) ( a b b −a )( x y ) (24)
Denote z := (x, y), Φ := ( a b −b a ) and define:
F (z) := ( ∇xf(x, y) −∇yf(x, y) ) = ( a b −b a ) ︸ ︷︷ ︸
Φ
( x y ) := Φ · ( x y ) ,
Let the eigenvalues of matrix Φ be λ1, λ2. We know they satify the characteristic equation (λ − a)2 + b2 = 0. By Vieta’s formulas, we know that λ1 + λ2 = 2a, λ1λ2 = a2 + b2. This justifies the following proposition. Proposition 4. For any complex number c ∈ C, there exist a, b ∈ R s.t. the eigenvalues of Φ are c and c̄. Here c̄ is the complex conjugate of c.
Proof. Let c = p+ qi for some p, q ∈ R, we can choose a = (c+ c̄)/2 = p, b = ± √ cc̄− a2 = ±q. It is easy to check such matrix Φ has eigenvalues c and c̄.
F.1 EXTRAGRADIENT METHODS
The extragradient algorithm (Korpelevich, 1976) uses the following update:
zt+1/2 =zt − ηF (zt) zt+1 =zt − ηF (zt+1/2)
For the case of quadratic function specified by (24), this update is equivalent to
zt+1 = (I − ηΦ(I − ηΦ))zt = (I − ηΦ + η2Φ2)zt Clearly, the eigenvalues of matrix (I−ηΦ+η2Φ2) are simply (1−ηλ1 +η2λ21) and (1−ηλ2 +η2λ22). Proposition 5. For the extragradient algorithm with any fixed learning rate η, there exists a quadratic function, and appropriate initial points such that the extragradient algorithm is trapped in a limit cycle.
Proof. For any given θ ∈ (0, 2π), we can simply pick λ1 ∈ C to be the solution of equation 1− ηλ1 + η2λ21 = eiθ. This is a quadratic equation of λ1, which always has nonzero complex roots. For λ2 = λ̄1, we verify that 1− ηλ2 + η2λ22 = e−iθ. Finally, by Proposition 4, we know that there exists a choice of a, b such that, the two eigenvalues of (I − ηΦ + η2Φ2) are precisely eiθ and e−iθ.
If the initial point ( x0 y0 ) can be decomposed as ( x0 y0 ) = α1z1 + α2z2, where z1 and z2 are the two eigenvectors of Φ corresponding to eigenvalues λ1 and λ2 respectively, we see that the extra gradient
algorithm follows the trajectory ( xt yt ) = α1e iθtz1 + α2e −iθtz2, thereby getting trapped in a limit cycle.
F.2 OPTIMISTIC GRADIENT DESCENT ASCENT (OGDA)
The OGDA algorithm (Daskalakis & Panageas, 2018a) has the following update:
zt+1 = zt − 2ηF (zt) + ηF (zt−1). (Daskalakis & Panageas, 2018a)[Section 4.1] presents an example where OGDA is empirically not shown to converge for some initialization points. Here, we present an example for which nonconvergence of OGDA is shown rigorously. We can rewrite this update as(
zt+1 zt
) = ( I − 2ηΦ ηΦ
I 0 )( zt zt−1 ) There are four eigenvalues for the matrix ( I − 2ηΦ ηΦ
I 0
) . Two of them µ1, µ2 are eigenval-
ues of the matrix (
1− 2ηλ1 ηλ1 1 0 ) while the other two µ3, µ4 are eigenvalues of the matrix(
1− 2ηλ2 ηλ2 1 0
) , where λ1 and λ2 are the eigenvalues of Φ.
Proposition 6. For the OGDA algorithm with any fixed learning rate η, there exists a quadratic function, and a choice of initial points such that the iterates are trapped in a limit cycle.
Proof. We will fist show that there is a choice for a and b so that the resulting eigenvalues µ1, µ2 of (
1− 2ηλ1 ηλ1 1 0
) and µ3, µ4 of ( 1− 2ηλ2 ηλ2
1 0
) satisfy |µ1| = |µ3| = 1 and |µ2| =
|µ4| < 1. Let us first fix µ1 = eiθ and choose ηλ1 = µ1(µ1−1)2µ1−1 so that we have µ1 is a root of µ2 − (1− 2ηλ1)µ+ ηλ1 = 0. We note that µ2 is the other root of the above equation. We have that:
|ηλ1| = |µ1 − 1| |2µ1 − 1| =
√ (cos θ − 1)2 + sin2 θ
(2 cos θ − 1)2 + sin2 θ .
Therefore, for any θ ∈ (0, π/4], we have |ηλ1| < 1. That is |µ1µ2| < 1, since |µ1| = 1, we have |µ2| < 1. By symmetry, we know by choosing λ2 = λ̄1, the two eigenvalues of (
1− 2ηλ2 ηλ2 1 0 ) are µ3 = µ̄1 and µ4 = µ̄2. In sum, we have proved that for any θ ∈ (0, π/4], and any learning rate η,
there exists a choice of a, b such that the four eigenvalues of ( I − 2ηΦ ηΦ
I 0
) are e±iθ, c′, c̄′
where |c′| = |c̄′| < 1. If the initial points ( z1 z0 ) have the decomposition ∑4 i=1 αiz̄i, where
z̄i is the eigenvector corresponding to eigenvalue µi, then the iterates zt and zt−1 are given by( zt zt−1 ) = ∑4 i=1 αiµ t iz̄i. As t → ∞, ( zt zt−1 ) converges to α1eiθtz̄1 + α3e−iθtz̄3, proving that OGDA iterates get trapped in a limit cycle and neither converge to a single point nor escape to infinity.

heading: G ADDITIONAL EXPERIMENTS AND DETAILS
text: In this appendix section, we provide additional experimental results and details.
Dirac-GAN. In the results presented in Section 6 for this problem, the discriminator sampled its initialization uniformly from the interval [−0.1, 0.1] and performed T = 10 steps of gradient ascent. For the results given in Figure 5, we allow the discriminator to sample uniformly from the interval [−0.5, 1] and consider the discriminator performing T = 100 (Figure 5b) and T = 1000 (Figure 5c) gradient ascent steps. The rest of the experimental setup is equivalent to that described in Section 6.
For the result presented in Figure 5b, we see that with this distribution of initializations for the discriminator and T = 100 gradient ascent steps, the generator is not able to converge to the optimal parameter of θ∗ = 0 to recreate the underlying data distribution using our algorithm which descends ∇f(θ,A(θ)) or the algorithm that descends ∇θf(θ,A(θ)). However, we see that our algorithm converges significantly closer to the optimal parameter configuration. Furthermore, we still observe stability and convergence from our training method, whereas standard training methods using simultaneous or alternating gradient descent-ascent always cycle. This example highlights that the optimization through the algorithm of the adversary is important not only for the rate of convergence, but it also influences what the training method converges to and gives improved results in this regard.
Finally, in the result presented in Figure 5b, we see that with this distribution of initializations for the discriminator and T = 1000 gradient ascent steps, the generator is able to converge to the optimal parameter of θ∗ = 0 to recreate the underlying data distribution using our algorithm which descends ∇f(θ,A(θ)) or the algorithm that descends ∇θf(θ,A(θ)). Thus, while with T = 100 we did not observe convergence to the optimal generator parameter, with a stronger adversary we do see convergence to the optimal generator parameter. This behavior can be explained by the fact that when the discriminator is able to perform enough gradient ascent steps to nearly converge, the gradients ∇f(θ,A(θ)) and ∇θf(θ,A(θ)) are nearly equivalent. We remark that we repeated the experiments 5 times with different random seeds and show the mean generator parameters during the training with a window around the mean of a standard deviation. The results were very similar between runs so the window around the mean is not visible.
Mixture of Gaussians. We noted in Section 6 that we repeated our experiment training a generative adversarial network to learn a mixture of Gaussians 10 times and observed that for each run of the experiment our training algorithm recovered all modes of the distribution. We now show those results in Figure 6. In particular, in Figure 6a we show the real data distribution and in Figures 6b–6k we show the final generated distribution from 10 separate runs of the training procedure after 150k generator updates. Notably, we observe that each run of the training algorithm is able to generate a distribution that closely resembles the underlying data distribution, showing the stability and robustness of our training method.
We also performed an experiment on the mixture of Gaussian problem in which the discriminator algorithm was the Adam optimization procedure with parameters (β1, β2) = (0.99, 0.999) and learning rate η2 = 0.004 and the generator learning rate was η1 = 0.05. The rest of the experimental setup remained the same. We ran this experiment 10 times and observed that for 7 out of the 10 runs of the final generated distribution was reasonably close to the real data distribution, while for 3 out of the 10 runs the generator did not learn the proper distribution. This is to say that we found the training algorithm was not as stable when the discriminator used Adam versus normal gradient ascent. The final generated distribution from the 7 of 10 runs with reasonable distributions are shown in Figure 7.
Adversarial Training. We now provide some further background on the adversarial training experiment and additional results. It is now well-documented that the effectiveness of deep learning classification models can be vulnerable to adversarial attacks that perturb the input data (see, e.g., Biggio et al. 2013; Szegedy et al. 2014; Kurakin et al. 2017; Madry et al. 2018). A common approach toward remedying this vulnerability is by training the classification model against adversarial perturbations. Recall from Section 6 that given a data distributionD over pairs of examples x ∈ Rd and labels y ∈ [k], parameters θ of a neural network, a set S ⊂ Rd of allowable adversarial perturbations, and a loss function `(·, ·, ·) dependent on the network parameters and the data, adversarial training amounts to considering a minmax optimization problem of the form minθ E(x,y)∼D[maxδ∈S `(θ, x+ δ, y)].
A typical approach to solving this problem is an alternating optimization approach (Madry et al., 2018). In particular, each time a batch of data is drawn from the distribution, T -steps of projected gradient ascent are performed by ascending along the sign of the gradient of the loss function with respect to the data and projecting back onto the set of allowable perturbations, then the parameters of the neural network are updated by descending along the gradient of the loss function with the perturbed examples. The experimental setup we consider is analogous but the inner maximization loop performs T -steps of regular gradient ascent (not using the sign of the gradient and without projections).
For the adversarial training experiment considered in Section 6, we also evaluated the trained models against various other attacks. Recall that the models were training using T = 10 steps of gradient ascent in the inner optimization loop with a learning rate of η2 = 4. To begin, we evaluated the trained models against gradient ascent attacks with a fixed learning rate of η2 = 4 and a number of steps T ∈ {5, 10, 20, 40}. We also evaluated the trained models against gradient ascent attacks with a fixed budget of Tη2 = 40 and various choices of T and η2. These results are presented in Figure 9. Finally, we evaluated the trained models against attacks using the Adam optimization method with a fixed budget of Tη2 = 0.04 and various choices of T and η2. These results are presented in Figure 10. Notably, we see that our algorithm outperforms the baselines and similar conclusions can be drawn as from the experiments for adversarial training presented in Section 6. The additional experiments highlight that our method of adversarial training is robust against attacks that the algorithm did not use in training when of comparable computational power and also that it improves robustness against attacks of greater computational power than used during training.
In Section 6, we showed the results of evaluating the gradient norms ‖∇f(θ,A(θ))‖ as a function of the number of gradient ascent steps T in the adversary algorithm A and observed that it grows much slower than exponentially. Here we provide more details on the setup. We took a run of our algorithm trained with the setup described in Section 6 and retrieved the models that were saved after 25, 50, 75, and 100 training epochs. For each model, we then sampled 100 minibatches of data and
for each minibatch performed T ∈ {20, 30, 40, 50, 60, 70, 80, 90, 100} steps of gradient ascent with learning rate η2 = 4 (the learning rate from training) and then computed the norm of the gradient ∇f(θ,A(θ)) where A corresponds to the gradient ascent procedure with the given number of steps and learning rate. In Figure 2, which is reproduced here in Figure 11a, the mean of the norm of the gradients over the sampled minibatches are shown with the shaded window indicating a standard deviation around the mean. We also repeated this procedure using η2 = 1 and show the results in Figure 11b from which similar conclusions can be drawn.
Finally, we provide details on the convolutional neural network model for the adversarial training experiments. In particular, this model is exactly the same as considered in (Nouiehed et al., 2019) and we reproduce it in Table 1.
Experimental Details. For the experiments with neural network models we used two Nvidia GeForce GTX 1080 Ti GPU and the PyTorch higher library(Deleu et al., 2019) to compute ∇f(θ,A(θ)). In total, running all the experiments in the paper takes about half of a day with this computational setup. The code for the experiments is included in the supplementary material with instructions on how to run. We built our code for the adversarial training based off code openly provided by the authors of (Nouiehed et al., 2019).

Review summaries:
The paper considers a min-max optimization of general nonconvex functions. The paper proposes methods to approximately find stationary points by "smoothing" the max part. Experimental results show the superiority of the proposed approach to previous work. 

This paper provides a new perspective to solve the nonconvex-nonconcave minimax problems. Specifically, the proposed method turns the nonconvex-nonconcave minimax problem to a nonconvex-concave minimax problem by using a toolkit of multiple smooth algorithms to find a solution of the maximization problem given fixed $x$. Moreover, it studies the convergence properties of the proposed algorithms. Some experimental results on generative gdversarial networks and adversarial training demonstrate the efficiency of the proposed algorithms. 

The paper is trying to address the problem of non-convex non-concave min-max optimization under the perspective of application of smoothed algorithms between the two opponents. More precisely, the paper examine a model where the max-player applied a zero-memory smooth (from differential perspective) algorithm and min-player SGD/SNAG or proximal methods providing results similar with the state of art. The convergence is reassured by "potential" arguments but the fixed point is not an equally game-theoretic notion like Nash Equilibrium.