Year: 2021

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.

heading: 1 INTRODUCTION
text: 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 on 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, 2015), RMSprop, AMSGrad (Reddi et al., 2018) and AdaDelta (Zeiler, 2012). In supervised learning, adaptive gradient methods and Adamtype 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 a limiting cycle, both of which will lead to an ill-performing solution, while Adam optimizer, as the default optimizer for GANs (Hsieh et al., 2020), can obtain better performance. The reason why these two optimizers have so much difference in GAN’s training has long been an open problem. Traditionally, the training performance of min-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 Fashion-MNIST, we can find that, in a practical training process of GAN, Adam optimizer does not perfectly converge since the
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
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-convex 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 on convex concave or non-convex concave min-max optimization, in the non-convex non-concave setting which is most general, there is no 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; Zou et al., 2021) 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, to formally analyze the convergence of Adam-type algorithms in min-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 as GAN’s training. We prove that, under the assumption of standard MVI condition, the Extra Gradient AMSGrad algorithm provably converges to a ε-stationary point with O(dε−2) complexity in deterministic setting and O(dε−4) 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 as well as in GAN’s training.

heading: 2 BACKGROUND AND RELATED WORKS
text: 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.

heading: 2.1 ADAPTIVE GRADIENT METHODS AND ADAM-TYPE METHODS
text: We consider the simplest 1-dimensional unconstrained minimization problem:
min x∈D⊆R f(x).
where f : D → R is a continuously differentiable function. As one of the most dominant algorithms on the optimization problem above, Stochastic Gradient Descent (SGD) was originally proposed by (Goodfellow et 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., 2018) and AdaDelta (Zeiler, 2012). Distinguished from the vanilla gradient descent or its stochastic version SGD, adaptive gradient methods use a 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:
mt+1 = ht∇f(xt) + rt ·mt, vt+1 = pt(∇f(xt))2 + qt · vt xt+1 = xt − λt ·
mt+1√ vt+1 + ε . [Adaptive]
Here, f is the objective function to minimize. h, r, p, q are scalars depending on t, λt is the learning rate of the t-th iteration and ε > 0 is a small constant used to protect the denominator from being close to 0. From the formula above, we see that the momentummt is the weighted sum of the past gradients and vt is the weighted sum of the past squared gradients. When h = 1, r = 0, mt+1 = ∇f(xt) is just the current gradient. We start with the original Adam.
vt+1 = αtvt + (1− αt)(∇f(xt))2, mt+1 = βtmt + (1− βt)∇f(xt) xt+1 = xt − λ · mt+1√ vt+1 + ε . [Adam]
As we can see, Adam is a combination of adaptive gradient method and momentum method. Here, the momentum term is 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 ht + rt = pt + qt = 1. When the αt = α, βt = β remains constant, there is a bias correction step where vt+1 ← vt+11−αt and mt+1 ← mt+1 1−βt . However, we may practically ignore this bias correction step since 11−αt and 1
1−βt rapidly approach to 1. As one of the variants of Adam, AMSGrad has the following formulation:
v̂t+1 = αtvt + (1− αt)(∇f(xt))2, vt+1 = max(vt, v̂t+1)
mt+1 = βtvt + (1− βt)∇f(xt), xt+1 = xt − λ · mt+1√ vt+1 + ε . [AMSGrad]
As we can see, their difference is that the velocity term vt 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. Basu et al. (2018) proved the convergence rate of RMSprop and Adam when using deterministic gradients instead of stochastic gradients. Li & Orabona (2018) analyzed the
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, a number of new algorithms are proposed, such as SC-AdaGrad / SC-RMSprop (Mukkamala & Hein, 2017), AdamW (Loshchilov & Hutter, 2019), AdaBound (Luo et al., 2019) etc..

heading: 2.2 MIN-MAX OPTIMIZATION
text: In the min-max optimization problem (or saddle point problem), we have to solve:
min x∈X max y∈Y φ(x, y), [SP]
where X ⊆ Rn1 ,Y ⊆ Rn2 , and φ : X × Y → R is the objective function. When φ is convex on x 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 z = (x, y) and Z = X × Y ⊆ Rn1+n2 . We also introduce our gradient vector field: V (z) = (−∇xφ(x, y),∇yφ(x, y)), which are the update directions on both sides. The goal of [SP] is to find a tuple z∗ = (x∗, y∗) such that φ(x∗, y) 6 φ(x∗, y∗) 6 φ(x, y∗) holds for ∀x ∈ X , y ∈ Y , which is called the solution of [SP]. If the inequality above only holds in the local neighbourhood of z∗, then z∗ can only be called a local solution. Notice that the necessary condition of being a solution (or even a local solution) is to be a stationary point of φ, which means V (z∗) = 0. Furthermore, if V is C1, any local solution of [SP] must be stable, which means ∇2xxφ(x∗, y∗) 0 and ∇2yyφ(x∗, y∗) 0. Next, we will introduce several commonly-used algorithms which are designed to solve [SP].
Stochastic Gradient Descent Ascent (SGDA) This is a simple extension of Stochastic Gradient Descent (SGD) algorithm for minimization problems (Johnsen, 1959). In the t-th iteration:
zt+1 = zt + γt · V (zt;ωt), [SGDA]
where ω1, ω2, · · · are the independent and identically distributed sequence of noises. V (z, ω) can be treated as a query to the stochastic first-order oracle (SFO). In each iteration of SGDA, we need to query SFO once. Notice that, we simultaneously 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 (AltSGDA) algorithm. Different from original SGDA, we have to make two queries to SFO in each iteration. One for zt = (xt, yt), and the other for the intermediate step (xt+1, yt). Since original SGDA is not going to work even in the convex-concave setting (such as minx maxy f(x, y) = xy), 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 Korpelevich (1976). Given zt as a base, we take a virtual gradient descent ascent step and obtain a z̃t, which can be treated as the shadow of zt. Then we use the gradient at z′t as the update direction of zt. This process can be described as:
z′t = zt + γt · V (zt;ω (1) t )
zt+1 = zt + γt · V (z′t;ω (2) t ).
[SEG]
In each iteration, we need to make two queries to the SFO. One for the base zt and the other for the shadow z′t. However, in the first step of [SEG], we can use the gradient at the previous shadow z ′ t−1 so that we only have to make only one query in each iteration and remember the query’s result of the previous step. This algorithm is called Optimistic Gradient or Popov’s Extra-gradient (Popov, 1980) which can be described as:
z′t = zt + γt · V (z′t−1;ωt−1) zt+1 = zt + γt · V (z′t;ωt).
[OG]
As a widely used algorithm, it has been applied in multiple works (Daskalakis et al., 2018; Mertikopoulos et al., 2019). Under some mild assumptions, convergence rates are proved by many theoretical works and we will summarize them in the next section.

heading: 2.3 CONVERGENCE RATES OF MULTIPLE MIN-MAX ALGORITHMS
text: 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 O(1/T ) convergence guarantee of Mirror-Prox in terms of duality gap. Juditsky et al. (2011) 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-prox algorithms are shown to be optimal. When it comes to the more challenging non-convex non-concave min-max optimization, Dang & Lan (2015) showed that the deterministic extragradient method can converge to ε-first order stationary point with non-asymptotic guarantee. Another interesting algorithm Inexact Proximal Point (IPP) method (Lin et al., 2018), which is a stage-wise algorithm, performs well when the objective function is weakly-convex weakly-concave. In each stage, we construct a strongly-convex stronglyconcave sub-problem by adding quadratic regularizers. Then, by using stochastic algorithms, we can approximately solve the original problem. It’s known that IPP also has a first order convergence guarantee. Also, Sanjabi et al. (2018) proposed an 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 1. Finally, MVI condition needs to be explained. Let K : Rd → Rd be
an operator and X ⊆ Rd is a closed convex domain. Hartman & Stampacchia (1966) proposed the Stampacchia Variational Inequality (SVI), which aims to find z∗ ∈ X , such that 〈K(z∗), z− z∗〉 > 0 holds for all z ∈ X . Similarly, Minty (1962) proposed the Minty Variational Inequality (MVI) problem, which aims to find z∗ ∈ X , such that 〈K(z), z − z∗〉 > 0. In Table 1, the operator K(z) = (∇xφ(x, y),−∇yφ(x, y))> = −V (z) with z = (x, y).

heading: 3 MAIN RESULTS
text: 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 (AMSGradEG-DRD) which inherit the idea of OAdaGrad into Adam-type algorithms. With AMSGrad-EG, we can prove its first-order convergence under MVI condition. However, as we stated above, Adam 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
more likely to hold. Under this condition, we prove that Extra Gradient AMSGrad with Dual Rate Decay (AMSGrad-EG-DRD) converges one-sidedly, which matches our experiment results.

heading: 3.1 PROBLEM SETTING AND ASSUMPTIONS
text: Throughout the paper, we analyze the min-max optimization problems:
min x∈X max y∈Y φ(x, y), [SP]
where X ⊆ Rn1 ,Y ⊆ Rn2 , and φ : X × Y → R is the objective function. We denote z = (x, y) and Z = X × Y . First, we state some useful assumptions on φ(x, y): Assumption 1. (1) V := (−∇xφ,∇yφ) is L-Lipschitz continuous under ‖ · ‖2 norm. (2) The stochastic first order gradient oracle (SFO) is unbiased and has bounded variance:
E[V (z; ξ)] = V (z) and E‖V (z; ξ)− V (z)‖2 6 σ2.
(3) The Stochastic first-order Gradient Oracle (SFO) has bounded output: there exists G > 0 and δ > 0 such that ‖V (z; ξ)‖2 6 G and ‖V (z; ξ)‖∞ 6 δ almost surely holds. (4) There exists a universal constant D > 0, such that ‖zk‖2 6 D holds for all points zk on our trajectory and ‖z∗‖2 6 D. If the feasible set Z is bounded, then this assumption naturally holds. Assumption 2 (Standard MVI condition). The MVI of −V (z) has a solution, which means there exists a z∗, such that: 〈−V (z), z − z∗〉 > 0 holds for ∀z ∈ Z .

