On the One-sided Convergence of Adam-type Algorithms in Non-convex Non-concave Min-max Optimization
Authors: Zehao Dou
Yuanzhi Li
Venue: ICLR 2022 Submitted (2022)
Keywords: Optimization
GAN
Convergence

Abstract: Adam-type methods, the extension of adaptive gradient methods, have shown great performance in the training of both supervised and unsupervised machine learning models. In particular, Adam-type optimizers have been widely used empirically as the default tool for training generative adversarial networks (GANs). On the theory side, however, despite the existence of theoretical results showing the efficiency of Adam-type methods in minimization problems, the reason of their wonderful performance still remains absent in GAN's training. In existing works, the fast convergence has long been considered as one of the most important reasons and multiple works have been proposed to give a theoretical guarantee of the convergence to a critical point of min-max optimization algorithms under certain assumptions. In this paper, we firstly argue empirically that in GAN's training, Adam does not converge to a critical point even upon successful training: Only the generator is converging while the discriminator's gradient norm remains high throughout the training. We name this one-sided convergence. Then we bridge the gap between experiments and theory by showing that Adam-type algorithms provably converge to a one-sided first order stationary points in min-max optimization problems under the one-sided MVI condition. We also empirically verify that such one-sided MVI condition is satisfied for standard GANs after trained over standard data sets. To the best of our knowledge, this is the very first result which provides an empirical observation and a strict theoretical guarantee on the one-sided convergence of Adam-type algorithms in min-max optimization. 

Under review as a conference paper at ICLR 2022
ON THE ONE-SIDED CONVERGENCE OF ADAM-TYPE ALGORIHTMS IN NON-CONVEX NON-CONCAVE MIN- MAX OPTIMIZATION
Anonymous authors Paper under double-bling review
ABSTRACT
Adam-type methods, the extension of adaptive gradient methods, have shown great performance in the training of both supervised and unsupervised machine learning models. In particular, Adam-type optimizers have been widely used empirically the default tool for training generative adversarial networks (GANs), On the theory side, however, despite the existence of theoretical results showing the efficiency of Adam-typa methods in minimization problems, the reason of their wonderful performance still remains absent in GAN's training. In existing works, the fast convergence has long been considered as one of the most important reasons and multiple works have been proposed to give a theoretical guarantee of the con- vergence to critical point of max-max optimization algorithms under certain assumptions. In this paper, we firstly argue empirically that in GAN's training, Adam does not converge to a critical point even upon successful training: Only the generator is converging while the discriminator's s gradient norm remains high throughout the training. We name this one-sided convergence. Then bridge the gap between experiments and theory by showing that Adam-type algorithms provably converge to one-sided first order stationary points in min-max opti- mization problems under the one-sided MVI condition. We also empirically verify that such one-sided MVI condition is satisfied for standard GANs after trained over standard data sets. To the best of our knowledge, this is the very first result which provides an empirical observation and a strict theoretical guarantee on the one-sided convergence of Adam-type algorithms in min-max optimization.
INTRODUCTION
As one of the most popular optimizers in supervised deep learning tasks like natural language processing (Chowdhury, 2003) as well as the main workhorse of generative adversarial network training (Goodfellow et al. (2014), Adam-type methods are widely used because of their minimal need for learning rate tuning and their coordinate-wise adaptivity local geometry. Starting from AdaGrad (Duchi et al., 2011). adaptive gradient methods have evolved into a variety of different Adam-type algorithms, such as Adam (Kingma & Ba 2013), RMSprop, AMSGrad (Reddi et al.) 2018) and AdaDelta (Zeiler 2012). In supervised learning, adaptive gradient methods and Adam- type algorithms play important roles. Especially in the field of NLP (natural language processing), Adam-type algorithms are the goto optimizer. Multiple NLP experiments show that sparse Adam outperforms other non-adaptive algorithms like Stochastic Gradient Descent (SGD) not only on the solution performance, but also on both the training and testing error's convergence rates. It's worth mentioned that the most popular pre-training language model BERT (Devlin et al. 2018) also uses Adam as its optimizer, which shows the power of Adam-type algorithms.
Also, Adam-type algorithms are very effective in min-max optimization. As a direct and widely used application of min-max optimization, generative adversarial networks (GANs) are notorious for the training difficulty. Training by SGD will easily diverge to nowhere or converge to limiting cycle, both of which will lead to ill-performing solution, while Adam optimizer, as the default optimizer for GANs (Hsich et al. 2020), can obtain better performance. The reason why these two optimizers have much difference in GAN's training has long been an open problem. Traditionally, the training performance of min-max max optimization is measured according to its first-order convergence, which means the norm of the gradient, but is it really true in GAN's training?
After training GAN on two relatively simple datasets, MNIST and
we can find that, in a practical training process of GAN, Adam optimizer does not perfectly converge since the

---

Under review as a conference paper at ICLR 2022
norm of discriminator's gradient remains quite high through out the training process. Instead, it only has a one-sided convergence as the norm of generator's ' gradient actually converges to 0. This
0
9
6
7
4
4
7
7 2
8
3
7 5
7
4
1
(a) MNIST
(b) Aishion-MNIST
(c) MNIST
(d) -NISS
We train GAN on the dataset MNIST and Fashion-MNIS" The first two figures above show us the Frobenius norm of the gradients of discriminator and generator. After 50k iterations, we obtain (c).(d by using Adam. Despite its one-sided convergence, the min-max training actually succeeds.
Figure 1:
paper thus aims to explain this phenomenon by bridging the gap between theory and practice. On one hand, we understand under which conditions Adam-type optimization algorithms have provable convergence for min-max optimization. Towards this end, a recent work (Liu et al. 2020) designs two algorithms, Optimistic Stochastic Gradient (OSG) and Optimistic AdaGrad (OAdaGrad) for solving a class of non-conver non-concave min-max problems and gives theoretical guarantee on their convergence. (Liu et al. 2020) also proposes an open problem on the convergence proof of Adam-type algorithms, which is solved by this paper. On the other hand, we find that the MVI condition needed for our convergence proof does not practically hold for GANs, Instead, we propose the much milder one-sided MVI condition, which tends to hold practically and under which we provide the theoretical guarantee of the one-sided convergence of Adam-type algorithms.
Despite some theoretical guarantee made on the convergence of Adam-type algorithms convex concave or non-convex concave min-max optimization, in the non-convex non-concav setting which is most general, there is theoretical guarantee on convergence. Comparatively speaking, proving the convergence of Adam-type algorithms is much more difficult since they use an empirical version of Momentum. Although it has been shown to perform well in practice, it is actually difficult to analyze theoretically. Even in the standard convex setting, proving the convergence of Adam-type algorithms (Reddi et al. 2018 8 Zou al. 202T) is much harder than other adaptive algorithms such as AdaGrad (Duchi et al. 2011). Actually, the original version of Adam is known not to converge in convex settings. Therefore, formally analyze the convergence of Adam-type algorithms in min-mat max optimization, we also consider a "theoretically correct" version of Adam, which is an analog of AMSGrad (Reddi et al., 2018).
In this paper, there are three main contributions. (1) We analyze Extra Gradient AMSGrad, which is an Adam-type algorithm used for solving non-convex non-concave min-max optimization problems as well GAN's training. We prove that, under the assumption of standard MVI condition, the Extra Gradient AMSGrad algorithm provably converges to a e-stationary point with (de complexity in deterministic setting and (de: complexity in stochastic setting. (2) Although the standard MVI condition above is a much milder assumption than convexity, we empirically show that MVI condition does not hold for GAN's objective functions in reality. Instead, the one-sided MVI condition proposed by us tends to hold, which is the mildest assumption ever used in all the convergence proofs for min-max optimization. Under the the one-sided MVI condition, we modify the algorithm above by using dual rate decay, and theoretically prove its convergence rate. (3) We conduct empirical experiments on GAN's training by the Extra Gradient AMSGrad algorithm and the Extra Gradient AMSGrad with dual rate decay analyzed by us. We show that they have much better performance than the Stochastic Gradient Descent Ascent (SGDA) algorithm. Also, we empirically verify that our new one-sided MVI condition is indeed satisfied during GAN's training while the previously proposed standard MVI condition is not, which makes the one-sided MVI condition much closer to reality than the standard version.
After achieving all these results, we are eventually able to understand the one-sided convergence of Adam-type algorithms in min-max optimization well as in GAN's training.
2

---

