A VARIATIONAL INEQUALITY PERSPECTIVE ON GENERATIVE ADVERSARIAL NETWORKS
Year: 2019

Abstract:
Generative adversarial networks (GANs) form a generative modeling approach known for producing appealing samples, but they are notably difficult to train. One common way to tackle this issue has been to propose new formulations of the GAN objective. Yet, surprisingly few studies have looked at optimization methods designed for this adversarial training. In this work, we cast GAN optimization problems in the general variational inequality framework. Tapping into the mathematical programming literature, we counter some common misconceptions about the difficulties of saddle point optimization and propose to extend techniques designed for variational inequalities to the training of GANs. We apply averaging, extrapolation and a computationally cheaper variant that we call extrapolation from the past to the stochastic gradient method (SGD) and Adam.

heading: 1 INTRODUCTION
text: Generative adversarial networks (GANs) (Goodfellow et al., 2014) form a generative modeling approach known for producing realistic natural images (Karras et al., 2018) as well as high quality super-resolution (Ledig et al., 2017) and style transfer (Zhu et al., 2017). Nevertheless, GANs are also known to be difficult to train, often displaying an unstable behavior (Goodfellow, 2016). Much recent work has tried to tackle these training difficulties, usually by proposing new formulations of the GAN objective (Nowozin et al., 2016; Arjovsky et al., 2017). Each of these formulations can be understood as a two-player game, in the sense of game theory (Von Neumann and Morgenstern, 1944), and can be addressed as a variational inequality problem (VIP) (Harker and Pang, 1990), a framework that encompasses traditional saddle point optimization algorithms (Korpelevich, 1976).
Solving such GAN games is traditionally approached by running variants of stochastic gradient descent (SGD) initially developed for optimizing supervised neural network objectives. Yet it is known that for some games (Goodfellow, 2016, §8.2) SGD exhibits oscillatory behavior and fails to converge. This oscillatory behavior, which does not arise from stochasticity, highlights a fundamental problem: while a direct application of basic gradient descent is an appropriate method for regular minimization problems, it is not a sound optimization algorithm for the kind of two-player games of GANs. This constitutes a fundamental issue for GAN training, and calls for the use of more principled methods with more reassuring convergence guarantees.
Contributions. We point out that multi-player games can be cast as variational inequality problems (VIPs) and consequently the same applies to any GAN formulation posed as a minimax or non-zerosum game. We present two techniques from this literature, namely averaging and extrapolation, widely used to solve VIPs but which have not been explored in the context of GANs before.1
We extend standard GAN training methods such as SGD or Adam into variants that incorporate these techniques (Alg. 4 is new). We also explain that the oscillations of basic SGD for GAN training previously noticed (Goodfellow, 2016) can be explained by standard variational inequality optimization results and we illustrate how averaging and extrapolation can fix this issue. ∗Equal contribution, correspondence to firstname.lastname@umontreal.ca. 1The preprints for (Mertikopoulos et al., 2019) and (Yazıcı et al., 2019), which respectively explored extrapolation and averaging for GANs, appeared after our initial preprint. See also the related work section §6.
We introduce a technique, called extrapolation from the past, that only requires one gradient computation per update compared to extrapolation which requires to compute the gradient twice, rediscovering, with a VIP perspective, a particular case of optimistic mirror descent (Rakhlin and Sridharan, 2013). We prove its convergence for strongly monotone operators and in the stochastic VIP setting.
Finally, we test these techniques in the context of GAN training. We observe a 4-6% improvement over Miyato et al. (2018) on the inception score and the Fréchet inception distance on the CIFAR-10 dataset using a WGAN-GP (Gulrajani et al., 2017) and a ResNet generator.2
Outline. §2 presents the background on GAN and optimization, and shows how to cast this optimization as a VIP. §3 presents standard techniques and extrapolation from the past to optimize variational inequalities in a batch setting. §4 considers these methods in the stochastic setting, yielding three corresponding variants of SGD, and provides their respective convergence rates. §5 develops how to combine these techniques with already existing algorithms. §6 discusses the related work and §7 presents experimental results.

heading: 2 GAN OPTIMIZATION AS A VARIATIONAL INEQUALITY PROBLEM

heading: 2.1 GAN FORMULATIONS
text: The purpose of generative modeling is to generate samples from a distribution qθ that matches best the true distribution p of the data. The generative adversarial network training strategy can be understood as a game between two players called generator and discriminator. The former produces a sample that the latter has to classify between real or fake data. The final goal is to build a generator able to produce sufficiently realistic samples to fool the discriminator.
In the original GAN paper (Goodfellow et al., 2014), the GAN objective is formulated as a zero-sum game where the cost function of the discriminator Dϕ is given by the negative log-likelihood of the binary classification task between real or fake data generated from qθ by the generator,
min θ max ϕ L(θ,ϕ) where L(θ,ϕ) def= −E x∼p [logDϕ(x)]− E x′∼qθ [log(1−Dϕ(x′))] . (1)
However Goodfellow et al. (2014) recommends to use in practice a second formulation, called non-saturating GAN. This formulation is a non-zero-sum game where the aim is to jointly minimize:
LG(θ,ϕ) def = − E
x′∼qθ logDϕ(x
′) and LD(θ,ϕ) def = − E
x∼p logDϕ(x) − E x′∼qθ log(1−Dϕ(x′)) . (2)
The dynamics of this formulation has the same stationary points as the zero-sum one (1) but is claimed to provide “much stronger gradients early in learning” (Goodfellow et al., 2014) .

heading: 2.2 EQUILIBRIUM
text: The minimax formulation (1) is theoretically convenient because a large literature on games studies this problem and provides guarantees on the existence of equilibria. Nevertheless, practical considerations lead the GAN literature to consider a different objective for each player as formulated in (2). In that case, the two-player game problem (Von Neumann and Morgenstern, 1944) consists in finding the following Nash equilibrium:
θ∗ ∈ arg min θ∈Θ LG(θ,ϕ∗) and ϕ∗ ∈ arg min ϕ∈Φ LD(θ∗,ϕ) . (3)
Only when LG = −LD is the game called a zero-sum game and (3) can be formulated as a minimax problem. One important point to notice is that the two optimization problems in (3) are coupled and have to be considered jointly from an optimization point of view.
Standard GAN objectives are non-convex (i.e. each cost function is non-convex), and thus such (pure) equilibria may not exist. As far as we know, not much is known about the existence of these equilibria for non-convex losses (see Heusel et al. (2017) and references therein for some results). In
2Code available at https://gauthiergidel.github.io/projects/vip-gan.html.
our theoretical analysis in §4, our assumptions (monotonicity (24) of the operator and convexity of the constraint set) imply the existence of an equilibrium.
In this paper, we focus on ways to optimize these games, assuming that an equilibrium exists. As is often standard in non-convex optimization, we also focus on finding points satisfying the necessary stationary conditions. As we mentioned previously, one difficulty that emerges in the optimization of such games is that the two different cost functions of (3) have to be minimized jointly in θ and ϕ. Fortunately, the optimization literature has for a long time studied so-called variational inequality problems, which generalize the stationary conditions for two-player game problems.

heading: 2.3 VARIATIONAL INEQUALITY PROBLEM FORMULATION
text: We first consider the local necessary conditions that characterize the solution of the smooth two-player game (3), defining stationary points, which will motivate the definition of a variational inequality. In the unconstrained setting, a stationary point is a couple (θ∗,ϕ∗) with zero gradient:
‖∇θLG(θ∗,ϕ∗)‖ = ‖∇ϕLD(θ∗,ϕ∗)‖ = 0 . (4) When constraints are present,3 a stationary point (θ∗,ϕ∗) is such that the directional derivative of each cost function is non-negative in any feasible direction (i.e. there is no feasible descent direction):
∇θLG(θ∗,ϕ∗)>(θ − θ∗) ≥ 0 and ∇ϕLD(θ∗,ϕ∗)>(ϕ−ϕ∗) ≥ 0 , ∀ (θ,ϕ) ∈ Θ× Φ. (5)
Defining ω def= (θ,ϕ), ω∗ def= (θ∗,ϕ∗), Ω def= Θ× Φ, Eq. (5) can be compactly formulated as:
F (ω∗)>(ω − ω∗) ≥ 0 , ∀ω ∈ Ω where F (ω) def= [ ∇θLG(θ,ϕ) ∇ϕLD(θ,ϕ) ]> . (6)
These stationary conditions can be generalized to any continuous vector field: let Ω ⊂ Rd and F : Ω→ Rd be a continuous mapping. The variational inequality problem (Harker and Pang, 1990) (depending on F and Ω) is:
find ω∗ ∈ Ω such that F (ω∗)>(ω − ω∗) ≥ 0 , ∀ω ∈ Ω . (VIP) We call optimal set the set Ω∗ of ω ∈ Ω verifying (VIP). The intuition behind it is that any ω∗ ∈ Ω∗ is a fixed point of the constrained dynamic of F (constrained to Ω).
We have thus showed that both saddle point optimization and non-zero sum game optimization, which encompass the large majority of GAN variants proposed in the literature, can be cast as VIPs. In the next section, we turn to suitable optimization techniques for such problems.

heading: 3 OPTIMIZATION OF VARIATIONAL INEQUALITIES (BATCH SETTING)
text: Let us begin by looking at techniques that were developed in the optimization literature to solve VIPs. We present the intuitions behind them as well as their performance on a simple bilinear problem (see Fig. 1). Our goal is to provide mathematical insights on averaging (§3.1) and extrapolation (§3.2) and propose a novel variant of the extrapolation technique that we called extrapolation from the past (§3.3). We consider the batch setting, i.e., the operator F (ω) defined in Eq. 6 yields an exact full gradient. We present extensions of these techniques to the stochastic setting later in §4.
The two standard methods studied in the VIP literature are the gradient method (Bruck, 1977) and the extragradient method (Korpelevich, 1976). The iterates of the basic gradient method are given by ωt+1 = PΩ[ωt − ηF (ωt)] where PΩ[·] is the projection onto the constraint set (if constraints are present) associated to (VIP). These iterates are known to converge linearly under an additional assumption on the operator4 (Chen and Rockafellar, 1997), but oscillate for a bilinear operator as shown in Fig. 1. On the other hand, the uniform average of these iterates converge for any bounded monotone operator with a O(1/ √ t) rate (Nedić and Ozdaglar, 2009), motivating the presentation of averaging in §3.1. By contrast, the extragradient method (extrapolated gradient) does not require any averaging to converge for monotone operators (in the batch setting), and can even converge at the faster O(1/t) rate (Nesterov, 2007). The idea of this method is to compute a lookahead step (see intuition on extrapolation in §3.2) in order to compute a more stable direction to follow.
3An example of constraint for GANs is to clip the parameters of the discriminator (Arjovsky et al., 2017). 4Strong monotonicity, a generalization of strong convexity. See §A.

