A Provably Convergent and Practical Algorithm for Min-Max Optimization with Applications to GANs
Authors: Oren Mangoubi
Sushant Sachdeva
Nisheeth K Vishnoi
Venue:  (2021)
Keywords: min-max optimization
GANs

Abstract: We present a first-order algorithm for nonconvex-nonconcave min-max optimization problems such as those that arise in training GANs.  Our algorithm provably converges in $\mathrm{poly}(d,L, b)$ steps for any loss function $f:\mathbb{R}^d \times \mathbb{R}^d \rightarrow \mathbb{R}$ which is $b$-bounded with ${L}$-Lipschitz gradient. To achieve convergence, we 1) give a novel approximation to the global strategy of the max-player based on first-order algorithms such as gradient ascent, and 2) empower the min-player to look ahead and simulate the max-player’s response for arbitrarily many steps, but restrict the min-player to move according to updates sampled from a stochastic gradient oracle. Our algorithm, when used to train GANs on synthetic and real-world datasets, does not cycle, results in GANs that seem to avoid mode collapse, and achieves a training time per iteration and memory requirement similar to gradient descent-ascent.


Under review as a conference paper at ICLR 2021
A PROVABLY CONVERGENT AND PRACTICAL ALGO- RITHM FOR MIN-MAX OPTIMIZATION WITH APPLICA- TIONS TO GANS
Anonymous authors Paper under double-biee blind review
ABSTRACT
We present a first-order algorithm for nonconvex-nonconcan min-max optimiza- tion problems such as those that arise in training GANs. Our algorithm provably converges in poly(d, L. b) steps for any loss function f Rd x Rd + R which is b-bounded with L-Lipschitz gradient. To achieve convergence, we 1) give a novel approximation to the global strategy of the max-player based on first-order algorithms such gradient ascent, and 2) empower the min-player to look ahead and simulate the max-player response for arbitrarily many steps, but restrict the min-player to move according to updates sampled from a stochastic gradient oracle. Our algorithm, when used to train GANs on synthetic and real-world datasets, does not eycle, results in GANs that seem to avoid mode collapse, and achieves training time per iteration and memory requirement similar to gradient descent-ascent
INTRODUCTION
We consider the problem of min-max optimization minzeR max [z, y), where the loss func- tion ff may be nonconvex in z and nonconcave in Min-max optimization of such loss functions has many applications machine learning, including to GANs (Goodfellow et al., 2014) and adversarial training (Madry et al.) 2018). In particular, following Goodfellow et al. (0114), GAN training can be formulated min-max optimization problem where æ encodes the parameters of "generator" network, and y encodes the parameters of "discriminator" network. Unlike standard minimization problems, the min-max nature of GANs makes them particularly difficult to train (Goodfellow 2017), and has received wide attention. A common algorithm solve these min-max optimization problems, gradient descent ascent (GDA), alternates between stochastic gradient descent steps for æ and ascent steps for y The advantage of GDA is that just requires first-order access and each iteration is efficient in terms of memory and time, making it quite practical. However, as many works have observed, GDA suffer from issues such cycling (Arjovsky & Bottou 2017) and "mode collapse" (Dumoulin et al. 2017 Che et al. 2017 Santurkar et al. 2018).
Several recent works have focused on finding convergent first-order algorithms for min-max opti- mization (Ratique et al., 20188) Daskalakis et al. 2018: Liang & Stokes 2019 Gidel et al.) 22196] | Nouiehed al. 2019 Lu et al. 2020; Lin al. 2020 Mokhtari et al. To19|Thekumparampp et 2019 Mokhtari et al. 2020). However, these algorithms are also not
Mertikopoulos | 2019
min-max problems. The challenge is that min-max optimization generalizes nonconvex minimization, which, in general, is intractable. Algorithms for nonconvex minimization resort to finding "local" optima or assume a starting point "close" to global optimum. However, unlike minimization problems where local notions of optima exist (Nesterov & Polyak| 2006). it has been challenging to define a notion of convergent points for min-max optimization, and most notions of local optima considered in previous works (Daskalakis & Panageas 2018 [in et al. 2020 Fiez et al.) 2019) require significant restrictions for existence.
guaranteed to converge for general munconvxx-nonconee
Our contributions. Our main result is new first-order algorithm for min-max optimization (Al- gorithm I that for any & > O, any conconvex-nonconcavy loss function, and any starting point, converges poly L, 1/e) steps, if / b-bounded with L-Lipschitz gradient (Theorem 2.3
In practice, gradients steps often replaced by ADAM steps; ignore this distinction for this discussion.

---

Under review as a conference paper at ICLR 2021
A key ingredient in our result is approximation the global max function max2cR4 far 2). Unlike GDA and related algorithms that alternate between updating the discriminator and generator in incremental fashion, our algorithm lets the discriminator run a convergent algorithm (such as gradient ascent) until if reaches a first-order stationary point. We then empower the generator to simulate the discriminator's response for arbitrarily many gradient ascent updates. Roughly, each iteration of our algorithm, the min-player proposes a stochastic (batch) gradient update for æ and simulates the response of the max-player with gradient ascent steps for y until reaches a first-order stationary point. If the resulting loss has decreased, the updates for x: and are accepted; otherwise they are only accepted with small probability (a la simulated annealing).
The point (a*, (e")"") returned by our algorithm satisfies the following guarantee: if the min-player proposes a stochastic gradient descent update to x², and the max-player is allowed to respond by updating y" using any "path" that increases the loss at rate of at least e - with high probability, the final loss cannot decrease by more than e. See Section 2 for our convergence guarantees, Section + for the key ideas in our proof, and Appendix C for comparison to previous notions of convergence.
Empirically, we apply our algorithm for training GANs (with the cross-entropy loss) on both synthetic (mixture of Gaussians) and real-world (MNIST and CIFAR-10) datasets (Section 3). We compare our algorithm''s 's performance against two related algorithms: gradient/ ADAM descent ascent (with one or multiple discriminator steps). and Unrolled GANs (Metz et al. 2017). Our simulations with MNIST (Figure 1 and mixture of Gaussians (Figure 2 indicate that training GANs using our algorithm can avoid mode collapse and cycling. For instance, the Gaussian mixture dataset, we found that by around the 1500'th iteration GDA learned only one mode in 100% of the runs, and cycled between multiple modes. In contrast, our algorithm learned all four modes in 68% of the runs, and three modes in 26% of the runs. On 0-1 MNIST, we found that GDA tends to briefly generate shapes that look like a combination of O's and 1's, then switches between generating only I's and only O's. In contrast, our algorithm seems to learn to generate both O's and I's early on and does not stop generating either digit. GANs trained using our algorithm generated both digits by the 1000'th iteration in 86% of the runs, while those trained using GDA only did so in 23% of the runs. Our CIFAR-10 10 simulations (Figure 3) indicate that our algorithm trains more stably, resulting in a lower mean and standard deviation for FID scores compared to GDA. Furthermore, the per-step computational and memory cost of our algorithm is similar to GDA indicating that our algorithm can scale to larger datasets.
Related work
Guaranteed convergence for min-max optimization. Several works have studied GDA dynamics in GANs (Nagarajan & Kolter 2017 Mescheder et al., 2017 Li et al.) 2018 Balduzzi et al. 2018
Daskalakis & Panageas 2018 Jin et al. 2020) and established that GDA suffers from severe limitations: GDA can exhibit rotation around some points, or otherwise fail to converge. Thus, expeot global convergence guarantees for GDA. To address these convergence issues for GDA, multiple works have proposed algorithms based on Optimistic Mirror Descent (OMD), Extra-gradient method, or similar approaches (Gidel et al., 2019b Daskalakis alkiis et al. 2018 Liang & Stokes 2019 Daskalakis & Panageas, 2019 Mokhtari et al. 2019 2020). These algorithms avoid some of the pathological behaviors of GDA and achieve guaranteed convergence in poly (s. log(1// iterations where & is the condition number of f. However, all these results either require convexity/concavii assumptions on f. which usually do not hold for GANs, or require that the starting point lies in a small region around an equilibrium point, and hence provide no guarantees for an arbitrary initialization. Some works also provide convergence guarantees for min-max optimization (Nemirovski & Yudin 1978, Kinderlchrer & Stampacchia 1980 Nemirovski 2004, Rafique et al., 2018 Lu et al. 2020
Lin et al. 2020; Nouiched et al.) [219 Thekumparampil al. 2019 However, they require f to be concave in y. again limiting their applicability.
As for conconvex-nonconncae nonconcave min- finite-step GDA, under the assumption that the underlying continuous dynamics converge to a local min-max optimum (this assumption may not even hold for f that is bi-linear). Jin al. (2020) present a version of GDA for min-max optimization (generalized by Fiez et al. (2019) such that if the algorithm converges, the convergence point is a local min-max optimum. Both these results require that the min- min-player use a vanishingly small step size relative to the max-player, resulting in slow convergence. Wang et al. (2020) present an algorithm that can converge for eenccnnveee functions, but requires the initial point to lie in a region close a local min-max optimum (such optima are not guaranteed to exist). In contrast to the above works, our algorithm is guaranteed to
min-max max optimization. Heusel et al. (0117) prove convergence of
2

---

Under review as a conference paper at ICLR 2021
converge for any eencoonee--noncoecvee loss, from any starting point, in poly(d, 1/2) steps, if f is b-bounded with L-Lipschitz gradient.
Greedy paths. The paths along which the max-player is allowed to make updates in equilibrium definition are inspired from the work of Mangoubi & Vishnoi (2020), which gives a second-order algorithm for min-max optimization. The "greedy paths" considered in their work are defined such that at every point along these paths, ff is non-decreasing, and the first derivative of f is at least E or the 2nd derivative is at least Ve. In contrast, we just require a condition on the first derivative of along the path. This distinction gives rise to a different notion of equilibrium than the one presented in their work. The first-order condition on the paths crucially also results in our algorithm being applicable to machine learning settings where only first-order oracles are available, because unlike Mangoubi & Vishnoi (2020), traversing such a path only requires first-order access to f.
Training GANs. Starting with Goodfellow et al. (2014), there has been considerable work to develop algorithms to train GANs. One line of work focuses on modifying the loss to improve conver- gence (Arjovsky et al.] 2017; Bellemare et al. 2017] Lim & Yel 2017, Mao et al.) [017 Salimans ct al. 2018 Metz et al. 2017). Another line of work regularizes the discriminator using gradient penalties or spectral normalization (Gulrajani et al. 2017 Kodali et al., 2017 Miyato et al. 2018).
Metz et al. (017)) introduced Unrolled GANs, where the generator optimizes an "unrolled" loss function that allows the generator to simulate fixed number of discriminator updates. While this has some similarity to our algorithm there are two important distinctions: 1) the discriminator in Unrolled GANs may not reach first-order stationary point, and hence their algorithm does not come with any convergence guarantees, and 2) unlike our algorithm, the implementation of the generator in Unrolled GANs requires memory that grows with the number of discriminator steps, limiting its scalability. We observe that our algorithm, applied to training GANs, trains stably and avoids mode collapse, while achieving a training time per iteration and memory requirements that are similar to GDA, and much lower than Unrolled GANs (Metz et al. 2017) (see also the discussion in Section 5}
Remark 1.1 (Loss functions in GANs), Loss functions f f Rd x Rd + IR which take bounded values on Bd Rdd arise in many GAN applications. For instance, GANs with mean- sqaa-e error loss Mao et al. (2017) have uniformly bounded f. GANs with cross entropy loss Goodfellow et al. (2014) have J uniformly bounded above, and Wasserstein GANs Arjovsky al. (2017) have loss function f2r,y) which is bounded above as a function of y and is uniformly bounded below.
THEORETICAL RESULTS
We consider the problem min, maxy f(x, v), where y, E Rd, and f' function Rd RRd + R. We consider / that is an empirical risk loss over m training examples. Thus, we have ʃ - m Eieim) Si, via a randomized oracle F such that E[F]= = f. We call such an oracle stochastic zeroth-order oracle for f. We are also given randomized oracles Gas G, for Va.f, VyJ, such that [ = V and E[GG)] Vy.f. We call such oracles stochastic gradient oracles for f. In practice, these oracles are computed by randomly sampling "batch" " B C [m]] and returning F = 1/1B1 EiEn fa. G2 = 1/18) EiEB V.fi, and Gy = 1/1B1 ΣIE Vyfi.
and are given access
For our convergence guarantees, we require bounds on standard smoothness parameters for functions f:
such that for all and all x, y, we have [f((x, y)1 S b, and L such that fa, y) - V fa',", .'''2' S L||x- x' 212 + Llyy - y' Such smoothnes//Lipshhie bounds are standard in convergence guarantees for optimization algorithms (Bubeck) [017 Nesterov & Polyak] 2006 Ge et al. 2015), and imply that is also continuous, b-bounded, and L-gradient-Lipschiiz.
Our algorithm described informally in Algorithm I and formally as Algorithm 2 in the Appendix.
Intuition for the algorithm. To solve the min-max problem, the max-player would ideally find the global maximum max; f(x, 2). However, since f may be nonconcave in y, finding the global maximum may be computationally intractable. To get around this problem, roughly speaking, in our algorithm the max- max-player computes its update by running gradient ascent until it reaches a first-order This allows our algorithm compute an approximation L. (xx y) = fxx s/) for the global maximum. (Note that even though max; f 2) is only function of Le may depend on both x and the initial point y.)
e-stationary point y'. that is, point where VV fz, y')ll
3