heading: 3.2 EXTRA GRADIENT AMSGRAD (AMSGRAD-EG)
text: In this section, we analyze the Extra Gradient AMSGrad (AMSGrad-EG) algorithm, which is 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 to obtain a related result. AMSGrad-EG algorithm is described as Algorithm 1.
Algorithm 1 Extra Gradient AMSGrad Input: The initial state z0 = m0 = v0 = 0, a constant learning rate η, momentum parameters β1t, β2, a Stochastic First-order Oracle (SFO) V (z; ξ), a sequence of batch sizes {Mk}. Output: zt where t is uniformly chosen from {0, 1, . . . , N − 1}.
1: for k = 1, . . . , N do 2: (Gradient Evaluation 1) gk−1 = 1Mk ∑Mk i=1 V (zk−1; ξ i k−1). 3: (Momentum Update 1) mk = β1km̂k−1 + (1− β1k)gk−1. 4: (Velocity Update 1) vk = max(β2v̂k−1 + (1− β2)g2k−1, v̂k−1), Hk = δI + Diag( √ vk). 5: (Shadow Update) ẑk = zk−1 + η ·H−1k mk. 6: (Gradient Evaluation 2) ĝk = 1Mk ∑Mk i=1 V (ẑk; ξ i k). 7: (Momentum Update 2) m̂k = β1kmk + (1− β1k)ĝk. 8: (Velocity Update 2) v̂k = max(β2vk + (1− β2)ĝ2k, vk), Ĥk = δI + Diag( √ v̂k)
9: (Real Update) zk = zk−1 + η · Ĥ−1k m̂k. 10: end for
Compared to the original Adam, we just add an 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 is non-decreasing.
Theorem 3.1 (Main Theorem 1). For the AMSGrad-EG algorithm, given the objective function φ(x, y) : Rn1+n2 → R and V (z) = (−∇xφ,∇yφ) that satisfy Assumption 1 and Assumption 2, as well as the initial point z0 ∈ Z , the iteration number N , a sequence of batch sizes {Mk} and a constant learning rate η 6 δ3L , then the output of the algorithm satisfies the following inequality:
E‖V (z)‖22 6 1
N
[ 6dD2(δ +G)2
η2 +
12dG2(δ +G)2
δ2
] + 150σ2(δ +G)
Nδ
N∑ t=1 1 Mt
+ 48GD(δ +G)
Nη
N∑ t=1 β1t + 108η2G2(δ +G) Nδ N∑ t=1 β21t.
Here, we analyze the conclusion above on two sides: parameter choosing on β1k and on Mk.
Discussion Here, we give some discussions on Theorem 3.1 and compare it with existing results. (1) There are two practical ways to choose the parameter sequence {β1t}: (1) β1t = β1 · λt−1 where β1, λ ∈ (0, 1) and (2) β1t = 1/t. In both settings, ∑N t=1 β 2 1t = O(1) and ∑N t=1 β1t = Õ(1).
Therefore, we can conclude from Theorem 3.1 that: E‖V (z)‖22 6 O(d/N) +O(1/N) · ∑N t=1 1/Mt holds after regarding D,G, δ, η as constants. (2) When the batch sizes Mk are constant, let Mk = Θ(1/ε2). To guarantee E‖V (z)‖22 6 ε2, the total number of iterations should beN = O(dε−2) and the total complexity is ∑N k=0Mk = O(dε−4). When the batch sizes Mk are increasing, let Mk = k + 1. To guarantee E‖V (z)‖22 6 ε2, the total number of iterations should be N = Õ(dε−2) and the total complexity is ∑N k=0Mk = Õ(d2ε−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 (z; ξ) = V (z), which means σ = 0. Theorem 3.1 leads to E‖V (z)‖22 6 O(d/N). To guarantee E‖V (z)‖22 6 ε2, the total number of iterations should be N = O(dε−2). (4) In the AMSGrad-EG algorithm, the momentum term is a technical difficulty on the convergence proof. Proofs in the past works always use the MVI condition or convex condition like 〈V (zk), zk − z∗〉 6 0 ⇒ 〈gk, zk − z∗〉 / 0 to control the gradient norms. However, if we replace gk with the momentum term mk, the inequality above will no longer hold, and then we have to find another way to control the upper bound of gradient norms. It’s also worth mentioned that our proof can’t be extended to Optimistic Adam (OAdam) since we need to guarantee that H1 H2 . . . in our proof. Actually, Adam may not even converge in convex case (Reddi et al., 2018). (5) Comparison with OAdaGrad: (Liu et al., 2020) proposes the Optimistic AdaGrad (OAdaGrad) algorithm and gives a convergence analysis on under Assumption 1, 2 and Bounded Cumulative Gradient Assumption (which assumes the existence of a constant 0 6 δ 6 1/2 such that the cumulative gradients are bounded as ‖ĝ1:k,i‖2 6 δkα for all k). Under these assumptions, they conclude that:
1
N N∑ k=1 E‖V (zk)‖2H−1k−1 6 O(1/N 1−α).
On one hand, notice that 1N ∑N k=1 E‖V (zk)‖2H−1k−1
is the average of the norms of V (zk). However, the norm keeps changing. Since H−1k−1 keeps decreasing and may limit to 0 as k →∞, its unclear what is the real convergence rate in terms of the size of the gradient. It would be more convincing if we can upper bound the average of constant norms like 1N ∑N k=1 E‖V (zk)‖22. 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., 2011), is actually a very strong assumption: Under this assumption, it holds that ‖ĝ1:k,i‖2 6 δkα, which naturally leads to:
1
N N∑ k=1 E‖V (zk)‖22 6 1 N N∑ k=1 E‖ĝk‖22 6 O ( d N1−2α ) ,
which causes circularity on the argument. In this paper, we overcome these two shortcomings.
Standard MVI and one-sided MVI conditions From Table 1, we can see that many related convergence proofs rely on assuming the MVI condition of −V (z), which means 〈V (z), z − z∗〉 6 0 ∀z ∈ Z . Although MVI condition is theoretically known to be true in many standard supervised deep learning settings (Li & Yuan, 2017; Kleinberg et al., 2018; Allen-Zhu & Li, 2020; AllenZhu & 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 a consistent gradient direction towards the optimal generator (which is the one that generates the target distribution), it is very unlikely that there is a “optimal discriminator” where the discriminator’s gradient is pointing to through the course of the training. Indeed, different generator
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, we only care about the min-variable x (which refers to the generator of GAN), and the optimally of y is not needed. Therefore, in the following part, we propose a weaker version of MVI condition, which is the one-sided MVI condition. Recall that z = (x, y), z∗ = (x∗, y∗) where x ∈ X , y ∈ Y,Z = X × Y , and V (z) = (−∇xφ(z),∇yφ(z)) := (Vx(z), Vy(z)). Then, the one-sided MVI condition implies that 〈Vx(z), x − x∗〉 6 0 ∀z ∈ Z , which means for any y ∈ Y , the x-part of function V , −V (·, y) 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 z, z∗ ∈ Z:
〈−V (z), z − z∗〉 = 〈−Vx(z), x− x∗〉+ 〈−Vy(z), y − y∗〉,
where z = (x, y), z∗ = (x∗, y∗). We call the three terms above as total MVI, x-sided MVI and y-sided MVI respectively. Assumption 2 requires total MVI to be non-negative, and Assumption 3 requires x-sided MVI to be non-negative. After training Wasserstein GAN on the MNIST/Fashion MNIST dataset with AMSGrad-EG optimizer, we denote zk := (xk, yk) as the value of z at the k-th iteration, and z∗ := (x∗, y∗) as the value of z at the last iteration. In the following Figure 2, we plot the total MVI values 〈−V (zk), zk − z∗〉, x-sided MVI values 〈−Vx(zk), xk − x∗〉, and y-sided MVI values 〈−Vy(zk), yk − y∗〉 along the training trajectory. We can see that x-sided MVI stays positive while the total MVI does not, which means the one-sided MVI condition proposed in Assumption 3 is more realistic than the original MVI condition in Assumption 2. Under the one-sided MVI condition,
we prove in our next theorem that, the conclusion of Theorem 3.1 still holds once we slightly modify AMSGrad-EG to Extra Gradient AMSGrad with Dual Rate Decay (AMSGrad-EG-DRD). To the best of our knowledge, this is a convergence guarantee of an adaptive min-max algorithm with the weakest assumption ever needed. In the next section, we introduce the AMSGrad-EG-DRD algorithm and its convergence property.

heading: 3.3 EXTRA GRADIENT AMSGRAD WITH DUAL RATE DECAY
text: Now, we write down the one-sided MVI condition introduced above in Assumption 3, which is the weakest assumption ever needed to obtain a convergence guarantee in min-max optimization.
Assumption 3 (One-sided MVI condition). The one-sided MVI of −V (z) has a solution, which means there exists a z∗ = (x∗, y∗) ∈ Z , such that:
〈−Vx(z), x− x∗〉 > 0 holds for ∀z = (x, y) ∈ Z.
After slightly modifying AMSGrad-EG with a O(1/ √ k) dual rate decay, we get Extra Gradient AMSGrad with dual rate decay (AMSGrad-EG-DRD). 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-Gradient and Dual Rate Decay (AMSGrad-EG-DRD) algorithm, given the objective function φ(x, y) : Rn1+n2 → R and V (z) = (−∇xφ,∇yφ) := (Vx(z), Vy(z)) that satisfy Assumption 1 and Assumption 3, as well as the initial point z0 ∈ Z , the iteration number N , a sequence of batch sizes {Mk} and a constant learning rate η 6 δ3L , then the output of the algorithm satisfies the following inequality:
E‖Vx(z)‖22 6 (15 + 3 logN)dG2(δ +G)2
Nδ2 +
6dD2(δ +G)2
Nη2 +
150σ2(δ +G)
Nδ
N∑ t=1 1 Mt
+ 48GD(δ +G)
Nη
N∑ t=1 β1t + 108η2G2(δ +G) Nδ N∑ t=1 β21t.
Similar to Theorem 3.1, in the deterministic setting where σ = 0, the total complexity is Õ(dε−2). In the stochastic setting, we have: E‖Vx(z)‖22 6 Õ(d/N) +O(1/N) · ∑N t=1 1/Mt. When we use constant batch sizes Mk = Θ(1/ε2), iteration number N should be Õ(dε−2) in order to guarantee that E‖Vx(z)‖22 6 ε2. So the total complexity should be Õ(dε−4).

heading: 4 EXPERIMENTAL RESULTS
text: In this section, we use experiments to verify the effectiveness of AMSGrad-EG and AMSGrad-EGDRD algorithms by applying Wasserstein GAN (Arjovsky et al., 2017) on the MNIST (LeCun et al., 1998) and Fashion-MNIST (Xiao et al., 2017) datasets in our experiments. More experiments will be shown in the appendix. The architectures of discriminator and generator are 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 1e-4 and we compare AMSGrad-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) to complete our experiments. As a 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.

heading: 5 DISCUSSION AND FUTURE WORKS
text: 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 an 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 an 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 so that we can get some intuition on their differences.

heading: A PROOF FOR THE CONVERGENCE OF AMSGRAD-EG
text: We recall that in the t-th iteration of Extra-Gradient AMSGrad, our update is as follows:
mt = β1tm̂t−1 + (1− β1t)gt−1, vt = max(β2v̂t−1 + (1− β2)g2t−1, v̂t−1) Ht = δI + Diag( √ vt), ẑt = zt−1 + η ·H−1t mt
m̂t = β1tmt + (1− β1t)ĝt, v̂t = max(β2vt + (1− β2)ĝ2t , vt) Ĥt = δI + Diag( √ v̂t), zt = zt−1 + η · Ĥ−1t m̂t.
(1)
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 mt, m̂t are also contained in l2 ball with radius G. Lemma A.1. There exist upper bounds for both velocity terms vt, v̂t and momentum terms mt, m̂t: (1) For ∀t ∈ N, almost surely, the momentum terms ‖mt‖2 6 G, ‖m̂t‖2 6 G. (2) For ∀t ∈ N, almost surely, the velocity terms |vt,i| 6 G2, |v̂t,i| 6 G2 hold for ∀i ∈ [d].
Proof of Lemma A.1. Actually, this lemma can be simply proved by using the method of induction. Since we’ve assumed that ‖V (z)‖2 6 G almost surely holds for z ∈ Z = Rd, so ‖gt‖2 6 G and ‖ĝt‖2 6 G almost surely holds. Therefore, by knowing that m0 = m̂0 = 0 ⇒ 0 = ‖m0‖2 = ‖m̂0‖ 6 G and once ‖mk−1‖2 6 G, ‖m̂k−1‖2 6 G, we have:
‖mk‖2 = ‖β1km̂k−1 + (1− β1k)gk−1‖2 6 β1k‖m̂k−1‖2 + (1− β1k)‖gk−1‖2 6 (1− β1k)G+ β1kG = G ‖m̂k‖2 = ‖β1kmk + (1− β1k)ĝk‖2 6 β1k‖mk‖2 + (1− β1k)‖ĝk‖2 6 (1− β1k)G+ β1kG = G.
Similarly, the upper bound for velocity terms can also be easily proved.