heading: 3.1 AVERAGING
text: More generally, we consider a weighted averaging scheme with weights ρt ≥ 0. This weighted averaging scheme have been proposed for the first time for (batch) VIP by Bruck (1977),
ω̄T def = ∑T−1 t=0 ρtωt ST , ST def = T−1∑ t=0 ρt . (7)
Averaging schemes can be efficiently implemented in an online fashion noticing that,
ω̄T = (1− ρ̃T )ω̄T−1 + ρ̃TωT where 0 ≤ ρ̃T ≤ 1 . (8) For instance, setting ρ̃T = 1T yields uniform averaging (ρt = 1) and ρ̃t = 1−β < 1 yields geometric averaging, also known as exponential moving averaging (ρt = βT−t, 1 ≤ t ≤ T ). Averaging is experimentally compared with the other techniques presented in this section in Fig. 1.
In order to illustrate how averaging tackles the oscillatory behavior in game optimization, we consider a toy example where the discriminator and the generator are linear: Dϕ(x) = ϕTx and Gθ(z) = θz (implicitly defining qθ). By substituting these expressions in the WGAN objective,5 we get the following bilinear objective:
min θ∈Θ max ϕ∈Φ,||ϕ||≤1
ϕTE[x]−ϕTθE[z] . (9)
A similar task was presented by Nagarajan and Kolter (2017) where they consider a quadratic discriminator instead of a linear one, and show that gradient descent is not necessarily asymptotically stable. The bilinear objective has been extensively used (Goodfellow, 2016; Mescheder et al., 2018; Yadav et al., 2018) to highlight the difficulties of gradient descent for saddle point optimization. Yet, ways to cope with this issue have been proposed decades ago in the context of mathematical programming. For illustrating the properties of the methods of interest, we will study their behavior in the rest of §3 on a simple unconstrained unidimensional version of Eq. 9 (this behavior can be generalized to general multidimensional bilinear examples, see §B.3):
min θ∈R max φ∈R
θ · φ and (θ∗, φ∗) = (0, 0) . (10)
The operator associated with this minimax game is F (θ, φ) = (φ,−θ). There are several ways to compute the discrete updates of this dynamics. The two most common ones are the simultaneous and the alternating gradient update rules,
Simultaneous update: { θt+1 = θt − ηφt φt+1 = φt + ηθt , Alternating update: { θt+1 = θt − ηφt φt+1 = φt + ηθt+1 . (11)
Interestingly, these two choices give rise to completely different behaviors. The norm of the simultaneous updates diverges geometrically, whereas the alternating iterates are bounded but do not converge to the equilibrium. As a consequence, their respective uniform average have a different behavior, as highlighted in the following proposition (proof in §B.1 and generalization in §B.3): Proposition 1. The simultaneous iterates diverge geometrically and the alternating iterates defined in (11) are bounded but do not converge to 0 as
Simultaneous: θ2t+1 + φ 2 t+1 = (1 + η 2)(θ2t + φ 2 t ) , Alternating: θ 2 t + φ 2 t = Θ(θ 2 0 + φ 2 0) (12)
where ut = Θ(vt)⇔ ∃α, β, t0 > 0 such that ∀t ≥ t0, αvt ≤ ut ≤ βvt.
The uniform average (θ̄t, φ̄t) def = 1t ∑t−1 s=0(θs, φs) of the simultaneous updates (resp. the alternating updates) diverges (resp. converges to 0) as,
Simultaneous: θ̄2t +φ̄ 2 t = Θ
( θ20 + φ 2 0
η2t2 (1 + η2)t
) , Alternating: θ̄2t +φ̄ 2 t = Θ ( θ20 + φ 2 0
η2t2
) . (13)
This sublinear convergence result, proved in §B, underlines the benefits of averaging when the sequence of iterates is bounded (i.e. for alternating update rule). When the sequence of iterates is not bounded (i.e. for simultaneous updates) averaging fails to ensure convergence. This theorem also shows how alternating updates may have better convergence properties than simultaneous updates.
5Wasserstein GAN (WGAN) proposed by Arjovsky et al. (2017) boils down to the following minimax formulation: minθ∈Θ maxϕ∈Φ,||Dϕ||L≤1 Ex∼p[Dϕ(x)]− Ex′∼qθ [Dϕ(x ′)].

heading: 3.2 EXTRAPOLATION
text: Another technique used in the variational inequality literature to prevent oscillations is extrapolation. This concept is anterior to the extragradient method since Korpelevich (1976) mentions that the idea of extrapolated “prices” to give “stability” had been already formulated by Polyak (1963, Chap. II). The idea behind this technique is to compute the gradient at an (extrapolated) point different from the current point from which the update is performed, stabilizing the dynamics:
Compute extrapolated point: ωt+1/2 = PΩ[ωt − ηF (ωt)] , (14) Perform update step: ωt+1 = PΩ[ωt − ηF (ωt+1/2)] . (15)
Note that, even in the unconstrained case, this method is intrinsically different from Nesterov’s momentum6 (Nesterov, 1983, Eq. 2.2.9) because of this lookahead step for the gradient computation:
Nesterov’s method: ωt+1/2 = ωt − ηF (ωt) , ωt+1 = ωt+1/2 + β(ωt+1/2 − ωt) . (16)
Nesterov’s method does not converge when trying to optimize (10). One intuition of why extrapolation has better convergence properties than the standard gradient method comes from Euler’s integration framework. Indeed, to first order, we have ωt+1/2 ≈ ωt+1 + o(η) and consequently, the update step (15) can be interpreted as a first order approximation to an implicit method step:
Implicit step: ωt+1 = ωt − ηF (ωt+1) . (17)
Implicit methods are known to be more stable and to benefit from better convergence properties (Atkinson, 2003) than explicit methods, e.g., in §B.2 we show that (17) on (10) converges for any η. Though, they are usually not practical since they require to solve a potentially non-linear system at each step. Going back to the simplified WGAN toy example (10) from §3.1, we get the following update rules:
Implicit: { θt+1 = θt − ηφt+1 φt+1 = φt + ηθt+1 , Extrapolation: { θt+1 = θt − η(φt + ηθt) φt+1 = φt + η(θt − ηφt) . (18)
In the following proposition, we see that for η < 1, the respective convergence rates of the implicit method and extrapolation are highly similar. Keeping in mind that the latter has the major advantage of being more practical, this proposition clearly underlines the benefits of extrapolation. Note that Prop. 1 and 2 generalize to general unconstrained bilinear game (more details and proof in §B.3),
Proposition 2. The squared norm of the iterates N2t def = θ2t + φ 2 t , where the update rule of θt and φt are defined in (18), decreases geometrically for any η < 1 as,
Implicit: N2t+1 = ( 1− η2 + η4 +O(η6) ) N2t , Extrapolation: N 2 t+1 = (1− η2 + η4)N2t . (19)

heading: 3.3 EXTRAPOLATION FROM THE PAST
text: One issue with extrapolation is that the algorithm “wastes” a gradient (14). Indeed we need to compute the gradient at two different positions for every single update of the parameters. We thus propose a technique that we call extrapolation from the past that only requires a single gradient computation per update. The idea is to store and re-use the extrapolated gradient for the extrapolation:
Extrapolation from the past: ωt+1/2 = PΩ[ωt − ηF (ωt−1/2)] (20) Perform update step: ωt+1 = PΩ[ωt − ηF (ωt+1/2)] and store: F (ωt+1/2) (21)
The same update scheme was proposed by Chiang et al. (2012, Alg. 1) in the context of online convex optimization and generalized by Rakhlin and Sridharan (2013) for general online learning. Without projection, (20) and (21) reduce to the optimistic mirror descent described by Daskalakis et al. (2018):
Optimistic mirror descent (OMD): ωt+1/2 = ωt−1/2 − 2ηF (ωt−1/2) + ηF (ωt−3/2) (22)
We rediscovered this technique from a different perspective: it was motivated by VIP and inspired from the extragradient method. Using the VIP point of view, we are able to prove a linear convergence rate for extrapolation from the past (see details and proof of Theorem 1 in §B.4). We also provide results for a stochastic version in §4. In comparison to the results from Daskalakis et al. (2018) that
6Sutskever (2013, §7.2) showed the equivalence between “standard momentum” and Nesterov’s formulation.
−1 0 1 2 θ
−1.0
−0.5
0.0
0.5
1.0
φ
Start
Adam with γ = 0.01 Gradient method γ = 0.1 Averaging γ = 2.0
Extrapolation from the past γ = 0.5 Extrapolation γ = 0.6
Figure 1: Comparison of the basic gradient method (as well as Adam) with the techniques presented in §3 on the optimization of (9). Only the algorithms advocated in this paper (Averaging, Extrapolation and Extrapolation from the past) converge quickly to the solution. Each marker represents 20 iterations. We compare these algorithms on a non-convex objective in §G.1.
Algorithm 1 AvgSGD Let ω0 ∈ Ω for t = 0 . . . T − 1 do ξt ∼ P (mini-batch) dt ← F (ωt, ξt) ωt+1 ← PΩ[ωt − ηtdt]
end for Return ω̄T ← ∑T−1 t=0 ηtωt∑T−1 t=0 ηt
Algorithm 2 AvgExtraSGD for t = 0 . . . T − 1 do ξt, ξ ′ t ∼ P (mini-batches)
dt ← F (ωt, ξt) ω′t ← PΩ[ωt − ηtdt] d′t ← F (ω′t, ξ′t) ωt+1 ← PΩ[ωt − ηtd′t]
end for Return ω̄T ← ∑T−1 t=0 ηtω ′ t∑T−1
t=0 ηt
Algorithm 3 AvgPastExtraSGD Let ω0 ∈ Ω for t = 0 . . . T − 1 do ξt ∼ P (mini-batch) ω′t ← PΩ[ωt − ηtdt−1] dt ← F (ω′t, ξt) ωt+1 ← PΩ[ωt − ηtdt]
end for Return ω̄T ← ∑T−1 t=0 ηtω ′ t∑T−1
t=0 ηt
Figure 2: Three variants of SGD computing T updates, using the techniques introduced in §3.
hold only for a bilinear objective, we provide a faster convergence rate (linear vs sublinear) on the last iterate for a general (strongly monotone) operator F and any projection on a convex Ω. One thing to notice is that the operator of a bilinear objective is not strongly monotone, but in that case one can use the standard extrapolation method (14) which converges linearly for a (constrained or not) bilinear game (Tseng, 1995, Cor. 3.3). Theorem 1 (Linear convergence of extrapolation from the past). If F is µ-strongly monotone (see §A for the definition of strong monotonicity) and L-Lipschitz, then the updates (20) and (21) with η = 14L provide linearly converging iterates,
‖ωt − ω∗‖22 ≤ (
1− µ 4L
)t ‖ω0 − ω∗‖22 , ∀t ≥ 0 . (23)

heading: 4 OPTIMIZATION OF VIP WITH STOCHASTIC GRADIENTS
text: In this section, we consider extensions of the techniques presented in §3 to the context of a stochastic operator, i.e., we no longer have access to the exact gradient F (ω) but to an unbiased stochastic estimate of it, F (ω, ξ), where ξ ∼ P and F (ω) := Eξ∼P [F (ω, ξ)]. It is motivated by GAN training where we only have access to a finite sample estimate of the expected gradient, computed on a mini-batch. For GANs, ξ is a mini-batch of points coming from the true data distribution p and the generator distribution qθ.
For our analysis, we require at least one of the two following assumptions on the stochastic operator: Assumption 1. Bounded variance by σ2: Eξ[‖F (ω)− F (ω, ξ)‖2] ≤ σ2 , ∀ω ∈ Ω . Assumption 2. Bounded expected squared norm by M2: Eξ[‖F (ω, ξ)‖2] ≤M2, ∀ω ∈ Ω. Assump. 1 is standard in stochastic variational analysis, while Assump. 2 is a stronger assumption sometimes made in stochastic convex optimization. To illustrate how strong Assump. 2 is, note that it does not hold for an unconstrained bilinear objective like in our example (10) in §3. It is thus mainly reasonable for bounded constraint sets. Note that in practice we have σ M . We now present and analyze three algorithms that are variants of SGD that are appropriate to solve (VIP). The first one Alg. 1 (AvgSGD) is the stochastic extension of the gradient method for solving (VIP); Alg. 2 (AvgExtraSGD) uses extrapolation and Alg. 3 (AvgPastExtraSGD) uses extrapolation from the past. A fourth variant that re-use the mini-batch for the extrapolation step (ReExtraSGD, Alg. 5) is described in §D. These four algorithms return an average of the iterates (typical in stochastic setting). The proofs of the theorems presented in this section are in §F.
To handle constraints such as parameter clipping (Arjovsky et al., 2017), we gave a projected version of these algorithms, where PΩ[ω′] denotes the projection of ω′ onto Ω (see §A). Note that when Ω = Rd, the projection is the identity mapping (unconstrained setting). In order to prove the convergence of these four algorithms, we will assume that F is monotone:
(F (ω)− F (ω′))>(ω − ω′) ≥ 0 ∀ω,ω′ ∈ Ω . (24) If F can be written as (6), it implies that the cost functions are convex.7 Note however that general GANs parametrized with neural networks lead to non-monotone VIPs. Assumption 3. F is monotone and Ω is a compact convex set, such that maxω,ω′∈Ω ‖ω−ω′‖2 ≤ R2. In that setting the quantity g(ω∗) := maxω∈Ω F (ω)>(ω∗ − ω) is well defined and is equal to 0 if and only if ω∗ is a solution of (VIP). Moreover, if we are optimizing a zero-sum game, we have ω = (θ,ϕ), Ω = Θ × Φ and F (θ,ϕ) = [∇θL(θ,ϕ) −∇ϕL(θ,ϕ)]>. Hence, the quantity h(θ∗,ϕ∗) := maxϕ∈Φ L(θ∗,ϕ) −minθ∈Θ L(θ,ϕ∗) is well defined and equal to 0 if and only if (θ∗,ϕ∗) is a Nash equilibrium of the game. The two functions g and h are called merit functions (more details on the concept of merit functions in §C). In the following, we call,
Err(ω) def =  max(θ′,ϕ′)∈ΩL(θ,ϕ ′)− L(θ′,ϕ) if F (θ,ϕ) = [∇θL(θ,ϕ) −∇ϕL(θ,ϕ)]>
max ω′∈Ω
F (ω′)>(ω − ω′) otherwise. (25)
Averaging. Alg. 1 (AvgSGD) presents the stochastic gradient method with averaging, which reduces to the standard (simultaneous) SGD updates for the two-player games used in the GAN literature, but returning an average of the iterates. Theorem 2. Under Assump. 1, 2 and 3, SGD with averaging (Alg. 1) with a constant step-size gives,
E[Err(ω̄T )] ≤ R2
2ηT + η
M2 + σ2
2 where ω̄T
def =
1
T T−1∑ t=0 ωt , ∀T ≥ 1 . (26)
Thm. 2 uses a similar proof as (Nemirovski et al., 2009). The constant term η(M2 + σ2)/2 in (26) is called the variance term. This type of bound is standard in stochastic optimization. We also provide in §F a similar Õ(1/
√ t) rate with an extra log factor when ηt = η√t . We show that this variance term
is smaller than the one of SGD with prediction method (Yadav et al., 2018) in §E.
Extrapolations. Alg. 2 (AvgExtraSGD) adds an extrapolation step compared to Alg. 1 in order to reduce the oscillations due to the game between the two players. A theoretical consequence is that it has a smaller variance term than (26). As discussed previously, Assump. 2 made in Thm. 2 for the convergence of Alg. 1 is very strong in the unbounded setting. One advantage of SGD with extrapolation is that Thm. 3 does not require this assumption. Theorem 3. (Juditsky et al., 2011, Thm. 1) Under Assump. 1 and 3, if Eξ[F ] is L-Lipschitz, then SGD with extrapolation and averaging (Alg. 2) using a constant step-size η ≤ 1√
3L gives,
E[Err(ω̄T )] ≤ R2
ηT +
7 2 ησ2 where ω̄T def = 1 T T−1∑ t=0 ω′t , ∀T ≥ 1 . (27)
Since in practice σ M , the variance term in (27) is significantly smaller than the one in (26). To summarize, SGD with extrapolation provides better convergence guarantees but requires two gradient computations and samples per iteration. This motivates our new method, Alg. 3 (AvgPastExtraSGD) which uses extrapolation from the past and achieves the best of both worlds (in theory). Theorem 4. Under Assump. 1 and 3, if Eξ[F ] is L-Lipschitz then SGD with extrapolation from the past using a constant step-size η ≤ 1
2 √ 3L , gives that the averaged iterates converge as,
E[Err(ω̄T )] ≤ R2
ηT +
13
2 ησ2 where ω̄T
def =
1
T T−1∑ t=0 ω′t ∀T ≥ 1 . (28)
The bound is similar to the one provided in Thm. 3 but each iteration of Alg. 3 is computationally half the cost of an iteration of Alg. 2.
7The convexity of the cost functions in (3) is a necessary condition (not sufficient) for the operator to be monotone. In the context of a zero-sum game, the convexity of the cost functions is a sufficient condition.

heading: 5 COMBINING THE TECHNIQUES WITH ESTABLISHED ALGORITHMS
text: In the previous sections, we presented several techniques that converge for stochastic monotone operators. These techniques can be combined in practice with existing algorithms. We propose to combine them to two standard algorithms used for training deep neural networks: the Adam optimizer (Kingma and Ba, 2015) and the SGD optimizer (Robbins and Monro, 1951). For the Adam optimizer, there are several possible choices on how to update the moments. This choice can lead to different algorithms in practice: for example, even in the unconstrained case, our proposed Adam with extrapolation from the past (Alg. 4) is different from Optimistic Adam (Daskalakis et al., 2018) (the moments are updated differently). Note that in the case of a two-player game (3), the previous convergence results can be generalized to gradient updates with a different step-size for each player by simply rescaling the objectives LG and LD by a different scaling factor. A detailed pseudo-code for Adam with extrapolation step (Extra-Adam) is given in Algorithm 4. Note that our interest regarding this algorithm is practical and that we do not provide any convergence proof.
Algorithm 4 Extra-Adam: proposed Adam with extrapolation step. input: step-size η, decay rates for moment estimates β1, β2, access to the stochastic gradients ∇`t(·) and to the projection PΩ[·] onto the constraint set Ω, initial parameter ω0, averaging scheme (ρt)t≥1 for t = 0 . . . T − 1 do
Option 1: Standard extrapolation. Sample new mini-batch and compute stochastic gradient: gt ← ∇`t(ωt) Option 2: Extrapolation from the past Load previously saved stochastic gradient: gt = ∇`t−1/2(ωt−1/2) Update estimate of first moment for extrapolation: mt−1/2 ← β1mt−1 + (1− β1)gt Update estimate of second moment for extrapolation: vt−1/2 ← β2vt−1 + (1− β2)g2t Correct the bias for the moments: m̂t−1/2 ← mt−1/2/(1− β2t−11 ), v̂t−1/2 ← vt−1/2/(1− β 2t−1 2 ) Perform extrapolation step from iterate at time t: ωt−1/2 ← PΩ[ωt − η m̂t−1/2√ v̂t−1/2+ ] Sample new mini-batch and compute stochastic gradient: gt+1/2 ← ∇`t+1/2(ωt+1/2) Update estimate of first moment: mt ← β1mt−1/2 + (1− β1)gt+1/2 Update estimate of second moment: vt ← β2vt−1/2 + (1− β2)g2t+1/2 Compute bias corrected for first and second moment: m̂t ← mt/(1− β2t1 ), v̂t ← vt/(1− β2t2 ) Perform update step from the iterate at time t: ωt+1 ← PΩ[ωt − η m̂t√v̂t+ ]
end for Output: ωT−1/2, ωT or ω̄T = ∑T−1 t=0 ρt+1ωt+1/2/ ∑T−1 t=0 ρt+1 (see (8) for online averaging)

heading: 6 RELATED WORK
text: The extragradient method is a standard algorithm to optimize variational inequalities. This algorithm has been originally introduced by Korpelevich (1976) and extended by Nesterov (2007) and Nemirovski (2004). Stochastic versions of the extragradient have been recently analyzed (Juditsky et al., 2011; Yousefian et al., 2014; Iusem et al., 2017) for stochastic variational inequalities with bounded constraints. A linearly convergent variance reduced version of the stochastic gradient method has been proposed by Palaniappan and Bach (2016) for strongly monotone variational inequalities. Extrapolation can also be related to optimistic methods (Chiang et al., 2012; Rakhlin and Sridharan, 2013) proposed in the online learning literature (see more details in §3.3). Interesting non-convex results were proved, for a new notion of regret minimization, by Hazan et al. (2017) and in the context of online learning for GANs by Grnarova et al. (2018).
Several methods to stabilize GANs consist in transforming a zero-sum formulation into a more general game that can no longer be cast as a saddle point problem. This is the case of the non-saturating formulation of GANs (Goodfellow et al., 2014; Fedus et al., 2018), the DCGANs (Radford et al., 2016), the gradient penalty8 for WGANs (Gulrajani et al., 2017). Yadav et al. (2018) propose an optimization method for GANs based on AltSGD using an additional momentum-based step on the generator. Daskalakis et al. (2018) proposed a method inspired from game theory. Li et al. (2017)
8The gradient penalty is only added to the discriminator cost function. Since this gradient penalty depends also on the generator, WGAN-GP cannot be cast as a SP problem and is actually a non-zero sum game.
suggest to dualize the GAN objective to reformulate it as a maximization problem and Mescheder et al. (2017) propose to add the norm of the gradient in the objective to get a better signal. Gidel et al. (2019) analyzed a generalization of the bilinear example (9) with a focus put on the effect of momentum on this problem. They do not consider extrapolation (see §B.3 for more details). Unrolling steps (Metz et al., 2017) can be confused with extrapolation but is fundamentally different: the perspective is to try to approximate the “true generator objective function" unrolling for K steps the updates of the discriminator and then updating the generator.
Regarding the averaging technique, some recent work appear to have already successfully used geometric averaging (7) for GANs in practice, but only briefly mention it (Karras et al., 2018; Mescheder et al., 2018). By contrast, the present work formally motivates and justifies the use of averaging for GANs by relating them to the VIP perspective, and sheds light on its underlying intuitions in §3.1. Subsequent to our first preprint, Yazıcı et al. (2019) explored averaging empirically in more depth, while Mertikopoulos et al. (2019) also investigated extrapolation, providing asymptotic convergence results (i.e. without any rate of convergence) in the context of coherent saddle point. The coherence assumption is slightly weaker than monotonicity.

heading: 7 EXPERIMENTS
text: Our goal in this experimental section is not to provide new state-of-the art results with architectural improvements or a new GAN formulation, but to show that using the techniques (with theoretical guarantees in the monotone case) that we introduced earlier allows us to optimize standard GANs in a better way. These techniques, which are orthogonal to the design of new formulations of GAN optimization objectives, and to architectural choices, can potentially be used for the training of any type of GAN. We will compare the following optimization algorithms: baselines are SGD and Adam using either simultaneous updates on the generator and on the discriminator (denoted SimAdam and SimSGD) or k updates on the discriminator alternating with 1 update on the generator (denoted AltSGD{k} and AltAdam{k}).9 Variants that use extrapolation are denoted ExtraSGD (Alg. 2) and ExtraAdam (Alg. 4). Variants using extrapolation from the past are PastExtraSGD (Alg. 3) and PastExtraAdam (Alg. 4). We also present results using as output the averaged iterates, adding Avg as a prefix of the algorithm name when we use (uniform) averaging.
7.1 BILINEAR SADDLE POINT (STOCHASTIC)
We first test the various stochastic algorithms on a simple (n = 103, d = 103) finite sum bilinear objective (a monotone operator) constrained to [−1, 1]d:
1
n n∑ i=1 ( θ>M (i)ϕ+ θ>a(i) +ϕ>b(i) ) (29)
solved by (θ∗,ϕ∗) s.t. { M̄ϕ∗ = −ā M̄Tθ∗ = −b̄ ,
where ā := 1n ∑n i=1 a (i), b̄ := 1n ∑n i=1 b
(i) and M̄ := 1n ∑n i=1M (i). The matrices M (i)kj , a (i) k , b (i) k ; 1 ≤ i ≤ n, 1 ≤ j, k ≤ d were randomly generated, but ensuring that (θ∗,ϕ∗) belongs to [−1, 1]d. Results are shown in Fig. 3. We can see that AvgAltSGD1 and AvgPastExtraSGD perform the best on this task.

heading: 7.2 WGAN AND WGAN-GP ON CIFAR10
text: We evaluate the proposed techniques in the context of GAN training, which is a challenging stochastic optimization problem where the objectives of both players are non-convex. We propose to evaluate the Adam variants of the different optimization algorithms (see Alg. 4 for Adam with extrapolation) by training two different architectures on the CIFAR10 dataset (Krizhevsky and Hinton, 2009). First, we consider a constrained zero-sum game by training the DCGAN architecture (Radford et al.,
9In the original WGAN paper (Arjovsky et al., 2017), the authors use k = 5.
2016) with the WGAN objective and weight clipping as proposed by Arjovsky et al. (2017). Then, we compare the different methods on a state-of-the-art architecture by training a ResNet with the WGAN-GP objective similar to Gulrajani et al. (2017). Models are evaluated using the inception score (IS) (Salimans et al., 2016) computed on 50,000 samples. We also provide the FID (Heusel et al., 2017) and the details on the ResNet architecture in §G.3.
For each algorithm, we did an extensive search over the hyperparameters of Adam. We fixed β1 = 0.5 and β2 = 0.9 for all methods as they seemed to perform well. We note that as proposed by Heusel et al. (2017), it is quite important to set different learning rates for the generator and discriminator. Experiments were run with 5 random seeds for 500,000 updates of the generator.
Tab. 1 reports the best IS achieved on these problems by each considered method. We see that the techniques of extrapolation and averaging consistently enable improvements over the baselines (see §G.5 for more experiments on averaging). Fig. 4 shows training curves for each method (for their best performing learning rate), as well as samples from a ResNet generator trained with ExtraAdam on a WGAN-GP objective. For both tasks, using an extrapolation step and averaging with Adam (ExtraAdam) outperformed all other methods. Combining ExtraAdam with averaging yields results that improve significantly over the previous state-of-the-art IS (8.2) and FID (21.7) on CIFAR10 as reported by Miyato et al. (2018) (see Tab. 5 for FID). We also observed that methods based on extrapolation are less sensitive to learning rate tuning and can be used with higher learning rates with less degradation; see §G.4 for more details.

heading: 8 CONCLUSION
text: We newly addressed GAN objectives in the framework of variational inequality. We tapped into the optimization literature to provide more principled techniques to optimize such games. We leveraged these techniques to develop practical optimization algorithms suitable for a wide range of GAN training objectives (including non-zero sum games and projections onto constraints). We experimentally verified that this could yield better trained models, improving the previous state of the art. The presented techniques address a fundamental problem in GAN training in a principled way, and are orthogonal to the design of new GAN architectures and objectives. They are thus likely to be widely applicable, and benefit future development of GANs.

heading: ACKNOWLEDGMENTS.
text: This research was partially supported by the Canada CIFAR AI Chair Program, the Canada Excellence Research Chair in “Data Science for Realtime Decision-making”, by the NSERC Discovery Grant RGPIN-2017-06936 and by a Google Focused Research award. Gauthier Gidel would like to acknowledge Benoît Joly and Florestan Martin-Baillon for bringing a fresh point of view on the proof of Proposition 1.

heading: A DEFINITIONS
text: In this section, we recall usual definitions and lemmas from convex analysis. We start with the definitions and lemmas regarding the projection mapping.

heading: A.1 PROJECTION MAPPING
text: Definition 1. The projection PΩ onto Ω is defined as,
PΩ(ω ′) ∈ arg min ω′∈Ω ‖ω − ω′‖22 . (30)
When Ω is a convex set, this projection is unique. This is a consequence of the following lemma that we will use in the following sections: the non-expansiveness of the projection onto a convex set.
Lemma 1. Let Ω a convex set, the projection mapping PΩ : Rd → Ω is nonexpansive, i.e.,
‖PΩ(ω)− PΩ(ω′)‖2 ≤ ‖ω − ω′‖2 , ∀ω,ω′ ∈ Ω . (31)
This is standard convex analysis result which can be found for instance in (Boyd and Vandenberghe, 2004). The following lemma is also standard in convex analysis and its proof uses similar arguments as the proof of Lemma 1.
Lemma 2. Let ω ∈ Ω and ω+ def= PΩ(ω + u), then for all ω′ ∈ Ω we have,
‖ω+ − ω′‖22 ≤ ‖ω − ω′‖22 + 2u>(ω+ − ω′)− ‖ω+ − ω‖22 . (32)
Proof of Lemma 2. We start by simply developing,
‖ω+ − ω′‖22 = ‖(ω+ − ω) + (ω − ω′)‖22 = ‖ω − ω′‖22 + 2(ω+ − ω)>(ω − ω′) + ‖ω+ − ω‖22 = ‖ω − ω′‖22 + 2(ω+ − ω)>(ω+ − ω′)− ‖ω+ − ω‖22 .
Then since ω+ is the projection onto the convex set Ω of ω + u, we have that (ω+ − (ω + u))>(ω+ − ω′) ≤ 0 , ∀ω′ ∈ Ω, leading to the result of the Lemma.

heading: A.2 SMOOTHNESS AND MONOTONICITY OF THE OPERATOR
text: Another important property used is the Lipschitzness of an operator.
Definition 2. A mapping F : Rp → Rd is said to be L-Lipschitz if,
‖F (ω)− F (ω′)‖2 ≤ L‖ω − ω′‖2 , ∀ω,ω′ ∈ Ω . (33)
In this paper, we also use the notion of strong monotonicity, which is a generalization for operators of the notion of strong convexity. Let us first recall the definition of the latter,
Definition 3. A differentiable function f : Ω→ R is said to be µ-strongly convex if
f(ω) ≥ f(ω′) +∇f(ω′)>(ω − ω′) + µ 2 ‖ω − ω′‖22 ∀ω,ω′ ∈ Ω . (34)
Definition 4. A function (θ,ϕ) 7→ L(θ,ϕ) is said convex-concave if L(·,ϕ) is convex for all ϕ ∈ Φ and L(θ, ·) is concave for all θ ∈ Θ. An L is said to be µ-strongly convex-concave if (θ,ϕ) 7→ L(θ,ϕ)− µ2 ‖θ‖ 2 2 + µ 2 ‖ϕ‖ 2 2 is convex-concave.
If a function f (resp. L) is strongly convex (resp. strongly convex-concave), its gradient∇f (resp. [∇θL −∇ϕL]>) is strongly monotone, i.e.,
Definition 5. For µ > 0, an operator F : Ω→ Rd is said to be µ-strongly monotone if
(F (ω)− F (ω′))>(ω − ω′) ≥ µ‖ω − ω′‖22 . (35)

heading: B GRADIENT METHODS ON UNCONSTRAINED BILINEAR GAMES
text: In this section, we will prove the results provided in §3, namely Proposition 1, Proposition 2 and Theorem 1. For Proposition 1 and 2, let us recall the context. We wanted to derive properties of some gradient methods on the following simple illustrative example
min θ∈R max φ∈R
θ · φ (36)

heading: B.1 PROOF OF PROPOSITION 1
text: Let us first recall the proposition:
Proposition’ 1. The simultaneous iterates diverge geometrically and the alternating iterates defined in (11) are bounded but do not converge to 0 as
Simultaneous: θ2t+1 + φ 2 t+1 = (1 + η 2)(θ2t + φ 2 t ) , Alternating: θ 2 t + φ 2 t = Θ(θ 2 0 + φ 2 0) (37)
where ut = Θ(vt)⇔ ∃α, β, t0 > 0 such that ∀t ≥ t0, αvt ≤ ut ≤ βvt.
The uniform average (θ̄t, φ̄t) def = 1t ∑t−1 s=0(θs, φs) of the simultaneous updates (resp. the alternating updates) diverges (resp. converges to 0) as,
Simultaneous: θ̄2t +φ̄ 2 t = Θ
( θ20 + φ 2 0
η2t2 (1 + η2)t
) , Alternating: θ̄2t +φ̄ 2 t = Θ ( θ20 + φ 2 0
η2t2
) . (38)
Proof. Let us start with the simultaneous update rule:{ θt+1 = θt − ηφt φt+1 = φt + ηθt .
(39)
Then we have,
θ2t+1 + φ 2 t+1 = (θt − ηφt)2 + (φt + ηθt)2 (40)
= (1 + η2)(θ2t + φ 2 t ) . (41)
The update rule (39) also gives us, { ηφt = θt − θt+1 ηθt = φt+1 − φt .
(42)
Summing (42) for 0 ≤ t ≤ T − 1 to get telescoping sums, we get
(η2T 2)(φ̄2T + θ̄ 2 T ) = (θ0 − θT )2 + (φ0 − φT )2 (43)
= ((1 + η2)T + 1)(θ20 + φ 2 0)− 2θ0θT − 2φ0φT (44) = Θ ( (1 + η2)T ((θ20 + φ 2 0) ) . (45)
Let us continue with the alternating update rule{ θt+1 = θt − ηφt φt+1 = φt + ηθt+1 = φt + η(θt − ηφt)
(46)
Then we have, [ θt+1 φt+1 ] = [ 1 −η η 1− η2 ] [ θt φt ] . (47)
By simple linear algebra, for η < 2, the matrix M def= [ 1 −η η 1− η2 ] has two complex conjugate
eigenvalues which are
λ± = 1− η η ± i
√ 4− η2
2 (48)
and their squared magnitude is equal to det(M) = 1− η2 + η2 = 1. We can diagonalize M meaning that there exists P an invertible matrix such that M = P−1 diag(λ+, λ−)P . Then, we have[
θt φt
] = M t [ θ0 φ0 ] = P−1 diag(λt+, λ t −)P [ θ0 φ0 ] (49)
and consequently,
θ2t + φ 2 t = ∥∥∥∥∥ [ θt φt ]∥∥∥∥∥ 2
C
= ∥∥∥∥∥P−1 diag(λt+, λt−)P [ θ0 φ0 ]∥∥∥∥∥ 2
C
≤ ‖P−1‖‖P‖(θ20 + φ20) (50)
where ‖ · ‖C is the norm in C2 and ‖P‖ := maxu∈C2 ‖Pu‖C‖u‖C is the induced matrix norm. The same way we have,
θ20 + φ 2 0 = ∥∥∥∥∥M−t [ θt φt ]∥∥∥∥∥ 2
C
= ∥∥∥∥∥P−1 diag(λ−t+ , λ−t− )P [ θt φt ]∥∥∥∥∥ 2
C
≤ ‖P−1‖‖P‖(θ2t + φ2t ) (51)
Hence, if θ20 + φ 2 0 > 0, the sequence (θt, φt) is bounded but do not converge to 0. Moreover the update rule gives us,
{ ηφt = θt − θt+1 ηθt = φt − φt−1 ⇒  η T T−1∑ t=0 φt = θ0 − θT T η
T T−1∑ t=0 θt = φT−1 − φ0 + ηθ0 T ⇒
 φ̄T = θ0 − θT ηT θ̄T = φT−1 − φ0 + ηθ0
ηT
(52)
Consequently, since θ2t + φ 2 t = Θ(θ 2 0 + φ 2 0),√
θ̄2t + φ̄ 2 t = Θ
(√ θ20 + φ 2 0
ηt
) (53)
B.2 IMPLICIT AND EXTRAPOLATION METHOD
In this section, we will prove a slightly more precise proposition than Proposition 2,
Proposition’ 2. The squared norm of the iterates N2t def = θ2t + φ 2 t , where the update rule of θt and φt is defined in (18), decrease geometrically for any 0 < η < 1 as,10
Implicit: N2t+1 = N2t
1 + η2 , Extrapolation: N2t+1 = (1− η2 + η4)N2t , ∀t ≥ 0 (54)
Proof. Let us recall the update rule for the implicit method{ θt+1 = θt − ηφt+1 φt+1 = φt + ηθt+1 ⇒ { (1 + η2)θt+1 = θt − ηφt (1 + η2)φt+1 = φt + ηθt
(55)
Then,
(1 + η2)2(θ2t+1 + φ 2 t+1) = (θt − ηφt)2 + (φt + ηθt)2 (56)
= θ2t + φ 2 t + +η 2(θ2t + φ 2 t ), (57)
implying that
θ2t+1 + φ 2 t+1 =
θ2t + φ 2 t
1 + η2 , (58)
10Note that the relationship (54) holds actually for any η for the implicit method, and thus the decrease is geometric for any non-zero step size.
which is valid for any η.
For the extrapolation method, we have the update rule{ θt+1 = θt − η(φt + ηθt) φt+1 = φt + η(θt − ηφt)
(59)
Implying that,
θ2t+1 + φ 2 t+1 = (θt − η(φt + ηθt))2 + (φt + η(θt − ηφt))2 (60)
= θ2t + φ 2 t − 2η2(θ2 + φ2) + η2((θt − ηφt)2 + (φt + ηθt)2) (61)
= (1− η2 + η4)(θ2t + φ2t ) (62)

heading: B.3 GENERALIZATION TO GENERAL UNCONSTRAINED BILINEAR OBJECTIVE
text: In this section, we will show how to simply extend the study of the algorithm of interest provided in §3 on the general unconstrained bilinear example,
min θ∈Rd max ϕ∈Rp
θ>Aϕ− b>θ − c>ϕ (63)
where, A ∈ Rd×p, b ∈ Rd and c ∈ Rp. The only assumption we will make is that this problem is feasible which is equivalent to say that there exists a solution (θ∗,ϕ∗) to the system{
Aϕ∗ = b A>θ∗ = c . (64)
In this case, we can re-write (63) as
min θ∈Rd max ϕ∈Rp
(θ − θ∗)>A(ϕ−ϕ∗) + c (65)
where c := −θ∗>Aϕ∗ is a constant that does not depend on θ and ϕ. First, let us show that we can reduce the study of simultaneous, alternating, extrapolation and implicit updates rules for (63) to the study of the respective unidimensional updates (11) and (18).
This reduction has already been proposed by Gidel et al. (2019). For completeness, we reproduce here similar arguments. The following lemma is a bit more general than the result provided by Gidel et al. (2019). It states that the study of a wide class of unconstrained first order method on (63) can be reduced to the study of the method on (36), with potentially rescaled step-sizes.
Before explicitly stating the lemma, we need to introduce a bit of notation to encompass easily our several methods in a unified way. First, we let ωt := (θt,ϕt), where the index t here is a more general index which can vary more often than the one in §3. For example, for the extrapolation method, we could consider ω1 = ω′0+1/2 and ω2 = ω ′ 1, where ω
′ was the sequence defined for the extragradient. For the alternated updates, we can consider ω1 = (θ′1,ϕ ′ 0) and ω2 = (θ ′ 1,ϕ ′ 1) (this also defines θ2 = θ′1), where θ ′ and ϕ′ were the sequences originally defined for alternated updates. We are thus ready to state the lemma.
Lemma 3. Let us consider the following very general class of first order methods on (63), i.e.,
θt ∈ θ0 + span(Fθ(ω0), . . . , Fθ(ωt)) , ∀t ∈ N , ϕt ∈ ϕ0 + span(Fϕ(ω0), . . . , Fϕ(ωt)) , ∀t ∈ N ,
(66)
where ωt := (θt,ϕt) and Fθ(ωt) := Aϕt − b, Fϕ(ωt) = A>θt − c. Then, we have
θt = U >(θ̃t − θ∗) and ϕt = V >(ϕ̃t −ϕ∗) , (67)
whereA = UDV > (SVD decomposition) and the couples ([θ̃t]i, [ϕ̃]i)1≤i≤r follow the update rule of the same method on a unidimensional problem (36). In particular, for our methods of interest, the couples ([θ̃t]i, [ϕ̃]i)1≤i≤r follow the same update rule with a respective step-size σiη, where σi are the singular values on the diagonal ofD.
Proof. Our general class of first order methods can be written with the following update rules:
θt+1 = θ0 + t+1∑ s=0 λstA(ϕs −ϕ∗)
ϕt+1 = ϕ0 + t+1∑ s=0 µstA >(θs − θ∗) ,
where λit, µit ∈ R , 0 ≤ i ≤ t + 1. We allow the dependence on t for the algorithm coefficients λ and µ (for example, the alternating rule would zero out some of the coefficients depending on whether we are updating θ or ϕ at the current iteration). Notice also that if both λ(t+1)t and µ(t+1)t are non-zero, we have an implicit scheme.
Thus, using the SVD ofA = UDV >, we get
U>(θt+1 − θ∗) = U>(θ0 − θ∗) + t+1∑ s=0 λstDV >(ϕs −ϕ∗)
V >(ϕt+1 −ϕ∗) = V >(ϕ0 −ϕ∗) + t+1∑ s=0 µstD >U>(θs − θ∗) ,
which is equivalent to  θ̃t+1 = θ̃0 + t+1∑ s=0 λstDϕ̃s ϕ̃t+1 = ϕ̃0 + t+1∑ s=0 µstD >θ̃s ,
(68)
whereD is a rectangular matrix with zeros except on a diagonal block of size r. Thus, each coordinate of θ̃t+1 and ϕ̃t+1 are updated independently, reducing the initial problem to r unidimensional problems,  [θ̃t+1]i = [θ̃0]i + t+1∑ s=0 λstσi[ϕ̃s]i [ϕ̃t+1]i = [ϕ̃0]i + t+1∑ s=0 µstσi[θ̃s]i 1 ≤ i ≤ r , (69)
where σ1 ≥ . . . ≥ σr > 0 are the positive diagonal coefficients ofD. Finally, for the coordinate i where the diagonal coefficient of D is equal to 0, we can notice that the sequence ([θ̃t]i, [ϕ̃t]i) is constant. Moreover, we have the freedom to chose any [θ∗]i ∈ R and [ϕ∗]i ∈ R as a coordinate of the solution of (63). We thus set them respectively equal to [θ0]i and [ϕ0]i. The update rule (69) corresponds to the update rule of the general first order method considered on this proof on the unidimensional problem (36).
Note that the only additional restriction is that the coefficients (λst) and (σst) (that are the same for 1 ≤ i ≤ r) are rescaled by the singular values of A. In practice, for our methods of interest with a step-size η, it corresponds to the study of r unidimensional problem with a respective step-size σiη , 1 ≤ i ≤ r.
From this lemma, an extension of Proposition 1 and 2 directly follows to the general unconstrained bilinear objective (63). We note
N2t := dist(θt,Θ ∗)2 + dist(ϕt,Φ ∗)2 , (70)
where (Θ∗,Φ∗) is the set of solutions of (63). The following corollary is divided in two points, the first point is a result from Gidel et al. (2019) (note that the result on the average is a straightforward extension of the one provided in Proposition 1 and was not provided by Gidel et al. (2019)), the second result is new. Very similar asymptotic upper bounds regarding extrapolation and implicit methods can be derived by Tseng (1995) computing the exact values of the constant τ1 and τ2 (and
noticing that τ3 = ∞) introduced in (Tseng, 1995, Eq. 3 & 4) for the unconstrained bilinear case. However, since Tseng (1995) works in a very general setting, the bound are not as tight as ours and his proof technique is a bit more technical. Our reduction above provides here a simple proof for our simple setting.
Corollary 1. • Gidel et al. (2019): The simultaneous iterates diverge geometrically and the alternating iterates are bounded but do not converge to 0 as,
Simultaneous: N2t+1 = (1 + (σmin(A)η) 2)N2t , Alternating: N 2 t = Θ(N 2 0 ) , (71)
where ut = Θ(vt) ⇔ ∃α, β, t0 > 0 such that ∀t ≥ t0, αvt ≤ ut ≤ βvt. The uniform average (θ̄t, φ̄t) def = 1t ∑t−1 s=0(θs, φs) of the simultaneous updates (resp. the alternating updates) diverges (resp. converges to 0) as,
Simultaneous: N̄2t ≤ Θ ( N20 t2 (1 + (σmin(A)η) 2)t ) , Alternating: N̄2t = Θ ( N20 t2 ) .
• Extrapolation and Implicit method: The iterates respectively generated by the update rules (14) and (17) on a bilinear unconstrained problem (63) do converge linearly for any 0 < η < 1σmax(A) at a rate, 11
Implicit: N2t+1 ≤ N2t
1 + (σmin(A)η)2 , ∀t ≥ 0 (72)
Extrapolation: N2t+1 ≤ (1− (σmin(A)η)2 + (σmin(A)η)4)N2t , ∀t ≥ 0 . (73) Particularly, for η = 12σmax(A) we get for the extrapolation method,
Extrapolation: N2t+1 ≤ (1− 18κ ) tN20 , ∀t ≥ 0 . (74)
where κ := σmax(A) 2 σmin(A)2 is the condition number ofA>A.

heading: B.4 EXTRAPOLATION FROM THE PAST FOR STRONGLY CONVEX OBJECTIVES
text: Let us recall what we call projected extrapolation form the past, where we used the notation ω′t = ωt+1/2 for compactness,
Extrapolation from the past: ω′t = PΩ[ωt − ηF (ω′t−1)] (75) Perform update step: ωt+1 = PΩ[ωt − ηF (ω′t)] and store: F (ω′t) (76)
where PΩ[·] is the projection onto the constraint set Ω. An operator F : Ω → Rd is said to be µ-strongly monotone if
(F (ω)− F (ω′))>(ω − ω′) ≥ µ‖ω − ω′‖22 . (77)
If F is strongly monotone, we can prove the following theorem:
Theorem’ 1. If F is µ-strongly monotone (see §A for the definition of strong monotonicity) and L-Lipschitz, then the updates (20) and (21) with η = 14L provide linearly converging iterates,
‖ωt − ω∗‖22 ≤ (
1− µ 4L
)t ‖ω0 − ω∗‖22 , ∀t ≥ 0 . (78)
Proof. In order to prove this theorem, we will prove a slightly more general result, ‖ωt+1 − ω∗‖22 + ‖ω′t−1 − ω′t‖22 ≤ (
1− µ 4L
) (‖ωt − ω∗‖22 + ‖ω′t−1 − ω′t−2‖22) . (79)
with the convention that ω′0 = ω ′ −1 = ω ′ −2. It implies that ‖ωt+1 − ω∗‖22 ≤ ‖ωt+1 − ω∗‖22 + ‖ω′t−1 − ω′t‖22 ≤ (
1− µ 4L
)t ‖ω0 − ω∗‖22 . (80)
Let us first proof three technical lemmas. 11As before, the inequality (73) for the implicit scheme is actually valid for any step-size.
Lemma 4. If F is µ-strongly monotone, we have µ ( ‖ωt − ω∗‖22 − 2‖ω′t − ωt‖22 ) ≤ 2F (ω′t)>(ω′t − ω∗) , ∀ω∗ ∈ Ω∗ . (81)
Proof. By strong monotonicity and optimality of ω∗,
2µ‖ω′t − ω∗‖22 ≤ 2F (ω∗)>(ω′t − ω∗) + 2µ‖ω′t − ω∗‖22 ≤ 2F (ω′t)>(ω′t − ω∗) (82)
and then we use the inequality 2‖ω′t − ω∗‖22 ≥ ‖ωt − ω∗‖22 − 2‖ω′t − ωt‖22 to get the result claimed.
Lemma 5. If F is L-Lipschitz, we have for any ω ∈ Ω,
2ηtF (ω ′ t) >(ω′t − ω) ≤ ‖ωt − ω‖22 − ‖ωt+1 − ω‖22 − ‖ω′t − ωt‖22 + η2tL2‖ω′t−1 − ω′t‖22 . (83)
Proof. Applying Lemma 2 for (ω,u,ω+,ω′) = (ωt,−ηtF (ω′t),ωt+1,ω) and (ω,u,ω+,ω′) = (ωt,−ηtF (ω′t−1),ω′t,ωt+1), we get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t)>(ωt+1 − ω)− ‖ωt+1 − ωt‖22 (84)
and ‖ω′t − ωt+1‖22 ≤ ‖ωt − ωt+1‖22 − 2ηtF (ω′t−1)>(ω′t − ωt+1)− ‖ω′t − ωt‖22 . (85)
Summing (84) and (85) we get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t)>(ωt+1 − ω) (86) − 2ηtF (ω′t−1)>(ω′t − ωt+1)− ‖ω′t − ωt‖22 − ‖ω′t − ωt+1‖22 (87)
= ‖ωt − ω‖22 − 2ηtF (ω′t)>(ω′t − ω)− ‖ω′t − ωt‖22 − ‖ω′t − ωt+1‖22 − 2ηt(F (ω′t−1)− F (ω′t))>(ω′t − ωt+1) . (88)
Then, we can use the Young’s inequality 2a>b ≤ ‖a‖22 + ‖b‖22 to get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t)>(ω′t − ω) + η2t ‖F (ω′t−1)− F (ω′t)‖22 + ‖ω′t − ωt+1‖22 − ‖ω′t − ωt‖22 − ‖ω′t − ωt+1‖22 (89)
= ‖ωt − ω‖22 − 2ηtF (ω′t)>(ω′t − ω) + η2t ‖F (ω′t−1)− F (ω′t)‖22 − ‖ω′t − ωt‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t)>(ω′t − ω) + η2tL2‖ω′t−1 − ω′t‖22 − ‖ω′t − ωt‖22 . (90)
Lemma 6. For all t ≥ 0, if we set ω′−2 = ω′−1 = ω′0 we have
‖ω′t−1 − ω′t‖22 ≤ 4‖ωt − ω′t‖22 + 4η2t−1L2‖ω′t−1 − ω′t−2‖22 − ‖ω′t−1 − ω′t‖22 . (91)
Proof. We start with ‖a+ b‖22 ≤ 2‖a‖2 + 2‖b‖2.
‖ω′t−1 − ω′t‖22 ≤ 2‖ωt − ω′t‖22 + 2‖ωt − ω′t−1‖22 . (92)
Moreover, since the projection is contractive we have that
‖ωt − ω′t−1‖22 ≤ ‖ωt−1 − ηt−1F (ω′t−1)− ωt−1 − ηt−1F (ω′t−2)‖22 (93) = η2t−1‖F (ω′t−1)− F (ω′t−2)‖22 (94) ≤ η2t−1L2‖ω′t−1 − ω′t−2‖22 . (95)
Combining (92) and (95) we get,
‖ω′t−1 − ω′t‖22 = 2‖ω′t−1 − ω′t‖22 − ‖ω′t−1 − ω′t‖22 (96) ≤ 4‖ωt − ω′t‖22 + 4‖ωt − ω′t−1‖22 − ‖ω′t−1 − ω′t‖22 (97) ≤ 4‖ωt − ω′t‖22 + 4η2t−1L2‖ω′t−1 − ω′t−2‖22 − ‖ω′t−1 − ω′t‖22 . (98)
Proof of Theorem 1. Let ω∗ ∈ Ω∗ be an optimal point of (VIP). Combining Lemma 4 and Lemma 5 we get,
ηtµ ( ‖ωt − ω∗‖22 − 2‖ω′t − ωt‖22 ) ≤ ‖ωt−ω∗‖22−‖ωt+1−ω∗‖22+η2tL2‖ω′t−1−ω′t‖22−‖ω′t−ωt‖22
leading to,
‖ωt+1 − ω∗‖22 ≤ (1− ηtµ) ‖ωt − ω∗‖22 + η2tL2‖ω′t−1 − ω′t‖22 − (1− 2ηtµ)‖ω′t − ωt‖22 (99) Now using Lemma 6 we get,
‖ωt+1 − ω∗‖22 ≤ (1− ηtµ) ‖ωt − ω∗‖22 + η2tL2(4η2t−1L2‖ω′t−1 − ω′t−2‖22 − ‖ω′t−1 − ω′t‖22) − (1− 2ηtµ− 4η2tL2)‖ω′t − ωt‖22 (100)
Now with ηt = 14L ≤ 1 4µ we get, ‖ωt+1 − ω∗‖22 ≤ (
1− µ 4L
) ‖ωt − ω∗‖22 + 1
16
( 1
4 ‖ω′t−1 − ω′t−2‖22 − ‖ω′t−1 − ω′t‖22 ) Hence, using the fact that µ4L ≤ 1 4 we get,
‖ωt+1 − ω∗‖22 + 116‖ω ′ t−1 − ω′t‖22 ≤
( 1− µ
4L
)( ‖ωt − ω∗‖22 + 116‖ω ′ t−1 − ω′t−2‖22 ) . (101)

heading: C MORE ON MERIT FUNCTIONS
text: In this section, we will present how to handle an unbounded constraint set Ω with a more refined merit function than (25) used in the main paper. Let F be the continuous operator and Ω be the constraint set associated with the VIP,
find ω∗ ∈ Ω such that F (ω∗)>(ω − ω∗) ≥ 0 , ∀ω ∈ Ω . (VIP) When the operator F is monotone, we have that F (ω∗)>(ω − ω∗) ≤ F (ω)>(ω − ω∗) , ∀ω,ω∗. Hence, in this case (VIP) implies a stronger formulation sometimes called Minty variational inequality (Crespi et al., 2005):
find ω∗ ∈ Ω such that F (ω)>(ω − ω∗) ≥ 0 , ∀ω ∈ Ω . (MVI) This formulation is stronger in the sense that if (MVI) holds for some ω∗ ∈ Ω, then (VIP) holds too. A merit function useful for our analysis can be derived from this formulation. Roughly, a merit function is a convergence measure. More formally, a function g : Ω→ R is called a merit function if g is non-negative such that g(ω) = 0⇔ ω ∈ Ω∗ (Larsson and Patriksson, 1994). A way to derive a merit function from (MVI) would be to use g(ω∗) = supω∈Ω F (ω)
>(ω∗ − ω) which is zero if and only if (MVI) holds for ω∗. To deal with unbounded constraint sets (leading to a potentially infinite valued function outside of the optimal set), we use the restricted merit function (Nesterov, 2007):
ErrR(ωt) def = max ω∈Ω,‖ω−ω0‖≤R F (ω)>(ωt − ω) . (102)
This function acts as merit function for (VIP) on the interior of the open ball of radius R around ω0, as shown in Lemma 1 of Nesterov (2007). That is, let ΩR def = Ω ∩ {ω : ‖ω − ω0‖ < R}. Then for any point ω̂ ∈ ΩR, we have: ErrR(ω̂) = 0⇔ ω̂ ∈ Ω∗ ∩ ΩR. (103)
The reference point ω0 is arbitrary, but in practice it is usually the initialization point of the algorithm. R has to be big enough to ensure that ΩR contains a solution. ErrR measures how much (MVI) is violated on the restriction ΩR. Such merit function is standard in the variational inequality literature. A similar one is used in (Nemirovski, 2004; Juditsky et al., 2011). When F is derived from the gradients (5) of a zero-sum game, we can define a more interpretable merit function. One has to be careful though when extending properties from the minimization setting to the saddle point setting (e.g. the merit function used by Yadav et al. (2018) is vacuous for a bilinear game as explained in App C.2).
In the appendix, we adopt a set of assumptions a little more general than the one in the main paper:
Assumption 4. • F is monotone and Ω is convex and closed.
• R is set big enough such that R > ‖ω0 − ω∗‖ and F is a monotone operator.
Contrary to Assumption 3, in Assumption 4 the constraint set in no longer assumed to be bounded. Assumption 4 is implied by Assumption 3 by setting R to the diameter of Ω, and is thus more general.

heading: C.1 MORE GENERAL MERIT FUNCTIONS
text: In this appendix, we will note Err(VI)R the restricted merit function defined in (102). Let us recall its definition,
Err (VI) R (ωt) def = max ω∈Ω,‖ω−ω0‖≤R F (ω)>(ωt − ω) . (104)
When the objective is a saddle point problem i.e.,
F (θ,ϕ) = [∇θL(θ,ϕ) −∇ϕL(θ,ϕ)]> (105)
and L is convex-concave (see Definition 4 in §A), we can use another merit function than (104) on ΩR that is more interpretable and more directly related to the cost function of the minimax formulation:
Err (SP) R (θt,ϕt) def = max
ϕ∈Φ,θ∈Θ ‖(θ,ϕ)−(θ0,ϕ0)‖≤R
L(θt,ϕ)− L(θ,ϕt) . (106)
In particular, if the equilibrium (θ∗,ϕ∗) ∈ Ω∗ ∩ ΩR and we have that L(·,ϕ∗) and −L(θ∗, ·) are µ-strongly convex (see §A), then the merit function for saddle points upper bounds the distance for (θ,ϕ) ∈ ΩR to the equilibrium as:
Err (SP) R (θ,ϕ) ≥
µ 2 (‖θ − θ∗‖22 + ‖ϕ−ϕ∗‖22) . (107)
In the appendix, we provide our convergence results with the merit functions (104) and (106), depending on the setup:
ErrR(ω) def = Err (SP) R (ω) if F is a SP operator (5)
Err (VI) R (ω) otherwise.
(108)

heading: C.2 ON THE IMPORTANCE OF THE MERIT FUNCTION
text: In this section, we illustrate the fact that one has to be careful when extending results and properties from the minimization setting to the minimax setting (and consequently to the variational inequality setting). Another candidate as a merit function for saddle point optimization would be to naturally extend the suboptimality f(ω)− f(ω∗) used in standard minimization (i.e. find ω∗ the minimizer of f ) to the gap P (θ,ϕ) = L(θ,ϕ∗) − L(θ∗,ϕ). In a previous analysis of a modification of the stochastic gradient descent (SGD) method for GANs, Yadav et al. (2018) gave their convergence rate on P that they called the “primal-dual“ gap. Unfortunately, if we do not assume that the function L is strongly convex-concave (a stronger assumption defined in §A and which fails for bilinear objective e.g.), P may not be a merit function. It can be 0 for a non optimal point, see for instance the discussion on the differences between (106) and P in (Gidel et al., 2017, Section 3). In particular, for the simple 2D bilinear example L(θ,ϕ) = θ ·ϕ, we have that θ∗ = ϕ∗ = 0 and thus P (θ,ϕ) = 0 ∀θ,ϕ .
C.3 VARIATIONAL INEQUALITIES FOR NON-CONVEX COST FUNCTIONS
When the cost functions defined in (3) are non-convex, the operator F is no longer monotone. Nevertheless, (VIP) and (MVI) can still be defined, though a solution to (MVI) is less likely to exist. We note that (VIP) is a local condition for F (as only evaluating F at the points ω∗). On the other hand, an appealing property of (MVI) is that it is a global condition. In the context of minimization of a function f for example (where F = ∇f ), if ω∗ solves (MVI) then ω∗ is a global minimum of f (and not just a stationary point for the solution of (MVI); see Proposition 2.2 from Crespi et al. (2005)).
A less restrictive way to consider variational inequalities in the non-monotone setting is to use a local version of (MVI). If the cost functions are locally convex around the optimal couple (θ∗,ϕ∗) and if our iterates eventually fall and stay into that neighborhood, then we can consider our restricted merit function ErrR(·) with a well suited constant R and apply our convergence results for monotone operators.

heading: D ANOTHER WAY OF IMPLEMENTING EXTRAPOLATION TO SGD
text: We now introduce another way to combine extrapolation and SGD. This extension is very similar to AvgExtraSGD Alg. 2, the only difference is that it re-uses the mini-batch sample of the extrapolation step for the update of the current point. The intuition is that it correlates the estimator of the gradient of the extrapolation step and the one of the update step leading to a better correction of the oscillations which are also due to the stochasticity. One emerging issue (for the analysis) of this method is that since ω′t depend on ξt, the quantity F (ω ′ t, ξt) is a biased estimator of F (ω ′ t).
Algorithm 5 Re-used mini-batches for stochastic extrapolation (ReExtraSGD) 1: Let ω0 ∈ Ω 2: for t = 0 . . . T − 1 do 3: Sample ξt ∼ P 4: ω′t def = PΩ[ωt − ηtF (ωt, ξt)] . Extrapolation step
5: ωt+1 def = PΩ[ωt − ηtF ( ω′t, ξt ) ] . Update step with the same sample 6: end for 7: Return ω̄T = ∑T−1 t=0 ηtω ′ t/ ∑T−1 t=0 ηt
Theorem 5. Assume that ‖ω′t − ω0‖ ≤ R, ∀t ≥ 0 where (ω′t)t≥0 are the iterates of Alg. 5. Under Assumption 1 and 4, for any T ≥ 1, Alg. 5 with constant step-size η ≤ 1√
2L has the following
convergence properties:
E[ErrR(ω̄T )] ≤ R2
ηT + η
σ2 + 4L2(4R2 + σ2)
2 where ω̄T
def =
1
T T−1∑ t=0 ω′t .
Particularly, ηt = η√T gives E[ErrR(ω̄T )] ≤ O(1)√ T .
The assumption that the sequence of the iterates provided by the algorithm is bounded is strong, but has also been made for instance in (Yadav et al., 2018). The proof of this result is provided in §F.
E VARIANCE COMPARISON BETWEEN AVGSGD AND SGD WITH PREDICTION METHOD
To compare the variance term of AvgSGD in (26) with the one of the SGD with prediction method (Yadav et al., 2018), we need to have the same convergence certificate. Fortunately, their proof can be adapted to our convergence criterion (using Lemma 7 in §F), revealing an extra σ2/2 in the variance term from their paper. The resulting variance can be summarized with our notation as (M2(1 + L) + σ2)/2 where the L is the Lipschitz constant of the operator F . Since M σ, their variance term is then 1 + L time larger than the one provided by the AvgSGD method.

heading: F PROOF OF THEOREMS
text: This section is dedicated on the proof of the theorems provided in this paper in a slightly more general form working with the merit function defined in (108). First we prove an additional lemma necessary to the proof of our theorems.
Lemma 7. Let F be a monotone operator and let (ωt), (ω′t), (zt), (∆t), (ξt) and (ζt) be six random sequences such that, for all t ≥ 0
2ηtF (ω ′ t) >(ω′t − ω) ≤ Nt −Nt+1 + η2t (M1(ωt, ξt) +M2(ω′t, ζt)) + 2ηt∆>t (zt − ω) ,
where Nt = N(ωt,ω′t−1,ω ′ t−2) ≥ 0 and we extend (ω′t) with ω′−2 = ω′−1 = ω′0. Let also assume that with N0 ≤ R , E[‖∆t‖22] ≤ σ2, E[∆t|zt,∆0, . . . ,∆t−1] = 0 , E[M1(ωt, ξt)] ≤ M1 and E[M2(ω′t, ζt)] ≤M2 , then,
E[ErrR(ω̄T )] ≤ R2 ST + M1 +M2 + σ 2 2ST T−1∑ t=0 η2t (109)
where ω̄T def = ∑T−1 t=0 ηtω ′ t/ST and ST def = ∑T−1 t=0 ηt.
Proof of Lemma 7. We sum (7) for 0 ≤ t ≤ T − 1 to get,
2 T−1∑ t=0 ηtF (ω ′ t) >(ω′t − ω) ≤
T−1∑ t=0 [ (Nt −Nt+1) + η2t ((M1(ωt, ξt) +M2(ω′t, ζt)) + 2ηt∆>t (zt − ω) ] . (110)
We will then upper bound each sum in the right-hand side,
∆>t (zt − ω) = ∆>t (zt − ut) + ∆>t (ut − ω)
where ut+1 def = PΩ(ut − ηt∆t) and u0 def = ω0. Then, ‖ut+1 − ω‖22 ≤ ‖ut − ω‖22 − 2ηt∆>t (ut − ω) + η2t ‖∆t‖22 leading to
2ηt∆ > t (zt − ω) ≤ 2ηt∆>t (zt − ut) + ‖ut − ω‖22 − ‖ut+1 − ω‖22 + η2t ‖∆t‖22 (111)
Then noticing that z0 def = ω0, back to (110) we get a telescoping sum,
2 T−1∑ t=0 ηtF (ω ′ t) >(ω′t−ω) ≤ 2N0+ T−1∑ t=0 [ η2t ((M1(ωt, ξt)+M2(ω ′ t, ζt))+‖∆t‖22)+2ηt∆>t (zt−ut) ] . (112) If F is the operator of a convex-concave saddle point (5), we get, with ω′t = (θt,ϕt)
F (ω′t) >(ω′t − ω) ≥ ∇θL(θt,ϕt)>(θt − θ)−∇ϕL(θt,ϕt)>(ϕt −ϕ)
≥ L(θt,ϕ)− L(θt,ϕt) + L(θt,ϕt)− L(θ,ϕt) (by convexity and concavity)
= L(θt,ϕ)− L(θ,ϕt) then by convexity of L(·,ϕ) and concavity of L(θ, ·), we have that,
2ST T−1∑ t=0 ηt ST F (ω′t) >(ω′t−ω) ≥ 2ST T−1∑ t=0 ηt ST (L(θt,ϕ)−L(θ,ϕt)) ≥ 2̄ST (L(θ̄t,ϕ)−L(θ̄,ϕt)) (113) Otherwise if the operator F is just monotone since F (ω′t)
>(ω′t − ω) ≥ F (ω′)>(ω′t − ω) we have that
2ST T−1∑ t=0 ηtF (ω ′ t) >(ω′t − ω) ≥ 2ST T−1∑ t=0 ηtF (ω ′)>(ω′t − ω) = 2STF (ω′)>(ω̄t − ω) (114)
In both cases, we can now maximize the left hand side respect to ω (since the RHS does not depend on ω) to get,
2ST ErrR(ω̄t) ≤ 2R2 + T−1∑ t=0 [ η2t ((M1(ωt, ξt)+M2(ω ′ t, ζt))+‖∆t‖22)+2ηt∆>t (zt−ut) ] . (115)
Then taking the expectation, since E[∆t|zt,ut] = E[∆t|zt,∆0, . . . ,∆t−1] = 0, Eζt [‖∆t‖22] ≤ σ2, Eξt [M1(ωt, ξt)] ≤M1 and Eζt [M2(ω′t, ζt)] ≤M2 , we get that,
E[ErrR(ω̄T )] ≤ R2 ST + M1 +M2 + σ 2 2ST T−1∑ t=0 η2t (116)

heading: F.1 PROOF OF THM. 2
text: First let us state Theorem 2 in its general form,
Theorem’ 2. Under Assumption 1, 2 and 4, Alg. 1 with constant step-size η has the following convergence rate for all T ≥ 1,
E[ErrR(ω̄T )] ≤ R2
2ηT + η
M2 + σ2
2 where ω̄T
def =
1
T T−1∑ t=0 ωt . (117)

heading: Particularly, η = R√
text: T (M2+σ2) gives E[ErrR(ω̄T )] ≤ R √ M2+σ2√ T .
Proof of Theorem 2. Let any ω ∈ Ω such that ‖ω0 − ω‖2 ≤ R,
‖ωt+1 − ω‖22 = ‖PΩ(ωt − ηtF (ωt, ξt))− ω‖22 ≤ ‖ωt − ηtF (ωt, ξt))− ω‖22
(projections are non-contractive, Lemma 1)
= ‖ωt − ω‖22 − 2ηtF (ωt, ξt)>(ωt − ω) + ‖ηtF (ωt, ξt)‖22 Then we can make appear the quantity F (ωt)>(ωt − ω) on the left-hand side,
2ηtF (ωt) >(ωt−ω) ≤ ‖ωt−ω‖22−‖ωt+1−ω‖22+η2t ‖F (ωt, ξt)‖22+2ηt(F (ωt)−F (ωt, ξt))>(ωt−ω) (118) we can sum (118) for 0 ≤ t ≤ T − 1 to get,
2 T−1∑ t=0 ηtF (ωt) >(ωt − ω) ≤
T−1∑ t=0 [ (‖ωt − ω‖2 − ‖ωt+1 − ω‖2) + η2t ‖F (ωt, ξt)‖22 + 2ηt∆>t (ωt − ω) ] (119)
where we noted ∆t def = F (ωt)− F (ωt, ξt). By monotonicity, F (ωt)>(ωt − ω) ≥ F (ω)>(ωt − ω) we get,
2STF (ω) >(ω̄T−ω) ≤ T−1∑ t=0 [ (‖ωt − ω‖2 − ‖ωt+1 − ω‖2) + η2t ‖F (ωt, ξt)‖22 + 2ηt∆>t (ωt − ω) ] , (120) where ST def = ∑T−1 t=0 ηt and ω̄T def = 1ST ∑T−1 t=0 ηtωt. We will then upper bound each sum in the right hand side,
∆>t (ωt − ω) = ∆>t (ωt − ut) + ∆>t (ut − ω)
where ut+1 def = PΩ(ut − ηt∆t) and u0 = ω0. Then,
‖ut+1 − ω‖22 ≤ ‖ut − ω‖22 − 2ηt∆>t (ut − ω) + η2t ‖∆t‖22 leading to
2ηt∆ > t (ωt − ω) ≤ 2ηt∆>t (ωt − ut) + ‖ut − ω‖22 − ‖ut+1 − ω‖22 + η2t ‖∆t‖22 (121)
Then noticing that u0 def = ω0, back to (120) we get a telescoping sum,
2STF (ω) >(ω̄T − ω) ≤ 2‖ω0 − ω‖2 + T−1∑ t=0 η2t (‖F (ωt, ξt)‖22 + ‖∆t‖22) + 2 T−1∑ t=0 ηt∆ > t (ωt − ut)
≤ 2R+ T−1∑ t=0 η2t (‖F (ωt, ξt)‖22 + ‖∆t‖22) + 2 T−1∑ t=0 ηt∆ > t (ωt − ut)
Then the right hand side does not depends on ω, we can maximize over ω to get,
2ST ErrR(ω̄T ) ≤ 2R+ T−1∑ t=0 η2t (‖F (ωt, ξt)‖22 + ‖∆t‖22) + 2 T−1∑ t=0 ηt∆ > t (ωt − ut) (122)
Noticing that E[∆t|ωt,ut] = 0 (the estimates of F are unbiased), by Assumption 2 E[(‖F (ωt, ξt)‖22] ≤M2 and by Assumption 1 E[‖∆t‖22] ≤ σ2 we get,
E[ErrR(ω̄T )] ≤ R ST + M2 + σ2 2ST T−1∑ t=0 η2t (123)
particularly for ηt = η and ηt = η√t+1 we respectively get,
E[ErrR(ω̄T )] ≤ 2R ηT + η 2 (M2 + σ2) (124)
and
E[ErrR(ω̄T )] ≤ 4R
η √ T + 1− 1 + 2η ln(T + 1) M2 + σ2√ T + 1− 1
(125)

heading: F.2 PROOF OF THM. 3
text: Theorem’ 3. Under Assumption 1 and 4, if Eξ[F ] is L-Lipschitz, then Alg. 2 with a constant step-size η ≤ 1√
3L has the following convergence rate for any T ≥ 1,
E[ErrR(ω̄T )] ≤ R2
ηT +
7 2 ησ2 where ω̄T def = 1 T T−1∑ t=0 ω′t . (126)
Particularly, η = √
2R σ √ 7T gives E[ErrR(ω̄T )] ≤ √ 14Rσ√ T .
Proof of Thm. 3. Let any ω ∈ Ω such that ‖ω0 − ω‖2 ≤ R. Then, the update rules become ωt+1 = PΩ(ωt − ηtF (ω′t, ζt)) and ω′t = PΩ(ωt − ηF (ωt, ξt)). We start by applying Lemma 2 for (ω,u,ω′,ω+) = (ωt,−ηF (ω′t, ζt),ω,ωt+1) and (ω,u,ω′,ω+) = (ωt,−ηtF (ωt, ξt),ωt+1,ω′t),
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ζt)>(ωt+1 − ω)− ‖ωt+1 − ωt‖22 ‖ω′t − ωt+1‖22 ≤ ‖ωt − ωt+1‖22 − 2ηtF (ωt, ξt)>(ω′t − ωt+1)− ‖ω′t − ωt‖22
Then, summing them we get
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ζt)>(ωt+1 − ω) − 2ηtF (ωt, ξt)>(ω′t − ωt+1)− ‖ωt − ω′t‖22 − ‖ωt+1 − ω′t‖22 (127)
leading to
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ζt)>(ω′t − ω) + 2ηt(F (ω ′ t, ζt)− F (ωt, ξt))>(ω′t − ωt+1)− ‖ωt − ω′t‖22 − ‖ωt+1 − ω′t‖22
Then with 2a>b ≤ ‖a‖22 + ‖b‖22 we get
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ζt)>(ω′t − ω) − ‖ωt − ω′t‖22 + η2t ‖F (ω′t, ζt)− F (ωt, ξt)‖22
Using the inequality ‖a+ b+ c‖22 ≤ 3(‖a‖22 + ‖b‖22 + ‖c‖22) we get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ζt)>(ω′t − ω)− ‖ωt − ω′t‖22 + 3η2t (‖F (ωt)− F (ωt, ξt)‖22 + ‖F (ω′t)− F (ω′t, ζt)‖22 + ‖F (ω′t)− F (ωt)‖22)
Then we can use the L-Lipschitzness of F to get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ζt)>(ω′t − ω)− ‖ωt − ω′t‖22 + 3η2t (‖F (ωt)− F (ωt, ξt)‖22 + ‖F (ω′t)− F (ω′t, ζt)‖22 + L2‖ωt − ω′t‖22)
As we restricted the step-size to ηt ≤ 1√3L we get,
2ηtF (ω ′ t) >(ω′t − ω) ≤ ‖ωt − ω‖22 − ‖ωt+1 − ω‖22 + 2ηt(F (ω′t)− F (ω′t, ζt))>(ω′t − ω)
+ 3η2t ‖F (ωt)− F (ωt, ξt)‖22 + 3η2t ‖F (ω′t)− F (ω′t, ζt)‖22 We get a particular case of (7) so we can use Lemma 7 where Nt = ‖ωt − ω‖22, M1(ωt, ξt) = 3‖F (ωt)−F (ωt, ξt)‖22 , M2(ω′t, ζt) = 3‖F (ω′t)−F (ω′t, ζt)‖22, ∆t = F (ω′t)−F (ω′t, ζt) and zt = ω′t. By Assumption 1, M1 = M2 = 3σ
2 and by the fact that E[F (ω′t) − F (ω′t, ζt) |ω′t,∆0, . . . ,∆t−1] = E[E[F (ω′t) − F (ω′t, ζt) |ω′t]|∆0, . . . ,∆t−1] = 0 the hypothesis of Lemma 7 hold and we get,
E[ErrR(ω̄T )] ≤ R2
ST +
7σ2
2ST T−1∑ t=0 η2t (128)

heading: F.3 PROOF OF THM. 4
text: Theorem’ 4. Under Assumption 1, if Eξ[F ] is L-Lipschitz, then AvgPastExtraSGD (Alg. 3) with a constant step-size η ≤ 1
2 √ 3L has the following convergence rate for any T ≥ 1,
E[ErrR(ω̄T )] ≤ R2
ηT +
13
2 ησ2 where ω̄T
def =
1
T T−1∑ t=0 ω′t . (129)
Particularly, η = √
2R σ √ 13T gives E[ErrR(ω̄T )] ≤ √ 26Rσ√ T .
First let us recall the update rule{ ωt+1 = PΩ[ωt − ηtF (ω′t, ξt)] ω′t+1 = PΩ[ωt+1 − ηt+1F (ω′t, ξt)] .
(130)
Lemma 8. We have for any ω ∈ Ω,
2ηF (ω′t, ξt) >(ω′t − ω) ≤ ‖ωt − ω‖22 − ‖ωt+1 − ω‖22 − ‖ω′t − ωt‖22 + 3η2tL2‖ω′t−1 − ω′t‖22 + 3η2t [ ‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + ‖F (ω′t)− F (ω′t, ξt)‖22 ] . (131)
Proof. Applying Lemma 2 for (ω,u,ω+,ω′) = (ωt,−ηtF (ω′t, ξt),ωt+1,ω) and (ω,u,ω+,ω′) = (ωt,−ηtF (ω′t−1, ξt−1),ω′t,ωt+1), we get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ωt+1 − ω)− ‖ωt+1 − ωt‖22 (132)
and
‖ω′t − ωt+1‖22 ≤ ‖ωt − ωt+1‖22 − 2ηtF (ω′t−1, ξt−1)>(ω′t − ωt+1)− ‖ω′t − ωt‖22 . (133)
Summing (132) and (133) we get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ωt+1 − ω) (134) − 2ηtF (ω′t−1, ξt−1)>(ω′t − ωt+1)− ‖ω′t − ωt‖22 − ‖ω′t − ωt+1‖22 (135)
= ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ω′t − ω)− ‖ω′t − ωt‖22 − ‖ω′t − ωt+1‖22 (136) − 2ηt(F (ω′t−1, ξt−1)− F (ω′t, ξt))>(ω′t − ωt+1) . (137)
Then, we can use the inequality of arithmetic and geometric means 2a>b ≤ ‖a‖22 + ‖b‖22 to get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ω′t − ω) + η2t ‖F (ω′t−1, ξt−1)− F (ω′t, ξt)‖22 + ‖ω′t − ωt+1‖22 − ‖ω′t − ωt‖22 − ‖ω′t − ωt+1‖22 (138)
= ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ω′t − ω) (139) + η2t ‖F (ω′t−1, ξt−1)− F (ω′t, ξt)‖22 − ‖ω′t − ωt‖22 . (140)
Using the inequality ‖a+ b+ c‖22 ≤ 3(‖a‖22 + ‖b‖22 + ‖c‖22) we get,
‖F (ω′t−1, ξt−1)− F (ω′t, ξt)‖22 ≤ 3(‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + ‖F (ω′t−1)− F (ω′t)‖22 + ‖F (ω′t)− F (ω′t, ξt)‖22) (141) ≤ 3(‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + L2‖ω′t−1 − ω′t‖22
+ ‖F (ω′t)− F (ω′t, ξt)‖22) , (142) where we used the L-Lipschitzness of F for the last inequality.
Combining (140) with (142) we get,
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ω′t − ω)− ‖ω′t − ωt‖22 + 3η2tL2‖ω′t−1 − ω′t‖22 + 3η2t [ ‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + ‖F (ω′t)− F (ω′t, ξt)‖22 ] . (143)
Lemma 9. For all t ≥ 0, if we set ω′−2 = ω′−1 = ω′0 we have ‖ω′t−1 − ω′t‖22 ≤ 4‖ωt − ω′t‖22 + 12η2t−1 ( ‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + L2‖ω′t−1 − ω′t−2‖22
+ ‖F (ω′t−2)− F (ω′t−2, ξt−2)‖22) ) − ‖ω′t−1 − ω′t‖22 . (144)
Proof. We start with ‖a+ b‖22 ≤ 2‖a‖2 + 2‖b‖2.
‖ω′t−1 − ω′t‖22 ≤ 2‖ωt − ω′t‖22 + 2‖ωt − ω′t−1‖22 . (145) Moreover, since the projection is contractive we have that
‖ωt − ω′t−1‖22 ≤ ‖ωt−1 − ηt−1F (ω′t−1, ξt−1)− ωt−1 − ηt−1F (ω′t−2, ξt−2)‖22 (146) = η2t−1‖F (ω′t−1, ξt−1)− F (ω′t−2, ξt−2)‖22 (147) ≤ 3η2t−1 ( ‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + L2‖ω′t−1 − ω′t−2‖22
+ ‖F (ω′t−2)− F (ω′t−2, ξt−2)‖22) ) . (148)
where in the last line we used the same inequality as in (142). Combining (144) and (148) we get,
‖ω′t−1 − ω′t‖22 = 2‖ω′t−1 − ω′t‖22 − ‖ω′t−1 − ω′t‖22 (149) ≤ 4‖ωt − ω′t‖22 + 4‖ωt − ω′t−1‖22 − ‖ω′t−1 − ω′t‖22 (150) ≤ 4‖ωt − ω′t‖22 + 12η2t−1 ( ‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + L2‖ω′t−1 − ω′t−2‖22
+ ‖F (ω′t−2)− F (ω′t−2, ξt−2)‖22) ) − ‖ω′t−1 − ω′t‖22 . (151)
Proof of Theorem 4. Combining Lemma 9 and Lemma 8 we get,
2ηtF (ω ′ t, ξt) >(ω′t − ω) ≤ ‖ωt − ω‖22 − ‖ωt+1 − ω‖22 + 36η2t η 2 t−1L 2 ( ‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + L2‖ω′t−1 − ω′t−2‖22
+ ‖F (ω′t−2)− F (ω′t−2, ξt−2)‖22 )
− 3η2tL2‖ω′t−1 − ω′t‖22 + (12η2tL2 − 1)‖ω′t − ωt‖22 + 3η2t [ ‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22 + ‖F (ω′t)− F (ω′t, ξt)‖22] .
(152)
Then for ηt ≤ 12√3L we have 36η 2 t η 2 t−1L 4 ≤ 3η2t−1L2,
2ηtF (ω ′ t) >(ω′t − ω) ≤ ‖ωt − ω‖22 − ‖ωt+1 − ω‖22
+ 3L2(η2t−1‖ω′t−1 − ω′t−2‖22 − η2t ‖ω′t−1 − ω′t‖22) + 2ηt(F (ω ′ t)− F (ω′t, ξt))>(ω′t − ω)
+ 3η2t [ |F (ω′t−2, ξt−2)− F (ω′t−2)‖22 + 2‖F (ω′t−1, ξt−1)− F (ω′t−1)‖22
+ ‖F (ω′t)− F (ω′t, ξt)‖22] . (153) We can then use Lemma 7 where
Nt = ‖ωt − ω‖22 + 3L3ηt−1‖ω′t−1 − ω′t−2‖22, M1(ωt, ξt) = 0
M2(ω ′ t, ξt) = 3‖F (ω′t)− F (ω′t, ξt)‖22 + 6‖F (ω′t−1)− F (ω′t−1, ξt−1)‖22
+ 3‖F (ω′t−2)− F (ω′t−2, ξt−2)‖22 ∆t = F (ω ′ t)− F (ω′t, ξt)
zt = ω ′ t .
By Assumption 1, M2 = 12σ2 and by the fact that E[F (ω′t) − F (ω′t, ξt) |ω′t,∆0, . . . ,∆t−1] = E[E[F (ω′t) − F (ω′t, ξt) |ω′t]|∆0, . . . ,∆t−1] = 0 the hypothesis of Lemma 7 hold and we get,
E[ErrR(ω̄T )] ≤ R2
ST +
13σ2
2ST T−1∑ t=0 η2t (154)

