Minimax Optimization with Smooth Algorithmic Adversaries
Authors: Tanner Fiez
Chi Jin
Praneeth Netrapalli
Lillian J Ratliff
Venue: ICLR 2022 Poster (2022)
Keywords: Minimax optimization
two player zero sum games
generative adversarial networks
adversarial training

Abstract: This paper considers minimax optimization $\min_x \max_y 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,\cdot)$ 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 \emph{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.

Published as a conference paper at ICLR 2022
MINIMAX OPTIMIZATION WITH SMOOTH ALGORITH- MIC ADVERSARIES
Tanner Fiez, Lillian J. Ratliff University of Washington, Seattle (fiezt, ratliffl] Bww. edu
Chi Jin
Princeton University
chi chij@prt ierrinnettnnccm edu
Praneeth Netrapalli Google Research, India pnetrapall1@oogg.....
ABSTRACT
This paper considers minimax optimization min, max, fzz y) in the challeng- ing setting where f can be both nonconvex in æ 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 nonconvex-noncomeer -onconccve minimax optimization that addresses both the above issues. The starting point of this paper is the observation that, under computa- tional budget, the max-player can not fully maximize f(x .) since nonconcave framework, and corre-
maximization is NP-hard in general. So, propose sponding algorithm, for the min 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 find an appropriate "stationary point" in 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 simple, conceptual settings.
INTRODUCTION
This paper considers minimax optimization min, max, f(x y) the context of two-player zero-sum games, where the min-player (controlling r) tries to minimize objective f assuming a worst-case opponent (controlling y) that acts so as to maximize it. Minimax optimization naturally arises in 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 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 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 the minimax theorem, i.e., min, max, J [x,, y) max, ming / (æ, y). which no longer holds beyond the convex-concave setting. Recent line of works (Lin et al.) 2020al Nouiched al. 2019 Thekumparampil et al. 2019; Lin al. 2020b Ostrovskii et al. 2020) address the nonconver-concave setting where f is nonconvex in x but concave
CCurrently with Amazon.

---

Published as a conference paper at ICLR 2022
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 noncomeex-nnnconenny setting.
Consequently, nonconvex-noncconant optimization remains challenging, and two of the most fun- damental theoretical issues are still unresolved: (i) what is 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 [20 8aj Bailey et al. (2200). This current state of affairs strongly motivates the need to develop a strong theoretical foundation for nonconvex-nonconeau minimax optimization and to design better algorithms for solving them.
This work considers the challenging nonconvex-nonconee the practical consideration that under a computational budget, the max-player cannot fully maximize fzx .) since nonconcave maximization NP-hard in general. In fact, in both the settings of GAN and adversarial training, in practice, the max- plx-ellaer employs simple gradient based algorithms such as gradient ascent, run for a few steps - on the order of for GAN training and 40 for adversarial training (see, e.g., Arrovsky et al. 2017: Madry al. 2018 to estimate argmax, I (1x y). To capture this aspect, we assume that the max-player has toolkit of multiple (potentially randomized) algorithms A,, A2. ; AA in an attempt to solve the maximization problem given fixed æ, and picks the best solution among these algorithms. This motivates us to study the surrogate of the minimax optimization problem as
setting. Our framework sprouts from
min, max4e[M] (z,))) = min, maxied, E A,((),,())),,
(1)
where AS denotes the k-dimensional simplex, and Az)z) denotes the output of algorithm A, for given x. When both the objective function f and the algorithms {Ai) are smooth (defined formally in Section 3). we can show that (I) becomes smooth noncomvex-concaa 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 ( The first algorithm is based on stochastic gradient descent (SGD), which is guaranteed to find an appropriate notion of "e-approximate stationary point" in (E gradient computations. The second algorithm is based on proximal algorithm, in the case of deterministic adversarial algorithms {.A,) = this algorithm has an improved gradient complexity O(e-3) or Öppoyy (k))e ()) 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 accelcrated gradient ascent are in fact smooth. Therefore, our framework readily applies 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 proof of concept demonstration that our algorithm converges to desirable points in practice, at least on simple conceptual examples.
2 RELATED WORK
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-nonconeee
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. 2020al Farnia & Ozdagla ar 2020). To the best of our knowledge, the only works that propose relaxed local optimality notion that is shown to exist and be computable in polynomial time is due
to Keswani et al. (2020): Mangoubi & Vishnoi (002). The aforementioned works are similar to this
2

---