---

Under review as a conference paper at ICLR 2021
Algorithm 1 Algorithm for min-max optimization
input: A stochastic zeroth-order oracle F for loss function f: IR x Rd - IR, and stochastic gradient
oracles Gg for V=J. and Gy for y.f. An initial point (z. y), and an error parameter E. output: A point (a",
hyperparameters: Tmax (maximum number of rejections); Ti (hyperparameters for annealing): ADAM hyperparameters
Set r 0, +-0
while S Tmax do
Sold F),,y), i i+i+1
Set Gz + Gzt y) [Compute a stochastic gradient)
Use stochastic gradient G2 to compute one-step ADAM update A for Set x' t- x + A {Compute the proposed update for the min-player)
Starting at point y. use stochastic gradients Gy to run multiple ADAM steps in the y-variable, until point y' is reached such that ||Gy , ll1 S (Simulate max-player's update) Set fnew f- F(x',/) 3/) {Compute the new loss value]
Set Accept f- True.
if fnew > foldd 10--f 5/2, set Accept + False with probability max(0, 1 e- {accept or reject)
if Accept = True then Set f- x', f- y &- O {Accept the updates}
else Set + + 1 (Reject the updates, and track how many successive steps were rejected.
return y)
We would like the min-player to minimize Le (x,,)) v). Ideally, the min-player would make updates in the direction - Ce. However, (a, y) may not differentiable and may even be discontinuous in (see Section 2.2 for an example), making it challenging to optimize. Moreover, even at points where Lg is differentiable, computing v,C; may require memory proportional to the number of max-player steps used to compute Le (for instance, this is the case for Unrolled GANs (Metz et al. 2017). For this reason, we only provide our min-player with access to the value of Ce-
One approach to minimize Le would be to min min-player proposes a random update to z, and then only accept this update it results in a decrease in Le. At each iteration of our algorithm, the min-player proposes update roughly in the direction - Vvr y). To motivate this choice, note that once the min-player proposes an update to x, the max-player's updates will only increase f. i.e., (a A v) f(r Á, y). Moreover, since y is first-order stationary point of f(x,-) -) (because was computed using gradient ascent in the previous iteration), we also have (x. y) f(z, y). Therefore, we want an update A such that
zeroth-order optimization procedure where the
f( A. S fx A, S L. v) = yx,
(1)
which implies that any proposed step which decreases L. must also decrease f (although the converse not true). This motivates proposing steps in the direction of the gradient [x, v).
Unfortunately, updates in the direction - / y) do not necessarily decrease L.- Our algorithm instead has the min-player perform random search by proposing stochastic update in the direction of a batch gradient with mean - fzf((z, y) (or. more precisely, the ADAM batch gradients), and accepts this update only if Le decreases by some fixed amount. We show empirically that these directions allow the algorithm to rapidly decrease the simulated loss. The fact that L. decreases whenever the min-player takes a step allows us guarantee that our algorithm eventually converges.
A final issue is that converging to a local minimum point does not guarantee that the point is desirable from applications standpoint. To allow our algorithm to escape undesirable local minima of (- y), we use randomized accept-reject rule inspired by simulated annealing if the resulting loss has decreased the updates for and y are accepted: otherwise they are only accepted with small probability -1/2, where 71 is "temperature" parameter.
2.1 CONVERGENCE GUARANTEES
We first formally define "simulated loss" and what it means for f to increase rapidly. Definition 2.1. For any I, y, and E > O, define E(E,x,y) y) S. Rd to be points w s.t. there a continuous and (except at finitely many points) differentiable path 7()) starting y, ending at w,
4

---