heading: F.4 PROOF OF THEOREM 5
text: Theorem 5 has been introduced in §D. This theorem is about Algorithm 5 which consists in another way to implement extrapolation to SGD. Let us first restate this theorem,
Theorem’ 5. Assume that ‖ω′t − ω0‖ ≤ R, ∀t ≥ 0 where (ω′t)t≥0 are the iterates of Alg. 5. Under Assumption 1 and 4, for any T ≥ 1, Alg. 5 with constant step-size η ≤ 1√
2L has the following
convergence properties:
E[ErrR(ω̄T )] ≤ R2
ηT + η
σ2 + 4L2(4R2 + σ2)
2 where ω̄T
def =
1
T T−1∑ t=0 ω′t .
Particularly, ηt = η√T gives E[ErrR(ω̄T )] ≤ O(1)√ T .
Proof of Thm. 5. Let any ω ∈ Ω such that ‖ω0 − ω‖2 ≤ R. Then, the update rules become ωt+1 = PΩ(ωt − ηtF (ω′t, ξt)) and ω′t = PΩ(ωt − ηF (ωt, ξt)). We start the same way as the proof of Thm. 3 by applying Lemma 2 for (ω,u,ω′,ω∗) = (ωt,−ηF (ω′t, ξt),ω,ωt+1) and (ω,u,ω′,ω+) = (ωt,−ηtF (ωt, ξt),ωt+1,ω′t),
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ωt+1 − ω)− ‖ωt+1 − ωt‖22 ‖ω′t − ωt+1‖22 ≤ ‖ωt − ωt+1‖22 − 2ηtF (ωt, ξt)>(ω′t − ωt+1)− ‖ω′t − ωt‖22
Then, summing them we get
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ωt+1 − ω) − 2ηtF (ωt, ξt)>(ω′t − ωt+1)− ‖ω′t − ωt‖22 − ‖ωt+1 − ω′t‖22 (155)
leading to
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ω′t − ω) + 2ηt(F (ω ′ t, ξt)− F (ωt, ξt))>(ω′t − ωt+1)− ‖ω′t − ωt‖22 − ‖ωt+1 − ω′t‖22
Then with 2a>b ≤ ‖a‖22 + ‖b‖22 we get
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ω′t − ω) +η2t ‖F (ω′t, ξt)− F (ωt, ξt)‖22 − ‖ω′t − ωt‖22
Using the Lipschitz assumption we get
‖ωt+1 − ω‖22 ≤ ‖ωt − ω‖22 − 2ηtF (ω′t, ξt)>(ω′t − ω) + (η2tL2 − 1)‖ωt − ω′t‖22
Then we add 2ηtF (ω′t) >(ω′t − ω) in both sides to get,
2ηtF (ω ′ t) >(ω′t − ω) ≤ ‖ωt − ω‖22 − ‖ωt+1 − ω‖22
− 2ηt(F (ω′t, ξt)− F (ω′t))>(ω′t − ω) + (η2tL2 − 1)‖ωt − ω′t‖22 (156)
Here, unfortunately we cannot use Lemma 7 because F (ω′t, ξt) is biased. We will then deal with the quantity A = (F (ω′t, ξt)− F (ω′))>(ω′t − ω) . We have that,
A = (F (ω′t, ξt)− F (ωt, ξt))>(ω − ω′t) + (F (ωt)− F (ω′t))>(ω − ω′t) + (F (ωt, ξt)− F (ωt))>(ωt − ω′t) + (F (ωt, ξt)− F (ωt))>(ω − ωt) ≤ 2L‖ω′t − ωt‖2‖ω′t − ω‖2 + ‖F (ωt, ξt)− F (ωt)‖‖ω′t − ωt‖2
+ (F (ωt, ξt)− F (ωt))>(ω − ωt) (Using Cauchy-Schwarz and the L-Lip of F )
Then using 2‖a‖‖b‖ ≤ δ‖a‖22 + 1δ ‖b‖ 2 2, for δ = 4,
−2ηt(F (ω′t, ξt)− F (ω′t))>(ω′t − ω) ≤ 1
2 ‖ω′t − ωt‖2 + 8η2tL2‖ω′t − ω‖22
+ 4η2t ‖F (ωt, ξt)− F (ωt)‖22
+ 1
4 ‖ω′t − ωt‖22 + 2ηt(F (ωt, ξt)− F (ωt))>(ω − ωt)
leading to,
2ηtF (ω ′ t) >(ω′t − ω) ≤ ‖ωt − ω‖22 − ‖ωt+1 − ω‖22 + 2ηt(F (ωt, ξt)− F (ωt))>(ω − ωt)
+ (η2tL 2 − 14 )‖ωt − ω ′ t‖22 + 4η2t (2L 2‖ω′t − ω‖22 + ‖F (ωt, ξt)− F (ωt)‖22)
If one assumes finally that ‖ω′t − ω0‖2 ≤ R (assumption of the theorem) and that ηt ≤ 12L we get,
2ηtF (ω ′ t) >(ω′t − ω) ≤ ‖ωt − ω‖22 − ‖ωt+1 − ω‖22 + 2ηt(F (ωt, ξt)− F (ωt))>(ω − ωt)
+ 4η2t (4L 2R2 + ‖F (ωt, ξt)− F (ωt)‖22)
where we used that ‖ω′t − ω‖2 ≤ ‖ω′t − ω0‖2 + ‖ω0 − ω‖2 ≤ 2R. Once again this equation is a particular case of Lemma 7 where Nt = ‖ωt − ω‖22, M1(ωt, ξt) = 4(4L
2R2 + ‖F (ωt, ξt) − F (ωt)‖22), M2(ω′t, ζt) = 0, zt = ωt and ∆t = F (ωt, ξt) − F (ωt). By Assumption 1 E[M1(ωt, ξt)] ≤ 16L2R2 + 4σ2 and E[∆t|ωt,∆0, . . . ,∆t−1] = E[E[∆t|ωt]|∆0, . . . ,∆t−1] = 0 so we can use Lemma 7 and get,
E[ErrR(ω̄T )] ≤ R2 ST + σ2 + 16L2R2 + 4σ2 2ST T−1∑ t=0 η2t . (157)