Published as a conference paper at ICLR 2022
paper in the sense that the min- min-player faces the max- max-player with computational restrictions, but 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 (202T) 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 "max" function computed by particular smooth algorithms given their initializations, which is 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 & Vishnol (202I) and the optimal points in our paper can be very different, making them incomparable.
PRELIMINARIES
In this section, we present problem formulation and preliminaries. We consider function f satisfying Assumption 1. We denote w (x, y), and assume f Rd x R - TR is:
(a) B-bounded ie., [f()) I B,
(b) G-Lipschitz i..., (f(w1) f(w22) S Gl| w2ll. (c) L-grdiient Lipschitz i.e.. [f V f S [|| w2ll.
(d) p p-Hessian Lipschitz i.e.. f - v² f (w2))l || S pllw - wzll-
where ||-11 denotes Euclidean norm vectors and operator norm for matrices.
We aim to solve gin max fxx v). Since max fx, y) involves non-concave maxi- mization 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 2 E Rd assume that the y-player chooses her (potentially random) strategy U2 (z) = (a) (x, (x)( where we use shorthand 2 == (21, ...... zk). as e" (x) = argmax,e[*] A,,, 2)).. where AI.... As are k deterministic algorithms that take as imput r and random seed 2; E R', where 2; are all independent. Note that the framework captures randomized algorithms e.g.. A could be stochastic gradient ascent on [xx, with initialization, mini- batching 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:
minzeR g(x) where g(x) == B2 (x)))
(2)
21)) need not be continuous even when f satisfies Assumption However, if the algorithms A, are smooth as defined below, the functions f(x Ar, 2:)) behave much more nicely.
For general algorithms A,. the functions
Definition (Algorithm Smoothness). randomized algorithm A: Rd x R + Rd is:
(a) G-Lipschitz. if [|A(1)) 2) A(x2, < G||z1 - x2 ll for any 2.
(b) L-gradient Lipschitz. if (DA(1, - DA(22, 2) S L|| x22 for any
Here DA(x,22 2) E Rd1 x R is the Jacobian of the function A(-, 22 for fixed z. The following lemma tells us that A(z, 2)) behaves nicely whenever AA is a Lipschitz and gradient Lipschitz algorithm. For deterministic algorithms, we also use the shortened notation A(z) and D((()).
G' Lipsschitz and L' graddint Lipschitz and f satisfies Assumption ! Then, for a fixed 2, function f(. A(,,)) is G(1 + G')+ LLipschiitt and L(1 +(1+ + GL' "'L'-gradien Lipschitz.
Lemma 1. Suppose
While g(x) defined in (2) is not necessarily gradient Lipschitz, it can be shown be weakly-convex as defined below. Note that an L-gradient Lipschitz function is L-weakly convex.
Definition 2. function g Rdd1 + R L-weakly convex if x, there exists a vector ue satisfying:
g(x') 2 g(x) + (uz, - xx) ||a se| A s'.
(3)
Any vector us satisfying this property is called the subgradient of g at x and is denoted by Vg(x).
An important property of weakly convex function that the maximum over a finite number of weakly convex function is still weakly convex function.
Lemma 2. Given L-weakly convex functions g1.-.. .9k Rd + R. the maximum function g(.)
max (i()) ) is also L-weakly convex and the set of subgradients of g(-) at x is given by:
0g(x) (Ejesz)) >g (z) >3 2 0, Ejester >g = 1), where S(x) argmax,e(e) (x())
3

---

Published as a conference paper at ICLR 2022
Thus, under Assumption I and the assumptions A, are all G'-Lipschitz and L' L'-gradient Lipschitz, then g(.) defined in (2) is L(1 + G + GL' wwekly 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 approxi- mate stationary points, also need the notion of Moreau envelope.
Definition 3. The Moreau envelope of a function Ied - IR. and parameter À is:
gx (x)
m' g(x') + (2A)-1 || x211
(4)
The following lemma provides useful properties of the Moreau envelope.
Lemma 3. For an L-weakly convex function 9 RR4 + R and À < L/L, we have:
(a) The minimizer (x)))= arg m g(x') + (2 1| 2²11² 3 is unique and (()x
S
(x(x) I g(x). Furthermore, arg min, g(x) = arg min, (z). (b) gx is X x- (1 (1 ())--)--smootti and thus differentiable, and
(c) minweag(ex(s)) (o)) ||u|| I X (z) - =
First order stationary points (FOSP) of non-smooth nonconvex function well-defined, i.e., is
a FOSP of a function (xx) if, 0 E 0f(x"). However, unlike smooth functions, it is nontrivial to define an approximate FOSP. For example, if we define an E-FOSP as the point with min ||u|| S E. where 01(x)) denotes the subgradients of g at x; there may never exist such a point for sufficiently small E, unless x is exactly a FOSP. In contrast, by using above properties of the Moreau envelope of weakly convex function, it's approximate FOSP can be defined (Davis & Drusvyatskiy, 2018):
Definition 4. Given I.-weakly convex function 9. say that x² is e-first order stationary point (e-FOSP) if. (91122(<")) I E, where 91/21 is the Moreau envelope with parameter 1/2L.
Using Lemma 3 we can show that for any s-FOSP x", there exists & such that || x11l S e/2L and migg |
In other words, e-FOSP is Oss) close to point which has subgradient smaller than Other notions of FOSP proposed recently such as in Nouiched et al. (2019) can be shown to strict generalization of the above definition.
MAIN RESULTS
In this section, we present our main results. Assuming that the adversary employs Lipschitz and grassett-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 e-FOSP in O (E-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 e-FOSP faster than SGD. For convenience, we denote (z) == f(x, A, 24)) and recall g(x) == Eg maxxe][]] (x)]. For deterministic A,, we drop and just use gi (z).
4.1 COMPUTING STOCHASTIC SUBGRADIENTS OF g(x)
In this section, we give characterization of subgradients of g(x) and show how compute stochastic subgradients efficiently under the following assumption.
Assumption 2. Algorithms A; in are -'-Lipschitz and T,' T'-gradient Lipschitz as per Definition !
Under Assumptions 1 lndd] 2 Lemma 1 tells us that (x)((x) a G[1++G" and L(1 2')2 GL' GL'-gradient Lipschitz function for every i E [k] with
(zz
=)) + DA, 21) Vyl(2,, #;)),
(5)
where we recall that (A,(z, zi) E Rd xda is the Jacobian matrix of Ai(,, 2;) Rd: + Rd at æ and [a, Ax(x, 2)) denotes the partial derivative of f with respect to the first variable at (x, A,(x, 21)). While there is no known general recipe for computing DA, 2,) for arbitrary algorithm A, 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
4

---

Published as a conference paper at ICLR 2022
Algorithm 1: Stochastic subgradient descent (SGD)
Input: initial point zo. step size 1)
for 8 = 0, 1, ..... do
Sample 21
2 and compute Vg(rzs) according eq. 6
1s+1 f 2s - 1f Vg((ss)
return 8. f- Jis. where s is uniformly sampled from (0.... S...
in PyTTocc (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 (x=,((x) in (5) is most twice the cost of evaluating 9a. [z) s-iit consists forward pass for evaluating (x) and a backward pass for evaluating its gradient (Grefenstette et al. 2019
Lemma 2 shows that g(r) := Ez [maxie(M] [x): a weakly convex function and a stochastic subgradient of g(-) can be computed by generating a random sample of 21. "1. 2k as:
9g(z)=
Σ
(z) for any X E As, where S(x) == argmax Jx,i iE[k]
(6)
JES(Z)
Here Ag is the k-dimensional probability simplex. It can be seen that E, [g(x)] E 0g(x). Further- more, if all A; are deterministic algorithms, then the above is indeed a subgradient of g.
4.2 CONVERGENCE RATE OF SGD
The SGD algorithm to solve (2) is given in Algorithm T The following theorem shows that Algo- rithm finds an c-FOSP of g(.) in = O (c+) iterations. Since each iteration of Algorithm requires computing the gradient of y2,x(x) for each E [A:] at a single point v. this leads to total of
S = 0 (c-) gradient computations for each (x))
Theorem 1. Under Assumptions and 2
S 2 1 and learning rate n (2B/ + 1))) then oulput of Algorithm satisfies (1) S 2, where L == L(1+ G²) GL' and G := G')
Theorem D claims that the expected norm squared of the Moreau envelope gradient of the output point satisfies the condition for being e-FOSP. This, together with Markov's inequality, implies that at least half of ....... .y are 2c-FOSPs, so that the probability of outputting a 2c-OOP is at least 0.5. Proposition in Appendix C how use efficient postprocessing mechanism output a 2e-FOSP with high probability. Theorem I essentially follows from the results of (Davis & Drusvyatskiy 2018), where the key insight is that, expectation, the SGD procedure in Algorithm
almost monotonically decreases the Moreau envelope evaluated x, i.c.. E 91/22 (1x) is almost
monotonically decreasing. This shows that Algorithm T makes (almost) monotonic progress in a precise sense and hence does not have limit cycles. In contrast, none of the other existing algorithms minimax optimization enjoy such a guarantee. Note that this claim in- cludes 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.
for nonconvex-nonconeee
4.3 PROXIMAL ALGORITHM WITH FASTER CONVERGENCE FOR DETERMINISTIC ALGORITHMS
While the rate achieved by SGD the best known for weakly-convex optimization with stochastic subgradient oracle, faster algorithms exist for functions which can be written as maximum over finite number of smooth functiios with access to exact subgradients of these component functions. These conditions are satisfied when A, 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 the results of Thekumparampi et al. (2019), the following theorem provides two alternate ways of implementing Step 3 of Algorithm resulting in two different (and incomparable) convergence rates.
5

---

Published as a conference paper at ICLR 2022
Algorithm 2: Proximal algorithm
Input: initial point zo, target accuracy e, smoothness parameter Σ 8 x- e² (647.)
for [ = 0, S do
Find #s+1 such that
max (e(#x+1) + Ell - x,+1 113 ming max4e(M] (i(x)) + E1| 11 =1(?) + 2/4
if max)e[[]] (xx4+1) + Lilar, 1z41ll 11 maXie[N] (:(2)) 32/4 then
return
and 2 if == L(1 G¹y² + GL' KG(L G') and $ 2 200LBe then Algorithm returns I, satisfying (V (+.)l S c. Depending on whether we use (Thekumparampil et a. 2019 Algorithm 1) or cutting plane method (Lee et al. 2015) for solving Step 3 of Algorithm
Theorem 2. Under Assumptions
the total number of gradient computations of each gi is O 1 or
O LB pool((k) log? ! respectively.
2 outputs an c-FOSP using (ke 3) or O (poly(k)c~21og !) gradient queries to each 9a depending on whether Thekumparampil et al. (2019 Algorithm 3) or cutting plane method (Lee et al. 2015) was used for implementing Step While the proximal algorithm itself works even when A, are randomized algorithms, there are known algorithms that can implement Step (3) with fewer than O (c stochastic gradient queries. Hence, this does not improve upon the O (E-1) guarantee for Algorithm
Ignoring the parameters I., G, I,' and G², the above theorem tells us that Algorithm
when A, are randomized algorithms. The proof of Theorem (2nni22shoo shows that the iterates x. monotonically
decrease the value ((x,), guaranteeing that there are no limit cycles for Algorithm 2 as well.
SMOTTHNSSS POPULAR ALGORITHMS
In this section, we show that two popular algorithms- (SGA) and T T-sp stochastic Nesterov's 's accelerated gradient ascent (SNAG) are both Lipschitz and gradient-Lipschiee satisfying Assumption and hence are captured by our results in Section 4 Con- sider the setting [(x, y) = Σjem SJ (zr, v). Let
T-step stochastic gradient ascent
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 7 T-step SGA for different assumptions 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 given and random seed 2, the T-step SGA update is given by: V6+1 Y1 + v ff yt), where o : [T] + [N] is a sample selection function and 17 is the stepsize. Observe that with the same randomness z, the initial point does not depend on I i.c., (z)))) = (o so Dyo = 0. The following theorems provide the Lipschitz and gradient Lipschitz constants of yr (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-conent
nonconvex-nomconccve
and nonconvex nonconvex-stronggy concave.
Theorem (General Case). Suppose for all j E [n], f, satisfies Assumption
7 Then, for any fixed randomness z, T -tepp SGA is + +1) -Lisschit and 4(p/ L)) (1 + (1+nL)²r -gradient Lipschitz.
Theorem 4 (Concave Case). Suppose for all j E [p), f3 satisfies Assumption | and fú is concave for any x. Then, for any fixed randomness z, T-step SGA is -ipschitz and (p/L)- (1+ nLT)3 gradient Lipschitz.
Theorem's 5 cerongly-concave Case), Suppose for all j [n]. f, satisfies Assumption I Land fa is a-strongly concave for any x. Then, for any fixed randomness T-step SGA is k- k-Tipschitz and 4(p/ L) 13 gradient Lipschitz, where K = L/a is the condition number.
T-step SNAG: For a given random seed 2, the Tsstpp SNAG update is given by:
J yı + (1 0) 12-1) and yt-1 ÿe 1/ fo Wc),

---

Published as a conference paper at ICLR 2022
where 77 is the stepsize, 8 E [0, 1] is the momentum parameter. The output of the algorithm is given by A(x, 2) = yr (2). Furthermore, we have the following guarantee.
Theorem (General Case), Suppose for all E [n), f, satisfies Assumption 7 Then. for any fixed seed 2, Ttep SNAG r[1+nL/0)) Lipshhit and p/ L) T (1+
-gradient Lipschitz.
Remarks on the Impact of the Smoothness Results: eters for Tstep SGA and T-step SNAG in the setting where f is nonconvex nonconcave nonconvex-nnnccnncavv are all exponential in T' the duration of the algorithm. In general, this scems 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, R.SPrrp,, etc. In contrast, in the nonconvex-concave and honconvex-strongl 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-s/rongly concave, the analogous smoothness parameters are no longer dependent on T. We conjecture this also the case for T Testep 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 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 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 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 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 in Appendix E.5
The I. Lipschitz and gradient Lipschitz param-
limit the ability of
EMPIRICAL RESULTS
This section presents empirical results evaluating our SGD algorithm (Algorithm IT for generative adversarial networks (Goodfellow et al.] 2014) and adversarial training (Madry et al. 2018). Our results demonstrate that our framework results 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 charac- terized by the following minimax problem (Nagarajan & Kolter| 2017: Mescheder et al. 2018):
(7) In this formulation GB 2 - X' is the generator network parameterized by 0 that maps from the latent space 2 to the input space X, D., : X' + R is discriminator network parameterized by w that maps from the input space X' real-valued logits, and px and pz are the distributions over the input
ming max f(0, w) = Ez-px [((w(<))) + Ezopz E( (G)))))
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-GAM (Mescheder et al. 2018) is simple and common baseline for eval- uating the efficacy of generative adversarial network training methods. In this problem, the gen- erator distribution G=(z) 8y is a Dirac distribution concentrated at 0, the discriminator network (w) -wa is linear, and the real data distribution px = ón is a Dirac distribution concentrated at zero. The resulting objective after evaluating 7 with the loss ((w)
(1 + (xp(-w)) is
ming max f(8, = E(Bw) + E(0) = log(1 + e -0w) - log(2))
To mimic the real data distribution, the generator parameter 0 should converge to 0 = 0. Notably, simultancous and alternating gradient descent-ascent are known to cycle and fail to converge on this problem (see Figure T]. We consider instantiation of our framework where the discriminator
7

---

Published as a conference paper at ICLR 2022
Sim-GDA
Alt-GDA
V10.A(0))
Training Epachs-25
Gradient Norm
10a
Trainingg Spachsm50
Teiinigg Epochs=75
VMM
Training Epochs-100
10
2000 2000
SAAU
20:00
1900
20000
10
Inner Optimization Steps
10
Figure 1: Dirac-GAN: Generator parameters while training using simultaneous and alternating gradient descent-ascent (left), and our framework (right) with & without optimizing through the discriminator. Un- der our framework, training is stable and converges to correct distribution. Further, differentiating through the discriminator results faster convergence.
Adversarial training: f0, A(O)) as a function of number of steps T taken by gradient ascent (GA) algorithm A evaluated at multiple points in the training procedure. The plot shows that, in practice the Lipschitz parameter of GA does not grow exponentially in
Figure
(a) Real Data
(b) 10k
(c) 40k
(d) 70k
(e) 100k
(I) 130k
(g) 150k
Figure 3: Mixture of Gaussians: Generated distribution at various steps during course of training.
We that training is stable and results in monotonic progress towards the true distribution.
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 17 0.01. We present the results in Figure Notably, the generator parameter monotonically converges to the optimal 6* and matches the real data distribution using our training method. We also show the performance when the generator descends using partial gradient V (a, A(t) instead of the total gradient V (0, A(0)) Algorithm T This method able to converge to the optimal generator distribution but at 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
now demonstrate that the insights we developed from the Dirac-GAN (stability and monotonic improvement) carry over to the more complex problem of learning 2- dimensional mixture Gaussians. This is a common example and a number of papers (see, c.g., Metz al. 2017 Mescheder et al. 2017] Balduzzi 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 ó E /4]7 and each with covariance o² where o² = 0.05. For training, the real data E I22 is drawn random from the set of Gaussian distributions and the latent data R 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 ReI.U activation functions. We consider the objective from 7 with (xxp(ww)
Mixture of Gaussians.
((w) = - log(1 + exp(p 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] 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 both fixed to be 7) 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 robust by presenting the
8

---

Published as a conference paper at ICLR 2022
GA Attack: (Steps, LR:: (10, 4)
GA Attack: (Steps. LB): 11
GA Attack: (Steps, LA): 120,0
Adam Attack: (Staps. 180 0.002)
90
90
90
Accuracy
85
85
75
85
80
80
75
75
65
75
70
55
75
100
100
100
Training Epochs
Training Epochs
Training Epochs
Training Epochs
Standard Training
Vef(O.A(0))
Figure 4: Adversarial training: Test accuracy during course of training where the attack used during training gradient ascent (GA) with learning rate (LR) of 4 and number of steps (Steps) of 10 but evaluated against attacks with different Steps and LR. These plots show that training with a single attack gives more robustness to even other attacks with different parameters or algorithms of similar computational power. This empirical insight is complementary to our theoretical results that extend to the setting of training against multiple smooth algorithms. Finally, using total gradient ([(0,A(0)) yields better robustness compared to using partial gradient (of A(O)).
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 [
Adversarial Training, Given data distribution D over pairs of examples x E Id and labels y [k]] parameters of neural network, set C IRd 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 ming (( [maxses E(0, x + 6, y)] In practice Madry et al. 2018)), the inner maximization problem maxées E x + 5, y) solved using projected gradient ascent. However, as described in Section 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 T with usual adversarial training (Madry et al. 2018) which descends Vef A())) instead of (0 A(0)), and baseline of standard training without adversarial training. For each algorithm, we train for 100 passes over the training set using batch size of 50. The minimization procedure has fixed learning rate of 7/2 0.0001 and the maximization procedure runs for = 10 steps with a fixed learning rate of 722 = 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 V (0,,A(0)) A(0))] 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
7 CONCLUSION
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 new framework for solving nonconvex- nonnonocve 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 small- scale 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. An important future direction of work is to scale our algorithm to large scale, state of the art GAN benchmarks. The key challenge here is that reinitializing the discriminator parameters necessitates running several steps of gradient ascent for discriminator for every generator update. One approach to overcome this could be use pretrained networks for initializing the discriminator.

---

Published as a conference paper at ICLR 2022
REFERENCES
Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann. Local saddle point optimization: A curvature exploitation approach. In International Conference on Artificial Intelli- gence and Statistics, pp. 486-495, 2019.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International Conference on Machine Learning, pp. 214-223, 2017.
Kendall Atkinson, Weimin Han, and David E Stewart. Numerical solution of ordinary differential equations, volume 108. John Wiley & Sons, 2011.
James P Bailey, Gauthier Gidel, and Georgios Piliouras. Finite regret and cycles with fixed step-size via alternating gradient descent-ascent. Conference on Learning Theory, pp. 391 407. PMLR, 2020.
David Balduzzi, Sehastien Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanics n-player differentiable games. International Conference on Machine Learning, pp. 354-363, 2018.
Tamer Başar and Geert Jan Olsder. Dynamic noncooperative game theory. SIAM, 1998.
Dimitri P Bertsekas. Convex optimization theory. Athena Scientific Belmont, 2009.
Battista Biggio, Igino Corona, Davide Maiorca, Blaine Nelson, Nedim vSrndie, Pavel Laskov, Giorgio Giacinto, and Fabio Roli. Evasion attacks against machine learning at test time. In European conference machine learning and knowledge discovery in databases, pp. 387-402, 2013.
Benjamin Chasnov, Tanner Fiez, and Lillian Ratliff. Opponent anticipation via conjectural variations. In Smooth Games Optimization and Machine Learning Workshop at NeurIPS 2020: Bridging Game Theory and Deep Learning, 2020.
Earl A Coddington and Norman Levinson. Theory of ordinary differential equations. Tata McGraw-
Hill Education, 1955.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, pp. 9256-9266, 2018a.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9246,
2018b.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In International Conference Learning Representaatinns (ICLR 2018), 2018.
Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis. The complexity of constrained min-max optimization. ACM Symposium on Theory of Computing, 2021.
Damek Davis and Dmitriy Drusvyatskiy. Stochastic subgradient method converges at the rate o(k (14) on weakly convex functions. arXiv preprint arXiv: 100. 08020009820.8... 2018.
Tristan Deleu, Tobias Würfl, Mandana Samiei, Joseph Paul Cohen, and Yoshua Bengio. Torchmeta: A meta-learning library for pytorch. arXiv preprint
2019.
Farzan Farnia and Asuman Ozdaglar. Do gans always have nash equilibria? In International Conference on Machine Learning, pp. 3029-3039, 2020.
Tanner Fiez and Lillian Ratliff. Local convergence analysis of gradient descent ascent with finite timescale separation. In International Conference Learning Representations, 2021.
Tanner Fiez, Benjamin Chasnov, and Lillian Ratliff. Implicit learning dynamics in stackelberg games: Equilibria characterization, convergence analysis, and empirical study. International Conference Machine Learning, pp. 3133-3144, 2020.
10

---

Published as a conference paper at ICLR 2022
Jakob Foerster, Richard Y Chen, Maruan Al-Shedivat, Shimon Whiteson, Pieter Abbeel, and Igor Mor- datch. Learning with apponent-learning awareness. In International Conference on Autonomous Agents and MulttiAgent Systems, pp. 122-130, 2018.
Yoav Freund, Michael Kearns, Yishay Mansour, Dana Ron, Ronitt Rubinfeld, and Robert E Schapire. Efficient algorithms for learning to play repeated games against computationally bounded adver- saries. In Proceedings of IEEE 36th Anmual Foundations of Computer Science, pp. 332-341. IEEE, 1995.
lan J Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial networks. In Advances in Neural Information Processing Systems, 2014.
Edward Grefenstette, Brandon Amos, Denis Yarats, Phu Mon Htut, Artem Molchanov, Franziska Meier, Douwe Kiela, Kyunghyun Cho, and Soumith Chintala. Generalized inner loop meta-learning. arXiv preprint arXiv:1910.01727, 2019.
Joseph Y Halpern, Rafael Pass, and Lior Seeman. Decision theory with resource-bounded agents. Topics in cognitive science, 6(2):245-257, 2014.
Philip Hartman. Ordinary Differential Equations. Society for Industrial and Applied Mathematics, second edition, 2002. doi: 10.1137/1 011377/97780997192222
Nicholas JA Harvey, Christopher Liaw, and Sikander Randhawa. Simple and optimal bigb-irobabillty bounds for strongly-convex stochastic gradient descent. arXiv preprint vrXiiv1909.000 00843, 2019.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: Convergence to spurious non-critical sets. arXiv preprint 2rXiv:2006.00065 2020.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-noncoocan minimax optimization? In International Conference on Machine Learning, pp. 4880-4889, 2020.
Sham Kakade, Shai Shalev-Shward Ambuj Tewari, et al. On the duality of strong convexity and strong smoothness: Learning applications and matrix regularization. Unpublished Manuscript, http://ttic. uchicago. hhluhhailpoper/KkkaaeSSaeeeeee
pdf. 2(1), 2009.
Vijay Keswani, Oren Mangoubi, Sushant Sachdeva, and Nisheeth K Vishnoi. Gans with first-order greedy discriminators. arXiv preprint arXiv:2006. 12376, 2020.
Weiwei Kong and Renato DC Monteiro. An accelerated inexact proximal point method for solving nonconvex-coneave min-max problems. arXiv preprint arXiv: 13433, 2019.
Galina M Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Alexey Kurakin, Ian J Goodfellow, and Samy Bengio. Adversarial machine lcarning at scale. In International Conference Learning Representations, 2017.
Yin Tat Lee, Aaron Sidford, and Sam Chiu-wai Wong. A faster cutting plane method and its implications for combinatorial and convex optimization. In 2015 IEEE 56th Annual Symposium on Foundations of Computer Science, pp. 1049-1065. IEBE, 2015.
Qi Lei, Sai Ganesh Nagarajan, Ioannis Panageas, and xiao wang. Last iterate convergence in no-regret learning: constrained min-max optimization for conex-econcve landscapes. In International Conference on Artificial Intelligence and Statistics, pp. 1441-1449, 2021.
Alistair Letcher. On the impossibility of global convergence in multi-loss optimization. In Interna- tional Conference on Learning Representations, 2021.
Alistair Letcher, Jakob Foerster, David Balduzzi, Tim Rocktäschel, and Shimon Whiteson. Stable op- ponent shaping in differentiable games. In International Conference on Learning Representations, 2019.
Haochuan Li, Yi Tian, Jingzhao Zhang, and Ali Jadbabaie. Complexity lower bounds for nonconvex- strongly-coneave min-max optimization. arXiv preprint 144.0:2/04.08708, 2021.
11

---

Published as a conference paper at ICLR 2022
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex nonconvex-coneaww concave minimax problems. In International Conference on Machine Learning. pp. 6083-6093, 2020a.
Tianyi Lin, Chi Jin, Michael Jordan, et al. Near-optimal algorithms for minimax optimization. In Conference on Learning Theory, pp. 2738-2779, 2020b.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive ap- proximation for one-sided non-convex min-mat problems: algorithms and applications. IEEE Transactions on Signal Processing, 2020.
Luo Luo, Haishan Ye, Zhichao Huang, and Tong Zhang. Stochastic recursive gradient descent ascent minimax problems. Advances in Neural Information
for stochastic manconve--stronglyy- Processing Systems, 33, 2020.
Aleksander Madry. Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant to adversarial attacks. International Conference on Learning Representations, 2018.
Oren Mangoubi and Nisheeth K Vishnoi. Greedy adversarial equilibrium: An efficient alternative to nonconvex-nonccocan min-max optimization. In ACM Symposium on Theory of Computing, 2021.
Eric Mazumdar, Lillian Ratlif,, and S Shankar Sastry. On gradient- learning in continuous games. SIAM Journal on Mathematics of Data Science, 2(1):103-15))) 2020.
Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) zero-sum games. arXiv preprint arXiv: (eXiiv/901..000 00838, 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in
Neural Information Processing Systems, pp. 1823-1833, 2017.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for gans do actually converge? In International Conference on Machine Learning, pp. 3481-3490, 2018.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. In International Conference on Learning Representations, 2017.
Vaishnavh Nagarajan and J Zico Kolter. Gradient descent gan optimization is locally stable. In Advances in Neural Information Processing Systems, pp. 5591-5600, 2017.
Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, (5(1):229-25) 2004.
J Neumann. Zur theorie der gesellschaftsspeeee. Mathematische annalen, 100(1):295 320, 1928.
Maher Nouiched, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solving class of non-convex min-max games using iterative first order methods. In Advances in Neural Information Processing Systems, pp. 14934-1490 14942, 2019.
Dmitrii M Ostrovskii, Andrew Lowy, and Meisam Razaviyayn. Efficient search of first-order nash equilibria in nonconvex-concave smooth min-max problems. arXiv preprint arXiv:2002.07919 2020.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Weakly-convex-coneee min-max optimization: provable algorithms and applications in machine learning. Optimization Methods and Software, pp. 1-35, 2021.
L. J. Ratliff, A. Burden, and S. Sastry. Characterization and computation of local Nash equilibria in continuous games. In Allerton Conference on Communication, Control, and Computing, pp. 917-924, 2013.
Lillian Ratliff, Samuel A Burden, and S Shankar Sastry. On the characterization of local Nash equilibria in continuous games. IEEE Transactions on Automatic Control, (8):200112)33 2016.
12