Under review as a conference paper at ICLR 2021
and moving with "speed" most I in the Ex noom
d dt
dr
such that at any point on %
fr; (()) > E.
(2)
We define (z, y) := suPweS(E.x.)) f(z, w), and refer as the simulated loss.
few remarks are in order. Observe that L-co y) maxy I (1, y). Further, if | y y)ll S e, then E(e, x 3) {y} and (x y) = f(z,y) y) (this follows from Hölder's inequality, since y()) has speed at most 1 in the -norm, the dual of the {n-nrrm). Note that the path y need not be in the direction of the gradient, and there can potentially be infinitely many such paths starting at y.
Unfortunately, the simulated loss may not even be continuous in z, and thus, gradient- based notions of approximate local minima do not apply. To bypass this discontinuity (and hence non- differentiability), we use the idea to sample updates to x, and test whether Le has decreased (equa- This leads to the following definition of local min-max equilibrium (see also Section
tion 35 2.3):
Definition 2.2. Given a distribution D Dz. for each x. y E Rd and e* > O, we say that (x",y" is an e*-local min-max equilibrium with respect to the distribution D if
V " Il S6", and PrANDaror (Ce (x* + +A,'") < Les (x*,
(3)
(a""y"" .y) -+) <E",
(4)
In our main result, we set D to roughly be the distribution of ADAM stochastic gradients for V v
Also note that from the above discussion, equation 34 implies that C.- (x", y²) = f(x", yy) To allow convergence of ADAM (and avoid con-convegeence issues such those encountered in Reddi et al. (2019), in our main result we constrain the values of the ADAM hyperparameters Now, we can state the formal guarantees of our algorithm.
Theorem 2.3. Algorithm 2 with appropriate hyperparameters for ADAM and some constant T1 > 0. given access to stochastic zeroth-order and gradient oracles for a function f = Lig[m) Si where each fo is b-bounded with L-Lipschitz gradient for some b, L > O, and & >> O, with probability at least 9/10 returns point (a* (2*.y") E IR x Rd such that, for some =* [,, the point (x*, y²) is an -loca min-max equilibrium point with respect to the distribution Da.y. where Dz.. is the distribution of (x. v)l /G3 (x, y). where the division "I" is applied element-wise. The number of stochastic gradient and function evaluations required by the algorithm is poly(1/s, d, b, L).
We present key ideas in the proof in Section 4 and proof overview in Section B The full proof appears in Appendix D Note that Dz.y is the distribution of the stochastic gradient updates with element-wise normalizations. Roughly, this corresponds the distribution of ADAM steps taken by the algorithm for updating x if one uses a small step-size parameter for ADAM.
We conclude this section with a few technical remarks about the theorem. Our algorithm could provide guarantees with respect to other distributions Dz.y in equation (5 by sampling update steps for xr from Da.y instead of ADAM. The norm in the guarantees of the stationary point y" for our algorithm is & since we use ADAM for updating y. A simpler version of this algorithm using SGD would result in an f2-norm guarantee.
Comparison to notions of local optimality. Definition 2.2 provides a new notion of equilibrium for min-max optimization. Consider the problem min, maxy fax y). but with constraints on the player's updates to x, - the max player is restricted to updating y via a path which increases If f(x, y) at a rate of at least e* at every point on the path, and the min player proposes an update for a, A sampled from D. Then (x*, y²) satisfies Definition 2.2 if and only if (i) there is no update to yy that the max player can make which will increase the loss at a rate of at least e* (equation (3).. and, (ii) with probability at least 1 - e* for random step A D proposed by the min player, the above-constrained max player can update y" s.t. the overall decrease in the loss is at most e* from its original value f(x , y-))
We use the lo -orm in place of the Euclidean En-norm, as it a more natural norm for ADAM gradients. In this equation the derivative 4 is taken from the right.
*Consider the example far y) = min(a"y² (/)""""" 1). The simulated loss function for e > 0 is C.(xx)) =
f far y) if 22²y < and I otherwise. Thus L1/2 is discontinuous at (1/2,1) 1). In particular, we set the ADAM hyperparameters B1, B2 to be 8n 8g
5

---

Under review as a conference paper at ICLR 2021
As one comparison to previous notion of local optimality, any point which is local optimum under the definition used previously e.g. in Daskalakis & Panageas (2018), also satisfies our Definition 2.2 for small enough E and distribution D corresponding to smaluh step size. On the other hand, previous notions of local optima including the one in Daskaallasis & Panageas (2018) are not guaranteed to exist in general setting, unlike our definition. (See Appendix [ detailed comparison of how Definition 2.2 relates to previously proposed notions of local optimality).
3 EMPIRICAL RESULTS
We seek to apply our min-max optimization algorithm for training GANs on both real-world and synthetic datasets. Following Goodfellow et al. (014), we formulate GAN training as a min-max optimization problem using the cross entropy loss, f(z,)) = log(D, (C)) + log(1 - Dj (G)())) where z, y are the weights of the generator and discriminator networks and D respectively. is sampled from the data, and Ş ~ (0, Ia). For this loss, the smoothness parameters b, L may not be finite. To adapt Alg. to training GANs, we make the following simplifications in our simulations:
(1) Temperature schedule: We use fixed temperature т, constant with iteration i, making it simpler to choose a good temperature value rather than a temperature schedule. (2) Accept/reject rule: We replace the randomized acceptance rule with a deterministic rule: If fnew I fold we accept the proposed step, and if snew > fold we only accept if i is multiple of e corresponding to an average acceptance rate of e- -- (3) Discriminator steps: We take a fixed number of discriminator steps at each iteration, instead of taking as many steps needed to achieve a small gradient.
These simplifications do not seem to significantly affect our algorithm's performance (see Appendix F.5 for simulations showing it effectively trains GANs without most of these simplifications). More- over, our simulations show a smaller number of discriminator steps k is usually sufficient in practice.
Datasets and Metrics. We perform simulations on MNIST (LeCun et al. 2010) and CIFAR-10 -0 (Krizhevsky et al.) datasets to evaluate whether GANs trained using our algorithm converge, and whether they are able to learn the target distribution. Convergence evaluated by visual inspection (for MNIST and CIFAR), and by tracking the loss (for MNIST) and FID scores (for CIFAR).
As noted by previous works (Borji 2019 Metz et al. 2017 Srivastava et al., 2017). it challenging to detect mode collapse on CIFAR and MNIST, visually or using standard quantitative metrics such as FID scores, because CIFAR (and to some extent MNIST) do not have well-separated modes. Thus, consider two datasets, one real and one synthetic, with well-separated modes, whence mode collapse can be clearly detected by visual inspection.
For the real dataset consider the 0-1 MNIST dataset (MNIST restricted to digits labeled 0 or 1). The synthetic dataset consists of 512 points sampled from a mixture four Gaussians in two dimensions with standard deviation 0.01 and means at (0, 1), (1, 0), (-1, 0) and (0,-1).
Hyperparameters and hardware. The details the networks and hyperparameter choices are given in Appendix E. Simulations MNIST and Gaussian datasets used four 3.0 GHz Intel Scalable CPUs, provided by AWS. On 100 we used one High freq. Intel Xeon E5-2686 v4 GPU.
3.1 EVALUATING THE PERFORMANCE OF OUR ALGORITHM
We compare algorithm's performance to both GDA and unrolled GANs. All algorithms implemented using ADAM (Kingma & Ba 2015).
MNIST. We trained GAN on the full MNIST dataset using algorithm for 39,000 iterations (with A = 1 discriminator steps and acceptance rate e - 1/5). We this simulation five times; each time the GAN learned to generate all ten digits (see Appendix F.I for generated images).
0-1 MNIST. We trained GAN using our algorithm on the 0-1 MNIST dataset for 30,000 iterations and ploted a moving average of the loss values. We repeated this simulation five times; in each of the five our algorithm learned to generate digits which look like both the "0" and "1" digits, and the loss seems to decrease and stabilize once our algorithm learns how to generate the two digits. (See Appendix E3 for the generated images and loss value plots.)

---

Under review as a conference paper at ICLR 2021
GDA
Our algorithm
250
500
1,000
2,000
3,000
500
1,000
2,000
3,000
Figure I: We trained GAN using our algorithm on 0-1 MNIST for 30,000 iterations (with k = discriminator steps and acceptance rate 1/- 1/s). We repeated this experiment 22 times for our algorithm and 13 times for GDA. Shown here are the images generated from one of these runs at various itcrations for our algorithm (right) and GDA (left) (see also Appendix F.3 for images from other rums).
GDA
Unrolled GANS with unrolling steps
1000
200
400
600
1000
1500
GDA with discriminator steps
Our algorithm
400
000
1000
200
400
800 1000
1500
Figure 2:
algorithm (bottom right), unrolled GANs with 6 unrolling steps (top right), GDA with
k (top left) and = 6 discriminator steps (bottom left). Each algorithu was trained on 4-Gaussian mixture for 1500 iterations. Our algorithm used k 6 discriminator steps and acceptance rate e 1/4. show points generated by each these algorithms after the specified number iterations.
CIFAR-10. We ran our algorithm (with discriminator steps and acceptance rate - = 1/2) on CIFAR-10 10 for 50,000 iterations. We compare with GDA with = 1 discriminator steps. We plotted the FID scores for both algorithms. We found that both algorithms have similar FID scores which decrease over time, and produce images of similar quality after 50,000 iterations (Figure
Clock time per iteration. When training on the 0-1 MNIST dataset (with A = discriminator steps each iteration), our algorithm took 1.4 seconds per iteration the AWS CPU server. On the same machine, GDA took 0.85 seconds per iteration. When training on CIFAR- 10, our algorithm and GDA both took the same amount of time per iteration, 0.08 seconds, on the AWS GPU server.
Mitigating mode-collapse on 0-1 MNIST. We trained GANs using both GDA and our algorithm on the 0-1 MNIST dataset, and ran each algorithm for 3000 iterations (Figure D GDA seems to briefly generate shapes that look like combination of O's and 1 I's, then switches to generating only 's, and then re-learns how to generate O's. In contrast, our algorithm seems to learn how generate both O's and I's early on and does not mode collapse to either digit.
We repeated this simulation 22 times for our algorithm and times for GDA, and visually inspected the images at iteration 1000. GANs trained using our algorithm generated both digits by the 1000't th iteration 86% of the runs, while those trained using GDA only did so in 23% the runs at 1000'th th iteration (see Appendix F.4 for images from all runs).
Mitigating mode-collapse on synthetic data. We trained GANs on the 4-Gaussian mixture dataset for 1500 iterations (Figure 2 using algorithm, unrolled GANs with & = 6 unrolling steps, and GDA with and discriminator steps. We repeated each simulation 10-20 times.
By the 1500'th iteration GDA with k discriminator steps seems to have learned only one mode in 100% the runs. GDA with & = 6 discriminator steps learned two modes 65% of the runs, one mode 20% of runs, and four modes 15% of runs. Unrolled GANs learned one mode 75% of the runs, two modes 15% of the runs, and three modes 10% of the runs. In contrast, our algorithm learned all four modes 68% of the runs, three modes 26% of the runs, and modes 5% of the runs.
7

---

1/2) Under review as a conference paper at ICLR 2021
GDA
Our algorithm
Figure 3: GAN trained using our algorithm (with 1 discriminator steps and acceptance rate e
GDA on CIFAR-10 for 50,000 iterations. The images generated from the resulting generator for both our algorithm (middle) and GDA (left). Over 9 runs, our algorithm achieves a very similar minimum FID score (33.8) compared GDA (33.0), and better average FID score over 9 runs (mean /1 35.6, std. dev. 1.1) compared GDA (p= 53.8, 53.9). Images shown from each; Appendix F2 for full results.
4 KEY IDEAS IN THE PROOF
For simplicity, assume = L - = There are two key pieces to proving Theorem 2.3 The first to show that our algorithm converges to point (x* y²) in poly(d, !/e) gradient and function evaluations (Lemma D.7.. Secondly, we show that, y" a first-order E-stationary point for f( and x* is, roughly, a e-local minimum for the simulated loss function Le(. v²) (Lemma D.9
Stepl: Bounding the number of gradient evaluations: After (llog( steps, the decaying accep- tance rate of the simulated annealing step ensures that our algorithm stops whenever Tmax = O proposed steps are rejected in a row. Thus, for every O(rmar/e²) iterations where the algorithm does terminate, with probability at least - e the value of the loss decreases by more than e. Since f is 1-bounded, this implies our algorithm terminates after roughly O(rmus/>²) iterations of the minimization routine (Proposition D.6).
Next, since f is I-bounded with I-Lipschitz gradient, in each iteration, we require at most poly(//s) gradient ascent steps to reach an e-stationary point. Since each step the maximization subroutine requires one gradient evaluation, and each iteration of the minimization routine calls the maximization routine exactly once, the total number gradient evaluations is poly(d, (d.)).
Step 2: Show x² is an c-local minimum for (-(vv") and y* is an e-stationary point. First, we note that since our algorithm runs the gradient ascent maximization subroutine until it reaches an e-stationary point, we have, || Vx y/" S
Our stopping condition for the algorithm implies the last max updates A proposed by the max-player were all rejected, and hence were sampled from the distribution Dar, of the ADAM gradient at (x*, ,y"). Roughly, this implies
(5) where the maximization subroutine computes y by gradient ascent f(x A,-) initialized at y*. other words, equation 5 says that at the point (x*, yy") where our algorithm stops, if the min-player samples update A from the distribution Dær followed by the max-player updating y using gradient ascent, with high probability the final loss value cannot decrease by more than E.
PrAwDay If(** + A,8) 2 [(x".)' 21111
To show equation 35 holds, need to replace f in the above equation with the simulated loss L.- We first show that the gradient ascent steps form an "s "'-increasing" path, starting at y with endpoint y' along which increases at rate at least (Prop. D.8). This crucially exploits that algorithm restricts the max player to only use such "e-increasing" paths. Since Le is the supremum f at the endpoints of all such e-increasing paths starting at y" we get
f(x + A. v') < (x +A,").
Finally, recall from Section 2 that / >111 < Ex implies Le V" f(x", ,y"). Combining the above observations implies the elocaal minimum condition equation 35
Note that could pick any distribution D for the updates and the proof still holds the distribution of ADAM gradients works well in practice. Also, we could replace simulated annealing with a deterministic rule, but such algorithm often gets stuck poor local equilibria in GAN training.
8

---

Under review as a conference paper at ICLR 2021
5 CONCLUSION
In this paper, we develop convergent first-order algorithm for min-max optimization and show how it can lead to a stable and scalable algorithm for training GANs. We prove that our algorithm converges in time polynomial in the dimension and the smoothness parameters of the loss function. Our simulations show that a version of our algorithm can lead to more stable training of GANs on synthetic and real-world datasets. And yet the amount of memory and time required by each iteration of our algorithm is competitive with GDA. Our algorithm synthesizes a first-order approximation to the global strategy of the max-player, look ahead strategy based on batch gradients for the min- player, and simulated annealing. We believe that these ideas of imposing computational restrictions on the min- and max-players should be useful in obtaining convergent and practical algorithms for other applications of min-mas max optimization, such as adversarial learning.
REFERENCES
Jacob Abernethy, Kevin A Lai, and Andre Wibisono. Last-iterate convergence rates for min-max optimization. arXiv preprint arXiv:1906.02022. 2019.
Martín Arjovsky and Léon Bottou. Towards principled methods for training generative adversarial networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference on machine learning, pp. 214 223, 2017.
Rowel Atienza.
GAN by example using keras on tensorflow backend. -ennoongoo
httpltussiiicc..o////aaaaaaaaaaa 1a6d51 1 5a60d0", 2017.
David Balduzzi, Sebasticn Racaniere, James Martens, Jakob Foerster, Karl Tuyls, and Thore Graepel. The mechanies of n-player differentiable games. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 354-363, Stockholmsmässsan Stockholm Sweden, 10-15 Jul 2018. PMLR.
Marc G. Bellemare, Ivo Danihelka, Will Dabney, Shakir Mohamed, Balaji Lakshminarayanan. Stephan Hoyer, and Rémi Munos. The Cramer distance solution biased Wasserstein gradients. CoRR, abs/1705. 10743, 2017. http::t:://aaat wwtp:aawwww.og//////a/oa//////aa 7055 10..100444 10743
Jérôme Bolte, Lilian Glaudin, Edouard Pauwels, and Mathieu Serrurier. Ah3," olderian backtracking method for min-max and min-min problems. arXiv preprint arXiv:2007.088800 2020.
Ali Borji. Pros and cons of gan evaluation measures. Computer Vision and Image Understanding, 179:41-65, 2019.
Jason Brownlee. How to develop GAN to generate CIFARIO small color pho- http://wwwe...eoooooooeeoeeeeeee tographs. hawpeciheeeeccnllloiicoioooohhhe
for-a-cifar-10-ssaallll
2019.
Sébastien Bubeck. Convex optimization: Algorithms and complexity. Foundations and Trends in Machine Learning, 8, 2017.
Tong Che, Yanran Li, Athul Paul Jacob, Yoshua Bengio, and Wenjie Li. Mode regularized generative adversarial networks. In International Conference on Learning Representations, ICLR, 2017.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In S. Bengio, H. Wallach. H. Larochelle, K. Grauman, N. Cesa-Biant Bianchi, and R. Gamett (eds.), Advances in Neural Information Processing Systems 31, pp. 9236-92444 Curran Associates, Inc., 2018.

---

Under review as a conference paper at ICLR 2021
Constantinos Daskalakis and Ioannis Panageas. Last-iterate convergence: Zero-sum games and constrained min-max optimization. In 10th Innovations in Theoretical Computer Science Confer- ence, ITCS 2019, January 10-12. 2019, San Diego, California, USA. pp. 27:1-27:188 2019. doi: 10.42300LIPIcs.ITCSS.00000
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference on Learning Representations, 2018.
Vincent Dumoulin, Ishmael Belghazi, Ben Poole, Alex Lamb, Martín Arjovsky, Olivier Mastropietro, and Aaron C. Courville. Adversarially learned inference. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Tanner Fiez, Benjamin Chasnov, and Lillian J. Ratliff. Convergence of learning dynamics in stackelberg games. CoRR, abs/1906.01217, 2019. URL URL:ttp://arxx wttp:/iwwrr//ab//10000
01217
Rong Ge, Furong Huang. Chi Jin, and Yang Yuan. Escaping from saddle points online stochastic gradient for tensor decomposition. Conference on Learning Theory, pp. 797-842, 2015.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste- A
variational inequality perspective on generative adversarial networks. In International Conference on Learning Representations (ICLR 2019), 2019a.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of Machine Learning Research, volume 89 of Proceedings of Machine Learning Research, pp. 1802-1811, PMLR, 16-18 Apr 2019b.
lan Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley. Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- fion processing systems, pp. 2672-2680, 2014.
lan J. Goodfellow. NIPS 2016 tutorial: Generative adversarial networks. CoRR, abs/ 1701.001661 2017.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of Wasserstein GANs. In Advances in neural information processing systems, pp. 5767-5777, 2017.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by a two time-scale update rule converge a local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626-6637, 2017.
Chi Jin, Praneeth Netrapalli, and Michael Jordan. What is local optimality in nonconvex-nonconee minimax optimization? In JCML 2020. International Machine Learning Society (IMLS), 2020.
Renu Khandelwal.
Generative adversarial network
(GAN) using keras.
"https://medium.c www.aaadewonnnngggerrrreeaaaaaea celc05cfdfa3". 2019.
David Kinderlehrer and Guido Stampacchia. An introduction to variational inequalities and their applications, volume 31. Siam, 1980.
Diederik P. Kingma and Jimmy Ba. Adam: A method for stochastic optimization. In International Conference for Learning Representations, pp. 1595-1625, 2015.
Naveen Kodali, Jacob D. Abernethy, James Hays, and Zsolt Kira. How to train your DRAGAN. CoRR, abs/1705.07215. 2017. URL /
072115
Alex Krizhevsky, Vinod Nair, and Geoffrey Hinton. Cifar-10 (canadian institute for advanced research). URL URLhttp: http: htpp:///www......... cs
far.
10

---

Under review as a conference paper at ICLR 2021
Yann LeCun, Corinna Cortes, and CJ Burges. Mnist handwritten digit database. ATT Labs [Online]. Available: http:://anm.. www.n.ccc..ooooo wwt../////////iiitttt.omom 2, 2010.
Jerry Li, Aleksander Madry, John Peebles, and Ludwig Schmidt. On the limitations of first-order approximation in GAN dynamics. In International Conference on Machine Learning, pp. 301 3019, 2018.
Tengyuan Liang and James Stokes. Interaction matters: A note on non-asympiotic local convergence of generative adversarial networks. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 907-915, 2019.
Jac Hyun Lim and Jong Chul Ye. Geometric gan. arXiv preprint arXiv:1705.0289. 2017.
Qihang Lin, Mingrui Liu, Hassan Rafique, and Tianbao Yang. Solving weakly-coovve-weakly concave saddle-point problems as weakly-monotone variational inequality. arXiv preprint arXiv: 10207, 2018.
Tianyi Lin, Chi Jin, and Michael Jordan. On gradient descent ascent for nonconvex-concave minimax problems. In 37th International Conference on Machine Learning, ICML 2020. International Machine Learning Society (IMLS), 2020.
Songtao Lu, Ioannis Tsaknakis, Mingyi Hong, and Yongxin Chen. Hybrid block successive ap- proximation for one-sided non-convex min-max problems: algorithms and applications. IEEE Transactions on Signal Processing, 2020.
Aleksander Madry, Aleksandar Makelov, Ludwig Schmidt, Dimitris Tsipras, and Adrian Vladu. Towards deep learning models resistant adversarial attacks. ICLR, 2018.
Niru Maheswaranathan. Luke Metz, George Tucker, Dami Choi, and Jascha Sohl-Dickstein. Guided evolutionary strategies: augmenting random search with surrogate gradients. In International Conference on Machine Learning, pp. 4264-4275 2019.
Oren Mangoubi and Nisheeth K Vishnoi. second-order equilibrium in min-max optimization: Existence and algorithm. arXiv preprint arXiv:2006. /2363, 2020.
Xudong Mao, Qing Li, Haoran Xie, Raymond YK Lau, Zhen Wang, and Stephen Paul Smolley. Least squares generative adversarial networks. In Proceedings of the IEEE International Conference on Computer Vision, pp.
2017.
Panayotis Mertikopoulos, Bruno Lecouat, Houssam Zenati, Chuan-Sheng Foo, Vijay Chandrasekhar, and Georgios Piliouras. Optimistic mirror descent in saddle-point problems: Going the extra (gradient) mile. In International Conference on Learning Representations (ICLR 2019), 2019.
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans, In Advances in Neural Information Processing Systems, pp. 1835-1835, 2017.
Luke Metz, Ben Poole, David Pfau, and Jascha Sohl-Dickstein. Unrolled generative adversarial networks. In 5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings, 2017.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. In International Conference on Learning Representations, 2018. URL httpthts:///peeeeeeeeee wwtp:viwwwwweeeeeeeemmmmmm nwt. forum? wwwtorummddiB@@ooe id=B1
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Proximal point approximations achieving convergence rate of o (1/k) for smooth convex-concas saddle point problems: Optimistic gradient and extra-gradient methods. arXiv preprint arXiv: 995.00/150....... 2019.
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. unified analysis of extra- strri-tradient and optimistic gradient methods for saddle point problems: Proximal point approach. In International Conference on Artificial Intelligence and Statistics, pp. 1497-1507. PMLR, 2020.
Vaishnavh Nagarajan and Zico Kolter. Gradient descent GAN optimization is locally stable. In Advances in Neural Information Processing Systems, pp. 5585-5595, 2017.
11

---

Under review as a conference paper at ICLR 2021
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, 15(1):229-25 2004.
Arkadi S Nemirovski and David Berkovich Yudin. Cesari convergence of the gradient method of approximating saddle points of convex-coneave functions. In Doklady Akademii Nauk, volume 239. pp. 1056-1059. Russian Academy of Sciences, 1978.
Yurii Nesterov and Boris T Polyak. Cubic regularization of newton method and global performance. Mathematical Programming, 108(1):177-205, 2006.
Maher Nouiehed, Maziar Sanjabi, Tianjian Huang, Jason D Lee, and Meisam Razaviyayn. Solv- ing a class of non-convex min-max games using iterative first order methods. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' Alché-Buc, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems 32, pp. 14905-14916. Curran Associates, Inc., 2019.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications machine learning. arXiv preprint arXiv:/810.02060 2018.
Sashank Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:1904.099 09237, 2019.
Tim Salimans, Han Zhang, Alec Radford, and Dimitris Metaxas. Improving GANs using optimal transport. In International Conference on Learning Representations, 2018. URL https://
openreview nwt. http//ooruummddrrkkkkmmmm
Shibani Santurkar, Ludwig Schmidtt and Aleksander Madry, classification- study of covariate shift in GAN distributions. In International Conference on Machine Learning, pp. 1480-4488 PMLR, 2018.
Akash Srivastava, Lazar Valkov, Chris Russell, Michael Gutmann, and Charles Sutton. Veegan: Reducing mode collapse in gans using implicit variational learning. In Advances in Neural Information Processing Systems, pp. 3308-3318, 2017.
Kiran Koshy Thekumparampil. Prateek Jain, Praneeth Netrapalli, and Sewoong Oh. Efficient algorithms for smooth minimax optimization. NeurlPS, 2019.
Yuanhao Wang, Guodong Zhang, and Jimmy Ba. On solving minimax optimization locally: follow-the-ridge approach. In International Conference on Learning Representations, 2020.
12

---

Under review as a conference paper at ICLR 2021
A
THE FULL ALGORITHM
Algorithm 2 Algorithm for min-max optimization (formal version)
input:
Stochastic zeroth-order oracle F for loss function f Rd Rd R. and stochastic gradient oracle G2 for VzJ, f, and Gy for Vyf
input: Initial point (Io, yo), Error parameter
output: A point (x", ,y")
hyperparameters: Tmax (max number of rejections); 7i > 0 (hyperparameter for simulated anneal- ing); hyperparameters a, 17, 5 > 0 and 31, $2 E [0, 1] for ADAM
1: Set 0, + O, f- 0, mo 0, to +- 0, m 0, 0, + 0, =
2: Set fold - oo {Set fold to oo (or the largest possible value allowed by the computer) to ensure that the first step is accepted]
3: while r S Fmax do
4: Set Suiiitti
5: Set 9x,i + Gz(,,, Hi) ( {Compute proposed stochastic gradient)
6: Set Mi+1 + Bim4 + (1 S1)gr,is and V1+1 + B2 + +11 32) {Compute proposed ADAM
update for first- and second- moment estimates)
7: Set Xi41
Met1/( 24 a #4
1 V 6) {Compute proposed ADAM update
x-variable)
8:
Run Algorithm 3 with inputs X +- X f Ve. (m, s), and e' < (1 + n))
ADAM optimizer to simulate the max player's response.
9:
Set Ve+1 < Ystationary and (M, V, (Mout: Vout: Sout) to be the outputs of Alg.
10:
Set Jnew x- F(X++1,
11:
if Snew > Sold 1. then
Set Accept, + False with probability m0ax00,1 - (Decide to accept or reject)
12:
13:
if Accept, True then
14:
Set r1+1 + X,+1, V1-1 t V1+1 faccept the proposed x and y updates}
15:
Set t- M,+1, Ui+1 Vi+1, and (m, v) +- (M, V) {accept the proposal's ADAM
moment estimates)
16:
Set fold - Snew
17:
Set a + a + (keep track of how many steps we accepted]
18:
Setr
19:
Set E:+1 t E3(1 7)2
else
21:
Set Fi+1 +- Jzs Vi+1 1 Vi {go back to the previous and values]
Set m++1 +- my, Mi+1 +- v; {go back to the previous ADAM moment estimates)
23:
r + (Keep track of how many steps were rejected since the last acceptance. If too many steps were rejected in row, stop the algorithm and output the current weights.)
24:
Set 6i+1 f
25:
return (x" 15") < (xz V/)
13

---

Under review as a conference paper at ICLR 2021
Algorithm 3 ADAM (for the max max-player updates)
input: Stochastic gradient oracle Gy for Vyf
input: X, Yo. m, v, number of steps s taken at previous iterations
output: point Ystationary which is first-order e' -ttatioonyry point for f(x,
+), and Sout. Mout, Vout
hyperparameters:
0; ADAM hyperparameters â, 0 and 31 $2
[0,
1: Set t- 0
2: Set Stop False
3: while Stop False do
4: Set j - j +
5: Set gy.j & Gy(x, Y,)
6:
if Ily 1 E' then
7:
Set j + +-+11
8:
Set m, < fim, + (1 - B1 I9 and V + 82v; + +1 - -B32g (Compute proposed ADAM second- moment estimates)
update first
9:
Set Yj+1 5- Yj + ā 1 85
1- + 6) (Compute proposed ADAM update of /3/ VVVVVVVv 1- 1-
y-variable]
10:
else
Set Stop True
12:
Set Vstationary + yj and Sout f- 8 + Mout f- mj, Vout + V
B PROOF OVERVIEW
To prove Theorem 2.3 we would like to show two things: First, that our algorithm converges to some point (xx* y in number of gradient and function evaluations which is polynomial in 1/8, d. b, (Lemma D.7 in the appendix). Secondly, roughly, we would like to show y* is a first-order s- stationary point for f(x".-) and x* is a e-local minimum for the simulated loss function C.(, v")
(Lemma D.9).
Bounding the number of gradient and function evaluations (Lemmaa D.7 First, we bound the number of gradient evaluations for the maximization subroutine for (Line 6 of Algorithm|] [ and then bound the number of iterations the minimization routine for x (the "While" loop Alg. D
Step 1: Bounding the number of gradient ascent steps for the maximization subroutine: Consider the sequence of ADAM gradient ascent steps y = y1, 1/2 ... ....We Vt = y the max-player uses to compute her update y' in Line of Alg. [ For our choice of hyperparameters, the ADAM update is Vj+1 My + (G, (G) (z, y;)) where is the ADAM learning rate. Since the magnitude of our ADAM gradient satisfies ||G (x, (GG "1)) = [[, 3y)]l1 our stopping condition for gradient ascent (Line 6 of Alg. []. which says that gradient ascent stops whenever [[G (2,3,) 9;) S implies that at each step of gradient ascent our ADAM update has magnitude at least ae in 2n-ormm Using this, we then show that each step yj of gradient ascent, we have with high probability that f(y++1) f(y) 2 Q(aE),
(7)
Since f is b-bounded, this implies that the ADAM gradient ascent subroutine must terminate after ((b((oe) O(bLd/e) steps.
the ADAM learning rate satisfies a s ((f((La)) (Proposition D.5
Step 2: Bounding the number of iterations for the mininization routine: We first show a concentration bound for our stochastic zeroth-order oracle (Proposition D.3 and use it show that, for our temperature schedule of T; T//.. after I := Ti log b/e3 iterations, our algorithm rejects any proposed step I' = x + A for which f(x', y²) > f(x, u) - with probability at most roughly
1 1--- < - /((2r Therefore, roughly, with probability at least - for the first 2rmsch/e
iterations after 2, we have that only proposed steps x' = I + A for which f(x' v') < f(x,, y) are accepted. Moreover, our stopping condition (Line 2 in Alg. I stops the algorithm whenever Tmax proposed steps are rejected in row. Therefore, with probability at least 1 - we have that the value of the loss decreases by more than 25/e between iterations I and Î + "/=", unless our algorithm terminates during these iterations. Since is b-bounded, this implics our algorithm must terminate after roughly O Ofrm.))/e") iterations of the minimization routine (Proposition D.6).
14

---

Under review as a conference paper at ICLR 2021
Now, each of the (bbldf)) steps of the maximization subroutine requires one gradient evaluation, and each of the 0/2maz//="" iterations of the minimization routine calls the maximization routine exactly once (and makes one call to stochastic oracles for the function f and the x-gradient). Therefore, the total number of gradient and function evaluations is roughly bLd/e x r //3 which, for our choice of hyperparameter Tmax of roughly ''max = 1/c, is polynomial in 1/e, d, b, I.
Showing (x", v²) satisfies Inequalities equation 34 and equation 35 (Lemma D.9
Step 1: Show y" is a first-order e-stationary point f(x"," (-) (equation 34 Our stopping condition
for the maximization subroutine says [|Gy(a", .3"')h S & at the point y" where the subroutine
terminates. To prove equation 34 we show concentration bound for our stochastic gradient Gy
(the second part of Proposition D.3) and use this to show that the bound [[ y )[1 S on the
stochastic gradient obtained from the stopping condition implies the desired bound on the exact gradient, V (x*, y" Il1 S.
Step 2: Show x" is an e-local minimum for (y) (equation 35 First, we show our stopping condition for the minimization routine implies the last ''max steps A proposed by the algorithm were all rejected. This implies the last Tmax proposed steps were sampled from the distribution Dr of the ADAM gradient Gx y²) /") y y²)) and, since they were rejected, our stopping condition implies, roughly, f(** + A, y²y f(a" y²) -E for all these proposed steps A. Roughly, we use this, together with our poly( d, b, L) bound on the number of iterations (Proposition D.6 to show
PrA-D...y- [f(x* + A,1) 2 f(x" - a) 21-8
where the maximization subroutine computes y by gradient ascent on f(x" + A.-) initialized at y"
To show that equation 35 holds, roughly, we would like to replace "f" in the bound in Ineq. equation with the simulated loss function L. Towards this end, we first show that the steps traced by the gradient ascent maximization subroutine form an "e-increasing" path, with endpoint 3/. along which I increases at rate at least (Prop. D.8}. Although we would ideally like to use this fact to show that f(a + 3 = (x + A, y²), this equality does not hold in general since L. is defined using a large set of such E e-increasing paths, only one of which is simulated by the maximization subroutine. To get around this problem, we instead use the fact that Le is the supremum of the values of f at the endpoints of all e-increasing paths starting at y" which seek to maximize f(x" + A,,,, to show that
f(r - A.V) S (x + +A,"".
Finally, we already showed that ff y11 S E": recall from Section 2 that this implics (x y*) f(r y*). Combing this with equation equation 9 implies the e-local minimum condition equation 35
C COMPARISON OF NOTIONS OF LOCAL OPTIMALITY
In previous works Daskalakis & Panageas (018): Heusel et al. 2017). a local saddle point (equiva- lently a local Nash point) has been considered as possible notion of local min-max optimum. A point (x*, 3²" is said to be local saddle point if there exists a small neighborhood around x and y such that y" is a first-order stationary point for the function [(x", :); and x² is local minimum for the function f(,y") ). A key difference between a local saddle point and the local min-max equilibrium we introduce in our paper (Definition 2.2 is that local saddle point does not take into account the order in which the min-player and max-player choose x and y.
While a local saddle point is not guaranteed to exist in general nonconvex-nonconeee min-max problems, if there exists local saddle point, this saddle point is also a local min-max equilibrium as given by Definition 2.2 More specifically, any local saddle point for a smooth function is an e-local min-max equilibrium for every >> 0, provided that we pick the step size for the min-player to be small enough. This is because, if there a point (x*, ) local saddle, then y* is a first-order stationary point for the function (x=,-)) Thus, the gradient at (x*, (x*,y") must be zero and the first condition (Inequality equation 34 is satisfied.
If we pick the step size small enough, the step A will be such that xt + +A lies within this neighborhood of x= and hence
Celx" ,v") [(=",0") )²²== E f(x +A, S Le(x* +A,y")
15

---

Under review as a conference paper at ICLR 2021
for all 0 Thus the second condition (Inequality equation 35 is satisfied for any 0.
Another notion of local minimax point was proposed in Jin et al. (2020). In their definition, the max player is able choose her move after the min-player reveals her move. The max- max-player is restricted to move in a small ball around y", but is always able to find the global maximum inside this ball. In contrast, in definition, the max-player is empowered to move much farther, long she is following a path along which the loss function increases rapidly. Hence, in general these two notions incomparable. However, even under mild smoothness conditions, local minimax point is guaranteed to exist Jin et al. 2020), whereas local min-max equilibrium (Definition 2.2 ís.
Finally, in a parallel line of work, prove the existence of stronger, second-order notion of min- max equilibrium for emnconve--nomconca
functions motivated by the notion of approximate local minimum introduced in Nesterov & Polyak| (2006). The advantage of the notion our current paper (Definition 2.2) is that it yields a concise proof of convergence and the accompanying algorithm, as our empirical results show, is effective for training GANs.
MAIN RESULT D
Recall that we have defined Day be the distribution of the point-wise normalized stochastic gradient Gz y)/ w)/vG2 (z, y). We also recall that we have made the following assumptions about stochastic gradient, which restate here for convenience:
Assumption D.1 (smoothness). Suppose that fe(a, v) ~ Da.y y is sampled from the data distribution for any x, y E Rd. Then, with probability 1, fe is b-bounded, L In-Lipschitz and has L-Lipschitz gradients Sr.
Assumption D.2 (batch gradients).
1
F(x,y)
f( y)
60
b
Gz(x,)) =
V V fz v),
6%
1
Gy
by
where, fe are sampled iid (with replacement) from the distribution D(z.g) and bo, bzs by are batch sizes. Every time Gu, Gy. or F is evaluated, a new, independent, batch is used.
Setting parameters: For the theoretical analysis, we set the following parameters, and we define if 0. We also assume $ 1.
1. a a==1
2. 31 0, B2 = =0
3. W
( )
256 log(Ti 256 log (100 (TI + _) + +1)]
2iobLd+16
4. Tmax
128
log
100 (TI + (8 + +1 1)= log( 1
:
5. Define I = Ti log( Tmax
Sr inax
6. 17 2 -1
(in particular, note that the fact that 2 - and I 2 1 implies that
57 51 S +
E(1 s(1-1i-)
7. & 10Ld
8. Define I =
20h 355
RReall from Sec.
that if Eq. equation 34 satisfied then Ce(x". f(x", (v²"""))
16

---

Under review as a conference paper at ICLR 2021
9. 1 3/ It4
10. b =1
11. bo = Ei- 142222 (2w)
12. by 1,2 log(l///ww) (/ww)
In particular, we note that S (323+16)7 and Fmax 2 log( 1002), ) At every iteration i, where 8
: set E Eis also have e' Eo 1)22 and hence that ( + Lvdā) (1 )00 I
(1- I4o )s'
Proposition D.3. For any w > O, if we use batch sizes by = 2102 log(1/w) and bo 142140 log()) log()/), we have that
61
PP
Vol(,,))
< wi
(10)
10
and
P ( ((E.)))
81
f(x,
(11)
10
Proof.
From Assumption D.2 we have that
1 b, = by
Gy(2, 8) V fff(r,))
2 V. - vzf 8)},
where fl....fe f₂ are sampled iid (with replacement) from the data distribution D.
But by Assumption D.I we have (with probability 1) that
[V)fl(..v) - v 3)ll & | fo (2) + Il S 2L1.
Now,
E ( -[V f[, v)]l 0.
Therefore, by the Azuma-Hoefding inequality for mean-zero bounded vectors, we have
P 1
8 svby +
< 2c 1-
24,
Vs 0.
by
Hence, if we set = 6log (²)) (2
we have that 7log 1/2 (2(3)) v b, + 1122 2 b, + and hence that
(2)
7 7log 1/2 (2) by 2L1
(off((,))) vyf(a,
w.
by
b,
Therefore,
by v fe
E
IP
V wyf(e, y)]
2
<
by
10
which completes the proof of Inequality equation
10
Inequality equation follows from the exact same steps the proof of Inequality equation 10 if we replace the bound L, for V y)112 with the bound on (f, v)]-
17