Under review as a conference paper at ICLR 2022
2 BACKGROUND AND RELATED WORKS
In this section, we will introduce the background knowledge as well as related works on the following three fields: adaptive gradient methods, min-max optimization, and the convergence properties of multiple algorithms for min-max optimization problems.
2.1
ADAPTIVE GRADIENT METHODS AND ADAM-TYPE METHODS
We consider the simplest 1 1-dimensional unconstrained minimization problem:
min f(z). #DDER
where f: D
+ R is continuously differentiable function. As one of the most dominant algorithms on the optimization problem above, Stochastic Gradient Descent (SGD) was originally proposed by (Goodfellow al. 2016), which has been both empirically and theoretically proved effective, especially when facing large datasets and complicated models. To further improve the performance of SGD, several adaptive variants of SGD have been proposed, such as RMSprop, Adam (Kingma & Ba 2015), AdaGrad (Duchi et al., 2011), AMSGrad (Reddi et al. (018)) and AdaDelta (Zeiler) 2012). Distinguished from the vanilla gradient descent or its stochastic version SGD, adaptive gradient methods use coordinate- wise scaling of the updating direction and each iteration relies on the history information of past gradients. In AdaGrad, we use arithmetic average when adopting history gradient information of each iteration while in Adam, RMSprop etc., we use exponential moving average instead because its believed that the more current gradient information is more important. Although adaptive gradient methods and momentum based methods are two different routes on optimization, they are combined perfectly in Adam. Now we introduce the family of adaptive gradient methods and Adam-type, and all of them have the following form:
M h4 V ((x) + Wa, 0++1 (V ((xx)) + -
M4+1
[Adaptive]
T++1 24
A
Vu+i +E
Here, f is the objective function to minimize. h, r, 9 are scalars depending on f, A is the learning rate of the t-th iteration and & > is a small constant used to protect the denominator from being close see that the momentum m, is the weighted sum of the past gradients
to O. From the formula above, and vn is the weighted sum of the past squared gradients. When h = 1,r = 0, Mz+1 = V (xxe) is just the current gradient. We start with the original Adam.
U = Ur + (1 az) (v)(V(()))) m Beme + (1 f(x)
M4+1
[Adam]
L = - A /u++1 +
As we can see, Adam is a combination of adaptive gradient method and momentum method. Here, the momentum term empirical, meaning that it does not coincide with acceleration techniques that are theoretically sound, which creates extra difficult for the analysis. In Adam, we have hy + r. = Pt + gt = 1. When the ar a, Br = 33 remains constant, there a bias correction step FLll where tt-1 I-at and m++1 1-pr. However,
may practically ignore this bias correction step since - and I-3e rapidly approach to 1. As one of the variants of Adam, AMSGrad has the following formulation:
1ill
01+1 = 0222 + (1 av) 1141 = max (1, 0c+1)
M++1 = B,ve + (1 3.) f()), Ze+1 = 24 A
M4+1
[AMSGrad]
Vu++ +
As we can see, their difference is that the velocity term v, keeps increasing in AMSGrad.
After showing the details of these traditional adaptive gradient methods and Adam-type methods, we introduce their convergence properties as well as their further variants. Reddi et al. (2018) shows that Adam does not converge in some settings where large gradient information is rarely encountered and it will die out quickly because of the "short memory" property of the exponential moving average. However, under some conditions, the convergence proofs of adaptive gradient methods have been obtained. [asu et al. (2018) proved the convergence rate of RMSprop and Adam when using deterministic gradients instead of stochastic gradients. Li & Orabonal (008)) analyzed the
3

---

Under review as a conference paper at ICLR 2022
convergence rate of AdaGrad under both convex and non-convex settings. All the papers above provide theoretical guarantee for the convergence of different types of adaptive gradient descent. After that, Chen et al. 2019) extends Adam to a broader class of Adam-type algorithms and provides its convergence analysis for non-convex optimization problems. In order to combine the fast convergence of adaptive methods and better generalization with momentum based methods, number of new algorithms are proposed, such as SC-AdaGrad / SC-RMSprop (Mukkamala & Hein 2017). AdamW (oshchilovv & Hutter 2019), AdaBound (Luo et al. 2019) etc..
2.2 MIN-MAX OPTIMIZATION
In the min-max optimization problem (or saddle point problem), we have to solve:
min max 6(x, v), ZE yEy/
[SP]
where X' C IR1,, y C R=² and & : X'xx y R is the objective function. When is convex on and concave on y. we call it a convex-concave min-max optimization. Otherwise, it's a more general non-convex non-concave min-max optimization. For the brevity, we denote
(xr, v) and 2 X' x x C *" We also introduce our gradient vector field: V(z) = (- (-V,0(z,))) y). V y)), which are the update directions on both sides. The goal of [SP] is find a tuple =" (x",3") such that "(x",,) & "0x", .V") & (xx, y²) holds for Vrr X, E V. which is called the solution of [SP]. If the inequality above only holds in the local neighbourhood of z", then 2" can only be called a local solution. Notice that the necessary condition of being solution (or even a local solution) is to be stationary point of Φ. which means V(=*)= = 0. Furthermore, must be stable, which means V2 ó0 y²) ž 0 and V p(x" " y²) = 0. Next, we will introduce several commonly-used algorithms which are designed to solve [SP].
is C2, any local solution of [SP]
Stochastic Gradient Descent Ascent (SGDA) This is simple extension of Stochastic Gradient Descent (SGD) algorithm for minimization problems (Johnsen 1959). In the 1-th iteration:
2++1 = + 7 ((za;
SGDA]
where wi, W2, are the independent and identically distributed sequence of noises. V(2, w) can be treated as query to the stochastic first-order oracle (SFO). In each iteration of SGDA, we need to query SFO once. Notice that, we simultancously update x, y in each iteration of SGDA. Therefore, if we alternate the updates of x and y. we obtain a variant of SGDA, which is named as the alternating stochastic gradient descent ascent (AItSGDA) algorithm. Different from original SGDA, have to make two queries to SFO in each iteration. One for 2, = (xte, yt). and the other for the intermediate step (I++1,, 3t). Since original SGDA is not going to work even in the convex-concave setting (such as minl max,, (I, 8) = ry), so researchers propose the following "theoretically correct modification".
Stochastic Extra-gradient (SEG) This is a different algorithm with the above SGDA, and it is originally proposed for solving the convex-concave setting of min-max optimization problems by Corpelevich((197) Given 2, as a base, we take a virtual gradient descent ascent step and obtain a ž, which can be treated the shadow of 2z. Then we use the gradient of as the update direction of zt- This process can be described as:
2 = 22 + 7 V (()
[EEG]
2+41 = ze + 70 (2))
In each iteration, we need to make two queries to the SFO. One for the base ,, and the other for the shadow z/- However, in the first step of [SEG], we can use the gradient the previous shadow 2ا_ so that we only have to make only one query in each iteration and remember the query's 's result of the previous step. This algorithm is called Optimistic Gradient or Popov's Extra-gradient (Popov) 1980 which can be described as:
a = 2t + Yt ((
[OG]
2-1= = 24 + 7t- (221:w))
As a widely used algorithm, it has been applied in multiple works (Daskalakis et al. 2018 Mer tikoooulos et al., 2019). Under some mild assumptions, convergence rates are proved by many theoretical works and we will summarize them in the next section.
4

---

Under review as a conference paper at ICLR 2022
2.3 CONVERGENCE RATES OF MULTIPLE MIN-MAX ALGORITTMS
In this section, we summarize the convergence rates of different algorithms as well as the assumptions needed. For convex-concave optimization, Nesterov (2007) provided the O1/TT) convergence guarantee of Mirror-Prox in terms of duality gap. Juditsky et al. (20TT) introduced its stochastic version where only the stochastic first order oracle can be accessed. After combining with (Darzentas) 1983), convergence rates for both deterministic and stochastic mirror- purror-prox algorithms are shown to be optimal. When it comes to the more challenging non-convex non-coneave min-max optimization, Dang & Lan (015)) showed that the deterministic extragradient method can converge to c-first order stationary point with non-asymptotic guarantee. Another interesting algorithm Inexact Proximal Point (IPP) method (Lin et al. 2018), which is stage-wise algorithm, performs well when the objective function is weakly-conves weakly-coneaye In each stage, we construct a strongly-conve strongly- concave sub- prob-problm by adding quadratic regularizers. Then, by using stochastic algorithms, can approximately solve the original problem. It's known that IPP also has a first order convergence guarantee. Also, (Sanjabi et al. (20T8) proposed alternating deterministic optimization algorithm, where multiple steps of gradient ascents are conducted before one gradient descent step. Therefore, we can approximately make sure that the max step always reaches near optimal. However, in order to guarantee its convergence to first order stationary point, we have to assume that the inner maximization problem satisfies PL condition (Polyak) 1969). For the details of convergence rate, we summarize them into Table I
Finally, MVI condition needs to be explained. Let K Rd + Rd be
Assumption
IC
Guarantee
OMD Daskalakis al.
2018
bilinear
N/A
asymptotic
(deterministic)
0G
(Liu et al. 2020
MVI has solution
O(E-))
&-SP
(stochastic)
OAdaGrad (Liu et al.
2020
MVI has solution
(dd/22)
E-SP
(stochastic)
BCG Condition
SEG (lusem et al.
2017
pseudo-monotonicity
0(E
E-SP
(stochastic)
Extra-gradient (Azizian et al. 2019)
strong- mongoomtnt
(llo(1//=)
s-optim
(determimsticc)
AltSGDA al.
2019
bilinear
(llo((I/E)
s-optim
(deterministic)
IPP (Lin et al. 2018
MVI has solution
0(s-5)
8-SP
(stochastic)
Extra Gradient AMSGrad (ours)
O & O(de
MVI has solution
E-SP
(deterministic & stochastic)
Extra Gradient AMSGrad
one-sided MVI has solution
Ode & ÖdE
with Dual Rate Decay (ours)
&-SP
(deterministic & stochastic)
Table 1: Summary of different algorithms for min-max optimization. IC stands for iteration complex- ity, E-SP stands for E-first order stationary point, and E-optim stands for s-close to the set of optimal solutions. The last two lines are algorithms analyzed by us in this paper. BCG condition stands for the bounded cumulative gradient assumption.
an operator and X IRd is closed convex domain. Hartman & Stampacchia ( 19666
proposed the Stampacchia Variational Inequality (SVI), which aims to find z" e X. such that (K ), z*) > 0 holds for all E X. Similarly. Minty| (1962) proposed the Minty Variational Inequality (MVT) problem, which aims to find x² E X. such that (K(z), - 2*) > O. In Table I the operator
K(=) (V v), - Vvp( v)) = VV with (x,y).
MAIN RESULTS
In this section, we introduce the main results of this paper. We focus on two algorithms: Extra Gradient AMSGrad (AMSGrad-EG) and Extra Gradient AMSGrad with Dual Rate Decay (AMSGrad- EG-DRD) which inherit the idea of OAdaGrad into Adam-type algorithms. With AMSGrad-FF -GG, can prove its first-order convergence under MVI condition. However, does not perfectly converge in GAN's training since MVI condition does not always hold for GAN's objective functions. We bridge the gap by proposing one-sided MVI condition which is shown to be
stated above, Adam
5

---

Under review as a conference paper at ICLR 2022
more likely hold. Under this condition, prove that Extra Gradient AMSGrad with Dual Rate Decay BAaGGrd--EG-DROA converges one-sidedly, which matches our experiment results.
3.1 PROBLEM SETTING AND ASSUMPTIONS Throughout the paper, we analyze the min-max optimization problems:
min max (xx, v), yey
[SP]
where X C R C _ and Ø x x - I is the objective function. We denote (z, 1) and = X x V. First, we state some useful assumptions on ((r,))
Assumption 1.
V= (-V y is L-Lipschitz continuous under -1- norm.
(2) The stochastic first order gradient oracle (SFO) is unbiased and has bounded variance:
(2 [)] V(z) and (v())) =0?
(3) The Stochastic first-order Gradient Oracle (SFO) has bounded output: there exists and
6 > O such that [=V & G and (=; {) & almost surely holds.
(4) There exists a universal constant D O, such that || & D holds for all points 2 on our trajectory and || D. If the feasible set Z is bounded, then this assumption naturally holds.
Assumption (Standard MVI condition). The MVI of -V(z) has solution, which means there
exists a 2", such that: (-V(x), 2-) > 0 holds for 4z
3.2 EXTRA GRADIENT AMSGRAD (AMSGRAD-EG)
In this section, we analyze the Extra Gradient AMSGrad (AMSGrad- algorithm, which used for non-convex non-concave min-max optimization, and we theoretically provide its convergence rate. So far, the convergence rate of Adam-type algorithms for min-max optimization has long been an open problem, and this work is the very first obtain a related result. AMSGrad-EG algorithm is described as Algorithm
Algorithm Extra Gradient AMSGrad
Input:
The initial state mg = Up = 0, a constant learning rate momentum parameters Bics B2, Stochastic First-order Oracle (SFO) V(2; {), sequence of batch sizes {M&). Output: 2, where is uniformly chosen from {0, I,..., N 1}.
for k= 1 N do
2: (Gradient Evaluation 1) Ix-1 = Mr My Viz--1i Ei
3: (Momentum Update 1) my = 11 + (1 31k 31k)gh11
4:
(Velocity Update 1) Uj max(32ūkk] + 32) Ūk-1). Hs 81 Diag( vex).
5: (Shadow Update) &4 = 2k-1 + H My.-
6: (Gradient Evaluation 2) 9r Mr Σi=l V (t)
1 Mx
7:
(Momentum Update mh -1
BIK)AN-
8: (Velocity Update 2) 0g maxx(32%) + (1 321 Uk), f. 8I Diag (vt))
9: (Real Update) = 2k-1 + A. -mn--
end for
Compared to the original Adam, we just add an extra- extra-gradient technique and a taking max process in velocity updates. It's worth mentioned that if we delete the maximizing operation in velocity update steps, then this algorithm degenerates to Extra-Gradient Adam, since the largest difference between Adam and AMSGrad is that the latter one guarantees that the velocity term non-decreasing.
Theorem 3.1 (Main Theorem 1). For the AMSGrad-Ea EG algorithm, given the objective function ((x, y) : tr2 + R and Vzz) (-V v, that satisfy Assumption 7 and Assumption 2 as well as the initial point zo Z, the iteration number N, a sequence of batch sizes {Mr} and constant learning rate yj & 3r, then the output of the algorithm satisfies the following inequality:
8

---

Under review as a conference paper at ICLR 2022
6dD2 (8 + +G²
18dG + +
150o² (0 + G)
N
B=](3 <
N
172
82
NO
M
48G + G)
G0 + G)
N1
31
NO
Pic
Here, we analyze the conclusion above on two sides: parameter choosing on 31 and on Mr-
Discussion Here, we give some discussions on Thcorem 3.1 and compare it with existing results. (I) There are two practical ways to choose the parameter sequence {:te): (1) B1t B1 X where $1. A E (0, 1) and (2) $1t 1/t. In both settings, Σn= 87. O(1) and Σ f1 O(). Therefore, we can conclude from Theorem 3.1 that: (z) & O(d/N) + -(L/N) Σ 1/M, holds after regarding D, G. 6, 1) as constants.
(2) When the batch sizes M2 are constant, let M₁ = (11=a). To guarantee E (2)1l < E², the total number of iterations should be N O(d=~2) and the total complexity is Ex=
k= M₁ O(d
.2
When the batch sizes M3 are increasing, let M₁- = 1: + 1. To guarantee EE| (z) 11 < E² the total
number of iterations should be N (dee 2) and the total complexity is Σ M = O 4)
Obviously, using constant batch sizes obtains a better total complexity.
(3) In the deterministic setting, the first-order oracle directly outputs the accurate gradient V(2:()
V(z), which means = 0. Theorem 3.1 leads to ( < Odd/N). To guarantee E|| VEIV(= <
e², the total number of iterations should be N = Ode
(4) In the AMSGrad -GG algorithm, the momentum term is technical difficulty the convergence
proof. Proofs in the past works always use the MVI condition or convex condition like (V(*)) 2
(Dt: 2I =²) E 0 to control the gradient norms. However, if replace gt: with the momentum term my, the inequality above will no longer hold, and then we have to find another way control the upper bound of gradient norms. It's also worth mentioned that our proof can't 't be extended to Optimistic Adam (OAdam) since we need to guarantee that H 3 H2 ... in our proof. Actually, Adam may not even converge in convex case (Reddi et al. 2018).
& =²)
(5) Comparison with OAdaGrad: (Liu et al. (020) proposes the Optimistic AdaGrad (OAdaGrad) algorithm and gives convergence analysis on under Assumption I and Bounded Cumulative
Gradient Assumption (which assumes the existence of a constant 0
< 8 < 1/2 such that the
cumulative gradients are bounded as |1 & 8h.a for all k). Under these assumptions, they conclude that:
1 N
BIV(2)))
H, & O(1/NT-a)
On one hand, notice that NV (I the norm keeps changing. Since H keeps décreasing and may limit to 0 as k cc, its unclear what the real convergence rate in terms of the size of the gradient. It would be more convincing
is the average of the norms of V(z)). However,
we can upper bound the average of constant norms like 2/ Σ (x()(()) 13. On the other hand, the Bounded Cumulative Assumption though widely used in related papers (Zhou et al., 2018 Reddi
et al. 2018 Duchi et al. (201T), is actually a very strong assumption: Under this assumption, it holds
that 91 < ōka, which naturally leads to:
Σ E(V(2=)
N
1
1
N
< <O
(0
&
N
N1
which causes circularity on the argument. In this paper, overcome these two shortcomings.
Standard MVI and one-sided MVI conditions From Table D we can see that many related convergence proofs rely on assuming the MVI condition of - (2), which means (V(z), 2 2²) < Vz E Z. Although MVI condition is theoretically known be true in many standard supervised
deep learning settings (Li & Yuan 2017 Kleinberg et al. 2018 Allen-Zhu & Li 2020 Allen Zhu & Li. 2020: Li et al. 2018 2020, Allen-Zhu & Li 2020 2019). However, this is a rather unrealistic assumption for GANs: In some practical scenarios such as DCGAN (Radford et al. 2015), it is unclear whether the training objective can satisfy the MVI condition: While the generator might have consistent gradient direction towards the optimal generator (which is the one that generates the target distribution), it is very unlikely that there a "optimal discriminator" where the discriminator's gradient is pointing through the course of the training. Indeed, different generator
7

---

Under review as a conference paper at ICLR 2022
should in principle requires different discriminator to discriminate it from the target distribution, which precludes the MVI condition to hold on y.
Also, in practical scenarios like GAN, only care about the min- variable (which refers to the generator of GAN), and the optimally of y is not needed. Therefore, in the following part, we propose weaker version of MVI condition, which is the one-sided MVI condition. Recall that == (z, y). x = (x", y²) where I E X, y 2 = X x V/ and ( (Va(z), (z)). Then, the one-sided MVI condition implies that (V=(z), x²) & Vz E Z, which means for any E V the z-part of function V, -V (- 3) satisfies the MVI condition. Now we empirically verify that one-sided MVI is more likely to hold in practice in some simple applications of GANs. For 2, x" E Z:
Vo)(z)) =
=- (-Vi))--=)=--Vaa)---=>---=-
where: = = =""",)),""""", yy""))). We call the three terms above as total MVI, x-sided MVI and y-sided MVI respectively. 2 cecipptioooruuuurreeeeeee requires total MVT be non-negative, and Assumption requires x-sided MVI to be non-negative. After training Wasserstein GAN on the MNIST/Fashion MNIST dataset with AMSGrad-EG optimizer, we denote 2 == (2y,, y&) as the value of the k-th iteration, and x² = (x*,y") as the value of z at the last iteration. In the following Figure we plot the total MVI values (=V( 2 2²), x-dieed MVI values (-V2(2*), JFk - x²), and y-sided MVI values (- (2x),,),, 3/k y²) along the training trajectory. We can see that xr-ddeed MVI stays positive
while the total MVI does not, which means the one-sided MVI condition proposed in Assumption is
more realistic than the original MVI condition in Assumption 2
Under the one-sided MVI condition,
159
MNIST
(b) Fashion MNIST
Figure 2: This figure shows the MVI values along the training trajectory. As we can see, the blue curve stays above x axis in both experiments while the red curve does not. Since we use non-linear activations in the network architecture, this result is exciting. It's safe say that the one-sided MVI condition proposed by us fits the reality since the z-sided MVI keeps positive.
we prove in our next theorem that, the conclusion of Theorem 3.1 still holds once we slightly modify AMSGrad-FF to Extra Gradient AMSGrad with Dual Rate Decay (AMSGrad-EG-DRD) To the best of our knowledge this a convergence guarantee of an adaptive min-max algorithm with the weakest assumption ever needed. In the next section, we introduce the U'SGrad-EG-DRe algorithm and its convergence property.
3.3 EXTRA GRADIENT AMSGRAD WITH DUAL RATE DECAY
Now, we write down the one-sided MVI condition introduced above in Assumption 3 which is the weakest assumption ever needed obtain a convergence guarantee in min-max optimization.
Assumption 3 (One-sided MVI condition). The one-sided MVI of - V(2) has solution, which means there exists 2 = =(x", (x",)") E Z, such that:
(2), x²) > 0 holds for V2 = (I,y) E Z.
After slightly modifying AMSGrad-EG with a O(1/Vk) dual rate decay, we get Extra Gradient AMSGrad with dual rate decay (AMSGrad-EG-DRN) Its pseudo-algorithm is placed in the appendix. We propose its convergence property as follows:
Theorem 3.2 (Main Theorem 2). For the AMSGrad with Extra-Gradien and Dual Rate Decay algorithm,, given the objective function 6(x,V) v) R2 + R and V(z) (-v20, V v, == (V, (2), (2) that satisfy Assumption 7 and Assumption 3 as well as the initial point zo E Z, the iteration number N, a sequence of batch sizes [Mx] and constant learning rate n 3L. then the output of the algorithm satisfies the following inequality:
(AMSGrad-EG-DDe)
8

---

Under review as a conference paper at ICLR 2022
7
3
3
6
6
O
3
3
7
5
9
7
7 4
7
6
2
C
0
7
1
7
3
5
3
f 1
7
3
0
6
7
4
3
7
0
i
(a) A-EG
(b) A-EG-DRD
(c) SGDA
(d) A-EG
(e) A-EG-DRD
(f) SGDA
Figure 3: Generated MNIST and Fashion-MNIST figures by the three algorithms after 10k, 20k, 50k iterations. A-EG and A-EG-DRD stand for AMSGrad-EG and AMSGrad-EG-DDR
(15+3) log NB + G)²
GdD + G)²
15 + G)
N
B]]V2 <
Σ
N82
21²
N8
M
t=1
48GD(6 + N
108 G)
N
B1 +
N1
N6
It
Similar Theorem 3.1 in the deterministic setting where a the total complexity Ö 2). In the stochastic setting, we have: (=) < O(d/N) + (1/NN) Σ 1/M,. When we use constant batch sizes MA- = (11/e²), iteration number N should be (de ((ds-2) in order to guarantee that TE| V (=) & e². So the total complexity should be Ode--1)
EXPERIMENTAL RESULTS
In this section, we use experiments to verify the effecttivnness of AMSGrad-EG and AMSGrad-EG DRD algorithms by applying Wasserstein GAN (Arjovsky et al. 2017) the MNIST (LeCun et al., 1998) and Fashion-MNIST (iio et al. 2017) datasets our experiments. More experiments will be shown in the appendix. The architectures of discriminator and generator set to be MLP. The layer widths of generator MLP are 100, 128, 784 and the layer widths of discriminator MLP are 784, 128, 1. We set batch sizes as 64, learning rate as le-4 and we compare AMSSGrad-EG, AMSGrad-EG-DRD and SGDA by printing their generated figures after 10k, 20k, 50k iterations in the following Figure 3 We use the Tensorflow framework (Abadi et al. 2016) complete our experiments. As result, unlike the non-adaptive SGDA algorithm, the two algorithms proposed by us perform better than the non-adaptive SGDA and their generated figures are realistic, which shows their effectiveness.
5 DISCUSSION AND FUTURE WORKS
This work fills up the blank in the theory of non-convex non-concave min-max optimization as well as GAN's training. We bridge the gap between theory and practice and provide the theoretical guarantee of the one-sided convergence of Adam under one-sided MVI condition, which perfectly matches the empirical observation. To the best of our knowledge, it is the very first proof for the convergence of Adam-type algorithms in non-convex non-concave min-max optimization. Future follow-up works can go further on the following two directions: (a) Figure out which part of Adam-type algorithms play important role on the outstanding performance: automatic tuning of learning rate or local geometry adaptivity. (b) With both the discriminator and generator of GANs to be overparameterized 2-layer ReLU networks, it would be influential work to figure out the convergence property, the converging limit and the training trajectory of min-max optimization under multiple optimizers like Adam and SGDA that can get some intuition their differences.

---

Under review as a conference paper at ICLR 2022
REFERENCES
Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthicu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et Tensorflow: system for large-scale machine learning. In /2th USENIX symposium on operating systems design and implementation (OSDI 16), pp. 265-283, 2016.
Zeyuan Allen-Zhu and Yuanzhi Li. What can resnet learn efficiently, going beyond kernels? arXiv preprint arXiv:/905. 10337, 2019.
Zeyuan Allen-Zhu and Yuanzhi Li. Backward feature correction: How deep learning performs deep learning. arXiv preprint wrXiv2201.044111 2020.
Zeyuan Allen-Zhu and Yuanzhi Li. Feature purification: How adversarial training performs robust deep learning. arXiv preprint arXiv:2005. 10/90, 2020.
Zeyuan Allen-Zlne and Yuanzhi Li. Towards understanding ensemble, knowledge distillation and self-distillation in deep learning. arXiv preprint arXiv:2012.098/6, 2020.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein generative adversarial networks. In International conference machine learning, pp. 214-223. PMLR, 2017.
Waiss Azizian, loannis Mitliagkas, Simon Lacoste-Julien, and Gauthier Gidel. A tight and unified analysis of extragradient for whole spectrum of differentiable games. arXiv: Learning, 2019.
Amitabh Basu, Soham De, Anirbit Mukherjee, and Enayat Ullah. Convergence guarantees for rmsprop and adam in non-convex optimization and their comparison to nesterov acceleration on autoencoders. 2018.
Xiangyi Chen, Sijia Liu, Ruoyu Sun, and Mingyi Hong. On the convergence of a class of adam-type algorithms for non-convex optimization. In ICLR 2019: : 7th International Conference on Learning Representations, 2019.
Gobinda G Chowdhury. Natural language processing. Annual review of information science and technology, 37(1):51-89, 2003.
Cong D. Dang and Guanghui Lan. On the convergence properties of non-cuclidean extragradi- ent methods for variational inequalities with generalized monotone operators. Computational Optimization and Applications, 60(2)2777310, 2015.
John Darzentas. Problem complexity and method efficiency in optimization. 1983.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training gans with optimism. In /CLR 2018: International Conference on Learning Representations 2018, 2018
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina N. Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. In Proceedings of the 2019 Conference of the North American Chupter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long and Short Papers), pp. 4171-4186, 2018
John C Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12:2121-2159, 2011.
Gauthier Gidel, Reyhane Askari Hemmat, Mohammad Pezeshki, Gabriel Huang, Rémi Le Priol, Simon Lacoste-Julien, and Ioannis Mitliagkas. Negative momentum for improved game dynamics. In The 22nd International Conference on Artificial Intelligence and Statistics, pp. 1802-1811, 2019.
Ian 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 Information Processing Systems 27, pp. 2672-2680, 2014.
Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep Learning. 2016.
10

---

Under review as a conference paper at ICLR 2022
Philip Hartman and Guido Stampacchia. On some non non-linear elliptic Acta Mathematica, 115(1):271-10, 1966.
equations.
Ya-Ping Hsieh, Panayotis Mertikopoulos, and Volkan Cevher. The limits of min-max optimization algorithms: convergence to spurious non-critical sets. arXiv preprini 200i::2006.090665 2020.
Alfredo N. Jusem, Alejandro Jofré, Roberto Imbuzeiro Oliveira, and Philip Thompson. Extragra- dient method with variance reduction for stochastic variational inequalities. Siam Journal on Optimization, 27()):686-722 2017.
Erik Johnsen. Arrow, hurwicz and uzawa: Studies in linear and non-linear programming, stanford univeristy press 1958. 229 S., 7,50. Ledelse and Erhverssoknomii 23, 1959.
Anatoli Juditsky, Arkadi S. Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-pra prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Diederik P. Kingma and Jimmy Lei Ba. Adam: A method for stochastic optimization. In ICLR 2015: International Conference on Learning Representations 2015, 2015.
Robert Kleinberg, Yuanzhi Li, and Yang Yuan. An alternative view: When does sgd escape local minima? arXiv preprint arXiv: 067 2018.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 36(11):227--222) 1998.
Xiaoyu Li and Francesco Orabona. On the convergence of stochastic gradient descent with adaptive stepsizes. In The 22nd International Conference Artificial Intelligence and Statistics, pp. 983-992, 2018.
Yuanzhi Li and Yang Yuan. Convergence analysis of two-layer neural networks with relu activation. In Advances Neural Information Processing Systems, pp. 597-607. http://arxiv.or//ab/// /tt////55008888 2017.
Yuanzhi Li, Tengyu Ma, and Hongyang Zhang. Algorithmic regularization in over ver-parameterized matrix sensing and neural networks with quadratic activations. In COLT, 2018.
Yuanzhi Li, Tengyu Ma, and Hongyang R Zhang. Learning over-parametrized two-layer neural networks beyond ntk. In Conference on Learning Theory, pp. 2613-2682, 2020.
Qihang Lin, Mingrui Liu, Hassan Rafique, and Tianbao Yang. Solving weakkyycoovee--eeklly concave saddle-poing problems as weakly-monotone variational inequality. 2018.
Mingrui Liu, Youssef Mroueh, Jerret Ross, Wei Zhang, Xiaodong Cui, Payel Das, and Tianbao Yang. Towards better understanding of adaptive gradient algorithms generative adversarial nets. In ICLR 2020 Eighth International Conference on Learning Representations, 2020.
Ilya Loshchilov and Frank Hutter. Decoupled weight decay regularization. ICLR 2019 7th International Conference Learning Representations, 2019.
Liangchen Luo, Yuanhao Xiong, Yan Liu, and Xu Sun. Adaptive gradient methods with dynamic bound of learning rate. In ICLR 2019: 7th International Conference on Learning Representations, 2019.
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 ICLR 2019 7th International Conference on Learning Representations, pp. 1-23, 2019.
George J. Minty. Monotone (nonlinear) operators in hilbert space. Duke Mathematical Journal, 29 (3) (3):341-346, 1962.
11

