Towards Better Understanding of Adaptive Gradient Algorithms in Generative Adversarial Nets
Authors: Mingrui Liu
Youssef Mroueh
Jerret Ross
Wei Zhang
Xiaodong Cui
Payel Das
Tianbao Yang
Venue:  (2020)
Keywords: Generative Adversarial Nets
Adaptive Gradient Algorithms

Abstract: Adaptive gradient algorithms perform gradient-based updates using the history of gradients and are ubiquitous in training deep neural networks. While adaptive gradient methods theory is well understood for minimization problems, the underlying factors driving their empirical success in min-max problems such as GANs remain unclear. In this paper, we aim at bridging  this gap from both theoretical and empirical perspectives. First, we analyze a variant of Optimistic Stochastic Gradient (OSG) proposed in~\citep{daskalakis2017training} for solving a class of non-convex non-concave min-max problem and establish $O(\epsilon^{-4})$ complexity for finding $\epsilon$-first-order stationary point, in which the algorithm only requires invoking one stochastic first-order oracle while enjoying state-of-the-art iteration complexity achieved by stochastic extragradient method by~\citep{iusem2017extragradient}. Then we propose an adaptive variant of OSG named Optimistic Adagrad (OAdagrad) and reveal an \emph{improved} adaptive complexity $O\left(\epsilon^{-\frac{2}{1-\alpha}}\right)$, where $\alpha$ characterizes the growth rate of the cumulative stochastic gradient and $0\leq \alpha\leq 1/2$. To the best of our knowledge, this is the first work for establishing adaptive complexity in non-convex non-concave min-max optimization. Empirically, our experiments show that indeed adaptive gradient algorithms outperform their non-adaptive counterparts in GAN training. Moreover, this observation can be explained by the slow growth rate of the cumulative stochastic gradient, as observed empirically.

Published as a conference paper at ICLR 2020
TOWARDS BETTER UNDERSTANDING OF ADAPTIVE GRADIENT ALGORIHTMS IN GENERATIVE ADVER- SARIAL NETS
Mingrui Liu'r Youssef Mrouch", Jerret Ross", Wei Zhang", Xiaodong Cui', Payel Das", Tianbao Yang* 1 Department of Computer Science, The University of lowa, lowa City, IA, 52242, USA 2 IBM T. J. Watson Research Center, Yorktown Heights, NY, 10598, USA
ABSTRACT
Adaptive gradient algorithms perform gradient-based updates using the history of gradients and are ubiquitous in training deep neural networks. While adaptive gradient methods theory is well understood for minimization problems, the under- lying factors driving their empirical success in min-max problems such as GANs remain unclear. In this paper, we aim at bridging this gap from both theoretical and empirical perspectives. First, we analyze variant of Optimistic Stochastic Gradient (OSG) proposed in (Daskalakis et al., 2017) for solving class of non- convex non-concave min-max problem and establish O complexity for find- ing e-dirst-order stationary point, in which the algorithm only requires invoking stochastic first-order oracle while enjoying state-of- the-art art iteration complex- ity achieved by stochastic extragradient method by (lusem et al., 2017). Then we propose adaptive variant of OSG named Optimistic Adagrad (OAdagrad) and reveal an improved adaptive complexity O (CF=), where a characterizes the growth rate of the cumulative stochastic gradient and 0 < S 1/2. To the best of our knowledge, this the first work for establishing adaptive complexity in non- convex non-concave min-max optimization. Empirically, our experiments show that indeed adaptive gradient algorithms outperform their non-adaptive counter- parts in GAN training. Moreover, this observation can be explained by the slow growth rate of the cumulative stochastic gradient, as observed empirically.
INTRODUCTION
Adaptive gradient algorithms (Duchi et al., 2011; Tieleman & Hinton, 2012: Kingma & Ba, 2014; Reddi et al., 2019) are very popular in training deep neural networks due their computational efficiency and minimal need for hyper-parameter tuning (Kingma & Ba, 2014). For example, Ada- grad (Duchi et al., 2011) automatically adjusts the learning rate for each dimension of the model parameter according to the information of history gradients, while its computational cost is almost the same as Stochastic Gradient Descent (SGD). However, supervised deep learning (for ex- ample. image classification tasks using a deep convolutional neural network), there is not enough evidence showing that adaptive gradient methods converge faster than its non-adaptive counterpart (i.e.. SGD) on benchmark datasets. For example, it is argued in (Wilson al., 2017) that adaptive gradient methods often find a solution with worse performance than SGD. Specifically, Wilson et al. (2017) observed that Adagrad has slower convergence than SGD in terms of both training and testing error, while using VGG (Simonyan & Zisserman, 2014) on CIFAR10 data.
GANs (Goodfellow et al., 2014) are a popular class of generative models. In a nutshell, they consist of a generator and a discriminator, both of which are defined by deep neural networks. The gen- erator and the discriminator are trained under an adversarial cost, corresponding non-concave min-max problem. GANs are known to be notoriously difficult to train. In practice, Adam (Kingma & Ba, 2014) is the defacto optimizer used for GAN training. The common op- timization strategy is to alternatively update the discriminator and the generator (Arjovsky et al.,
non-convex
CCoresponddnnce mi ngrui -1 1uuuii owa edu

---

Published as a conference paper at ICLR 2020
2017: Guirajani al., 2017). Using Adam is important in GAN training, since replacing it with non-adaptive methods (e.g. SGD) would significantly deteriorate the performance. This paper stud- ies and attempts to answer the following question:
Why do adaptive gradient methods outperform their non-adaptive counterparts in GAN train- ing?
We analyze a variant of Optimistic Stochastic Gradient (OSG) in (Daskalakis & Panageas, 2018) and propose adaptive variant named Optimistic Adagrad (OAdagrad) for solving class of non- convex non-concave min-max problems. Both of them are shown to enjoy state-of-the-ar complex- ities. We further prove that the convergence rate of OAdagrad to an e-first-order stationary point depends on the growth rate of the cumulative stochastic gradient. In our experiments, we observed an interesting phenomenon while using adaptive gradient methods for training GANs: the cumula- tive stochastic gradient grows at a slow rate. This observation is in line with the prediction of our theory suggesting improved convergence rate for OAdagrad in GAN training, when the growth rate of the cumulative stochastic gradient is slow.
Since GAN is a min-max optimization problem in nature, our problem of interest is to solve the following stochastic optimization problem:
min max F(u, v) == REED v;),,; uell veV
where U. V are closed and convex sets, F(u, v) is possibly non-convex in u and non-concave in v. & is a random variable following an unknown distribution D. In GAN training, u, v represent the parameters of generator and discriminator respectively.
The ideal goal for solving (I) is to find saddle point (u,, E ll x V such that F(u,,v) S v(u..v.) S Fuu, v=) for Vu E U, Vv E V.
To achieve this goal, the typical assumption usually made is that the objective function is convex- concave. When F(u, v) is convex in u and concave in v, non-asymptotic guarantee in terms of the duality gap is well established by a series of work (Nemirovski & Yudin, 1978; Nemirovski, 2004; Nesterov, 2007; Nemirovski et al., 2009; Juditsky et al., 2011). However, when F(u, v) is non-convex in u and non-concave in v. finding the saddle point is NP-hard in general. Instead, we focus on finding the first-order stationary point provided that the objective function smooth. Le. aim to find (u, v) u x V such that V.F(u, v) O. F(F = O. Note that this is necessary condition for finding the (local) saddle point.
Related Work. Several works designed iterative first-order deterministic (Dang & Lan, 2015) and stochastic (lusem et al., 2017; Lin et al., 2018) algorithms for achieving the c-first-order sta- tionary point with non-asymptotic guarantee. The goal is to find x such that [[((x)] I or [[[[(x)]]] S 6, where the first-order oracle is defined as T(x) = VV, v). F(, v)) with x (u, and the first-order stochastic oracle is the noisy observation of T, i... T(x:
[V.F v: V) Flu, v:] For instance, Dang & Lan (2015) focuses on the deterministic setting. On the other hand, (lusem et al., 2017) develops a stochastic extra tattiigr algorithm that enjoys O(e-)) iteration complexity. The extra-gradient method requires two stochastic first-order oracles in one iteration, which can be computationally expensive in deep learning applications such as GANs. The inexact proximal point method developed in (Lin et al., 2018) has iteration complex- ity O(E-6) for finding an e-first-order stationary point !
To avoid the cost of an additional oracle call in extragradient step, several studies (Chiang et al., 2012; Rakhlin & Sridharan, 2013; Daskalakis et al., 2017: Gidel et al., 2018; Xu et al., 2019) pro- posed single-call variants of the extragradient algorithm. Some of them focus on the convex setting (e.g. (Chiang et al., 2012: Rakhlin & Sridharan, 2013)), while others focus the non-convex set- ting (Xu et al., 2019). The closest to our work is the work by (Daskalakis et al., 2017; Gidel et al., 2018), where the min-max setting and GAN training are considered. However, the convergence of those algorithms is only shown for a class of bilinear problems in (Daskalakis et al., 2017) and for monotone variational inequalities in (Gidel et al., 2018). Hence a big gap remains between the spe- cific settings studied in (Daskalakis et al., 2017; Gidel et al., 2018) 8) and more general non-convex
'The result in (Lin et al.. 2018) assumes the first order oracle 7' is a weakly-monoter operator, which is milder than the Lipschitz-comtinuity assumption as assumed in Jusem et al. (2017). 7). However, simply applying the Lipschitz-comtimuity condition in their proof does not change their iteration complexity.
2

---