heading: Lemma A.2.
text: ‖zt − z∗‖2Ĥt 6 ‖zt−1 − z ∗‖2 Ĥt − ‖zt−1 − ẑt‖2Ĥt + ‖ẑt − zt‖ 2 Ĥt + 2〈η · ε̂t, ẑt − z∗〉+ 8ηβ1tGD.
Here, ε̂t = ĝt − V (ẑt) = 1Mt ∑Mt i=1 V (ẑt; ξ̂i)− V (ẑt).
Proof of Lemma A.2. According to the update rules:
‖zt − z∗‖2Ĥt = ‖zt−1 + η · Ĥ −1 t m̂t − z∗‖2Ĥt
= ‖zt−1 + η · Ĥ−1t m̂t − z∗‖2Ĥt − ‖zt−1 + η · Ĥ −1 t m̂t − zt‖2Ĥt = ‖zt−1 − z∗‖2Ĥt − ‖zt−1 − zt‖ 2 Ĥt + 2〈η · m̂t, zt − z∗〉 = ‖zt−1 − z∗‖2Ĥt − ‖zt−1 − ẑt + ẑt − zt‖ 2 Ĥt + 2〈η · m̂t, zt − ẑt〉+ 2〈η · m̂t, ẑt − z∗〉 = ‖zt−1 − z∗‖2Ĥt − ‖zt−1 − ẑt‖ 2 Ĥt − ‖ẑt − zt‖2Ĥt − 2〈Ĥt(zt−1 − ẑt), ẑt − zt〉
+ 2〈η · m̂t, zt − ẑt〉+ 2〈η · m̂t, ẑt − z∗〉 = ‖zt−1 − z∗‖2Ĥt − ‖zt−1 − ẑt‖ 2 Ĥt − ‖ẑt − zt‖2Ĥt + 2〈η · m̂t, ẑt − z ∗〉
+ 2〈zt − ẑt, Ĥt(zt−1 − ẑt + η · Ĥ−1t m̂t)〉 = ‖zt−1 − z∗‖2Ĥt − ‖zt−1 − ẑt‖ 2 Ĥt − ‖ẑt − zt‖2Ĥt + 2〈η · m̂t, ẑt − z ∗〉
+ 2〈zt − ẑt, Ĥt(zt − ẑt)〉 = ‖zt−1 − z∗‖2Ĥt − ‖zt−1 − ẑt‖ 2 Ĥt + ‖ẑt − zt‖2Ĥt + 2〈η · m̂t, ẑt − z ∗〉
Notice that ĝt = V (ẑt) + ε̂t. Since z∗ is a solution of MVI which means 〈V (z), z − z∗〉 6 0 holds for ∀z ∈ Z , so 〈V (ẑt), ẑt − z∗〉 6 0. Therefore:
〈η · m̂t, ẑt − z∗〉 = 〈η · (β1tmt + (1− β1t)ĝt), ẑt − z∗〉 6 〈η · ĝt, ẑt − z∗〉+ 〈η · β1t(mt − ĝt), ẑt − z∗〉 6 〈η · (V (ẑt) + ε̂t), ẑt − z∗〉+ ηβ1t · ‖mt − ĝt‖2 · ‖ẑt − z∗‖2 (a)
6 〈ηε̂t, ẑt − z∗〉+ 4ηβ1tGD.
Here, (a) holds because ‖mt − ĝt‖2 6 ‖mt‖2 + ‖ĝt‖2 6 2G, ‖ẑt − z∗‖2 6 2D and by using MVI property, 〈V (ẑt), ẑt − z∗〉 6 0. Combine it with the inequality above, we obtain that:
‖zt − z∗‖2Ĥt 6 ‖zt−1 − z ∗‖2 Ĥt − ‖zt−1 − ẑt‖2Ĥt + ‖ẑt − zt‖ 2 Ĥt + 2〈η · ε̂t, ẑt − z∗〉+ 8ηβ1tGD.
which comes to our conclusion.
In the lemma above, 〈η · ε̂t, ẑt − z∗〉 has zero mean. So it can be ignoring when taking expectation. Next, we upper bound the ‖ẑt − zt‖2Ĥt term.

heading: Lemma A.3.
text: ‖ẑt − zt‖2Ĥt 6 2η 2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 16η2G2β21t δ + 12η2L2 δ2 · ‖ẑt − zt−1‖2Ĥt
+ 12η2 · ( ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 H−1t ) .
Here, εt−1 = gt−1 − V (zt−1) and ε̂t = ĝt − V (ẑt).
Proof of Lemma A.3. According to the update rules (1), we know that zt − ẑt = η · (Ĥ−1t m̂t − H−1t mt). Therefore, we upper bound the term ‖ẑt − zt‖2Ĥt as follows:
‖ẑt − zt‖2Ĥt = η 2 · ‖Ĥ−1t m̂t −H−1t mt‖2Ĥt = η 2 · ‖Ĥ−1t (m̂t −mt) + (Ĥ−1t −H−1t )mt‖2Ĥt 6 2η2 · ( ‖m̂t −mt‖2Ĥ−1t + ‖(Ĥ −1 t −H−1t )mt‖2Ĥt ) (a) = 2η2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 2η
2 · ‖β1t(mt − m̂t−1) + (1− β1t)(ĝt − gt−1)‖2Ĥ−1t (b) 6 2η2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 4η 2 ( β21t‖mt − m̂t−1‖2Ĥ−1t + (1− β1t) 2‖ĝt − gt−1‖2Ĥ−1t ) (c)
6 2η2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 16η2β21tG 2 δ + 4η2‖ĝt − gt−1‖2Ĥ−1t
(d) = 2η2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 16η2G2β21t δ
+ 4η2‖V (ẑt)− V (zt−1) + ε̂t − εt−1‖2Ĥ−1t (e)
6 2η2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 16η2G2β21t δ + 12η2 · ‖V (ẑt)− V (zt−1)‖2Ĥ−1t
+ 12η2 · ( ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 Ĥ−1t ) (f)
6 2η2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 16η2G2β21t δ + 12η2L2 δ2 · ‖ẑt − zt−1‖2Ĥt
+ 12η2 · ( ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 H−1t ) Here, (a) holds because mt = β1tm̂t−1 + (1− β1t)gt−1, m̂t = β1tmt + (1− β1t)ĝt, and then:
m̂t −mt = β1t(mt − m̂t−1) + (1− β1t)(ĝt − gt−1).
(b) holds because ‖a + b‖2C 6 (‖a‖C + ‖b‖C)2 6 2(‖a‖2C + ‖b‖2C) and (e) holds because of the similar reason: ‖x+ y + z‖2C 6 (‖x‖C + ‖y‖C + ‖z‖C)2 6 3(‖x‖2C + ‖y‖2C + ‖z‖2C). (c) holds because (1− β1t)2 < 1 and
‖mt − m̂t−1‖2Ĥ−1t 6 ‖mt − m̂t−1‖2 δ 6 4G2 δ .
(d) holds because ĝt = V (ẑt) + ε̂t and gt−1 = V (zt−1) + εt−1. (f) holds because of the following fact:
δI = H0 Ĥ0 H1 Ĥ1 . . . ĤN . . . , or equivalently:
1 δ I H−10 Ĥ −1 0 H −1 1 Ĥ −1 1 . . . Ĥ −1 N . . . ,
which leads to ‖εt−1‖2Ĥ−1t 6 ‖εt−1‖ 2 H−1t . Also, V (·) is L-Lipschitz continuous and δI Ĥt, so:
‖V (ẑt)− V (zt−1)‖2Ĥ−1t 6 L2 δ2 ‖ẑt − zt−1‖2Ĥt .
Since our learning rate η 6 δ5L , we have 12η2L2 δ2 6 1 2 . Now, we can combine Lemma A.2 and Lemma