---

Under review as a conference paper at ICLR 2022
Mahesh Chandra Mukkamala and Matthias Hein. Variants of rmsprop and adagrad with logarithmic regret bounds. In LIIMCMMI 17 Proceedings of the 34th International Conference on Machine Learning Volume 70, pp. 2545-2553, 2017.
Yurii Nesterov. Dual extrapolation and its applications solving variational inequalities and related problems. Mathematical Programming, 109(2):319-344, 2007.
B.T. Polyak. Minimization of unsmooth functionals. Ussr Computational Mathematics and Mathe- matical Physics, 9(3):14-29 29, 1969.
L. D. Popov. A modification of the arrow-hurwicz method for search of saddle points. Mathematical Notes, 28(5):845-848, 1980.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks, arXiv preprint arXiv:1511.06434, 2015.
Sashank J. Reddi, Satyen Kale, and Sanjiv Kumar. On the convergence of adam and beyond. In ICLR 2018: International Conference on Learning Representutions 2018, 2018.
Maziar Sanjabi, Meisam Razaviyayn, and Jason D. Lee. Solving non-convex non-concave min-max games under polyak- Eojasiewwa condition. arXiv preprint arXtv:/8/2.00287, 2018.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: novel image dataset for benchmarking machine learning algorithms. arXiv preprint arXiv:1708.07744 2017.
Matthew D. Zeiler. Adadelta: An adaptive learning rate method. arXiv preprint arXiv:1212.570. 2012.
Dongruo Zhou, Yiqi Tang, Ziyan Yang, Yuan Cao, and Quanquan Gu. On convergence of adaptive gradient methods for nonconvex optimization. arXiv preprint arXiv:1808.05660 2018.
Difan Zou, Yuan Cao, Yuanzhi Li, and Quanquan Gu. Understanding the generalization of adam in learning neural networks with proper regularization. arXiv preprint 13311 2021.
12

