Two steps at a time --- taking GAN training in stride with Tseng's method
Authors: Axel Böhm
Michael Sedlmayer
Ernö Robert Csetnek
Radu Ioan Bot
Venue:  (2021)

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 \emph{monotone operator} theory, in particular the \emph{Forward-Backward-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 \emph{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 $\mathcal{O}(\nicefrac{1}{k})$ and $\mathcal{O}(\nicefrac{1}{\sqrt{k}})$, respectively.
We complement our theoretical results with empirical improvements in the training of Wasserstein GANs on the CIFAR10 dataset.

Under review as a conference paper at ICLR 2021
Two STEPS AT A TIME TAKING GAN TRAINING IN STRIDE WITH TSENG'S METHOD
Anonymous authors Paper under double-blind review
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 Forward- Backward-Forwal (FBF) method, which avoids the known issue of limit cycling by correcting each update by second gradient evaluation. Furthermore, we propose a seemingly new scheme which recycles old gradients to mitigate the additional computational cost. In doing 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 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 convergence rate of (1/x)) and ((4/V)), respectively. We complement our theoretical results with empirical improvements the training of Wasserstein GANs on the CIFAR10 dataset.
INTRODUCTION
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 zero game this task can be formulated 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 suggested in Gidel
ctt al. (2019), whereas Daskalakis et al. (2018); Daskalakis & Panageas| 2018); Liang & Stokes (019) studied Optimistic Gradient Descent Ascent (OGDA) based on optimistic mirror descent (Rakhlin &
Sridharan 2013a b). We however investigate the Forward-Backward Backward-Forward (FBF) method (Tseng
1991) from monotone operator theory, which uses two gradient evaluations per update, similar EG,
in order to circumvent the aforementioned issues.
Instead of trying 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 moti- vates to use the FBF method, originally designed to solve this type of problems. This approach allows to naturally extend the constrained setting 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 known method, related to OGDA. By developing a unifying scheme that captures FBF and generalization of OGDA, we reveal a hitherto unknown connection. Using this approach 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 obtain rates of O(1/s) and O(IVE). respectively. Concluding, highlight the relevance of

---

