Year: 2020

Abstract:
Motivated by the training of Generative Adversarial Networks (GANs), we study methods for solving minimax problems with additional nonsmooth regularizers. We do so by employing monotone operator theory, in particular the ForwardBackward-Forward (FBF) method, which avoids the known issue of limit cycling by correcting each update by a second gradient evaluation. Furthermore, we propose a seemingly new scheme which recycles old gradients to mitigate the additional computational cost. In doing so we rediscover a known method, related to Optimistic Gradient Descent Ascent (OGDA). For both schemes we prove novel convergence rates for convex-concave minimax problems via a unifying approach. The derived error bounds are in terms of the gap function for the ergodic iterates. For the deterministic and the stochastic problem we show a convergence rate of O(1/k) and O(1/k), respectively. We complement our theoretical results with empirical improvements in the training of Wasserstein GANs on the CIFAR10 dataset.

heading: 1 INTRODUCTION
text: Generative Adversarial Networks (GANs) (Goodfellow et al., 2014) have proven to be a powerful class of generative models, producing for example unseen realistic images. Two neural networks, called generator and discriminator, compete against each other in a game. In the special case of a zero sum game this task can be formulated as a minimax (aka saddle point) problem.
Conventionally, GANs are trained using variants of (stochastic) Gradient Descent Ascent (GDA) which are known to exhibit oscillatory behavior and thus fail to converge even for simple bilinear saddle point problems, see Goodfellow (2016). We therefore propose the use of methods with provable convergence guarantees for (stochastic) convex-concave minimax problems, even though GANs are well known to not warrant these properties. Along similar considerations an adaptation of the Extragradient method (EG) (Korpelevich, 1976) for the training of GANs was suggested in Gidel et al. (2019), whereas Daskalakis et al. (2018); Daskalakis & Panageas (2018); Liang & Stokes (2019) studied Optimistic Gradient Descent Ascent (OGDA) based on optimistic mirror descent (Rakhlin & Sridharan, 2013a;b). We however investigate the Forward-Backward-Forward (FBF) method (Tseng, 1991) from monotone operator theory, which uses two gradient evaluations per update, similar to EG, in order to circumvent the aforementioned issues.
Instead of trying to improve GAN performance via new architectures, loss functions, etc., we contribute to the theoretical foundation of their training from the point of view of optimization.
Contribution. Establishing the connection between GAN training and monotone inclusions motivates to use the FBF method, originally designed to solve this type of problems. This approach allows to naturally extend the constrained setting to a regularized one making use of the proximal operator.
We also propose a variant of FBF reusing previous gradients to reduce the computational cost per iteration, which turns out to be a known method, related to OGDA. By developing a unifying scheme that captures FBF and a generalization of OGDA, we reveal a hitherto unknown connection. Using this approach we prove novel non asymptotic convergence statements in terms of the minimax gap for both methods in the context of saddle point problems. In the deterministic and stochastic setting we obtain rates of O(1/k) and O(1/√k), respectively. Concluding, we highlight the relevance of
our proposed method as well as the role of regularizers by showing empirical improvements in the training of Wasserstein GANs on the CIFAR10 dataset.
Organization. This paper is structured as follows. In Section 2 we highlight the connection of GAN training and monotone inclusions and give an extensive review of methods with convergence guarantees for the latter. The main results as well as a precise definition of the measure of optimality are discussed in Section 3. Concluding, Section 4 illustrates the empirical performance in the training of GANs as well as solving bilinear problems.

heading: 2 GAN TRAINING AS MONOTONE INCLUSION
text: The GAN objective was originally cast as a two-player zero-sum game between the discriminator Dy and the generator Gx (Goodfellow et al., 2014) given by
min x max y
Eρ∼q[log(Dy(ρ))] + Eζ∼p[log(1−Dy(Gx(ζ)))],
exhibiting the aforementioned minimax structure. Due to problems with vanishing gradients in the training of such models, a successful alternative formulation called Wasserstein GAN (WGAN) (Arjovsky et al., 2017) has been proposed. In this case the minimization tries to reduce the Wasserstein distance between the true distribution q and the one learned by the generator. Reformulating this distance via the Kantorovich Rubinstein duality leads to an inner maximization over 1-Lipschitz functions which are approximated via neural networks, yielding the saddle point problem
min x max y:‖Dy‖Lip≤1
Eρ∼q[Dy(ρ)]− Eζ∼p[Dy(Gx(ζ))].

heading: 2.1 CONVEX-CONCAVE MINIMAX PROBLEMS
text: Due to the observations made in the previous paragraph we study the following abstract minimax problem
min x∈Rd max y∈Rn
Ψ(x, y) := f(x) + Eξ∼Q [Φ(x, y; ξ)]− h(y), (1)
where the convex-concave coupling function Φ(x, y) := Eξ∼Q [Φ(x, y; ξ)], which hides the stochasticity for ease of notation, is differentiable with L-Lipschitz continuous gradient. The proper, convex and lower semicontinuous functions f : Rd → R ∪ {+∞} and h : Rn → R ∪ {+∞} act as regularizers. A solution of (1) is given by a so-called saddle point (x∗, y∗) fulfilling for all x and y
Ψ(x∗, y) ≤ Ψ(x∗, y∗) ≤ Ψ(x, y∗).
In the context of two-player games this corresponds to a pair of strategies, where no player can be better off by changing just their own strategy.
For the purpose of this motivating section, we will restrict ourselves for now to the special case of the deterministic constrained version of (1), given by
min x∈X max y∈Y Φ(x, y),
where f and h are given by indicator functions of closed convex sets X and Y , respectively. The indicator function δC of a set C is defined as δC(z) = 0 for z ∈ C and δC(z) = +∞ otherwise.