Published as a conference paper at ICLR 2020
Assumption
Setting
IC
PC
Guarantee
Extragradient (lusem et 2017)
pscudo-monotomicity
stochastic
O(e-1)
2Tp
e-SP
OMD (Daskalakis al., 2017)
bilinear
deterministic
N/A
Tg
asymptotic
AvgPastFXtraSGI
monotonicity
stochastic
Ole-3)
Tg
e-DG
(Gidel et al., 2018)
OMD
(Mertikopoulos al., 2018)
coherence
stochastic
N/A
2T,
asymptotic
IPP
MVT has solution
stochastic
O(e-9)
Tg
eSSP
(Lin et ul., 2018)
Alternating Gradient
bilinear form
deterministic
O(lug(1/e)
Tg
c-optim
(Gidel et al., 2019)
SVRE
strong-mookoonicity finite sum
stochastic finite sum
O(log(1/e)
(n #)T,"
e-optim
(Chavdarova et al., 2019)
Extragrudient
strong-monotonicity
deterministic
O(log(1/e)
2T,
E-optim
(Azizian et al., 2019)
OSG (this work)
MVI has solution
stochastic
O(e**)
Tg
e-SP
OAdagrad
MVI has solution
stochastic
O(e (()
Tg
c-SP
(this work)
Table 1: Summary of different algorithms with IC (Iteration Complexity), PC (Per-iteration Com- plexity) to find e-SP (e-firstordder Stationary Point), e-DG (e-Duality Gap, i.e. point (ú, v) such that max, F(ú, v) miny F(u, v) S <), e-optim (e-close to the set of optimal solution). T stands for the time complexity for invoking one stochastic first-order oracle.
non-concave min-max problems. Table provides complete overview of our results and existing results. It is hard to give justice to the large body of work on min-max optimization, so we refer the interested reader to Appendix that gives a comprehensive survey related previous methods that not covered in this Table.
Our main goal is to design stochastic first-order algorithms with low iteration complexity, low per- iteration cost and suitable for general class of non-convex non-concave min-max problems. The main tool we use in our analysis is variational inequality.
Let Rd + Rdd be operator and X C Rd is closed convex set. The Stampacchia Variational Inequality (SVI) problem (Hartman & Stampacchia, 1966) is defined by the operator T and X and denoted by SVI(T, X).. It consists of finding x, X' such that (T(x.). x x.) > 0 for Vx E X. A similar one is Minty Variational Inequality (MVI) problem (Minty et al., 1962) denoted by MVI(T, which consists of finding x. such that (T(x), x.) 2 0 for Vx X. Min-max optimization is closely related to variational inequalities. The corresponding SVI and MVI for the min-max problem are defined through T(x) [V,F(u, v). VV. FV, with (u,
Our main contributions are summarized as follows:
Following (Daskalakis et al., 2017), we extend optimistic stochastic gradient (OSG) anal- ysis beyond the bilinear and unconstrained case, by assuming the Lipschitz continuity of the operator T and the existence of solution for the variational inequality MVI(T,X) These conditions were considered in the analysis of the stochastic extragradient algorithm in (lusem al., 2017). We analyze variant of Optimistic Stochastic Gradient (OSG) un- der these conditions, inspired by the analysis of (lusem et al., 2017). We show that OSG achieves state-of-the-ar iteration complexity (L)/e) for finding e-first-order stationary point. Note that our OSG variant only requires invoking one stochastic first-order oracle
2 Note the pseudo-mm monooooinnt assumption used by (lusem et al., 2017) can also replaced by our MVI assumption in their proof. The main difference between our OSG and the stochastic extragradient method in (lusem et al., 2017) is the number of stochastic gradient calculations in each iteration.
'Here the bilinear game defined minuea" max u1 Av a bv where the smallest singular value of E RP* positive, E RTx1 b E R
'Here J., f denote the number of components in the finite structure, Lipschitz constant and strong- monotonicity parameter of the operator of variational inequality respectively.
3

---

Published as a conference paper at ICLR 2020
while enjoying the site---fthhhart iteration complexity achieved by stochastic extragradi- ent method (lusem et al., 2017).
Under the same conditions, we design an adaptive gradient algorithm named Optimistic Adagrad (OAdagrad), and show that enjoys better adaptive complexity 0 O r
where characterizes the growth rate of cumulative stochastic gradient and 0 S 1/2. Similar to Adagrad (Duchi et al., 2011), our main innovation is in considering variable met- rics according to the geometry of the data in order to achieve potentially faster convergence min min-max games. Note that this adaptive com- (i.e., O(1/e")) achieved by OSG. To the best
rate for class of wenccovvx--onncoeee plexity improves upon the non-adaptive of our knowledge, we establish the first known adaptive complexity for adaptive gradient algorithms in class of non-convex non-coneave min-max problems.
We demonstrate the effectiveness of algorithms in GAN training CIFAR10 data. Empirical results identify an important reason behind why adaptive gradient methods be- have well in GANs, which due to the fact that the cumulative stochastic gradient grows in a slow rate. We also show that OAdagrad outperforms Simultancous Adam in sample qual- ity ImageNet generation using self-attention GANs (Zhang et al., 2018). This confirms the superiority of OAdagrad in min-max optimization.
2 PRELIMINARIES AND NOTATIONS
In this section, we fix some notations and give formal definitions of variational inequalities, and their relationship to the min-max problem (1).
Notations. Let X' C Rd be closed convex and |-|| the euclidean norm. We note 1Ix the projec- tion operator. i.c. (x) arg minxex ly x|| Define T(x) VuF(u, v). Fu, v)] with x = (u, v) in problem (1). At every point x E X. we don't 't have access to T(x) and have only access a noisy observations of T(x). That is, (x;;), where & is random variable with distribution D. For the ease of presentation, we use the terms stochastic gradient and stochastic first-order oracle interchangeably to stand for T(x: {) in the min-max setting.
Definition (Monotonicity). An operator T is monotone if (T(x)-T(y)) x-y)
y) 2 0for E X.
An operator T is pseudo-monotone if (T x) 2 0 (T x) 2 f vx,y X. An operator t-strongly-monotonee monotone (T T(y). y) 2 1 for Vx,y E
We give here formal definitions of monotonic operators T and the c-first-order stationary point.
Definition 2 (e-First-Order Stationary Point). A point X is called e-first-order stationary point if [T(x))] < c.
Remark: We make the following observations:
(a). From the definition, it is evident that arrong-monotonicee monotonicity. Assuming SVI has a solution and pseudo-monotonicty of the operator T imply that MVI(T, X) has solution. To see that, assume that SVI has nonempty solu- tion set, i.c. there exists x. such that (T(x),,y - x.) monotonicity means that for every y, (T(x), x) 0 implies (T(y).y x) 2 O, we have (T x.) 2 0 for any y, which means that x, is the solution of Minty variational inequality. Note that the reverse may not true and an example is provided in Appendix G.
monotonicity =pseudo-
-x)) 2 0 for any y. Noting that pseudo-
(b). For the min-max problem (1), when F(u, v) is convex in u and concave in T is mono- tone. And, therefore solving SVI(T, X) is equivalent solving (1). When T is not mono- tone, by assuming T is Lipschitz continuous, it can be shown that the solution set of (1) is a subset the solution set of SVI(T,X' X).. However, even solving SVI(T, X) 2) is NP-hard in general and hence we resort to finding e-first-order stationary point.
Throughout the paper, we make the following assumption:
Assumption 1. (i). is L-Lipschitz continuous, i.e. [|T(x;) - T(xe)112 I L||x| X2l12 Vx,,X2 E X.
4

---

Published as a conference paper at ICLR 2020
(ii). X)) has solution, i.e. there exists x, such that (T(x), x.) E
(ii). For Vx E E, E [T(: = T(x), E [T(x:) - s
Remark: Assumptions (i) and (iii) are commonly used assumptions in the literature of variational inequalities and non-convex optimization (Juditsky et al., 2011; Ghadimi & Lan, 2013; lusem al., 2017). Assumption (ii) is used frequently in previous work focusing analyzing algorithms that solve non-monotone variational inequalities (lusem et al., 2017; Lin et al., 2018; Mertikopoulos et al., 2018). Assumption (ii) is weaker than other assumptions usually considered, such as pseudo- monotonicity, monotonicity, or coherence as assumed in (Mertikopoulos et al., 2018). For non- convex minimization problem, has been shown that this assumption holds while using SGD to learn neural networks (Li & Yuan, 2017; Kleinberg et al., 2018; Zhou et al., 2019).
OPTIMISTIC STOCHASTIC GRADIENT
This section serves as warm-up and motivation of our main theoretical contribution presented in the next section. Inspired by (lusem et al., 2017), we present algorithm called Optimistic Stochas- tic Gradient (OSG) that saves the cost of the additional oracle call as required (lusem et al., 2017) and maintains the same iteration complexity. The main algorithm is described in Algorithm 1, where my denotes the minibatch size for estimating the first-order oracle. is worth mentioning that Algo- rithm 1 becomes stochastic extragradient method if one changes - E to T (x in line 3. Stochastic extragradient method requires to compute stochastic gradient over both sequences {x*} and {zæ)- In contrast, {x&) is ancillary sequence in OSG and the stochastic gradient is only computed over the sequence of {zx}. Thus, stochastic extragradient method is twice as ex- pensive OSG in each iteration. In some tasks (e.g. training GANs) where the stochastic gradient computation is expensive, OSG is numerically more appealing.
Algorithm Optimistic Stochastic Gradient (OSG)
1: Input: Zg Xg
2: for = 1..... N do
3: Zk 11x
Xs-1 - 77
Diml T(za-iiEt
4: X2 1xx
X;-1 - -1 mak
Ei=1 T T(ax: 5k
5: end for
Remark: When X' Rdd, the update in Algorithm 1 becomes the algorithm in (Daskalakis al.,
2017), i.e.
2k+1 2k- 2m
T(zz: +
Σ
((2=11:
mk-1
mA-1 1
1=1
The detailed derivation of (2) can be found in Appendix
Theorem 1. Suppose that Assumption holds. Let To va(zs) & 1/9L and run Algorithm 1 for N iterations. Then we have
12z IIx (Za aT (zx))l Let
1
N
81
12
1007²
o²
N
N
N
m
Corollary 1. Consider the unconstrained case where X
R.d. Let rj S 1/9L, and we have
N
X
1
100 N
BIT(Z))
+
(3)
N
P
N
m
k=
k=0
Remark: There two implications of Corollary 1.
5

---

Published as a conference paper at ICLR 2020
(Increasing Minibatch Size) Let 7)
9L. m. k 1. To guarantee
N E B| Σ c², the total number of iterations is N 0 (c- and the total
complexity is Ex= my ())t), where O(-) hides logarithmic factor of
(Constant Minibatch Size) Let 1) ST. my 1/c². To guarantee N E B|T(2>] e, the total number of iterations is N = () and the total complexity is = m. = O(c-))
4 OPTIMISTIC ADAGRAD
4.1 ADAGRAD FOR MINIMIZATION PROBLEMS
Before introducing Optimistic Adagrad, we present here quick overview of Adagrad (Duchi et al., 2011). The main objective Adagrad solve the following minimization problem:
min ((w)= B
welld
where is the model parameter, and Ç is random variable following distribution P. The update rule of Adagrad is
W+1 = W. - 11, 8i.
(5)
where 17 0, g: Vf(we: Gt), H, = diag ( (Ein 8i 2 (B:)
with o denoting the Hadamard
product. Adagrad when taking H, reduces to SGD. Different from SGD, Adagrad dynamically incorporates knowledge of history gradients to perform more informative gradient-based learning. When solving a convex minimization problem and the gradient is sparse, Adagrad converges faster than SGD. There several variants of Adagrad, including Adam (Kingma & Ba, 2014), RM- SProp (Tieleman Hinton, 2012), and AmsGrad (Reddi et al., 2019). All of them share the spirit, they take advantage of the information provided by the history of gradients. Wilson et al. (2017) provide a complete overview of different adaptive gradient methods in a unified framework. It is worth mentioning that Adagrad not be directly applied solve non-convex non-concave min- max problems with provable guarantee.
4.2 OPTIMISTIC ADAGRAD FOR MIN-MAX OPTIMIZATION
Our second algorithm named Optimistic Adagrad (OAdagrad) is adaptive variant of OSG, which also updates minimization variable and maximization variable simultaneously. The key difference between OSG and OAdagrad is that OAdagrad inherits ideas from Adagrad to construct variable metric based on history gradients information, while OSG only utilizes fixed metric. This dif- ference helps us establish faster adaptive convergence under some mild assumptions. Note that in OAdagrad we only consider the unconstrained case, i.e. X = Rdd
Assumption 2.
(i). There exists > 0 and 5 such that [ E)112 S G. (1T((2;))) S 8 for all z almost surely.
(ū)). There exists a universal constant D > O such that ||xx|12 S D/2 k = 1,...,N, and [x_ < D/2.
Assumption 2 (i) a standard one often made in literature (Duchi et al., 2011) 1). Assump- tion 2 (ii) holds when use normalization layers in the discriminator and generator such spectral normalization of weights (Miyato et al., 2018; Zhang et al., 2018), that will keep the norms of the weights bounded. Regularization techniques such weight decay also ensure that the weights of the networks remain bounded throughout the training.
Remark:
||x||= = V(x, /xx, Hx). Denote Book by the concatenation of go, .. Ck. and denote Bo-k.i by the i-th of go:k-
Define gx = 1 E Tiza: E

---

Published as a conference paper at ICLR 2020
Algorithm 2 Optimistic AdaGrad (OAdagrad)
1: Input: 2o No 0, Ho
81
2: for 1,.... N , do
3: 2 Xk-1 nH -
4: X)= = X n k Bk
5: Update go:k = gook
1x Sk, Il i I...., and set H₂ 81 diag(s; (sk-1)
6: end for
Theorem Suppose Assumption and 2 hold. Suppose 1ig I 8k with S a S 1/2 for every = 1,...,d d and every = I,...,N. N. When v S DT. after running Algorithm 2 for N iterations, we have
N
81 + d(N - 1)9) 100 (o² fo2/m + d (282 No + G9))
E ((zk)]
(6)
N
N
N
To make sure 2 Ex
(Z*{)) S E² the number of iterations is N = (
Remark:
Note that the convergence measure used in Theorem 2 is different from that in Corol-
lary 1. However we show that under the measure used in Theorem 2, OSG (Algorithm 1) still has complexity O(1/e4). By the construction of HІ in Algorithm 2, know that [T(())] m= & [|T()))l for any k 2 0 and any z, and hence & > [2I((2)))l H S
E [[) 113. By Corollary 1, we know that OSG still requires (1/c²)) complexity to guarantee that 1/4 Σ E [
N Σ B| No! N
H=! (2x)))
Se.
We denote gi.k by the cumulative stochastic gradient, where 1g..,:ll2 S ōk characterizes the growth rate of the gradient in terms of i-th coordinate. In our proof, key quantity is 1g that crucially affects the computational complexity of Algorithm 2. Since 1g... < ådk", in the worst case, 1.- But in practice, the stochastic gradient is usually sparse, and hence can be strictly smaller than 5.
As shown in Theorem 2, the minibatch size used in Algorithm for estimating the first- order oracle be any positive constant and independent of e. This is more practical than the results established either increase in terms of number of iterations is dependent complexity of Algorithm is ((1/et,, which matches the complexity stated in Theorem 1. When < _ the complexity of OAdagrad given in Algorithm 2 is O T ii.. strictly better than that OSG given in Algorithm
Theorem 1, since the minibatch size in Theorem does When
2 the
Comparison with Alternating Adam and Optimistic Adam Alternating Adam is very popular in GAN training (Goodfellow et al., 2014; Arjovsky et al., 2017: Gulrajani et al., 2017; Brock et al., 2018). In Alternating Adam, alternates between multiple steps of Adam the discriminator and a single step of Adam on the generator. The key difference between OAdagrad and Alternating Adam is that OAdagrad updates the discriminator and generator simultaneously. It is worth men- tioning that OAdagrad naturally fits into the framework of Optimistic Adam proposed in (Daskalakis al., 2017). Taking 31 0, 32 - in their Algorithm reduces OAdagrad with annealing learning rate. To the best of our knowledge, there is no convergence proof for Alternating Adam for non-convex non-concave problems. Our convergence proof for OAdagrad provides a theoretical justification of special case of Optimistic Adam.
5 EXPERIMENTS
WGAN-GP on CIFAR10 In the first experiment, we verify the effectiveness of the proposed al- gorithms in GAN training using the PyTorch framework (Paszke al., 2017). We use Wasserstein
7

---

Published as a conference paper at ICLR 2020
WOAN-GP on CIFAR1O with OAdagrad
WGAN-GP on CIFAR10 with O8G
WQAN-GP on CIFAR1O with Alternating Adam
mon Sccan
Sanin Score
Inception 01 o
Eix 175
0.5 Number Derationa
0.5
1.5
0.5
1.
Number barationa
x
Number harationa
XTO
Figure 1: OAdagrad, OSG and Alternating Adam for WGAN-GP on CIFARIO data
x106
WOAN-GP (CIFAR18)
-2100
WGAN-OP (CIFAR18)
=11
WOAN-OP (CIFAR10)
Cunmuraad Oddkent
0.5
0.5
1.5
0.5
1.
Number heratios (Bedroom)
Number heratios (Bedroom)
Number horations
x10
WGAN (Bedroom)
Oummuusto Gudert
Cummu Commulatedon Cradlent
Cummulated Creckent 5
5.5
Number heraitinss
Number herattons
Numbor horattons
Figure 2: Cumulative Stochastic Gradient as function of number of iterations, where netD and netG stand for the discriminator and generator respectively. The blue curve and red curve stand for the growth rate of the cummulative stochastic gradient for OAdagrad and its corresponding tightest polynomial growth upper bound, respectively.
GAN with gradient penalty (WGAN-GP) (Gulrajani et al., 2017) and CIFARIO data in our experi- ments. The architectures of discriminator and generator, and the penalty parameter in WGAN-GP are set to be same as in the original paper. We compare Alternating Adam, OSG and OAdagrad, where the Alternating Adam is to run steps of Adam on the discriminator before performing step of Adam on the generator. We try different batch sizes (64, 128, 256) for each algorithm. For each algorithm, we tune the learning rate the range of (1x 10 2x 10 1x10 2 10 1x100 }} when using batch size 64, and use the same learning rate for batch size 128 and 256. We report In- ception Score (IS) (Salimans et al., 2016) as a function of number of iterations. Figure suggests that OAdagrad performs better than OSG and Alternating Adam, and OAdagrad results in higher IS. We compare the generated CIFARIO 10 images associated with these three methods, which is in- cluded in Appendix A. We also provide experimental results to compare the performance of different algorithms using different minibatch sizes, which are included in Appendix
Growth Rate of Cumulative Stochastic Gradient In the second experiment, we employ OAd- agrad to train GANs and study the growth rate of the cumulative stochastic gradient (i.e., EL (1g.). We tune the learning rate from {1 [1x10-3 2,2x 10 1x 10 4, 4,2x 10-5, 1 10-5) 53 and choose batch size to be 64. In Figure 2, the blue curve and red curve stand for the growth rate for OAdagrad and its corresponding tightest polynomial growth upper bound respectively. N is the number of iterations, and c is multiplicative constant such that the red curve and blue curve overlaps at the starting point of the training. The degree of the polynomial determined using bi- nary search. We can see that the growth rate of cumulative stochastic gradient grows very slowly in GANs (the worst-case polynomial degree 0.5, but it is 0.2 for WGAN-GP on CIFAR and 0.07 for WGAN on LSUN Bedroom dataset). As predicted by theory, this behavior explains the faster convergence of OAdagrad versus OSG, consistent with what is observed empirically in Figure 1.
8

---

Published as a conference paper at ICLR 2020
SA-GAN on ImageNet
SA-GAN on ImageNet
14
300
Fréchet eptiiio Distance
mutaredus Adam
12
pltimiski Adagrad
250
10-
Inception
200
6-
4
S inuutarious Adam
O Otimmistic Adagrad
100
0
5
10
15
5
10
15
Number of Iterations
x10
Number of Iterations
x10*
(a) Inception Score
(b) FID
Figure 3: Self-Attention GAN on ImageNet, with evaluation using Official TensorFlow Inception Score and Official TensorFlow FID. We see that OAdagard indeed outperforms Simultaneous Adam terms of the (TensorFlow) Inception score (higher is better), and terms of (TensorFlow) Fréchet Inception Distance (lower is better). We don't 't report here Alternating Adam since in our run it has collapsed.
Self-Attention GAN ImageNet In the third experiment, consider GAN training large- scale dataset. We use the model from Self-Attention GAN (Zhang et al., 2018) (SA-GAN) and ImageNet our dataset. Note that in this setting the boundedness of both generator (G) and dis- criminator (D) is ensured by spectral normalization of both G and D. Three separate experiments are performed, including Alternating Adam (baseline), Simultaneous Adam (Mescheder et al., 2017), and OAdagrad. It should be mentioned that the update rule of Simultaneous Adam involves per- forming Adam-type update for discriminator and generator simultaneously. Training is performed with batch size 128 for all experiments.
For the baseline experiment (Alternttigg Adam) we use the default settings and hyper parameters reported in SA-GAN (Zhang et al., 2018) (note that we are not using the same batch size of 256 as in (Zhang et al., 2018) due to limited computational resources). In our experience, Alternating Adam training for a batch size of 128 with same learning rate in SA-GAN (0.0001 for generator and 0.0004 for discriminator) collapsed. This does not mean that Alternating Adam fails, it just needs more tuning find the correct range of learning rates for the particular batch size have. With the hyperparameters ranges we tried Alternating Adam collapsed, with extra tuning efforts and an expensive computational budget Alternating Adam would eventually succeed. This is inline with the large scale study in (Lucic et al., 2018) that states that given a large computational budget for tuning syper-parameters most GANs training succeed equally.
For both OAdagrad and Simultaneous Adam, we use different learning rate for generator and dis- criminator, as suggested in (Heusel al., 2017). Specifically, the learning rates used are 10-3 for the generator and 4 x 10-5 for the discriminator. We report both Inception Score (IS) and Fréchet Inception Distance (Heusel al., 2017) (FID) as a function of number of iterations.
We compare the generated ImageNet images associated with the three optimization methods in Ap- pendix Since Alternating Adam collapsed we don't 't report its Inception Score or FID. As can be seen in Figure 3 and Appendix A, OAdagrad outperforms simultaneous Adam in quantitative met- rics (IS and FID) and in sample quality generation. Future work will include investigating whether OAdagrad would benefit from training with larger batch size, in order to achieve state-of-the-art results.
CONCLUSION
In this paper, we explain the effectiveness of adaptive gradient methods in training GANs from both theoretical and empirical perspectives. Theoretically, we provide two efficient stochastic algorithms for solving a class of min-max non-convex non-concave problems with sfate-of ofate-of-the-an computa- tional complexities. We also establish adaptive complexity results for Adagrad-style algorithm by using coordinate-wist stepsize according to the geometry of the history data. The algorithm is proven enjoy faster adaptive convergence than its non-adaptive counterpart when the gradient is

---

Published as a conference paper at ICLR 2020
sparse. which is similar Adagrad applied convex minimization problem. We have conducted extensive empirical studies to verify our theoretical findings. In addition, our experimental results suggest that the reason why adaptive gradient methods deliver good practical performance for GAN training is due to the slow growth rate of the cumulative stochastic gradient.
ACKNOWLEDGMENTS
The authors thank the anonymous reviewers for their helpful comments, M. Liu and T. Yang partially supported by National Science Foundation CAREER Award 1844403, M. Liu would like to thank Xiufan Yu from Pennsylvania State University and Zehao Dou from Yale University for helpful discussions.
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. arXiv:1701.0785, 2017.
Wasserstein gan.
arXiv preprint
Waiss Azizian, Ioannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and uni- fied analysis of extragradient for a whole spectrum of differentiable games. arXiv preprint arXiv:1906.05945 2019.
Francis Bach and Kfir Y Levy. A universal algorithm for variational inequalities adaptive to smooth- ness and noise. arXiv preprint arXiv:1902.01637. 2019.
Andrew Brock, Jeff Donahue, and Karen Simonyan. Large scale gan training for high fidelity natural image synthesis. arXiv preprint arXiv: 2018.
Tatjana Chavdarova, Gauthier Gidel, Francois Fleuret, and Simon Lacoste-Julien. Reducing noise in gan training with variance reduced extragradient. arXiv preprint 1904v:9904.000 08598, 2019.
Chao-Kai Kai Chiang, Tianbao Yang, Chia-Jung Lee, Mehrdad Mahdavi, Chi-Jen Lu, Rong Jin, and Shenghuo Zhu. Online optimization with gradual variations. In Conference Learning Theory, pp. 6-1, 2012.
Cong D Dang and Guanghui Lan. On the convergence properties of non-euclidean extragradient methods for variational incqualities with generalized monotone operators. Computational Opti- mization and applications, 60(2):277-310, 2015.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9244 6264,,6,,
2018.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. arXiv preprint arXiv:/711.0014// 2017.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(11))2121-2159, 2011.
Saeed Ghadimi and Guanghui Lan. Stochastic first-and orde methods for nonconvex stochas- tic programming. SIAM Journal Optimization, 23(4): 2013.
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective generative adversarial networks. arXiv preprint 18Xiv:1802. 10551, 2018.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Rémi Le Priol, Gabriel Huang, Simon Lacoste-Julies and loannis Mitliagkas. Negative momentum for improved game dynam- ics. 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 2019. URL http: / ptwp//dooceeeeeoec ngs mlr wtw.s//wessssseeeeeeeeeeee wtw.mnm........//..888.131.
9a html.
10

---

Published as a conference paper at ICLR 2020
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farles Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural infor- mation processing systems, pp. 2672-2680, 2014.
Paulina Grnarova, Kfir Levy, Aurelien Lucchi, Thomas Hofmaann, and Andreas Krause. An online learning approach to generative adversarial networks. arXiv preprint
2017.
Ishaan Guirajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Im- proved training of wasserstein gans. In Advances in neural information processing systems, pp- 5767-5777, 2017.
Philip Hartman and Guido Stampacchia. On some non-linear elliptic differential -anrettiallfunntioonall equa- tions. Acta mathemalica, 115(1):77--310 1966.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 1826-6637, 2017.
AN lusem, Alejandro Jofré, Roberto Oliveira, and Philip Thompson. Extragradient method with variance reduction for stochastic variational inequalities. SIAM Journal on Optimization, 27(2): 686-724, 2017.
Anatoli Juditsky, Arkadi Nemirovski, Claire Tauvel, al. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Diederik P Kingma and Jimmy Ba. Adam: A method for stochastic optimization. arXiv preprint 11Xiv:1412.6990, 2014.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? arXiv preprint /vXiv:/802.061// 2018.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Yuanzhi Li and Yang Yuan. Convergence analysis two-layer neural networks with relu activation. In Advances in Neural Information Processing Systems, pp. 597-607, 2017.
Qihang Lin, Mingrui Liu, Hassan Rafique, and Tianbao Yang. Solving weakly-convex-weale concave saddle-point problems as weakly-monotone variational inequality. arXiv preprint arXiv: 10207, 2018
Tianyi Lin, Chi Jin, and Michael I Jordan. On gradient descent ascent for nonconvex-concave minimax problems. arXiv preprint arXiv:1906.00 00006.0031,000 2019.
Mingrui Liu, Zhuoning Yuan, Yiming Ying, and Tianbao Yang. Stochastic auc maximization with deep neural networks. In International Conference Learning Representations, 2020. URL https: /ttp://pppnnne wwwpeeeeeevveeeeeeeeeeee/eeeeeee iew....ww.... net / forum? d=HJepXaVYDr.
Songtao Lu, Ioannis Tsaknakis, and Mingyi Hong. Block alternating optimization for non-convex min-max problems: algorithms and applications signal processing and communications. In ICASSP 2019-2019 IEEE International Conference Acoustics, Speech and Signal Processing (ICASSP), pp. 4758- IEEE, 2019.
Mario Lucic, Karol Kurach, Marcin Michalski, Sylvain Gelly, and Olivier Bousquet. Are gans created equal? a large-scale study. Advances neural information processing systems, pp- 700-709, 2018.
Eric V Mazumdar, Michael I Jordan, and S Shankar Sastry. On finding local nash equilibria (and only local nash equilibria) in zero-sum games. arXiv preprint arXiv:1901.00 00838, 2019.
Panayotis Mertikopoulos, Houssam Zenati, Bruno Lecouat, Chuan-Sheng Foo, Vijay Chan- drasekhar, and Georgios Piliouras. Mirror descent saddle-point problems: Going the extra (gradient) mile. arXiv preprint 1r0Xiv:807.0200 2018

---

Published as a conference paper at ICLR 2020
Lars Mescheder, Sebastian Nowozin, and Andreas Geiger. The numerics of gans. In Advances in Neural Information Processing Systems, pp. 1825-1835, 2017.
George Minty al. Monotone (nonlinear) operators in hilbert space. Duke Mathematical Journal, 29(3):341-34,, 1962.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. arXiv preprini arXiv: 2018.
Vaishnavh Nagarajan and Zico Kolter. Gradient descent gan optimization is locally stable. In Advances in Neural Information Processing Systems, pp. 5585-5595, 2017,
Arkadi Nemirovski. Prox-method with rate of convergence (1/t) for variational inequalities with lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15()):229-251, 2004.
Arkadi Nemirovski and D Yudin. On cezari?s convergence of the steepest descent method for ap- proximating saddle point of convex-concave functions. In Sovier Math. Dokl, volume 19, pp. 258-269, 1978.
Arkadi Nemirovski, Anatoli Juditsky, Guanghui Lan, and Alexander Shapiro. Robust stochastic approximation approach to stochastic programming. SIAM Journal optimization, 19(4):1574 2009.
Arkadii Semenovich Nemirovsky and David Borisovich Yudin. Problem complexity and method efficiency in optimization. 1983.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems, Mathematical Programming, 109(2-3):319-34, 2007.
Adam Paszke, Sam Gross, Soumith Chintala, and Gregory Chanan. Pytorch: Tensors and dynamic neural networks in python with strong gpu acceleration. Team, Pytorch Core, 6, 2017.
Boris Teodorovich Polyak. Minimization of unsmooth functionals. USSR Computational Mathe- matics and Mathematical Physics, 9(3):14-29, 1969.
Hassan Rafique, Mingrui Liu, Qihang Lin, and Tianbao Yang. Non-convex min-max optimization: Provable algorithms and applications in machine learning. arXiv preprint arXiv:1810.02060, 2018.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable quences. In Advances in Neural Information Processing Systems, pp. 3066-3074, 2013.
Sashank J Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. arXiv preprint arXiv:1904.0923. 099307 2019.
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in neural information processing systems, pp. 2234 2242, 2016.
Maziar Sanjabi, Meisam Razaviyayn, and Jason D Lee. Solving non-convex non-concave min- max games under polyak- (LL)) ojasiewicz condition. arXiv preprint arXiv: 18/2.0287,, 2018.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint arXiv: 1409. 1556, 2014.
Tijmen Tieleman and Geoffrey Hinton. Lecture 6.5-rmsprop, coursera: Neural networks for machine learning. University of Toronto, Technical Report, 2012.
Ashia C Wilson, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148 4148-4188, 2017.
12

---

Published as a conference paper at ICLR 2020
Yi Xu, Zhuoning Yuan, Sen Yang. Rong Jin, and Tianbao Yang. On the convergence of (stochastic) gradient descent with extrapolation for non-convex optimization. arXiv preprint arXiv:1901.10682, 2019.
Abhay Yadav, Sohil Shah, Zheng Xu, David Jacobs, and Tom Goldstein. Stabilizing adversarial nets with prediction methods. arXiv preprint 17Xiv:1705.07364, 2017.
Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena. Self-attention generative adversarial networks. arXiv preprint arXiv: 2018.
Renbo Zhao. Optimal stochastic algorithms for convex-concave saddle-point problems. arXiv preprint arXiv: 1rXiv:1903.01687, 2019.
Yi Zhou, Junjie Yang, Huishuai Zhang, Yingbin Liang, and Vahid Tarokh. Sgd converges global
minimum in deep learning via star-convex path. arXiv preprint arXiv:190.004551 2019. 2019.
13

---

Published as a conference paper at ICLR 2020
A MORE EXPERIMENTAL RESULTS
Comparison Generated CIFARIO Images by Different Optimization Methods In this section, we report the generated CIFAR 10 images during the training of WGAN-GP by three optimization methods (OSG, OAdagrad, Alternating Adam). Every method uses batch size 64, and iteration represents calculating the stochastic gradient with minibatch size 64 once. Figure 4 consists of images by three optimization methods at iteration 8000. Visually we can see that OAdagrad is better than Alternating Adam, and both of them significantly better than OSG. It is consistent with the inception score results reported in Figure 1, and it also illustrates the tremendous benefits delivered by adaptive gradient methods when training GANs.
(a) OSG
(b) OAdagrad
(c) Altemating Adam
Figure 4: WGAN-GP: Generated CIFAR10 images using different optimization methods at iteration 8000.
Comparison Generated ImageNet Images by Different Optimization Methods In this section, report the generated ImageNet images during the training of Self-Attention GAN by three opti- mization methods (OAdagrad, Simultaneous Adam, Alternating Adam). Every method uses batch size 128 and I iteration represents calculating the stochastic gradient with minibatch 128 once. Fig- ure 5 consists of images by three optimization methods at iteration 135000. Visually it is apparent that OAdagrad is better than Simultaneous Adam, and both of them are significantly than Alternating Adam.
(a) OAdagrad
(b) Simultaneous Adam
(c) Alternating Adam
Figure 5: Self-Attention GAN (SA-GAN): Generated ImageNet images using different optimization methods iteration 135000. OAdagrad produces better quality images than simultaneous Adam. For both Oadagrad and simultaneous Adam we use the same learning rates: 0.001 for generator and 0.00004 for the discriminator. Alternating Adam in experience with same learning rate as in SA-GAN 0.0001 for generator and 0.0004 for discriminator collapsed. Note that our setting is different from SA-GAN since our batchsize is 128 while it is 256 in SA-GAN. It also noted in SA-GAN that alternating Adam is hard to train.
14

---

Published as a conference paper at ICLR 2020
Unofficial PyTorch Inception Score and FID results for SA-GAN on ImageNet
SA-GAN on ImageNet
SA-GAN on ImageNet
12
300
Fréchet Inception Distance
Sinuttaneuus Adam
Optimistic Adagrad
10
250
Inception Score
200
6
150
4
100
Simultaneous Adam
Optimistic Adagrad
10
15
10
15
Number of Iterations
x10
Number of Iterations
x10*
(a) Inception Score
(b) FID
Figure 6: Self-Attention GAN on ImageNet, with evaluation using Unoffical Py Inception Score and Unoffical Pytorch FID. We see that OAdagard indeed outperforms Simultaneous Adam in terms of the (PyTorch) Inception score (higher is better), and in terms of (Py PyTorhh) Fréchet Inception Distance (lower is better). We don't report here Alternating Adam since in our run it has collapsed.
B RELATED WORK
Min-max Optimization and GAN Training For convex-concave min-max optimization, the ex- tragradient method was first proposed by (Korpelevich, 1976). Later on, under gradient Lipschitz condition, Nemirovski (2004) extended the idea of extragradient to mirror mirror-prox prox and obtained the O(1/N) convergence rate in terms of the duality gap (see also (Nesterov, 2007)), where N is the number of iterations. When only the stochastic first-order oracle is available, the stochastic mirror- prox was analyzed by (Juditsky et al., 2011). The convergence rates for both deterministic and stochastic mirror-prox are optimal (Nemirovsky & Yudin, 1983). Recently, Zhao (2019) developed a nearly-optimal stochastic first-order algorithm when the primal variable is strongly convex in the primal variable. Bach & Levy (2019) proposed universal algorithm that is adaptive smoothness and noise, and simultaneously achieves optimal convergence rate.
There is a plethora of work analyzing one-sider sided nonconvex min-max problem, where the objective function is nonconvex in the minimization variable but concave in maximization variable. When the function weakly-convex in terms of the minimization variable, Rafique et al. (2018) propose a stage-wise stochastic algorithm that approximately solves convex-concave subproblem by adding quadratic regularizer and show the oidet-order convergence of the equivalent minimization problem. Under the same setting, Lu et al. (2019) utilize block-based optimization strategy and show the con- vergence of the stationarity gap. By further assuming that the function smooth the minimization variable, Lin et al. (2019) show that (stochastic) gradient descent ascent is able to converge to the first-order stationary point of the equivalent minimization problem. Liu et al. (2020) cast the prob- lem of stochastic AUC maximization with deep neural networks into nonconvex-concaw min-max problem, show the PL tion problem, and propose an algorithm and establish its fast convergence rate.
condition holds for the objective of the outer minimiza-
A more challenging problem is the non-convex non-concave min-max problem. Dang & Lan (2015) demonstrate that the deterministic extragradient method is able converge e-first-order station- ary point with non-asymptotic guarantee. Under the condition that the objective function is weakly- convex and weakly-coneave, Lin al. (2018) designs a stage-wise algorithm, where in each stage strongly-conee convexx strongly-concav subproblem is constructed by adding quadratic terms and appro- priate stochastic algorithms can employed to approximately solve it. They also show the conver- gence to the stationary point. Sanjabi et al. (2018) design an alternating deterministic optimization algorithm, in which multiple steps of gradient ascent for dual variable are conducted before one step of gradient descent for primal variable is performed. They show the convergence stationary point based on the assumption that the inner maximization problem satisfies PL condition (Polyak, 1969). Our work is different from these previous methods in many aspects. In comparison to (Lin et al., 2018), our result does not need the bounded domain assumption. Furthermore, our iteration complexity is (11/e2) to achieve e-first-order stationary point while the corresponding complexity
15

---

Published as a conference paper at ICLR 2020
in (Lin et 2018) is O(1/e)). When comparing (Sanjabi et al., 2018), do not assume that the PL -ojisewwe) condition holds. Additionally, our algorithm is stochastic and not restricted to the deterministic case. Apparently the most related work to the present one is (lusem al., 2017). The stochastic extragradient method analyzed in (lusem et al., 2017) requires calculation of two stochastic gradients per iteration, while the present algorithm only needs since it memorizes the stochastic gradient in the previous iteration to guide the update in the current iteration. Nevertheless, iteration complexity as in (lusem et al., 2017).
achieve the
There are a body of work analyzing the convergence behavior of min-max optimization algorithms and its application in training GANs (Heusel al., 2017: Daskalakis Panageas, 2018: Nagarajan & Kolter, 2017; Grnarova et al., 2017; Yadav et al., 2017: Gidel et al., 2018; Mertikopoulos et al., 2018; Mazumdar et al., 2019). few of them (Heusel al., 2017; Daskalakis & Panageas, 2018; Mazumdar et al., 2019) only have asymptotic convergence. Others (Nagarajan & Kolter, 2017; Grnarova al., 2017; Daskalakis al., 2017; Yadav al., 2017: Gidel al., 2018; Mertikopoulos et al., 2018) focus more restricted settings. For example, Nagarajan & Kolter (2017); Grnarova et al. (2017) require the concavity of the objective function in terms of dual variable. Yadav et al. (2017); Gidel et al. (2018) assume the objective be
Mertikopoulos et al. (2018) imposes the so-called coherence condition which is stronger than our assumption. Daskalakis et al. (2017) analyze the last-iteration convergence for bilinear problem. Recently, Gidel et al. (2019) ana- lyze the benefits of using negative momentum in alternating gradient descent to improve the training of a bilinear game. Chavdarova et al. (2019) develop variance-reduced extragradient method and shows its linear convergence under strong monotonicity and finite-sum structure assumptions. Az- izian et al. (2019) provide unified analysis of extragradient for bilinear game, strongly monotone case, and their intermediate cases. However, none of them give asymptoti convergence results for the class of non-convex non-concave min-max problem considered in our paper.
C PROOF OF THEOREM
C.I FACTS
Suppose C IR. is closed and convex set, then we have
Fact 1. For all E Rd and y E X, [IIx(x) - y/ [xIx(x)= x|| || y
Fact 2. For all x Rd and y E X, (x y (x)(x)) s 0.
C.2 LEMMAS
Lemma 1. For 17 S BT. we have
1
N
XR 1-
xx: - 20.13 ||100 1xxxxx111-1111
- 11 +1
Σ
| 12
Σ
As (7)
2
1=1
k=1
k=0
x=1
Proof. Let X², where X" is the set of optimal solutions of AVI( i.e. (T(x), - x.) 2
0 holds for Vx X. Define 6y ma Dm T
T(z {t) T(zz), and (( 2x) T((x) + 6k- For
16

---

Published as a conference paper at ICLR 2020
any N, we have
[x. x||2= = x (xx-1- -
117 ((2, 2x3) xx12
(0)
Xt-1 TT[(EK zzz) (z) -x
x - r/T(Ee, 25)) - 11x [xk-1 - nT zu:) )m:)|( ||²
Xx-1 (Tk, 2x2 - x
X/-1 - T) zx.) - -X
| x|2 - | xx:l2 + 2 ( x Xx, 1) Rx))
||*-| x|| | xx|1² + 2
x Zk: (E
(ER, zmr) + +2(2x Xk, S/:://Tes -xx 2x))
||x x|2 - | 2 + z -x+112 2 + 2 2k, nT zx)) +2 22 xx, (T(( zx))
||xx=1 x|| | zx12 - 1,4 xx11 - 2 (xx-1 24 2x xx)
2 2(x- 2k. 1x-22 (Ek) 2x)) 2 2x Xx, (T&, 2xx)
-1|x--1 x|| - ||*|-1 z 1| -1zz xx|12 + +2 22xx (x Zki (Ek, 2n3) + +2(xxx X
17 2x.)
Zz
(8)
where (a) holds by using Fact 1. Note that
2 2xx.- Zk, (Tx, zx)) 2 (xx 2k, 17 (T(s)) + cx)) 2 Zk. n(x);
(9)
where the last inequality holds by the fact that (x. 2x, T(zx)) < 0 since x. is a solution of MVI(T, X). Note that
2 Xx Zga x (fK, 2kk)
zkk + (xx Zk (T(C)-1, Zk-1) [(kk, mi))
x 2k
(0)
3 2n ||x - -zxll ||T(ES-1, -T(E,, 2ni1
(9)
3 2n
11x (x6-1- -1. (((c, 24)) 1Ix (xx-1- -11 ..n.TT(ceee [Cc (
((c--1, - - T(kk, 21)
_ 21² 2
(((k-1) 21-1 (E2) 253)
= 211² [[((z=))) + Ek-1 - ((T(z)) + tem)ll?
s 2ny² (|T(Z)-1) - T(2x))l + ||ck-1/| + 11exx1)2 (d)
S 27²² (L|Izk-1 - 2xll + +||c--11 + 1|cx1)2
(e)
< 61p (1,21 - 22 + ||exx11 1
+ 11ea|1
(10)
where (a) holds by (xx 2k, x - (, 21-1)
< and Cauchy-Schwarde inequality,
where the former inequality comes from Fact 2 and the update rules of the algorithm, (b) holds by the update rule of n and Xs, (c) holds by the nonexpansion property of the projection operator, (d)
holds since T is L-Lipschitz continuous, (e) holds since (a + b c)² 3a² + 352 + 3c..
Define A = 2(x, 2k. TEK). Taking x = x. in (8) and combining (9) and (10), we have
||x: - 12
< |x--1 - xx 112 ||xx-1 - 2x122 - - xx|12 + 2 [1 - -zxl2 + 6n72) 11 + =6n + A
(11)
Noting that
| z || = |z-1 Xt-1 + x 2x S 3112z-11 11-111+ 31|xx-11 21212 + 31|xx= 2x
we rearrange terms in (11), which yields
| 1= |zz- x1.11 L2 (3 83|1z-11 - xx-1 1| 3 [1- 2z 22 1 3//2z Xx 172
||x4-1 - x, 11 - ||x: - x. 1|2 + 617 |||| 112 + 667 1e + A
(12)
17

---

Published as a conference paper at ICLR 2020
Take summation over l = 1,...,, N in (12) and note that Xu
Zo. which yields
N
(1 - 181
Σ
xk-1 2x:12 + (1 (1-361) 1
z
k=1
k=1
(13)
N
N
< Xx0 -x,112 - ||xN - x=112 -x,1² + 12m
||eu|12
+
AA
k=0
k=1
By taking 1) S
1 9Z. we have 1 36,7 L2 N 1/2 and we have the result.
C.3 MAIN PROOF OF THEOREM 1
Proof.
Define Ty (Zt) = 1zz - IIx (Zy: - --T((x)))] Our goal is to get a bound on (,,()), We
have:
(2))
11 11x (zz- (zx))1 1 Xk +x 11x (ZR (xx)))
(a)
$
1|zx
xx1
+ 2 x 1Ix (Zx - 11 (z=)l)))
2||zz
2
xx11
2 2 1Ix Xk-1 1/I (ek, zu3) 1xx (zu: - n(T((z)))
(14)
(6)
X 2 + [ - 2x112 2 + +nn ((xx) T(ek:
S 2
1|z
S 4 ||zz
xx112
4 1| =zxl1 + |cx11
where (a) holds since (a + 6)2 < 2n² + +2b,, (b) holds by the non-expansion property of the
projection operator and (a + 6)² 2a + 2b2.
Let x, E X², where X" is the set of optimal solutions of MVI X)), i.e. (T(x), x,,, 2
holds for Vx X. Define Ex ma 5m T(zk: { T(z)), and T(Ek. zι) = T(xx) + Cb. Define Ag = 2(x.- - Zg, 7Es))
By summing over & in Equation (14) and using Equation (7) in Lemma 1, we have
N
4
xx112
+
X 11 + 4n²
c I1
1=1
1=1
k=1
1=
N
1
8
|z xx| 1/2
| - 2x11
4n²
||ex11
(15)
2
A=1
k=1
k=
N
N Σ
N
By
8
||xo
x. 11? + 12n
|| +
Ak
+ 4n)
||< 12
k=0
#=1
k=0
Taking expectation and divided by N on both sides, we have
+ 4n² Σ
E
(Zx))
|xo x. 2 12n²
Σ E
E
Σ
B(Ax)
Bl|Ex| 1|
k=1
N
4np N
o²
| - x.1 11 + 12ny
NV
N
k=0
k=0
8 Xn
x, 11
1007² 2
N
N
N
m7
k=0
(16)
n
18

---

Published as a conference paper at ICLR 2020
D PROOF OF THEOREM 2
In this section, we define gi: = T(zx), cx = -8 gk.
D.I LEMMAS
Lemma 2. For any positive definite diagonal matrix H satisfying H / 51 with 8 > 0, if [T(x))
T(x2)ll2 S [||x| X2llafor x1, X2 E X, then
[T(x)) -((x))l S 8 ||x - X2llH-
Proof. Note that H 2 81, we have 0 < 11-1 3 LL. Noting that ||x|| = Vx Hxx we have
V88 [1T(x (x2))l22 S 48
1
4
-x2l22 S - [|(x x2 x2||H- H-
[T(xi) - (xx))l V
|x - x2212
Lemma 3. When 1) S
yL. we have
N
X 2x11 N
-
Xs Zz 11712
2 k=1
k=1
N
N
N
|
x111 1x,1-xx - ||x: - x. 11126_..) + 12n2
|1ea [11011266 +
|
2
H
+
A
k=1
(17)
Proof.
Define EY gx: Bk. For any x X, we have
|xx x|1i1... = =||xK-1 1 1- gh x He-: =||x -| - -x1 He-1 - -|
nHH 18c
Xx
1
H
||xx-1 - x x11it-1
xx--1 x [1i,__, + 2 2((x - Xk: 118b)
||X--1 x| H=-1
X4-1 Xx 11 1ite_ + +2 Zk. 1/gk) + (zz= Xk,, rigk)
||X--1 - x x11211
X 2b + 2k - xx11 3/11 + 2 (x - Zk: 7/8b) ) + (zu: - Xx;, 78g
||xA- x1121,
| 2x.1ir1
122 xx xx11i11 -2 2 (H (Xk-1 2z)) 2s xx) +
2 (x Zk. n + 2 (Z)- Xx. (gx))
||xx-1 x112t__1 X 2v: 11:10-..
12 x +2 Zk: '18k)
+ (Xx=
Zk: H (Xx-1 - 2/)) 1/8b)
(18)
Note that
2 2xx. Zb, T8k) = 2 (x, Zk: 17 (gi +x)) 22 (x. Zk, nex)
(19)
where the last inequality holds by the fact that (x, Zk: gk) I 0 since x, is solution of MVI X). Note that
2 (xx Zk. H - - npax)
2 (xx- Ex, H4 1 (xk-1 2か n 1-1--18-111 1)) + 2 Zz: (gi-1 (x))
(0)
2 ( ((x--1 - n 4 [8k) - -(x:-1 1/ 4- 1- 18-1) .77 (gt-1 - -gx))
2np 1 - @ -2n22 ||g g: + Ck-1 + cK 1l
(
[|g-1 - Ballm,1, + ||16--1l + || ||<x|1 )²
(20)
2 2/²
(c)
7
2
$ 2n²
| zellm + (10=-111 + ||call
8
(d)
12
< 617
1 - 2xll + 1|ca-1112 112, + 11<x 12
8
19

---

Published as a conference paper at ICLR 2020
where (a) holds by the update rule of 2ạ and X in Algorithm 2, (b) holds by the triangle inequality,
(c) holds by utilizing the Lipschitz continuity of T, Lemma and the fact that Hę-1 t 61 for any k. (d) holds since (a + + c)² I 3a² + 3b² 3c².
Define A7- = 2(x,- - 2k. 7E2). Taking x = x, in (18) and combining (19) and (20), we have
6n2
x. x.11 S
||xx-1 x. 11:t0-. 1|xx-1 2xll - ||ze -xxll
zk-
Zi 12e117 Ha-1
82
+ c + 617/ ll, + Ax
(21)
Noting that
Zz--1 Z Zel1it.. = 1| X4-1 + Xx-1 -/ Z Ma-1
Zk-1 Xk-1 1/:80-1 311
2xll + +3//zx Xx xxI|
we rearrange terms in (21), which yields
6n L2
|x--1 Zz 1lllite-. + 1|zk xx 11
(31zz-1--xx-
+ +311xx-11 Z 2ill + +312z
Xxx 11118
82
$ | - x. 1illit- - ||X| - xx 11112 11 + 617 b01211c-11li Ma.
+
6n7 [0/|les11i =67"||ex11?,, + Ax
(22)
Taking summation over ls = 1, I,.... N in (22), and noting that 20. ||x 2 ||x for all
and/ /. 2 1, we have
18 1,2
36172,2
|
zx 2
(1-
8k
2
82
82
k=1
N
N
[|x--1 - X, 11:1i - ||xx - Xx xx11210.1) + 12n2²
||eoll2e,
||co |lg
+
|ex
+
Ax
H
1=1
(23)
By taking 1) S 6. 92. we have 36m"
2 1 2. and we have the result.
Lemma 4. When [B1:Nall22 S NNa with 0 S a 5 1/2 22222z for every i, we have
[ xx 1|xe- x.1 D28 D² -00Nd8(NN-- 1)aa
(24)
Proof.
N
[| [x6-] - -x.1171 - -1|x4 x,11711 .)
l|x0-
x. x111310
||x| x- 111100 + ||x|| x. x.11ir, - 1|x: x.11in .... ||xN-| xx1121x-- -|[xN x. x.11
1|x0 x. 212
+ (-lix) x.11220 + || - -x.112,) +... + (- ||xx-11 -x,11 -x,12 + +1|xN-1 x. x.112
< |xx0 x. 2
+ D2 (Ir(H, Ha) + ir(H2 - H1) + (N
||xo x. 1. + D2 (I((Hx11- Ho)) S ||xo - x. x.1220 + DDuu(HN-1) & D28 + D2 dō(N - 1)a
(25)
Lemma 5. When II: S 8N with 0 < a S 1/2 for every i, we have
N
25dN + GPd)
96n ||co 12, n1 + 100n² 2
Σ
| --
<
+ 100n?
(26)
md
20

---

Published as a conference paper at ICLR 2020
Proof. Note that
N
N
N Σ Bllgk
N
E
2
H
E
gh
Bk
2-
Bh H
=
Σ
10 Bb
11 H
k=1
k=1
N
N
B
BA
1|
El
E
E 88
12
Bl |
M5-1
HE
ME-1
k=1
k=1
k=1
N
N
11
gk
H
+
Bkg
(H
H (Bk )1))
5
El
Bk ||
+
- -
E
k=1
k=1
k=1
(a)
(b) + HHo 102
G2d
E
2
S 20dNa +
8
(27)
where (a) holds since we have Σx=1 | H ing Lemma of (Duchi et al., 2011), (b) holds because of 1l S ONa
S 2 1 by the setting of H3 and utiliz-
In addition, we have E [loolli S o² and hence
N
96n2o² m5
25dN + G2d
96n 2lco 12,, Ho
+ 100
2
|
2
S
+ 1001?
(28)
H 1
D.2 MAIN PROOF OF THEOREM 2
Proof. Our goal is bound 1. ΣN E|| Note that
1/2 (zx- (zr- nHl T(xx)) (2))
= 1/111/1 1/2 (zs Xx + xx
(zx
m/1 T (
(o)
H 1 (zy x+)|
+
1/2 k-
[*
(zz - nH [HH,TT(Z))))
2 H 1/2 (zN xx)
l|²
+ 2
H
k-
1/2
[x
(z: n 1
_ T
@ 2 1zz - xx 11/pp_. +2
[1
1/2
[x--1 nH
-
B (z) - n (T
k-
k-
< 2 1z X 112 |
+ 4 ||x 1 أساة + 4n² ll T(z 11 1|
= 2 1
x
2 1/,_.. + ||x - 2z 22112 + 4n² || P
(29)
where (a) holds by the triangle inequality, (b) is due to (a + 6)2 < 2a + 26 (c) holds by the update rule of X2 of Algorithm 2, (d) comes from the triangle inequality and (a + b)2 < 2a² + 212.
21

---

Published as a conference paper at ICLR 2020
Taking summation over k ,....,,N N over (29) and invoking Lemma 3, we have
(Zk)) 11 M=
Σ
2
Xx 1x1l124 l1 +
|
z2 21l1ian. Ha-i + =1/2 ||
11call7tz21
k=1
1z xsk 1111
+
1
Σ
|
||Ex l1 H + 2n7
2
A=1
By (17)
N
N Σ |le ll
N
8
| - x. x1
- ||x: - x. x.11i1-11)
+ 1-122
|1col12,.
+
Σ k=1
An
k=1
+ 4v)²
||ex:1 ||Ex||
1=1
N
[ x. 11
||x; x, x.11p1n..) 96n9 [kaal + 100n 2
||
( h-1
+8 A
(30)
Taking expectation on both sides, and invoking Lemma and Lemma 5, and noting that Σx= As O, we have
(1TT())) 28(D'8+ D² dō(N- - 1)9) + 96
mn + +1007² (2ddNa + G2d
Σ
8 (31)
Dividing n² N on both sides, we have
8D2 d(N 1)²) 100 (o²/m /m d (262 Na Gz)
N E T() T
(32)
N
E MORE EXPERIMENTAL RESULTS ON CIFAR10
In Figure we compare the performance of OSG, Alternating Adam (AlterAdam) and OAdagrad under the same minibatch size setting on CIFARIO dataset, where one epoch means one pass of the dataset. We can see that OAdagrad and Alternating Adam behave consistently better than OSG. When the minibatch size is small (e.g.. 64), OAdagrad and Alternating Adam have comparable performance, but when the minibatch size large (e.g., 128 256), OAdagrad converges faster than Alternating Adam. This phenomenon shows the benefits of OAdagrad when large minibatch size is used.
WGAN-OP
score Aanggn
Inospiinn
Meoppin
0000
2000
100
Epochs
Epochs
Number Epochs
Figure 7: OAdagrad, OSG and Alternating Adam for WGAN-GP CIFAR10 data with different batch sizes
22

---

Published as a conference paper at ICLR 2020
F THE EQUIVALENCE BETWEEN OSG IN UNCONSTRAINED CASE AND THE ALGORITHM IN DASKALAKIS ET AL. (2017)
Define gs m. EE ((zai (b), then the update rule of Algorithm becomes
Zk Xk- -
(33)
and
X = X 178k-
(34)
These two equalities together imply that
Zi+1
X 7gk Xk-1
2rgge Zi + 7/g-1 2n/gk=
(35)
where the first equality comes from (33) by replacing k k + the second equality holds by (34), and the third equality holds by using (33) again. (35) is the algorithm in (Daskalakis et al. 2017).
G THE EXISTENCE OF MVI SOLUTION MAY NOT IMPLY HEUDO-MONNOTONICIY
Consider the function f RR R, where
f(x) = { coo((c)
if S x S 2T
x $ or x 2 2T
Define T(x)= = (z)).. Then T(x) = (i) if < x < 2T and T(x) = 0f x < or 2 2T. Then we know that π is the solution of both SVI (i.c (T(T), - क) 2 0 for any x E X) and MVI (i.e. (T(x), x TT) 0 for any x X). However T is not pseudo-monotone.
To this, take x = and y = and we have (T(x), y - x)) = 0 and (T(y). y - x) < 0, which means that not pseudo-monotone.
23


Reviews:
[{"review_id": "rklsNMOaYS", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 two methods named OSG and OAdagrad for solving stochastic non-convex non-concave min-max problems. In theoretical analyses, a convergence rate of $O(\\epsilon^{-4})$ and a much better rate are provided for OSG and OAdagrad, respectively, to find the $\\epsilon$-accurate first-order stationary point. Finally, the superior performance of the proposed method is empirically verified on training generative adversarial networks (GANs).\n\nClarity:\nThe paper is well organized and easy to read.\n\nQuality:\nThe work is of good quality and is technically sound. However, I did not verify the proof in detail.\n\nSignificance:\nA stochastic non-convex non-concave minimax problem studied in this paper is recently considered as an important class of the optimization problems because important machine learning problems such as GANs fall into this class and most past papers studied convex-concave min-max problems instead. A few studies [Iusem+(2017), Lin+(2018)] proposed optimization algorithms for this problem and derived convergence rates $O(\\epsilon^{-4})$ and $O(\\epsilon^{-6})$, respectively. On the other hand, proposed methods have several preferable properties compared to these methods. For instance, OSG exhibits a comparable convergence rate to [Iusem+(2017)] with a fewer per-iteration complexity and OAdagrad exhibits a much faster convergence rate $O(\\epsilon^{-2/(1-\\alpha)})$ depending on the parameter $\\alpha$ that is an order of the growth of the cumulative stochastic gradients norm. In addition, the order of $\\alpha$ is shown to be slow in general and certainly faster convergence rates are also confirmed in experiments on training GANs. Thus, experimental results seem consistent with the theory. \nSince a derived convergence rate of OAdagrad is potentially much faster than those of existing methods, I think the OAdagrad is one of the promising methods for training GANs.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I did not assess the derivations or theory."}, "extra_text": {}}, {"review_id": "r1xHK7B9KB", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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": "--------------------------\nAfter the revisions made by the authors, my main concerns about the paper have been removed. Therefore, I am raising my score to 6 (weak accept).\n--------------------------\n\nSummary\n\nThe present work is concerned with the development of algorithms for the solution of variational inequalities in the stochastic setting, that is when the gradient computations are corrupted by noise. In this setting, the authors propose a variation of the extragradient method which they call Optimistic Stochastic Gradient (OSG), and show that by using a suitable method of variance reduction, the convergence rate of the algorithm matches the state of the art rate of convergence while relaxing the assumptions on the VI from pseudomonotone to assuming that the associated minty variational inequality has a solution. The authors furthermore introduce an adagrad-version of the same algorithm and show that improved convergence rates can be obtained depending on the growth rate of the cumulative stocastic gradients. An extensive suite of experiments studies the empirical performance of the proposed algorithms and compares them to the commonly used Adam optimizer.\n\nDecision\n\nIn its present form, while some of the contributions of the paper seem to be relevant contributions (theoretical analysis of adagrad version, state of the art performance of optimistic mirror descent), other contributions (some of which are advertised strongly in the abstract) are incremental or implicit in earlier work (optimistic stochastic gradient descent, relaxation from pseudomonotone to minty VI). Furthermore, while the experimental part is detailed, the connection to the theory could arguably be strengthened more. I believe that by more concisely focusing the paper on its innovative aspects while relating it more directly to existing prior work, it could make for a much more valuable contribution to the literature, which is why I vote for rejecting the paper in its present form.\n\nAdditional Detail on decision\n\nNovelty of OSG\nThe authors themselves note that the difference between OSG and OMD of Deskalakis et al is the inclusion of a projection step and the variance reduction by averaging multiple gradient evaluation at each iteration (which corresponds to choosing a different batch size for different iterations). I don't think these modifications are major enough to warrant \"introduction of a new algorithm\". The fact that all experiments seem to be conducted without constraints and constant batch size further strengthens this impression.\n\nRelaxation to Minty VI\nAnother claimed improvement of the paper is relaxing the assumption of pseudomonotonicity to the mere assumption of existence of a variational inequality. However, if I'm not mistaken (please correct me if this assesment is incorrect), the only part where the pseudomonoonicity assumption enters the proof in Iusem et al is on page 36, to prove the last inequality of Equation (105). Here, however, the assumption of a Minty VI could equally be used. Thus, the weakened monotonicity assumption is not related to the use of SGO as opposed to extragradient, which is not apparent from the paper.\n\nSuggestions for revision\n\nI do think that the material can make for a solid paper, but I think it would strengthen rather than weaken the contribution to point out in more detail the close precursors of some of the results in the paper. Notably, rather than inventing a new algorithm (OSG), the paper proposes a way to combine variance reduction with Optimistic mirror descent of Deskalakis et al such as to achieve state of the art convergence rates which so far were only known for the variance reduced extragradient method. Furthermore, it points out that these convergence results (just as in the case of variance reduced extragradient) hold as soon as the associated Minty variational inequality holds true. This latter point would be much stronger, if examples were given that illustrate why this is a meaningful extension. Finally, the paper derives improved rates of an OAdagrad. In my opinion this point should be made more prominent by deemphasizing the part on OSG.\n\nThere is a typo in the definition of pseudomonotonicity.\n\nQuestions for authors\n\n(1) Does figure 1 show iterations or epochs on the x axis? In order to support the theoretical claims, wouldn't it need to show the epochs on the x-axis? Otherwise, a larger batch-size simply corresponds to having access to more calls of the stochastic gradient oracle.\n\n(2) Is there a new technical difficulty to overcome when replacing the extragradient method with the OSG compared to the proof of Iusem et al? If yes, can you give a concise description of it?\n\n(3)It is not \"evident from the definition\" to me, why pseudo-monotonicity implies the existence of a solution of the Minty variational inequality, even though I believe that this is true. Could the authors explain this to me?\n\n(4) The main improvement of OSG over extragradient lies in it needing to compute half the number of gradients per iteration. Is it possible to  explicitly compare the constants in the bounds on the convergence rates of the two algorithms? It seems that this would be required to truly make the case of a reduced complexity of OSG.\n\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJenu0PTFB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "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 proposed a new algorithm (Optimistic Stochastic Gradient) for solving a class of non-convex non-concave min-max problem. The convergence theory is established for finding first order stationary point. The authors also proposed an adaptive variant of the proposed algorithm, called OAdagrad and showed an improved adaptive complexity.\n\n- It is not immediately clear to me why the update of Algorithm 1 becomes the algorithm in (Daskalaskis et al. 2017) when there is no constraint. Can the authors further explain this clearly? The two variables in (Daskalaskis et al. 2017) are updated with different signs, but here  z=(u,v)  (I assume, the authors should clearly define z too), it seems that u and v are updated with the same sign?\n\n- In terms of the theoretical contributions, aside from the presenting theorems, can the authors also comment on what is the key point to achieve the derived results? For example, in Algorithm 1, the only difference from stochastic extragradient method is T(z_{k-1}) instead of T(x_{k-1}), and the theorem achieves the same iteration complexity with weaker assumption.  Is this because the replacement term, or it is the proving technique improvement that can also be applied to stochastic extragradient method?\n\n- For Algorithm 2, why there is no projection operator like in Algorithm 1? Also, the algorithm design is a bit different from traditional AdaGrad as their H matrix is the historical average of all past gradient square (element-wise). Here the s_i is L_2 norm of historical gradient, there is no averaging (divided by k) operator. Can the authors elaborate on this algorithm design?\n\n- For experiments part, it is better for the authors to compare with more baseline methods such as Optimistic Adam. For Figure 1, can the authors put different batches in different plot so that we can directly compare the performances of different algorithms? It does not make sense that alternating Adam failed in training SA-GAN here but success in the original paper. Can the authors figure it out and provide the comparison on this?\n\nDetailed comments: \n\n- it is better to define m_t in or before Algorithm 1 to make it clear for the readers.\n- In Page 7, comparison with … paragraph, should be \\beta_1 = 0, \\beta_2 -> 1? If so, it is still a bit different with OAdagrad?\n\n\n======================\nafter the rebuttal\n\nI thank the authors for their response and it addressed most of my concerns.  ", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This work proposes a new adaptive method for solving certain min-max problems.

The reviewers all appreciated the work and most of their concerns were addressed in the rebuttal. Given the current interest in both adaptive methods and min-max problems, this work is suited for publication at ICLR.
Decision: Accept (Poster)