---

Under review as a conference paper at ICLR 2022
A PROOF FOR THE CONVERGENCE OF AMSGRAD-EG
We recall that in the 1-th iteration of Extra-Gradient AMSGrad, our update is as follows:
my = - + (1 - B1e)9t-1, 1/- = max((320-1 + (1 -2)92-1, 8c-1)
H. = 57 + Diag( Vvt), &, = - + 11 H +m m
(I)
th = B10m, + (1 - f1.)g,, 0t = max(332 + (1 - .2)
H. = 5T + Diag( V 0t), 2t = 1 + 1) H, -
Now we begin to prove Theorem 3.1 (Main Theorem 1). Before that, we prove that as the weighted sum of stochastic gradient, the momentum terms my, rit, are also contained in l2 ball with radius G.
Lemma A.1. There exist upper bounds for both velocity terms Us, Dt and momentum terms my my (1) For Vt E N, almost surely, the momentum terms |mmella & G, lhaalll & G.
(2) For VL E N, almost surely, the velocity terms |e, & G2, 00,al & G hold for Vi E [d].
Proof of LemmalA.1 Actually, this lemma can be simply proved by using the method of induction.
Since we ve assumed that (z)ll2 < G almost surely holds for 2 E 2 = RR4 so || < G and
l0all2 < G almost surely holds. Therefore, by knowing that my mi 0 0 |moll
|moll < G and once | < G, | ll2 & G. we have:
[mm/l22 = 1 + (1 -
lll2 & BLX 1 + (1 B1a < (1- - BIx)G + BING = G
| [181umm + (1 3Ix) 1l2 < 9I mm + (1 - B1x) l2 & (1- - BIx]G + BI, G.
Similarly, the upper bound for velocity terms can also be easily proved.
Lemma A.2.
|| z² = < -1
- 2²11?;, - | - -&el??, 83 + 112 - zel??, - -(n Ec, - -2²) + 11
Here, & = Ô1 - V(t)) = M. EM
- -((E).
Proof of Lemma
A.2
According to the update rules:
1|ze- x² ==11?,
||t-1 77- f1, m z² =²11? it.
|| + 77 HH, m =²112,, || + 17- H. 1 m zell?
= || z² -12 - -112-1 - 2z 122. + 2(11 miz 2t x²)
= || - x= 112 || - 4s + 2 - 2,112, A. + 2(11 nu 2t - -2.)) + 2(11 mis, 2e - x²)
= || 2" 112
|| - & 1/,, 11 - = =e122, 2 2,H - -i)); &r - 21)
+ +2(n mr, 21) + 2n mi, & 2²)
|| x" 1/ ||ze_1 - &n 1224 -112e =e + 2nn m 2r - =z)
+ 2(2 ε, H, (2: - 24 + 17. -m+))
|| 2" 112 f1, || - & 11?
11 -2el??, it,
+ 2(n me, En - 2²)
+ 2(2 2, Ai (21 - -2,)
||=--1 =" =112,, || 2x 11/. +1 - =01 + 22n mi, 2n =z)
Notice that 9. = V(&) + E.. Since 8² is a solution of MVI which means (V(2), 2 - 2²) & 0 holds
for Vz Z, 50 (É+), & x²) < 0. Therefore:
(n) mr, 2 - =²) (n (Brm: + (1 - (rx))t), & x²) < (n dc, & - =²) + (n - Pre(me 9c); 2s 2²)
< (1) (V(+)) + &.), 2, =²) + n1e I| gell2 || - -0===1i 2"112
(0)
< (né,, & - =²) + 4n.
13

---