---

Published as a conference paper at ICLR 2022
Julia Robinson. An iterative method of solving game. Annals of mathematics, pp. 1951.
Tuomas W Sandhlom and Victor RT Lesser. Coalitions among computationally bounded agents. Artificial intelligence, 94(1-2)999-137, 1997.
Christian Szegedy, Wojeiech Zaremba, llya Sutskever, Joan Bruna, Dumitru Erhan, lan Goodfellow, and Rob Fergus. Intriguing properties of neural networks. International Conference on Learning Representations, 2014.
Kiran K Thekumparampil. Prateek Jain, Pranceth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. Advances in Neural Information Processing Systems, 32: 12680-12691, 2019.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: A follow-the-ridge approach. In International Conference on Learning Representations, 2020.
Chongjie Zhang and Victor Lesser. Multi-agent learning with policy prediction. In AAAI Conference on Artificial Intelligence, 2010.
Guojun Zhang, Pascal Poupart, and Yaoliang Yu. Optimality and stability non-comyex-noo--oonaae min-max optimization. arXiv preprint 1 2020a.
Guojun Zhang, Kaiwen Wu, Pascal Poupart, and Yaoliang Yu. Newton-type methods for minimax 2020b.
optimization. arXiv preprint arXiv:2006.
Siqi Zhang, Junchi Yang, Cristóbal Guzmán, Negar Kiyavash, and Niao He. The complexity of nonconnex--tronnlyycoomeve minimax optimization. arXiv preprint arXiv:2103. 15888, 2021.
Renbo Zhao. A primal dual smoothing framework for max-structured nonconvex optimization. arXiv preprint arX1vv2003.04335, 2020.
13