heading: G ADDITIONAL EXPERIMENTAL RESULTS

heading: G.1 TOY NON-CONVEX GAN (2D AND DETERMINISTIC)
text: We now consider a task similar to (Mescheder et al., 2018) where the discriminator is linear Dϕ(ω) = ϕ
Tω, the generator is a Dirac distribution at θ, qθ = δθ and the distribution we try to match is also a Dirac at ω∗, p = δω∗ . The minimax formulation from Goodfellow et al. (2014) gives:
min θ max ϕ − log
( 1 + e−ϕ Tω∗ ) − log ( 1 + eϕ T θ )
(158)
Note that as observed by Nagarajan and Kolter (2017), this objective is concave-concave, making it hard to optimize. We compare the methods on this objective where we take ω∗ = −2, thus the position of the equilibrium is shifted towards the position (θ,ϕ) = (−2, 0). The convergence and the gradient vector field are shown in Figure 5. We observe that depending on the initialization, some methods can fail to converge but extrapolation (18) seems to perform better than the other methods.

heading: G.2 DCGAN WITH WGAN-GP OBJECTIVE
text: In addition to the results presented in section §7.2, we also trained the DCGAN architecture with the WGAN-GP objective. The results are shown in Table 3. The best results are achieved with uniform averaging of AltAdam5. However, its iterations require to update the discriminator 5 times for every generator update. With a small drop in best final score, ExtraAdam can train WGAN-GP significantly faster (see Fig. 6 right) as the discriminator and generator are updated only twice.