Under review as a conference paper at ICLR 2022
Here, (a) holds because ||mm Se l2l2 < || mella + llăell2 2G, 1| =2112 & 2D and by using MVI property, (2()), 2 - 2²) v O.
Combine it with the inequality above, obtain that:
|| =" 1 <
||=-1 > 1| - Eell B. + 1| zel - 2( 6,, - =²) + 1..
which comes to our conclusion.
In the lemma above, (17 Ée. 24 - =²) has zero mean. So it can be ignoring when taking expectation. Next, we upper bound the 1| 21 2 term.
it.
Lemma A.3.
G2
12
-He & zell? it. E 2n7² -1((1) - H-,HH')mm mmell +
11 - 2 -2-1 11/ ft.
6
8
+ 12n2 (1e:112,. + 1le.-11?,,)
Here, E(-1 91-1 (2(-1) and É = 90 V(2)).
Proof of Lemma A.3
According to the update rules
I we know that 2, 2c 11 (Ht, ii
H,-m,) m.). Therefore, we upper bound the term || ze 2 H. as follows:
1| =ell? =17². | -mme - H₂ H -1 (m+ - mi) + (H, mmel?
& 2n7² (lite melli, + +I((it= - HH (1'))mll?'
(0) 2n/ |1A,, H )m 12g,
+ +20/ 1181e(mm - -11-1) + -Bie)(0 - 9t -t- 11
(
< 2r |1A, - -H, mm 11...
+ 44²² ( ml - -mp-11 A,, + (1 - B1e)2 - -c- 11x.))
(9)
+ 16n2 G7.G2
< 2n
|| H )mg l1?
219: -91-11 AT.
16n G2 Bi
- 2n ||A, H )
+
((()) V(2-1) + Es - 1111
(c)
167 G2 B7.
< 2n² [( - -HH -H,'mmm) ))mml
+
+ +2n² |IV(&) - (E
8
+ +121? (1Eal12, + ||E--1113, .)
(
161 BL.
-1 - 2t-1 2 R4 12
< 21, |(AA
f7:
+
5
52
+ +22?? (11aalir,, + 11ee-111?1,-)
Here, (a) holds because m, = -,, 1 + (1 - (1,) m4 = 3 + (1 B1r)ge, and then:
m: m4 3m - - + (1- (1 9t-1).
(b) holds because ||a + b12 < (Aallcc + [b|c]² < 2[|a||] + =1b12)) and (e) holds because of the
similar reason: || + y + 2 2112 & (1|=lcc + 1ellllc + ||=||c) < 3(1=112 + 11lll + [| (c) holds
because (1 1 320)2 < 1 and
m,
m 1|
4G
|l - M 12
8
(d) holds because 9. = V(+)) + & and 9:-1 = V (2=-1) + (f) holds because of the following fact:
61 = Ho = H - H = A Σ - A _....
or equivalently:
1 I H 7 A H
A ...,
8
14

---

Under review as a conference paper at ICLR 2022
which leads to 1|= < ||Er-111 H. Also, V(.) is L-Lipschitz continuous and 81 = He, so:
T,2
(Iv(2)) - -((--)) & 8² & - 21-1
4 5L we have 12n < 2.
Since our learning rate
Now, we can combine Lemma A.2 and Lemma
1|2 - -2" < 1|
='11i,, - -112-11 - Bellii. + E 2 - =²) + 8n31.GD
G2 Bi.
12n
+ 21)² ||(Ht, - 11, mmell +
+
11 -t- 12..
82
+ 12n2² (1év112,, + ||εe- 11,
Since 12 6z
< 1 2.
therefore:
|| - =" =3 < || - =01121, - -1 || -eel??.. + 2/n E,, &g - ==) + 81131; + 12
1
+ 21/² -1((1 H mm= + 1212 (1é:11?7; + || 1 1
After taking expectation and summation over t = 1.2..... . N, we obtain that:
G6
E1 - - 20
E ||--1 - =111 - -11= - x² =111
8nBI,GDD +
8
1=11
+ 277²
Σ El| H, 1 H. m R1
+ 12n2²
ΣE E
[|Eel13 H.
l| 1ee=1117.
1=1
(2)
Since 1 - = 111--11 H, me mel. and ((=-22) = 11-1-81-1 m4 - 12-1))
we know that:
|IV 111 1- 1|m+ Bre 99--1) Ec- 11, 11,
[Imellnn. + 11.10(mme111 91-1) )l P || (1,1))
3
-9t- 11-1) 1 H.--
+ ||==-1
3 |1H mmll?
(3)
2 3i.
3
+ -311Ec-111,, 1,+ y/2
|| En ll
After combining Equation
2 and Equation 33, it holds that:
6
N
4881GGD
108n Bi.
1--1--2113 - 1| 2=112,,]
Σ
172
7
N
+ 12
Σ
mm )), ft
+
75
E
||
A +
||e. 11 112
(4)
In the following steps, we will upper bound the four terms above on the right side one by one, and we start from the first term.
Lemma A.4.
||--11 2" =1,,,, -11= >=11?,]] dD (8 G),
which is constant.
15

---

Under review as a conference paper at ICLR 2022
Proof of Lemma A.4
Notice that
N-1
||--1
2" 11
-1|z - -="1l 11100 ==Ilito
Σ
||
="Il%,,,
1| ==11?
t=1
N-1
11 - =z'1l
+
- -=== -0====(((f++) ((+et) H.) (2+ - =
N-
< D2 tr( (H()
Σ
D² . - (t((tt))) = D² tr(HH)) & 16
which comes to our conclusion.
For the second term, it's easy to see that:
GD
G0
48GD
G0
B1c +
(5)
7
7
8
Next, analyze the third term. Lemma A.5.
(
Σ I(H, A1,1))mm melll <
82
Proof of Lemma A.S
For any 5 & x < y, notice that:
1) = (y x²
1 2
Y-
x
-
(6)
z²y
x
82
Therefore, we have:
(11 - 111,1)mell ft,
Σ m (11 -1 M1, 1m
G tr (1I, - A (H) - (1,1))
N G²
[tr(ff)) - -tr(He))
82
G2
d + GG)
tr((fN) <
d(ō G)
8
8z
82
Here, (a) holds because of Equation 6
Li
Finally, come to the noise term Σ batch sizes M,. Obviously, we have:
E
||eel1?,- H1
+ ||E/-111 112
which is closely related to
1 8
o²
E El
Elléel12 &
8 M,
Similarly,
1 2²
E H g
M,
Therefore, we can upper bound the expectation of the noise term as:
N
20
N
|
2 H + ||e. 112 H
<
(7)
8
M
t=1
16

---

Under review as a conference paper at ICLR 2022
Finally, after combine Equation 4 with Equation we obtain that:
Equation and Lemma A.4
Lemma A.5
N
6dD2 (6 166+0 G)
12dG (6
G)
150g² 2
1
17?
8
M₁
48GD N
108 N
Bie +
B1
8
tm
Since for Vl,
[[V
2 84G (zt 1)1,2, therefore:
N
6d + G)
12dG G)²
15 (8+G) G)
N
172
82
M
t=1
(8)
48GD + G)
108 G
31
Σ
$1
"
which comes to our conclusion.
B PROOF FOR THE CONVERGENCE OF AMSGRAD-EG-DRD
In the t-th iteration of AMSGrad-EG-DD
update is follows:
m. = -1 + (1 - -1e) 0z max ( + (1 - 32)9 0/-1)
H, 57 + Diag( (vt)), 2, = (er.9e) (#+-1 + 17 (H;)) Ut-1 +
1)
-HH))-
(H?)
Vt
(9)
mn = B1.m + - Bie)@r, 82 = max (B2 + (1- 32) vt)
A. 5T + Diag( V 0t); 2t = (zt. W+) = (z4-1 + (H₂) m Ut
+
Vi
11
-
Most parts of this convergence proof are similar to the convergence proof of AMSGrad-EGG Lemma still holds.
Lemma B.1.
| x² "ppp -112-1-2"11 x01 1 2z f1 + || xel sel1?pg + +2 -7, fr - 8n.I.GDD
Here, ET = 07 Va
(&))
1 M,
Σ
1 Va
Mr
(2::
(2))
We can use the same technique of Lemma A.2 to prove it. Next, we obtain the next lemma.
Lemma B.2.
16
12n
| zz 12 < 2n² [[((()))) (H1F) mmm 12 +
11 - 2 11?
5
82
+ 12n2"
11 ( + || 1(
Here, Et-1 It-1 V(z-1) and é g. V(2))
We prove it by using the same technique Lemma A.3 Since we have 12 & 1. Now, can combine Lemma B. and Lemma B.2
| x 11 < ||-:-1 - xx 11 - || - 1el1 + 2(n Et, E,
x²)
+ Sn
G 32
+ 2nn² -1(((1(;)))) (115) -1))))1)mm1 1m 11as
+
1l - -z- 111
6
2
+ +1ny²
+ I1ef- 11ef=1l(ess3-1))
17

---

Under review as a conference paper at ICLR 2022
After taking expectation and summation over t 1,2..... ................................ NN, we obtain that:
16 Bic
E
Bell H
| - x²1 11 - x² I1
Bg +
N
+
217²
Ell( ((t - ((1,))~))1 A + 12n2²
E
| (Ap)) + -112-11(0pp)))
1=1
1
+
E lyt-1 - 't "1l1221
2
1=1
(10)
Since ||x2-1 2el12,; 1 (11F) mfl and (=((z-1) Fi-1 -7-1 mm 31.
I--) 1.-1, we know that:
(V2 l|m - f1e( - r4-1) - cr- -f-1l(1a)>+
[1mmil(up)] + 11 of
+ ||= ||(
(131n( - -6- -(-1)((m))= + || 1e(=1[(1))))
+ (13-1((17)-11
12G Bi.
3
+ 3|1 11( + up
|-|-1 tx lp
(11)
After combining Equation
(T))
and Equation I1I it holds that:
N
6
N
N
483,GGD
108 G2 Si
<
E
|1--1 - 101 1 - 101 1ig
+
11
5
N
+ 12
B(((((r;)) (02)-1)m²
+
75
E
|| [1671|:055 (Az)-) + -lee-_1 11
3 1/2
Bllyt-1
Dr 1
(12)
In the following steps, we will upper bound the five terms above on the right side. Actually, the first four terms can be upper bounded by using the same technique in the convergence proof of AMSGrad-EE EG algorithm above.
Lemma B.3.
11,e x² x1(ppp] Σ |1--1 x² x01
< dD (6 + G),
which is a constant.
Lemma B.4.
N
d G G)
Σ ((()))=2((A))))))
82
Finally, the last term can perfectly bounded by the (1I/Vl decayed learning rate.
N
2
Bllut-1 - De
E [((
-1m))
m1
A?
1=
n
G
G2
B
+ (o+log log
(13)
8
To sum up, we eventually get the equation that:
(15 + (15+3)
log N) (6
6d + G)²
150 + G
N
B]]V((>)] <
N2
21p
No
M
18

---

Under review as a conference paper at ICLR 2022
48G + G)
Σ BIc +
N
G
+
G)
Σ
N
Nn
N8
which comes to our conclusion.
C MORE EXPERIMENTAL RESULTS
In this section, we further use experiments to verify the effectiveness AMSGrad-EB -G and AMSGrad- EG-DRD algorithms proposed by Also, show that the one-sided MVI condition is more feasible than standard MVI condition even in a more complicated setting. Here, we use DCGAN (Radford al., 2015) CIFAR1O dataset. We our batch size 100, learning rate 1e-4 and compare AMSGrad-EG, AMSGrad-ECC -G-DDDD and SGDA by drawing their generated figures after 50, 100, 200 iterations in the following Figure 2. The algorithms proposed by again perform better than the non-adaptive SGDA. After training DCGAN on the CIFAR 10 dataset with AMSGrad-EG
optimizer, we plot the total MVI values (- (2k), 2 2"), z-sided MVI values
3'k x²)
and y-sided MVI values V,, 24
ME u²) along the training trajectory as the following Figure 4
35
X-sided
Y-stded
25
Total MVI
20
10-
100
200
300
400
500
Iterations
Figure 4: This figure shows the MVI values along the DCGAN's training trajectory. As we can see, the blue curve stays above z axis in the experiment while the red curve does not.
19

---

Under review as a conference paper at ICLR 2022
(a) AMSGrad-EG
AMSGrad-EG-DDE
SGDA
Figure 5: These the generated CIFAR10 figures by the three algorithms after 50, 100, 200 iterations.
D STOCHASTIC EXTRA-GRADIES AND ADAPTIVE ETRRA-GRADIENT ALGORITHMS
In previous paper (Liu et al. 2020), the authors propose the Optimistic Gradient (OG) method and Optimistic AdaGrad (OAdagrad) method. In this section, we extend them to the Extra-Gradient type algorithms: Stochastic Extra-Gradien (SEG) and Adaptive Extra-Gradient (AEG). We put the result the appendix because it just a by-product of this research and not our main result.
Before we introduce our the Stochastic Extra-Gradient (SEG) algorithm, by using different batch sizes in each iteration, as Algorithm below.
Adaptive Extra-Gradient method, we slightly modify
Algorithm 2 Stochastic Extra-Gradient (SEG) with batch size
Input: The initial state åσ 2n 0. constant learning rate 7,, Stochastic First-order Oracle (SFO) ((2; {). sequence of batch sizes {m 1x21-
Output: 24, is uniformly chosen from (0, 1, .......AA. N 1}.
1: for I,...,N N do
2: (Gradient Evaluation) 9k-1 my ΣMH (( 11-1)
(Shadow Update) 24 [= + Ik-
4: (Gradient Evaluation) gh- -1 mi
E V(áx: (
5: (Real Update) 2 = 12 + 17 9k-1]
6: end for
Algorithm is a basic idea on the design of AEG algorithm. Here, we use constant batch size m and let 9h- 1 Em V( ( = m Σm V(2,, ( ) be the estimated gradients 2k-1 and Ex in the k-th iteration. Also, 91.k is the concatenation of .1,....9h and 91:k, is its i-th
20

---

Under review as a conference paper at ICLR 2022
row vector. Similarly, Pusk is the concatenation of 9o. ... 9k+ and 9osk,a is its i-th row vector. Note that all the matrices H3, SІ are diagonal so they don't 't require extra computation complexity.
Algorithm 3 Adaptive Extra-Gradient (AEG)
Input: The initial state 2g 20 0, Ho Ho 81, constant learning rate 7, Stochastic First-order Oracle (SFO) (2:; {), a constant batch size m.
Output: 2t, t is uniformly chosen from {0, ........
N 1}.
for k= L...... do
2: (Gradient Evaluation) 9k-1 E Vi
3: (Gradient Concatenation and Norm Calculation) Update go.k = 190.2-2 9k- Sk
I| (90:k-1,: 915k-1,1) |l2 1, and Hę-1 ó1 + (skg()
4:
(Shadow Update) & = 2k + H1-19t-1 Σ V(2xi
5: (Gradient Evaluation) 9k-1
6:
(Gradient Concatenation and Norm Calculation) Update 91.k ( &8-18
|| (g0 (1sk,s) |l2 1,2,.... d and Sk-1 = + diag($k-1)
7: (Real Update) 2 = 2k-1 + 1
8: end for
Now, we introduce the following two theorems (Theorem D.I and Theorem D.2) which compare the convergence rates SEG and its adaptive variant AEG. Theorem D.1 (Convergence of SEG). There is an algorithm (Stochastic Extra-Gradient), which given:
A Stochastic First-order Oracle (SFO) access to the objective function Φ(x. X x R where X S IR , S R which denoted as: ((z;)) {) and satisfies the following conditions:
E[V(22;) = (-V V V and [I[V(=; E) - -V(=)]I E²²
Here, 2 == (x, y) and := X' x V. Also: the corresponding MVI function of - V has solution Z, which means (z) 2*) > 0 holds for Yz Z.
A positive real such that V L-Lipschitz continuous with respect || 112-
The learning rate 17.
An initial point 2n E Z.
The iteration number N.
The sequence of batch sizes each iteration {mx (mgligi
Then, we output result z E Z which satisfies:
4 20
22 +
50m² N
o²
[T) <
m&
where ra (a(z) 1 v(2))ll2 and n < aL- 1f2 = R1 then the projection operator
Il is the identity, and (2) a [V(2))2. The inequality above becomes:
41120 - 12
N
d2
(+] &
m&
Compared with Optimistic Stochastic Gradient (OSG) method proposed in (Liu et al. 2020), we can have a larger learning rate in this theorem.
Remark. Let 1) AT- If the batch sizes are constant, which means my = m for Vk. In order to guarantee that [Z[[(2)]** < e2, we have to make m O(1/s²) and N = O(L2/E2), and the total complexity is EN my = mN O /eA). In another scenario where my 1: + 1 is increasing sequence, in order to guarantee that (2) & e?, we have to make N = O /62 and then the total complexity is EN my EN= (k (6T7/64)
21

---

8 Under review as a conference paper at ICLR 2022
Theorem D.2 (Convergence of AEG). When our objective function 6(x.y) y) satisfies Assumption I and 2, as well as the bounded cumulative gradient condition, there exists an algorithm (AEG), given:
A Stochastic First-order Oracle (SFO) access to the objective function ó(x, y) R IR, which is denoted as: ((z; and it satisfies the following conditions:
E[V(2; V()) - V. v and (2] V(z) o².
Here, =: (x,, y) and = Rui+na Rd where d == ni + n2. Also: the corresponding MVI function of V has solution =" Z.
Positive real numbers G, such that (V E) & G almost surely holds.
A positive real such that V L-Lisschitz continuous with respect || 11-112-
A universal constant > 0 such that ||=x - ==112 < and for all the points on the trajectory of our algorithm.
An initial point 20 Z.
The iteration number N.
A constant batch size m.
A constant 0 < a < 1/2 such that: the cumulative gradients are bounded as: [g91: 01:k,i)ll2 & 26 ka for all i,
The constant learning rate 17 < 41.
The output results 2o; 21,..., 22....,2N-1 satisfies the following inequality:
1 N E N
16dD28/1p + 200d5 + 40dG2/6 506o² f + 2G2
IV()))
NI-a
N
k=0
we switch the assumption of MVI condition (Assumption 2) to the one-sided MVI condition slightly modify the Adaptive Extra- Gradient (AEG) method to Adaptive
(Assumption 3), Extra-Gradee Gradient with Dual Rate Decay (AEG-DRD), where the learning rate {8k variables set - In the Algorithm 4 below, Hy Diag( (A,, B&) and Ss. Diag(CR, D2) where for each k N, Ag, Ck R x and Bg, Dj R22xn2 Also, 9k (gh gh) and ğk (0%,0) 9k) where gf o% E R and 0% 0% E TR=
Algorithm Adaptive Extra-Gradient with Dual Rate Decay (AEG-DRD)
Input: The initial state åg First-order Oracle (SFO) ((2: E). constant batch size m.
0, Ho Ho ōT, constant learning rate n, Stochastic
Output: 2, where is uniformly chosen from {0, NI
N...NN-
1: for k= 1...... N do
2: (Gradient Evaluation) 9k-1 = Em V(z-- Et-
3: (Gradient Concatenation and Norm Calculation) Update go.k = [90:6-2 Jk Ik-1), 8k-1,i = |l (9u:k-1,6 91:k-1,1) [[2 = 2, and Ha-1 5T + diag(sk-1).
4: (Shadow Update of 2) St Tk- + 17 1-1-h-1-
5: (Shadow Update of y) 0x = Uk-1 + B B
6: (Gradient Evaluation) 9 m
D. V( El )
7:
(Gradient Concatenation and Norm Calculation) Update 91.k [6 8x1,88-1.5
|| (10 )1.k,s) ll2 i 1,2,.... d and Sk-1 81 + (1))).
8: (Real Update of x) I = Tt- + m C 1
9: (Real Update of g) yk yk-1 + E D=10
10: end for
22

---

Under review as a conference paper at ICLR 2022
Theorem D.3 (Convergence of AEG-DRD). When objective function 6(x, y) satisfies Assump- tion and 3, as well as the bounded cumulative gradient condition, there exists an algorithm (AEG-DRD), given:
A Stochastic First-order Oracle (SFO) access to the objective function d(x, v) Rnitte
IR, which denoted as: (=;; and it satisfies the following conditions:
[2) = (z) = 2= V v and [z] V(2)ll ~
Here, 2 = (x., 1) and = IR + = I2d where == 7i + 12.. Also: the one-sided MVI function of V has solution 2" E Z.
Positive real numbers G. such that [V(2 & G almost surely holds.
A positive real L. such that V T-ILipschtzz continuous with respect || 11-112-
A universal constant D 0 such that || 2*112 D and for all the points the trajectory of our algorithm.
An initial point E Z.
The iteration number N.
A constant butch size
1/2 such that: the cumulative gradients are bounded as: A constant 0 & & 25 ka for all i,
[[g., (1:2,))l2
The constant learning rate nj &
8 AL'
The output results 20, 2 2N-1 satisfy the following inequality:
16dD25/1 + 200d8 + 40dG 24dG2 500o2 2
E
| (V (1
N
N1-a
N
D.1
PROOF THEOREM D.I
We recall that in the 1-th iteration of Stochastic Extra-Gradient (SEG) algorithm with batch size, we have the following updates:
& = ll
V Va (2-11: 1i
= 1lz 1 9t-1]
= ll
21-1 + 17
V(ae: (1 1/
= II [ze-1 + 17 91-11
me
Before start our proof, we introduce simple properties of the projection operation IT as follows, where 2 C Rd is closed and convex.
Lemma D.1.
(I) | +2))))++1IZZ2) 2|12 - z|I² and (IIz(x) - x2, - & 0 holds for Va E E Z. Actually, the first inequality a simple extension of the second one.
(2) The projection operator TT is compression, which means for Vx. E Rdd it holds that:
| lz(2))l2 & ||x -vl2--
Now, we can start our formal proof.
Lemma D.2.
Pk =01 2 & ||=t-1 - 2²112 (1- || - =2 11 E사 I|2
+ (1Ex<<1 1|Éx-111 1 (22) + 2( =,, Ex-1)-
Here, Ek-1
- V(z=-1 1 ((E-1) and ēk-1 me Em V(Es; (t)):t) (2xx).
my
23

---

Under review as a conference paper at ICLR 2022
Proof of Lemma D.2 According to the Property (1) of Lemma D.I
we know that:
2| - 2" 2=113 = ||T 2k-1 + 7 9k-1] - ==1 < | + 9k-1
201 1| + 17 9k-1 2x=12
1|=x-1 =1 - 2 + 2(17 Oh- zx x²)
|| 2²1 1|2 - | - 2x + 24 - 2 + +(1 9h 1: 2x -2") ) + +(17 11 2xr
-1 2²1 1zk-1 2x - -12x =x11 - 2(2k-1 -2,, 2bm
+ +1 (V(x)) + Ex-1), 2s ==²) +2211 2(m 9x-1, 2k =xx
-1 - ==1
- 1
1& - 2x11² + 2(2x
2k: 2x - -k--1 -1 -7. gh-1)
+ V( 4x --² + 2(1 6 & =²)
Since 2" is a solution of MVI inequality, we know that for V/2 E 2, it holds that (V(2), - 2*) < 0, Therefore:
(V(S)), - =²) & O.
Also, since 2n = Izz + 17 9k-11 according to the property (1) of Lemma D.1 we have: (ax 2k: 2 (#k-1 1) 9k-1)) 1)) & 0.
After combining all the three inequalities above, we have:
1 < ||= ==1 || -2 |1 2/ + 2/n Ea 1, 2x 2²)
+ +((2x 2k, 2 - =k-1 1) 9k-1 + 1) - - 11 gh 9k-1)
|| - ==11? - || - 1x - 112x - 2x12 2 + 2(m Ek- 2x 2*)
+ +2 =k,"1 -k-1 11 9)-11)
(a)
|zk-1 1=1 ||-k-1 111 2-2 11 2x11 + 2n|l =xll -19h-
9k-1l
+ +2nn- Ex-1, 2x 2²1)
(6)
| =0112 --12-1|==--> ||=k-1 1x 1- - 1| 1x + 11921 11-1
+ 2(1 - 1 2 - >²)
(14)
Here, (a) holds by Sccwha-Schwarz inequality, and (b) holds because by using the property (2) of
Lemma D.I. we know that
|| - =x = [= + 1k-1] - IT (=k-1 + 7 9x -ل-l < [1(2k-1 + v 1 - (#k-1 + n 2r -1]l
= = 11 92-1 ||-
Now, we focus on dealing with 119x-1 - -6-1l1 1ll In fact:
11gh- N4- 11 ( [ - ((x)) + -k-1 Ex 1111
(d)
3 33
V 22 + ||Ek-11 116x-1113)
(15)
(e) 3L || - 2x 2 + 3 0||==111 1|
Here, (c) holds by the definition of Ek-1, E (d) holds because by Cauchy Inequality, ||x + y + 2|| < 3[1x=] 12 + ||yll2 + ||| always holds. (e) holds because we've assumed that V(z) is
T-Lipschitz continuous under I 2l2 norm. Combine Equation (14) and (15), obtain that:
|| - == < = (1 L
-xel" 1PF-11a 1| =ul1 2 6r7² (lee-- 1|2 + || ll2)
+ 2mm Ê 2s 2"),
which is exactly what we want to prove in this lemma.
Now, we come back our Theorem D.I Notice that
Ty (2x)² = || - 11 [*x
+ 17 V (zx)]]l = 1| Ex+1 + 8x41 - 112 +1 (=))]l?
2 (1|= 2 2| + [1 Hz nn ((2))1113)
(16)
2 ||*
أ || + | z [Ex + 17 gul nz[ + +n V(=))ll²)
(6)
< - - 2x+1| 1| 2n² ||
Here, (a) comes from Cauchy Inequality and (b) holds because of the property (2) of Lemma D.1
24

---

Under review as a conference paper at ICLR 2022
Proof of Theorem D.7 Put l = 1,2,................... ........,....................... .N in Lemma
D.2 and add them up, and obtain that:
N
| - 12 & |1:0 - ==1 - (1 - 12)
1| - 2x+1l1
2 - 2x 1|
k=
N-1
6n)
(1|=x|1 + 2|Ex|12+11EAN 11xxxl1)) + >
(2x 2=",,,''''', ,77 Ex-1).
0=
k=1
Therefore, after combining with Equation (T6). we have:
N-1
Σ
(=x)
2
<
2
Σ
1|
Ek+1l1 + +27²²
||x
k=0
k=
N-1
NV
2
|1=0-2011 + 61/²
Σ
(Ilex 1|2 + +1xx11?) +
Σ
(Ex - ,,, Ek-1) 1)
1 - 2,7
k=0
k=1
N-1
+ 207²
||Ex11
k=
Since <
37, we have 617²
1
>> 1.2 After taking expectation on the inequality above, it holds
that:
N
4 20
11
4872
2
N-1
2m
N-1 1
(xx)))
+
N
N
N
m&
N
k=0
4| 20
50n
N-1
o²
N
N
m&
k==
which comes to our conclusion. Here, use the fact that E||Ex|| (ax- 17 êk-1) 1)
<
E1
o²
and
ma
me
D.2 PROOF OF THEOREM D.2
We recall that in the 1-th iteration of Adaptive Extra-Gradient, our update is as follows:
1 2 7) H 11
2 = 2 + 1) 5-199
Now we begin our proof by introducing several lemmas. Lemma D.3.
|| - 2"" 112 < || - 22. - 1
2 112,,
+ 11
Exll3,
+ +(n Eks 2x 10-- 2²).
Here, EN -Ôv- V(22)= = 2/ Em (i): - (2
Proof of Lemma D.3 According to our update rule, we know that:
1|zk z" 2 11:
|| + 1) S 19: z=" 11 1
|| + 17- 5 96 - z" 112__, - -| +
---11-10 - 2k 123._.
|| z² 11 ='1[3__1
|| 2ul13r11 + 2(11 Ir: =k- =x")
= || - 2" 2
|| 1 + 24 2x 1//3,_ + 2(11 gk: 2k - -2x) + 2(11 gk: 2x z²)
= || - 2² 201 31
| Exl13 - 11 - 2x 2211 1 215x=1(2E-0 - -2x), 2x 2x)
+ +2(n Jk, 2k= 2))
+ 2/m gr: 2x z²)
|| z 11:2__
|| 2u 11?___,
11 - zn 112 +2(m gr. Ex - =²")
+ +((Zk - 22 Sx
(=t-1 - 2/ + Sx110k)
|| z" 11 113
|| 2 1
11 2x 11 113 + 2(1 gr. Eh 2*)
+ -2/2k 24. Sg (2k- -
= ||=0-1 - = = - || Ex 11
+ 11 - 2* 13,,3__, + 2(n Dr. Ex - 2*)
25

---

Under review as a conference paper at ICLR 2022
Notice that 9k ((2)) + ER- Since 2" is solution of MVI which means (V(2), 2²) & 0 holds
for V22 E 2, so (V (2x), 8k - 2*) < 0. Therefore:
(n 9k. 2 > = (1 (V())) + +x), 2n z²) & (1) Eks 2x - 2²).
Combine it with the inequality above, we obtain that:
I| 11.__ < ||=--1 "Is.... || 1 &x 11..s + 11 - 2x113,_, 2(nm Eks 2x =²),,
which comes to our conclusion.
In the lemma above, it's worth mentioned that the expectation of (1) ck. 82 - =²) is O. In the next lemma, we are going deal with the upper bound of | 2x s.... Before that, notice the following fact:
Hg 3o H1
m S
3 I HN I SN.
Lemma D.4.
1,2
||= - Exll3
|| || - 1 + 6n2
+ 11xx- (1ssT))
+ 2n²² ||(5 H 9g 11a--1
Proof of Lemma D.4 Since ãn žい + 1)- k- 19k and -k-1 1 + 11 Sp- gx. we have:
|| - 1x Su
= 172 || 0h - H 1 1--1- 100-111:1 113, = 1)² 1 - 9 - S 9k 1
1 194
1 113
(a)
$ 21/² (15T_1 (òx- - Ok- 1)13 + |1(5 H g9k 12 1l3__.)
= 2r7 (lli: - gh -2-1l 5 + |[(TT] 11 1gh-1 11
= 2//² [V(x)) - V(Ek-1) + 6--1 Ex- |ل + 217² ||(ST_]
1T11)99- 1133
(6)
< 6n² (1I(()) V(zx || s
+ +1Ex
||3 55
+ |||xx 11 11
+ 2n7
||(5]1 1 )g
11:2-11
(0)
L2
< 67/²
|| - - 113,_, +
11 s-
+ ||Ek- 11
+ 2n/²
||(S_] -
)g 113,--1
which comes to our conclusion. Here, (a) holds since for any norm | IlA, we have ||x + yll < (|æ=]|a> Ilylla)² < 2[[1=|1| 11 and (b) holds for the similar reason. (c) holds because of the
following two reasons: (I) Since V is L-Lipschitz continuous, and 81 < Sp-1, 1. we have:
L2 ([V())) v((+1))) & (IV(EE) ((a-1) 11 2x1112
L2
82 11 2k zk 112.1
(2) Since Ha-1 I Sk-1, we have spl1 Hn Therefore, || < [||Ex-1
Since 17 & 1. then
< 4. According to Lemma D.3 and Lemma D.4 we have:
|| 20 < || - z" 2011 -1 ||zz-1
21 + 2(m š 2x >²)++ + | 2x 31
+ 6rj² (182-111 + -|12-1113
+ 2n²² ||(ST_1 -H 11
26

---

Under review as a conference paper at ICLR 2022
which means:
2 Fk-1 2xll3s
< || -2"1ls - 1| - -2"133e. + +2( Êk-1, 2x - -²))
+ 6n²² (1EA-2 1 H,, + [| s + 2nj² |1(5 H 129-199--1
15..
(17)
Notice that, 1| - 2/ = 1,77 H - 113s 11a--. Therefore,
1
11 1| = -- 113
191-
|11 1 + (5 1
H -- 9
19t-1116600 1113
+ |1(5 1k-1)ga-- 11.3...)
(18)
2
||
Ex 11 +2 ||(ST1] H gk 11
172
Combine Equation
17
and
18
we obtain that:
1
<
(1 - 20113 - 11 - 2" 22, 2-1 + (f 23 - -2")
172
(19)
24 (1Ex-111 + -11Ek-11
10 |1(5T_1
H 1-
55
In the inequality above, the expectation of (Éx-1 2q. -- 2²) is
0, O. which can be ignored under expectation.
Since we are going do the summation over 1, ...,.... N in the future, the following lemmas, we analyze the upper bounds of Σ (1|=x-1
2"113,_1 || = ="13__,) I (1
- and E 122 |,,,, +
-|(kk 11 113_1
Lemma D.5.
||zz-1 *'113__, - 1| =="113 ==113__1) < 2dd28 No.
Proof of Lemma D.5
Notice that
N
N-1
Σ
||--1
1 - -2x ==113._.) < 11200 =='113 + Σ
|| ==113. - -11z 2 ==113__.)
k=1
N-1
= ||20 - =1"1,,, +
Σ
[( - =²")
=²)TT((' (Sxx - Sk (zu- - =²)]
1856-5x11
k=1
N-1
Σ
D² (tr(Sk) - tr(Sx-1)) D² tr((N-1) < 2d
which comes to conclusion.
Lemma D.6.
N
2dG Na
Σ
|[S_]]
8
Proof of Lemma D.6
For any 5 y, we notice that:
1 2
(y
x)
T
(20)
x²y y
82
27

---

Under review as a conference paper at ICLR 2022
Therefore, have:
(1 k- - H -
Σ 9 -
19
Ir (HH - 1
[tr(S)
-tr(Hx-1))
82
G
2dG No
tr
2dd
No
82
82
Here, (a) holds because Equation 20
Lemma D.7.
E
[|ER-1l| 112. +
1|Ex-111
4d8 N
The proof of this lemma can be found in (Duchi al. Equation
2011) Combine Lemma D.5
D.6
D.7
with
19
we obtain that:
N
4 1p
[80²
2dG² No
E
1
1
2dD +44 + 4dō Noo
10
k=1
Now, we replace the ge-1 with the true gradient ((*--1) follows:
N
N
N
N
E
(
H =
1g + Ek-1 HJl
2. E
11 112--112--- 11
+
|| 1 H
k=1
1=1
k=1
k=1
(a)
0002
<
2
E
|1 11 12:11 -h- ( - - -9--1 +
+ 4d0 No0
111
k=1
(ō0²
2-
11
11 112-1 +2.
+408 No8 No)
Na
2G2 Σ
[tr(H
tr((
m
2
2dG Na
2dD25Na +50
+ 4d8 Na
+ 20
+ 2G2 tr H)
m
1602
2dG Na
2Gdd
2dD25N" + 50
+ 4d8
No
+ 20
+ 8
1/2
8
Here.
(a)
uses the conclusion of Lemma D.7 Finally, we multiplies A on both sides and finish the
proof:
16dD25/1 + 20045 + 40dG2/8 50602/n m//m/mmmmmm + 2G2
E N
IV(=))
N1-a
N
k=0
D.3 PROOF OF THEBREE D.3
In this proof, are still using the Adaptive Extra-Gradies Gradient (AEG) algorithm, which its f-th iteration
is:
2 24-1 17 H H:
21 2 17 S-1
For simplicity, we split the update of x variable and y variable. Recall that H₃ Diag (Ag, Bx) and
Se Diag(Ck, D2) where for each A: E N, As, Ck E R and Bg, D₃. E R Also,
28

---

Under review as a conference paper at ICLR 2022
denote 9l (g] 9 and 9k above can be rewritten as:
(0% ( where gE. 9 E R and 9k 9 E " Then, the update
f. - I--1 + A-
9: = yt- + - 13--19-11
I; I 1 77 C--1
y/ 1 + D.-1.8
Similar to Lemma D.3 we only focus the x-s,, and then we can get our upper bound for aa x² lo._,, which is the first step of our proof.
Lemma D.8.
||0x - x 1 & 12 -x I' - -1 it 22... + 1 - Sx f2.l.... + 2(m . Ek dx - x²)
Proof of Lemma D.8
According to the update rule of Iy,, Øx,, we know that:
|| x² "16....
||Tk-1 + 77 - 1h
x 11:
|a + 17 C 19
x² 11e... - 11181-1+1 Ch-10 x 12
| 1 - x" 112,_
- | Iz 1x1/2a1 + +2(11 Th. Tk - x²)
| x² $1
| 4x + .x x 12 + 2(111 9h. 3k (xx) + 2(1 Fh. tt x²)
||aa-1 x= 21122_11
| - 1x
11 - rx 1x112,.
-2(xx- 1 - .xk), 5x rkk
+ 2(n Fo. 0b - 1x)) + 2(n 8h, 5 - x²)
= || - x" "1,
| +t 11: - 1 - 1x112
+ +21 Nh. 0t - x²)
+2( Sx, Ch- 1 (Ix-1 1 5x " Cx
= ||aK-1 - x ='12,_ - | - 2x S1.1e.. - -110g - 1x1.2.. + +2(n gh. Rtg - x
+ 2(xx - ixz 1x-1 &x))
1| - x² 2'112_,, -1 2x 11: + 11 10--==1122-0- 1x122n1
+ 2(m gh. 2t. - x²)
Notice that 9N = V(2) + E ol Vz(2t) + E Since 2n satisfies the one-side MVI
condition, therefore (Va x - x²) < 0 holds for Vz = (x.1) E 2, so (Va(Eu), dx - x²) & 0. Therefore:
9 24 -=)= = (n- (Va(2)) + f) x²) < {n Ex 1 1: 22 x²).
Combine it with the incquality above, we obtain that:
|| x* 112, | x² 12.. -| tx 12 + 1 2k xxx12 1l., +2(n 1 x*),
which comes to conclusion.
Notice that the term 2 Lt - x²) has zero mean, which can be ignored when taking expectation.
In the next step, we upper bound the || - Ix 1 term. Also, we notice the following facts:
Ao Co Ai 3 C. ....5 AN 3 CN,
Bo 1 Do 1 B, - D1 .... - BN - DN.
Lemma D.9.
L2
|| @xlle,_,
||a*-1 - 2z 12, + 11y8-11 - dx Dil1B..)) + 6r7² (1EA-1112,,, + 1é6-1113
82
+ 2m² ||[Cr]]
A 1 119g-1112... 11
Proof of Lemma D.9 Since âΙ = Æパ-1 +
A
1 and I& = xz-1 + CT we have:
||o 3x 1lc_. = =1² - 1 A A
1
2 || - CT-10 1
29

---

Under review as a conference paper at ICLR 2022
(a)
< 2n² (I0= (9k g sk-1)ll. -1 A 44-1) Do 11o...)
= 21/
(lIE g 1 11 ooo1 +
(
< 2n (l6x - 9k 113 + |1(00-1 - A - 996 11
21/ (V((E)) - V(=x-1 1) + êk- Ek 5/2 1 + +21/ 11(0 A
9 6n/ (IV(a)) V (=k-1))| 131
+ +1(6--1
11 55 + ||EE 111 111321)
227 ||(0 - A 1
6n/
(5z 11 m사 1132_1 - 1166-111 بلا + +1|EK-1 11
+ 2n/² |1(CT-1 - A 1 1 11.
( 61²² (o2 || xk-1 1 12 1 +
1,2
1,2
llue 1k-1
+ -11xx-113==- 5, + +1|Ek
1
82
M
+ 2ny² ||(CT'1 - A 11c
(21)
which comes to our conclusion. Here, (a) holds since for any norm || IIA, we have || + vll3 <
[||=||- + | < 19 -h-1 ST1, 1 - _ 11% 9h - > 1 - and (e) holds for
2[[ + [1)aaa, and (c) holds for the similar reason. (b) holds because
the same reason. (d) holds because of the following two reasons: (1) Since V is L-Lisschitz continuous, and 81 = S we have:
L2 p
((+( - V( < (V( - V(= 11 1 16 -1xx-au0 21-11
21-1133-1.
(2) Since Ha-1 3 Sk-1, we have S = H Therefore,
|| < || 1 11 |
Since we require our learning rate 17 <
4E. the coefficient above
5
2 82 < }/2 After combining
Lemma D.8 and Lemma D.9 we obtain that:
| x² I1e,_ < || - x 1 2 -4-1 - 5x fx1l... + 1
21118-1 - -ix1 + +2(n
1; _t - xx)
+ +n7² (1ex-
+ -1 11
+ +21) .1(Ck( - -A 1
(22)
which means:
2 |kkk-1 - 8x 12.,, < ||06-1 - x² 2011,,1, - 1 - x 11,
+ 2 Ellse- - -i - + +(1
1 tt - x²)
+ +n72 (1EA-1ll2 + 11 11221 + 227 ||( - A 1a6 1 11a.-,
(23)
Notice that, || 12,18, = |l1
A
Therefore,
11g 11
10
1
x
||A + (O A 1
21 11,, + ||(T/-1- - 1 1 ) [|A
(24)
2
|| - tx 12.. +2 [[CT_] - A A )0k 112
2
30

---

Under review as a conference paper at ICLR 2022
Combining Equation
23 and Equation 24 we get:
1 1
(128-1 x= ll...
||-0 x² 11
) ll 11.1.3. mp (n
2
1, =x")
1
1p
+ 24
||=x-111 11 + 115E 11 1| + 10
11--1(((== - 10
(25)
Then, take summation over k 1,2,.... N and take expectation, and obtain that:
N
N
g
11 Cp-
$ 172
x= - -11ax - 22112x .) +
1k-1
Uk Vkll
112
1=
+ 24 E
(1Ex-1l12 Hz.! + 11 + 10 E
[[
A 19%-11122
1=1
k=1
(26)
In the following steps, we will upper bound the four terms above on the right side. The third term
E
(1e--112 E
1ل, + 1léx- |=2 can be upper bounded by using Lemma D.7
N
80² + 4d8 No. <
E
||E2-1| 11 H 1 + 1|6x-111 s
(27)
k=1 1
The fourth term E k=
|1( 1-1 - 15-1)9%-1118 can be upper bounded by using Lemma D.6:
2dG². No
E
|(CTT1
- - A 112,
|1(s=1 H 11
For the first term E kk=1
(107--1
x² 20
1|00 x 2011 =18...) can use the similar techniques
as Lemma D.5
Lemma D.10.
N
| - 12 - |100 - 1=1 .) < 2dD No.
Proof of Lemma D.10
Notice that
N-1
1x6-1 - x²1 1 - 11=====""00 - xxx11
-221)2m- < 11100 ==112 +
| 11. - -11-0 x x='1,__,)
k=1
k=
N-1
11:0
2111,,
[ - 100==()TT00 TC²T((= -C-1)) (xr -x)]
N-1
< D2. 1 tr((C)) +
Σ
D2 (tr(Ck) tr(Ck-1)) = D2 -t((CC-C) < tr(SSx)-1) < D2. 2d8N%,
which comes to our conclusion.
For the second term E
11yk-1 - 0m.1., notice that:
N =
1/2
2
18k 80
18
11,,, =
- Dz-1
9 9
T
D
B
h²
k2
k=1
k=1
n²
2d
Crtr(B
De B
G
12
12
82
dG2 N
k2-o
km
31

---

Under review as a conference paper at ICLR 2022
Here, notice that:
N
N
1
de < 1 L/¹
/ 1
)
<
dr = 1 +
< 3.
22
x2-a
23/2
VN
A=1
Therefore:
GrjdG²
11kk-1 Dill
According to Equation 26
2
Gn
0
2dG No
gh 11 C 1p2
2dDDD8---0 No
24
+ 4d6 Noo)
+ 10
op
m
8
=Na (
(Bi1)" 112
20dG
12dG2
245a²
+ 96d8 +
+
8
8
m
(28)
Finally, we replace the gk- above with the actual gradient (a(=k-1) Since:
(Vo(==-1)1 < (110--1lle,s + || MEk-illc.!! )²
< (108% (16R-111e22 + 11 142-)1)221)
we can upper bound the target term E
3 k= (2x 11
N
N
12
E
2
(19
1
11
+
& 2E
11 c
+ 21
1 11
1=1
1=1
k=1
A=1
(a)
16d 1/2
40dG2
24dG2
4850²
No
192d8
+ 2F Σ
||0x-1 113 1124
-11xx-1
(0)
2 1/2
40dG²
24dG2
4860
2
[80²
< Na.
192d8
+
+
+ 4d5 Na
8
8
m
m
(16dD28
+ 200d5 + 40dG
24dG
5086
No.
172
(29)
which means that:
16dD28/1p + 200d8 + 40dG
24dGP /8 + 50602 /m
Σ
N1-a
N
which comes to our conclusion.
32

---

Under review as a conference paper at ICLR 2022
E PSEUDO-ALGORITHM OF AMSGRAD-EG-DRD
Algorithm 5 Extra Gradient AMSGrad with Dual Rate Decay
The initial state 2g = my = d = 0, constant learning rate 77 a Stochastic First-order Oracle (SFO) ((2; E), momentum parameters S1c, 82, sequence of batch sizes {Mx}. Output: 24 with uniformly chosen from (0, 1,....,........... - 1}.
Input:
for k = I......,N N do
2: (Gradient Evaluation 1) 9k-1 = -/ Er (( E
3: (Momentum Update 1)m = - + (1 81k g -
4: (Velocity Update 1) U/. max(320k
(1 32) 0k- 1), Hx = 81 Diag( vz)).
5:
(Shadow Update) i = -h + 11 (Hz) m
OA 1 " (H*) -1 m 2/- (3k. (k).
VI
6: (Gradient Evaluation 2) 0 M. E (( [k)
7:
(Momentum Update 2) m = BImm+ + (1 bIk)
8:
(Velocity Update 2) б% max(32ux + (1 32) vk), H2 = 81 + Diag( (v
9:
(Real Update) 2k 1 1 7) H, mm
10: (Real Update) z4 = -k 17. [ m
5/4 = 1k-1 + JE (
m 2k = (Iks ykk)
end for
33


Reviews:
[{"review_id": "z8sI2BiuX5M", "reviewer": "Reviewer_nfde", "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": "This paper looks particularly interesting to me because of its clarity in presentations and its novelty in the theoretical results. As I am not an expert in min-max optimization or GANs, I cannot be very confident that the results are completely new. However, analyzing Adam-type algorithms in the training of GANs is, as far as I am aware, an important yet not sufficiently explored direction. The authors have chosen a general nonconvex, nonconcave problem to analyze, and have shown the results under the standard MVI assumption and the one-sided MVI assumption. The one-sided convergence behavior is also supported by the experiments. Therefore, I like the results of this paper.\n\nIn terms of weaknesses, I would like to discuss the following questions with the authors.\n\n1. In terms of the assumptions in Table 1, since the authors not only need MVI but also some other assumptions (e.g. Lipchitzness and boundedness in Assumption 1), why do the authors only list MVI in the table? I spent some time reading the other papers mentioned in this table, and it seems to me that different papers have very different assumptions, and Assumption 1 does not seem to be used in all of them. Therefore, I don't think Table 1 is clear enough. I wish the authors could explain Table 1 a little more thoroughly.\n\n2. In terms of the optimization algorithm, I wonder whether the other adaptive algorithms could also obtain similar results. Of course, AMSGrad is a perfectly fine choice. However, I don't see the technical difficulty if the authors just use a general non-decreasing $H_t$. Since the authors are claiming the convergence results for Adam-type algorithms, a general choice of $H_t$ would make their argument stronger. Besides, is it possible to use Popov's Extra gradient to reduce the number of queries to the SFO?\n\n3. The experiments part (section 4) looks less convincing to me, or even unnecessary because the main point of this paper is on the theoretical side and to show that one-sided convergence exists. I don't see why it is needed to compare the performance of the proposed algorithm with SGDA. Also, there are no FID scores / Inception scores and it's really hard to tell which images are better.\n\nAgain, I am not an expert in this area and I might be missing something. I look forward to the authors' discussions.\n", "summary_of_the_paper": "This paper analyzes the performance of Adam-type algorithms (AMSGrad, to be specific) in nonconvex nonconcave minimax optimization. The authors propose that Adam-type algorithms can converge to a stationary point with the standard MVI assumption and an even weaker one-sided MVI assumption. The authors verify their claims using Experiments.", "summary_of_the_review": "This paper provides a solid contribution to the area of min-max optimization, with their theory supported by experiments in training GANs.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "4: The contributions are significant, and do not exist in prior works."}, "extra_text": {}}, {"review_id": "sQ7jjmSDNQ4", "reviewer": "Reviewer_M4vM", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The proposed one-sided MVI condition is interesting, and the analysis under this condition provides new insights into the convergence of adaptive optimization algorithms on min-max problems such as GANs. The theoretical analysis is clear and easy to follow.\n\nThe authors argue that \"it is very unlikely that there is a optimal discriminator\" based on the observation that the gradient norm of discriminators remains large throughout the training process of GANs. However, it is possible there exists an optimal solution for discriminators, which the optimizer fails to converge to, and there is no convincing evidence in the paper to prove otherwise. For instance, the MVI condition seems to hold reasonably well in some scenarios, such as the DCGAN experiments presented in Appendix C. Furthermore, the Adam variants are proposed to simplify the analysis of Adam, therefore it is necessary to show if the variants perform similarly as Adam in practice, which is not done in the empirical study. In addition, the generative performances of different optimizers are only compared qualitatively without using metrics like FID.\n\nThere are also noticeable typos or errors throughout the paper. E.g., in Sec. 2.1, \"Stochastic Gradient Descent (SGD) was originally proposed by (Goodfellow et al., 2016)\". And in Sec. 5, \"provide the theoretical guarantee of the one-sided convergence of Adam under one-sided MVI condition\", where it should be Adam-like algorithms instead?", "summary_of_the_paper": "This paper analyzes two variants of the Adam optimizer, and proves their convergence under either the standard MVI condition or the newly proposed one-sided MVI condition. The aforementioned Adam variants are then empirically evaluated by training GANs on MNIST, Fashion-MNIST, and CIFAR-10, demonstrating better sample quality than SGD.", "summary_of_the_review": "This paper presented some interesting theoretical analysis of Adaptive optimization algorithms, but part of its theory and experiments are not convincing enough, and the overall writing needs to be improved.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "U7v5H1OPOVC", "reviewer": "Reviewer_wnya", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strengths: the paper is well-written. The one-sided MVI assumption is an interesting observation. \n\nWeaknesses:\n1. The main technical proofs follow closely to [Liu et al. 2020], expect for changing the gradient to moving-averaged gradient. AMSGrad-EG uses the same MVI assumption as in [Liu et al. 2020]. AMSGrad-EG-DRD only requires one-sided MVI assumption, but the convergence measure is also weaker (only partial gradient in terms of $x$). Please explain what is the technical contribution of your Theorem 3.1 and Theorem 3.2 when compared with [Liu et al. 2020]. \n\n2. One-sided MVI is not weaker than MVI assumption, since they cannot imply each other. However, Theorem 3.2 is a weaker convergence result since the LHS is only a partial gradient in terms of $x$.\n\n3. For both Theorem 3.1 and Theorem 3.2, the convergence crucially relies on large minibatch. This is not practical. \n\n4. Assumption 1 (4) requires bounded iterate. However it seems that the authors did not consider a projection in their algorithm.\n\n5. I have a very big concern about experiments. (i). The evaluation is not comprehensive and not convincing. For example, the authors only show the results on MNIST dataset which is too small for GAN. Also they only provided subjective generated picture without providing quantitative results (e.g., Inception Score and Frechet Inception Distance). (ii). The experiments presented in Figure 3 are very poor. For example, Columns (d) (e) (f) are all pictures of visually bad quality, I personally do not think column (e) is better than (d) and (f) at all.\n\n\n\n\n", "summary_of_the_paper": "This manuscript developed several algorithms (e.g., AMSGrad-EG, AMSGrad-EG-DRD) for nonconvex-nonconcave min-max optimization. The convergence result of AMSGrad-EG-DRD is shown under the one-sided MVI condition. Polynomial-time complexity results are established. Some toy experiments are conducted for GAN on MNIST and fashion-MNIST datasets.", "summary_of_the_review": "This manuscript proposed an interesting one-sided MVI assumption for nonconvex-nonconcave minimax problems, and developed some algorithms with polynomial-time complexity to first-order stationary points. The theory requires certain unrealistic assumptions (e.g., large minibatch, bounded iterate), and overall is not surprising. Empirical results are poorly evaluated and are not convincing. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "IeoBXVF102s", "reviewer": "Reviewer_jDRv", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Pros:\n- The paper is well written and easy to follow.\n- The convergence analysis of the proposed algorithms are solid.\n\nCons:\nMy main concerns of the paper focus on the motivation and the experiments.\n- When training the GAN models, we usually require that the loss function given by the discriminator approaches to zero, in terms of either KL divergence or Wasserstein distance. Although Fig. 1 gives the gradient information of both the generator and discriminator, it is hard to say if the model really converges well. As a nonconvex problem, it is possible that the gradient of the generator approaches to zero, while the model actually doesn't converge. In such situation, the generated data may be meaningless. Moreover, with the low quality of the generated images, it is highly possible that the GAN model does not converge. Thus, I am not sure if GAN model is a proper application of the proposed algorithms.\n- In the experiments, the authors use the Wasserstein GAN [Arjovsky et al., 2017] to conduct the experiments. The vanilla WGAN [Arjovsky et al., 2017] model may fail to converge due to the lack of the 1-Lipschitz constraint of the discriminator. The generator only works well with a promising and working discriminator. This means that the used WGAN model may not satisfy Assumption 1 or Assumption 3. In such situation, it is hard to differentiate if the proposed mechanism or the nonworking discriminator causes the zero gradient problem of the generator.\n- To make the experiments more convincing, I suggest the authors to experiment on 2-dimensional toy dataset first, which will be much simpler and be easier to find if the model does converge.", "summary_of_the_paper": "The paper observes the one-sided convergence phenomenon of GAN's training, and proposes the one-sided MVI condition suitable for this problem. Then the convergence analysis is provided for the proposed AMSGRAD-EG and AMSGrad-EG-DRD algorithms.", "summary_of_the_review": "It seems that the theoretical part of the paper does not support the motivation well. If this problem can be solved, I'll raise my rating.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper studies the convergence of Adam-type algorithms (two variants of AMSGrad in particular) in min-max problems that satisfy a one-sided "Minty variational inequality" condition.

The reviewers identified several weaknesses in the paper and the authors did not provide a rebuttal to these concerns so there was consensus to reject the paper.
Decision: Reject