Under review as a conference paper at ICLR 2021
proposed method well the role of regularizers by showing empirical improvements in the training of Wasserstein GANs on the CIFARIO dataset.
Organization. This paper is structured as follows. In Section 2 we highlight the connection of GAN training and monotone inclusions and give extensive review of methods with convergence guarantees for the latter. The main results as well as a precise definition of the measure of optimality discussed in Section Concluding. Section iillustrates fillutttall the empirical performance in the training of GANs as well as solving bilinear problems.
2 GAN TRAINING AS MONOTONE INCLUSION
The GAN objective originally cast two-player zero-sum game between the discriminator D, and the generator G2 (Goodfellow et al. 2014) given by
min max E (log D (p)) + B DDy(G
exhibiting the aforementioned minimax structure. Due problems with vanishing gradients in the training of such models, a successful alternative formulation called Wasserstein GAN (WGAN) (Ar) jovsky et al. 2017) has been proposed. In this case the minimization tries to reduce the Wasserstein distance between the true distribution and the one learned by the generator. Reformulating this distance via the Kantorovich Rubinstein duality leads an inner maximization over 1-Lipschitz functions which are approximated via neural networks, yielding the saddle point problem
min max E Ep-glDy(p)] - Ee (Dy(((())))
2.1 CONVEX-CONCAVE MINIMAX PROBLEMS
Due to the observations made in the previous paragraph study the following abstract minimax problem
min max ((r,y) = f(x) + Ee-q ( y E)] h(y), BER yER"
(I)
where the convex- coupling function (z. y) == Eg~q (0 y: E)]. which hides the stochas- ticity for ease of notation, is differentiable with T--Lipschitz continuous gradient. The proper, convex and lower semicontinuous functions f TR - TR U {+o)} and h : R - U [+00] act as regularizers. solution of ([) is given by so-called saddle point (a* .y" fulfilling for all and y
(x"" 4) V( ,v") ((r,y").
In the context of two-player games this corresponds a pair of strategies, where no player can be better off by changing just their own strategy.
For the purpose of this motivating section, will restrict ourselves for now the special of the deterministic constrained version of (I) given by
min max ((r,)), zeX yeY
where f and are given by indicator functions of closed convex sets and Y, respectively. The indicator function de of set C' is defined dz(2) for C and (c(=) = +oo otherwise.
2.2 MINIMAX PROBLEMS AS MONOTONE INCLUSIONS
If the coupling function & convex-concave and differentiable then solving [ is equivalent to solving the first order optimality conditions which can be written as so-called monotone inclusion with w (x. v) E R.m and d + n, given by
e F(w) No(w).
The entities involved are
F(x,y) = (V. -V,
(3)
2

---

Under review as a conference paper at ICLR 2021
and the normal cone Na of the convex set Ω X x Y. The normal cone mapping is given by
(w) = {ur E I (u, we
w) I 0 Vw' EΩ),
for w and Na(w) for w & Here, the operators F and Ng satisfy well known properties from convex analysis (Bauschke & Combettes] 2011), in particular the first one is monotone (and Lipschitz V is so) whereas the latter one is maximal monotone. call a, possibly set-valued, operator A from E" to itself monotone if
(u u', 2')
Yu E A(z), E A(²).
We say is maximal monotone, if there exists no monotone operator A' such that the graph of 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 Baatund-accward-Foie Forward (Tseng)
1991). Both methods are known to generate sequences of iterates converging to solution of (2) Note that in the unconstrained setting (i.e. if Q2 is the entire space) both of these algorithms even produce the same iterates.
2.3 SOLVING MONOTONE INCLUSIONS
The connection between monotone inclusions and saddle point problems is of course new. The application of Extragradient (EG) to minimax problems has been studied in the seminal paper[Ne mirovski (2004) under the name of Mirror Prox and a convergence rate of O1/k) in terms of the function values has been proven. Even stochastic version of the Mirror Prox algorithm has been studied in Juditsky et al. (2011) with a convergence rate of ((IVE). Applied to problem (2), with Po being the projection onto Ω2 it iterates
Wk Pa|za (=x)] žk+1 = Pa(= ax
EG:
The BrwwwardBaacward----a 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. is given by
(FBF) method, introduced in Tseng 1991]. has not been studied
Pa[=x- agF
FBF:
(4)
Fk+1 = wy + ork (F(x)) F(wr))-
Both, EG and FBF, have the "disadvantage" of needing two gradient evaluations per iteration. A possible remedy suggested in Gidel al. (2019) for EG under the name of extrapolation from the past is to recycle previous gradients. In a similar fashion we consider
wh = Pa(=s og F(wx-1)) Zk+1 we ar (F(w F(wx)),
FBFp:
(5)
where we replaced F(2x) by F(wa-1) twice in 4 As matter of fact, the above method can be written exclusively in terms of the first variable we by incrementing the index & in the first update and then substituting in the second line. This results
wk+1 Pn. [ - ax+1 F(wx) + ag (F(WW())))- - F(wx))
This way we rediscover known method which studied in Malitsky & Tam (0000) for general monotone inclusions under the name of cewward-reflecteedeee wackeardda..dddd...... It reduces to optimistic mirror descent (Rakhlin & Sridharan 2013a b) in the unconstrained case with constant step size ag a. giving
Wk++1 wi o(2F(wz) F(wk-1))
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 the monotone operator formulation of the saddle point problem where the two components z and y play a symmetric role. Taking the special minimax structure into consideration, Hamedani & Aybat (018) showed convergence of method
3

---

Under review as a conference paper at ICLR 2021
that uses optimistic step 7 in one component and regular gradient step in the other, thus requiring less storing of past gradients in comparison to 66
On the downside, however, by reducing the number of required gradient evaluations per iteration, the largest possible step size is reduced from I/L (sec Korpelevich 1976) or Section to 1/2L (see Gidel et al. (2019); Malitsky & 'amm (2020) Malitsky] (2015) Section(3) To summarize, the number of required gradient evaluations is halved, but so is the step size, resulting in no clear net gain.
2.4 REGULARIZERS
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 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. (006);; Rosset et al. (2007): ) Pieper & Petrosyan (2020). Other examples include the box- cox-constraints for WGANs with weight clipping (see Arjovsky et al. (017)) )) or spectral normalization (see Miyato et al 2018) which has so far rather been considered part of the architecture, but at the same time
regularization
term the function values.
In the framework of monotone operator theory the optimality condition of the regularized minimax problem (T) can be written as
0 E F(w) + ar(w),
(8)
where is given by (x. v) + f(x) h(y). The possibly set-valued operator Ör denotes the subdifferential of and is given by
0r(w) = {u E Rm - r(w) S r(w') Vu' E RR
The monotone inclusion { generalizes 2 in natural way, since No 062. Similarly, the projection constitutes special case of the so-called proximal mapping which for the function r and is given by
prox (w) == arg min (r(w') wr
- 11 wl]}]
1 2X
In particular, the proximal mapping of the indicator ón yields the projection onto the set Ω i.e. prox Pn-
MAIN RESULTS
Motivated by the considerations above we study the inclusion problem
0 E F (w) + ar(w),
where F: RT + RT is monotone and Lipschitz operator r R + R {RU(+00) is proper convex lower semicontinuous function.
3.1 MEASURE OF OPTIMALITY
There are two common quantities measuring the quality of point with respect to the monotone inclusion ( The most natural one is the distance to the solution set for which typically only asymptotic convergence can be proved. F' arises from a saddle point problem ( meaning that 33, we want to more problem specific measure, the minimax gap, which for point w (u, v) E Rd x R" is given by
F has the form
sup (u, inf v (x, () VER*
sup V(u - ((( ZERO YER"
(10)
SER
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
4

---

Under review as a conference paper at ICLR 2021
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 E IR" by
sup mm
(F(=), w r(w)) r(z).
If r is the indicator óg of the compact and convex set 52 it is clear that the supremum is only taken over & E Q 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 auxiliary compact set B R" instead of the entire space. Note that the restricted gap is in general only reasonable measure of optimality for elements of B. It nonnegative on B and zero for points of which solve 9 Additionally we want be able to conclude that if 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 ensured if B is chosen large enough.
In order to capture both at the same time we define the following unifying gap
()) (u, v) (x, suppEB (F(z), 2) +r(w) -r()) otherwise.
if F and r come from
(n(w)=
(11)
3.2 METHODS
We now present a novel unifying scheme for solving problem ()) which generalizes FBF (4 and in addition recovers the method motivated in FBFp. Let us point 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 starting point zo E Rm and step sizes aş we consider
for all k 2 0
Wk = prox (2s - ag (()x)) Zk++1 Wk + (F())()) F(wx))-
For Qx =z this reduces to the well known FBF method, whereas Qk = Wk-1, with the additional initial condition w-1 20, recycles previous gradients (FBFp).
Consider the scenario where is given as an expectation [x[F((;E)] e.g. coming from (.. and only stochastic estimator F(::E) 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 E 1.th and step sizes we consider for all
εK Q (optionally mi ~ Q) Wg prox, (2t Fax (x))
2k+1 wh. + on (F(m; Du) ) - (wwE5 Ex)).
For Qb = 2k and DE Ths this results in stochastic version of FBF, whereas Qx = W and
De Ek-1 recycles previous gradients (stochastic FBFp) with the additional initial condition
W-1 = 20 and E-1 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 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.
5

---

Under review as a conference paper at ICLR 2021
3.3 CONVERGENCE
Let in the following B C Rm be the compact set of the restricted (unifying) gap function with D e 2 w| denoting its diameter. For convenience in the estimation assume that the starting point of the discussed methods is in B.
Theorem (deterministic). Let (wa) be the sequence generated by Algorithm 3.1 If
(i) FBF, i.e. QE with step size a = a S 1/2, or (ii) FBFp, i.e. Qx wk-1, with step size a₁ = S 1/2L
chosen, then for all K 2 1 the averaged iterates wk == k ER=0 we fulfill
D
GB(üx) - 2aK
where GB the restricted gap defined in
In order to derive similar convergence statements for the stochastic algorithm we need to assume (standard) properties of the gradient estimator E):
Assumption 1. Unbiasedness: EEg [Fw:; [)] F(w) Ve R.
Assumption 2. Bounded variance: Eg (w:: ( E) F(w)ll S o² Ve RR.
In particular we actually only need the above assumption to hold for all iterates wi- 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 priori.
Assumption 3. The samples ε are independent of the iterates wh. for all k 2 0.
Equipped with these assumptions we are now able to prove the statement.
Theorem 3.2 (stochastic). Let Assumption 7 and hold and let (wx))z2) be the sequence generated
by Algorithm 3.2 If
(i) stochastic FBF, i.e. 4x = and 4 The with step size a S a S 1/V2L, or
(ii) stochastic FBFp, i.e. Qx= wk-1 and Db Ex-1, with step size an S S 1/3L
is chosen, then for all K 2 1 the averaged iterates WK = E1 an fulfill
Σt- az
D2 + 240 K-1
-k=00 ox.
B[GB(Tk)]
Σ k=0 axk
where GB the restricted gap defined in
The above theorem exhibits classical step size dependence (Robbins & Monro 1951), yielding convergence for sequences (ax);20 that are square summable Lk=0 a +oo but not summable
E O +oc. Additionally, if in the setting of Theorem 3.2 the step size is chosen to be as a/ Vk + 1, convergence rate can be obtained and is given by
B[GB(Øx)) = ( (VR
(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 the gap up to residual stemming from the variance. In particular, for constant step size ark have
D
B[GB(Tk)] S ak + 240
(13)
Additionally, if the number of iterations is fixed beforehand, a conclusion similar to can be obtained by choosing 1/VR in (3).

---

Under review as a conference paper at ICLR 2021
4 EXPERIMENTS
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.
4.1 2D TOY EXAMPLE
Following Goodfellow (016); Mescheder et al. (2018) and others we consider the canonical example min, maxy zy, illustrating the cycling behavior of (even bilinear) minimax problems. We augment this approach by adding a nonsmooth Li-regularizer for one player, with k >> 0, resulting
min max k//z| + zy.
(14)
zER yE[-1,1]
The aforementioned issue of GDA (and its proximal extension PGDA) cycling around the solution is highlighted in Figure [ The other methods, for which display the averaged iterates, however do converge to solution and show 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.
EGr x- 65
12
18
18P 2=10
No
NEB 001
06 1
25
30
(a) Trajectories converging to solution.
(b) Restricted gap function.
Figure 1: A comparison of the methods presented in Section 2.3 applied problem (1) with K = 0.01. PGDA denotes (alternating) gradient descent ascent with proximal steps. As mentioned in the introduction it fails converge. EGp denotes the method presented in Gidel et al. (2019) as extrapolation from the past. For the restricted gap we use B₁ = B2 = 1-1,
4.2 WGAN TRAINED ON CIFARIO
In this section we apply the above proposed techniques from monotone inclusions to the training of Wasserstein GANs employing DCGAN (Radford et al.] 2013) and ResNet (He et al. 2016) architectures. All models are trained on the CIFARTO dataset (Krizhevsky 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 clip- ping, since includes regularizers innately (the indicator box for the weights of the discriminator). In addition propose modification of the WGAN formulation which replaces the box constraint on the discriminator's weights with an LI reegulaarizatinn under the name of WGAN-LI. This results in thrshhliesoo 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 enforee the Lipschitz constraint, together with spectral normalization of the weight matrices (Miyato et al. 2018) which can be seen as a projection.
7

---

Under review as a conference paper at ICLR 2021
Table 1: The best Inception Score (IS) and Fréchet Inception Distance (FID), The column denoted by WGAN, WGAN-LI and WGAN-GP refers to the standard formulation with weight clipping, our regularized implementation using the 1-norm and the formulation with gradient penalty and spectral normalization, respectively.
WGAN
WGAN-LI
WGAN-GP
IS
FID
IS
FID
IS
FID
Method
AltAdaml
4.12+t.06
56.444..2
4.43+F.03
50.86+2.11
6.01+F31
28.11+3.65
Extra Adam
4.07=.05
56.67
4.67
47.24
6.58
21.40
FBF Adam
4.54:.04
45.85=.35
4.681.16
46.60=.76
6.57
21.22++1.29
Opt. Adam
4.35#:06
50.41
4.634..13
47.98
6.422..10
23.01
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 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: AltAdaml.
Our hyperparameter search was limited to the step sizes when using the WGAN-LI and WGAN-GP formulation, while all other parameters were kept the same as Gidel et al. (011) Bot et al. (2020). It seems noteworthy that in the case of coft-thresholdigg bigger step sizes performed better with the only exception of AltAdaml.
Irgopton Soore
Incoppon Suore
Abkarr FGl Adan
Abkaert
FSF Aaan
Optnmtnc
19425
30-55
56.25
Figure 2: Left: Average and best/worst IS on the WGAN objective with weight clipping. Right: Average and best/worst IS on the WGAN-LI objective using the proximal operator; The WGAN- L1 objective improves the in comparison to weight clipping and stabilizes the behavior of all considered methods during the training procedure.
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 (208)). All results are averaged over 5 runs for each method.
Adurs
Adar
FSF Ade'
Opter Admn
Figure 3: Average and best/worst results regarding IS (left) and FID (right) using ResNet architecture on the WGAN-GP objective including spectral normalization. Middle: Samples from the generator trained with FBF Adam.
In Table the best IS and FID for each method are reported. FBF Adam performs at least as good as all considered competitors with respect both evaluation metrics. One also that WGAN-L1
8

---

Under review as a conference paper at ICLR 2021
using the proximal operator improves the performance of all considered methods. Figure shows the training progress regarding for each method and both problem formulations. The graphs suggest that making of WGAN-LI objective has stabilizing effect during training, leading smoother and more consistent learning curve a property that only FBF Adam seems to exhibit for weight clipping. Figure as well as T 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 time savings of up 10% as reported in Miyato al. (2018)
CONCLUSION
By highlighting the connection between GAN objectives and monotone inclusions, able to tackle their training via the 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 FBF can lead improved performance and saved computation time (compared to EG).
method which is known to converge to
REFERENCES
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein GAN. arXiv:1701.078755 2017.
Francis Bach. Breaking the curse of dimensionality with convex neural networks. The Journal of Machine Learning Research, 18(1):629-681, 2017.
Shane Barratt and Rishi Sharma. A note on the inception score. arXiv:1801.0197. 2018.
Heinz H Bauschke and Patrick Combettes. Conver Analysis and Monotone Operator Theory in Hilbert Spaces, volume 408. Springer, 2011.
Yoshua Bengio, Nicolas L Roux, Pascal Vincent, Olivier Delalleau, and Patrice Marcotte. Convex neural networks. Advances in Neural Information Processing Systems, pp. 123-130, 2006.
Radu Ioan Bot, Panayotis Mertikopoulos, Mathias Staudigl, and Phan Tu Vuong. Forward-backward- forward methods with variance reduction for stochastic variational inequalities. arXiv preprint
D0Gi:/9902.03355 2019.
Radu Ioan Bot, Michael Sedlmayer, and Phan Tu Vuong. relaxed inertial forward-backward- forward algorithm for solving monotone inclusions with application to GANs. arXh::2003.07886 2020.
Constantinos Daskalakis and Ioannis Panageas. The limit points of (optimistic) gradient descent in min-max optimization. In Advances in Neural Information Processing Systems, pp. 9236-9246,
2018.
Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng. Training GANs with optimism. In International Conference on Leurning Representations, 2018. URL https //openreview www.:eetfffoooo
Gauthier Gidel, Hugo Berard, Gaëtan Vignoud, Pascal Vincent, and Simon Lacoste-Julien. A variational inequality perspective on generative adversarial networks. In International Confer- ence on Learning Representations, 2019. URL https:://penreeeeew.cc www.:/rmmfffoofocoommmmmoo
r #111anAAYm
Ian Goodfellow. Nips 2016 tutorial: Generative adversarial networks. arXiv: 2016.
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farles Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in Neural Information Processing Systems, pp. 2672-2680, 2014.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville. Improved training of Wasserstein GANs. Advances in Neural Information Processing Systems, pp. 5767-5777, 2017. 2017.

---

Under review as a conference paper at ICLR 2021
Erfan Yazdandoost Hamedani and Necdet Serhat Aybat. A primal-dual algorithm for general convex- concave saddle point problems. arXiv:/803.014000 2018.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recognition. In Proceedings of the IEEE conference computer vision and pattern recognition, pp. 770-778, 2016.
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. GANs trained by two time-scale update rule converge local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626-6637, 2017.
Anatoli Juditsky, Arkadi Nemirovski, and Claire Tauvel. Solving variational inequalities with stochastic mirror-prox algorithm. Stochastic Systems, 1(1):17-58, 2011.
Diederik Kingma and Jimmy Ba. Adam: method for stochastic optimization. 11Xi::1412.6980, 2014.
GM Korpelevich. The extragradient method for finding saddle points and other problems. Matecon, 12:747-756, 1976.
Alex Krizhevsky, Geoffrey Hinton, al. Learning multiple layers of features from tiny images. 2009.
Tengyuan Liang and James Stokes. Interaction matters: A note on non- con-asymptotic local convergence of generative adversarial networks. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), The 22nd International Conference on Artificial Intelligence and Statistics, volume 89 of Proceedings of Machine Learning Research, pp. 907-915. PMLR, 2019.
Yura Malitsky. Projected reflected gradient methods for monotone variational inequalities. SIAM Journal on Optimization, 25( (5(11:5500 1:552-5200, 2015.
Yura Malitsky and Matthew K Tam. A forward brraaddbackwardd splitting method for monotone inclusions without cocoercivity. SIAM Journal Optimization, 30(2):1451-1477 2020.
Lars Mescheder, Andreas Geiger, and Sebastian Nowozin. Which training methods for GANs do actually converge? In International Conference on Machine Learning, 2018
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for
generative adversarial networks. In International Conference Learning Representations, 2018.
URL
net f forum? d= d==1QRgz
Aryan Mokhtari, Asuman Ozdaglar, and Sarath Pattathil. Convergence rate of O(1/k) for optimistic gradient and extra extra-gradient methods in smooth convex-concave saddle point problems. arXiv preprint arXiv:1906.01113 2019.
Arkadi Nemirovski. Prox-method with rate of convergence O(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM Journal on Optimization, 15(1):229-2511 2004.
Yurii Nesterov. Dual extrapolation and its applications to solving variational inequalities and related problems. Mathematical Programming, 109(2-3):319-34, 2007.
Daniel Palomar and Yonina Eldar. Convex optimization signal processing and communications. Cambridge university press, 2010.
Konstantin Pieper and Armenak Petrosyan. Nonconvex penalization for sparse neural networks. arXiv:2004. 15515, 2020.
Alec Radford, Luke Metz, and Soumith Chintala. Unsupervised representation learning with deep convolutional generative adversarial networks. arXin:1511.06434 2015.
Alexander Rakhlin and Karthik Sridharan. Online learning with predictable sequences. In Proceedings of the 26th Annual Conference on Learning Theory, pp. 993-1019, 2013a.
Sasha Rakhlin and Karthik Sridharan. Optimization, learning, and games with predictable sequences. In Advances in Neural Information Processing Systems, pp. 3066-3074, 2013b.
10

---

Under review as a conference paper at ICLR 2021
Herbert Robbins and Sutton Monro. A stochastic approximation method. The annals of mathematical statistics, pp. 400-407, 1951.
Saharon Rosset, Grzegorz Swirszez, Nathan Srebro, and Zhu. regularization infinite dimensional feature spaces. In International Conference on Computational Learning Theory, pp. 544-558. Springer, 2007.
Lconid Rudin, Stanley Osher, and Emad Fatemi. Nonlinear total variation based noise removal algorithms. Physica D: nonlinear phenomena, 60(1-4):259-200 1992.
Tim Salimans. Ian Goodfellow, Wojeiech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training GANs. In Advances in Neural Information Processing Systems, pp. 2234-2242, 2016.
Robert Tibshirani. Regression shrinkage and selection via the lasso. Journal of the Royal Statistical Society: Series B (Methodological), (8(1):267-288) 1996.
Paul Tseng. Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM Journal Control and Optimization, 29(1):119-153) 1991.
A DEFINITIONS
In Section 2.4 we require the regularizers be proper, convex and lower semicontinuous which are common properties in convex analysis. We call function r R - R U {+oo} proper if it is not constant +oc, which means that takes finite value for at least single point. In addition, we say that is lower semicontinuous if for all 20 R
lim inf r(2) 2 r(zo). 2->20
is easy to see that C c RT is nonempty, closed and convex, then the indicator d0 of this set, given by
if E
8c(2)
+oo
otherwise
fulfills the assumptions of being proper, convex and lower semicontinuous.
B ABOUT THE GAP FUNCTION
Typically in monotone inclusions, the distance to the set of solutions is used as a measure of quality of 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 [201 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 ( For this reason we use the following (restricted) minimux gap, common for saddle point problems, which for point (u, v) is given by
GB(u,v)
sup (x.g)eB
V (u, y) (z,
(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 E IRm given by
GB(w)= sup (F(z), w 2) + r(w) r(2), =
(16)
where we interpret the possible occurrence of oc 00 as +oo. It stems from the field of Variational Inequalities where such 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 tb : Rd x R + R be continuously differentiable and f Rd + RU (+00).
h: R" + R U } be proper, convex and lower semicontinuous and B C Rd x R". A point (x", yy in the interior of solves the saddle point problem (T) if and only if its minimax gap [5] is zero, Gn(x", ,²")"""==""""" O. For all other elements of B the gap is nonnegative.
11

---

Under review as a conference paper at ICLR 2021
Proof. A saddle point (x", y²) clearly fulfills that (uP(e.))RR'xR (( y) - (x, y²) 0. On the other hand let (z y²) O. For arbitrary point (I, y) we can choose E (0, large enough such that (u, u) = a (x",, vV) + (1--00 (z, y) is in the interior of B. Therefore,
(( v) - (u, y²) (x"", "(x""y"" ay" + (1 - a)v) (ax" + (1 - a) y S 0.
Using the convex-concave structure of up we deduce that
a''''', (1 (x v) a'(('' - (1 az) (x, S 0,
which implies that (a y) s yz) Since (xr, v) was chosen arbitrary (a* ,y" is 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 Incqualities.
Theorem B.2. Let F: Rm R be monotone and continuous, r R R U {+oo} proper.
convex and lower semicontinuous and B C RR... A point w" in the interior of B solves the monotone inclusion
0 F(w) + ar(w)
(17)
if and only if its restricted gap 16 is zero, GB(w") = 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 by making use of the associated Variational inequality (VI)
find such that (F(w), w) + r(w) N 0 V/2
(18)
Lemma B.3. The monotone inclusion 17 is equivalent to the VI 18
Proof.
The equivalence of and 18 follows immediately from the definition of the subdifferential
of
The formulation (18 is typically referred to as the strong form of the VI, whereas
find such that (F(z), 2 w) + r(w)
A2 E R
(19)
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 it is clear that w² is solution to the strong formulation 18 it is also a solution to the weak formulation (9). In fact, if F is continuous the reverse implication
also holds true. To see this, let be a solution the weak (19 and ow" + - a.u for an arbitrary E _d and a E (0, 1), then
(F(aw" (1 a))), (1 - a)(u w²)) + r(ow" + a)))) r(w") 0.
This implies by the convexity of that
(1 (1-a) (FF()""ow"* (1 a)u), (u- w²)) (1 (1-))r(u)-
0.
By dividing by (1 a:) and then taking the limit a - we obtain that w" is 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 clear that Gp(w) 2 for w B as 2 = w can be chosen in the supremum. On the other
hand if wn E B is solution to the weak VI (19 then Gz(w*) 0. This follows from the fact that for a solution of (19 for all E
(F(z), w² - 2) + r(w") - r(2) < 0.
Therefore the supremum over the above expression also less than zero, but clearly zero is obtained for w".
12

---

Under review as a conference paper at ICLR 2021
For the reverse implication to hold true, may not points the boundary of B. Lemma B.6. If a point w² in the interior of B exhibits zero gap Ga(w") = 0, then it is solution the weak VI [19..
Proof. Since w" is in the interior of B we can, for arbitrary R", choose E (0, 1) large enough such that z = ow" + (1 10-a) a)w E B. Using this z in the supremum of the gap we deduce that
r(aw" + - a)w) s (F(aw" +1 - a)w), w" - www - (1 - -a)w) + r(ww)
This implies that
(1 -1-ah a:) (F (ow" + (1 - a)w), w w²) + (1 - a)(((w) r(ww)()))))) 20 0.
By dividing by a:) and then taking the limit a 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
C REFINED THEOREMS
Recall that restricted (unifying) gap function GB defined in 11 is computed with respect set C. R" where := sup,. ||z - w denotes its diameter and it is assumed that 2g E B. Furthermore, the averaged iterates Wk for K are given by
K
ÜK
K K=0
ak
C.I DETERMINISTIC STATEMENTS
The convergence statement of Theorem 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) be the sequence generated by Algorithm 3.1 If
(i) FBF, i.e. QK 24, with step size 0 < as S a S I/L, or (ii) FBFp, i.e. Qx W with step size 0 < 0rk S a 1/2L
is chosen, then for all K 2
D
Gs(ūk) <
2 2 Ofk
C.2 STOCHASTIC STATEMENTS
We actually prove a slightly more general version 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
2 and hold and let (wR)a20 be the sequence generated by FBF,
iee. Algorithm
3.2 with DE 2% and A Mjk Let the step size Ork I < 1. then
D + 4(1 100-02277 a2122) - Σ of
B[GB(0x)]
2 K-1 Ok
for all K > 1.
Theorem 3.2 (i) can be deduced from the above statement by using = 1/vZL which yields that
(1-a21.2) aT 2.
13

---

Under review as a conference paper at ICLR 2021
Theorem C.3. Let Assumption 7 and 3 hold and let (wx)x20 be the sequence generated by FBFp.
i.c. Algorithm 3.2 with Qk Wk-1 and 4 = Ek-1. 1. Let the step size Ok S a 2/21.' then
D2 +
+ 1- 8. L
4,
R==
ak
B[Gb(wx)]
Σk= k=0 0g
K K-1
for all K 1.
Theorem 3.2 (ii) obtained from the above theorem by using the particular step size bound of 1/31, which yields that
2
1 2 = 4.
Although, the step size in the refined statements Theorem and C.3 can be chosen arbitrarily close to 1/z and 1/12V2L) for stochastic FBF and stochastic FBFp, respectively. This does not mean it should be - since the constant the convergence rate deteriorates when the step size is close to its allowed upper bound.
D PROOFS
D.1 PREPARATIONS
We introduce the notation connected to the strong formulation of the VI monotone inclusion ( given by
18) associated to the
g(w,2) == (F(w), w + +(w) r(2), for g : Rm R m IR U (+oo]. Next will establish the fact that this function be used bound the (restricted) unifying gap function, which we remind, defined as
(uP().)) (u, (x, GB(w)= suppEB (F(z), w - 2) + +r(w) - r(z) otherwise,
if
where in the first case (u, v) E Rd R is identified with w R 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 2
K
sup =
Σ ak
arg(uk, 2) an)(w).2)
f2 2 (GB(Tx) GB(wk).
K=
Proof. First we will prove the case is derived from a saddle point problem. Note that from the convex-concave structure of get that
(u, < (u, (u, (V ou, u), y-y-- v)
and
s (u, V v), - u) - ( By summing the two up we obtain
[v, v), x - u V (v v).
( 9) (x.
y-
We can reformulate the above inequality in terms of g to see that for (z, v) E Rd x R (F(w), =) > ② v) ((x,v), v).
The statement of the first case is obtained by adding r(w) r(2) on both sides and using the fact that is convex-concave
If F is general monotone operator, then use its monotonicity to deduce that (F(w), w 2) (F(z), w - 2)- The desired result follows from using the linearity of the inner product.
14

---

Under review as a conference paper at ICLR 2021
Notation.
We denote the enror of the stochastic estimator via Zx = F(0s; Ax) - F((4)) and Wx == Fx)x; F(wx).
(20)
Furthermore, 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)220 Rd be given sequence and (uk)u20 recursively defined all k 2
by Uk41 = Uk Ph for some vo E R.,, then
K
K- Σ k=0
Σ
Pk, Us
u) S 2 11:0 -ul² +
1pp 12
Proof. From the three point identity it follows immediately that
(Pe, 2kk - u) = (e%- Uk+1, Ui- u) =
2 (I10k u/1² 10x+1 u||² + 11u++1 - oxe17)
from which the statement the lemma follows.
D.2 A UNIFIED DECREASE RESULT
We will start with a unifying proposition which covers the common parts of all convergence proofs. Proposition D.3. For ry > 0 we have that for all k 2 0 and E 1
agg(uu, 2) || =||2 _ || =1|2 - -l we 11 + (/ (1)))0021310 wxx1
+ az (Wa, wx) + (1 + (1+ + Izull²).
(21)
Proof. Let h 2 and 2 E R be arbitrary. Using the decomposition 20 it follows that
(at (w.:: Ek), wh 2) a (WK. wk 2) + (F(((u))) Wk 2).
(22)
Since prox (Id + 0r) we deduce that
(2 Wk. Wik 24 F Ax)) (r(w)))))))))))))))))))(())))( - r(2)).
(23)
Adding (2) and 23 gives that
(an (F Ex) F(:; Ax)) + 2ạ Wk: Wi 2) ap (We, wi 2) + aug(wk,)),
which, using the definition of 2x+1, is equivalent to
(2 wkk 2++1 2x) 2 a4 (Wk, w/ 2) + ang( 2).
(24)
We estimate the inner product on the left side of the inequality by inserting and subtracting zμ and using the three point identity twice to deduce
(z Wks Zk+11
2x) (z 2 + 26
Wky Zx+1 - zxk
1
(25)
2 (I|= 2=11 || 2|1² + || w/.12 -| wx wxxl3)
The first two summands are fine they will telescope, are left with estimating || wk 1| By the definition of z we have that
||= - w = a F( 4x) F(wxiEx))*
= (((()( - F(wx) + 2z - W
(26)
S (1+7)ag ( [|
(1 +1 )1 - -
<1++)) 1, wx|l
2(1 + " (11 ||Wr)13),
where we inserted and subtracted F(Q+) and F(w)) and applied Young's inequality to deduce the result. Adding (26). (25) and 24 conclude that
1 7 wxll
(ug 2) || 211²
1 211² |1 wxll 11 +
2/1
+ as (Wk, 2 wk) + (1 7 + 12+1
15

---

Under review as a conference paper at ICLR 2021
D.3 BACKWARD-FORWARK
Proof for deterministic FBF, Theorem C.I (i). We start off by plugging OE - 2k into 21 Since
Wa Zz we use > - to deduce that for all k
1 wwk 2) | =112 - 2 2k =
1
1 1
a 1|
wxll
From this it is clear that the step size is constrained by I I/L as stated in the theorem. By summing up from 0 to K 1 and dividing by Σk-1 ar we obtain
ong(wk 2) S = =
Σ
2 > O4
O
The claimed statement is then derived by taking the supremum in over B and applying Lemma D.1
Proof for stochastic FBF, Theorem C.2
Plugging Ox Zς and Ae 7/k into 21 gives for all
k 2 0
aug(wk: 2) + || - 2||2
2
| - =|12 2/1 (1 (1++1) (1+ wwl1 + an (Wk, un)
+ (Wa, wx) + -1- (1 [
By summing this inequality up and applying Lemma D.2 with to Ug Pk we deduce that
2n. Pk Orp. WR and Uk+1 ==
K
ag Wh, us - 2) =) $ 2 11:0 - 2/12 +
1
Σ
a 1
(27)
2
K=U
k=0
and therefore
K-1
aug(uk 2) S 11:00 - =/12 + a (We, U2 wk) + + -1 11))
we deduce that 1 + + =1/11 - a...2). Next, we take the supremum over z E B and the expectation to obtain
By choosing y such that = (VI+7/
K-1
anglur 2)
}
K-1
E
sup =EB
Σ
< SD2
DD +
D2
4(1 4011-2213)-
Σ
2
kmm0
where we used that
E (W wxYl 18 E (We, - ww) [1imm E/- 11]
Wx Wpp)) Eip-1 || Us w6) 0.
with Eik-1] = (Co. ... 1 and wTps (wo. ........ wR). The final statement follows by dividing by ΣK-1 ag and applying Lemma D.1
L
D.4 BAEEO--AAAAAAARREAAAAAAA
Proof for deterministic FBFp. Theorem C.I (ii). We start off by plugging O+ = zy into 21 Since
We Zz we can use ? + conclude that for all & 2 0
1
1 a 2 Wk-1 w6
aug(w,, 2) + 2 |k+11 21|2 < 12 2112
2 1
we 1|2
+
12
(28)
2
Now we need to bound the term | wx 12 by 1| wx Since
2||= wx|l 12 + 2| wh 11/
w
| Wt 1
(29)
16

---

Under review as a conference paper at ICLR 2021
have for all k 2
1
|| - wxll 2 -1|2s wk- 112-
| - -wul 112
(30)
| 2 0K 1,2
Wk uk- =1lwa-1 -wx 1xxl1
whereas for k- 0, since w-1 = 20. we have that
|| 20 woll ||w-1 2011
(31)
Plugging into 28 for we get that
0ggg Wo: =) + 2
21 =1| + 1 an )110000000 -w-1l1 S 1
1 1=0 =11??
(32)
Plugging 30 into 28
we get that for all
1
ang(wRk (kk, 2)
2 - 2/12
( 1
ai
| - -
2
(33)
1
2|1² + -
1121|
wk-2l'
2
In order to be able to telescope need to ensure that for all l: 2 0
(1 172 oz L.
This is equivalent to the condition 0g S 1/21. which was required in the statement of the theorem. Now we sum up 33 from k to K 1 which yields
(1 ||zx 2112 + 2 a -²x || ux-2l1
aug(uk: 2)
(34)
1
|1 =112+ + 3
L 21100 w-111
2
Adding (34) and
32 and dividing by Σ Ek=o O% to deduce
K
=) < 11:0 - =
ang(un:
Σ
2 2 akk
ak
K=0
where we used that 1- L3 af to get rid of Ilm w- --111 112. The final statement follows by
taking the supremum in over B and applying Lemma D.I
Proof for stochastic FBFp, Theorem that
By using O = wk-1 1 we deduce from (1 for all k
1 Ogg(w,, =) +
1
1 (1 + 7) || =
2 11 - =|1² < 2 =x =||2
2 | w2
2 + 21 10
+ ar (Wk, wx) + 2(1 7 '') 1| + 12)
As in (7) we can split (k: 2- wx) into Wa z vn) + (ar: WR, wk- wxx and use Lemma D.2 to deduce
K
K
amD(W,, 2) < $ =112
wxll2 + - (1 + 7)a - -wwl
2
k=
+ (ox We, Ch wx) + 3(1
) + 1| 12))
Taking now the supremum over 2 E B and then the expectation we conclude that the inequality
}
sup zEB
aug(wn,2)
D
Σ
(1
wall (1 + 7) -wxl 13
(35)
K-1
+ +3(1 + 1
Σ
a
k=
17

---

Under review as a conference paper at ICLR 2021
holds. Let from now on & will treat the case lt 0 separately. Using 29
we deduce that
= wkl 1 2 -1 =| wk- 11 [k-- wx|1"
(36)
1
2 - F(w-=(1111 1: 1x-1) - F( Ek 2) + [u wx
2
Now we bound the difference the two estimators by inserting + F(wx-1) + =F(uk-2) and applying the inequality ||a + b elI2 < 3(1|a|) + ||6| + ||c|3) which yields
[LF((k-1:&A Ek-1) ( = 3|W 11 + 3 Wx + Fll F(wx-11l1
We conclude that
E [1x ER-1) (( - 6o 332 - 2k
(37)
Using
37 in 36 we deduce that
E| 2k wx|l? 2 - -0 1602 +
2 -1l
(38)
whereas for k 0 we have 33p.. Now we plug (38) into (35) conclude that
}
E
sup sEB
aig(
(wxk 2)
k=
K-1
33 - LL21| - 2 g (1+ (1+)))())) | wxll?
$ D
k=1
K-1
+ 2 (11 + 7)) - 1)
woll? + 6(1 + r )
k=0
(39)
From this we conclude that in order to be able to telescope need to enforce
1/ (1 + 7) 2 30 T.2
which is equivalent to
2(4+ L.
Since og S a, we can ensure this by choosing y such that
2(4+7) = 22
(40)
With 40
in place conclude from 39 that the inequality
K-1
E
sup =EB
ond Wk,
k=
1 ((4 7)0 --][w=1-- wpl 6(1 + + 00²
2
0
2
2
Using the fact that 3a < 1 (1 + 2)aA12 from 440 to discard the ||wo
2 term, yields
K-1
}1
K
E
sup B
ang(wn:
< D2 + 6(1
)0
0
2
(41)
A=0
k==0
Through 44)..
we can estimate
1
202
(42)
7
802
Plugging
into
dividing by Ek-1 ag and applying Lemma D.I deduces the final statement.
18

---

Under review as a conference paper at ICLR 2021
E ARCHITECTURE
E.I DCGAN
Table 2: DCGAN architecture used for the CIFARIO experiments.
Generator
Input: E 12 (0, 1) Linear 128 + 512 x x 4
Batch Normalization ReLU
transposed conv. (kernel: Batch Normalization
512 - 256, stride: 2, pad: 1)
ReLU
transposed conv. (kernel: 4 x 4, 256 + 128, stride: 2, pad: 1)
Batch Normalization
ReLU
transposed conv, (kernel: x 4, 128 3, stride: pad:
Tanh(-)
Discriminator
Input: x E 3x3xx32
conv. (kernel: 4 4, - 64, stride: 2, pad: 1)
LeakyReLU (negative slope: 0.2)
conv. (kernel: 4 x 4, 64 - 128, stride: 2, pad: 1)
Batch Normalization
LeakyReLU (negative slope: 0.2)
conv. (kernel: x 4, 128 + 256, stride: 2, pad: 1)
Batch Normalization
LeakyReLU (negative slope: 0.2)
Linear 128
4 x
E.2 RESNET
Table 3: ResNet architecture used for the CIFARIO experiments.
Generator
Input: E 1228
Linear 128 - 128 x 4 4
ResBlock 128 - 128
ResBlock 128 - 128
ResBlock 128 - 128
ReLU
transposed conv. (kernel: 3x3, 128 - stride: 1, pad: 1)
Tanh(-)
Discriminator
Ipput: 3x332233
ResBlock 3 + 128
ResBlock 128 128
ResBlock 128 - 128
ResBlock 128 - 128
Linear 128 + 1
19

---

Under review as a conference paper at ICLR 2021
F HYPERPARAMETERS
For the WGAN formulation with weight clipping, see Table we used the extensively tuned hyperparameters from Gidel et al. (2019) for ExtraAdam, Adaml 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 proposed Barratt Sharma (2018). For FBF-Adam we tuned the step size and kept all other hyperparameters equal.
Table 4: Hyperparameters used for the WGAN formulation (with weight clipping).
(DCGAN) WGAN Hyperparameters
Batch size
= =64
Number of generator updates
500, 000
Adam 3
= =0.5
Adam B2
= =0.9
Weight clipping for the discriminator
= =0.01
Learning rate for discriminator
10
(Extra Adam)
2 X 10 (AltAdaml, FBF Adam, Optim. Adam)
Learning rate for generator
= 5 X 10 10-5 (Extra Adam)
= 2 10 (AltAdaml, FBF Adam, Optim. Adam)
For newly proposed WGAN-LI formulation using 1-Norm regularization, Table we limited the hyperparameter search to the step sizes, with the values Table initial guesses. We chose the value performing the best in terms of IS and FID for sample seed. All other parameters were kept the same as Gidel et al. (2019): Bot et al. 2020).
Table 5: Hyperparameters used for the WGAN-LI formulation (with soft thresholding).
(DCGAN) WGAN-LI Hyperparameters
Batch size
Number of generator updates
500, 000
Adam 31
0.5
Adam 3g
= -0.9
LI regularization for the discriminator
= =1 X 10
Learning rate for discriminator
10 (FBF Adam, Extra Adam)
= 5 10 (Optim. Adam)
= X 10 10 (AltAdaml)
Learning rate for generator
10 (FBF Adam, Extra Adam)
5 10 (Optim. Adam)
= X 10 (AltAdaml)
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 al. (2018) and reduced the number of generator updates by factor of two to ease the computational burden.
20

---

Under review as a conference paper at ICLR 2021
Table 6: Hyperparameters used for the WGAN-GP formulation (with spectral normalization).
(ResNet) WGAN-GP Hyperparameters
Batch size
64
Number of generator updates
250, 000
Adam $1
0.5
Adam B2
0.9
Gradient penalty
= 10
Power iterations for spectral normalization
=
Learning rate for discriminator
=5 X 10 (FBF Adam, Extra Adam, Optim. Adam)
= =2 10 (AltAdaml)
Learning rate for generator
=5 X 10 (FBF Adam, Extra Adam, Optim. Adam)
2 10 (AltAdaml)
21


Reviews:
[{"review_id": "lVwYVd9lbOV", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: This paper introduces the forward-backward-forward splitting for variational inequalities. The main results are an asymptotic convergence results and a non-asymptotic convergence results using a restricted merit function. A new method, FBFp, is introduced and studied. Complete proofs are given. Preliminary numerical results obtained by training GANs are reported. \n\nPros:\n+ complete proofs \n+ A new stochastic operator splitting method based on Tseng's FBF is introduced in which the operator needs to be evaluated once per iteration. This splitting, called FBFp, is indeed new, and has the potentially of being of practical relevance.\n+ Preliminary numerical results on standard GAN architectures. \n\nCons: \n- The paper takes a long time until it becomes clear what actually the monotone inclusion looks like. It seems that the problem of interest is formulation in eq. (9), preceded by a long and unnecessary discussion about existing solvers. It would have been much more accurate to simply start with the problem formulation, then propose your solution method, followed by a critical explanation of the contribution. \n- p.3 claim that FBF has not been rigorously analyzed for saddle point problems. This is of course not true. Even the original paper by Tseng (A MODIFIED FORWARD-BACKWARD SPLITTING METHOD FOR MAXIMAL MONOTONE MAPPINGS, SICON 2000) discusses the application to saddle point problems. See Example 5 in that paper.  \n- The stochastic FBF has been studied in Bot et al. Mini-batch Forward-Backward-Forward Methods for solving Stochastic Variational inequalities, forthcoming in Stochastic Systems. Note that the Arxive version of that paper is available since 2019. Overall, the paper contains only marginal contributions to the state-of-the-art. \n- Only convergence rates for the ergodic average is provided. It is known that the ergodic average might destroy important features of the true solution, such as sparsity. For SFBF we know non-asymptotic convergence rates of the last iterate. This is not mentioned at all. \n- I have some doubts that the restricted merit function is the appropriate one here. Note if the aim is to solve the VI over an unconstrained domain, then FBF coincides with EG, and there is nothing to be analyzed. The interesting case is thus only the constrained case. These constraints are usually encoded in the non-smooth part of of eq. (8), so there is no need to write this explicitly. In my opinion it would therefore be cleaner to assume at the outset that the domain of $F+\\partial r$ is bounded. The gap function used can in fact be traced back to Facchinei & Pang (2003) and is most likely even longer in use than that. \n", "extra_scores": {}, "extra_text": {}}, {"review_id": "XWHQfvu5_6G", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nPros:\n1) To the best of my knowledge, the connection between OGDA and monotone inclusion problems is new.\n2) Convergence results are non asymptotic for the specified gap function.\n\nCons:\n1) The connection of this work with GANs is a bit tenuous because, as the authors also acknowledge, training GANs is a non-convex non-concave min-max problem. The authors should try to express why they believe their  unification result informs practical applications.\n2) This lack of connection is reflected in the experimental section as well. Most experiments re-establish that optimism, extragradient updates or regularization are beneficial for min-max optimization, observations that are already widely known. Again, any experimental insight that is particular to this work, would go a long way towards closing this gap.\n3) It is not clear that the connection of OGDA to FBF and monotone inclusion provides any new insights about the convergence properties of either method.  It would be very helpful, if the authors provided any additional intuition why their result could be used to answer open questions related to OGDA or FBF.  For example, last iterate convergence of OGDA is still an open problem even in convex-concave problems.\n4) While the gap function used allows the authors to provide non asymptotic guarantees, the intuition behind this gap function when its value is non-zero is unclear. Does this gap function have any game theoretic interpretation?\n\nFor now, I am assigning a weak reject score mainly because it is unclear to me if there are significant implications of this unification result either in theory or practice. I am willing to increase my score substantially if the authors provide additional details that address my concerns outlined above.    \n\n---------------------------------\nPost-Rebuttal evaluation.\n\nI would like to thank the authors for their detailed answers, especially regarding the interpretation of the gap function.\nBased on their answers, I decided to increase my score to a 6.", "extra_scores": {}, "extra_text": {}}, {"review_id": "CvBWcXq43u_", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "In this paper,\nthe authors first formulate the optimization problem of GANs as an abstract minimax problem (Equation(1)).\nAs compared to the original optimization objective of Goodfellow's GANs,\nthere is an additional term $h(y)$.\nWhy do you introduce $h(y)$ here? Just for facilitating the adoption of the MONOTONE INCLUSIONS on it?\nThe authors should provide a clear explanation about this point.\n\nLater the author restrict Equation(1) to a deterministic version,\nwhich means that the noise input of GANs will no longer be considered.\nThe noise input is an important ingredient of GANs.\nDespite many new variants of the GANs,\nat least, the noise input is import for the Goodfellow's GANs, which is adopted in this submission as a staring point.\nIt is very hard for me to decide whether this simplification is appropriate.\nExcept Algorithm 3.2 and Theorem 3.2 which suddenly provide stochastic versions,\nall the following results are on this deterministic version.\nIn my opinion, the authors should provide more explanations on this point.\n\nI cannot understand the first sentence of Section 2.2, after read it many times.\nWhat is the exact necessary and sufficient optimality condition for the coupling function being convex-concave and differentiable?\nBefore Equation (2), the authors didn't explain what is monotone and what is monotone inclusion.\nI don't think these concepts are very famous in machine learning community.\n\nIn Section 2.3,\nthe authors provided the introduction of lots of iterative methods.\nIt is difficult for me to distinguish which are completely new findings for solving their inclusion problem and which are the existing results.\nThe authors completed a literature review here.\n\nIn Section 2.4,\nI don't know why the problem (1) can be written as Equation (8).\nCould you provide more explanations about this point?\nLimited space of one submission should be on important points.\n\nIn Section 3,\ncould you explain more about why $G_B(w)$ in Equation (10) is defined as this form?\nJust for facilitating the proof of Theorem 3.1 and Theorem 3.2?\n\nIn Section 3.2,\nthe authors provided a generalized FBF algorithm.\nIsn't this Algorithm 3.1 a combined re-written version of Equation (4) and Equation (5)?\n\nThere is a big gap between Equation (9), Theorem 3.1 and Theorem 3.2 and the experimental results shown in Section 4.\nBesides, there are no open source codes provided.\nIt is very hard for me to figure out the details of the experiments and meantime to check the reproducibility of this paper.\n\nAlthough, the authors stated that \"Due to the theoretical nature of this work, the aim of this section is not to achieve new state-of-the-art\nresults.\"\nI don't think optimization is a theoretical branch of our machine learning community.\nIf a proposed optimization method cannot be proved to be very useful in certain ares or specific tasks,\nit will be very doubting.\nIf we intend to do theoretical contributions,\nwe should try to prove the theoretical properties or convergence bounds for the existing useful optimization methods.\n\nSince ICLR is a highly selective conference,\nthe originality and significance of one submission will always be in the first priority.\nI cannot accept this paper in current state.", "extra_scores": {}, "extra_text": {}}, {"review_id": "9qbmDI2d5L-", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary: 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. \n\nReview: This paper is well-written, though I think the difference with extra-gradient can be made much clearer. For example, the authors could compare FBF with EG for a toy example like Eqn. (13). As far as I can tell, the main difference with extra-gradient is just the regularization term. From this standpoint, the authors should clarify the motivations and importance of adding regularizers. In the current version of the paper, section 2.4 is vague and doesn't explain the role of regularizers well in GAN training.\nBesides, a similar convergence analysis has been done for EG and OGDA (the authors don't even cite properly), so I believe the convergence analysis of this paper is not novel. Given these reasons, I suggest the rejection of this paper and give a score of 4.\n\nComments:\n- It was shown in [1] that the ergodic (averaged) iterates of extra-gradient converge with a rate of O(1/k) which is the same as FBF. Could the authors clarify the novelty/difference of your proof technique for FBF?\n\n- It was shown in [2] that extra-gradient is NOT robust to gradient noise in convex-concave minimax optimization. Could the authors comment on that and explain why FBF could achieve the rate of O(1/sqrt(k)) in the stochastic setting (while EG fails)?\n\n- In GAN training, we typically care more about the last iterate since averaging could actually hurt the performance when the loss surface is highly nonconvex. Is it possible to derive the last iterate convergence rate? \n\n\nI'm willing to increase my rating if the authors could resolve some of my concerns, especially my concern on the novelty of the analysis.\n\n\n-------------\n**I've read the authors' response. I'm still concerned with the novelty of the paper given there are similar results for EG/OGDA. Therefore, I stick to my original rating.**\n\nReferences:\n\n[1] Convergence Rate of O(1/k) for Optimistic Gradient and Extra-gradient Methods in Smooth Convex-Concave Saddle Point Problems, 2019.\n\n[2] Explore Aggressively, Update Conservatively: Stochastic Extragradient Methods with Variable Stepsize Scaling, 2020.\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper provides a unified view of some known methods for monotone operator inclusion problems like Forward-Backward-Forward (FBF) and OGDA, and provides new convergence results for the stochastic version of a variant of FBF called FBFp. All reviewers initially recommended rejection. The rebuttal and the manuscript update addressed several concerns from the reviewers, though the general consensus after rebuttal was still that the paper lacked in significance for the ICLR community. The AC thinks that the paper could make an interesting overview paper in a more optimization / theoretically minded venue.
Decision: Reject