---

Under review as a conference paper at ICLR 2021
Proposition D.4. For every j we have
1yy++1 - -sll2 s avd.
(12)
Moreover. for every i we have,
|0++1 - -2:l2 I avd.
(13)
Proof.
|1 055l2 s allm;// /2,l2 â Σ
By [k]] ( [b
ávd
This proves Inequality equation above.
12
The proof of Inequality equation 13 follows from the same steps
Proposition D.5. Algorithm terminates in at most J probability at least w x J.
iterations of its "While" loop, with Site
20h
Proof. Recalling that and v- denote element-wise operations, we have
((m// grn)
gr s6. gy.skk)
(14)
1 [k]]
11 111
since, whenever Algorithm is called by Algorithm 2 Algorithm some value E 2 5 Therefore, we have that
2 sets Algorithm) 3 input s' to
Prop D3
1y++1 - Yy- (x),,))))
(y++1 - Yj. gy.) - 1lyy+11 - Yýll2 x
(15)
10
(á(m,/ Vz); 9y.5) - -llys+1 - -ysll2 é
10
14
E
|ly Vil12 x
10
Prog
5 ávd
2
10
2 âs,
10
with probability at least w. since é1
5
Since f has L-Lipschitz gradient, there exits a vector u, with [|u||2 S L1lyy+1 - -ylll, such that
f(y++1) - 5(y,)
-(yj+1 yj, vgf(x, + w)
(16)
<(y++1 - Yú, Vyf(x. y5)) + (y5+1 - Yy, u)
F 1b
âg L - 11112
10
Prop 12.4
4
âg Ladd
10
18

---

Under review as a conference paper at ICLR 2021
3
ae,
10
with probability at least w. since â 10Ld'
Since f takes values in [-b, b), Inequality equation 16 1mimlls that Algorithm 3 terminates in at most J 204 iterations, with probability at least 1 w x J. 3
Proposition D.6. Algorithm 2 terminates in at most I == log( (iax + Sr 5t'ax b + iterations of its "While" loop, with probability at least 1 2w (Tmax f
26
1).
Proof. For any i > 0, let Eg be the "bad" event that both / ( Mi+1) (11, 11) Accept, = True.
and
Then by Proposition D.3 since
é S g. we have that I0
P(Es) Se - #744 ww
(17)
Define I := Ti log( [max ).
Then for i 2 Σ, from Line 12 of Algorithm
we have by Inequality equation 17 that P(E)) S 2w.
Define h : T'ax
2b + 1. Then
I+h P
E.
2w h.
(18)
i=1
Since takes values in [- b), if U E, does not occur, the number of accepted steps over the iterations 2 < i < I h (that is, the size of the set (i: : i < < 2 + h, Accept, True)) is at most 2h
2b Therefore, since Tmax f
1, we must have that there exists number with Ý i i+ Tmax S
+ ht such that Accept, = False for all E [i, + Tmax].
Therefore the condition in the While loop (Line 9 of Algorithm 2 implies that Algorithm terminates 2++h after at most i + Tmax < i + h iterations of its While loop, as long as U, E, does not occur.
Therefore, Inequality 18 implies that, with probability at least 2i X (Fmax it 1), Algorithm terminates after at most
Ż + h log(
Tmax + 8r +1
b
iterations of its "While" loop.
Lemma D.7. Algorithm terminates after at most (Tr log( Tmmax ) 4r max b +1) (Jxx x xb, bbybbb +bu bb+) gradient and function evaluations.
Proof. Each iteration of the While loop in Algorithm 2 computes one batch gradient with batch size 6z and one stochastic function evaluation of batch size bo. and calls Algorithm exactly once.
Each iteration of the While loop in Algorithm computes one batch gradient with batch size by-
The result then follows directly from Propositions D.6 and D.5
19

---

Under review as a conference paper at ICLR 2021
Recall the paths (t) from Definition 2.1 From now will refer to such paths as "E-increasing paths". That is, for any & >> O, we say that a path (() is an "E-imcreasing path" if at every point along this path we have that it [t))ll and that de (xx > (Inequality equation 33).
Proposition D.8. Every time Algorithm is called have that, with probability at least 1 2w the path consisting of the line segments
J. Y2+1) Y formed by the points y, computed by Algorithm has a parametrization 7(t) which an -increasing path.
Proof. We consider the following continuous parametrized path (t):
7(1) - y, + b0g E [á<j do],
j E Limax];
where U1 == 9v.j/ V (2 and Jmax is the number of iterations of the While loop of Algorithm
First, we show that this path has at most at most unit- unio-velocity in the infinity-norm at all but a finite number time-points. For any point in one of the open intervals & E (ū(j 1), āz), we have that
(f) = l|,y = /9yy (gy.)) S II.L...., 1) = 1. dt
This implies that the path (t) has unit velocity in the infinity norm at all but a finite number of time-points.
Next, we show that 4 fx, r(t)) 2 s'. Now,
|eyll2 = Vd
(19)
and hence,
||y - Y5l12 = 1|āvbl12 = àvd
(20)
at every step
By Line 12 of Algorithm 3 we have that ||gy../ gy.a 12 > e' for every E [mmax]] where we define Jmax E MU (Do) to be the number of iterations the While loop Algorithm 3 Therefore, for
every j [max] by Proposition D.3 we have with probability least 1 w that
f(x (x y3) Llly+41 Ysll2u] 0y
(21)
F 20
V (x, LVdani] J0z
Lgy
LVdāvu] Tog oj
10
81 TVVe Tzj
10
STo (ovss/
(gx.))
El + L LV ddu] uy
10
=1laxs/ V
112
w + I.ddru]T Tu
10
2 119y.s/ / V
19y.
112
+
LV dái 11yl112
10
Es 19
1,.y.5/ V
+ LVVdavV
10
81
2
+ LVdájvá
10
Vt E [ā(j - 1), aj],
1 + 17
'Recall that we use convention
0/0 when computing the Adam update our algorithm. This implies
that lør./ / (ov (1,...,1)
20

---

Under review as a conference paper at ICLR 2021
for unit vectors u, E R since ( Lvdaavd (1- Ihe)e I (1 1 )='.
But by Proposition D.5 have that Jmax I J with probability at least 1 x J. Therefore inequality equation 21 implies that
d
1
dt (x, (()) 2
Vt E [ā(] 1).
Vj E [mmax]
1+
with probability at least 2wJ.
Lemma D.9. Let i be such that is the last iteration of the "While" loop Algorithm for which Accept, True. Then with probability at least 1 2w:JI 2w X (Tmax 2b
+ 1) we have that
4
1yy(("")"") 1l1 s v1 + E5..
(22)
Moreover, with probability least
(Tmax 24
+ 1) we have that
100
PaWDer,,' (oe (x" + +,, S Le,, (0",
=
1
x
y
S 8.
(23)
2
2
and that
8 S Ei. Se.
(24)
2
First, note that (x*,"") (wi vi) for all i {i* ...., mmax ). and that Algorithm stops after exactly it + Tmax iterations of the "While" loop in Algorithm
Proof.
Define A; := 9x.i/ V (2x,i) for every i. Then A Dz..
Let H; be the "bad" event that, when Algorithm B is called during the ith iteration of the "While" loop in Algorithm [ the path traced by Algorithm is not an ey-increasing path. Then, by Proposition D.8 have that
P(H,) 2WJ.
(25)
&1 10- Let K; be the "bad" event that [[,, vi) far v:))l2 2 D.5 we have that
Then by Propositions D.3 and
P(K,) & 2wJ.
(26)
Whenever KE occurs we have that
[1 9: (G, vyl(x,
(27)
A E + G. (xf(,,,)))1
61
1 1 & +
10
Ei. V1 1]
where the second Inequality holds by Line 12 of Algorithm 3
and the last incquality holds since
é TO Therefore, Inequalities equation 26 and equation 27 together with Proposition D.6 imply that
1- र
-/
VV
VI+ Ei.
with probability at least 1 - 2WJI 2w x (rmax
2b
+ 1). This proves Inequality equation 22
is
21

---

Under review as a conference paper at ICLR 2021
Inequality equation 27 also implies that, whenever Kद occurs, the set Se,,z.. of Ej-increasing paths with initial point y4 (and v-value zy) consists only of the single point yr. Therefore, we have that
Ce, (Z 9i) = f(z;, y:)
(28)
whenever Çţ occurs.
Moreover, whenver Hद occurs we have that 24+1 is the endpoint of an E--increasing path with starting point (z; + A, Mt). Now, Le, (zy + As, y4) is the supremum of the value of f at the endpoints of all ex-increasing paths with starting point (2r + A., Therefore, we must have that
(x, ()) 2 [a + 1++1)
(29)
whenever HÇ occurs.
Therefore.
1
P PA-Da
Le + A,) > Le, (xi,
2 -/ (ii..1 2/:
(30)
Ex 29
P PANDrF.M
f(z; A1.D++1) > f(z1, 8/)
- 24,
P(H,) P(K:)
2
Prop D3
P Da
F(x; A, F(
Dia Vi
2w -(HH,) P(Ki)
P Accept, False Tie V/)) 2w P(H::) PP(K))
26
P (Accept, False 24, 31)) 2ww -WT 2WJJ
vi II
where the second inequality holds by Proposition D.3 since &
S S.
TO
Define P: = PAWDoE. (cx A. (x4,00))))
fe Vi for every E N. Then In-
equality equation 30 implies that
PP (Accept, = False| m)) S +w + 5
sp: S VIII,
(31)
since w S 325+16
We now consider what happens for indices i for which p; - f.c. Since (I Vi4s) = (x vi)
whenever Accept False for all s, have by Inequality equation 31 that
1 Tmax
Tmox (Accepty45 False) p) S
20
s (1
Vi S I Tmax
100Z
since Fmax log(( 1000) ).
Therefore, with probability at least 1 XI = 1-
100 we have that the event ("mma (Accept
1007
False) does not occur for any i < I Tmax for which ps < f.
Recall from Proposition D.6 that Algorithm terminates at most iterations of its "While" loop, with probability at least 2w x (Tmax
2h 1).
Therefore,
E
Pi
2
2
100
2w x (Fmax
I + 1).
1
(32)
In other words, by the definition of pi+, Inequality equation 32 implies that with probability least 1). the point (x*,y²) y²) is such that
1
2w x (Trax
2b
TOo
$6
PP PawDerar ( (Ce. (x" + +A, S Le,, (0
1
x+
S =
22

---

Under review as a conference paper at ICLR 2021
This completes the proof of inequality equation 23
terminates in at most I iterations of its "While" loop, we have EG. (1 + 7)) 25* S co + 7) S This completes the proof on Inequality equation 24
Finally we note that when Algorithm
L
We complete the proof of the main theorem:
Proof of Theorem 2.3 First, by Lemma D.7 our algorithm converges to point (z* ,y") after
most (T) log( Tuaa. 4r maxxx 1) (I by bo b²) gradient and function evaluations, which is polynomial in 1/e, d, b, L1, L. In particular, for L, b 2 1, the number of gradient and function evaluations is L ".
if we set E* Ei,, we have that Inequalities equation 34 and equation 35 hold for e* E [2,66 with probability at least 2w - 2w x (Fmax
By Lemma D.9
2b
+ 1) T0
E SIMULATION SETUP
In this section we discuss the neural network architectures, choice of hyperparameters, and hardware used for both the real and synthetic data simulations.
Datasets. We evaluate the performance of our algorithm both real-world and synthetic data. The real-world datasets used are MNIST and CIFAR-10. In one of our MNIST simulations we train our algorithm on the entire MNIST dataset, and on the remaining simulations the MNIST dataset which includes only the digits labeled 0 or (note however that the algorithms do not see the labels). For simplicity, we refer this dataset as the 0-1 MNIST dataset.
train on the subset of
The synthetic dataset we use consists of 512 points points sampled at the start of each simulation from a mixture of four equally weighted Gaussians in two dimensions with standard deviation 0.01; and means positioned at (0, 1), (1, 0), (-1,0) 0) and (0, -1).
Gowdffllowo et al. (2014) and Metz et al. (2017), we use the cross entropy loss function for training, where f(r,, y) = log (c)())
For all of our simulations on both real and synthetic datasets,
log(1- - D., (G where z are the weights of the generator's ' neural network and are the weights of the discriminator's neural network, where C is sampled from the data distribution, and & is
Gaussian with identity covariance matrix. The neural network architectures and hyperparameters' for both the real and synthetic data simulations are specified in the following paragraphs.
Hyperparameters for MNIST simulations. For the MNIST simulations, we use a batch size of 128, with Adam learning rate of 0.0002 and hyperparameter 31 0.5 for both the generator and discriminator gradients. Our code for the MNIST simulations is based on the code of Renu Khandelwal Khandelwal (2019) and Rowel Atienza Atienza (2017), which originally used gradient descent ascent and ADAM gradients for training.
For the generator we use a neural network with input of size 256 and hidden layers, with leaky RELUS each with "alpha" parameter 0.2 and dropout regularization of 0.2 at each layer. The first layer has size 256, the second layer has size 512, and the third layer has size 1024, followed by an output layer with hyperbolic tangent ("tanh") acvtivation.
For the discriminator we use a neural network with hidden layers, and leaky RELUS each with "alpha" parameter 0.2, and dropout regularization of 0.3 (for the first two layers) and 0.2 (for the last layer). The first layer has size 1024, the second layer has size 512, the third layer has size 256, and the hidden layers are followed by a projection to dimension with sigmoid activation (which is fed as input to the cross entropy loss function).
Hyperparameters for Gaussian mixture simulations. For the simulations Gaussian mixture data, we have used the code provided by the authors Metz et al. (2017). which uses a batch size 512, Adam learning rates of 10-3 for the generator and 10 for the discriminator, and Adam parameter 3 0.5 for both the generator and discriminator
"Note that the authors also mention using slightly different ADAM parameters and neural network architecture in their paper than in their code; we have used the Adam parameters and neural network architecture provided in their code.
23

---

Under review as a conference paper at ICLR 2021
We use the same neural networks that were used in the code from Metz et al. (201)): The generator uses a fully connected neural network with 2 hidden layers of size 128 and REL activation, followed by linear projection to two dimensions. The discriminator uses fully connected neural network with hidden layers of size 128 and RELU activation, followed by linear projection to dimension (which is fed as input the cross entropy loss function). As in the paper |Metz al. (2017), initialize all the neural network weights to be orthogonal with scaling 0.8.
Hlpperparameters for CIFAR-10 simulations. For the CIFAR-10 simulations, we a batch size of 128, with Adam learning rate of 0.02 and hyperparameter B1 = 0.5 for both the generator and discriminator gradients. Our code for the CIFAR-10 simulations based on the code of Jason Brownlee (2019), which originally used gradient descent ascent and ADAM gradients for training.
For the generator we use neural network with input of size 100 and 4 hidden layers. The first hidden layer consists of a dense layer with 4, 096 parameters, followed by a leaky RELU layer, whose activations are reshaped into 246 4 x 4 feature maps. The feature maps are then upscaled to an output shape of 32 x 32 via three hidden layers of size 128 each consisting of a convolutional Conn2DTrunspose layer followed by leaky RELU layer, until the output layer where three filter maps (channels) are created. Each leaky RELU layer has "alpha" parameter 0.2.
For the discriminator, we layers. The first four hidden layers each consist of a convolutional Com22Dranspos layer followed by leaky RELU layer with "alpha" parameter 0.2. The first layer has size 64, the next two layers each have size 128, and the fourth layer has size 256. The output layer consists of a projection to dimension with dropout regularization of 0.4 and sigmoid activation function.
neural network with imput of size 32 32 x 3 followed by 5 hidden
FID scores were computed every 2500 iterations. To compute each FID score we used 10,000 randomly selected images from the CIFAR-10 dataset, and 10,000 generated images.
Setting hyperparameters. In our simulations, our goal was to be able to use the smallest number of discriminator or unrolled steps while still learning the distribution in short amount of time, and we therefore decided to compare all algorithms using the same hyperparameter k. To choose this single value of k we started by running each algorithm with discriminator steps until one of the algorithms was able to learn the distribution consistently in the first 1500 iterations. This resulted in a choice of k for the MNIST datasets and a choice of k for the Gaussian mixture model data. For the 110AR-10 dataset we simply used k 1 for both algorithms (since for CIFAR-10 10 is difficult to visually determine if all modes were learned).
1 and increased the number of
Our temperature hyper-paramede parameter was set by running our algorithm with temperatures in the set {1,2,3, 4, 5, 10), and choosing the temperature which gave the best performance.
Hardware. Our simulations the MNIST, 0-1 MNIST, and Gaussian datasets were performed on four 3.0 GHz Intel Scalable CPU Processors, provided by AWS.
Our simulations on the CIFAR-10 dataset were performed on one GPU with High frequency Intel Xeon E5-2686 v4 (Broadwell) processors, provided by AWS.
F ADDITIONAL SIMULATION RESULTS
In this section we show additional results from simulations which we did not have space to include in the main body of the paper.
F.1 OUR ALGORITIIM ON THE FULL MNIST DATASET
Here we show the results of the simulation of our algorithm on the full MNIST dataset (Fig. 4)
F.2 OUR ALGORITIM AND GDA TRAINED ON THE CIFAR- 10 DATASET.
In this section we show the results of all the runs of the simulations of our algorithm and GDA on the CIFAR-10 dataset, which were mentioned in Section 3.1 (Figures and [).
24

---

Under review as a conference paper at ICLR 2021
Figure 4:
We ran our algorithm (with & discriminator steps and acceptance rate - () on the full MNIST dataset for 39,000 iterations, and then plotted images generated from the resulting generator. We repeated this simulation five times; the generated images from each of the five runs are shown here.
F.3 OUR ALGORITHM TRAINED ON THE 0-1 MNIST DATASET.
Here we show the results of the simulations of our algorithm on 0-1 MNIST which were mentioned in Section 3.1 (Figures and 8).
F.4 COMPARISON WITH GDA ON MNIST
In this section we show the results from the different runs of the simulations of our algorithm and
GDA on the 0-1 MNIST dataset, which were mentioned in Section 3.2 (Figures 9 and 10)
F.5 RANDOMIZED ACCEPTANCE RULE WITH DECREASING TEMPERATURE
In this section we give the simulations mentioned in the paragraph towards the beginning of Section 3 which discusses simplifications to our algorithm. We included these simulations to check whether our algorithm also works well when implemented using a randomized acceptance rule with a decreasing temperature schedule.
F.6 COMPARISON OF ALGORIHTS ON MIXTURE OF 4 GAUSSIANS
In this section we show the results of all the runs of the simulation mentioned in Figure 2 where all the algorithms were trained on a 4-Gaussian mixture dataset for 1500 iterations. For each run, we plot points from the generated distribution at iteration 1,500. Figure 13 gives the results for GDA with discriminator step. Figure gives the results for GDA with k = 6 discriminator steps. Figure 15 gives the results for the Unrolled GANs algorithm. Figure T6 gives the results for our algorithm.
25

---

Under review as a conference paper at ICLR 2021
GDA
Our Algorithm
Figure 5: GAN trained using algorithm (with & 1 discriminator steps and acceptance rate 4/- = 1/2) and GDA. We repeated this simulation nine times; we display here images generated from the resulting generator for each of the nine runs of GDA (top) and our algorithm (bottom). The final FID scores at 50,000 iterations for each of the nine runs (corresponding to the images above from left right and then top bottom) (33.0, 197.1, 34.3, 34.3, 33.8, 37.0, 45.3, 31.7, 34.73 GDA.
[35.6, 36.3, 33.8, 35.2, 34.5, 36.7, 34.9, 36.9, 36.6) for algorithm and
26

---

Under review as a conference paper at ICLR 2021
200
FID score
100
0 OK
20K iteration
40K
Figure 6: Plots of FID for GANs trained using algorithm (with k discriminator steps and acceptance rate e e/1/- 1/2) and GDA CIFAR-10 for 50,000 iterations. We repeated this simulation nine times, and plotted the FID scores for algorithm (dashed blue) and GDA (solid red).
Our algorithm
1,500
O
O
D
C
D
2,000
5,000
10,000
O
0
0.8
We trained our algorithm on the 0-1 MNIST dataset for 30,000 iterations (with k = discriminator steps and acceptance rate e = 4). We repeated this experiment five times. For one of the runs, we plotted 25 generated images produced by the generator at various iterations. We also plotted moving average of the computed loss function values, averaged over window size of 50.
Figure 7:
Figure 8: We show the images generated the 30,000'th th iteration for all runs of the simulation in Figure together with a plot of their computed loss function values. Recall from the caption of Figure that we trained our algorithm on the 0-1 MNIST dataset for 30,000 iterations (with
discriminator steps and acceptance rate = }) We repeated this experiment five times. For one of the runs, we plotted generated images produced hy the generator at various iterations. We also plotted a moving average of the computed loss function values, averaged over window size of 50.
27

---

Under review as a conference paper at ICLR 2021
Figure 9: Images generated at the 1000'th iteration the 13 runs the GDA simulation mentioned in Figure In 77% of the runs the generator seems to be generating only I's at the 1000'th th iteration.
Figure 10: Images generated at the 1000'th th iteration of each of the 22 runs of our algorithm for the simulation mentioned in in Figure
0
0
8
0
0
500
1,000
1,500
2,000
O
Q [
0
8
O
C
/
5,000
10,000
20,000
39,000
Figure 11: In this simulation we used a randomized accepUreject rule, with a decreasing temperature schedule. The algorithm was run for 39,000 iterations, with temperature schedule of steps which decreased the computed value of the loss function were accepted with probability 1, and proposed steps which increased the computed value of the loss function were rejected with probability max(0, 1 e - at each iteration i. We ran the simulation 5 times, and obtained similar results each time, with the generator learning both modes, In this figure, we plotted the generated images from one of the runs at various iterations, with the iteration number specified the bottom each figure (see also Figure for results from the other four runs)
(1/2000))) Proposed
28

---

Under review as a conference paper at ICLR 2021
e
0
O
e
0
A
6
O
/
O
O
O
7
0
Figure 12: Images generated the 39,000'th th iteration of each of the runs of our algorithm for the simulation
mentioned in Figure
with randomized acceptance rule with a temperature schedule of (+e(x/20000)
GDA
The generated points at the 1500'th th iteration for all 9 of the GDA algorithm with 1 discriminator step. simulation mentioned Figure the 1500'th iteration, GDA had learned exactly one mode for each of the runs.
Figure 13:
GDA with 6 discriminator steps
Figure 14: The generated points at the 1500'th th iteration for all 20 runs of the GDA algorithm, with h 6 discriminator steps, for the simulation mentioned in Figure At the 1500'th iteration, GDA had learned two modes 65% of the runs, one mode 20% of runs, and four modes 15 % the runs.
Unrolled GANs with 6 unrolling steps
P
Figure 15: The generated points at the 1500'th 'htt iteration for all 20 runs of the Unrolled GAN algorithm for the example in Figure with l 6 unrolling steps. By the 1500'th th iteration, Unrolled GANs learned one mode 75% of the runs, modes 15% of the runs, and three modes 10% of the runs.
Our algorithm
Figure 16: The generated points at the 1.500'th iteration for all 19 runs of our algorithm, for the simulation mentioned in Figure 2 Our algorithm used ào = 6 discriminator steps and an acceptance rate hyperparameter of 1. By the 1500 th iteration, algorithu seems have learned all four modes 68% of the runs, three modes 26% of the runs, two modes 5% runs.
29

---

Under review as a conference paper at ICLR 2021
G EXTENSION TO FUNCTIONS WITH COMPACT CONVEX SUPPORT
In this section we introduce a version of our algorithm (Section G.1
for loss functions with compact convex support, and run it simple bilinear loss function (Section G.2). We also introduce a version of our g-local min-max equilibrium (Section G.3p which applies to loss functions with
compact convex support. We then show that, if is also convex-concave, then, for 0, this e-local min-max equilibrium is equivalent to global min-max point (Section G.4).
G.1 PROJECTED GRADIENT MIN-MAX ALGORITHM FOR COMPACTLY SUPPORTED LOSS
Algorithm 4 Algorithm for min-max optimization on compact support
input: stochastic zeroth-order oracle F' for loss function f X y + R where X. y S Rd compact convex sets. Stochastic gradient oracles G2 for V.J, and G, for Vyf- Projection oracles Px R + X for X and Py R y for y. An initial point (z. y) X x V and an error parameter E.
output: A point (x*,"" hyperparameters:
Tmax
(maximum
number
rejections),
7
Set + 0,i00
while S Tmax do
fold - F)r,y), iti+1
Set G2 (2, y) [Compute stochastic gradient)
Set x' Px r/,,) {Compute the proposed update for the min-player)
Starting at point y, use stochastic gradients Gy(a', )) to multiple projected gradient ascent
steps in the y-variable, until point y' is reached such that [G,((',, ,/) S (Simulate max- player's update)
Set +0
Set t y and Stop False
while Stop False do
Set j t j
Set gy.j (x((Xyj)
if 1 Ily Pyly 19y.)ll2 > e' then
n Šet j t j+1
Sety t Pyly - (g (Simulate max-player's update via projected gradient ascent)
else
Set Stop = True
Set fnew F(x', y²) {Compute the new loss value)
Set Accept - True.
if fnow > fold - 6/2, Accept False {accept or reject]
if Accept = True then Set x +- x', +- y', +- 0 {Accept the updates)
else Setr
(Reject the updates, and track how many successive steps were rejected.)
return (x. y)
G.2 NUMERICAL SIMULATION ON COMPACTLY SUPPORTED BILINEAR FUNCTION
In this appendix, we discuss numerical simulations on the bilinear loss function f(x, v) = ry with compact support (x. y) E [-1,1] x [1,, For this function, the gradient descent-ascent algorithm known to diverge away from the global min-max point (see for instance Jin et al. (2020)).
This function has global min-max point at every point in the set {(x, y) x = 0, y E [-1, 1]}. We ran Algorithm on this function with hyperparamters 7 0.2, F(x,y) y) = f(z y). gradient oracle Gz,
0.06. and Tmax 5, value oracle (z, y) = Vyf fx. y). stochastic gradient oracle Va,((r, y) + where & ~ (0, 1), and initial point (æ, y) = (0.4. 0.4). After 341 iterations of the outer loop, our algorithm reached the point (0.0279, -0.9944), which very close to one of its true global max-max points, (0,- 11)
30

---

Under review as a conference paper at ICLR 2021
G.3 LOCAL MIN-MAX EQUILIBRIUM FOR COMPACTLY SUPPORTED LOSS FUNCTIONS
Global min-max point. First, we recall the definition of global min-max point:
Definition G.1. We say that (x" (x")"")= E Xxy is global min-max point for fufuctionn f xx>y -
if
f(x". )²== max f(x"
yEY
and
f(a", = min max [(x, v).
=E yEy
Local min-max equilibrium for projected subgradients. In this section introduce version of the local min-max equilibrium which applies to compactly supported loss functions (Definition G.3). The main difference with our previous definition (Definition 2.2 is the need for projected gradient to deal with the compact support of the objective function.
In the following we assume that f X' y IR, where X' y I2d are two compact convex sets, and that f is continuously differentiable on X' x V. We denote by V the projected gradient in the variable for the set y
We first formally define "simulated loss" and what it means for f to increase rapidly.
Definition G.2. For any z,y, and > O, define ElE,x,y) S. to be points w s.t. there continuous and (except at finitely many points) differentiable path 7(t) contained in y starting at ending at w, and moving with "speed" at most 1 in the -norm, (1) S such that at
any point on %
10
J (()), >
(33)
We define Le y) == suPwES(e.a.)) f(z, w), and refer to it as the simulated loss.
Definition G.3. Given a distribution Da.g. with Pra-Da,s (x + A X) for each x. y E TR.. and e* 2 0, we say that (x" ,y") is an E* elocoall min-max equilibrium with respect to the distribution D if
1 . I11 SE: and PrA-Da (fe. (x* + A,V") < fe -0a=,v")='' Se",
(34)
(35)
Remark G.A. As simple application of Algorithm 4 consider the bilinear loss function f(x, y) xy where x and are constrained to the set - 2 1t is easy to see that the set of global min-max
points consists of the points (z, y) where x = 0 and is any point in 2 2. The local min-max equilibria according to our definition are the set of points (x, y) where x is any point [-e, E) and y is any point in 11 2
This is because, when running Algorithm oon this example, if x is outside the set [-E,e], the max- player will follow increasing trajectory to always return a point y - or y = which means that, roughly speaking, the min-player is attempting to minimize the function 2z This means that the algorithm will accept all updates x
A for which f Al < =// implying that the algorithm
converges towards a point with |x] S. &.
Thus, as goes zero, the set of local min-max equilibrium points coincides with the set of global min-mas optima for the function f(z, y) zy.
This latter fact holds more generally for any conver-concave function with compact convex domain (see Theorem G.5).
G.4 COMPARISON OF LOCAL MIN-MAX AND GLOBAL MIN-MAX IN THE COMPACTLY SUPPORTED CONVEX-CONCAVE SETTING.
The following theorem shows that, in the compactly supported convex-concave setting, a point (a* yy" a local min-max equilibrium for (in the sense of Definition G.3) if and only it is global min-max point:
II other words there is some 7 2 0 such that y : 00, 7] + V.
In this equation the derivative is taken from the right.
31

---

Under review as a conference paper at ICLR 2021
Theorem G.5. Let f: x - R be convex-concave, where X.Y C Rd are compact convex sets. And let Da.y be continuous distribution with support on y such that, for every (x. y) E X x V, Day there is some open ball C. Rd containing a such that Dz,y has non-zero probability density at every point in B eny. Then (x* ,2") is E-local min-max equilibrium for e = 0 if and only if it is a global min-max point.
Proof. Define the "global max" function (xx)) == maXzEy f(z y) for all E X. We start by showing that the function (xx) is convex on the convex set X. Indeed, for any 21, 22 E X and any [0, 1] we have
(Axa + (1 - A)22)
max s(xx + (1 1)
vey
I max v) + (1 ()2 w)1
vEy
S Xmax f(11, v)] + (1 1)ma f(22,))] VEy
vEy
= Ar)(21) + +(1 - (x))
where the second inequality holds by convexity of f(:,)).
Moreover, we note that, since, for all æ E X. f(x, .) is continuously differentiable on compact convex set, every allowable path (with parameter E endpoint ú has projected gradient V (x*, = 0.
can be extended to allowable path whose
Therefore, for every (z, y) E X x V, there exists an allowable path with initial point y whose endpoint y satisfies
f(,,0) = 0.
(36)
Since f(x,-) is concave, equation 36 implies that
f(z. 9) max f(z, v). yEy
(37)
and hence that
Lo(o,y) (xx 0)
(38)
Thus, equation 37 and equation 38 immly that
Co(x. y) (x)
V(r.y) E xxx
(39)
since vbxx) maxyey (x.
1. First we prove the "only if" direction:
Suppose that (x*, vy") is e-local min-max equilibrium of for = 0. Let y be global maximizer of the function f(*"..) (the function achieves its global maximum since is continuous and y is compact). Then the projected gradient at this point is
V f=="" v') 0.
(40)
Since f(r,) is concave for all æ, and V fx"" y²) O, every point y along the line [yt, y²] connecting the points yt and y equation 40 implies that
sy v) = 0, Vy E ,"".
(41)
Therefore, equation 41 implies that
f(x",y²) f(x",'""
and hence that
f(x"
max f(x", (x="1) v),
(42)
DEy
since max f(x v) [xxx,="))
32

---

Under review as a conference paper at ICLR 2021
Now, since (x", yy* is e-local min-max equilibrium for 0, [oo("* + +,,"" < Lo( ,y)) 0.
Pr AnD "g
(43)
Thus, equation 39 and equation 49 together imply that
Pr AND Da".""
(0 A) (x(x)]] 0.
(44)
Since v is convex, and since there is an open ball B for which D w has non-zero probability density every point Bny, equation equation implies that æt is global minimizer for th:
(xxx)
min (x). øEA
(45)
Therefore, equation 42 and equation 45 immply that (x", is a global min-max point for f: X' IR whenever (x*."" .y" a e-local min-max equilibrium of f for & 0.
2. Next, we prove the "if" direction:
Conversely, suppose that (x", .y") is a global min-max point for f X x y - R. Then f(x", maxzey f(x v). Since f is differentiable on X' V, this implies that
V f(=", v²) O.
(46)
Moreover, since f(x", v²) ) is a global min-max point, we also have that
f(x", = min sex
max fxx v))
min ((x), x
DEy
and hence that
(xx")
min (z)).
(47)
#ex
Since we have already shown that vó is convex, equation 47 implies that
Pr
[+(++A1 < (b(x))]] = 0.
(48)
AND
Since we have also shown in equation 39 that vb(x)) = Lo(x, y) for all (x, E X x y, equation 48 implies that
Pr AND
[Lo( + +A,)) < Lu(x", "(lxtv"")) = 0.
(49)
Therefore, equation 46 and equation 49 imply that, for s = 0, (x* (w"))") IR whenever (a* .y") is global min-max point for f.
) is a e-local min-max
equilibrium of X y
H COMPARISON TO OTHER MIN-MAX ALGORITHMS WITH MAXIMIZATION SUBROUTINES
Many algorithms for min-max games can viewed as using an inner maximization subroutine (c.g., unrolled GANs Metz et al. (2017), and even versions of the GDA algorithm where the max- player's update computed using multiple gradient ascent steps Goodfellow et al. (2014), as well as Maheswaranathan al. (2019); Bolte et al. (2020).. However, in contrast to these algorithms, algorithm has polynomial -ime guarantees on the number of gradient and function evaluations when is bounded with Lipschitz Hessian.
In particular, while Bolte et al. (2020) provides theoretical guarantees, there are two key differences between their work and ours: (i) Their min-max algorithm (Algorithm 3 in their paper) requires
33

---

Under review as a conference paper at ICLR 2021
access to oracle which returns the global maximum argmax,, f(z, y) for any input However, since f can be nonconcave in y, computing the global maximum may be intractable and one therefore may not have access to oracle for the global maximum value in practice. In contrast, only requires access to a (stochastic) oracle for the gradient and function value of f. (ii) Bolte et al. (2020) only prove that their algorithm converges asymptotically, and do not provide any bounds the time to convergence. In contrast, our algorithm has polynomial-tine guarantees on the number of gradient and function evaluations.
algorithm
I COMPARISON TO MIN-MAX ALGORITHMS WITH CONVEREGENCE GUARANTEES IN NONCONVEX DONCONVEX-NONCONCANC -NONCONCAVE SETTINGS
Multiple works provide min-max optimization algorithms with convergence guarantees in various settings where f may nonconvex-nonconcave. However, the convergence results in these works still require strong assumptions on the loss function. For instance, MMrtikopouloss et al. (2019): Lin al. (2018); Gidel et al. a (2019a) provide convergence guarantees under the assumption that f satisfies variational inequality, such as the "coherence" condition of Mertikopoulos al. (2019). Specifically, one the assumptions of this coherence condition is that there exists a global min-max solution point (z* ) for min, maxy [z, which satisfies the variational inequality (V,,(I, 2),
(V,f(z, y). w²) 2 for all (Ir, 3) in d Rd. This is relatively strong assumption since it says that at every point (ar, v) E Rd x Rd, the vector field V v), (x, v)) must not point direction "away" from the global min-max point (x". yy""
Another setting where convergence guarantees have been show for min-max algorithms in the nonconvex-nonconcan setting is when f satisfies a "sufficient bilinearity" condition Abermethy et al. (2019). Roughly, this condition says that there is number 7 2 such that, at every Z, R all the singular values of the cross derivative fxz y) are greater than 7. If, in addition, f is 1 1-Lipschitz then (Abernethy et al. (2019) show that their algorithm reaches first-order e-stationary point-that is a point where the gradient for the min- and max- players has magnitude at most e-in roughly O log(E)) evaluations of Hessian-vector product of
In contrast to these works, our main result only assumes that the loss function is bounded with Lipschitz Hessian.
34


Reviews:
[{"review_id": "wJZi_DL_h9O", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper introduces a first-order algorithm for nonconvex-nonconcave min-max optimization problems. The proposed algorithm terminates in time polynomial in the dimension and smoothness parameters of the loss function. The points (x*,y*) returned by the algorithm satisfy the following guarantee: if the min-player proposes a stochastic gradient descent update to x^*, and the max-player is allowed to respond by updating y^* using any “path” that increases the loss at a rate of at least \\epsilon with high probability, the final loss cannot decrease by more than \\epsilon. Then the algorithm is tested in GANs settings on mixtures of Gaussians, MNIST and CIFAR-10 datasets against compared against gradient/ADAM descent ascent and Unrolled GANs. The algorithm is shown to be significantly more stable than GDA (e.g. less mode collapse, cycling, and more stable digit generation).  \n\nThe paper works on the hard and ambitious problem of general non-convex non-concave optimization which has multiple AI applications such as GANs. On the proposed approach is novel considering a new solution concept and the paper provides some theoretical and experimental results. On the negative side neither the theoretical nor the experimental results seem particularly strong. \n\nMy main issue on the theoretical side has to do with the solution concept itself. The solution concept seems unnatural to me. Definition 2.1 about \\El_\\eps(x,y) a critical notion about the ``path\" that the max-agent is allowed to use is non-constructive and obtuse. The only closely related solution concept seems to be in a recent unpublished manuscript by Mangoubi and Vishnoi. Given the novelty of the solution concept I think the authors should have spent much more time building intuition about what this concept corresponds to especially in simple settings such as bilinear zero-sum games. It seems that effectively all states satisfy the definition of the provided solution concept in a bilinear game. E.g. suppose that we are arbitrarily far from the max-min equilibrium, the min agent suggests a small improvement step now the max agent can move in the direction of the gradient for arbitrarily long distance negating any gains by the small move of the min agent. This is clearly unnatural and explains why this algorithm can terminate fast, it is because it is willing to accept arbitrarily bad states as solutions. I think that this is a major shortcoming of the solution concept. The authors seem to agree that the solution concept is rather bad at times by explicitly allowing the dynamic to escape from these points with some small probability. The theoretical analysis is definitely non-trivial but if the proposed algorithm fails to solve even simple bilinear zero-sum games then the theoretical guarantees are not particularly strong. \n\nOn the experimental side, the algorithm is being compared against weak benchmarks such as GDA. As the paper itself presents in the related work there have been a lot of recent developments on variations to the standard GDA techniques such as extra-gradient, optimistic methods, different types of averaging, etc which are known to significantly and robustly outperform GDA both theoretically and experimentally across numerous datasets. The reported FID scores are far from the state of the art and even the visual samples seem of relatively poor quality.\n\nOverall, I believe the paper attacks a very hard problem and pursues an interesting idea but both the theoretical and experimental results seem to suggest to me that the proposed approach is not very promising.", "extra_scores": {}, "extra_text": {}}, {"review_id": "TL5WmAu2YON", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper proposes a new stochastic gradient descent-ascent-based method to approximate a stationary point (or local min-max solution) of a nonconvex-nonconcave minimax problem with application in GANs. The method is similar to the one in the GAN original paper, but the authors incorporate it with an acceptance rule and use a different model for the max problem. The algorithm also uses ADAM instead of standard SGD. The authors also provide some convergence guarantee to a local min-max point in polynomial-time complexity. Unfortunately, the reviewer was unable to verify the proof due to the time limit.\n\nThe reviewer finds that it is really hard to understand the proof techniques as well as the meaning of local min-max points defined in this paper especially via a neighborhood D_{x*,y*}. Many places are explained in words which are also hard to verify some of the statements. For example, Theorem 2.3 expresses the complexity in poly(...), which does not know what is the maximum order of epsilon. The proofs are also breaking into different pieces where so many technical details related to high probability statements are used. This makes another difficulty to check the correctness. To this end, the reviewer would like to raise the following question?\n1. First, since the problem is nonconvex-nonconcave,  how can the algorithm guarantee that the min-play can always decrease the objective function with a certain amount that is fixed as stated in (5)?\n2. Second, it is known that ADAM is not convergent even on a convex problem (see (https://openreview.net/pdf?id=ryQu7f-RZ)), do the authors use a modified variant of ADAM, or what has been changed to guarantee its convergence?\n3. Third, in Definition 2, does D_{x*,y*} form a \"full\" neighborhood of (x*,y*) in the feasible set of f(x, y)?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "DlcquFUQr6b", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper treats non-convex/non-concave min/max problems motivated by the respective problems that arise in GAN training. The main contribution is that they develop an ADAM-based algorithm that converges to \\eps- local min/max points. The paper seems to be well-written and easy to follow. Moreover the proofs seem correct and sound. That said, my main concerns about this paper are twofold: \n\n1.The idea of dividing the min/max game into minimization/maximization problems is not new (see for example: Bolte et al. (2020) A Hölderian backtracking method for min-max and min-min problems). Therefore, a reasonable question would be how this work is related with this kind of results.\n2. Additionally, it is not true that Extra-Gradient are only applicable for convex-structured problems (see for example: Mertikopoulos et. al ICLR (2019), Yu Guan Hsieh et.al NeuRIPS (2019)). Hence, I think a more detailed justification towards these approaches is needed.\n\nOverall, without being an expert myself, I would gladly raise my score if the author(s) clarify these issues in a more detailed manner.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: All reviewers appreciated the main idea in the paper for solving the nonconvex-nonconcave minimax problems, which is deemed an extremely hard open problem. However, as R1 also pointed out, neither the theoretical nor the experimental results seem particularly strong, given that many variations of GDA and theoretical understanding of different notions of optimality have been recently developed. The paper fails to draw proper comparisons to these existing work. 
Unfortunately, the paper is slightly below borderline and cannot be accepted this time. 

Decision: Reject