heading: A.3:
text: ‖zt − z∗‖2Ĥt 6 ‖zt−1 − z ∗‖2 Ĥt − ‖zt−1 − ẑt‖2Ĥt + 2〈η · ε̂t, ẑt − z ∗〉+ 8ηβ1tGD
+ 2η2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 16η2G2β21t δ + 12η2L2 δ2 · ‖ẑt − zt−1‖2Ĥt
+ 12η2 · ( ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 H−1t ) ,
Since 12η 2L2
δ2 6 1 2 , therefore:
‖zt − z∗‖2Ĥt 6 ‖zt−1 − z ∗‖2 Ĥt − 1 2 ‖zt−1 − ẑt‖2Ĥt + 2〈η · ε̂t, ẑt − z ∗〉+ 8ηβ1tGD + 16η2G2β21t δ
+ 2η2 · ‖(Ĥ−1t −H−1t )mt‖2Ĥt + 12η 2 · ( ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 H−1t ) .
After taking expectation and summation over t = 1, 2, . . . , N , we obtain that:
1
2 N∑ t=1 E‖zt−1 − ẑt‖2Ĥt 6 N∑ t=1 E [ ‖zt−1 − z∗‖2Ĥt − ‖zt − z ∗‖2 Ĥt ] + N∑ t=1 [ 8ηβ1tGD + 16η2G2β21t δ ]
+ 2η2 · N∑ t=1 E‖(Ĥ−1t −H−1t )mt‖2Ĥt + 12η 2 · N∑ t=1 E [ ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 H−1t ] .
(2) Since ‖zt−1−ẑt‖2Ĥt = ‖η·H −1 t mt‖2Ĥt and V (zt−1) = gt−1−εt−1 = mt−β1t(m̂t−1−gt−1)−εt−1, we know that:
‖V (zt−1)‖2H−1t = ‖mt − β1t(m̂t−1 − gt−1)− εt−1‖ 2 H−1t 6 3 ( ‖mt‖2H−1t + ‖β1t(m̂t−1 − gt−1)‖ 2 H−1t + ‖εt−1‖2H−1t ) = 3 ( ‖β1t(m̂t−1 − gt−1)‖2H−1t + ‖εt−1‖ 2 H−1t ) + 3 · ‖H−1t mt‖2Ĥt
6 12G2β21t
δ + 3‖εt−1‖2H−1t +
3
η2 ‖zt−1 − ẑt‖2Ĥt
(3)
After combining Equation (2) and Equation (3), it holds that: N∑ t=1 E‖V (zt−1)‖2H−1t 6 6 η2 N∑ t=1 E [ ‖zt−1 − z∗‖2Ĥt − ‖zt − z ∗‖2 Ĥt ] + N∑ t=1 [ 48β1tGD η + 108η2G2β21t δ ]
+ 12 N∑ t=1 E‖(Ĥ−1t −H−1t )mt‖2Ĥt + 75 N∑ t=1 E [ ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 H−1t ] .
(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.

heading: Lemma A.4.
text: N∑ t=1 [ ‖zt−1 − z∗‖2Ĥt − ‖zt − z ∗‖2 Ĥt ] 6 dD2 · (δ +G),
which is a constant.
Proof of Lemma A.4. Notice that
N∑ t=1 [ ‖zt−1 − z∗‖2Ĥt − ‖zt − z ∗‖2 Ĥt ] 6 ‖z0 − z∗‖2Ĥ0 + N−1∑ t=1 ( ‖zt − z∗‖2Ĥt+1 − ‖zt − z ∗‖2 Ĥt ) = ‖z0 − z∗‖2Ĥ0 + N−1∑ t=1 [ (zt − z∗)>(Ĥt+1 − Ĥt) · (zt − z∗)
] 6 D2 · tr(Ĥ0) +
N−1∑ t=1 D2 · (tr(Ĥt+1)− tr(Ĥt)) = D2 · tr(ĤN ) 6 dD2 · (δ +G),
which comes to our conclusion.
For the second term, it’s easy to see that:
N∑ t=1 [ 48β1tGD η + 108η2G2β21t δ ] = 48GD η N∑ t=1 β1t + 108η2G2 δ N∑ t=1 β21t, (5)
Next, we analyze the third term. Lemma A.5.
N∑ t=1 ‖(H−1t − Ĥ−1t )mt‖2Ĥt 6 dG2(δ +G) δ2 .
Proof of Lemma A.5. For any δ 6 x < y, we notice that:
y
( 1
x − 1 y
)2 = (y − x)2
x2y < y − x x2 6 y − x δ2 . (6)
Therefore, we have:
N∑ t=1 ‖(H−1t − Ĥ−1t )mt‖2Ĥt 6 N∑ t=1 m>t (H −1 t − Ĥ−1t )Ĥt(H−1t − Ĥ−1t )mt
6 N∑ t=1 G2 · tr ( (H−1t − Ĥ−1t )Ĥt(H−1t − Ĥ−1t ) )
(a) 6 N∑ t=1 G2 δ2 · [tr(Ĥt)− tr(Ht)]
6 G2
δ2 · tr(ĤN ) <
G2
δ2 · d(δ +G) = dG
2(δ +G)
δ2 .
Here, (a) holds because of Equation (6). Finally, we come to the noise term ∑N t=1 E [ ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 H−1t ] , which is closely related to our batch sizes Mt. Obviously, we have:
E‖ε̂t‖2Ĥ−1t 6 1 δ · E‖ε̂t‖22 6 1 δ · σ
2
Mt .
Similarly,
E‖εt−1‖2H−1t 6 1 δ · σ
2
Mt Therefore, we can upper bound the expectation of the noise term as:
N∑ t=1 E [ ‖ε̂t‖2Ĥ−1t + ‖εt−1‖ 2 H−1t ] 6 2σ2 δ N∑ t=1 1 Mt . (7)
Finally, after we combine Equation (4) with Equation (5), Equation (7) and Lemma A.4, Lemma A.5, we obtain that:
N∑ t=1 E‖V (zt−1)‖2H−1t 6 6dD2(δ +G) η2 + 12dG2(δ +G) δ2 + 150σ2 δ N∑ t=1 1 Mt
+ 48GD
η N∑ t=1 β1t + 108η2G2 δ N∑ t=1 β21t.
Since for ∀t, ‖V (zt−1)‖H−1t > 1 δ+G‖V (zt−1)‖2, therefore:
N∑ t=1 E‖V (zt−1)‖2 6 6dD2(δ +G)2 η2 + 12dG2(δ +G)2 δ2 + 150σ2(δ +G) δ N∑ t=1 1 Mt
+ 48GD(δ +G)
η
N∑ t=1 β1t + 108η2G2(δ +G) δ N∑ t=1 β21t,
(8)
which comes to our conclusion.

heading: B PROOF FOR THE CONVERGENCE OF AMSGRAD-EG-DRD
text: In the t-th iteration of AMSGrad-EG-DRD, our update is as follows:
mt = β1tm̂t−1 + (1− β1t)gt−1, vt = max(β2v̂t−1 + (1− β2)g2t−1, v̂t−1) Ht = δI + Diag( √ vt), ẑt := (x̂t, ŷt) = (xt−1 + η · (Hxt )−1mxt , yt−1 +
η√ t · (Hyt )−1m y t )
m̂t = β1tmt + (1− β1t)ĝt, v̂t = max(β2vt + (1− β2)ĝ2t , vt) Ĥt = δI + Diag( √ v̂t), zt := (xt, yt) = (xt−1 + η · (Ĥxt )−1m̂xt , yt−1 +
η√ t · (Ĥyt )−1m̂ y t ).
(9)
Most parts of this convergence proof are similar to the convergence proof of AMSGrad-EG. Lemma A.1 still holds.
Lemma B.1.
‖xt−x∗‖2Ĥxt 6 ‖xt−1−x ∗‖2 Ĥxt −‖xt−1− x̂t‖2Ĥxt + ‖x̂t−xt‖ 2 Ĥxt + 2〈η · ε̂xt , x̂t−x∗〉+ 8ηβ1tGD.
Here, ε̂xt = ĝ x t − Vx(ẑt) = 1Mt ∑Mt i=1 Vx(ẑt; ξ̂i)− Vx(ẑt).
We can use the same technique of Lemma A.2 to prove it. Next, we obtain the next lemma.

heading: Lemma B.2.
text: ‖x̂t − xt‖2Ĥxt 6 2η 2 · ‖((Ĥxt )−1 − (Hxt )−1)mxt ‖2Ĥxt + 16η2G2β21t δ + 12η2L2 δ2 · ‖ẑt − zt−1‖2Ĥt
+ 12η2 · ( ‖ε̂xt ‖2(Ĥxt )−1 + ‖ε x t−1‖2(Hxt )−1 ) .
Here, εt−1 = gt−1 − V (zt−1) and ε̂t = ĝt − V (ẑt).
We can prove it by using the same technique as Lemma A.3. Since we have 12η 2L2
δ2 6 1 2 . Now, we
can combine Lemma B.1 and Lemma B.2:
‖xt − x∗‖2Ĥxt 6 ‖xt−1 − x ∗‖2 Ĥxt − ‖xt−1 − x̂t‖2Ĥxt + 2〈η · ε̂ x t , x̂t − x∗〉+ 8ηβ1tGD
+ 2η2 · ‖((Ĥxt )−1 − (Hxt )−1)mxt ‖2Ĥxt + 16η2G2β21t δ + 1 2 ‖ẑt − zt−1‖2Ĥt
+ 12η2 · ( ‖ε̂xt ‖2(Ĥxt )−1 + ‖ε x t−1‖2(Hxt )−1 ) ,
After taking expectation and summation over t = 1, 2, . . . , N , we obtain that:
1
2 N∑ t=1 E‖xt−1 − x̂t‖2Ĥxt 6 N∑ t=1 E [ ‖xt−1 − x∗‖2Ĥxt − ‖xt − x ∗‖2 Ĥxt ] + N∑ t=1 [ 8ηβ1tGD + 16η2G2β21t δ ]
+ 2η2 · N∑ t=1 E‖((Ĥxt )−1 − (Hxt )−1)mxt ‖2Ĥxt + 12η 2 · N∑ t=1 E [ ‖ε̂xt ‖2(Ĥxt )−1 + ‖ε x t−1‖2(Hxt )−1 ] + 1
2 N∑ t=1 E‖yt−1 − ŷt‖2Ĥyt .
(10) Since ‖xt−1 − x̂t‖2Ĥxt = ‖η · (H x t ) −1mxt ‖2Ĥxt and Vx(zt−1) = g x t−1 − εxt−1 = mxt − β1t(m̂xt−1 − gxt−1)− εxt−1, we know that:
‖Vx(zt−1)‖2(Hxt )−1 = ‖m x t − β1t(m̂xt−1 − gxt−1)− εxt−1‖2(Hxt )−1 6 3 ( ‖mxt ‖2(Hxt )−1 + ‖β1t(m̂ x t−1 − gxt−1)‖2(Hxt )−1 + ‖ε x t−1‖2(Hxt )−1 ) = 3 ( ‖β1t(m̂xt−1 − gxt−1)‖2(Hxt )−1 + ‖ε x t−1‖2(Hxt )−1 ) + 3 · ‖(Hxt )−1mxt ‖2Ĥxt
6 12G2β21t
δ + 3‖εxt−1‖2(Hxt )−1 +
3
η2 ‖xt−1 − x̂t‖2Ĥxt
(11) After combining Equation (10) and Equation (11), it holds that: N∑ t=1 E‖Vx(zt−1)‖2(Hxt )−1 6 6 η2 N∑ t=1 E [ ‖xt−1 − x∗‖2Ĥxt − ‖xt − x ∗‖2 Ĥxt ] + N∑ t=1 [ 48β1tGD η + 108η2G2β21t δ ]
+ 12 N∑ t=1 E‖((Ĥxt )−1 − (Hxt )−1)mxt ‖2Ĥxt + 75 N∑ t=1 E [ ‖ε̂xt ‖2(Ĥxt )−1 + ‖ε x t−1‖2(Hxt )−1 ] + 3
η2 N∑ t=1 E‖yt−1 − ŷt‖2Ĥyt . (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-EG algorithm above.

heading: Lemma B.3.
text: N∑ t=1 [ ‖xt−1 − x∗‖2Ĥxt − ‖xt − x ∗‖2 Ĥxt ] 6 dD2 · (δ +G),
which is a constant.

heading: Lemma B.4.
text: N∑ t=1 ‖((Hxt )−1 − (Ĥxt )−1)mt‖2Ĥxt 6 dG2(δ +G) δ2 .
Finally, the last term can be perfectly bounded by the O(1/ √ t) decayed learning rate.
N∑ t=1 E‖yt−1 − ŷt‖2Ĥyt 6 N∑ t=1 E η2 t ‖(Ĥyt )−1m y t ‖2Ĥyt
6 N∑ t=1 E η2 t · G 2 δ = η2G2 δ (1 + logN). (13)
To sum up, we eventually get the equation that:
E‖Vx(z)‖22 6 (15 + 3 logN)dG2(δ +G)2
Nδ2 +
6dD2(δ +G)2
Nη2 +
150σ2(δ +G)
Nδ
N∑ t=1 1 Mt
+ 48GD(δ +G)
Nη
N∑ t=1 β1t + 108η2G2(δ +G) Nδ N∑ t=1 β21t,
which comes to our conclusion.

heading: C MORE EXPERIMENTAL RESULTS
text: In this section, we further use experiments to verify the effectiveness of AMSGrad-EG and AMSGradEG-DRD algorithms proposed by us. Also, we 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 et al., 2015) on CIFAR10 dataset. We set our batch size as 100, learning rate as 1e-4 and we compare AMSGrad-EG, AMSGrad-EG-DRD and SGDA by drawing their generated figures after 50, 100, 200 iterations in the following Figure 2. The two algorithms proposed by us again perform better than the non-adaptive SGDA. After training DCGAN on the CIFAR10 dataset with AMSGrad-EG optimizer, we plot the total MVI values 〈−V (zk), zk− z∗〉, x-sided MVI values 〈−Vx(zk), xk−x∗〉, and y-sided MVI values 〈−Vy(zk), yk − y∗〉 along the training trajectory as the following Figure 4.

heading: D STOCHASTIC EXTRA-GRADIENT AND ADAPTIVE EXTRA-GRADIENT ALGORITHMS
text: In a 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-Gradient (SEG) and Adaptive Extra-Gradient (AEG). We put the result in the appendix because it is just a by-product of this research and not our main result.
Before we introduce our newly-proposed Adaptive Extra-Gradient method, we slightly modify the Stochastic Extra-Gradient (SEG) algorithm, by using different batch sizes in each iteration, as Algorithm 2 below.
Algorithm 2 Stochastic Extra-Gradient (SEG) with batch size Input: The initial state ẑ0 = z0 = 0, a constant learning rate η, a Stochastic First-order Oracle (SFO) V (z; ξ), a sequence of batch sizes {mk}k>1. Output: zt, t is uniformly chosen from {0, 1, 2, . . . , N − 1}. 1: for k = 1, . . . , N do 2: (Gradient Evaluation) gk−1 = 1mk ∑mk i=1 V (zk−1; ξ i k−1).
3: (Shadow Update) ẑk = ΠZ [zk−1 + η · gk−1]. 4: (Gradient Evaluation) ĝk−1 = 1mk ∑mk i=1 V (ẑk; ξ̂ i k−1) 5: (Real Update) zk = ΠZ [zk−1 + η · ĝk−1] 6: end for
Algorithm 3 is a basic idea on the design of AEG algorithm. Here, we use constant batch size m and let gk−1 = 1m ∑m i=1 V (zk−1, ξ i k−1), ĝk−1 = 1 m ∑m i=1 V (ẑk, ξ̂ i k−1) be the estimated gradients on zk−1 and ẑk in the k-th iteration. Also, ĝ1:k is the concatenation of ĝ1, . . . , ĝk, and ĝ1:k,i is its i-th
row vector. Similarly, g0:k is the concatenation of g0, . . . , gk, and g0:k,i is its i-th row vector. Note that all the matrices Hk, Sk are diagonal so they don’t require extra computation complexity.
Algorithm 3 Adaptive Extra-Gradient (AEG) Input: The initial state ẑ0 = z0 = 0, H0 = Ĥ0 = δI , a constant learning rate η, a Stochastic First-order Oracle (SFO) V (z; ξ), a constant batch size m. Output: zt, t is uniformly chosen from {0, 1, 2, . . . , N − 1}. 1: for k = 1, . . . , N do 2: (Gradient Evaluation) gk−1 = 1m ∑m i=1 V (zk−1; ξ i k−1).
3: (Gradient Concatenation and Norm Calculation) Update g0:k = [g0:k−2 gk−1], sk−1,i = ‖ (g0:k−1,i ĝ1:k−1,i) ‖2 i = 1, 2, . . . , d and Hk−1 = δI + diag(sk−1). 4: (Shadow Update) ẑk = zk−1 + η ·H−1k−1gk−1 5: (Gradient Evaluation) ĝk−1 = 1m ∑m i=1 V (ẑk; ξ̂ i k−1). 6: (Gradient Concatenation and Norm Calculation) Update ĝ1:k = [ĝ1:k−1 ĝk], ŝk−1,i = ‖ (g0:k−1,i ĝ1:k,i) ‖2 i = 1, 2, . . . , d and Sk−1 = δI + diag(ŝk−1). 7: (Real Update) zk = zk−1 + η · S−1k−1ĝk−1 8: end for
Now, we introduce the following two theorems (Theorem D.1 and Theorem D.2), which compare the convergence rates of 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, y) : X ×Y → R where X ⊆ Rn1 ,Y ⊆ Rn2 , which is denoted as: V (z; ξ) and it satisfies the following conditions:
E[V (z; ξ)] = V (z) := (−∇xφ,∇yφ) and E‖V (z; ξ)− V (z)‖2 6 σ2. Here, z := (x, y) and Z := X × Y . Also: the corresponding MVI function of −V has a solution z∗ ∈ Z , which means 〈−V (z), z − z∗〉 > 0 holds for ∀z ∈ Z .
• A positive real L such that V is L-Lipschitz continuous with respect to ‖ · ‖2.
• The learning rate η.
• An initial point z0 ∈ Z .
• The iteration number N .
• The sequence of batch sizes in each iteration {mk}k>1.
Then, we output a result z ∈ Z which satisfies:
E[r2η(z)] 6 4‖z0 − z∗‖2
N +
50η2
N N−1∑ k=0 σ2 mk
where rα(z) := ‖z−ΠZ(z+α ·V (z))‖2 and η 6 14L . If Z = R n1+n2 , then the projection operator Π is the identity, and rα(z) := α · ‖V (z)‖2. The inequality above becomes:
E‖V (z)‖22 6 4‖z0 − z∗‖2
η2N +
50
N N−1∑ k=0 σ2 mk .
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 η = 14L . If the batch sizes are constant, which means mk = m for ∀k. In order to guarantee that E‖V (z)‖2 6 ε2, we have to make m = O(1/ε2) and N = O(L2/ε2), and the total complexity is ∑N k=1mk = mN = O(L
2/ε4). In another scenario where mk = k + 1 is an increasing sequence, in order to guarantee that E‖V (z)‖2 6 ε2, we have to make N = O(L2/ε2) and then the total complexity is ∑N k=1mk = ∑N k=1(k + 1) = O(L 4/ε4).
Theorem D.2 (Convergence of AEG). When our objective function φ(x, y) satisfies Assumption 1 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) : Rn1+n2 → R, which is denoted as: V (z; ξ) and it satisfies the following conditions:
E[V (z; ξ)] = V (z) := (−∇xφ,∇yφ) and E‖V (z; ξ)− V (z)‖2 6 σ2.
Here, z := (x, y) and Z := Rn1+n2 = Rd where d := n1 + n2. Also: the corresponding MVI function of V has a solution z∗ ∈ Z .
• Positive real numbers G, such that ‖V (z; ξ)‖2 6 G almost surely holds.
• A positive real L such that V is L-Lipschitz continuous with respect to ‖ · ‖2.
• A universal constant D > 0 such that ‖zk − z∗‖2 6 D and for all the points on the trajectory of our algorithm.
• An initial point z0 ∈ Z .
• The iteration number N .
• A constant batch size m.
• A constant 0 6 α 6 1/2 such that: the cumulative gradients are bounded as: ‖(g1:k,i ĝ1:k,i)‖2 6 2δ · kα for all i, k.
• The constant learning rate η 6 δ4L .
The output results z0, z1, . . . , zN−1 satisfies the following inequality:
1 N E N−1∑ k=0 ‖V (zk)‖2H−1k 6 16dD2δ/η2 + 200dδ + 40dG2/δ N1−α + 50δσ2/m+ 2G2d/δ N .
If we switch the assumption of MVI condition (Assumption 2) to the one-sided MVI condition (Assumption 3), we can slightly modify the Adaptive Extra-Gradient (AEG) method to Adaptive Extra-Gradient with Dual Rate Decay (AEG-DRD), where the learning rate of {yk} variables set as ηk . In the Algorithm 4 below, Hk = Diag(Ak, Bk) and Sk = Diag(Ck, Dk) where for each k ∈ N, Ak, Ck ∈ Rn1×n1 and Bk, Dk ∈ Rn2×n2 . Also, gk = (gxk , g y k) and ĝk = (ĝ x k , ĝ y k) where gxk , ĝ x k ∈ Rn1 and g y k , ĝ y k ∈ Rn2 .
Algorithm 4 Adaptive Extra-Gradient with Dual Rate Decay (AEG-DRD) Input: The initial state ẑ0 = z0 = 0, H0 = Ĥ0 = δI , a constant learning rate η, a Stochastic First-order Oracle (SFO) V (z; ξ), a constant batch size m. Output: zt where t is uniformly chosen from {0, 1, 2, . . . , N−1}. 1: for k = 1, . . . , N do 2: (Gradient Evaluation) gk−1 = 1m ∑m i=1 V (zk−1; ξ i k−1).
3: (Gradient Concatenation and Norm Calculation) Update g0:k = [g0:k−2 gk−1], sk−1,i = ‖ (g0:k−1,i ĝ1:k−1,i) ‖2 i = 1, 2, . . . , d and Hk−1 = δI + diag(sk−1). 4: (Shadow Update of x) x̂k = xk−1 + η ·A−1k−1gxk−1. 5: (Shadow Update of y) ŷk = yk−1 + ηk ·B −1 k−1g y k−1.
6: (Gradient Evaluation) ĝk−1 = 1m ∑m i=1 V (ẑk; ξ̂ i k−1). 7: (Gradient Concatenation and Norm Calculation) Update ĝ1:k = [ĝ1:k−1 ĝk], ŝk−1,i = ‖ (g0:k−1,i ĝ1:k,i) ‖2 i = 1, 2, . . . , d and Sk−1 = δI + diag(ŝk−1). 8: (Real Update of x) xk = xk−1 + η · C−1k−1ĝxk−1. 9: (Real Update of y) yk = yk−1 + ηk ·D −1 k−1ĝ y k−1.
10: end for
Theorem D.3 (Convergence of AEG-DRD). When our objective function φ(x, y) satisfies Assumption 2 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 φ(x, y) : Rn1+n2 → R, which is denoted as: V (z; ξ) and it satisfies the following conditions:
E[V (z; ξ)] = V (z) := (−∇xφ,∇yφ) and E‖V (z; ξ)− V (z)‖2 6 σ2.
Here, z := (x, y) and Z := Rn1+n2 = Rd where d := n1 + n2. Also: the one-sided MVI function of V has a solution z∗ ∈ Z .
• Positive real numbers G, such that ‖V (z; ξ)‖2 6 G almost surely holds.
• A positive real L such that V is L-Lipschitz continuous with respect to ‖ · ‖2.
• A universal constant D > 0 such that ‖zk − z∗‖2 6 D and for all the points on the trajectory of our algorithm.
• An initial point z0 ∈ Z .
• The iteration number N .
• A constant batch size m.
• A constant 0 6 α 6 1/2 such that: the cumulative gradients are bounded as: ‖(g1:k,i ĝ1:k,i)‖2 6 2δ · kα for all i, k.
• The constant learning rate η 6 δ4L .
The output results z0, z1, . . . , zN−1 satisfy the following inequality:
1
N E N∑ k=1 ‖Vx(zk−1)‖2C−1k−1 6 16dD2δ/η2 + 200dδ + 40dG2/δ N1−α + 24dG2/δ + 50δσ2/m N .