---

Published as a conference paper at ICLR 2022
A DETAILED RELATED WORK
Nonconvex-Noncoonen Zero-Sum Games. The existing work on nonconvex -onnnneevennncceveee zero- sum games has generally focused on (1) defining and characterizing local equilibrium solution concepts and (2) analyzing the local stability and convergence behavior of gradient-base algorithms around fixed points of the dynamics. The concentration on local analysis stems from the inherent challenges that arise in nonconvex-noncooean zero-sum games from both 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 con-trivial periodic orbits that are antithetical to any type of global convergence guarantee in this class of games (Hsich et al. 2020: Letcher 2.21). Moreover, on constrained domains, it has been shown that finding even local equilibrium is computationally intractable (Daskalakis et al. 2021).
learning
A number of local equilibrium notions for non.nnecee zero-sum games now exist with characterizations in terms of gradient-based conditions relevant to gradient-based learning. This includes the local Nash (Ratiff 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-theeretic 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
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 eenoonnvex-noccoccvee 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.] (200aa), 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 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 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 sufficient timescale separation between the minimizing and maximizing players (Jin et al. 2020 Fiez & Ratliff 202I). 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.
descent-ascent in
The challenges of nonconvex-nonconee zero-sum games we have highlighted limit the types of provable guarantees that can be obtained and consequently motivate tractable relaxations including to emnconvex-concvee zero-sum games and the general framework we formulate in this work. Before moving on, we mention that from related perspective, line of recent work (Keswani al. 2020 Mangoubi& & Vishnoi 2021) in -encoonmee--onnocccvee.e 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 approximate local maximum of the cost function and the minimizing player is at an approximate local minimum of 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-Concare Zero-Sum Games. The past few years has witnessed significant amount of work on gradient- dynamics in manconvex-concal zero-sum games. The focus of existing work on nonconvex-concan zero-sum games has key distinctions from that in
14

---