heading: 2.2 MINIMAX PROBLEMS AS MONOTONE INCLUSIONS
text: If the coupling function Φ is convex-concave and differentiable then solving (1) is equivalent to solving the first order optimality conditions which can be written as a so-called monotone inclusion with w = (x, y) ∈ Rm and m = d+ n, given by
0 ∈ F (w) +NΩ(w). (2)
The entities involved are F (x, y) := (∇xΦ(x, y),−∇yΦ(x, y)), (3)
and the normal cone NΩ of the convex set Ω := X × Y . The normal cone mapping is given by
NΩ(w) = {v ∈ Rm : 〈v, w′ − w〉 ≤ 0 ∀w′ ∈ Ω},
for w ∈ Ω and NΩ(w) = ∅ for w /∈ Ω. Here, the operators F and NΩ satisfy well known properties from convex analysis (Bauschke & Combettes, 2011), in particular the first one is monotone (and Lipschitz if ∇Φ is so) whereas the latter one is maximal monotone. We call a, possibly set-valued, operator A from Rm to itself monotone if
〈u− u′, z − z′〉 ≥ 0 ∀u ∈ A(z), u′ ∈ A(z′).
We say A is maximal monotone, if there exists no monotone operator A′ such that the graph of A is properly contained in the graph of A′.
Problems of type (2) have been studied thoroughly in convex optimization, with the most established solution methods being Extragradient (Korpelevich, 1976) and Forward-Backward-Forward (Tseng, 1991). Both methods are known to generate sequences of iterates converging to a solution of (2). Note that in the unconstrained setting (i.e. if Ω is the entire space) both of these algorithms even produce the same iterates.

heading: 2.3 SOLVING MONOTONE INCLUSIONS
text: The connection between monotone inclusions and saddle point problems is of course not new. The application of Extragradient (EG) to minimax problems has been studied in the seminal paper Nemirovski (2004) under the name of Mirror Prox and a convergence rate of O(1/k) in terms of the function values has been proven. Even a stochastic version of the Mirror Prox algorithm has been studied in Juditsky et al. (2011) with a convergence rate of O(1/√k). Applied to problem (2), with PΩ being the projection onto Ω, it iterates
EG: ⌊ wk = PΩ[zk − αkF (zk)] zk+1 = PΩ[zk − αkF (wk)].
The Forward-Backward-Forward (FBF) method, introduced in Tseng (1991), has not been studied rigorously for minimax problems in terms of function values yet, despite promising applications in Boţ et al. (2020) and its advantage of it only requiring one projection, whereas EG needs two. It is given by
FBF: ⌊ wk = PΩ[zk − αkF (zk)] zk+1 = wk + αk(F (zk)− F (wk)). (4)
Both, EG and FBF, have the “disadvantage” of needing two gradient evaluations per iteration. A possible remedy — suggested in Gidel et al. (2019) for EG under the name of extrapolation from the past — is to recycle previous gradients. In a similar fashion we consider
FBFp: ⌊ wk = PΩ[zk − αkF (wk−1)] zk+1 = wk + αk(F (wk−1)− F (wk)), (5)
where we replaced F (zk) by F (wk−1) twice in (4). As a matter of fact, the above method can be written exclusively in terms of the first variable wk by incrementing the index k in the first update and then substituting in the second line. This results in
wk+1 = PΩ [ wk − αk+1F (wk) + αk(F (wk−1)− F (wk)) ] . (6)
This way we rediscover a known method which was studied in Malitsky & Tam (2020) for general monotone inclusions under the name of forward-reflected-backward. It reduces to optimistic mirror descent (Rakhlin & Sridharan, 2013a;b) in the unconstrained case with constant step size αk = α, giving wk+1 = wk − α(2F (wk)− F (wk−1)) (7) which has been proposed for the training of GANs under the name of Optimistic Gradient Descent Ascent (OGDA), see Daskalakis et al. (2018); Daskalakis & Panageas (2018); Liang & Stokes (2019).
All of the above methods and extensions rely solely on the monotone operator formulation of the saddle point problem where the two components x and y play a symmetric role. Taking the special minimax structure into consideration, Hamedani & Aybat (2018) showed convergence of a method
that uses an optimistic step (7) in one component and a regular gradient step in the other, thus requiring less storing of past gradients in comparison to (6).
On the downside, however, by reducing the number of required gradient evaluations per iteration, the largest possible step size is reduced from 1/L (see Korpelevich (1976) or Section 3) to 1/2L (see Gidel et al. (2019); Malitsky & Tam (2020); Malitsky (2015) or Section 3). To summarize, the number of required gradient evaluations is halved, but so is the step size, resulting in no clear net gain.

heading: 2.4 REGULARIZERS
text: The role of regularizers is well studied in many fields such as statistics (Tibshirani, 1996), signal processing (Palomar & Eldar, 2010) or inverse problems (Rudin et al., 1992). They serve different purposes such as inducing sparsity in the solution or conditioning of the problem. In the context of deep learning this has been explored from different perspectives, e.g. in incremental convex neural networks where neurons with zero weights are removed from the network and new ones are inserted according to different policies, see Bach (2017); Bengio et al. (2006); Rosset et al. (2007); Pieper & Petrosyan (2020). Other examples include the box-constraints for WGANs with weight clipping (see Arjovsky et al. (2017)) or spectral normalization (see Miyato et al. (2018)) which has so far rather been considered as part of the architecture, but can at the same time seen as a regularization term of the function values.
In the framework of monotone operator theory the optimality condition of the regularized minimax problem (1) can be written as 0 ∈ F (w) + ∂r(w), (8) where r is given by (x, y) 7→ f(x) + h(y). The possibly set-valued operator ∂r denotes the subdifferential of r and is given by
∂r(w) := {v ∈ Rm : 〈v, w′ − w〉+ r(w) ≤ r(w′) ∀w′ ∈ Rm}.
The monotone inclusion (8) generalizes (2) in a natural way, since NΩ = ∂δΩ. Similarly, the projection constitutes a special case of the so-called proximal mapping which for the function r and λ > 0 is given by
proxλr (w) := arg min w′∈Rm
{ r(w′) + 1
2λ ‖w′ − w‖2
} .
In particular, the proximal mapping of the indicator δΩ yields the projection onto the set Ω, i.e. proxλδΩ = PΩ.

heading: 3 MAIN RESULTS
text: Motivated by the considerations above we study the inclusion problem
0 ∈ F (w) + ∂r(w), (9)
where F : Rm → Rm is a monotone and Lipschitz operator and r : Rm → R ∪ {+∞} is a proper convex lower semicontinuous function.