heading: D.1 PROOF OF THEOREM D.1
text: We recall that in the t-th iteration of Stochastic Extra-Gradient (SEG) algorithm with batch size, we have the following updates:
ẑt = ΠZ [ zt−1 + η · 1
mt mt∑ i=1 V (zt−1; ξ i t−1)
] := ΠZ [zt−1 + η · gt−1]
zt = ΠZ [ zt−1 + η · 1
mt mt∑ i=1 V (ẑt; ξ̂ i t−1)
] := ΠZ [zt−1 + η · ĝt−1]
Before we start our proof, we introduce two simple properties of the projection operation ΠZ as follows, where Z ⊆ Rd is closed and convex.

heading: Lemma D.1.
text: (1) ‖x − ΠZ(x)‖2 + ‖ΠZ(x) − z‖2 > ‖x − z‖2 and 〈ΠZ(x) − x,ΠZ(x) − z〉 6 0 holds for ∀x ∈ Rd, z ∈ Z . Actually, the first inequality is a simple extension of the second one. (2) The projection operator ΠZ is a compression, which means for ∀x, y ∈ Rd, it holds that:
‖ΠZ(x)−ΠZ(y)‖2 6 ‖x− y‖2.
Now, we can start our formal proof.

heading: Lemma D.2.
text: ‖zk − z∗‖2 6 ‖zk−1 − z∗‖2 − (1− 6η2L2) · ‖zk−1 − ẑk‖2 − ‖zk − ẑk‖2
+ 6η2(‖εk−1‖2 + ‖ε̂k−1‖2) + 2〈ẑk − z∗, η · ε̂k−1〉. Here, εk−1 = 1mk ∑mk i=1 V (zk−1; ξ i k−1)− V (zk−1) and ε̂k−1 = 1mk ∑mk i=1 V (ẑk; ξ̂ i k)− V (ẑk).
Proof of Lemma D.2. According to the Property (1) of Lemma D.1, we know that: ‖zk − z∗‖2 = ‖ΠZ [zk−1 + η · ĝk−1]− z∗‖2 6 ‖zk−1 + η · ĝk−1 − z∗‖2 − ‖zk−1 + η · ĝk−1 − zk‖2
= ‖zk−1 − z∗‖2 − ‖zk−1 − zk‖2 + 2〈η · ĝk−1, zk − z∗〉 = ‖zk−1 − z∗‖2 − ‖zk−1 − ẑk + ẑk − zk‖2 + 2〈η · ĝk−1, ẑk − z∗〉+ 2〈η · ĝk−1, zk − ẑk〉 = ‖zk−1 − z∗‖2 − ‖zk−1 − ẑk‖2 − ‖ẑk − zk‖2 − 2〈zk−1 − ẑk, ẑk − zk〉
+ 2〈η · (V (ẑk) + ε̂k−1), ẑk − z∗〉+ 2〈η · ĝk−1, zk − ẑk〉 = ‖zk−1 − z∗‖2 − ‖zk−1 − ẑk‖2 − ‖ẑk − zk‖2 + 2〈ẑk − zk, ẑk − zk−1 − η · ĝk−1〉
+ 2〈η · V (ẑk), ẑk − z∗〉+ 2〈η · ε̂k−1, ẑk − z∗〉 Since z∗ is a solution of MVI inequality, we know that for ∀z ∈ Z , it holds that 〈V (z), z − z∗〉 6 0,. Therefore: 〈V (ẑk), ẑk − z∗〉 6 0. Also, since ẑk = ΠZ [zk−1 + η · gk−1], according to the property (1) of Lemma D.1, we have: 〈ẑk − zk, ẑk − (zk−1 + η · gk−1)〉 6 0. After combining all the three inequalities above, we have: ‖zk − z∗‖2 6 ‖zk−1 − z∗‖2 − ‖zk−1 − ẑk‖2 − ‖ẑk − zk‖2 + 2〈η · ε̂k−1, ẑk − z∗〉
+ 2〈ẑk − zk, ẑk − zk−1 − η · gk−1 + η · gk−1 − η · ĝk−1〉 6 ‖zk−1 − z∗‖2 − ‖zk−1 − ẑk‖2 − ‖ẑk − zk‖2 + 2〈η · ε̂k−1, ẑk − z∗〉
+ 2〈ẑk − zk, η · gk−1 − η · ĝk−1〉 (a) 6 ‖zk−1 − z∗‖2 − ‖zk−1 − ẑk‖2 − ‖ẑk − zk‖2 + 2η‖ẑk − zk‖ · ‖gk−1 − ĝk−1‖ + 2〈η · ε̂k−1, ẑk − z∗〉
(b) 6 ‖zk−1 − z∗‖2 − ‖zk−1 − ẑk‖2 − ‖ẑk − zk‖2 + 2η2‖gk−1 − ĝk−1‖2
+ 2〈η · ε̂k−1, ẑk − z∗〉 (14) Here, (a) holds by Cauchy-Schwarz inequality, and (b) holds because by using the property (2) of Lemma D.1, we know that ‖ẑk − zk‖ = ‖ΠZ [zk−1 + η · gk−1]−ΠZ [zk−1 + η · ĝk−1]‖ 6 ‖(zk−1 + η · gk−1)− (zk−1 + η · ĝk−1)‖
= η · ‖gk−1 − ĝk−1‖. Now, we focus on dealing with ‖gk−1 − ĝk−1‖. In fact:
‖gk−1 − ĝk−1‖2 (c) = ‖V (zk−1)− V (ẑk) + εk−1 − ε̂k−1‖2
(d) 6 3 ( ‖V (zk−1)− V (ẑk)‖2 + ‖εk−1‖2 + ‖ε̂k−1‖2 ) (e) 6 3L2‖zk−1 − ẑk‖2 + 3(‖εk−1‖2 + ‖ε̂k−1‖2)
(15)
Here, (c) holds by the definition of εk−1, ε̂k−1. (d) holds because by Cauchy Inequality, ‖x + y + z‖2 6 3(‖x‖2 + ‖y‖2 + ‖z‖2) always holds. (e) holds because we’ve assumed that V (z) is L-Lipschitz continuous under ‖ · ‖2 norm. Combine Equation (14) and (15), we obtain that: ‖zk − z∗‖2 6 ‖zk−1 − z∗‖2 − (1− 6η2L2)‖zk−1 − ẑk‖2 − ‖ẑk − zk‖2 + 6η2 · (‖εk−1‖2 + ‖ε̂k−1‖2) + 2〈η · ε̂k−1, ẑk − z∗〉, which is exactly what we want to prove in this lemma.
Now, we come back to our Theorem D.1. Notice that rη(zk) 2 = ‖zk −ΠZ [zk + η · V (zk)]‖2 = ‖zk − ẑk+1 + ẑk+1 −ΠZ [zk + η · V (zk)]‖2
(a) 6 2 ( ‖zk − ẑk+1‖2 + ‖ẑk+1 −ΠZ [zk + η · V (zk)]‖2 ) = 2 ( ‖zk − ẑk+1‖2 + ‖ΠZ [zk + η · gk]−ΠZ [zk + η · V (zk)]‖2
) (b) 6 2‖zk − ẑk+1‖2 + 2η2 · ‖εk‖2
(16)
Here, (a) comes from Cauchy Inequality and (b) holds because of the property (2) of Lemma D.1.
Proof of Theorem D.1. Put k = 1, 2, . . . , N in Lemma D.2 and add them up, and we obtain that:
‖zN − z∗‖2 6 ‖z0 − z∗‖2 − (1− 6η2L2) · N−1∑ k=0 ‖zk − ẑk+1‖2 − N∑ k=1 ‖zk − ẑk‖2
+ 6η2 · N−1∑ k=0 ( ‖εk‖2 + ‖ε̂k‖2 ) + 2 N∑ k=1 〈ẑk − z∗, η · ε̂k−1〉.
Therefore, after combining with Equation (16), we have: N−1∑ k=0 rη(zk) 2 6 2 N−1∑ k=0 ‖zk − ẑk+1‖2 + 2η2 · N−1∑ k=0 ‖εk‖2
6 2
1− 6η2L2
( ‖z0 − z∗‖2 + 6η2 ·
N−1∑ k=0 ( ‖εk‖2 + ‖ε̂k‖2 ) + 2 N∑ k=1 〈ẑk − z∗, η · ε̂k−1〉
)
+ 2η2 · N−1∑ k=0 ‖εk‖2
Since η 6 14L , we have 1− 6η 2L2 > 12 . After taking expectation on the inequality above, it holds that: 1
N N−1∑ k=0 E[rη(zk)2] 6 4‖z0 − z∗‖2 N + 48η2 N N−1∑ k=0 σ2 mk + 2η2 N N−1∑ k=0 σ2 mk
= 4‖z0 − z∗‖2
N +
50η2
N N−1∑ k=0 σ2 mk
which comes to our conclusion. Here, we use the fact that E‖εk‖2 6 σ 2 mk ,E‖ε̂k‖2 6 σ 2 mk and E〈ẑk − z∗, η · ε̂k−1〉 = 0.