heading: G.3 FID SCORES FOR RESNET ARCHITECTURE WITH WGAN-GP OBJECTIVE
text: In addition to the inception scores, we also computed the FID scores (Heusel et al., 2017) using 50,000 samples for the ResNet architecture with the WGAN-GP objective; the results are presented in Table 5. We see that the results and conclusions are similar to the one obtained from the inception scores, adding an extrapolation step as well as using Exponential Moving Average (EMA) consistently improves the FID scores. However, contrary to the results from the inception score, we observe that uniform averaging does not necessarily improve the performance of the methods. This could be due to the fact that the samples produced using uniform averaging are more blurry and FID is more sensitive to blurriness; see §G.3 for more details about the effects of uniform averaging.

heading: Generator
text: Input: z ∈ R128 ∼ N (0, I) Linear 128→ 512× 4× 4
Batch Normalization ReLU
transposed conv. (kernel: 4×4, 512→ 256, stride: 2, pad: 1) Batch Normalization ReLU transposed conv. (kernel: 4×4, 256→ 128, stride: 2, pad: 1)
Batch Normalization ReLU
transposed conv. (kernel: 4×4, 128→ 3, stride: 2, pad: 1) Tanh(·)

heading: Discriminator
text: Input: x ∈ R3×32×32
conv. (kernel: 4×4, 1→ 64; stride: 2; pad:1) LeakyReLU (negative slope: 0.2)
conv. (kernel: 4×4, 64→ 128; stride: 2; pad:1) Batch Normalization
LeakyReLU (negative slope: 0.2) conv. (kernel: 4×4, 128→ 256; stride: 2; pad:1)
Batch Normalization LeakyReLU (negative slope: 0.2)
Linear 128× 4× 4× 4→ 1