Published as a conference paper at ICLR 2022
zero-sum games. Generally, the work on nonconvex-coneayy vero-sum games has analyzed dynamics on constrained domains, where typically the strategy space of the maximizing player is constrained to closed convex set and occasionally the minimizing player also faces constraint. In contrast, nonconvex-nonconean 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-nonconeat zero-sum games, the body of work on nonconvex-concat zero-sum games has focused on achieving stationarity of the game cost function f(-,-) or the best-response function o max, (:,y).
The structure present in nonconvex-comee concave zero-sum games has been shown to simplify the problem compared to nonconvex-nonconcave zero-sum games so that global finite-time time convergence guaran- tees are achievable. Thus, work in this direction has focused on improving the rates of convergence in terms of the gradient complexity to find c-approximate stationary points of f((::) or ((.), both with deterministic and stochastic gradients. Guarantees on the former notion of stationarity can be translated to guarantees the latter notion of stationarity with extra computational cost (Lin et al. 2020a).
For the the class of noncomvex--troonlly-coom
zero-sum games, a series of works design algorithms that are shown to obtain a-apprxximate stationary points of the functions f(: or (.)) with a
gradient complexity of ( in terms of c in the deterministic setting (Jin et al. 2020 Rafique al., [021]
Lu Lu 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 logarithmic dependence (Lin et al., 2020a). Lower bounds for this problem have also been established (Zhang et al. [ Li et al. 202T). In the stochastic nonconvex-strooglyy-ooo
problem, existing work has developed algorithms that are shown to obtain e-approximate stationary points of the function
(-) in gradient complexities of (c=r)) Rafique et al. 2021 Jin et al. 2020 Lin et al. 2020a) and
Ō(--)) (Luo et al. 2020 in terms of dependence.
concave problem, a number of algorithms with provable guarantees to eppproxxmmtee stationary points of the function f(---) have been shown with gradient complexities
In the deterministic
of 0( (Lu al. 2020), Ō(E-3.5) (Nouiehed et al. 2019). and ((-52.5 OOtrooskki et al. 2020 Lin et al. 2020b). Similarly, in this class of problems, there exist results on algorithms that guarantee convergence to an e-approximate stationary points of the function (-) with gradient complexities
Ö 6) (Rafique et al. 2021: Jin et al. 2020 Lin et al. 2020a) and Ō(E=a) (Thekumpaamppil et al. (019/Zhao 2020 Kong & Monteiro 2019 Lin et al. [020bb). Finally, existing results in the
stochastic setting for achieving an e-approximate stationary point of (-.) show gradient complexities
of () (Rafique et al. 2021) and ((c-)) (Lin et al. 2020a).
In this work, we build on the developments for nonconvex-come
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 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 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 simultancously 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 set of learning dynamics called iterated descent descent with policy prediction (IGA- PP) and show asymptotic convergence to Nash equilibrium. this set of learning dynamies, 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 x' and a cost function f((x", x that after
15

---

Published as a conference paper at ICLR 2022
incorporating the prediction becomes f( -V-------r-iii 2;")) To optimize the objective,
each player takes a first-order Taylor expansion of their cost function to give the augmented objective
f(r). - - -V- ~
- - -VV (x) V=if-((z);
Each player in the game simultaneously follows the gradient of their augmented objective which is given by
Vefi(z,, - -V -i V V-if-i(a),
This gradient computation is derived based on the fact that the assumed update of the other player V-,f-i(2f, 25 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.) (019). 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 f((z) " -V- x, ')). To derive the learning rule, an augmented objective is again formed by computing first-order Taylor expansion, but now the term V-sf-; x in the augmented objective is treated as dependent on the optimization variable so that the gradient of the augmented objective is given by
-ff(()(,"".)) Vafi - 7V -V-aaf V- --nnf V
Finally, to arrive 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
Vefa(af, 25 - -VV- 25 V V-ifi
While convergence results are given for LOLA, a follow-up work shows local convergence guar- antees to stable fixed points for IGA-PP and learning dynamics called stable opponent shaping (SOS) that interpolate between IGA-PP and LOLA (Letcher al., 2019). A related work derives learning dynamic based on the idea that the opponent selects a best-response to the chosen strategy (Fiez
cct al., 2020). The resulting learning dynamics can be viewed LOLA with the opponent selecting Newton learning rate. For
-onoooccce zero-sum games, local convergence guarantees to
only local Stackelberg equilibrium are given for this set of learning dynamics (Fiez et al. 2020).
is worth remarking that gradient-basee learning with opponent modeling is historically rooted in the general framework of consistent conjectural variations (see, e-g., Ba.ar & Olsder 1998 Chapter 4.6), 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 fixed number of gradient steps from the current parameter configurations of the generator and discriminator. The resulting discriminator parameters 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 gradient step on its objective. In our framework, for generative adversarial networks when the discriminator is modeled as performing T stsssss 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 Appendix F we present simple examples demonstrating that the extragradient method well as another variant called optimistic gradient descent ascent, do not converge for general nonconvex- nonconcave minimax optimization.
monoonocceeeeccc settings. In fact, in
Games with computationally bounded adversaries: There are also a few works in the game theory literature which consider resourcefcomputationalyy bounded agents. For example Freund et al. (1955)
16

---

Published as a conference paper at ICLR 2022
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 distinet 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 's theorem (see classical references differential equations such as asCCodingnon
Levinson 1955, Chapter 2) or Hartman 2002 Chapter IV.2)).
In numerical methods, such results 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.. .tt.nsonnoonn al. 201 Chapter 1.2). In particular, initial value problem is only considered well-posed if there continuous dependence on initial data. For instance, the simple scalar differential equation
(()) -v( + OSIST, v(0)
has solution ytt) = 1, yet the perturbed problem,
jie (4) = yv (1) + +1,10,5IS,, -,,,000, 3. (0) = +
has solution (t) = + ce - so that
(v(1) - y. (1) s [e], OS
If the maximum error 11ye-vl oo (much) larger than then the initial value problem is ill-oonitioned and any typical attempt to numerically solve such 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:
i(t) = (z, y(t)) - Uk+1 = yk + V f (x,
As such, the techniques for showing continuity of the solution of differential equation with respect to initial data other problem parameters (c.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 yr (xr) 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 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.
B PROOF OF RESULTS IN SECTION 3
Proof of Lemma 7 For any fixed z, we note that A(., 2) a deterministic algorithm. Consequently, it suffices to prove the lemma for a deterministic algorithm A(-). By chain rule, the derivative of [(, A(x)) is given by:
(8) where DA(x) E Rdixd is the derivative of A(.) Rd + R at x and (x, and (x, denote the partial derivatives of with respect the first and second variables
- DA(x)
DA(()) (alee)vv,fffe vyf(e,A(z)),
17

---

Published as a conference paper at ICLR 2022
respectively at (z, A(z)) An easy computation shows that
((x)) s [ [PAc) (VW
- -1+
This shows that f(z, Axx)) is (1 G'IG-Lipshhit Similarly, we have:
-
& [1, - A(z))) + HD0p: -od
For the first term, we have:
IV A(zi) - V22(2,;
< A(s)) V22(2 VV [[,( - -Volo
S < x2ll ||A(2)) A(r2) - [ G¹) | 52/l-
Similarly, for the second term have:
< (ataa///aaauuaao-aaaaaaa///////e
Attes// - |A
& (1.' + G') + GT)) ||m .2
This proves the lemma.
Proof of Lemma
Given any x and y, and any À such that A3 and Ejes(e) XÚ have:
g(v) max g, (y)
Σ
XvS,(1) 2 E A
(g)( x) 2L 11 y/13)
JE(K]
JES(X)
JES(x)
1
= gg(x)+
Σ
1,Vg,(2),v- x)
-- n|13,
2L
JES(#)
proving the lemma.
Proof of Lemma 3 We re-write (x) minimum value of ( L)-strong convex function Φx,..
as g L-weakly convex (Definition 2 and 2 || z²112 is differentiable and I -stronnlyy convex,
(x
min #'ER41
(x') g(x²)=
11 2X 1| - 2'11?
Then first part of (a) follows trivially by the strong convexity. For the second part notice the following.
1
min (x)) = min min g(x') +
2 || 2112
= min min g(x²) + 2x ||: 0'12
z'
min)g(x))
2'
Furthermore, we will show that arg ming (x) = arg ming ((x). Consider x" E argmin, g(x). We have that for any x,
1
gx = min g(z') + ||x x'12 g(x*) 2 9x(x*).
2X
This shows that x E argmin, (z) and hence argmin, g(x) C argmin (1))). Similarly, for any x² E argmiin 9x (z), we have:
1
(x(x*) s(fx(=")) + [x)(x*) x01 g((x(x")) 2 gx((((=')).
2X
18

---

Published as a conference paper at ICLR 2022
Algorithm 3: Estimating Moreau envelope's is gradient for postprocessing
Input: point 2; stochastic subgradient oracle for function g. error 6, failure probability
Find X such that g(x) + L|| - x|| I (ming g(x') + L||= x²11²) + iz using (Harvyy et al. 2019 Algorithm 1). return 2L - x).
Since x² E argmin, 9x(x), the above inequality is infact an equality and hence fx(x*) = x² So, gx(x*) y(=*) and hence x² E argmin, g(r) implying that argmin (x(x) S argmin, ((x). Thus arg min, (x(x) = arg ming g(x). For (b) we can re-write the Moreau envelope 9x as,
1
(x(2)
min g(x') +
11
1'11
21
1|
|
max(x" - -Ag(2')
2X
2
x 1 (xg()) 11.112) (z)
(10)
2
2
where (-)* is the Fenchel conjugation operator. Since L 1/A, using L-weak convexity of g, it is is
easy to see that )g(z')= + |=''|" 2 (1
A-)-stoongy convex, therefore its Fenchel conjugate would be term implies that (x (x + X(1 x())z))
(1-XL) -moothh (Kakade et al. 2009 Theorem 6). This, along with } -mmoothness of first quadratic ) -smooth, and thus differentiable.
1
For (c) we proceed as follows. Since (x)) = argming (2,= by first order KKT optimality conditions, we have that
(11) Further, from proof of part (a) we have that xx,=(2" (x') (1 AL) -tronngglyy--oovvee in x' and it is
(x) E A0g(2))
quadratic (and thus convex) in x. Danskin's 's theorem (Bertsekas) 2009 Section 6.11) thus implies
that for (xr = min (xx), we have that (g)(#) = (x (x)) Letting (x(x)= == -- (I (x)) E 0g(z), we have that:
min ||u|| S [[x(z)]| 1- - [V>x
(E))((x(a))
C PROOFS OF RESULTS IN SECTION
In order to prove convergence of this algorithm, we first recall the following result from (Davis & Drusvyatskiy 2018).
Theorem (Corollary 2.2 from (Davis & Drusvyatskiy 2018 Suppose g(-) is L-weakly convex, and ........
9 < G². Then, the output F of Algorithm 1 with stepsize n ग5F
satisfies:
[1V9 [+] 22 (o (2o) min, g(x) LG2g2
11+1
Proof of Theorem 7 Lemmas and 2 tell that g(x) is L-weakly convex and for any choice of
the stochastic subgradient g (x) is bounded in norm by G. Consequently, Theorem with the stated
choice of S proves Theorem
Proposition 1. Given a point x, an L-weakly convex function g and a G-norm bounded and a stochastic subgradient oracle g (i.e. given any point x', which returns stochastic vector such that E Eju] E Ög(2') and ||u]|| < G), with probability at least 1 - ō, Algorithm 3 returns a vector u satisfying uu - [gx(x)] < with at most of g.
G² log 1
queries to the stochastic subgradient oracle
19

---

Published as a conference paper at ICLR 2022
Proof of Proposition Let +
xx) == g(z') + L|| x'12 Recall the notation of Lemma
F. tr (x) = argmin zr. (a', 22 x) and gx (z) ming' 1 2..
(x', x). The proof of Lemma tells us that
V (1)
and also that | (c) x1 -
G Since tb * (1::) is a T-strongly convex
2L
and G Lipschitz function in the domain x' : 1 (x) x 27. (Harvey et al.
2019 Theorem
3.1) tells us that we can use SGD with G² log $ stochastic gradient oracle queries to implement Le
Step 1 of Algorithm with success probability at least 1 5, where Z== d- Simplifying this G log
e² 8).
expression gives us a stochastic gradient oracle complexity of O
D PROOFS OF RESULTS IN SECTION 4.3
2 Letting h(2, == EnEny (zgi(z), we note that V A)ll [Eee(h] \ 9: (z)]l S L(1 G*)² GL', where we used Lemmal and the fact that Σ, A4 S 1. On the other hand, [/Zz)(zz,)> [[CKEN]) Va(x))lI < kG(1 G*), where again used Lemma I Since Vxxh(z,A) 0, we can conclude that h is an L-gradient Lipschitz function with = L(1 G¹)² + GL' + kG(1 + G'). Consequently, g(z) maxxes h A), where = E R X 0, Eie | x }]. .... is E-wekkly convex and the Moreau envelope g 2z
Proof of Theorem
is well
defined.
Denote 9 F.
We now divide the analysis of each of iteration ma (x + L|| - 12.
of Algorithm 2 into two cases.
Case I, 1( < max (3r.)) 35/4: Since maxie[]] (1 S I( S (ax (1,)) - 32/4, we see that in this case g(xra) decreases monotonically by at least 32/4 in each iteration. Since by Assumption [ 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 I1, I( .r.) 2 max4e[]] ((rr)) 32/4: In this case, we claim that x, is an e-FOSP of g maX g (I). To see this, we first note that
g(xx)) - 32/4 - 9 20+1, x2)) S (min g(z) + L|I - x x21) +
g(x.) < min g[ xx)
+ ē.
x
(12)
Let x== == arg min, Haz; x.). Since is L-gradient Lipschitz, we note that xs) is L-strongly convex. We now use this to prove that x, is close to x;:
F g()) 2 Ix.
(0) & g(r)).)) + = ||x, x2:l <
26 1
=ill= S 0(2.ix.)
f(x.)
(13)
where (a) uses 12.. Now consider any 2, such that 4 /2/L S [ - -x,l1. Then,
((3) L 22 max ga (f) + L| x=11² = - x.) (0) g( 2 =13- x2,1
I
sE[R]
T.
f(x.) - ++ _/2 (1|e x.ll ||=, 21)) f f(x,) +
(14)
where (a) uses uses L-strong convexity of g xz) at its minimizer x;, (b) uses (2). and (b) and (c) use triangle inequality, B and 4v
/ 2/ < 20 xz
Now consider the Moreau envelope, g 1 (x) min Φ 1 an (x') where @ = = g(a') ) + L||x
21
22
212. Then, we can see that Φ - .z, (x') achieves its minimum in the ball {x' || - -xall= < 4 /
ē = 64L we get that, by [4 and Lemma a). Then, with Lemma b.c)) ànd
Vgg (sx))l < (2 & (x+)) 8V =
(15)
20

---

Published as a conference paper at ICLR 2022
Le., 2, is E-FOSP of By combining the above two cases, we establish that 32 E-FOSP.
"outer" iterations ensure convergence to
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 ming maxxes h(z, X) up to an accuracy of c/4.
Note that this step corresponds to solving
Option I, [Tekumparampil et al. 2019 Algorithm 2): Since the minimax optimization problem here
d-strongly-conves cononve and 2L-gradient Lipschitz, (Thekumparampil et al. 2019 Theorem tells us that this requires at most m gradient calls for each gi where,
6( Lm
8²
O L
S
S
m
(16)
2
Therefore the number of gradient computations required for each iteration of inner problem is o log" (!))
Option II, Cutting plane method (Lee al. 2015): Let consider u(A) min, (xx, X) Σ| - 1.1 which a I-Lipschitz, concave function of X. (Lee et al. 2015) tells us that we can use cutting plane algorithms obtain 7 satisfying u(²) 2 max u(A) using O (klog &Z gradient queries and poly(k log ( computation. The gradient of u is given by Vu(A)
(A), where x² (A) := argmin, Mxx, A) + Tl|l - 1. Since l(x,, A) + T. - 11,12 is a 37-smooth and L-strongly convex function in x² (A) can be computed up to ē error using gradient descent in O log iterations. If we choose = 2 pooly (k: L/14,, then Proposition 2 tells us that x (A) satisfies the requirements of Step (3) of Algorithm and the total number of gradient calls to each 9: most O (poly(k) log ! in each outer iteration of Algorithm 2
Proposition 2. Suppose h : Rd4 U R be such that ((,,)) j-stroonly convex for every X E U.
Mx,) :) is concave for every x E TR and h is L-gradiens Lipschitz. Let X be such that min, h(x, 2) 2 maxx min, 1(x, 2) and let x² (X) == argming 1(,,, X). Then, we have maxx 11(x" (A), A) S min, maxx 11x,, A) + c 4 e LDy. of
Va ve). where Du maxxi [l^r - -eel is the diameter
Proof of Proposition
From the hypothesis, we have:
2 h(2l* 11) h(x (2) 2 h(2=, h²xx,)) (xxx(1)) > ! "1o- -x= 2A)1.
where (x*, (x*, is the Nash equilibrium and the second step follows from the fact that X* argmax, h(x",\,, A) and the third step follows from the fact that x² =²²) argmin, h(x, 2). Con- sequently, have that ||a= x= =A)il < 22//u. Let À argmax, h(" (A), A). We now have
21

---

Published as a conference paper at ICLR 2022
that:
max (a22/((000 (2))
max min (/x, A) - h(22 A) - ,(x",1²)
1/20 1(x'(1),, (2), A) - 1(x (2)) (())))),)))))
(A), - -1x="
3 (Vih(> (2), - + >1 ==²11
(6)
3 ||VAK (2), I - - - Le
(6) (IVAME X + (()=*(A) - x²1) Due + Le
LDuV 28
Le 1
where (S1) follows from the fact that h(x² (A), is concave and x = argmin, h(z, X*), (S2) follows from the bound ||x- - x= (A)Il /2c/p, (Sx) follows from the L-gradient Lipschitz property of h, and the last step follows from the fact that V Vxh(x", ,*) = 0. This proves the proposition.
E PROOFS OF RESULTS IN SECTION 5
In this appendix, we present the proof' for the lemmas in Section 5 Recall the SGA update:
Vt+1 y/ + VV (x ve).
(17)
Therefore, the Jacobian of the T-step SGA update is given by
D = (T + V (x, Dye v/V yolo (x, with A(x, =y)()))))
(18)
E.1 PROOF THEOREM
Theorem 3 (General Case). Suppose for all E [n), Jj satisfies Assumption 7 Then, for any fixed
randomness 2, T Ttstep SGA is (1 + m,)T -Lisschitz and 4(p/ (1 + nm) -gradient Lipschitz.
Proof. Lipschitz of (z). We first show the Lipschitz claim. We have the following bound on the Jacobian of the update equation given in (8
DDv+ (z) || < [ V (I, 36 (()))) + V fa, ve (x))]l
<( + Db (x)] + tZ.
Since Dzo(=)= = 0, the above recursion implies that
f-1 [D)x S nL Ea+ S m1+
T=0
Gradient-Lipschite of y: (x). Next, we show the claimed gradient Lipschitz constant. As above, using the update equation in (18), have the following bound on the Jacobian:
[Dr+1 DDc+ (x2)
< (
+ (V D21(=2))1 + -
(e (((1)) - f (x2))
-
5(1 + +1)
Dy, mp |1 || +1 (x
<(1 + [[]+ Dy (21) - Dy (x2) + 41p + - - 22||-
The above recursion implies the claimed Lipschitz constant. Indeed,
[-1
(xx) Dye(x2)) s 4np (1
x2ll s 4(p/L) (1 + n x2ll-
22

---

Published as a conference paper at ICLR 2022
E.2 PROOF OF THEOREM 4
Theorem 4 (Concave Case). Suppose for all E [p], f3 satisfies Assumption 7 and [z(a, is concave
for any z. Then, for any fixed randomness 2, T T-sppp SGA is gradient Lipschitz.
and (p/ L) (1 + nLT)s.
Proof. Lipschitz of de (z). We first show the Lipschitz claim. Using the update equation in 18 we have the following bound on the Jacobian:
D <1(4 7 bf (()))) + (z,
< (z)] nL.
Since (x) = O, the above recursive implies that [Dye())) S TyLt.
Gradient-Lipschite of (x)). Next, we show the claimed gradient Lipschitz constant. Using the update equation in [8): we have the following bound on the Jacobian:
1D)+i(())) (1)+1((22))
< (I + V (x
Dyc(x2)) + 7 gef pa (((())))((x))))))))))) - yo f De (x2))) V f y (z2) (Dx
+ f - ff
< Dy((=1) - DD: + 7p(1 + | (x2) (l) - z + (1v) (((()))
< (Da(z1) - (x2)) + np(1 + ||= #2|1-
This recursion implies the following gradient Lipschitz constant:
1-1
(D)(z1) (x2)l & np Σ (1+ LL) x21 s (p/L) (1+ 1 x2ll.
(1+
7=0
E.3 PROOF OF THEOREM
Theorem 5 strongly-concavy Case). Suppose for all [n]. f, satisfies Assumption 7 Nand fy a-strongly concave for any x. Then, for any fixed randomness z. Ttstep SGA is n- L-psschitz and 4(p/ L) R² -g-grddient Lipschitz, where K L/a is the condition number.
Proof. Denote the condition number = L/a.
Lipschitz of ve (x)). We first show the claimed Lipschitz constant. Using the update equation 18 we have that
DD < [T + (
+ +ill vll (x, (x)))l
<( - Dy + In
Since Dzo(=)= 0, the above recursion gives the following bound:
f-1
(D)())) S nT.
Σ 11-not na)" S k.
Gradient-Lipschitz of y (z). Next we show the claimed gradient Lipschitz constant. Again, using the update equation, we have that
DDt+1((1) D <][(T + 1/ (,)
Dyr( + + / (e1, - V2 / yr (x2))
+ f(,, - /tal://wwaaalbo-///////////>a>aa
5(1 - Dy - - + mp(1
+ (y x2ll +lu((())) 11:0)--(00000 (x2)))
<(1 Dy (x2())) + 4npr² | a2ll
23

---

Published as a conference paper at ICLR 2022
This recursion implies that
(Du((z1) Dya(x22) & Anpk
Σ (1 r=0
1 x2ll s 4(p/L) 11/1201 x2ll-
E.4 PROOF OF THEOREM 6
Theorem (General Case). Suppose for all [m], Jj satisfies Assumption Then, for any fixed
seed 2, step SNAG is ((1 + nI//0" -Lipschitz and 50(p/L) T + n 2T -gradient Lipschitz.
Proof. Recall the SNAG update
V = y + (1 (v: - y1-1)
(19)
/++1 U. v/V (t) Dc).
(20)
Observe that the update equation for T-step SNAG implies that
Düe Dy: (1 (Dy Dy--1)
(21)
Dyc+1 (I + nV pocet) (z, Di) + v yu (x( ūt)
Lipschitz of (x)),, (x)). We first show the claimed Lipschitz constant. By the update equations in
we have that
Dyt+1 = (I + V (F, (Dy + (1 - () Dy + v7 yz fo()) (x, Mt). Denote 62 = Di Dy--1l and note that Dyo = Dy-1 0 so that 6o = 0. By the equation
above, we have that
ue+1 SnT. Dyell + + (1) 0)6, + 1
L Σ 8, + (1 LL 0)8, + nL.
In the following, induction prove that
& < (1 + L
(22)
It is easy to verify that this is true for the base case 60 = 0 < 1. Suppose the claim is true for all S then have that
0) nL/00 + +nL 8141 SnL Σ (1 mL/0 + +1+
r=1
LnL Σ (1 + /L/0) + + 0) 4L/))441
[[11 7L/0) + (1- mL/0) (1)))))=1//))+++++++++ (1
(1+1L/00**
This proves the induction claim. Therefore, by we have the following two bounds:
[D)( < Σ 8, S t(1 + mL/0)*
[x)x S(2 0)] (x) + (1 D) < 31(1 + nT//0)²
Gradient-Lipschhtzz of yr (1)). Next, we show the claimed gradient Lipschitz constant. For any fixed T2, denote w, = DDi (x)) Dy. (x2), we have
Wi+1 =(I V vy
)) (ure
(w( w.-1))
(VV (2) - V fa(t) (x(2)))
T
n ( vonfo(o (2 (21.
- V V fa v (x2)) + (1 (1 ()(()((22) Dy DD)-1(22)))
T2
24

---

Published as a conference paper at ICLR 2022
We note that upper bound the last two terms above follows:
Ti + T2 Smp(1<=1 æ2ll + (z)) (x
+ >np(1121 - Ø2 + ((())))))))))))))))((())))))))) (12))1(12)
224m (1 + T,/00) | - -22ll-
Therefore, let &e = ||0, - w ||+ and A = || - =2|1. we have the following:
G+1 SnL||wall + (1 + nL) (1 0)c₁ + 24npt (1 + nTL10)²
SnL Σ Sr + (1+ nL - 0)c + 24n (1 + mL/0)a A.
In the following, induction prove that
G 50(p/L) (1 nl/003 (t)).
(23)
It is easy to verify that this is true for the base case So 0. Suppose the claim is true for all then we have that
Se+1 250mp
71++1 (1 mL) (t)(t) + (1+
<0(p/L) [50e² (1 [1+nL/0)2(=1)
(1 11+12/0/==1 - + 24(1L/0) m (1 (1-0111-ttaatt (1+(+11) <0(p/L) [25t + + 20+- -- 0) +
+ 24t
<0(p/L) [500 (1 + 11/0))/0++) A (1 (0( 1).
This proves the induction claim. Therefore, by
23 we have that
[D)(( (22(22) ||w/|l S
S S (10 x2ll
E.5 PROJECTED GRADIENT ASCENT IS NOT GRADIENT-LIPSSHITZZ
Proposition 3. Consider fx, y) = xy for (x. y) E X x V, where X = (0, 10) and y [0. 1].
1-step projected gradient ascent given by:
(1(z) Py(uo + V,f vo))
0,
where 1) > 1/10 is not a gradient-Lipschite algoritim..
Proof. We see that y1 (x) min(1, qι) and f(x yı (x)) x min(1, For n 11/10, that f(z, y1 (x)) is not gradient-Lipschitz at x 1/n E (0, 10).
F ON NONCONVERGENCE OF EXTRAGRADIENT METHOD AND OPTIMISTIC GRADIENT DESCENT ASCENT (OGDA)
In this section, we show that there exist cunconvex-nonconeat problems where the extragradient method and OGDA get trapped in limit cycles. While the example construct is a quadratic function that is not bounded over 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 E R:
1 2 axx + buy 7ay² = (x
a
b
f(x v) =
v)
(24)
b
25

---

Published as a conference paper at ICLR 2022
Denote = (z, = (-6 b) a) and define:
F(z) = V (2f(z,y) ( of(zz)))
(-
b
x 11
=
a
Let the eigenvalues of matrix & be Å1, A2. We know they satify the characteristic equation (A
a)²+ + b² 0. By Vieta's formulas, know that A + A2 2a, λ1d2 a² 6². This justifies the following proposition.
Proposition For any complex number E there exist a, b s.t. the eigenvalues of & are e and &. Here ē is the complex conjugate of
Proof. Let c p qi for some p. g E R. we can choose a = (c+ 2)/2 =p. =v a² = -g. is easy to check such matrix has eigenvalues e and c.
F.1 EXTRAGRADIENT METHODS
The extragradient algorithm (Korpelevich 1976) uses the following update:
1/+1/2 =2 F
1++1 =2 1---10 -1/F((+11/))
For the case of quadratic function specified by (24). this update is equivalent to
2t+1 = -/- -/0)) = (1 rpt + x}²
Clearly, the eigenvalues of matrix (1=) are simply (1-1d1+1) X3) and 11-nd2++ X2). Proposition 5. For the extragradient algorithm with any fixed learning rate n, there exists quadratic function, and appropriate initial points such that the extragradient algorithm trapped in limit cycle.
Proof. For any given 8 E 2m. we can simply pick A E C to the solution of equation 1 - 1- + 2 e00 This is quadratic equation of X1, which always has nonzero complex roots. For X2 = Å1, we verify that 1a + 2) = e-18 Finally, by Proposition 4 we know that there exists choice of b such that, the two eigenvalues of (I 17 + 17 @2) are precisely e and e
(Du #1 0222, where and 22 are the two
If the initial point
can be decomposed as
yo
yo
cigenvectors corresponding to eigenvalues
a and A2 respectively, we see that the extra gradient
algorithm follows the trajectory
Ftt
are 101 21 agg-iit 101 22, thereby getting trapped in limit
y/
cycle.
F.2 OPTIMISTIC GRADIENT DESCENT ASCENT (OGDA)
The OGDA algorithm (Daskalakis & Panageas 2018a has the following update:
Zt+1 2, F (zx) (f(x.1)).
(Daskalakis & Panageas 8018a|/Section 4.1] presents 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
2++1
I 2n
17
21
Zt
1
21-1)
[ - 2
1/
There are four eigenvalues for the matrix
Two of them μl, P2 are eigenval-
ues the matrix (1-2
2n/A1
md1 ) while the other two μ3, M4 are eigenvalues of the matrix
(1 2112 1722)
0 where dj and X are the eigenvalues of +.
26

---

Published as a conference paper at ICLR 2022
Proposition 6. For the OGDA algorithu 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 so that the resulting eigenvalues fi,
1 27²1
and j43, M4 of [ 2m
nd2
112 of
satisfy | = |ps| and l =
1
0
0
so that we have f1 is root of u² - (1 -2nni) + n7d1 = O. We note that ur2 is the other root of the above equation. We have that:
< 1. Let us first fix μ1 e and choose 1711
Ma (ا11)
2p1
|M1 1|
(cos 0 - 1)2 + sin? (2 0 - 1)2 + sin" 0
1nd11
12p1
Therefore, for any 0 E (0, (0,z/4], we have |nA1| < 1. That is u2 < 1, since |Mi| 1, we have
|22| < 1. By symmetry, we know by choosing X2 X1, the two eigenvalues of 1 - 21
11/2)
are μl3 - jii and μ44 - μi2. sum, we have proved that for any 0 E (0, π 7/4,. and any learning rate n
there exists a choice of a, such that the four eigenvalues of (
[ ('777 20y
0 are e-10 .d
where |d'| |2"| < 1. If the initial points E; is the eigenvector corresponding to eigenvalue pi then the iterates and 2t-1 are given by converges to are" 21 + age i0tt 23, proving that
21 have the decomposition Ei= a where 20
2t
E a.,zz As t + co, -
2t-1
OGDA iterates get trapped in limit cycle and neither converge to a single point nor escape to infinity.
G ADDITIONAL EXPERIMENTS AND DETAILS
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 we allow the discriminator to sample uniformly from the interval [-0.5, 1] and consider the discriminator performing T = 100 (Figure (bb) and T = 1000 (Figure 5ch 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 8 0 to recreate the underlying data distribution using our algorithm which descends V/ A(0)) or the algorithm that descends (o ((0). 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 simultancous 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 we see that with this distribution of initializations for the diseriminator and T 1000 gradient ascent steps, the generator is able converge the optimal parameter of 0" = 0 to recreate the underlying data distribution using our algorithm which descends (0, A(o)) or the algorithm that descends (o,(0,AA0)) Thus, while with not observe convergence to the optimal generator parameter, with 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 ff A(l)) and (0, A(()) are nearly equivalent.
100 we did
We remark that 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 the window around the mean is not visible.
27

---

Published as a conference paper at ICLR 2022
vef(O,A(0))
Vf(0,A(0))
1.0
1.0
0.5
0.6
0.4
0.0
-0.5
0.0
600
800
lterations
Iterations (c)
(b)
Figure 5: Dirac-GAN: Generator parameters while training using framework with and without optimizing through the discriminator where between each generator update the discriminator samples an initial parameter choice uniformly random from the interval [-0.5, 1] and then performs = 100 (Figure and = 1000 (Figure 5ch steps of gradient ascent.
(b)
(c)
(d)
(c)
(f)
(a) Real Data
g
(h)
Figure 6: Mixture of Gaussians: Figure 6a shows the real data distribution and Figures 6b 6k show
the final generated distributions after 150k generator updates from 10 separate runs of the training procedure described in Section 6 generator distribution closely resembling the underlying data distribution.
using gradient ascent for the discriminator. Each run recovers
Mixture of Gaussians. We noted in Section that repeated experiment training generative adversarial network to learn 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 66 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 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 (31, ;22 (0.99, 0.999) and learning rate 7/2 0.004 and the generator learning rate was 7/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 out of the 10 runs the generator did not leam the proper distribution. This is to say that 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 shown in Figure 7
28

---

Published as a conference paper at ICLR 2022
(b)
(c)
(d)
(h)
(a) Real Data
(e)
(
(g)
Figure 7: Mixture of Gaussians: Figure 7 shows the real data distribution and Figures 7b show the final generated distributions after 150k generator updates from the 7 out of 10 separate runs of the training procedure using Adam optimization for the discriminator that produced reasonable distributions.
Adversarial Training. We now provide some further background on the adversarial training ex- periment 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 SSzegedy et 2014) Kurakin et al. 2017; Madry et al. 2018). A common approach toward remedying this vulnerability is by training the classification model against adversarial perturba- tions. Recall from Section that given a data distribution D over pairs of examples x E Rdd and labels y E [k]. parameters 0 of neural network, set S Fd of allowable adversarial perturbations, and loss function - dependent on the network parameters and the data, adversarial training amounts to considering minmax optimization problem of the form minø E<..))>> [maxses E(0, x + 8, v)].
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 T-sseps 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 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 7 7'steps of regular gradient ascent (not using the sign of the gradient and without projections).
For the adversarial training experiment considered in Section against various other attacks. Recall that the models were training using T 10 steps of gradient ascent in the inner optimization loop with learning rate of 1/2 4. To begin, evaluated the trained models against gradient ascent attacks with a fixed learning rate of 7/2 = and number of steps T' E (5, 10, 20, 40). We also evaluated the trained models against gradient ascent attacks with a fixed budget of T = 40 and various choices of T and 7/2. These results are presented in Figure 9 Finally, we evaluated the trained models against attacks using the Adam optimization method with fixed budget of T T7p- 0.04 and various choices of T and 172. These results are presented in Figure I0 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 in training when of comparable computational power and also that it improves robustness against attacks of greater computational power than used during training.
also evaluated the trained models
In Section 6
we showed the results of evaluating the gradient norms || |/,, A(0)) as 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 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, then sampled 100 minibatches of data and
29

---

Published as a conference paper at ICLR 2022
GA Altack: 5 Inner Steps
GA Attack: 10 Inner Steps
GA Attack: 20 Inner Steps
GA Attack: 40 Inter Steps
95
85
70
80
Accuracy
75
60
80
50
60
55
50
100
25
75
100
50
100
25
75 Training Egochs
100
Training Epochs
Training Epochs
Training Epochs
Standard Training
Vof(8.A(0)))
Vi(o.
Test accuracy during the course of training against gradient ascent attacks with fixed learning rate 122 = and the number steps T E (5, 10, 20, 40}.
Figure 8: Adversarial Training:
GA Allack: (Steps, (40:
GA Allack: (Steps, LR]: (20,
GA Allack: (Steps, LR):
95
GA Atlack: (Steps, LRI: 20)
90
90
85
85
80-
80
80
75
75
75 Training Epochs
50
100
25
75
100
25
50
75
100
25
50
75
100
Training Epochs
Training Epochs
Training Fpochs
Standard Training
Vgf(0,,(01))
v((0)
Figure 9: Adversarial Training: Test accuracy during the course training against gradient ascent attacks with fixed attack budget of Tn2- 40 where T is the number of attack steps and 7/2 is the learning rate (LR).
Adam Atterk:: (Wreos (00, 0.003)
Maa Attacc: LBC: 0.002)
Adamm Attect: iSteps, 0.00!)
Attact: (Steps, LBV: 0.02)
90
90
885
8.5
8.5
80
90
75
25
75 Training Epochs
50
100
25
50
75
100
25
50
75
100
25
50
75
100
Training Egechs
Training Epochs
Training Epochs
Standard Training
7.f(e.A(01)
Vfte. A(8))
Figure 10: Adversarial Training: Test accuracy during the course training against Adam opti- mization attacks with fixed attack budget of Tn2 0.04 where T is the number of attack steps and 772 is the learning rate (LR).
for each minibatch performed T E (20,30, 40, 50, 60, 70, 80, 90, 100} steps of gradient ascent with learning rate 7/2 = 4 (the learning rate from training) and then computed the norm the gradient (0, A(0)) 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 IIa the mean of the norm of the gradients over the sampled minibatches deviation around the mean. We also repeated this procedure using 72 and show the results in Figure 1 from which similar conclusions can be drawn.
shown with the shaded window indicating standard
30

---

Published as a conference paper at ICLR 2022
102
Training Epochs=25
Trining Epochs=25
Gradient Norm
10a
Training Epochs=50
Gradient Norm
Training Epochs-50
Training Epochs-75
Training Epochs-75
Training Epochs-100
Training Epochs-100
10
10
10
10a
10-
Inner Optimization Steps
Inner Optimization Steps
Figure 11: Adversarial Training: [V A(0) as function of the number of steps T taken by the gradient ascent algorithm A evaluated at multiple points in the training procedure. Figure Ila corresponds to using 7/2 in the gradient ascent procedure and Figure [lb corresponds to using T22 = the gradient ascent procedure.
Layer Type
Shape
Convolution ReLU
x 20
Max Pooling
2 2
Convolution + ReLU
x 5 x 20
Max Pooling
Fully Connected + ReLU
800
Fully Connected + ReLU
500
Softmax
10
Table 1: Convolutional neural network model for the adversarial training experiments.
Finally, we provide details on the convolutional neural network model for the adversarial training experiments. In particular, this model is exactly the same considered in (Nouiehed et al.) 2019) and we reproduce it in Table
Experimental Details. For the experiments with neural network models used Nvidia GeFFrce GTX 1080 Ti GPU and the PyTorch higher library(Deleu et al. 2019) to compute V'' In total, rumning all the experiments in the paper takes about half of 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).
31


Reviews:
[{"review_id": "VEwsLemjvhF", "reviewer": "Reviewer_WVv5", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Firstly, I would like to mention some technical details in the proofs of the primary appendix sections.\n\nIssue #1.[Lemma 2] In the lemma about the max of L-weak convex functions and its subgradient, the proof shows only the inclusion not the completeness. More precisely, from the proof I can see why the linear combinations of gradients correspond to subgradients of the max-functions. On the other hand, this does not show that all subgradients can be written in this form? \n\nPlease provide a new proof OR correct the statement and explain why a refined statement suffices for our task. A priori, I believe that the result should be correct as a generalization of Danskin's Theorem.\n\nIssue #2.[Lemma 3] The statement of the lemma is correct since they are folklore truths for proximal descent. HOWEVER, the proof that you provide has some mathematical flaws. \nExample: You say that min g(x) = min g_\\ell(x) and then you say that  \" Thus argmin g(x) = argmin g_\\ell(x)\". In general this is not correct for two function f_1,f_2 (i.e f_1(x)=|x|,f_2=|x-1|)\nThe only way that I know to show the result is via the facts that $argmin g(x) = fixpoints(proxGD)$ and \n$argmin g_\\ell(x) = fixpoints(proxGD)$\n\nSimilarly for item (c), I was not able to parse the argument. Could you please explain in a list the statements of the proof \n\nMAIN CONTRIBUTION:\n\nI really like the idea of the \"smoothed adversary\" as a refined benchmark. i agree that a better framework would be if we \"constrain\" the opponent in order to examine if it is possible to find efficiently a good solution. I appreciate the model and the conceptual, \"easily\"-understandable results and the well-written part of main paper. I don't like the fact that authors do not explain(hide) explicitly that the smooth adversaries have not memory in comparison with its opponent. If this is correct, I would appreciate some addition in the text which will explain that. Finally, there are two issues about the results:\n(1) we don't have convergence to a Nash equilibrium or local \\eps-Nash equilibrium but to a point which is biased against the \"inner\" player. (2) The novelty of the results is limited since the algorithmic concepts ,that are used, are somehow blackboxes. On the other hand, I understand that the main idea is to explain why the case of \"smooth adversaries\" is a tractable case.\n\nIn general I would like some answers in my \"complaints\"/ \"issues\" that I raised. I believe strongly that with a satisfying answer I will increase happily my score.", "summary_of_the_paper": "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,\nthe 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.", "summary_of_the_review": "While there are some typos and restriction, I strongly appreciate the model design which consists the backbone of the paper. Shortly describing, I like the main message of the paper even if there are main details that should be clarified and corrected to express the exact result that can be derived from the paper.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "TKYnWKIumXl", "reviewer": "Reviewer_9PEU", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "The topic of the paper is quite relevant in the community. The main idea makes sense and the experimental results are quite impressive. \n\n\nTechnical Issue:\n- I am afraid that the gradient of an algorithm is not well-defined. How do you compute the gradient? Probably the paper assumes that the algorithm trains a neural network and its gradient is that of the network. Please clarify it. ", "summary_of_the_paper": "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. ", "summary_of_the_review": "The paper is good enough and it is supported by experimental results.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "ROd_O_KDGhE", "reviewer": "Reviewer_BUCz", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "1) Their algorithms need $O(\\epsilon^4)$ gradient queries. It would be great if the authors can clarify that is this tight bound or can we achieve better complexity and if we can what would be a proper approach.\n\n2)The setting is novel and interesting from a practical and theoretical point of view.\n\n3)Author motivates the subject from a theoretical and practical point of view. \n\n4)In the introduction, the author reviewed the previous works carefully.\n\n5)The authors successfully provide simulation results for their algorithm.\n\n6)The paper is well-organized and well-written.\n\n7)the code is included.\n", "summary_of_the_paper": "This paper focuses on solving minimax optimization when the maximization oracle has a limited amount of computation power and can not compute the max exactly. They provide SGD based and proximal algorithms and analyze them for weakly convex function.", "summary_of_the_review": "1) Their algorithms need $O(\\epsilon^4)$ gradient queries. It would be great if the authors can clarify that is this tight bound or can we achieve better complexity and if we can what would be a proper approach.\n\n2)The setting is novel and interesting from a practical and theoretical point of view.\n\n3)Author motivates the subject from a theoretical and practical point of view. \n\n4)In the introduction, the author reviewed the previous works carefully.\n\n5)The authors successfully provide simulation results for their algorithm.\n\n6)The paper is well-organized and well-written.\n\n7)the code is included.\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "JukexQm5UHa", "reviewer": "Reviewer_nxeu", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Some comments:\n\n1) The authors should provide the gap between the original nonconvex-nonconcave minimax problem $\\min_x max_y f(x,y)$ and the obtained nonconvex-concave minimax problem $min_x max_{i\\in [k]}f(x,\\mathcal{A}_i(x))$ in both the theoretical and experimental aspects. \n\n2) Assumption 1 given in the paper may be not mild. So the authors should detail whether these assumptions are used in the existing methods.\n\n3) Recently many existing methods have studied the nonconvex-concave minimax problems. The authors should point the differences between the nonconvex-concave minimax problem (1) given in the paper and the generic nonconvex-concave minimax problems studied in the existing methods. \n\n4) The authors study the convergence properties of the proposed algorithms to solve the nonconvex-concave minimax problem (1) given in the paper. Compared the existing studies on the generic nonconvex-concave minimax problems, what are challenges? \n", "summary_of_the_paper": "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. ", "summary_of_the_review": "Overall, I like this paper. I hope the authors can deal with the above comments. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper addresses the problem of non-convex non-concave min-max optimization under the perspective of application of smoothed algorithms between two opponents.
The paper examines 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. Convergence guarantees proposed were sound and experimental results on generative adversarial networks and adversarial training demonstrate the efficiency of the proposed algorithms.
Decision: Accept (Poster)