heading: D.2 PROOF OF THEOREM D.2
text: We recall that in the t-th iteration of Adaptive Extra-Gradient, our update is as follows: ẑt = zt−1 + η ·H−1t−1gt−1 zt = zt−1 + η · S−1t−1ĝt. Now we begin our proof by introducing several lemmas.

heading: Lemma D.3.
text: ‖zk − z∗‖2sk−1 6 ‖zk−1 − z ∗‖2sk−1 − ‖zk−1 − ẑk‖ 2 sk−1 + ‖zk − ẑk‖2sk−1 + 2〈η · ε̂k, ẑk − z ∗〉.
Here, ε̂k = ĝk − V (ẑk) = 1m ∑m i=1 V (ẑk; ξ̂i)− V (ẑk).
Proof of Lemma D.3. According to our update rule, we know that: ‖zk − z∗‖2Sk−1 = ‖zk−1 + η · S −1 k−1ĝk − z
∗‖2Sk−1 = ‖zk−1 + η · S−1k−1ĝk − z ∗‖2Sk−1 − ‖zk−1 + η · S −1 k−1ĝk − zk‖ 2 Sk−1 = ‖zk−1 − z∗‖2Sk−1 − ‖zk−1 − zk‖ 2 Sk−1
+ 2〈η · ĝk, zk − z∗〉 = ‖zk−1 − z∗‖2Sk−1 − ‖zk−1 − ẑk + ẑk − zk‖ 2 Sk−1
+ 2〈η · ĝk, zk − ẑk〉+ 2〈η · ĝk, ẑk − z∗〉 = ‖zk−1 − z∗‖2Sk−1 − ‖zk−1 − ẑk‖ 2 Sk−1
− ‖ẑk − zk‖2Sk−1 − 2〈Sk−1(zk−1 − ẑk), ẑk − zk〉 + 2〈η · ĝk, zk − ẑk〉+ 2〈η · ĝk, ẑk − z∗〉
= ‖zk−1 − z∗‖2Sk−1 − ‖zk−1 − ẑk‖ 2 Sk−1 − ‖ẑk − zk‖2Sk−1 + 2〈η · ĝk, ẑk − z ∗〉
+ 2〈zk − ẑk, Sk−1(zk−1 − ẑk + η · S−1k−1ĝk)〉 = ‖zk−1 − z∗‖2Sk−1 − ‖zk−1 − ẑk‖ 2 Sk−1 − ‖ẑk − zk‖2Sk−1 + 2〈η · ĝk, ẑk − z ∗〉
+ 2〈zk − ẑk, Sk−1(zk − ẑk)〉 = ‖zk−1 − z∗‖2Sk−1 − ‖zk−1 − ẑk‖ 2 Sk−1 + ‖ẑk − zk‖2Sk−1 + 2〈η · ĝk, ẑk − z ∗〉
Notice that ĝk = V (ẑk) + ε̂k. Since z∗ is a solution of MVI which means 〈V (z), z − z∗〉 6 0 holds for ∀z ∈ Z , so 〈V (ẑk), ẑk − z∗〉 6 0. Therefore:
〈η · ĝk, ẑk − z∗〉 = 〈η · (V (ẑk) + ε̂k), ẑk − z∗〉 6 〈η · ε̂k, ẑk − z∗〉.
Combine it with the inequality above, we obtain that:
‖zk − z∗‖2Sk−1 6 ‖zk−1 − z ∗‖2Sk−1 − ‖zk−1 − ẑk‖ 2 Sk−1 + ‖ẑk − zk‖2Sk−1 + 2〈η · ε̂k, ẑk − z ∗〉,
which comes to our conclusion.
In the lemma above, it’s worth mentioned that the expectation of 〈η · ε̂k, ẑk − z∗〉 is 0. In the next lemma, we are going to deal with the upper bound of ‖ẑk − zk‖2Sk−1 . Before that, we notice the following fact:
H0 S0 H1 S1 . . . HN SN .