heading: Discriminator

heading: Generator

heading: G.4 COMPARISON OF THE METHODS WITH THE SAME LEARNING RATE
text: In this section, we compare how the methods presented in §7 perform with the same step-size. We follow the same protocol as in the experimental section §7, we consider the DCGAN architecture with WGAN-GP experiment described in App §G.2. In Figure 7 we plot the inception score provided by each training method as a function of the number of generator updates. Note that these plots advantage AltAdam5 a bit because each iteration of this algorithm is a bit more costly (since it perform 5 discriminator updates for each generator update). Nevertheless, the goal of this experiment is not to show that AltAdam5 is faster but to show that ExtraAdam is less sensitive to the choice of learning rate and can be used with higher learning rates with less degradation.
In Figure 8, we compare the sample quality on the DCGAN architecture with the WGAN-GP objective of AltAdam5 and AvgExtraAdam for different step-sizes. We notice that for AvgExtraAdam, the sample quality does not significantly change whereas the sample quality of AltAdam5 seems to be really sensitive to step-size tunning.
We think that robustness to step-size tuning is a key property for an optimization algorithm in order to save as much time as possible to tune other hyperparameters of the learning procedure such as regularization.

heading: G.5 COMPARISON OF THE METHODS WITH AND WITHOUT UNIFORM AVERAGING
text: In this section, we compare how uniform averaging affect the performance of the methods presented in §7. We follow the same protocol as in the experimental section §7, we consider the DCGAN architecture with the WGAN and weight clipping objective as well as the WGAN-GP objective. In Figure 9 and 10, we plot the inception score provided by each training method as a function of the number of generator updates with and without uniform averaging.
We notice that uniform averaging seems to improve the inception score, nevertheless it looks like the sample are a bit more blurry (see Figure 11). This is confirmed by our result (Figure 12) on the Fréchet Inception Distance (FID) which is more sensitive to blurriness. A similar observation about FID was made in §G.3.

