ODE Analysis of Stochastic Gradient Methods with Optimism and Anchoring  for Minimax Problems and GANs
Authors: Ernest K. Ryu
Kun Yuan
Wotao Yin
Venue:  (2020)
Keywords: GAN
minimax problems
stochastic gradients

Abstract: Despite remarkable empirical success, the training dynamics of generative adversarial networks (GAN), which involves solving a minimax game using stochastic gradients, is still poorly understood. In this work, we analyze last-iterate convergence of simultaneous gradient descent (simGD) and its variants under the assumption of convex-concavity, guided by a continuous-time analysis with differential equations. First, we show that simGD, as is, converges with stochastic sub-gradients under strict convexity in the primal variable. Second, we generalize optimistic simGD to accommodate an optimism rate separate from the learning rate and show its convergence with full gradients. Finally, we present anchored simGD, a new method, and show convergence with stochastic subgradients.

Under review as a conference paper at ICLR 2020
ODE ANALYSIS OF STOCHASTIC GRADIENT METH- ODS WITH OPTIMISM AND ANCHORING FOR MINIMAX PROBLEMS AND GANS
Anonymous authors Paper under double-bling review
ABSTRACT
Despite remarkable empirical success, the training dynamics of generative adver- sarial networks (GAN), which involves solving minimax game using stochastic gradients, is still poorly understood. In this work, we analyze last-iterate con- vergence of simultancous gradient descent (simGD) and its variants under the assumption of convex-concavity, guided by continuous-tine ferential equations. First, we show that simGD, as is, converges with stochastic sub-graden -o-ggrdddeetts under strict convexity in the primal variable. Second, we generalize optimistic simGD to accommodate an optimism rate separate from the learning rate and show its convergence with full gradients. Finally, we present anchored simGD, a new method, and show convergence with stochastic subgradients.
analysis with dif-
INTRODUCTION
Training of generative adversarial networks (GAN) (Goodfellow et al. 2014). solving a minimax game using stochastic gradients, is known to be difficult. Despite the remarkable empirical success of GANs, further understanding the global training dynamics empirically and theoretically is consid-
ered major open problem (Goodfellow 2016 Radford al. 2016 Metz al., 2017 Meschederi
ct al.
2018
Odena 2019).
The local training dynamics of GANs understood reasonably well. Several works have analyzed convergence assuming the loss functions have linear gradients and assuming the training uses full (deterministic) gradients. Although the linear gradient assumption is reasonable for local analysis (even though the loss functions may not be continuously differentiable due to ReLU activation func- tions) such results say very little about global convergence. Although the full gradient assumption is reasonable when the learning rate is small, such results say very little about how the randomness affects the training.
This work investigates global convergence of simultaneous gradient descent (simGD) and its vari- ants for zero-sum games with convex-concave cost using using stochastic subgradients. We specifically study convergence of the last iterates opposed to the averaged iterates.
Organization. Section presents convergence of simGD with stochastic subgradients under strict convexity in the primal variable. The goal is establish a minimal sufficient condition of global convergence for simGD without modifications. Section 3 presents a generalization of optimistic simGD (Daskalakis al. 22018). which allows an optimism rate separate from the learning rate. We prove the generalized optimistic simGD using full gradients converges, and experimentally demon- strate that the optimism rate must tuned separately from the learning rate when using stochastic gradients. However, it is unclear whether optimistic simGD is theoretically compatible with stochas- tic gradients. Section 4 presents anchored simGD, new method, and presents its convergence with stochastic subgradients. Anchoring represents what we consider to be the strongest contribution of this work. The presentation and analyses of Sections 2 and aare guided by continuous time first- order ordinary differential equations (ODE). In particular, discretizations of certain regularized dynamics. Section experimentally demonstrates the benefit of optimism and anchoring for training GANs in some setups.
interpret optimism and anchoring as

---