heading: Lemma D.4.
text: ‖zk − ẑk‖2Sk−1 6 6η2L2
δ2 ‖zk−1 − ẑk‖2Sk−1 + 6η 2 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 2η2 · ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1
Proof of Lemma D.4. Since ẑk = zk−1 + η ·H−1k−1gk−1 and zk = zk−1 + η · S −1 k−1ĝk, we have:
‖zk − ẑk‖2Sk−1 = η 2 · ‖S−1k−1ĝk −H −1 k−1gk−1‖ 2 Sk−1 = η2 · ‖S−1k−1ĝk − S −1 k−1gk−1 + S −1 k−1gk−1 −H −1 k−1gk−1‖ 2 Sk−1
(a) 6 2η2 · ( ‖S−1k−1(ĝk − gk−1)‖ 2 Sk−1 + ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1 ) = 2η2 · ( ‖ĝk − gk−1‖2S−1k−1 + ‖(S −1 k−1 −H −1 k−1)gk−1‖ 2 Sk−1
) = 2η2 · ‖V (ẑk)− V (zk−1) + ε̂k−1 − εk−1‖2S−1k−1 + 2η 2 · ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1
(b) 6 6η2 · ( ‖V (ẑk)− V (zk−1)‖2S−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 + ‖εk−1‖2S−1k−1 ) + 2η2 · ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1
(c) 6 6η2 · ( L2
δ2 ‖ẑk − zk−1‖2Sk−1 + ‖ε̂k−1‖ 2 S−1k−1 + ‖εk−1‖2H−1k−1 ) + 2η2 · ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1 ,
which comes to our conclusion. Here, (a) holds since for any norm ‖ · ‖A, we have ‖x + y‖2A 6 (‖x‖A + ‖y‖A)2 6 2(‖x‖2A + ‖y‖2A), and (b) holds for the similar reason. (c) holds because of the following two reasons: (1) Since V is L-Lipschitz continuous, and δI Sk−1, we have:
‖V (ẑk)− V (zk−1)‖2S−1k−1 6 1 δ ‖V (ẑk)− V (zk−1)‖22 6
L2
δ ‖ẑk − zk−1‖2 6
L2 δ2 ‖ẑk − zk−1‖2Sk−1 .
(2) Since Hk−1 Sk−1, we have S−1k−1 H −1 k−1. Therefore,
‖εk−1‖2S−1k−1 6 ‖εk−1‖ 2 H−1k−1 .
Since η 6 δ4L , then 6η2L2 δ2 6 1 2 . According to Lemma D.3 and Lemma D.4, we have:
‖zk − z∗‖2Sk−1 6 ‖zk−1 − z ∗‖2Sk−1 − ‖zk−1 − ẑk‖ 2 Sk−1 + 2〈η · ε̂k−1, ẑk − z∗〉+ 1
2 ‖zk−1 − ẑk‖2Sk−1 + 6η2 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 2η2 · ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1
which means:
1 2 ‖zk−1 − ẑk‖2Sk−1 6 ‖zk−1 − z ∗‖2Sk−1 − ‖zk − z ∗‖2Sk−1 + 2〈η · ε̂k−1, ẑk − z ∗〉
+ 6η2 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 2η2 · ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1
(17) Notice that, ‖zk−1 − ẑk‖2Sk−1 = ‖η ·H −1 k−1gk−1‖2Sk−1 . Therefore,
‖gk−1‖2S−1k−1 = ‖S −1 k−1gk−1‖ 2 Sk−1 = ‖H−1k−1gk−1 + (S −1 k−1 −H −1 k−1)gk−1‖ 2 Sk−1 6 2 ( ‖H−1k−1gk−1‖ 2 Sk−1 + ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1 ) = 2
η2 · ‖zk−1 − ẑk‖2Sk−1 + 2 · ‖(S −1 k−1 −H −1 k−1)gk−1‖ 2 Sk−1
(18)
Combine Equation (17) and (18), we obtain that:
‖gk−1‖2S−1k−1 6 4 η2 · (‖zk−1 − z∗‖2Sk−1 − ‖zk − z ∗‖2Sk−1) + 8 η 〈ε̂k−1, ẑk − z∗〉
+ 24 · ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 10 · ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1 (19)
In the inequality above, the expectation of 〈ε̂k−1, ẑk−z∗〉 is 0, which can be ignored under expectation. Since we are going to do the summation over k = 1, 2, . . . , N in the future, in the following lemmas, we analyze the upper bounds of ∑N k=1(‖zk−1 − z∗‖2Sk−1 − ‖zk − z ∗‖2Sk−1), ∑N k=1 ‖(S −1 k−1 −
H−1k−1)gk−1‖2Sk−1 , and ∑N k=1(‖εk−1‖2H−1k−1 + ‖ε̂k−1‖2S−1k−1 )

heading: Lemma D.5.
text: N∑ k=1 ( ‖zk−1 − z∗‖2Sk−1 − ‖zk − z ∗‖2Sk−1 ) 6 2dD2δ ·Nα.
Proof of Lemma D.5. Notice that
N∑ k=1 ( ‖zk−1 − z∗‖2Sk−1 − ‖zk − z ∗‖2Sk−1 ) 6 ‖z0 − z∗‖2S0 + N−1∑ k=1 ( ‖zk − z∗‖2Sk − ‖zk − z ∗‖2Sk−1 )
= ‖z0 − z∗‖2S0 + N−1∑ k=1 [ (zk − z∗)>(Sk − Sk−1) · (zk − z∗) ] 6 D2 · tr(S0) +
N−1∑ k=1 D2 · (tr(Sk)− tr(Sk−1)) = D2 · tr(SN−1) < D2 · 2dδNα,
which comes to our conclusion.
Lemma D.6. N∑ k=1 ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1 6 2dG2 ·Nα δ .
Proof of Lemma D.6. For any δ 6 x < y, we notice that:
y
( 1
x − 1 y
)2 = (y − x)2
x2y < y − x x2 6 y − x δ2 . (20)
Therefore, we have:
N∑ k=1 ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1 6 N∑ k=1 g>k−1(H −1 k−1 − S −1 k−1)Sk−1(H −1 k−1 − S −1 k−1)gk−1
6 N∑ k=1 G2 · tr ( (H−1k−1 − S −1 k−1)Sk−1(H −1 k−1 − S −1 k−1) ) (a)
6 N∑ k=1 G2 δ2 · [tr(Sk−1)− tr(Hk−1)]
6 G2
δ2 · tr(SN−1) <
G2
δ2 · 2dδ ·Nα = 2dG
2 ·Nα δ .
Here, (a) holds because of Equation (20).

heading: Lemma D.7.
text: E N∑ k=1 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) 6 δσ2 m + 4dδ ·Nα.
The proof of this lemma can be found in (Duchi et al., 2011). Combine Lemma D.5, D.6, D.7 with Equation (19), we obtain that:
E N∑ k=1 ‖gk−1‖2S−1k−1 6 4 η2 · 2dD2δNα + 24 · ( δσ2 m + 4dδ ·Nα ) + 10 · 2dG 2 ·Nα δ .
Now, we replace the gk−1 with the true gradient V (zk−1) as follows:
E N∑ k=1 ‖V (zk−1)‖2H−1k−1 = E N∑ k=1 ‖gk−1 + εk−1‖2H−1k−1 6 2 · E N∑ k=1 ‖gk−1‖2H−1k−1 + 2 · E N∑ k=1 ‖εk−1‖2H−1k−1
(a) 6 2 · E N∑ k=1 [ ‖gk−1‖2S−1k−1 + g > k−1(H −1 k−1 − S −1 k−1) · gk−1 ] + 2 · ( δσ2 m + 4dδ ·Nα )
6 2 · E N∑ k=1 ‖gk−1‖2S−1k−1 + 2 · ( δσ2 m + 4dδ ·Nα ) + 2G2 · N∑ k=1 [ tr(H−1k−1)− tr(S −1 k−1) ] 6 8
η2 · 2dD2δNα + 50 ·
( δσ2
m + 4dδ ·Nα
) + 20 · 2dG 2 ·Nα
δ + 2G2 · tr(H−10 )
= 8
η2 · 2dD2δNα + 50 ·
( δσ2
m + 4dδ ·Nα
) + 20 · 2dG 2 ·Nα
δ +
2G2d
δ .
Here, (a) uses the conclusion of Lemma D.7. Finally, we multiplies 1N on both sides and finish the proof:
1 N E N−1∑ k=0 ‖V (zk)‖2H−1k 6 16dD2δ/η2 + 200dδ + 40dG2/δ N1−α + 50δσ2/m+ 2G2d/δ N .

heading: D.3 PROOF OF THEOREM D.3
text: In this proof, we are still using the Adaptive Extra-Gradient (AEG) algorithm, which its t-th iteration is:
ẑt = zt−1 + η ·H−1t−1gt−1 zt = zt−1 + η · S−1t−1ĝt.
For simplicity, we split the update of x variable and y variable. Recall that Hk = Diag(Ak, Bk) and Sk = Diag(Ck, Dk) where for each k ∈ N, Ak, Ck ∈ Rn1×n1 and Bk, Dk ∈ Rn2×n2 . Also, we
denote gk = (gxk , g y k) and ĝk = (ĝ x k , ĝ y k) where g x k , ĝ x k ∈ Rn1 and g y k , ĝ y k ∈ Rn2 . Then, the update above can be rewritten as: x̂t = xt−1 + η ·A−1t−1gxt−1 ŷt = yt−1 + η
t ·B−1t−1g y t−1
xt = xt−1 + η · C−1t−1ĝxt yt = yt−1 + η
t ·D−1t−1ĝ y t .
Similar to Lemma D.3, we only focus on the x-s, and then we can get our upper bound for ‖xk − x∗‖2Ck−1 , which is the first step of our proof.

heading: Lemma D.8.
text: ‖xk −x∗‖2Ck−1 6 ‖xk−1−x ∗‖2Ck−1 −‖xk−1− x̂k‖ 2 Ck−1 + ‖xk − x̂k‖2Ck−1 + 2〈η · ε̂ x k−1, x̂k −x∗〉.
Proof of Lemma D.8. According to the update rule of xk, x̂k, we know that:
‖xk − x∗‖2Ck−1 = ‖xk−1 + η · C −1 k−1ĝ x k − x∗‖2Ck−1
= ‖xk−1 + η · C−1k−1ĝ x k − x∗‖2Ck−1 − ‖xk−1 + η · C −1 k−1ĝ x k − xk‖2Ck−1 = ‖xk−1 − x∗‖2Ck−1 − ‖xk−1 − xk‖ 2 Ck−1
+ 2〈η · ĝxk , xk − x∗〉 = ‖xk−1 − x∗‖2Ck−1 − ‖xk−1 − x̂k + x̂k − xk‖ 2 Ck−1
+ 2〈η · ĝxk , xk − x̂k〉+ 2〈η · ĝxk , x̂k − x∗〉 = ‖xk−1 − x∗‖2Ck−1 − ‖xk−1 − x̂k‖ 2 Ck−1
− ‖x̂k − xk‖2Ck−1 − 2〈Ck−1(xk−1 − x̂k), x̂k − xk〉 + 2〈η · ĝxk , xk − x̂k〉+ 2〈η · ĝxk , x̂k − x∗〉
= ‖xk−1 − x∗‖2Ck−1 − ‖xk−1 − x̂k‖ 2 Ck−1 − ‖x̂k − xk‖2Ck−1 + 2〈η · ĝ x k , x̂k − x∗〉
+ 2〈xk − x̂k, Ck−1(xk−1 − x̂k + η · C−1k−1ĝ x k)〉
= ‖xk−1 − x∗‖2Ck−1 − ‖xk−1 − x̂k‖ 2 Ck−1 − ‖x̂k − xk‖2Ck−1 + 2〈η · ĝ x k , x̂k − x∗〉
+ 2〈xk − x̂k, Ck−1(xk − x̂k)〉 = ‖xk−1 − x∗‖2Ck−1 − ‖xk−1 − x̂k‖ 2 Ck−1 + ‖x̂k − xk‖2Ck−1 + 2〈η · ĝ x k , x̂k − x∗〉
Notice that ĝk = V (ẑk) + ε̂k−1 ⇒ ĝxk = Vx(ẑk) + ε̂xk−1. Since z∗ satisfies the one-side MVI condition, therefore 〈Vx(z), x − x∗〉 6 0 holds for ∀z = (x, y) ∈ Z , so 〈Vx(ẑk), x̂k − x∗〉 6 0. Therefore:
〈η · ĝxk , x̂k − x∗〉 = 〈η · (Vx(ẑk) + ε̂xk−1), x̂k − x∗〉 6 〈η · ε̂xk−1, x̂k − x∗〉.
Combine it with the inequality above, we obtain that:
‖xk −x∗‖2Ck−1 6 ‖xk−1−x ∗‖2Ck−1 −‖xk−1− x̂k‖ 2 Ck−1 + ‖x̂k −xk‖2Ck−1 + 2〈η · ε̂ x k−1, x̂k −x∗〉,
which comes to our conclusion.
Notice that the term 2〈η ·ε̂xk−1, x̂k−x∗〉 has zero mean, which can be ignored when taking expectation. In the next step, we upper bound the ‖x̂k − xk‖2Ck−1 term. Also, we notice the following facts:
A0 C0 A1 C1 . . . AN CN , B0 D0 B1 D1 . . . BN DN .