heading: H HYPERPARAMETERS
text: (DCGAN) WGAN Hyperparameters Batch size = 64 Number of generator update = 500, 000 Adam β1 = 0.5 Adam β2 = 0.9 Weight clipping for the discriminator = 0.01 Learning rate for generator = 2× 10−5 (for Adam1, Adam5, PastExtraAdam, OptimisticAdam) = 5× 10−5 (for ExtraAdam) Learning rate for discriminator = 2× 10−4 (for Adam1, Adam5, PastExtraAdam, OptimisticAdam) = 5× 10−4 (for ExtraAdam) β for EMA = 0.999
(DCGAN) WGAN-GP Hyperparameters Batch size = 64 Number of generator update = 500, 000 Adam β1 = 0.5 Adam β2 = 0.9 Gradient penalty = 10 Learning rate for generator = 1× 10−4 (for Adam1, Adam5, PastExtraAdam, OptimisticAdam) = 5× 10−4 (for ExtraAdam) Learning rate for discriminator = 1× 10−4 (for Adam1, Adam5, PastExtraAdam, OptimisticAdam) = 5× 10−4 (for ExtraAdam) β for EMA = 0.999
(ResNet) WGAN-GP Hyperparameters Batch size = 64 Number of generator update = 500, 000 Adam β1 = 0.5 Adam β2 = 0.9 Gradient penalty = 10 Learning rate for generator = 2× 10−5 (for Adam1, Adam5, PastExtraAdam, OptimisticAdam) = 5× 10−5 (for ExtraAdam) Learning rate for discriminator = 2× 10−4 (for Adam1, Adam5, PastExtraAdam, OptimisticAdam) = 5× 10−4 (for ExtraAdam) β for EMA = 0.9999

Review summaries:
The authors take a variational inequality perspective to the study of the saddle point problem that defines a GAN. By doing so, they are able to profit from the corresponding literature and propose a few methods that are variants of SGD. The authors show in a simple example (a bilinear function) these exhibit better performance than Adam and a basic gradient method. After showing theoretical guarantees of these methods (linear convergence) the authors propose to combine them with existing techniques, and show in fact this leads to better results.