Under review as a conference paper at ICLR 2020
Prior work. There several independent directions for improving the training of GANs such as designing better architectures, choosing good loss functions, or adding appropriate regularizers (Radford et al.] 2016 Arjovsky et al. 2017; Sonderby al. [017 Arjovsky & Bottou, 2017 Gul- rajani et al., 2017] Wei et al.) 2018) Roth et al., 2017 Mescheder et al. 2018: 2017; Miyato et al., 2018). In this work, accept these factors given and focus how train (optimize) the model effectively.
Optimism is simple modification to remedy the cycling behavior of simGD, which can occur even under the bilinear convex-concave setup (Daskalakis et al. 2018 Daskalakis & Panageas, 2019; Mertikopoulos et al., 2019 Gidel et 201 & Stokes 2019 Mokhtari al, Peng et 2019). These prior work assume the gradients are linear and use full gradients.
2018
2019
Although the recent name 'optimism' originates from use online optimization (Chiang et al. Rakhlin & Sridharan 2013a b, Syrgkanis et al., 2015), the idea dates back to Popov's work
2012
the 1980s (Popov) 1980) and has been studied independently the mathematical programming community (Malitsky & Semenov 2014
Malitsky 2015 Malitsky & Tam 2018 Malitsky 2019
Csetnek et al. 2019).
We note that there are other mechanisms similar to optimism and anchoring such as "prediction" 2018). "negative momentum" (Gidel et al.) 2019b), and "extragradient" (Korpelevich)
Yadav et al.
1976 seng
2000 Chavdarova al. 2019). In this work, focus optimism and anchoring.
Classical literature analyze convergence of the Polyak-averaged iterates (which assigns less weight to newer iterates) when solving convex-concave saddle point problems using stochastic subgradients (Bruck 1977; Nemirovski & Yudin 1978) [ Nemirovski et al., 2009] Juditsky et al. [201 Godeel Gidel et al,,
2019ab. For GANs, however, last iterates or exponentially averaged iterates (Yazıeı al. 2019)
(which assigns more weight to newer iterates) are used in practice. Therefore, the classical work with Polyak averaging do not fully explain the empirical success of GANs.
We point out that we are not the first to utilize classical techniques for analyzing the training of GANs. In particular, the stochastic approximation technique (Heusel et al. [0017] Duchi Ruan 2018), control theoretic techniques (Heusel et al. 2017); Nagarajan & Kolter (2017). ideas from
variational inequalities and monotone operator theory (Gemp Mahadevan, 2018 Gidel et al,
2019a), and continuous-time ODE analysis (Heusel et al. 2017; Csetnek et al. 2019) have been
utilized for analyzing GANs.
STOCHASTIC SIMULTANEOUS SUBGRADIENT DESCENT
Consider the cost function Rm x Ra R and the minimax game min, max,, Lxx, u). We say (I,, u.) E Rm x R" is solution to the minimax game or a saddle point of Lf
L(x,, u) L(x., u.) (z.u.).
Vz R" ue R
We assume
L is convex-concave and has saddle point. By convex-concave, we mean [2, u) convex function in x for fixed u and a concave function in for fixed æ. Define
(A0)
T, u) G(x, u) (o,-TT(z,u)) u))
where o, and 0₂ respectively denote the subdifferential with respect to x and u. For simplicity,
write 2 (x. u) Rm+ and G(z) G(æ,, u). Note that 0 G(z) if and only if is saddle point. Since L is convex-concave, the operator is monotone (Rockatellar 1970):
(g) 92)
22) 2
Vg1 E G(21), 92 G(zz), 21, 1m+*
(1)
Let g(2:w) be a stochastic subgradient oracle, i.c., Eug(z;w) E G(2) for all 2 E Rut,, where w is random variable. Consider Simultaneous Stochastic Sub-Graud Gradient Descent
2k+1
2*
ang zx: wx)
(SSSGD)
for l 0, 1, where 2n Bu+n is a starting point, ap, a1. ... positive learning rates, and Wh. ...... are IID random variables. (We read SSSGD as "triple-SGD", In this section, we provide convergence of SSSGD when T(x,, u) is strictly convex in s.
2

---

Under review as a conference paper at ICLR 2020
z
z(0)
z(b
Figure 1: =tt) with =(t) = G=)(t)). (Left) u(z zu. All points satisfy (z
so (t) 2. || does decrease and =(t) forms cycle. (Right) L(x, u) 0.2x* ru. The dashed
line denotes where G(z)² (2 2.) = 0, but it is visually clear that 2, = 0 is the only cluster point.
2.1 CONTINUOUS -IMME ILLUSTRATION
To understand the asymptotic dynamics of the stochastic discrete-time system, consider responding deterministic continuous-time system. For simplicity, assume G is single-valued and smooth. Consider
+t) = -g(),,
g(t) G(z(t))
with an initial value x00) = 2g- (We introduce g(t) for notational simplicity.) Let 2, be saddle
point, i.e., G(2+) 0. Then 2t)) does not move away from 2,:
d 1 [1((()
=11 -0(0- (2(1) z+) 00
dt 2
where used (1. However, there is mechanism forcing =(t) to converge solution. Consider the two examples Lu(x, u) = zu and Lp(x,u) = (p/2) + vu with
Go(æ, u) = 0 1
x
Gø(æ, u)
(2)
0
u
u
where x E IR and u E IR and p > 0. Note that Lo is the canonical counter example that also arises as the Dirac-GAN (Mescheder et al. 2018). See Figure
The classical KrasooskKasn invariance principle (Krasvskkij 1959: LaSalle 1960) states
(paraphrased) if 2co is cluster point of 2(t), then the dynamics starting 2oc will have constant
distance to 2.. On the left of Figure [ we can see ||=(t) 2.1 1| is constant ár
d _ [1=(t) 2, 1| 0 for all On the right of Figure we can see that although dt [l2(t) 2, 2| when 2 = (0, u)
for u * 0 (the dotted line) this U derivative is temporary as 2f) will soon move past the dotted line.
Therefore, =l) can maintain a constant constant distance to z, only if starts at 0, and is the only cluster point of (().
2.2 DISCRETE-TIME CONVERGENCE ANALYSIS
Consider the further assumptions
Σ Okk ===00 20,
Σ o x
(A1)
k=0
Euy ()((=)))) - w2) < R2]|=1
22 R2
V 22 E Rm-n
(A2)
where Wi and W2 are independent random variables and Rí and R₂ 0. These assumptions are standard in the sense that analogous assumptions are used in convex minimization to establish almost sure convergence of stochastic gradient descent.
Theorem 1. Assume (AO), (11). and (22). Furthermore, assume L(I, u) is strictly convex in x for all u. Then SSSGD converges the sense of z "$ z, where 2, is saddle point of
We can alternatively assume [x,, u) strictly concave in for all and obtain the same result.
3

---

Under review as a conference paper at ICLR 2020
The proof uses the stochastic approximation technique of (Duchi & Ruan 2018 We show that the discrete-time process converges (in an appropriate topology) to a continuous time trajectory satisfying differential inclusion and use the LaSalle -aaaal--Kaasovkkiii invariance principle to argue that cluster points are solutions.
Related prior work. Theorem 3.1 of (Mertikopoulos et al. 2019) considers the more general mirror descent setup and proves convergence under the assumption of "strict coherence", which is analogous to the stronger assumption strict convex-concavity both æ and u.
3 SIMULTANEOUS GD WITH OPTIMISM
Consider the setup where is continuously differentiable and we access full (deterministic) gradi- ents
V V.L(x, u) G(a, u) = - VaL(a,
Consider Optimistic Simultaneous Gradient Descent
2k+1 = - -
G(zk-1))
(SimGD-O)
for k 0, where 20 Rm= is a starting point, 2-1 20. 0 is learning rate, and 8 > is the optimism rate. Optimism is modification to simGD that remedies the cycling behavior; for the bilinear example Lu of (2). simGD (case 3 0) diverges while SimGD-O with appropriate / converges. In this section, we provide a continuous-time interpretation of SimGD-O as regularized dynamics and provide convergence for the deterministic setup.
3.1 CONTINUOUS-TIME ILLUSTRATION
Consider the continuous-time dynamics
(t) = aag(t) - Bg((),
g = G(z(t)).
The discretization =()) 2k+1 2ą and j({) R G(zx) - G(=+1) yields SimGD-O. We discuss
how this system arises as certain regularized dynamics and derive the convergence rate
[1((1))2 O(1/))
Regularized gradient mapping. tion of G with parameter / is
The Moreau-Yosida MMrreu
1965
Yosida 1948
regulariza-
(1= (T+
To clarify, 1 Rm++ + Rm-n is the identity mapping and (I (G) is the inverse (as a function) of 7 3G, which is well-defined by Minty's theorem (Minty) 1962). It is straightforward verify that Gz(z) = 0 if and only if G(2) small can think of G3 as an approximation that is better-behaved. Specifically, merely monotone (satisfies (I). but G3 is furthermore /-cocoercive, i.e.,
O, i.e.. G3 and G share the same equilibrium points. For
(G G3(z2)) 22) 2 B[[Ga(2)) G3(22)11
V21, 22 E 1+
(3)
Regularized dynamics. Consider the regularized dynamies
(tt) - aG aG
Reparameterize the dynamics ?(1) - -GG((((1)) with z(1) -I BG) and g(() G(z(t)) to get ((t) = z(t) 3g(t) and
at) (t(() c(t) - (C(t) - 2(t)) -ag(t).
This gives us =(() ot)( ()(()-
4

---

Under review as a conference paper at ICLR 2020
Rate of convergence. We now derive rate of convergence. Let 2, satisfy G(2.)
(and
therefore Gg(2.) = 0). Then
d
[s((]) ==12== -.) ²() -a((()) 2z)²
dt 2
S <=a
where we use cocoercivity,
This translates
(t) + 3g(() 2.11² S - a
(4)
dt 2
The quantity [+)( nonincreasing since
dt 2 [|] = ((t) g(t) = a h- h (S(t + h) (Gs(((t - Gs(((t)))
lim
B
[Ga(((t + h)) - Gs(c(t))l - 00,
lim h h
where we use cocoercivity,
3
Finally, integrating on both sides gives us
1 2.
|=((0) + (3((0) - 2,112 v -a:3 /'/ 19(8)]12 ds ds -
2 |=((t) Bg(t)
2
la(t))1 2a =0) (g(0) 2. 11
Related prior work. The use of the M regularization for the continuous time anal- ysis was inspired by Attouch et al. (Attouch et al.] [002 Attouch & Peypouquet| (209)) who first used the Moreau-Yosida regularization in continuous- interpreted Norward-backwart wwrd-forwardttypp method as a discretization of continuous time dynam- ics with the Douglas Rachford operator. Daskalakis et al. (2018) interprets optimism as augmenting "follow the regularized leader" with the (optimistic) prediction that the next gradient will be the same as the current gradient in online learning setup. |Png et al. (2019) interprets optimism as "centripetal acceleration" but does not provide formal analysis with differential equations.
dynamics and Csetnek al. (2019) who
3.2 DISCRETE-TIME CONVERGENECE ANALYSIS
The discrete-time method SimGD-O converges under the assumption
L is differentiable and V is R-Lipschitz continuous.
(A3)
Theorem 2. Assume A0 and
A3
Ifo
2,3(1 23RR), then SimGD-O converges in the
sense of
2+ 2.2
min |[
=0 3G((z) =x,1²
4 R)
Furthermore, 2 z., where 2, a saddle point of
The proof can be considered discretization of the continuous- analysis. We further discuss the similarities and differences between the continuous and discrete analyses in Section
Corollary 1. In the setup of Theorem the choice a 1/(8R) and B = 2a yields
136R²
289R²
min t=.....k
[[G(=a)]
1| + (G(G)))) - 2, 11 <
|| - z. 1|
h
Related prior work. Peng et al. (2019) show convergence of simGD-O for a + B and bilinear
L. Malitsky & Tam 2018 and Csetnek et al. (2019) show convergence of simGD-O for and convex-conent L. Theorem establishes convergence for a * and convex-concave L and
presents explicit rate.
5

---

Under review as a conference paper at ICLR 2020
10
10
||,,2.11
[| 2.i2
p=0.5
p=0.5, q=0.25
p=0.6
p=0.6, q=0.6
p=0.667
p=0.7. q=0.1
p=0.8, q=0
p=0.9, g=0.1
p=0.9
10
10a
10* Iterations
10
10 10
10
10 Iterations
10
10a
Figure 2: Plot of || 2.1 vs. iteration count for simGD-OS (left) and SSSGD-A (right) with Ok = 1/k2 and 3g = 1/k4. We use Lo of (2) and Gaussian random noise. The shaded region denotes standard error. For simGD-OS, we that neither q 0 nor q p leads convergence. Rather, must satisfy 0 < < so that the learning rate diminishes faster than the optimism rate.
3.3 DIFFICULTY WITH STOCHASTIC GRADIENTS
Training in machine learning usually relies on stochastic gradients, rather than full gradients. We can consider a stochastic variation of SimGD-O:
1 = 2k (..g(z::w))
mx: - 3x (o(zz;w)) - 9(2k-1;46-1)
(SimGD-OS)
with learning rate og and optimism rate Akk-
Figure presents experiments of SimGD-OS simple bilinear problem. The choice 8, as where 0g - does not lead to convergence. Discretizing æ(t) = -ag(t)))B8 with a diminishing step h& leads to the choice oą añę and B& B3 but this choice does not lead to convergence either. Rather, it is necessary to tune Oş and 8 separately as Theorem to obtain convergence and dynamics appear to be sensitive to the choice of ag and Bg. In particular, both ag and By must diminish and must diminish faster than Br. One explanation of this difficulty is that the finite difference approximation og (g(zx: stochastic gradients.
((kk-1:kk-1)
g(t) unreliable when using
Whether the observed convergence holds generally in the nonlinear convex- conceee setup and whether optimism is compatible with subgradients is unclear. This motivates anchoring of the fol- lowing section which is provably compatible with stochastic subgradients.
Related prior work. Gidel al. (219a) show averaged iterates of SimGI--OS converge if iterates are projected onto a compact set. Mertikopoulos et al. (2019) show almost sure convergence of SimGD-OS under strict convex-concavity (and more generally under "strict coherence"). However, such analyses do not provide compelling reason to use optimism since SimGD without optimism already converges under these setups.
SIMULTANEOUS GD WITH ANCHORING
Consider setup of Section
3
We propose Anchored Simultaneous Gradient Descent
1-P G(2x) (k + 1)
(1 (1-p)7 p)T (zo -xx)
2k41
2k
(SimGD-A)
+
for & 2 O, where 20 E mm a starting point, p E (1/2, 1), and 7 > 0 is the anchor rate. this section, we provide continuous-time illustration of SimGD-A and provide convergence for both the deterministic and stochastic setups.
4.1 CONTINUOUS-TIME ILLUSTRATION
Consider the continuous-timg time dynamics
((t) = g + (20 - 2(t)),
g(t) = G(a(t)).

---

Under review as a conference paper at ICLR 2020
fort 2 where y 2 and z00) Zu- We will derive the convergence rate
[| ((1t²).
Discretizing the continuous ODE with diminishing steps (1 p)/(k 1) leads SimGD-A.
Rate of convergence.
First note
S h/ (= h) 2(t). h)) o(t)) (E(1).
as h 0.
Using this, we have
[|((1)] (=(0).(()) 7 2(1) + 2 (=00 -((0)))))
- (E(1). 112(0111 + (x(() - 20, 2)
S - -11((011=== 7 (=(1) =0, 2).
Using y 2 1, we have
d
|((1)
+ & (x(t) - z0, 2).
di 2
Multiplying by t and integrating both sides gives us
|=(0))2 - 1112()) =zol?.
2
Reorganizing, we get
t²
20 2(f) + ?2 |=(()) - 2012 2 [1l((t) 201l
2
2
Using 7 2 L, the monotonicity inequality, and Young's 's inequality, we get
27² 27 7 (o((), =())) - (g((), 20 -xa) - 11)(1))
27
|e(1))
12 ||
=2.12
and conclude
412 1 1.
lla(t)]1 <
Interestingly, anchoring leads to faster rate 0(1/12) compared to the ((1(l) of optimism in continuous time. The discretized method, however, is not faster than (11/k). We further discuss this difference in A
Related prior work. Anchoring was inspired by Halpern's 's method (Halpern 1967 Wittmann 1992 Lieder 2017) and James- Stein estimator (Stein 1956 James & Stein 1961): ); these methods pull/shrink the iterates/estimator towards specified point
4.2 DISCRETE-TIME CONVERGENECE ANALYSIS
We now present convergence results with anchoring. Theorem 3 we use deterministic gradients, we use stochastic subgradients.
and in Theorem 4 Theorem 3. Assume A0 and
A3 Pf (1/2,1) and & 2 2, then SimGD-A converges in the
sense of
[[G(z)]] =0
k2-
The proof can be considered discretization of the continuous-time analysis. Consider the setup of Section scent
We propose Anchored Simultaneous Stochastic SubGradient De-
(1 (1-1)7
2k+1
2/
(R: + 1)P 9 (=(;)))) +
(I: + 1
(20 2x)
(SSSGD-A)
(The small 0 is introduced for the proof of Theorem See Section A for further discussion.)
7

---

Under review as a conference paper at ICLR 2020
2
9
3
7
6
0 7
1
6
Q
3
9
3
4
9
9
4
3
3
7
0
9
4
!
7
3
r
2
3
6
9
|
/
g
7
9
5
5
8
4
6
3
4
/
Figure 3: Samples of generated MNIST and CIFAR-I0 images at the end of the training periods of anchored Adam.
Frechet inception Dietance (FID)
120
Adam
Adam
Optimistic Adam
Frechet Inception Distance
40
Optimistic Adam
100
Anchored Adam
Anchored Adam
80
30
60
25
20
0
50000
100000
150000
200000
0
50000
100000
150000
200000
Iterations
Iterations
Figure 4: FID score vs. iteration on MNIST (left) and CIFAR-10 (right). Optimism rate of 3 = 1 and anchor rate of 7 was used. The MNIST setup benefits from optimism but not from anchoring, while the CIFAR-10 setup benefits from optimism but not from anchoring.
Theorem 4. Assume
A0 and
(1/2,1), (0,)/2), and 7 0. then SSSGD-A 2., where 2, is a saddle point.
A2
If
converges in the sense of 2 4
(To clarify, we do not assume is differentiable.)
Main contribution. To the best of our knowledge, Theorem 4 is the first result establishing last- iterate convergence for convex-concave cost functions using stochastic subgradients without assum- ing strict convexity or analogous assumptions.
EXPERIMENTS
In this section, we experimentally demonstrate the effectiveness of optimism and anchoring for training GANs. We train Wasserstein- GaNs (Arjovsky al. 2017) with gradient penalty (Gulrajani
et al. 2017) on the MNIST and CIFAR-10 dataset and plot the Fréchet Inception Distance (FID) (Heusel al. 2017 Lucic et al., 2018). The experiments were implemented in PyTorch (Paszke et al. (017). We combine Adam with optimism and anchoring (described precisely in Appendix G and compare against the baseline Adam optimizer (Kingma Ba 2015). The generator and discriminator architectures and the hyperparameters
described in Appendix G For optimistic and
anchored Adam, we roughly tune the optimism and anchor rates and show the curve corresponding to the best parameter choice.
Figure shows that the MNIST setup benefits from anchoring but not from optimism, while the CIFAR- 10 setup benefits from optimism but not from anchoring. We leave comparing the effects of optimism and anchoring in practical GAN training (where the cost function is not convex-come concx--)n topic of future work.
8

---

Under review as a conference paper at ICLR 2020
6 CONCLUSION
In this work, we analyzed the convergence of SSSGD, Optimistic simGD, and Anchored SSSGD. Under the assumption that the cost L is convex-coneave, Anchored SSSGD provably converges under the most general setup. Through experiments, we showed that the practical GAN training benefits from optimism and anchoring some (but not all) setups.
Generalizing these results to accommodate projections and proximal operators, analogous to pro- jected and proximal gradient methods, is an interesting direction of future work. Weight clipping (Arjovsky et al., 2017) and spectral normalization (Miyato et al. 2018) are instances where projec- tions are used in training GANs.
REFERENCES
M. Arjovsky and L. Bottou. Towards principled methods for training generative adversarial net- works. ICLR, 2017.
M. Arjovsky, S. Chintala, and L.. Bottou. Wasserstein generative adversarial networks. ICMI, 2017.
H. Attouch and J. Peypouquet. Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators. Math. Program., 174(1):311-332, 2019.
H. Attouch, A. Cabot, and P. Redont. The dynamics of clastic shocks via epigraphical regularization of a differential inclusion. Advances in Mathematical Sciences and Applications, 12(1):273306, 2002.
P. Aubin and A. Cellina. Differential Inclusions: Set- Vel-Valued Maps and Viability Theory. Springer- Verlag, 1984.
H. H. Bauschke and P. L. Combettes. Convex Analysis and Monotone Operator Theory in Hilbert Spaces. Springer- Springer-Verlag, 2nd edition, 2017.
R. E. Bruck. On the weak convergence of an ergodic iteration for the solution of variational inequali- ties for monotone operators in Hilbert space. Journal of Mathematical Analysis and Applications, 61(1)1159-164, 1977.
T. Chavdarova, G. Gidel, F. Fleuret, and S. Lacoste-Julien. Reducing noise in GAN training with variance reduced extragradient. NeurIPS, 2019.
C.-K. Chiang, T. Yang, C.-.. Lee, M. Mahdavi, C.-J. Lu, R. Jin, and S. Zhu. Online optimization with gradual variations. COLT, 2012.
E. R. Csetnek, Y. Malitsky, and M. K. Tam. Shadow Douglas-Rachie Rachford splitting for monotone inclusions. Applied Mathematics & Optimization, 2019.
C. Daskalakis and I. Panageas. The limit points of (optimistic) gradient descent in min-max opti- mization. NeurIPS, 2018.
C. Daskalakis and I. Panageas, Last-iterate convergence: Zero-sum games and constrained min-max optimization. ITCS, 2019.
C. Daskalakis, A. Ilyas, V. Syrgkanis, and H. Zeng. Training GANs with optimism. ICLR, 2018.
Damek Davis, Dmitriy Drusvyatskiy, Sham Kakade, and Jason D. Lee. Stochastic subgradient method converges on tame functions. Foundations of Computational Mathematics, 2019.
A. Dembo. Lecture notes on probability theory: Stanford statistics 310. http: / stttteb. hww.toorddedu/aadaeee
stat 310b/ http//notes.pptt pdff 2019. Accessed: 2019-05-10.
J. Duchi and F. Ruan. Stochastic methods for composite and weakly convex optimization problems.
SIAM J. Optim., 28(4):3229-322) 2018.
I. Gemp and S. Mahadevan. Global convergence to the equilibrium GANs using variational inequalities. arXiv: /800.0888803311 2018.

---

Under review as a conference paper at ICLR 2020
G. Gidel, H. Berard, G. Vignoud, P. Vincent, and S. Lacoste-Julics A variational inequality per- spective on generative adversarial networks. ICLR, 2019a.
G. Gidel, M. Pezeshki R. A. Hemmat, R. Lepriol, G. Huang, S. Lacoste-Julien, and I. Mitliagkas. Negative momentum for improved game dynamics. AISTATS, 2019b.
I. Goodfellow. Nips 2016 tutorial: Generative adversarial networks. arXiv:1701.00166 2016.
I. Goodfellow, J. Pouget-Abadie, M. Mirza, B. Xu, D. Warde-Farley, S. Ozair, A. Courville, and Y. Bengio. Generative adversarial nets. NeurIPS, 2014.
Gulrajani, F. Ahmed, M. Arjovsky, V. Dumoulin, and A. Courville. Improved training of Wasserstein GANs. NewrIPS, 2017.
B. Halpern. Fixed points of nonexpanding maps. Bull. Amer. Math. Soc., 73(6)9557-61,, 1967.
M. Heusel, H. Ramsauer, Unterthiner, B. Nessler, and S. Hochreiter. GANs trained by two time-scale update rule converge to local Nash equilibrium. NeurlPS, 2017.
W. James and C. Stein. Estimation with quadratic loss. In J. Neyman (ed.), Proc. Fourth Berkeley Symp. Math. Statist. Prob, volume I, pp. 361-379, 1961.
A. Juditsky, A. Nemirovski, and C. Tauvel. Solving variational inequalities with stochastic mirro-- prox algorithm. Stoch. Syst, 1(1):17-58, 2011.
D. Kingma and J. Ba. Adam: A method for stochastic optimization. ICLR, 2015.
G. M. Korpelevich. The extragradient method for finding saddle points and other problems. Ekonomika Mat. Metody, 12:747-756, 1976.
N. N. Krasovskii. Some Problems in the Theory of Motion Stability. Fizmatgiz, Moscow, 1959.
J. LaSalle. Some extensions of Liapunov's second method. IRE Trans. Circuit Theory, 7(4):520~ 527, 1960.
Liang and Stokes. Interaction matters: A note on non-asymptotic local convergence of genera- tive adversarial networks. AISTATS, 2019.
F. Lieder. On the convergence rate of the Halpern-iteration Optimization Online:2017-11-6336 2017.
M. Lucic, K. Kurach, M. Michalski, O. Bousquet, and S. Gelly. Are GANs created equal? large- scale study. NeurlPS, 2018.
Y. Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM J. Optim., 25(1))502-520 2015.
Y. Malitsky, Golden ratio algorithms for variational inequalities. Mathematical Programming, 2019.
Y. Malitsky and M. K. Tam. forward-backward backward splitting method for monotone inclusions without cocoercivity. vrXiv:1808.04111 2018.
Y. V. Malitsky and V. V. Semenov. An extragradient algorithm for monotone variational inequalities. Cybern. Syst. Anal., 50(2):271-277, 2014.
P. Mertikopoulos, B. Lecouat, H. Zenati, C.-S. Foo, V. Chandrasekhar, and G. Piliouras. Optimistic mirror descent saddle-point problems: Going the extra(-gradient) mile. ICLR, 2019.
L. Mescheder, S. Nowozin, and A. Geiger. The numerics of GANs. NeurIPS, 2017.
I. Mescheder, A. Geiger, and S. Nowozin. Which training methods for GANs do actually converge? ICMI., 2018.
L. Metz, B. Poole, D. Pfau, and Sohl-Dickstein. Unrolled generative adversarial networks. ICLR, 2017.
10

---

Under review as a conference paper at ICLR 2020
G. J. Minty. Monotone (nonlinear) operators in Hilbert space. Duke Math. J., 29(3):341-333 -344,, 1962.
Miyato, T. Kataoka, M. Koyama, and Y. Yoshida. Spectral normalization for generative adversar- ial networks. ICLR, 2018.
A. Mokhtari, A. Ozdaglar, and S. Pattathil. A unified analysis of extra-gradient and optimistic gradient methods for saddle point problems: Proximal point approach. arXiv:1901.0885 2019.
J. J. Moreau. Proximité et dualité dans un espace hilbertien. Bulletin de la Société Mathématique de France, 93:273-299, 1965.
E. Moulines and F. Bach. Non-asymptotic analysis of stochastic approximation algorithms for ma- chine learning. NeurIPS, 2011.
V. Nagarajan and J. Kolter. Gradient descent GAN optimization is locally stable. NeurIPS, 2017.
A. Nemirovski and D. Yudin. On Cezari's convergence of the steepest descent method for ap- proximating saddle point of convex-concave functions. Dokludy Akademii Nuuk SSSR, 239(5): 483-486, 1978.
A. Nemirovski, A. Juditsky, G. Lan, and A. Shapiro. Robust stochastic approximation approach stochastic programming. SIAM J. Optim., 19(4):157--1609, 2009.
A. Odena. Open questions about generative adversarial networks (online article). https:// 2019. Accessed: 2019-05-10.
A. Paszke, S. Gross, S. Chintala, G. Chanan, E. Yang, Z. DeVito, Z. Lin, A. Desmaison, L. Antiga, and Lerer. Automatic differentiation PyTorch. NeurlPS Autodiff Workshop, 2017.
W. Peng, Y. Dai, H. Zhang, and L. Cheng. Training GANs with centripetal acceleration. 1902.089499999 2019.
B. Polyak.
Introduction optimization. Optimization Software, 1987.
L. D. Popov. A modification of the Arow-Hurwicz method for search of saddle points. Mat. Zametki, 28(5):777-784, 1980.
A. Radford, L. Metz, and Chintala. Unsupervised representattionn learning with deep convolutional generative adversarial networks. ICLR, 2016.
A. Rakhlin and Sridharan. Online learning with predictable sequences. COLT, 2013a.
A. Rakhlin and K. Sridharan. Optimization, learning, and games with predictable sequences. NeurIPS, 2013b.
H. Robbins and D. Siegmund. A convergence theorem for non negative almost supermartingales and some applications. In Jagdish S. Rustagi (ed.), Optimizing Methods in Statistics, pp. 233- 257. Academic Press, 1971.
R. T. Rockafellar. Monotone operators associated with saddle-functions and minimax problems. In Browder (ed.), Nonlinear Functional Analysis, Part I, volume 18 of Proceedings of Symposia in Pure Mathematics, pp. 241-250. American Mathematical Society, 1970.
K. Roth, A. Lucchi, S. Nowozin, and T. Hofmann. Stabilizing training of generative adversarial networks through regularization. NewrIPS, 2017.
E. K. Ryu and S. P. Boyd. Primer on monotone operator methods. Appl. Comput. Math., 15:3-43, 2016.
C. K. Sønderby. J. Caballero, L. Theis, W. Shi, and F. Huszár. Amortised MAP inference for image super-resolution. ICLR, 2017.
C. Stein. Inadmissibility of the usual estimator for the mean of multivariate normal distribution. In
J. Neyman (ed.), Proc. Third Berkeley Symp. Math. Statist. Prob., volume 1, pp. 197-206. 1956.
11

---

Under review as a conference paper at ICLR 2020
V. Syrgkanis, A. Agarwal, H. Luo, and R. E. Schapire. Fast convergence of regularized learning in games. NeurIPS, 2015.
A. Taylor and F. Bach. Stochastic first-order methods: non-asympiotic and computer-aided analyses via potential functions. COLT, 2019.
Tseng. A modified forward- backwrd splitting method for maximal monotone mappings. SIAM J. Control Optim., 38(2):431 -46, 2000.
X. Wei, B. Gong, Z. Liu, W. Lu., and L. Wang. Improving the improved training of Wasserstein GANs: A consistency term and its dual effect. ICLR, 2018.
R. Wittmann. Approximation of fixed points of nonexpansive mappings. Arch. Math., 58(5):486- 491, 1992.
A. Yadav, S. Shah, Z. Xu, Jacobs, and T. Goldstein. Stabilizing adversarial nets with prediction methods. ICLR, 2018.
Y. YazIcı, C.-S. Foo, S. Winkler, K.-H. Yap, G. Piliouras, and V. Chandrasekhar, The unusual effectiveness averaging in GAN training. ICLR, 2019.
K. Yosida. On the differentiability and the representation of one-parameter semi-group of linear operators. J. Math. Soc. Japan, 1(1):15-21, 1948.
12

---

Under review as a conference paper at ICLR 2020
A FURTHER DISCUSSION ON THE CONVERGENCE RESULTS
Theorems and use related but different notions of convergence. Theorems and are
asymptotic (has rate) while Theorems 2 and 3 are non-asymptotic (has rate). Theorems and [] respectively show almost sure and L convergence of the iterates. Theorems 2 and 3 show
convergence of the squared gradient norm for the best and last iterates, respectively. We did not
make these choices. The choices were dictated by what we can prove based on the analysis.
The discrete-time analysis of SimGD-O of Aieeorem2bouune the squared gradient norm of the best iterate, while the continuous-tin analysis bounds the squared gradient norm of the "last iterate" (at terminal time). The discrepancy comes from the fact that while we have monotonic decrease of [I)())] in continuous-time, we have no analogous monotonicity condition on ||g]|] in discrete time. To the best of our knowledge, there no result establishing (11/k) rate on the squared gradient norm of the last iterate for SimGD-O or the related "extragradient method" |Korpelevich (976).
Theorem 3 is the first result showing a rate close to (1//k) on the last literate.
For SimGD-O and Corollary the parameter choices are almost optimal. The optimal choices that minimize the bound of Theorem are a 0.124897 R and |3 = 1.94431 they provide factor of 135.771, very small improvement over the factor 136 of Corollary [
For SimGD-A and Theorem 3 there a discrepancy in the rate between the continuous time anal- ysis ((1(t²) and the discrete time rate ((1/k²=²)) for p E (1/2, 1), which is slightly slower than calculations to obtain a discrete proof, errors accumu-
(11/k). In discretizing the continuous late and prevent the rate from being better than (1/k). This is not artifact of the proof. Simple tests on bilinear examples show divergence when < 1/2.
SSSGD-A and Theorem 4 involves the parameter e. While the proof requires & >> 0, we believe this an artifact the proof. In particular, we conjecture that Lemma 17 holds with o(s/T) rather than Oss/7 ((ssT), and, if so, is possible to establish convergence with 5
In Figure 2 it seems that that the choice & = 0 and 2/3 is optimal for SSSGD-A. While we do not have theoretical explanation for this, we point that this is not surprising as p 2/3 is known to be optimal in stochastic convex minimization (Moulines & Bach 2011 2019
Taylor & Bach
Theorems and extend to monotone operators (Ryu & Boyd 2016 Bauschke & Combettes,
2017) without any modification their proofs. In infinite dimensional setups (which of interest
in the field of monotone operators) Theorem establishes strong convergence, while many conver- gence results (including theorems@aand establish weak convergence. However, Theorem does not extend to monotone operators, as the use of the A.Salle-Krasnovsii principle is particular to convex-concave saddle functions.
B NOTATION AND PRELIMINARIES
Write ER to denote the set of nonnegative real numbers and (+-)) denote inner product, i.e., (u, v) = u" for u, U E pm++
We say A is point-to-set mapping on Rd if A maps points of gd subsets of Rdd. For notational simplicity, we write
(A(x) - A(y), x y) = {(u v. v\ A(x), E A(y)).
Using this notation, define monotonicity of with
(A(x) A(y), y) 2 Va, E TRd
where the inequality requires every member of the set to be nonnegative. We say monotone operator A is maximal if there is no other monotone operator B such that the containment
{1., u) u e A(x)) c {(x, u) B(x))
proper.
m x F
R is convex-concave then the subdifferential operator
L(x, u)
G(a, u) = ())())(
13

---

Under review as a conference paper at ICLR 2020
maximal monotone (Rockafellar 1970). By Bauschke & Combettes (2017) Proposition 20.36, ((z) is closed-convex for any E R m By Bauschke & Combettes (2017 77) Proposition 20i3, maximal monotone operators then Ils E G(ze) for k = 0, ..... and (zk: 9k) + (Z>o Isc) imply Joo E G( (In other words, the graph of G is closed.) Deñin Zer(G) {z Rd 0 G(=)). which is the set of saddle-points or cquilibrium points. When G is maximal monotone, Zer(G) is a closed convex set. Write
upper semicontinuous in the sense that if G is maximal monotone,
Pzer(G) arg min || zoll =eZer(G)
for the projection onto Zcr(G).
Write C(RR, R for the space of R -vauued continuous functions on R., For fa R4 - R=+", we say fe + f in C(T,,, (2)) ) fa + uniformly on bounded intervals, i.e., all < co, we have
lim sup (If f(t)ll 0.
1 kEjo.T]
In other words, we consider the topology of uniform convergence on compact sets.
We rely the following inequalities, which hold for any a, R any 0.
1
(a, b) ||||2
2 |0/1
(5)
||a b112 S 2
|a| + 2||b[1?.
(6)
Both inequalities are called Young's inequality. (Note, (6) follows from (5) with E = 1.)
Lemma 1 (Theorem 5.3.33 of Dembo 22119). Let [FR]KEN be increasing sequence of a- algebras. Let (m,, FR) be a martingale such that
B[[lm]||]] 00
for all k 2 0 and
- < o
then my converges almost surely to a limit.
Lemma (Robbins & Siegmund (1971). Let {Fa)Ken, be an increasing sequence of o-algebras.
Let [Vi)keN, keN, (SE).EN, {Un)REN,, and {BE)KEN, be nonnegative Fa-measurable random
quences satisfying
E [V441 Fx] (1 Ba) Sx + Us.
If
Bg < 00,
U 00
k=
km
holds almost surely, then
Ve > Voc:
S% +
almost surely, where Voo is a random limit.
Define
G(2) [2,]( G(2).
Note that 0 + G(2.) is possible even if G(2.) when L is not continuously differentiable.
Lemma 3. Under Assumptions A0 and A2 we have
EE, 1g (|
< R2 - 2.112 + R²
for some Rg and R4 0.
14

---

Under review as a conference paper at ICLR 2020
Proof. Let be saddle point, which exists by Assumption (AO). Let and w' be independent and identically distributed. Then
Bullo(2;w)] = Eullo(2:w)) E (19(( ((2))l
Eu 11g (2:w) g(2.:w') + ((
- R 2 211g - g(= 21
- 21/11= 11 22 + 2z.)(
where we use the fact that (2,;:²) G(z.) ) is zero-mean random variable, Assumption A2 and
6 The stated result holds with R2 2 and R2 2 + (2
C ANALYSIS OF THEOREM
For convenience, we restate the update, assumptions, and the theorem:
2k+1 2g (+g((xw:w)
(SSSGD)
L is convex convex-concave and has a saddle point
(A0)
Σ ak = xo,
Σ at << k=0
(A1)
En llg((1;:()))) - (22 - 18
z1l2 + R2 V2 E Rm+"
(A2)
Furthermore, assume L(x, u) is strictly convex in x for all Then SSSGD converges in the sense of 2k " where 2, is a saddle point of L.
Theorem 1
Assume A0
and A2
Differential inclusion technique. We use the differential inclusion technique of Duchi & Ruan (2188), also recently used in Davis et al. (2019). The high-level summary of the technique very simple and elegant: (i) show the discrete-time process converges to a continuous-time trajectory satisfying differential inclusion, (ii) show any solution of the differential inclusion has a desirable property, and (iii) translate the conclusion in continuous time to discrete-timg time. However, the actual execution of this technique does require careful and technical considerations.
Proof outline. For step (i), we adapt the LaSalle-Krasnovase Krasnovski principle to show that a solution of the continuous-time differential inclusion converges to saddle point. (Lemma [5) Then we carry out step (ii) showing the time-shifted interpolated discrete time process converges to a solution of the differential inclusion. (Lemma (6) Finally, step (iii), the "Continuous convergence to discrete convergence", combines these two pieces to conclude that the discrete time process converges to
saddle point. The contribution and novelty of our proof in our steps and (iii).
Preliminary definitions and results. Consider the differential inclusion
=(1)= G(z(1)
with the initial condition =0) 2g. We say z [0, oc) m= satisfies 7 if there is Lebesgue integrable Ç [0, oo) + = such that
= (t) 2u S (ss)ds ds. <(t) E G(z(()), 42
(8)
Write 2(t) = (20) and call di m+ + Rm+n the time evolution operator. In other words, di maps the initial condition of the differential inclusion to the point at time which is well defined by the following result.
Lemma 4 (Theorem 5.2.1 of Aubin & Cellina 1984)). ). If G is maximal monotone. the solution to existy and is unique. Furthermore, 1 Rm is 1-Lipschitz continuous for all > 0.
15

---

Under review as a conference paper at ICLR 2020
C.I PROOF OF THEOREM I
Lemma 5 and its proof can be considered an adaptation of the LaSalle Krasnovskii invariance prin- ciple (Krasovski 1959 LaSalle 1960) to the setup of differential inclusions. The standard result
applies to differential equations.
Lemma (TaSalle-Krasnovski)
Assume A0 Assume L(r, u) is strictly convex in for all u. If 2() satisfies 7 then =(1) + 250 as oo and 2n0 E Zer Zer(G).
Proof. Consider any 2, Zer(G), which exists by Assumption AO continuous, so is [ 2,2, and we have
Since =(t) is absolutely
d 1 x(()) - 211²² (C(t), =(t) 2.) S di
for almost all where ((-) is as defined in (8 and the inequality follows from T monotonicity of G. Therefore, [|=(t) z+11² is a nonincreasing function of t. and
lim =1))) z.
for some limit 2 0. Since z(t) is a bounded sequence, has at least one cluster point.
Let to - such that =txx) + Zoo+ i.e. Roo is cluster point of z(-). Then, || = X. Since (.(+) (with fixed t) continuous by Lemma we have
lim @stty (20) lim dz(0r, (=(0)) = (2 8-000
k0000
for s 2 0. This means (260) is also cluster point of 2(-) and
[10,(200) - za|l
for all s 2 0. Therefore
0= ds (10 -()((((((()))))) 22)
(9)
for almost all 8 2 0.
Write 220 (Ios, Moo) and let 2+ (x u4) E Zer(G). Write (z.)) = (d.(2.)). If
(2.))) +x..)r..
(G(()(Exa)) (a(z)) - 2x) >
by strict convexity, and, in light of 9 we conclude (){(2)) = x. for almost all 2 0. Then for almost all 2 0, we have
E (G(os(Zze)) @o(2o)) - - 2a)
(0.(- (x,, 0- (2oc)) )), 0% u.)
- [( 23 (2o0) + [(I,, 114)
0.
where the first inequality follows from concavity of L(x, u) in u and the second inequality follows from the fact that u, is maximizer when x, is fixed. Therefore, we have equality throughout, and L(x., u.), i.e., 6% (2 also maximizes L(r...).
L(x., o2 (2oo))
Remember that d. (2o0) is continuous function of s for all 2 0. Therefore, that (2xxx)) = and that 6% (2o0) maximizes L( for almost s 2 0 imply that the conditions hold for 0. In other words, Foo x² and maximizes I(x., 1), and therefore =oc ZerG.
Finally, since zoo is solution, [2((t) 200 converges limit as sc. Since |2((t)) Zoo O, we conclude that [|z(t) Zoc + as t cc.
The following lemma is the crux of the differential inclusion technique. It makes precise in what sense the discrete-ting process converges solution of the continuous-time differential inclusion.
16

---

Under review as a conference paper at ICLR 2020
Lemma 6 (Theorem 3.7 of Duchi & Ruan (2018)) Consider the update
2k+1
2k axelS + Ex),
So E G(zx).
Define tk -i== ag and
-- tu (#k+1 - 2kb, E [t tx+1).
Zinterp (t) = 26 +
tx+1
Define the lime-shifted process
inteep(()) = Sinterpl (T +.).
Let the following conditions hold:
(i) The iterates are bounded, i.e., sup, || 3o and supk l|sall co.
(ii) The stepsizes satisfy Assumption AI
(iii) The weighted noise sequence converges: Σk= ORER v for some E Rd.
(iv) For any increasing sequence ny such that 2nz + 200, we have
m Σ
lim dist
Saz G(zco) O.
m
Then for any sequence {Tk C RR, the sequence of functions (zinterp (.)} is relatively compact in CR+,, If Tk + 20, all cluster points of (z (-)} satisfy the differential inclusion
We verify the conditions of Lemma and make the argument that the noisy discrete time process is close to the noiseless continuous time process and the two processes converge the same limit.
Verifying conditions of Lemma Condition (i). Let 2, Zer(G). Write Fs for the o-field generated by wh. .u....., Wk-1 G(=) Bg(z;w) E G(z). Then
Write
|| | 2.
|| - 11 (0 2., (( wb)) + a (1:1:=(x3000 wkx wx)l I1
E0 | 2, Fil
S || 2. 2a (2u 2,, G(zz)) at (R3 || 22 22.12 123)
(1 + R²) 2 - -2112 22 (2k 2., G(zx)) + a Ra.
where we used Assumption (A2 and Lemma 3 Since Σ of < xe by Assumption AII this inequality and Lemma tells
F 2,1
limit
for some limit, which implies zn is a bounded sequence. Since z is bounded, so is G(zz) since
||ā(==))l² < Bullg(es W|2 s R2 sup 2| - 2-12 + R²
by Lemma 3
Condition (ii). This condition is assumed.
Condition (iii). Define
5x = -() - ((2x)
and
k m =
Σ asti.
1=0
17

---

Under review as a conference paper at ICLR 2020
Then (m,, is martingale and
E [11m++1
mx
Fu
=
a [11& |
k=0
1 [[1g(z):)))) w1)11 Fic
k=0
0k (R - 2=11 Rgj)
0 sup 21 z +2221 11 2 R2
almost surely, where the first inequality is the second moment upper bounding the variance, the second inequality is Lemma 3 and the third inequality is (6) and condition (i). Finally, we have (iii)
by Lemma !
Condition (iv). As discussed in Section G is maximal monotone, which implies G is upper semicontinuous, i.e., (Zuu: 9nx) (Zoa: 9 implies 9 G(ze), and ((z is closed convex set. Therefore, dist(Sne: G(2zo)) - 0 as otherwise we can find further subsequence such that converging to Soo such that (Soo, G(zzo)) > O. (Here we use the fact that Ça bounded due to condition (i)). Since G(zoo) is a convex set,
dist(Snz: (( + 0 =
1
dist(Snz: G(Ex)) - dist
m
Sax G(Eoa)
- 0.
In the main proof, we show that cluster points of Zinterp (-) are solutions. We need the following lemma to conclude that these cluster points are also cluster points of the original discrete time process Zg.
Lemma 7. Under the conditions of Lemma 6 Zinterp (.) and zg share the cluster points.
Proof. If z is cluster point of 2g, then it is cluster point of (interp by definition. Assume zeo is a cluster point of Sinterp (-), i.e., assume there is sequence Tj + oc such that Zinterp(Ty) + Zoo- Define K; with
tR, S Tj < -1,-1.
Then
[Tintep((T))
-2k,) s ax11 2ky < au (IlC ll + [lExl])
where use the assumption (i) which states that || is bounded and assumption (iii) which states that Or >> 0. We conclude Zk: - Zoa-
Continuous convergence to discrete convergence. Let ki - oo be a subsequence such that Zk, Zoo- Let Kn be further subsequence such that
lim +00
= (pxo)
interrp
for all T > solution of the differential inclusion.) By Lemma
0, which exists by Lemma 6 (The time-shifted interpolated process converges
lim Φr Zoo - 2x0 T0000
where d. + 2xc as + 00 and 2x0 is a saddle point. (The solution to the differential inclusion converges to solution.)
18

---

Under review as a conference paper at ICLR 2020
These facts together imply that for any 0, there exists kj and Tj large enough that
fy Pinterp (T₃) - Or, (250)) < <e/2
and
100,, 2oo 200l < <6/2.
Together, these imply
Pinterp(tyy (ty, Ty) 200 < E.
since o interp ()) Zinterp (T + +.). Therefore, 2o0 a cluster point of Zinterp()), and, by Lemma 7 Po0 Zoo is cluster point Z
Since || 2o0 || converges to a limit and converges to 0 on this further subsequence, we conclude almost surely.
|| 200
D ANALYSIS OF THEOREM 2
For convenience, restate the update, assumptions, and the theorem:
2k+1 = 2µz - aG((z)) - ((G(=x) G(=x-1))
(SimGD-O)
L is convex-concave and has a saddle point
(A0)
L is differentiable and V is R-Lipschitz continuous
(A3)
Theorem sense of
Assume AO
and
O < a < 2 23RR), then SimGI--O converges in the A3
2+ 2,3 R
min |[
11 + 3G(=0) - =2.11?
R)2
Furthermore, 2 + 2., where 2, a saddle point of L.
D.1 PROOF OF THEOREM 2
Throughout this section, write gke G(zz) for -1 Since can define & aG and 8 = =3/a and write the iteration as
2k+1 2k G(x)) B(((zz)) - ((Ex-1)))
we assume a = without loss of generality. Then
||=++1 + 89g 21 1 + Bgk-1 2,11² 2(gk 2x =.) (gk. 239h-1 9k)
S =| + -gh-1 2.11² (grs 2.gr-1 -gh),
where the inequality follows from II monotonicity of G, and
- (gg,, 28gk-1
9x)
4 (gr: 9k-1, 2k+1) (2 1)]1 -2ell 82 (11+23)) 23) -
4,8² (ge= 9k 1, 2k+1) (2 1)1[ =2x|1
We can bound
2,32
4.3 - 9k-kk-1-0 2k 2kt1) S
1lgx - - 2,3 Rl 2k+1 - 2x 1
R
< 2,3 R 21 2k-1
2,3 R 24 1
where the first inequality follows from Young's 's inequality, with R and the second inequality follows from Assumption (A3), R-Lischiit continuity of G. Putting these together we get
|k++1 + +.gg 12 < || + 89h-1 1.
+ 2 R|| z4-1l (2 2,32 || 2x (10)
Since 8> 1/2 and R (2 - - is assumed for Theorem 2 we have
2B2 R (2g - R)
19

---

Under review as a conference paper at ICLR 2020
By summing (10), have
&
(23 - 1- 1-
Fi41 - zil?
2,2 R
|| - zi-1 Σ =| + 3g-1 -z+1?
1=0
==0
- (28-1-483)
Σ
2i41
zill < || 20 + 8g -zx12
(II)
1=0
where we use 20 = 2-1-
Next,
|1
||
24 + B(g gk- 1]11
21|+1 2x112 + 2,8² 1 9k-1 1|2
21|11 - =k + 2,3² R² 1 2k- 11.
where we use
66. Using 11). we get
(21 - 211 2,3² R²I ||: 21-1113) < 2, R
23 4.32R. 20 + 8g-1 12.
Therefore, 2/ 2 2x1 + 2,3 R² 1 -k-1 11 0 and 119x|1 0. Moreover, have
2+ R2
min
|1::11 -
1 + +-9-1 - 2.11?
(2g 432
By scaling by we get the first stated result.
By summing (T0). we have
7 + Bgk-1 2, 11112 < 1120 + 1--1-11---0 2.112
and using the triangle inequality get
2 S =0 8g-1 z. 311g + 1| + 39-1 - -2.ll
as le + CO. (Remember 9k - 0.) So 24 is a bounded sequence, and let 200 be the limit convergent subsequence Zng- Since G is continuous mapping with gr. G(zne) 2nz 2o0 and In. + O, we have G[ O.
Finally, show that the entire sequence zІ converges to Zoc. Reorganizing
(0). we get
| + .gg - 12 2.3 R||2++1 2=11 < 2| + 8gg--1 - 2+11 2.9 Rll 2k-1 112
228 - 4:2 R)) || EM 1|2
So ||2411 89g 2.112 2,3 2332|12441 2x is nonincreasing sequence, and the following limit exists
lim || + 8yr-1 =x11 + 2,3 zk-1 11 11:00 1=
Since a. can be any equilibrium point, we let 2, 2oc. This proves || 200 112 0. i.c..
Zg + Zoo.
E ANALYSIS OF THEOREM 3
E. PRELIMINARY LEMMAS
We quickly state few identities and inequalities later use. As the verification of these results are elementary, we only provide short summary of their proofs.
Lemma 8. For p (0, 1) and k 2
p
p(1 p)
(k + 1)
1P
p
k
2k
kP
k
20

---

Under review as a conference paper at ICLR 2020
The proof follows from basic application of the inequality
p(1 p) x
1+ pr
S (1+ x) S 11+ pe
2
for E [0, 1] and p E (0, 1).
Lemma 9. For p E (0, 1) and k 2
P
(k: + 1)P KP
kP
The proof follows from integrating the decreasing function p/x--P from to +
Lemma 10. For p (0, and k 2 L,
0 S P 1)P - hp
p( p1)
k S
k(k+1)
2k
The proof follows from Lemma 8
Lemma 11. Given any Vo, Vi,... E R. we have
10 + (V, - -V--) -V-1) +V,
k-k + 1)
V/
2
The proof follows from basic calculations. This result can be thought of as the discrete analog of
22 V(s) (s()) ds VV
2
Lemma 12. Let 20, 21. E IR t+ be an arbitrary sequence. Then for any k = 0, 0,...
|1 - 20ll
2 11
zoll? 2k+1 2ki 5 (3841 + 2/)) 20
The proof follows from basic calculations. This result can be thought of as the discrete analog of
d 1 [1((1) =ol1 = (i(1), z0)
dt 2
E.2 CONVERGENT SEQUENCE LEMMAS
In the proofs of Theorems and we establish certain descent inequalities. The following lemmas state that these inequalities imply boundedness or convergence. Lemma 13. Let (V& [Ve),EN, and [UR]KEN, be nonnegative (deterministic) sequences satisfying
Vi+1 - 1 (1-CL C1
C2
hi-e f(k) V& + fi-e
VVa + Us
where C1 > 0, C2 > 0, fkk = o(1/k with e E [0, 1), and
Up < 00.
Then limsup V4 < C//C2.
Proof. For any E C1), there a large enough
2 0 such that for all K,
C
C 5/2/2
kI-e f(k)
ki-e
Define
C
==
(C 8)
21

---

Under review as a conference paper at ICLR 2020
for k 2 0. Then
-1/2
C3
V/ V/
Ve+1 S
1 ki-t
V/ +
(CI 0)k2- max
+ Un
Cr - -8/2)
CZS
V4+1-VS -V
(V/ v)
kl-c
2k 1 8)2
C2
Vk
1, V2
+ (C1 5)k 1 max
1 + Uk
Note that max (VI-
1,I - 1} S max max(0, - 1} for all 0. So
Ci -
C3
Ve
Vk+1 - V
(Vis -v)+ -
(C1 - 8) 1k max {0. v
1 Uk
ki-c
Ci 6/2
(Vis v/) + C 8
k1- max {0, V2 -v3 + Uk
ki-e
C 5/2
Ci δ k1-5
max {0, Vi - -v} +
max f0, V2 v) + Uk
kl-c
max (0, V/s v} + Un
2k 2-1
for large enough k. Since
8
1
max {0, Vi: - 13 + Uk
26:1-c
for large enough k, we have
( 1
5 max {0, V/s - v3 + Uk
max {0, V of S
2h:1-
With a standard recursion argument (e.g. Lemma of (Polyak 1987
we conclude
max {0, 1/2 - / + 0. Since this holds for any > O. we conclude lim sup V
S C /2/ O
Lemma 14. Let E E (0. Let (V* KEES, and (U*]KEN, be nonnegative (deterministic) sequences satisfying
Vk+1 1 (1- ki-r +++++((()) f(k) V/ + + + UKk where C> 0. f(k) o(1/k' - g(k) = 011/k) and
Uh < x0.
Then V2 O.
Proof. For any > 0, there is large enough K 2 0 such that
C-8 8 V& +
5
Va+1 S
kI-c VV= + Up
カ--=
for all k 2 K. By Lemma 13 8 > 0, we conclude V₁ +0
conclude lim soo Va 52/(CC (CCC())) -5)2. Since this holds for all
E.3 PROOF OF THEOREM
For convenience, we restate the update, assumptions, and the theorem: (1 (1-p)r p)y
1-p
2k+1 2k
(k 1Ip G(zx)
(zo 2xc)
(SimGD-A)
k+1
is convex-concave and has a saddle point L is differentiable and V is R-Lipschitz continuous
(A0)
(A3)
22

---

Under review as a conference paper at ICLR 2020
Theorem 3 sense of
Assume
A0
If E (1/2,1) and oy 2 2, then SimGD-A converges in the and A3
[G((+)]| 00 k2-2pp
Proof outline. Lemma 15 shows the iterates are bounded. Lemma 1ooss that || 224 + 2k-1ll", the analog of is small. The second-order derivative does not arise the continuous- time analysis of Section 4.1 In the discrete-ting tinerete-timeeee setup, ||=x+1 22x 2 does arise, but use Lemma [6] to show that its contribution small. The main proof follows by mimicking the continuous-time analysis by bounding the higher-order terms.
Throughout this section, write = G(z+) for k 2 -1.
Lemma 15. For SimGD-A,
|| 2, SC
for all k 2 0 for some C > 0. (This result depends on assumption p > 1/2.)
Proof.
2(1 - p)
2 p)
|| =. ==1 =1|z
1|
(ghs -2a) +
(zo
-k; Fk z.)
(A: 1)0
k ++1
(k: + 1)p 9k + 7(1 - p)
1 p
2
+
(z0 2x
k + 1
2y p)
1|24 - 2, 11 2y(1 p)
(20
2x, 26 - 22)
h: ++1 1
k *+1
+ 2(1 p)
11 2 + 2y² - p)²
|1 2x11
(k: + 20
(k + 1)2
2y - p)
4/² - p)
1124 21 2/2 + 27(1 - p)
+
k+1 |1 - 2, 1211llz - 2.
k+1
(k + 1)2
+ 2(1 - p)2
472 pp] p)²
R² 1| - 20112
11:0 2
(k: + 1)20
(1: 1}2
2x p)
4-2(1 p)2
+ R 4(1 - pp)
||: 11
1
+ 1)²
(k + 1)2p
27(1 p)
2 + 47 y)² (k: + 1)2
|0 2+ |||| 2s
|| 12
k:
+
where the first inequality follows from 1. the monotonicity inequality, and 66) and the second inequality follows from Assumption A3 We conclude the statement with Lemma 13
Lemma 16. For SimGD-A,
[| 2zz Z4 21-111² 1l2
(72
R2
122 72 1242p
S 4(1 2)²
+
2|
z-11
+
4(1
p)²
11:0
2x
122
1.2
23

---

Under review as a conference paper at ICLR 2020
Proof.
2k - 22k + 24 2x-1l1
P
1-P P
pl7
(1 [1-p) (zo =x-1)
(k T)p 9k
9k-
(zo - 2x)) +
bp
k +
k
2
(k 1)p 9h
p
1-p P
9k-1
2
+2
7(1 -p) p)
(z0 =w))
7(1 7 p)
(20 zk-1)
2
kp
k
4(1 p)²
1 -
1 1-p p
19 9k 9k-1 +4
119x|1
hPp
(1: + 1)B
k"
41 p)2
(2 - p)
7(1 - p)
2
+
1|zx - 1k1 ? +4 4
11:0 - 2xll
h2
h: +
h
72 k2
R²
122 k2+2p
722
54(1-p)
+
1| - 2/-1l 11 + 41-1pp p)²
+ k4
||20 - 2n 11?
h2p
where the first and second inequalities follow from 6 and the third inequality follows from As- sumptions (A3) and Lemma 8
24

---

Under review as a conference paper at ICLR 2020
Main proof. In Section
4.1 showed
d
||())]1 - - (z(t) 20,
-0,
dt 2
in continuous time. We mimic analogous calculations the discrete-time setup:
1 211
2 2641 - zk 1|
2
b11z =k
2 (2b+1 2k -2k-1), 2x+1 - 22k + 26-1)
1 1-P P (Ex 11 9k-1) + (1 p))
(k: + 1)2 kk
711 - p))
(2x 2k 9k)
11 2k-1 11
kP
kP (k: 11/
k
7(1 - p)
1
k:lk: + (Zk- 21 zx)
1|
1 22xx 2 2
2
$ (1 p) (k + 1)0- 1.
(2x- 1,-1,
|| 2k 11?
(1: & 1)p
k
7(1 p)
(Ek- 2k-1 10
=x) +
|| 22x 2/ 2 11?
k:k + 1)
2
((1 -p)
(k: + 1)0
k2
7(1 - p)
7(1
- p) (le 1)2² - kD'
+
1| 21-211
k
kP
2k(k + +1)
2
kP 1)
(ke + 1)"
1
(Za Zk 1, 2/ - 2zk + zk-1) +
|||||
||
- 2zk + zx-11 111
KD
2
(k + 1)p KP
)
7(1 D)
k:(k: + 1)
( + 1)
2k 2k 20
2
(2x: + +z11)
7(1 p)
P
p(1 p) 711 p)
7M p)
||=1 2 1/1 111
k
k
21
2k(k + 1)
2(k + 1)2
(ke + 1)0-
1
(2k- 2k 1: 2k-1 22k + 2k-1) +
||
- 22 + 26-221 11?
KP
2
(k + 1)P K2)
)
71 p)
2k 1k-1: 50
(2x + =x11
k(KK + 1)
kP(k + 1)
7(1 p)
P
p(1
- p)
7(1 p)
+
7p(1 - p) 2(k + 1)2
|| 2x-1/1 11
k
2k
2k(k + 1)
p
Zk 2 3|
p
|x41
2zn z4 zz-1l) 1||
21
2
+
[k+1 22 + 11-1
2
(k: + 1)p k2) )
(
1
711 p)
2x 14-22-11 1--
(2t + +z11)
k(k + +1
kP(k + 1)
2
(11 p)
P p(1 --p) p)
7(1 p)
7p(1 p)
+
11 212
k
k
2k
2k(k + 1)
2(k + 1)2
2k
+ P
||24|
2%k + Zh 11²
2
7(1 - p)²
7/1 (zk + 2R1)
k(k + 11)
2/ zカ 1, 20
(k+ + 1)p 1pP
1-p P 1:( ((k+1)
7(1 -p)
zk 2b-1,
z (=x + =xa)
1o(k: 1)
kP + 11
(k.pp
where the first inequality follows from (T), the monotonicity inequality, the second inequality fol-
lows from Lemma g and (6). and the third inequality follows from Lemma g and (5), Young's inequality, with k.
25

---

Under review as a conference paper at ICLR 2020
By Lemma
10 C1 (ki p)] 1 p(1-p)
Using ())
Young's inequality, with 1 and (6) we get
2h
1
(k 1)p kD
1 1-p p
)
(
1
71 p)
(o + 1)
kp +
k(k + 1)
2k 2k-1. 20
2
(ex 2
- 7p(1 2)²
1| - 2k-1 112 + 7pp11 - p)2
1
1|20
(2x + xx11
4k2
4k:2
2
< 2pp(1 p)
|| - -か- 112 + yp(1 1 - p)²
(11z0 2x11 + 1120 2x-1
4k2
8k:2
Putting these together we get
1
12 - 2k-1 12 7(1 - p)²
(
2 |k - =x11²
2 2112x - 2k- 11 + k +
2x - 2k 2k-1, 2
(2x: + =k11) - 20
k(k + 1)
s - (7 - 1)(1 - -p)
+ 10 p)
p(1
p)
7(1 p)
1pp1 - -p)²
11 - 1111
k
2(k + 1)2
2k
21:(1: + 1)
2k
412
1 +
Tp( 1 p)²
+ 2
|| 2zk + -k-1 11 +
|0 1= + -|=00- 11-)
8k:4
With Lemma
15
and Lemma 16
we get
1 2
1
12 - 2k-1/1 7(1 - [p)
1
2b+1
2x.l
2k
1111
2k
+
- 2k- 2
(2x + 2x12) - 20
2
k
+
k(k + 1)
()-1)(1-))- 2(1+))((- ?
pppp pp)(--))-- p((-))
x(3-p)
202 - -p(1-0)
22 =
1| 2x-1112
k2p
262
2h(1-1)
4n2
122
72)
7P(1 - p))
+
2(1 + +p((1 - p))
k2+2p
+
+
8
C2
( - 1)(1 - p)
x
1| - 2/-1 1| +
k
2p
k:+2p
=Cs(k.T.p.R)
Note that there is a K such that Ca(k,77P S 0 for all k 2 K (with y, p. and R fixed).
In Section 4.1 we multiplied the established inequality by and integrating both sides to get
e |=((0)1 < 2 [1=((1) - 2ol12
2
We mimic analogous calculations in the discrete-ting setup. Multiply both sides with k-k + 1) and sum both sides from ls to k = k. and apply Lemma 11 and Lemma 12 to get
k(k + 1) || 1x < 7(1 p)² 1|
=012 + C4 O
2
1PP-1
where C2 < since Cs(ks, Y. R) > 0 for only finitely many k. Reorganizing we get
kkk + 1)(1 - p)
| 112 + k(1 - p)²22
k(1 - p)²²
120
2x
(gk: 20 2k)
2(k 1)2p
2(k + 1)
(k+ + 1)P
71 p)
1
z0ll2 + C +0
k2p-1
Reorganizing yet again we get
k(k + 1)(1 2)²
k(1 -p)2y
11gn|1
(gks 20 -Rn)
2(k: + 1)2p
(k + 1)p
< 7(1 2)
7k
1 -
1|ek
20112 20012 + C2 + +
2
k k+1
k2p-1
S C4 0
h:p-11
26

---

Under review as a conference paper at ICLR 2020
where we use the assumption that 2. Reorganizing again, get
27
2C4
11aa11 =
(k: + 1)² pp (gk,
2k) +
+
(1 - p)2kk 1)
1)
27
4C4
(k+ + 1) 1p (gh, 20 - -2,) +
(1 p)² 1)2-2p +0
272
4C
2 $119011 1| (k 1)2 -0 2. 1. +
(1 - 2k + 1)2-2p
for k 2 where the second inequality follows from I the monotonicity inequality, and the third
inequality follows from (5), Young's inquality, with = 7/(k + P Finally, we have
C
||
O
k222p
with C' = 4-2 875
ANALYSIS OF THEOREM
For convenience, we restate the update, assumptions, and the theorem:
1- 2k+1 26 (k + 1)p ((23)w)) + (1 p)y
(h: + 1) 1) (zo 2x)
(SSSGD-A)
L is convex-concave and has a saddle point
(A0)
Eus wa (19()))11)
((22)w2))1 Rill 2211 R
21,, 22 Bu
(A2)
Theorem Assume A0 and A2
I (1/2, e E 1/2), and y 0. then SSSGD-A
converges in the sense of 2y Zn, where 2. is a saddle point.
To clarify, we do not assume L is differentiable for Theorem
Proof outline. The key insight is to define Ça to be something like a "fixed point" the k-th iteration of SSSGD-A and then to show 2₁ shrinks towards to So in the following sense
||=+11 1++ < (1 something)ll=* Cx 2 + (something small).
Lemma 17 states that Ça slowly (stably) converges to solution. Using the fact that shrinks towards Ca and the fact that ÇL is a slowly moving target converging to a solution, we conclude E4 converges to solution.
Preliminary definition and result.
More precisely, we define Ça to satisfy
1-P 1-P G(C+) + (1- (zo Ck). (k 1>
Co E Ck
(k+ 1)1-c
(However, & not actually a fixed point, since SSSGD-A has noise and since is multi-valued operator.) We equivalently write
Sh+1 (1 (k 1k+1)'=p G
(zo).
7
Lemma 17 (Proposition 23.31 and Theorem 23.44 of Bauschke & Combettes (017)) Let G be
maximal monotone operator such that Zer(G)) * Then (I + +G) (2o)) - Pzor(G] (20) and
[I + (r+ (I -I (20) / 5 (
for any 2 0 as co.
27

---

Under review as a conference paper at ICLR 2020
F.1
PROOF OF THEOREM 4
Main proof.
Since 1 - - s > 0, Lemma 17 gives us
6a - (Zer(C)
Then we have
|k+1 Sk+1 11 Fk
|| 12 2s - Sk
1 1 p
(1 - (1-p)7
(20 2k) + SE - Sa+1 121 Fr
E
(k + 1)m g (z);:wk)
+
(k + 1)1-c
1-p
(1 - --)y
= -1|2k
lall
G(zx) +
(2k- 20), 2x - CK
(k: + 1)p
(k + 1)--c
+ (ax
Cki Ck Sk+1}
1 p
(1-p)y
+
(k: + 1 (20
(k: + 1)1- (zo - =x) - Gx + CR+1
Fk
(1 p)y
1
1|ek - -alll + 1| - Salll l15a - -k++1l
(k: + 1))--)
1
(1s(=anw))11 011 Fx +0 ( ( (I+ 1)-(1)a)0)
1|=0 - =x
(I: + 1)2p
(A: + 1)2
(1 p
|| - -xll + +((1/k) ||= - -cull
(k: + 1)
0
(1 - 2x + R
(k: + 1)2(-s) || - zu +
(k: + 1)2p
(I- + 1)
where the first inequality follows from (T. the monotonicity inequality, Cauchy- inequality, and (6), Now we take the full expectation to get
E
|| S1+111?]
$ 1 0
(Ks 1 (1++1)1-)+ +0
(k+ 1)2(-)))))) (0( E [1=2 - Scll²)
(k + 1)2r) +0
(ks
|1ze -Aal3]11 1/2
+ O(1/k)
+0 ( 1)30 ) (1|20 - 2=1 + 1)
())+1))ss)) (k+ ( ) 11 21 + + (
(I: + 1)2
where we used [=|1= 11 < B[||= Ca 12] Applying Lemma
14 we get IE ||=x Cx 0.
Since Se + Prer(c) (20), we conclude 2/e 1.2 Pro)(cy(Zo).
G EXPERIMENT DETAILS
In this section, we prodvide further details of the experiments of Section 5 Our Optimistic Adam is a variation of the Optimistic Adam of (Daskalakis al.) 20188. which uses = 1 while we allow for a general optimism rate / > 0. For Anchored Adam, we do not diminish the strength of the anchor proportional to 1/k: 1- since Adam does not diminish the learning rate. Rather, we maintain a constant anchor strength 7 but refresh the anchor point every T iterations. The notation V in algorithm tables denote the element-wil wise square operation.
28

---

Under review as a conference paper at ICLR 2020
Generator
latent space 100 (Gaussian noise)
dense 128 IReLU
dense 256 batchnorm IReLU
dense 512 batchnorm IReLU
dense 1024 batchnorm IReLU dense 1024 tanh Discriminator
Resize the imput image 28 x 28 to 32 x 32 dense 512 IReLU
dense 256 IReLU
dense 1
Table Generator and discriminator architectures for the MNIST experiment
Optimistic Adam
learning rate 7) exponential decay rates for moment estimates B1, $2 E [0, 1), optimism rate p > 0, and initial parameters 20
Parameters:
Repeat & 1.,..., K (iteration):
Compute stochastic gradient V., = G(zx)
Update biased estimate of first moment: my m1 (1-
Update biased estimate of second moment: Uk = B2th + (1-1
Scale the step-size: în n - / - B+)
Perform optimistic gradient step: 2/- 2k-1 n) (1 p) vorte + f /ox itc
Return 2K
Anchored Adam
learning rate exponential decay rates for moment estimates 31, B2 E [0, 1), anchor rate y > anchor update period T, and initial parameters 20
Parameters:
Repeat & 0, 1, ..., K (iteration):
set anchor σs = 2ς if mod(k; k, T) = 0 else on = dk-1
Compute stochastic gradient V., G(2+)
Update biased estimate first moment: my = 81m -11-11) Ve.k
Update biased estimate second moment: Uk = B20k + (1-13) V
z,k
Scale the step-size: în 7/ 55/ Bt)
Perform anchored gradient step: z = 2k-1
ma voc+t + 7(ax 2k-1)
Return 2K
29

---

Under review as a conference paper at ICLR 2020
batch size = 64
Adam learning rate = 0.0002
Adam B1 = 0.5
Adam A3 0.999
max iteration 200000
GAN objetive = "WGAN-GP"
Gradient penalty parameter À 10
dids = Optimizer "Adam", "Optimistic Adam", "Anchored Adam"
Optimism rate p = 1
Anchor rate 7 Anchor refresh period T = 10000
Table 2: Hyperparameters for the MNIST experiment
Generator
latent space 128 (Gaussian noise)
dense x 4 x 512 batchnorm ReLU
4 X 4 conv.T stride=2 256 batchnorm ReLU
X 4 conv.T stride=2 128 batchnorm ReLU
4 X 4 conv.T stride=2 64 batchnorm ReLU
4 x 4 conv.T stride=1 3 weightnorm tanh Discriminator
Input Image 32 32 3
3 x conv. stride=1 64 IReLU
3 conv. stride=2 128 IReLU
3 conv. stride=1 128 IReLU
3 conv. stride=2 256 IReLU
3 conv. stride=1 256 IReLU
3 conv, stride=2 512 IReLU
3 conv. stride=1 512 IReLU dense
Table 3: Generator and discriminator architectures for the CIFAR-10 experiment
batch size 64
Adam learning rate = 0.0001
Adam 81 0.0
Adam 32 = 0.9
max iteration 100000
GAN objetive = "WGAN-GP"
Gradient penalty parameter À =1
Ais = 1
Optimizer "Adam", "Optimistic Adam", or "Anchored Adam"
Optimism rate p ==1 Anchor rate 7 = 1
Anchor refresh period T 10000
Table 4: Hyperparameters for the CIFAR-10 experiment
30


Reviews:
[{"review_id": "H1e3787jYB", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 1, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "The paper studies last-iterate convergence of simultaneous gradient descent and related algorithms in (convex-concave) GANs.\n\nThe experiments are very weak. Figure 4 shows that anchored Adam outperforms Adam and optimistic Adam in terms of FID on MNIST, but not CIFAR-10. \n\nThe authors cite many of the vast number of algorithms that have been proposed to train GANs (Heusel, Mescheder, Gidel, Gemp, and on and on ... and on…) and discuss some of them in the analysis. However, when it comes to experiments, they only compare against vanilla Adam (!) and Optimism. I would summarize the experiments as *suggesting* that anchoring doesn’t hurt on MNIST or CIFAR-10. The paper doesn’t tune beta and gamma, so it’s hard to be sure. \n\nThe motivation for the paper is GANs, but GANs are not convex-concave. The analysis is therefore not directly relevant. From the experiments, it is not clear *at all* whether anchored Adam is *actually* an improvement in practice over any of the alternative algorithms that the authors discuss or cite. \n\nIn short, the contribution is unclear. The analysis is better suited to a venue like COLT. To be a reasonable ICLR submission, the paper needs to compare against more baselines at a bare minimum.\n", "extra_scores": {"experience_assessment": "I have published one or two papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "Byx_SfI1qS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "This paper analyzes the dynamics of stochastic gradient descent when applied to convex-concave games (motivated by the game used to train GANs, which is typically not convex-concave), as well as the previously proposed GD with optimism and a new anchored GD algorithm that provably converges under weaker assumptions than SGD or SGD with optimism.\n\nThis seems like a nice contribution to the GAN theory literature, and the anchored SSSGD algorithm might well have significant practical value (although more thorough experiments would be needed to make this claim). As such I recommend acceptance.\n\nThe obvious critique to raise of this kind of work is that the GAN problems that motivate it are clearly not convex-concave, and so it is unclear how or whether the results can or should inform practice. The simplest way to make the case for that kind of relevance is empirically, so I'd recommend that the authors consider what kinds of GAN experiments would support (or falsify) the claim that their theoretical results have some hope of generalizing to the non-convex-concave setting. Figure 4 is suggestive, but it doesn't say much except that anchored Adam might occasionally be a good choice (and sometimes isn't). The samples in Figure 3 are pretty far from the state of the art, and in any case Figure 3 doesn't even say which training method generated them.\n\nFinally, PLEASE don't include acknowledgments in a paper that's under double-blind review; it compromises your anonymity, which in principle could be grounds for a desk rejection.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BJx2N57Ctr", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "*Summary*\nThis paper provides the analysis of three algorithms in the context of minmax convex concave games: Simultaneous stochastic subgradient method, Simultaneous gradient with optimism and Simultaneous gradient with anchoring. These three algorithm are first analysed in continuous time with an ODE perspective and then leverage these intuitions and techniques to analyze the discrete time versions.\n\nI think that these contributions are of interest of ICLR community, however, I have some concerns regarding the presentations of the results. \n\n*Decision*\nI vote for a weak accept that could move to an accept if the authors improve the presentation of the paper:\nThe paragraph “Regularized dynamics and convergence’ in Section 3.1 in quite hard to follow. This subsection is basically the proof of the convergence of the continuous version of  GD-O. Stating the result before the proof would help the reader to understand where the authors want to go. \nVery same point for The subsection 4.1\nFor the stochastic version of SimGD-A a new parameter $\\epsilon$ is introduced without any comment or description on why it is necessary. \nA FID above 40 for MNIST is very far from standard results (that are below 1). Thus I am not convinced by the practical advantage of Anchored Adam on these models that have performances results very far from the standard ones.  (for instance between 20 and 25 for CIFAR10 is very reasonable). It is maybe because you do not use convolutional layers in your architecture. I think that using a DGAN architecture (for instance the one from the pytorch tutorial https://pytorch.org/tutorials/beginner/dcgan_faces_tutorial.html) would give the expected results (i.e. FID close to 0).\n\n*Questions*\n\n- When you cite Lassale Principle you mention that if $z_\\infty$ is a limit point of $z(t)$ then starting at $z_\\infty$, you stay at a constant distance to $z_*$. But in the bilinear example you give any point in the circle is not a limit point (size no dynamics converge to it). I guess when you said limit point you meant adherent point ?\n- Is the condition $\\epsilon$ only necessary for the proof ? Does $\\epsilon =1$ work in practice ? \nIf no, what is the best value for $\\epsilon$ ?\n", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: Motivated by GANs, the authors study the convergence of stochastic subgradient                                                     
descent on convex-concave minimax games.                                                                                           
They introduced an improved "anchored" SGD variant, that provably converges                                                        
under milder assumptions that the base algorithm.                                                                                  
It is applied to training GANs on MNIST and CIFAR-10, partially showing                                                            
improvements over alternative training methods.                                                                                    
                                                                                                                                   
A main point of criticism that the reviewers identify is the strength of the                                                       
assumptions needed for the analysis.                                                                                               
Furthermore, the experimental results were deemed weak as the reported scores                                                      
are far away from the SOTA, and only simple baselines were compared against.  
Decision: Reject