heading: Lemma D.9.
text: ‖xk − x̂k‖2Ck−1 6 6η2L2
δ2
( ‖xk−1 − x̂k‖2Ck−1 + ‖yk−1 − ŷk‖ 2 Dk−1 ) + 6η2 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 2η2 · ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1
Proof of Lemma D.9. Since x̂k = xk−1 + η ·A−1k−1gxk−1 and xk = xk−1 + η · C −1 k−1ĝ x k , we have:
‖xk − x̂k‖2Ck−1 = η 2 · ‖C−1k−1ĝ x k −A−1k−1g x k−1‖2Ck−1 = η 2 · ‖C−1k−1ĝ x k − C−1k−1g x k−1 + C −1 k−1g x k−1 −A−1k−1g x k−1‖2Ck−1
(a) 6 2η2 · ( ‖C−1k−1(ĝ x k − gxk−1)‖2Ck−1 + ‖(C −1 k−1 −A −1 k−1)g x k−1‖2Ck−1 ) = 2η2 · ( ‖ĝxk − gxk−1‖2C−1k−1 + ‖(C −1 k−1 −A −1 k−1)g x k−1‖2Ck−1
) (b)
6 2η2 · ( ‖ĝk − gk−1‖2S−1k−1 + ‖(C −1 k−1 −A −1 k−1)g x k−1‖2Ck−1 ) = 2η2 · ‖V (ẑk)− V (zk−1) + ε̂k−1 − εk−1‖2S−1k−1 + 2η 2 · ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1
(c) 6 6η2 · ( ‖V (ẑk)− V (zk−1)‖2S−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 + ‖εk−1‖2S−1k−1 ) + 2η2 · ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1
(d) 6 6η2 · ( L2
δ2 ‖ẑk − zk−1‖2Sk−1 + ‖ε̂k−1‖ 2 S−1k−1 + ‖εk−1‖2H−1k−1 ) + 2η2 · ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1
(e) = 6η2 ·
( L2
δ2 ‖x̂k − xk−1‖2Ck−1 +
L2 δ2 ‖ŷk − yk−1‖2Dk−1 + ‖ε̂k−1‖ 2 S−1k−1 + ‖εk−1‖2H−1k−1 ) + 2η2 · ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1
(21)
which comes to our conclusion. Here, (a) holds since for any norm ‖ · ‖A, we have ‖x + y‖2A 6 (‖x‖A + ‖y‖A)2 6 2(‖x‖2A + ‖y‖2A), and (c) holds for the similar reason. (b) holds because ‖ĝk − gk−1‖2S−1k−1 = ‖ĝxk − gxk−1‖2C−1k−1 + ‖ĝyk − g y k−1‖2D−1k−1 > ‖ĝxk − gxk−1‖2C−1k−1 , and (e) holds for the same reason. (d) holds because of the following two reasons: (1) Since V is L-Lipschitz continuous, and δI Sk−1, we have:
‖V (ẑk)− V (zk−1)‖2S−1k−1 6 1 δ ‖V (ẑk)− V (zk−1)‖22 6
L2
δ ‖ẑk − zk−1‖2 6
L2 δ2 ‖ẑk − zk−1‖2Sk−1 .
(2) Since Hk−1 Sk−1, we have S−1k−1 H −1 k−1. Therefore,
‖εk−1‖2S−1k−1 6 ‖εk−1‖ 2 H−1k−1 .
Since we require our learning rate η 6 δ4L , the coefficient above 6η2L2 δ2 < 1 2 . After combining Lemma D.8 and Lemma D.9, we obtain that:
‖xk − x∗‖2Ck−1 6 ‖xk−1 − x ∗‖2Ck−1 −
1 2 ‖xk−1 − x̂k‖2Ck−1 + 1 2 ‖yk−1 − ŷk‖2Dk−1 + 2〈η · ε̂ x k−1, x̂k − x∗〉
+ 6η2 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 2η2 · ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1 ,
(22) which means: 1 2 ‖xk−1 − x̂k‖2Ck−1 6 ‖xk−1 − x ∗‖2Ck−1 − ‖xk − x ∗‖2Ck−1 + 1 2 ‖yk−1 − ŷk‖2Dk−1 + 2〈η · ε̂ x k−1, x̂k − x∗〉
+ 6η2 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 2η2 · ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1 ,
(23)
Notice that, ‖xk−1 − x̂k‖2Ck−1 = ‖η ·A −1 k−1g x k−1‖2Ck−1 . Therefore,
‖gxk−1‖2C−1k−1 = ‖C −1 k−1g x k−1‖2Ck−1 = ‖A −1 k−1g x k−1 + (C −1 k−1 −A −1 k−1)g x k−1‖2Ck−1 6 2 ( ‖A−1k−1g x k−1‖2Ck−1 + ‖(C −1 k−1 −A −1 k−1)g x k−1‖2Ck−1 ) = 2
η2 · ‖xk−1 − x̂k‖2Ck−1 + 2 · ‖(C −1 k−1 −A −1 k−1)g x k−1‖2Ck−1 .
(24)
Combining Equation (23) and Equation (24), we get:
‖gxk−1‖2C−1k−1 6 4 η2 ( ‖xk−1 − x∗‖2Ck−1 − ‖xk − x ∗‖2Ck−1 ) + 2 η2 ‖yk−1 − ŷk‖2Dk−1 + 8 η2 〈η · ε̂xk−1, x̂k − x∗〉
+ 24 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 10 · ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1 ,
(25) Then, we take summation over k = 1, 2, . . . , N and take expectation, and we can obtain that: E N∑ k=1 ‖gxk−1‖2C−1k−1 6 4 η2 E N∑ k=1 ( ‖xk−1 − x∗‖2Ck−1 − ‖xk − x ∗‖2Ck−1 ) + 2 η2 E N∑ k=1 ‖yk−1 − ŷk‖2Dk−1
+ 24 · E N∑ k=1 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) + 10 · E N∑ k=1 ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1 .
(26) In the following steps, we will upper bound the four terms above on the right side. The third term
E ∑N k=1 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖2S−1k−1 ) can be upper bounded by using Lemma D.7:
E N∑ k=1 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) 6 δσ2 m + 4dδ ·Nα. (27)
The fourth term E ∑N k=1 ‖(C −1 k−1 −A −1 k−1)g x k−1‖2Ck−1 can be upper bounded by using Lemma D.6:
E N∑ k=1 ‖(C−1k−1 −A −1 k−1)g x k−1‖2Ck−1 6 E N∑ k=1 ‖(S−1k−1 −H −1 k−1)gk−1‖ 2 Sk−1 6 2dG2 ·Nα δ .
For the first term E ∑N k=1 ( ‖xk−1 − x∗‖2Ck−1 − ‖xk − x ∗‖2Ck−1 )
, we can use the similar techniques as Lemma D.5.

heading: Lemma D.10.
text: N∑ k=1 ( ‖xk−1 − x∗‖2Ck−1 − ‖xk − x ∗‖2Ck−1 ) 6 2dD2δ ·Nα.
Proof of Lemma D.10. Notice that N∑ k=1 ( ‖xk−1 − x∗‖2Ck−1 − ‖xk − x ∗‖2Ck−1 ) 6 ‖x0 − x∗‖2C0 + N−1∑ k=1 ( ‖xk − x∗‖2Ck − ‖xk − x ∗‖2Ck−1 )
= ‖x0 − x∗‖2C0 + N−1∑ k=1 [ (xk − x∗)>(Ck − Ck−1) · (xk − x∗) ] 6 D2 · tr(C0) +
N−1∑ k=1 D2 · (tr(Ck)− tr(Ck−1)) = D2 · tr(CN−1) < D2 · tr(SN−1) 6 D2 · 2dδNα,
which comes to our conclusion. For the second term E ∑N k=1 ‖yk−1 − ŷk‖2Dk−1 , notice that:
N∑ k=1 ‖yk−1 − ŷk‖2Dk−1 = N∑ k=1 η2 k2 · ‖B−1k−1g y k−1‖ 2 Dk−1 = N∑ k=1 η2 k2 · gy>k−1B −1 k−1Dk−1B −1 k−1g y k−1
6 N∑ k=1 η2 k2 ·G2tr(B−1k−1Dk−1B −1 k−1) < N∑ k=1 η2 k2 G2 · 2dδk α δ2
= 2η2dG2
δ
N∑ k=1 1 k2−α
Here, we notice that:
N∑ k=1 1 k2−α < 1 + ∫ N 1 1 x2−α dx < 1 + ∫ N 1 1 x3/2 dx = 1 + 2 ( 1− 1√ N ) < 3.
Therefore: N∑ k=1 ‖yk−1 − ŷk‖2Dk−1 < 6η2dG2 δ .
According to Equation (26): E N∑ k=1 ‖gxk−1‖2C−1k−1 6 4 η2 · 2dD2δ ·Nα + 2 η2 · 6η 2dG2 δ + 24 · ( δσ2 m + 4dδ ·Nα ) + 10 · 2dG 2 ·Nα δ
= Nα · ( 8dD2δ
η2 + 96dδ +
20dG2
δ
) + 12dG2
δ +
24δσ2
m .
(28) Finally, we replace the gxk−1 above with the actual gradient Vx(zk−1). Since:
‖Vx(zk−1)‖2C−1k−1 6 ( ‖gxk−1‖C−1k−1 + ‖ε x k−1‖C−1k−1 )2 6 2 ( ‖gxk−1‖2C−1k−1 + ‖ε x k−1‖2C−1k−1 ) ,
we can upper bound the target term E ∑N k=1 ‖Vx(zk−1)‖2C−1k−1 : E N∑ k=1 ‖Vx(zk−1)‖2C−1k−1 6 E N∑ k=1 2 ( ‖gxk−1‖2C−1k−1 + ‖ε x k−1‖2C−1k−1 ) 6 2E N∑ k=1 ‖gxk−1‖2C−1k−1 + 2E N∑ k=1 ‖εxk−1‖2C−1k−1
(a) 6 Nα · ( 16dD2δ
η2 + 192dδ +
40dG2
δ
) + 24dG2
δ +
48δσ2
m + 2E N∑ k=1 ( ‖εk−1‖2H−1k−1 + ‖ε̂k−1‖ 2 S−1k−1 ) (b)
6 Nα · ( 16dD2δ
η2 + 192dδ +
40dG2
δ
) + 24dG2
δ +
48δσ2
m + 2
( δσ2
m + 4dδ ·Nα ) = Nα · ( 16dD2δ
η2 + 200dδ +
40dG2
δ
) + 24dG2
δ +
50δσ2
m ,
(29) which means that:
1
N E N∑ k=1 ‖Vx(zk−1)‖2C−1k−1 6 16dD2δ/η2 + 200dδ + 40dG2/δ N1−α + 24dG2/δ + 50δσ2/m N ,
which comes to our conclusion.

heading: E PSEUDO-ALGORITHM OF AMSGRAD-EG-DRD
text: Algorithm 5 Extra Gradient AMSGrad with Dual Rate Decay Input: The initial state z0 = m0 = v0 = 0, a constant learning rate η, a Stochastic First-order Oracle (SFO) V (z; ξ), momentum parameters β1t, β2, a sequence of batch sizes {Mk}. Output: zt with t uniformly chosen from {0, 1, . . . , N − 1}.
1: for k = 1, . . . , N do 2: (Gradient Evaluation 1) gk−1 = 1m ∑m i=1 V (zk−1; ξ i k−1). 3: (Momentum Update 1)mk = β1km̂k−1 + (1− β1k)gk−1 4: (Velocity Update 1) vk = max(β2v̂k−1 + (1− β2)g2k−1, v̂k−1), Hk = δI + Diag( √ vk). 5: (Shadow Update) x̂k = xk−1 + η · (Hxk ) −1 mxk,
ŷk = yk−1 + η√ k (Hyk ) −1 myk, ẑk = (x̂k, ŷk). 6: (Gradient Evaluation 2) ĝk = 1Mk ∑Mk i=1 V (ẑk; ξ i k). 7: (Momentum Update 2) m̂k = β1kmk + (1− β1k)ĝk. 8: (Velocity Update 2) v̂k = max(β2vk + (1− β2)ĝ2k, vk), Ĥk = δI + Diag( √ v̂k) 9: (Real Update) zk = zk−1 + η · Ĥ−1k m̂k.
10: (Real Update) xk = xk−1 + η · ( Ĥxk )−1 m̂xk,
yk = yk−1 + η√ k ( Ĥyk )−1 m̂yk, zk = (xk, yk).
11: end for

Review summaries:
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.

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.