heading: 3.1 MEASURE OF OPTIMALITY
text: There are two common quantities measuring the quality of a point with respect to the monotone inclusion (8). The most natural one is the distance to the solution set for which typically only asymptotic convergence can be proved. If F arises from a saddle point problem (1) meaning that F has the form (3), we want to use a more problem specific measure, the minimax gap, which for a point w = (u, v) ∈ Rd × Rn is given by
sup y∈Rn Ψ(u, y)− inf x∈Rd
Ψ(x, v) (
= sup x∈Rd,y∈Rn
Ψ(u, y)−Ψ(x, v) ) . (10)
This minimax gap can be interpreted from a game theoretic standpoint as the sum of the maximal payoffs achievable by the two players by playing their respective best responses, given the current
strategy of the opponent. In the more general monotone inclusion setting where no function values are available, an appropriate generalization of (10) is given for any w ∈ Rm by
sup z∈Rm
〈F (z), w − z〉+ r(w)− r(z).
If r is the indicator δΩ of the compact and convex set Ω it is clear that the supremum is only taken over z ∈ Ω and will thus be finite.
The restricted gap. Since the problem (9) is in general unconstrained and the supremum can be infinite we consider instead, as done for example in Nesterov (2007), the restricted gap where the above supremum is taken over an auxiliary compact set B ⊂ Rm instead of the entire space. Note that the restricted gap is in general only a reasonable measure of optimality for elements of B. It is nonnegative on B and zero for points of B which solve (9). Additionally we want to be able to conclude that if a point w∗ has zero gap it solves (9). This is for example the case if w∗ is in the interior of B, which can always be ensured if B is chosen large enough.
In order to capture both at the same time we define the following unifying gap
GB(w) := { sup(x,y)∈B Ψ(u, y)−Ψ(x, v) if F and r come from (1) supz∈B 〈F (z), w − z〉+ r(w)− r(z) otherwise.
(11)

heading: 3.2 METHODS
text: We now present a novel unifying scheme for solving problem (9), which generalizes FBF (4) and in addition recovers the method motivated in (5) as FBFp. Let us point out again that the latter algorithm was already introduced in Malitsky & Tam (2020) and corresponds to OGDA (Rakhlin & Sridharan, 2013a; Daskalakis et al., 2018; Daskalakis & Panageas, 2018) if F stems from the minimax setting (3).
Algorithm 3.1 (generalized FBF). For a starting point z0 ∈ Rm and step sizes αk > 0 we consider for all k ≥ 0 ⌊
wk = proxαkr (zk − αkF (♦k)) zk+1 = wk + αk(F (♦k)− F (wk)).
For ♦k = zk this reduces to the well known FBF method, whereas ♦k = wk−1, with the additional initial condition w−1 = z0, recycles previous gradients (FBFp).
Consider the scenario where F is given as an expectation Eξ[F (· ; ξ)], e.g. coming from (1), and only a stochastic estimator F (· ; ξ) is accessible instead of F itself. In this case we adapt Algorithm 3.1 in the following way.
Algorithm 3.2 (generalized stochastic FBF). For a starting point z0 ∈ Rm and step sizes αk > 0 we consider for all k ≥ 0⌊
ξk ∼ Q (optionally ηk ∼ Q) wk = proxαkr (zk − αkF (♦k;4k)) zk+1 = wk + αk(F (♦k;4k)− F (wk; ξk)).
For ♦k = zk and 4k = ηk this results in a stochastic version of FBF, whereas ♦k = wk−1 and

heading: 4k = ξk−1 recycles previous gradients (stochastic FBFp) with the additional initial condition
text: w−1 = z0 and ξ−1 = η0.
Even though both methods encompassed by the unifying scheme Algorithm 3.1 have been studied in the deterministic setting before, the stated convergence results are new. Note that while the rate for FBF is completely new our result for FBFp provides only a generalization of the known rate for OGDA, see Mokhtari et al. (2019). Similarly, the stochastic version of FBF has been considered before in Bot et al. (2019) and rates have been obtained, but only in terms of the fixed point residual and not the function values. However, we want to point out that the stochastic version of FBFp has not been considered prior to this work.

heading: 3.3 CONVERGENCE
text: Let in the following B ⊂ Rm be the compact set of the restricted (unifying) gap function (11) with D := supw,z∈B ‖z − w‖ denoting its diameter. For convenience in the estimation we assume that the starting point z0 of the discussed methods is in B. Theorem 3.1 (deterministic). Let (wk)k≥0 be the sequence generated by Algorithm 3.1. If
(i) FBF, i.e. ♦k = zk, with step size αk = α ≤ 1/L, or
(ii) FBFp, i.e. ♦k = wk−1, with step size αk = α ≤ 1/2L
is chosen, then for all K ≥ 1 the averaged iterates w̄K := 1K ∑K−1 k=0 wk fulfill
GB(w̄K) ≤ D2
2αK ,
where GB is the restricted gap defined in (11).
In order to derive similar convergence statements for the stochastic algorithm we need to assume (standard) properties of the gradient estimator F (· ; ξ). Assumption 1. Unbiasedness: Eξ[F (w; ξ)] = F (w)∀w ∈ Rm. Assumption 2. Bounded variance: Eξ[‖F (w; ξ)− F (w)‖2] ≤ σ2 ∀w ∈ Rm.
In particular we actually only need the above assumption to hold for all iterates wk. Such an hypothesis is in practice difficult to check, but could be exploited in special cases where additional properties of the variance and boundedness of the iterates are known a priori. Assumption 3. The samples ξk are independent of the iterates wk, for all k ≥ 0.
Equipped with these assumptions we are now able to prove the statement. Theorem 3.2 (stochastic). Let Assumption 1, 2 and 3 hold and let (wk)k≥0 be the sequence generated by Algorithm 3.2. If
(i) stochastic FBF, i.e. ♦k = zk and4k = ηk, with step size αk ≤ α ≤ 1/ √ 2L, or
(ii) stochastic FBFp, i.e. ♦k = wk−1 and4k = ξk−1, with step size αk ≤ α ≤ 1/3L
is chosen, then for all K ≥ 1 the averaged iterates w̄K := ∑K−1
k=0 αkwk∑K−1 k=0 αk fulfill
E[GB(w̄K)] ≤ D2 + 24σ2
∑K−1 k=0 α
2 k∑K−1
k=0 αk ,
where GB is the restricted gap defined in (11).
The above theorem exhibits a classical step size dependence (Robbins & Monro, 1951), yielding convergence for sequences (αk)k≥0 that are square summable ∑∞ k=0 α
2 k < +∞ but not summable∑∞
k=0 αk = +∞. Additionally, if in the setting of Theorem 3.2 the step size is chosen to be αk = α/ √ k + 1, a convergence rate can be obtained and is given by
E[GB(w̄K)] = O ( 1√
K
) . (12)
If the step size does not go to zero, the gap can usually not be expected to vanish either. However, we can still show decrease in the gap up to a residual stemming from the variance. In particular, for a constant step size αk = α we have
E[GB(w̄K)] ≤ D2
αK + 24σ2α. (13)
Additionally, if the number of iterations K is fixed beforehand, a conclusion similar to (12) can be obtained by choosing α = 1/√K in (13).

heading: 4 EXPERIMENTS
text: The aim of this section is to show how the use of methods with convergence guarantees, albeit only in the monotone setting, can yield better training performance for different architectures and objectives. In particular, we demonstrate that FBF can perform at least as good as EG although requiring less evaluations of the regularizers.

heading: 4.1 2D TOY EXAMPLE
text: Following Goodfellow (2016); Mescheder et al. (2018) and others we consider the canonical example minx maxy xy, illustrating the cycling behavior of (even bilinear) minimax problems. We augment this approach by adding a nonsmooth L1-regularizer for one player, with κ > 0, resulting in
min x∈R max y∈[−1,1]
κ|x|+ xy. (14)
The aforementioned issue of GDA (and its proximal extension PGDA) cycling around the solution is highlighted in Figure 1. The other methods, for which we display the averaged iterates, however do converge to a solution and show a decrease in the restricted gap according to theory. Even though the proximal steps provide improvement towards the solution (0, 0) and FBF only uses half the amount of evaluations compared to EG, it outperforms the competing algorithms.

heading: 4.2 WGAN TRAINED ON CIFAR10
text: In this section we apply the above proposed techniques from monotone inclusions to the training of Wasserstein GANs employing DCGAN (Radford et al., 2015) and ResNet (He et al., 2016) architectures. All models are trained on the CIFAR10 dataset (Krizhevsky et al., 2009) which consists of 60,000 images in 10 different classes (with 50,000 training images and 10,000 test images) using an NVIDIA RTX 2080Ti GPU.
For the DCGAN experiments we work with the original WGAN formulation including weight clipping, since it includes regularizers innately (the indicator of a box for the weights of the discriminator). In addition we propose a modification of the WGAN formulation which replaces the box constraint on the discriminator’s weights with an L1-regularization, under the name of WGAN-L1. This results in a soft-thresholding operation instead of the “harsh” clipping.
For the experiments on ResNet we use the WGAN-GP formulation (Gulrajani et al., 2017) which penalizes the norm of the gradient of the discriminator to enforce the Lipschitz constraint, together with spectral normalization of the weight matrices (Miyato et al., 2018) which can be seen as a projection.
Given the ubiquity and dominance of Adam (Kingma & Ba, 2014) as an optimizer for many deep learning related training tasks, instead of using vanilla SGD we opt for Adam updates. This results in a method we call FBF Adam. Analogous approaches have been applied in Gidel et al. (2019) and Daskalakis et al. (2018) resulting in Extra Adam and Optimistic Adam, respectively. We compare the aforementioned methods with the status-quo in GAN training, namely alternating one Adam step for each network: AltAdam1.
Our hyperparameter search was limited to the step sizes when using the WGAN-L1 and WGAN-GP formulation, while all other parameters were kept the same as in Gidel et al. (2019); Boţ et al. (2020). It seems noteworthy that in the case of soft-thresholding bigger step sizes performed better with the only exception of AltAdam1.
The two evaluation metrics used are the Inception Score (IS, higher is better) (Salimans et al., 2016) and the Fréchet inception distance (FID, lower is better) (Heusel et al., 2017), both computed on 50,000 samples. In the case of the IS we use the updated and corrected implementation from Barratt & Sharma (2018). All results are averaged over 5 runs for each method.
In Table 1 the best IS and FID for each method are reported. FBF Adam performs at least as good as all considered competitors with respect to both evaluation metrics. One can also see that WGAN-L1
using the proximal operator improves the performance of all considered methods. Figure 2 shows the training progress regarding IS for each method and both problem formulations. The graphs suggest that making use of WGAN-L1 objective has a stabilizing effect during training, leading to a smoother and more consistent learning curve — a property that only FBF Adam seems to exhibit for weight clipping. Figure 3 as well as Table 1 show that for the WGAN-GP formulation FBF Adam maintains the improved performance of EG compared to GDA, while only requiring half the amount of spectral normalizations, resulting in time savings of up to 10% as reported in Miyato et al. (2018).

heading: 5 CONCLUSION
text: By highlighting the connection between GAN objectives and monotone inclusions, we are able to tackle their training via the Forward-Backward-Forward method which is known to converge to a solution for convex-concave minimax problems. We deepened this theoretical understanding by proving novel convergence rates in terms of the function values. We complement these rigorous considerations by promising practical results, indicating that application of FBF can lead to improved performance and saved computation time (compared to EG).

heading: A DEFINITIONS
text: In Section 2.4 we require the regularizers to be proper, convex and lower semicontinuous which are common properties in convex analysis. We call a function r : Rm → R ∪ {+∞} proper if it is not constant +∞, which means that it takes a finite value for at least a single point. In addition, we say that r is lower semicontinuous if for all z0 ∈ Rm
lim inf z→z0
r(z) ≥ r(z0).
It is easy to see that if C ⊂ Rm is nonempty, closed and convex, then the indicator δC of this set, given by
δC(z) = { 0 if z ∈ C +∞ otherwise
fulfills the assumptions of being proper, convex and lower semicontinuous.

heading: B ABOUT THE GAP FUNCTION
text: Typically in monotone inclusions, the distance to the set of solutions is used as a measure of quality of a given point due to the lack of more specific structure in general. Asymptotic convergence of the iterates has been established for FBF and FBFp in Bauschke & Combettes (2011, Proposition 27.13) and Malitsky & Tam (2020), respectively. Furthermore, no convergence rates can be expected without stronger monotonicity assumptions. We want to take into account the special structure of the monotone inclusion coming from the minimax problem (1). For this reason we use the following (restricted) minimax gap, common for saddle point problems, which for a point (u, v) is given by
GB(u, v) = sup (x,y)∈B
Ψ(u, y)−Ψ(x, v). (15)
For the general case, i.e. F being an arbitrary monotone and Lipschitz operator this is connected to the other measure of optimality we use in (11), for w ∈ Rm given by
GB(w) = sup z∈B 〈F (z), w − z〉+ r(w)− r(z), (16)
where we interpret the possible occurrence of∞−∞ as +∞. It stems from the field of Variational Inequalities where such a function is also known as merit function (Nesterov, 2007). The relevance of the above two quantities will be made clear by the following statements. Theorem B.1. Let Φ : Rd × Rn → R be continuously differentiable and f : Rd → R ∪ {+∞}, h : Rn → R ∪ {+∞} be proper, convex and lower semicontinuous and B ⊂ Rd × Rn. A point (x∗, y∗) in the interior of B solves the saddle point problem (1) if and only if its minimax gap (15) is zero, GB(x∗, y∗) = 0. For all other elements of B the gap is nonnegative.
Proof. A saddle point (x∗, y∗) clearly fulfills that sup(x,y)∈Rd×Rn Ψ(x ∗, y)−Ψ(x, y∗) = 0. On the other hand let GB(x∗, y∗) = 0. For an arbitrary point (x, y) we can choose α ∈ (0, 1) large enough such that (u, v) := α(x∗, y∗) + (1− α)(x, y) is in the interior of B. Therefore,
Ψ(x∗, v)−Ψ(u, y∗) = Ψ(x∗, αy∗ + (1− α)y)−Ψ(αx∗ + (1− α)x, y∗) ≤ 0. Using the convex-concave structure of Ψ we deduce that
αΨ(x∗, y∗) + (1− α)Ψ(x∗, y)− αΨ(x∗, y∗)− (1− α)Ψ(x, y∗) ≤ 0, which implies that Ψ(x∗, y) ≤ Ψ(x, y∗). Since (x, y) was chosen arbitrary (x∗, y∗) is a saddle point.
Similarly, an analogous statement can be shown for (16). The proof, however is split up into multiple lemmas to highlight the connection to Variational Inequalities. Theorem B.2. Let F : Rm → Rm be monotone and continuous, r : Rm → R ∪ {+∞} proper, convex and lower semicontinuous and B ⊂ Rm. A point w∗ in the interior of B solves the monotone inclusion 0 ∈ F (w) + ∂r(w) (17) if and only if its restricted gap (16) is zero, GB(w∗) = 0. For all other elements of B the gap is nonnegative.
Let the assumptions of Theorem B.2 hold true for the following lemmas as we break up the proof into separate statements. We do so by making use of the associated Variational inequality (VI)
find w such that 〈F (w), z − w〉+ r(z)− r(w) ≥ 0 ∀z ∈ Rm. (18) Lemma B.3. The monotone inclusion (17) is equivalent to the VI (18).
Proof. The equivalence of (17) and (18) follows immediately from the definition of the subdifferential of r.
The formulation (18) is typically referred to as the strong form of the VI, whereas
find w such that 〈F (z), z − w〉+ r(z)− r(w) ≥ 0 ∀z ∈ Rm, (19) is known as the weak formulation. Lemma B.4. Under the given assumptions the notion of weak and strong VI are equivalent.
Proof. For the monotone operator F it is clear that if w∗ is a solution to the strong formulation (18), it is also a solution to the weak formulation (19). In fact, if F is continuous the reverse implication also holds true. To see this, let w∗ be a solution to the weak VI (19) and z = αw∗ + (1− α)u for an arbitrary u ∈ Rm and α ∈ (0, 1), then
〈F (αw∗ + (1− α)u), (1− α)(u− w∗)〉+ r(αw∗ + (1− α)u)− r(w∗) ≥ 0. This implies by the convexity of r that
(1− α)〈F (αw∗ + (1− α)u), (u− w∗)〉+ (1− α)(r(u)− r(w∗)) ≥ 0. By dividing by (1− α) and then taking the limit α→ 1 we obtain that w∗ is a solution of the strong form (18).
With the notion of VIs in mind, the above defined gap (16) becomes natural as it measures how much the statement of (19) is violated. Lemma B.5. GB is nonnegative on B and zero for solutions of the weak VI.
Proof. It is clear that GB(w) ≥ 0 for w ∈ B as z = w can be chosen in the supremum. On the other hand if w∗ ∈ B is a solution to the weak VI (19) then GB(w∗) = 0. This follows from the fact that for a solution of (19) for all z ∈ B
〈F (z), w∗ − z〉+ r(w∗)− r(z) ≤ 0. Therefore the supremum over the above expression in z is also less than zero, but clearly zero is obtained for z = w∗.
For the reverse implication to hold true, we may not use points on the boundary of B. Lemma B.6. If a point w∗ in the interior of B exhibits zero gap GB(w∗) = 0, then it is a solution to the weak VI (19).
Proof. Since w∗ is in the interior of B we can, for an arbitrary w ∈ Rm, choose α ∈ (0, 1) large enough such that z := αw∗ + (1− α)w ∈ B. Using this z in the supremum of the gap we deduce that
〈F (αw∗ + (1− α)w), w∗ − αw∗ − (1− α)w〉+ r(w∗)− r(αw∗ + (1− α)w) ≤ 0.
This implies that
(1− α)〈F (αw∗ + (1− α)w), w − w∗〉+ (1− α)(r(w)− r(w∗)) ≥ 0.
By dividing by (1− α) and then taking the limit α→ 1 we deduce that w∗ solves the strong form of the VI (18).
Now, we can turn to proving the theorem.
Proof of Theorem B.2. Combine Lemma B.3, B.4, B.5 and B.6.

heading: C REFINED THEOREMS
text: Recall that restricted (unifying) gap function GB defined in (11) is computed with respect to a set B ⊂ Rm where D := supw,z∈B ‖z − w‖ denotes its diameter and it is assumed that z0 ∈ B. Furthermore, the averaged iterates w̄K for K ≥ 1 are given by
w̄K := ∑K−1 k=0 αkwk∑K−1 k=0 αk .

heading: C.1 DETERMINISTIC STATEMENTS
text: The convergence statement of Theorem 3.1 actually holds true not just for a constant step size as presented in Section 3, but for variable step sizes as well. Theorem C.1. Let (wk)k≥0 be the sequence generated by Algorithm 3.1. If
(i) FBF, i.e. ♦k = zk, with step size 0 < αk ≤ α ≤ 1/L, or
(ii) FBFp, i.e. ♦k = wk−1, with step size 0 < αk ≤ α ≤ 1/2L
is chosen, then for all K ≥ 1
GB(w̄K) ≤ D2 2 ∑K−1 k=0 αk .

heading: C.2 STOCHASTIC STATEMENTS
text: We actually prove a slightly more general version of Theorem 3.2. In particular the step size can be chosen larger than initially claimed, however, at the cost of a worse constant. Theorem C.2. Let Assumption 1, 2 and 3 hold and let (wk)k≥0 be the sequence generated by FBF, i.e. Algorithm 3.2 with ♦k = zk and4k = ηk. Let the step size αk ≤ α < 1L , then
E[GB(w̄K)] ≤ D2 + 4(1− α2L2)−1σ2
∑K−1 k=0 α 2 k
2 ∑K−1 k=0 αk
,
for all K ≥ 1.
Theorem 3.2 (i) can be deduced from the above statement by using α = 1/√2L which yields that (1− α2L2)−1 = 2.
Theorem C.3. Let Assumption 1, 2 and 3 hold and let (wk)k≥0 be the sequence generated by FBFp, i.e. Algorithm 3.2 with ♦k = wk−1 and4k = ξk−1. Let the step size αk ≤ α < 12√2L , then
E[GB(w̄K)] ≤ D2 + 6
( 1 + 4α 2L2
1−8α2L2 ) σ2 ∑K−1 k=0 α
2 k∑K−1
k=0 αk ,
for all K ≥ 1.
Theorem 3.2 (ii) is obtained from the above theorem by using the particular step size bound of α = 1/3L, which yields that
4α2L2
1− 8α2L2 = 4.
Although, the step size in the refined statements Theorem C.2 and C.3 can be chosen arbitrarily close to 1/L and 1/(2√2L) for stochastic FBF and stochastic FBFp, respectively. This does not mean it should be — since the constant in the convergence rate deteriorates when the step size is close to its allowed upper bound.

heading: D PROOFS

heading: D.1 PREPARATIONS
text: We introduce the notation connected to the strong formulation of the VI (18) associated to the monotone inclusion (9), given by
g(w, z) := 〈F (w), w − z〉+ r(w)− r(z), for g : Rm × Rm → R ∪ {+∞}. Next we will establish the fact that this function can be used to bound the (restricted) unifying gap function, which we remind, is defined as
GB(w) = { sup(x,y)∈B Ψ(u, y)−Ψ(x, v) if F is (3) supz∈B 〈F (z), w − z〉+ r(w)− r(z) otherwise,
where in the first case (u, v) ∈ Rd × Rn is identified with w ∈ Rm. In particular the dimensions fulfill d+ n = m, and r(w) is given by f(u) + h(v). Lemma D.1. It holds that for all K ≥ 1
sup z∈B
{ 1∑K−1
k=0 αk K−1∑ k=0 αkg(wk, z)
} ≥ GB(w̄K).
Proof. First we will prove the case if F is derived from a saddle point problem. Note that from the convex-concave structure of Φ we get that
Φ(u, y) ≤ Φ(u, v) + 〈∇yΦ(u, v), y − v〉 and Φ(u, v) + 〈∇xΦ(u, v), x− u〉 ≤ Φ(x, v). By summing the two up we obtain
Φ(u, y)− Φ(x, v) ≤ 〈 −∇xΦ(u, v), x− u ∇yΦ(u, v), y − v 〉 .
We can reformulate the above inequality in terms of g to see that for z = (x, y) ∈ Rd × Rn
〈F (w), w − z〉 ≥ Φ(u, y)− Φ(x, v). The statement of the first case is obtained by adding r(w)− r(z) on both sides and using the fact that Ψ is convex-concave.
If F is a general monotone operator, then we use its monotonicity to deduce that
〈F (w), w − z〉 ≥ 〈F (z), w − z〉. The desired result follows from using the linearity of the inner product.
Notation. We denote the error of the stochastic estimator via Zk := F (♦k;4k)− F (♦k) and Wk := F (wk; ξk)− F (wk). (20)
Furthermore, we will denote via E[ · |U ], the conditional expectation with respect to the random variable U .
We will also need the following lemma. Lemma D.2. Let (pk)k≥0 ∈ Rd be a given sequence and (vk)k≥0 recursively defined for all k ≥ 0 by vk+1 := vk − pk for some v0 ∈ Rd, then
K−1∑ k=0 〈pk, vk − u〉 ≤ 1 2 ‖v0 − u‖2 + 1 2 K−1∑ k=0 ‖pk‖2.
Proof. From the three point identity it follows immediately that
〈pk, vk − u〉 = 〈vk − vk+1, vk − u〉 = 1
2
( ‖vk − u‖2 − ‖vk+1 − u‖2 + ‖vk+1 − vk‖2 ) from which the statement of the lemma follows.

heading: D.2 A UNIFIED DECREASE RESULT
text: We will start with a unifying proposition which covers the common parts of all convergence proofs. Proposition D.3. For a γ > 0 we have that for all k ≥ 0 and z ∈ Rm
αkg(wk, z) + 1
2 ‖zk+1 − z‖2 ≤
1 2 ‖zk − z‖2 − 1 2 ‖zk − wk‖2 + 1 2 (1 + γ)α2kL 2‖♦k − wk‖2
+ αk 〈Wk, z − wk〉+ (1 + γ−1)α2k(‖Wk‖2 + ‖Zk‖2). (21)
Proof. Let k ≥ 0 and z ∈ Rm be arbitrary. Using the decomposition (20) it follows that 〈αkF (wk; ξk), wk − z〉 = αk〈Wk, wk − z〉+ αk〈F (wk), wk − z〉. (22) Since proxαkr = (Id + αk∂r) −1 we deduce that 〈z − wk, wk − zk + αkF (♦k;4k)〉 ≥ αk(r(wk)− r(z)). (23) Adding (22) and (23) gives that 〈αk(F (wk; ξk)− F (♦k;4k)) + zk − wk, wk − z〉 ≥ αk 〈Wk, wk − z〉+ αkg(wk, z),
which, using the definition of zk+1, is equivalent to 〈z − wk, zk+1 − zk〉 ≥ αk〈Wk, wk − z〉+ αkg(wk, z). (24)
We estimate the inner product on the left side of the inequality by inserting and subtracting zk and using the three point identity twice to deduce 〈z − wk, zk+1 − zk〉 = 〈z − zk + zk − wk, zk+1 − zk〉
= 1
2
( ‖z − zk‖2 − ‖zk+1 − z‖2 + ‖zk+1 − wk‖2 − ‖zk − wk‖2 ) . (25)
The first two summands are fine as they will telescope, so we are left with estimating ‖zk+1 − wk‖2. By the definition of zk+1 we have that
‖zk+1 − wk‖2 = α2k‖F (♦k;4k)− F (wk; ξk)‖2
= α2k‖F (♦k)− F (wk) + Zk −Wk‖2 ≤ (1 + γ)α2k‖F (♦k)− F (wk)‖2 + (1 + γ−1)α2k‖Zk −Wk‖2 ≤ (1 + γ)α2kL2‖♦k − wk‖2 + 2(1 + γ−1)α2k(‖Zk‖2 + ‖Wk‖2),
(26)
where we inserted and subtracted F (♦k) and F (wk) and applied Young’s inequality to deduce the result. Adding (26), (25) and (24) we conclude that
αkg(wk, z) + 1
2 ‖zk+1 − z‖2 ≤
1 2 ‖zk − z‖2 − 1 2 ‖zk − wk‖2 + 1 2 (1 + γ)α2kL 2‖♦k − wk‖2
+ αk 〈Wk, z − wk〉+ (1 + γ−1)α2k(‖Wk‖2 + ‖Zk‖2).

heading: D.3 FORWARD-BACKWARD-FORWARD
text: Proof for deterministic FBF, Theorem C.1 (i). We start off by plugging ♦k = zk into (21). Since Wk = Zk = 0 we can use γ → 0 to deduce that for all k ≥ 0
αkg(wk, z) + 1
2 ‖zk+1 − z‖2 ≤
1 2 ‖zk − z‖2 − 1 2 (1− α2kL2)‖zk − wk‖2.
From this it is clear that the step size is constrained by α ≤ 1/L as stated in the theorem. By summing up from k = 0 to K − 1 and dividing by ∑K−1 k=0 αk we obtain
1∑K−1 k=0 αk K−1∑ k=0 αkg(wk, z) ≤ ‖z0 − z‖2 2 ∑K−1 k=0 αk .
The claimed statement is then derived by taking the supremum in z over B and applying Lemma D.1.
Proof for stochastic FBF, Theorem C.2. Plugging ♦k = zk and 4k = ηk into (21) gives for all k ≥ 0
αkg(wk, z) + 1
2 ‖zk+1 − z‖2
≤ 1 2 ‖zk − z‖2 − 1 2 (1− (1 + γ)α2kL2)‖zk − wk‖2 + αk 〈Wk, z − vk〉
+ αk 〈Wk, vk − wk〉+ (1 + γ−1)α2k(‖Wk‖2 + ‖Zk‖2). By summing this inequality up and applying Lemma D.2 with v0 = z0, pk = −αkWk and vk+1 := vk − pk we deduce that
K−1∑ k=0 〈−αkWk, vk − z〉 ≤ 1 2 ‖z0 − z‖2 + 1 2 K−1∑ k=0 α2k‖Wk‖2, (27)
and therefore K−1∑ k=0 αkg(wk, z) ≤ ‖z0 − z‖2 + K∑ k=0 αk 〈Wk, vk − wk〉+ 2(1 + γ−1)α2k(‖Wk‖2 + ‖Zk‖2). By choosing γ such that α = ( √ 1 + γL) −1 we deduce that 1 + γ−1 = 1/(1 − α2L2). Next, we take the supremum over z ∈ B and the expectation to obtain
E [ sup z∈B { K−1∑ k=0 αkg(wk, z) }] ≤ D2 + 4(1− α2L2)−1σ2 K−1∑ k=0 α2k,
where we used that E[〈Wk, vk − wk〉] = E [ E [ 〈Wk, vk − wk〉 ∣∣w[k], ξ[k−1]]] = E [〈 E [ Wk
∣∣w[k], ξ[k−1]], vk − wk〉] = 0, with ξ[k−1] = (ξ0, . . . , ξk−1) and w[k] = (w0, . . . , wk). The final statement follows by dividing by∑K−1
k=0 αk and applying Lemma D.1.

heading: D.4 FORWARD-BACKWARD-FORWARD-PAST
text: Proof for deterministic FBFp, Theorem C.1 (ii). We start off by plugging ♦k = zk into (21). Since Wk = Zk = 0 we can use γ → 0 to conclude that for all k ≥ 0
αkg(wk, z) + 1
2 ‖zk+1 − z‖2 ≤
1 2 ‖zk − z‖2 − 1 2 ‖zk − wk‖2 + 1 2 α2kL 2‖wk−1 − wk‖2. (28)
Now we need to bound the term ‖wk−1 − wk‖2 by ‖zk − wk‖2. Since
2‖zk − wk‖2 + 2‖zk − wk−1‖2 ≥ ‖wk − wk−1‖2 (29)
we have for all k ≥ 1
‖zk − wk‖2 ≥ −‖zk − wk−1‖2 + 1
2 ‖wk−1 − wk‖2
≥ −α2k−1L2‖wk−1 − wk−2‖2 + 1
2 ‖wk−1 − wk‖2
(30)
whereas for k = 0, since w−1 = z0, we have that
‖z0 − w0‖2 = ‖w−1 − w0‖2. (31) Plugging (31) into (28) for k = 0 we get that
α0g(w0, z) + 1
2 ‖z1 − z‖2 +
1 2 (1− α20L2)‖w0 − w−1‖2 ≤ 1 2 ‖z0 − z‖2. (32)
Plugging (30) into (28) we get that for all k ≥ 1
αkg(wk, z) + 1
2 ‖zk+1 − z‖2 +
1
2
( 1
2 − α2kL2
) ‖wk − wk−1‖2
≤1 2 ‖zk − z‖2 + 1 2 α2k−1L
2‖wk−1 − wk−2‖2. (33)
In order to be able to telescope we need to ensure that for all k ≥ 0( 1
2 − α2kL2
) ≥ α2kL2.
This is equivalent to the condition αk ≤ 1/2L which was required in the statement of the theorem. Now we sum up (33) from k = 1 to K − 1 which yields
K−1∑ k=1 αkg(wk, z) + 1 2 ‖zK − z‖2 + 1 2 ( 1 2 − α2K−1L2 ) ‖wK−1 − wK−2‖2
≤ 1 2 ‖z1 − z‖2 + 1 2 α20L 2‖w0 − w−1‖2.
(34)
Adding (34) and (32) and dividing by ∑K−1 k=0 αk to deduce
1∑K−1 k=0 αk K−1∑ k=0 αkg(wk, z) ≤ ‖z0 − z‖2 2 ∑K−1 k=0 αk ,
where we used that 1 − α20L2 ≥ α20L2 to get rid of ‖w0 − w−1‖2. The final statement follows by taking the supremum in z over B and applying Lemma D.1.
Proof for stochastic FBFp, Theorem C.3. By using ♦k = wk−1 we deduce from (21) for all k ≥ 0 that
αkg(wk, z) + 1
2 ‖zk+1 − z‖2 ≤
1 2 ‖zk − z‖2 − 1 2 ‖zk − wk‖2 + 1 2 (1 + γ)α2kL 2‖wk−1 − wk‖2
+ αk 〈Wk, z − wk〉+ 2(1 + γ−1)α2k(‖Wk‖2 + ‖Zk‖2). As in (27) we can split 〈αkWk, z−wk〉 into 〈αkWk, z−vk〉+〈αkWk, vk−wk〉 and use Lemma D.2 to deduce
K−1∑ k=0 αkg(wk, z) ≤ ‖z0 − z‖2 − K−1∑ k=0 (1 2 ‖zk − wk‖2 + 1 2 (1 + γ)α2kL 2‖wk−1 − wk‖2
+ 〈αkWk, vk − wk〉+ 3(1 + γ−1)α2k(‖Wk‖2 + ‖Zk‖2) ) .
Taking now the supremum over z ∈ B and then the expectation we conclude that the inequality
E [ sup z∈B { K−1∑ k=0 αkg(wk, z) }] ≤ D2 − 1 2 K−1∑ k=0 ( ‖zk − wk‖2 − (1 + γ)α2kL2‖wk−1 − wk‖2 ) + 3(1 + γ−1)σ2
K−1∑ k=0 α2k
(35)
holds. Let from now on k ≥ 1 as we will treat the case k = 0 separately. Using (29) we deduce that
‖zk − wk‖2 ≥ −‖zk − wk−1‖2 + 1
2 ‖wk−1 − wk‖2
≥ −α2k−1‖F (wk−1; ξk−1)− F (wk−2; ξk−2)‖2 + 1
2 ‖wk−1 − wk‖2.
(36)
Now we bound the difference of the two estimators by inserting±F (wk−1),±F (wk−2) and applying the inequality ‖a+ b+ c‖2 ≤ 3(‖a‖2 + ‖b‖2 + ‖c‖2) which yields ‖F (wk−1; ξk−1)− F (wk−2; ξk−2)‖2 ≤ 3‖Wk−1‖2 + 3‖Wk−2‖2 + 3‖F (wk−2)− F (wk−1)‖2.
We conclude that E [ ‖F (wk−1; ξk−1)− F (wk−2; ξk−2)‖2 ] ≤ 6σ2 + 3L2E‖wk−1 − wk−2‖2. (37)
Using (37) in (36) we deduce that
E‖zk − wk‖2 ≥ −α2k−1(6σ2 + 3L2E‖wk−1 − wk−2‖2) + 1
2 E‖wk−1 − wk‖2, (38)
whereas for k = 0 we have (31). Now we plug (38) into (35) to conclude that
E [ sup z∈B { K−1∑ k=0 αkg(wk, z) }]
≤ D2 − 1 2 K−1∑ k=1 ( −3α2k−1L2E‖wk−1 − wk−2‖2 + (1 2 − (1 + γ)α2kL2 ) ‖wk−1 − wk‖2 )
+ 1
2 ((1 + γ)α20L 2 − 1)‖w−1 − w0‖2 + 6(1 + γ−1)σ2 K−1∑ k=0 α2k
(39) From this we conclude that in order to be able to telescope we need to enforce(
1 2 − (1 + γ)α2kL2
) ≥ 3α2kL2
which is equivalent to 1
2(4 + γ) ≥ α2kL2.
Since αk ≤ α, we can ensure this by choosing γ such that 1
2(4 + γ) = α2L2. (40)
With (40) in place conclude from (39) that the inequality
E [ sup z∈B { K−1∑ k=0 αkg(wk, z) }]
≤ D2 + 1 2 ((4 + γ)α20L 2 − 1)‖w−1 − w0‖2 + 6(1 + γ−1)σ2 K−1∑ k=0 α2k
Using the fact that 3α20L 2 ≤ 1− (1 + γ)α20L2 from (40) to discard the ‖w0 − w−1‖2 term, yields
E [ sup z∈B { K−1∑ k=0 αkg(wk, z) }] ≤ D2 + 6(1 + γ−1)σ2 K−1∑ k=0 α2k (41)
Through (40), we can estimate 1
γ =
2α2L2
1− 8α2L2 . (42)
Plugging (42) into (41), dividing by ∑K−1 k=0 αk and applying Lemma D.1, deduces the final statement.

heading: Discriminator

heading: Generator

heading: E.2 RESNET

heading: Discriminator

heading: Generator

heading: E.1 DCGAN

heading: E ARCHITECTURE

heading: F HYPERPARAMETERS
text: For the WGAN formulation with weight clipping, see Table 4, we used the extensively tuned hyperparameters from Gidel et al. (2019) for ExtraAdam, Adam1 and OptimisticAdam. Note that our values of the Inception Score (IS) differ from the ones reported in Gidel et al. (2019) as we use the newer implementation of the IS proposed in Barratt & Sharma (2018). For FBF-Adam we tuned the step size and kept all other hyperparameters equal.
For our newly proposed WGAN-L1 formulation using 1-Norm regularization, see Table 5, we limited the hyperparameter search to the step sizes, with the values in Table 4 as initial guesses. We chose the value performing the best in terms of IS and FID for a sample seed. All other parameters were kept the same as in Gidel et al. (2019); Boţ et al. (2020).
For the experiments based on the WGAN-GP formulation including spectral normalization we limited the hyperparameter search to the step sizes, with the values recommended in Gidel et al. (2019) as initial guesses. We used a single power iteration for the spectral normalization as suggested in Miyato et al. (2018) and reduced the number of generator updates by a factor of two to ease the computational burden.

Review summaries:
The authors in this paper, inspired by the applications of min-max optimization in GANs, study the problem of min-max optimization for convex-concave functions. The main contribution of the paper is proving novel convergence results for Forward-Backward-Forward (FBF) algorithms as well as Optimistic Gradient Descent Ascent (OGDA) based on tools from monotone inclusion problems. Their convergence results cover both deterministic and stochastic settings and the rates of convergence for suitably chosen gap function are non-asymptotic. Finally, they apply their algorithms both on toy problems but also on training GANs on CIFAR-10.

This work studies minimax optimization (a.k.a saddle-point problems) with nonsmooth regularizers. By leveraging the monotone operator theory, the authors propose to use the forward-backward-forward method so as to avoids the notorious limit cycling problem. The classical FBF method requires two gradient evaluations per step, the authors introduce a new algorithm which reuses the past gradient in the same way as OGDA. In the setting of convex-concave minimax optimization, the authors claim to prove novel convergence rates for both methods.