Two steps at a time -- taking GAN training in stride with Tseng's method

Introduction

Generative Adversarial Networks (GANs) 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 . 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) for the training of GANs was suggested in , whereas studied Optimistic Gradient Descent Ascent (OGDA) based on optimistic mirror descent . We however investigate the Forward-Backward-Forward (FBF) method 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.

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 $\mathcal{O}(\nicefrac{{1}}{{k}})$ and $\mathcal{O}(\nicefrac{{1}}{{\sqrt{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.

GAN training as monotone inclusion

The GAN objective was originally cast as a two-player zero-sum game (see ) between the discriminator $D_{y}$ and the generator $G_{x}$ given by

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) 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

Due to the observations made in the previous paragraph we study the following abstract minimax problem

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 illustrative purposes, we will restrict ourselves for now to the special case of the deterministic constrained version of (1), given by

where $f$ and $h$ are given by indicator functions of closed convex sets $X$ and $Y$, respectively. The indicator function $\delta_{C}$ of a set $C$ is defined as $\delta_{C}(z)=0$ for $z\in C$ and $\delta_{C}(z)=+\infty$ otherwise.

2 Minimax problems as monotone inclusions

If the coupling function $\Phi$ is convex-concave and differentiable then the necessary and sufficient optimality condition can be written as a so-called monotone inclusion using

We say $A$ is maximal monotone, if there exists no monotone operator $A^{\prime}$ such that the graph of $A$ is properly contained in the graph of $A^{\prime}$.

Problems of type (5) have been studied thoroughly in convex optimization, with the most established solution methods being Extragradient (aka Korpelevich) and Forward-Backward-Forward (aka Tseng) . Both methods are known to generate sequences of iterates converging to a solution of (5). Note that in the unconstrained setting (i.e. if $\Omega$ is the entire space) both of these algorithms even produce the same iterates.

3 Solving monotone inclusions

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 under the name of Mirror Prox and a convergence rate of $\mathcal{O}(\nicefrac{{1}}{{k}})$ in terms of the function values has been proven. Even a stochastic version of the Mirror Prox algorithm has been studied in with a convergence rate of $\mathcal{O}(\nicefrac{{1}}{{\sqrt{k}}})$. Applied to problem (5), with $P_{\Omega}$ being the projection onto $\Omega$, it iterates

The Forward-Backward-Forward (FBF) method has not been studied rigorously for minimax problems yet, despite promising applications in and its advantage of it only requiring one projection, whereas EG needs two. It is given by

Both, EG and FBF, have the “disadvantage” of needing two gradient evaluations per iteration. A possible remedy — suggested in for EG under the name of extrapolation from the past — is to recycle previous gradients. In a similar fashion we introduce

where we replaced $F(z_{k})$ by $F(w_{k-1})$ twice in (9). As a matter of fact, the above method can be written exclusively in terms of the first variable $w_{k}$ by incrementing the index $k$ in the first update and then substituting in the second line. This results in

This way we rediscover a known method which was studied in for general monotone inclusions under the name of forward-reflected-backward. It reduces to optimistic mirror descent in the unconstrained case with constant step size $\alpha_{k}=\alpha$, giving

which has been proposed for the training of GANs under the name of Optimistic Gradient Descent Ascent (OGDA), see .

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, showed convergence of a method that uses an optimistic step (12) in one component and a regular gradient step in the other, thus requiring less storing of past gradients in comparison to (11).

On the downside, however, by reducing the number of required gradient evaluations per iteration, the largest possible step size is reduced from $\nicefrac{{1}}{{L}}$ (see or Section 3) to $\nicefrac{{1}}{{2L}}$ (see 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.

4 Regularizers

The role of regularizers is well studied in many fields such as statistics , signal processing or inverse problems . 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 .

In the framework of monotone operator theory the optimality condition of the regularized minimax problem (1) can be written as

where $r$ is given by $(x,y)\mapsto f(x)+h(y)$. The possibly set-valued operator $\partial r$ denotes the subdifferential of $r$ and is given by

The monotone inclusion (13) generalizes (5) in a natural way, since $N_{\Omega}=\partial\delta_{\Omega}$. Similarly, the projection constitutes a special case of the so-called proximal mapping which for the function $r$ and $\lambda>0$ is given by

In particular, the proximal mapping of the indicator $\delta_{\Omega}$ yields the projection onto the set $\Omega$, i.e. $\operatorname{prox}_{\lambda\delta_{\Omega}}=P_{\Omega}$.

Main results

Motivated by the considerations above we study the inclusion problem

This minimax gap fulfills the same properties of being nonnegative on $B$ and zero for solutions of (16). In order to capture both at the same time we define the following unifying gap

2 Methods

We now present a novel unifying scheme for solving problem (16), which generalizes FBF (9) and in addition recovers the method motivated in (10) as FBFp. Let us point out again that the latter algorithm was already introduced in and corresponds to OGDA if $F$ stems from the minimax setting (4).

For $\diamondsuit_{k}=z_{k}$ this reduces to the well known FBF method, whereas $\diamondsuit_{k}=w_{k-1}$, with the additional initial condition $w_{-1}=z_{0}$, recycles previous gradients (FBFp).

For $\diamondsuit_{k}=z_{k}$ and $\triangle_{k}=\eta_{k}$ this results in a stochastic version of FBF, whereas $\diamondsuit_{k}=w_{k-1}$ and $\triangle_{k}=\xi_{k-1}$ recycles previous gradients (stochastic FBFp) with the additional initial condition $w_{-1}=z_{0}$ and $\xi_{-1}=\eta_{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. However, we want to point out that the stochastic version of FBFp has not been considered prior to this work.

3 Convergence

Let ${(w_{k})}_{k\geq 0}$ be the sequence generated by Algorithm 3.1. If

FBF, i.e. $\diamondsuit_{k}=z_{k}$, with step size $\alpha_{k}=\alpha\leq\nicefrac{{1}}{{L}}$, or

FBFp, i.e. $\diamondsuit_{k}=w_{k-1}$, with step size $\alpha_{k}=\alpha\leq\nicefrac{{1}}{{2L}}$

is chosen, then for all $K\geq 1$ the averaged iterates $\bar{w}_{K}:=\frac{1}{K}\sum_{k=0}^{K-1}w_{k}\,$ fulfill

where $G_{B}$ is the restricted gap defined in (19).

In order to derive similar convergence statements for the stochastic algorithm we need to assume (standard) properties of the gradient estimator $F(\cdot\,;\xi)$.

In particular we actually only need the above assumption to hold for all iterates $w_{k}$. 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.

The samples $\xi_{k}$ are independent of the iterates $w_{k}$, for all $k\geq 0$.

Equipped with these assumptions we are now able to proof the statement.

Let Assumption 1, 2 and 3 hold and let ${(w_{k})}_{k\geq 0}$ be the sequence generated by Algorithm 3.2. If

stochastic FBF, i.e. $\diamondsuit_{k}=z_{k}$ and $\triangle_{k}=\eta_{k}$, with step size $\alpha_{k}\leq\alpha\leq\nicefrac{{1}}{{\sqrt{2}L}}$, or

stochastic FBFp, i.e. $\diamondsuit_{k}=w_{k-1}$ and $\triangle_{k}=\xi_{k-1}$, with step size $\alpha_{k}\leq\alpha\leq\nicefrac{{1}}{{3L}}$

is chosen, then for all $K\geq 1$ the averaged iterates $\bar{w}_{K}:=\frac{\sum_{k=0}^{K-1}\alpha_{k}w_{k}}{\sum_{k=0}^{K-1}\alpha_{k}}\,$ fulfill

where $G_{B}$ is the restricted gap defined in (19).

The above theorem exhibits a classical step size dependence , yielding convergence for sequences ${(\alpha_{k})}_{k\geq 0}$ that are square summable $\sum_{k=0}^{\infty}\alpha_{k}^{2}<+\infty$ but not summable $\sum_{k=0}^{\infty}\alpha_{k}=+\infty$. Additionally, if in the setting of Theorem 3.2 the step size is chosen $\alpha_{k}=\alpha/\sqrt{k+1}$, a convergence rate can be obtained and is given by

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 $\alpha_{k}=\alpha$ we have

Additionally, if the number of iterations $K$ is fixed beforehand, a conclusion similar to (23) can be obtained by choosing $\alpha=\nicefrac{{1}}{{\sqrt{K}}}$ in (24).

Experiments

Due to the theoretical nature of this work, the aim of this section is rather to validate the results on standard examples and not to strive to achieve new state-of-the-art results. Instead we simply aim to show how the use of methods with convergence guarantees, albeit only in the monotone setting, can yield better training performance.

Following we consider the canonical example $\min_{x}\max_{y}\,xy$, which illustrates the cycling behavior of (even bilinear) minimax problems, and augment this approach by adding a nonsmooth L1-regularizer for one player, resulting in

Figure 1 highlights the aforementioned issue of GDA (and its proximal extension PGDA) cycling around the solution. 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.

2 WGAN trained on CIFAR10

In this section we apply the above proposed techniques from monotone inclusions to the training of Wasserstein GANs making use of the DCGAN architecture . All models are trained on the CIFAR10 dataset 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.

We choose to 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). Although more recent models like ones for example based on ResNet or SAGAN architectures provide better overall performance, they usually do not warrant the use of regularizers. We do this to highlight the difference between FBF and EG, as without projections or proximal steps they are equivalent and their relevance including state-of-the-art architectures has already been shown .

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.

Given the ubiquity and dominance of Adam 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 and 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 formulation, while all other parameters were kept the same as in . 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) and the Fréchet inception distance (FID) , both computed on 50,000 samples. In the case of the IS we use the updated and corrected implementation from . All results are averaged over $5$ runs for each method.

Table 1 reports the best IS and FID for each method. FBF Adam outperforms all considered competitors with respect to both evaluation metrics with the most significant difference for WGAN with weight clipping (“clip”). One can also see that WGAN-L1 using the proximal operator (“prox”) improves the performance of all considered methods, decreasing the absolute and relative differences. Note that the results with WGAN-L1 are comparable for the three methods with underlying convergence guarantees in the convex-concave case. 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.

Conclusion

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. Since FBF provides a natural way to deal with nonsmooth regularizers via the proximal mapping, we modified the WGAN objective to encompass a $1$-norm instead of the usual weight clipping. We showed that this formulation provides a benefit for all considered methods, smoothing the training process and improving Inception Score and Fréchet Inception Distance. Moreover FBF outperformed all competitors including the commonly used Gradient-Descent-Ascent method as well as other more principled schemes such as Extragradient or Optimistic GDA, where the Adam optimizer was used for all. The rigorous theoretical considerations complemented by promising practical results suggest that application of FBF may be fruitful to a wider range of GAN formulations, leading to more reliable training results.

Acknowledgements

This project has received funding from the doctoral programme Vienna Graduate School on Computational Optimization (VGSCO), FWF (Austrian Science Fund), project W 1260, as well as project P 29809-N32.

References

Appendix A Definitions

fulfills the assumptions of being proper, convex and lower semicontinuous.

Appendix B About the gap function

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 [4, Proposition 27.13] and , 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

where we interpret the possible occurrence of $\infty-\infty$ as $+\infty$. It stems from the field of Variational Inequalities where such a function is also known as merit function . The relevance of the above two quantities will be made clear by the following statements.

Using the convex-concave structure of $\Psi$ we deduce that

which implies that $\Psi(x^{*},y)\leq\Psi(x,y^{*})$. Since $(x,y)$ was chosen arbitrary $(x^{*},y^{*})$ is a saddle point. ∎

Similarly, an analogous statement can be shown for (29). The proof, however is split up into multiple lemmas to highlight the connection to Variational Inequalities.

if and only if its restricted gap (29) is zero, $G_{B}(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)

The monotone inclusion (32) is equivalent to the VI (33).

The equivalence of (32) and (33) follows immediately from the definition of the subdifferential of $r$. ∎

The formulation (33) is typically referred to as the strong form of the VI, whereas

Under the given assumptions the notion of weak and strong VI are equivalent.

This implies by the convexity of $r$ that

By dividing by $(1-\alpha)$ and then taking the limit $\alpha\to 1$ we obtain that $w^{*}$ is a solution of the strong form (33). ∎

With the notion of VIs in mind, the above defined gap (29) becomes natural as it measures how much the statement of (34) is violated.

$G_{B}$ is nonnegative on $B$ and zero for solutions of the weak VI.

It is clear that $G_{B}(w)\geq 0$ for $w\in B$ as $z=w$ can be chosen in the supremum. On the other hand if $w^{*}\in B$ is a solution to the weak VI (34) then $G_{B}(w^{*})=0$. This follows from the fact that for a solution of (34) for all $z\in B$

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$.

If a point $w^{*}$ in the interior of $B$ exhibits zero gap $G_{B}(w^{*})=0$, then it is a solution to the weak VI (34).

By dividing by $(1-\alpha)$ and then taking the limit $\alpha\to 1$ we deduce that $w^{*}$ solves the strong form of the VI (33). ∎

Appendix C Refined theorems

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.

Let ${(w_{k})}_{k\geq 0}$ be the sequence generated by Algorithm 3.1. If

FBF, i.e. $\diamondsuit_{k}=z_{k}$, with step size $0<\alpha_{k}\leq\alpha\leq\nicefrac{{1}}{{L}}$, or

FBFp, i.e. $\diamondsuit_{k}=w_{k-1}$, with step size $0<\alpha_{k}\leq\alpha\leq\nicefrac{{1}}{{2L}}$

C.2 Stochastic statements

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.

Let Assumption 1, 2 and 3 hold and let ${(w_{k})}_{k\geq 0}$ be the sequence generated by FBF, i.e. Algorithm 3.2 with $\diamondsuit_{k}=z_{k}$ and $\triangle_{k}=\eta_{k}$. Let the step size $\alpha_{k}\leq\alpha<\frac{1}{L}$, then

Theorem 3.2 (i) can be deduced from the above statement by using $\alpha=\nicefrac{{1}}{{\sqrt{2}L}}$ which yields that ${(1-\alpha^{2}L^{2})}^{-1}=2$.

Let Assumption 1, 2 and 3 hold and let ${(w_{k})}_{k\geq 0}$ be the sequence generated by FBFp, i.e. Algorithm 3.2 with $\diamondsuit_{k}=w_{k-1}$ and $\triangle_{k}=\xi_{k-1}$. Let the step size $\alpha_{k}\leq\alpha<\frac{1}{2\sqrt{2}L}$, then

Theorem 3.2 (ii) is obtained from the above theorem by using the particular step size bound of $\alpha=\nicefrac{{1}}{{3L}}$, which yields that

Although, the step size in the refined statements Theorem C.2 and C.3 can be chosen arbitrarily close to $\nicefrac{{1}}{{L}}$ and $\nicefrac{{1}}{{(2\sqrt{2}L)}}$ 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.

Appendix D Proofs

We introduce the notation connected to the strong formulation of the VI (33) associated to the monotone inclusion (16), given by

First we will prove the case if $F$ is derived from a saddle point problem. Note that from the convex-concave structure of $\Phi$ we get that

The statement of the first case is obtained by adding $r(w)-r(z)$ on both sides and using the fact that $\Psi$ is convex-concave.

If $F$ is a general monotone operator, then we use its monotonicity to deduce that

The desired result follows from using the linearity of the inner product. ∎

We denote the error of the stochastic estimator via

D.2 A unified decrease result

We will start with a unifying proposition which covers the common parts of all convergence proofs.

Since $\textup{prox}_{\alpha_{k}r}={(\textup{Id}+\alpha_{k}\partial r)}^{-1}$ we deduce that

which, using the definition of $z_{k+1}$, is equivalent to

We estimate the inner product on the left side of the inequality by inserting and subtracting $z_{k}$ and using the three point identity twice to deduce

The first two summands are fine as they will telescope, so we are left with estimating $\|z_{k+1}-w_{k}\|^{2}$. By the definition of $z_{k+1}$ we have that

where we inserted and subtracted $F(\diamondsuit_{k})$ and $F(w_{k})$ and applied Young’s inequality to deduce. Adding (60), (59) and (58) we deduce that

Here, $(*)$ holds because of the independence and unbiasedness, see Assumption 3 and 1, respectively. ∎

D.3 Forward-Backward-Forward

We start off by plugging $\diamondsuit_{k}=z_{k}$ into (54). Since $\sigma=0$ we can discard the expectations and use $\gamma\to 0$ to deduce that for all $k\geq 0$

From this it is clear that the step size is constrained by $\alpha\leq\nicefrac{{1}}{{L}}$ as stated in the theorem. By summing up from $k=0$ to $K-1$ and dividing by $\sum_{k=0}^{K-1}\alpha_{k}$ we obtain

The claimed statement is then derived by taking the supremum in $z$ over $B$ and applying Lemma D.1. ∎

Plugging $\diamondsuit_{k}=z_{k}$ and $\triangle_{k}=\eta_{k}$ into (54) gives for all $k\geq 0$

By choosing $\gamma$ such that $\alpha={(\sqrt{1+\gamma}L)}^{-1}$ we deduce that $1+\gamma^{-1}=1/(1-\alpha^{2}L^{2})$. Next, we sum up and divide by $\sum_{k=0}^{K-1}\alpha_{k}$ to obtain

The final statement follows by taking the supremum in $z$ over $B$ and applying Lemma D.1. ∎

D.4 Forward-Backward-Forward-past

We start off by plugging $\diamondsuit_{k}=z_{k}$ into (54). Since $\sigma=0$ we can ignore the expectations and use $\gamma\to 0$ to conclude that for all $k\geq 0$

Now we need to bound the term $\|w_{k-1}-w_{k}\|^{2}$ by $\|z_{k}-w_{k}\|^{2}$. Since

whereas for $k=0$, since $w_{-1}=z_{0}$, we have that

Plugging (72) into (69) for $k=0$ we get that

Plugging (71) into (69) we get that for all $k\geq 1$

In order to be able to telescope we need to ensure that for all $k\geq 0$

This is equivalent to the condition $\alpha_{k}\leq\nicefrac{{1}}{{2L}}$ which was required in the statement of the theorem. Now we sum up (74) from $k=1$ to $K-1$ which yields

Adding (76) and (73) and dividing by $\sum_{k=0}^{K-1}\alpha_{k}$ to deduce

where we used that $1-\alpha_{0}^{2}L^{2}\geq\alpha_{0}^{2}L^{2}$ to get rid of $\|w_{0}-w_{-1}\|^{2}$. The final statement follows by taking the supremum in $z$ over $B$ and applying Lemma D.1. ∎

By using $\diamondsuit_{k}=w_{k-1}$ we deduce from (54) for all $k\geq 0$ that

Let from now on $k\geq 1$ as we will treat the case $k=0$ separately. Using (70) we deduce that

Now we bound the difference of the two estimators by inserting $\pm F(w_{k-1})$, $\pm F(w_{k-2})$ and applying the inequality $\lVert a+b+c\rVert^{2}\leq 3(\lVert a\rVert^{2}+\lVert b\rVert^{2}+\lVert c\rVert^{2})$ which yields

whereas for $k=0$ we have (72). Now we plug (82) into (78) to conclude that

From this we conclude that in order to be able to telescope we need to enforce

Since $\alpha_{k}\leq\alpha$, we can ensure this by choosing $\gamma$ such that

With (86) in place we sum (83) from $k=1$ to $K-1$ to deduce that

Combining (87) and (88) and using the fact that $3\alpha_{0}^{2}L^{2}\leq 1-(1+\gamma)\alpha_{0}^{2}L^{2}$ from (86) to discard the $\|w_{0}-w_{-1}\|^{2}$ term, yields

Plugging (90) into (89), dividing by $\sum_{k=0}^{K-1}\alpha_{k}$ taking the supremum in $z$ over $B$ and applying Lemma D.1, deduces the final statement. ∎

Appendix E Architecture

Appendix F Hyperparameters

For the WGAN formulation with weight clipping, see Table 3, we used the extensively tuned hyperparameters from for ExtraAdam, Adam1 and OptimisticAdam. Note that our values of the Inception Score (IS) differ from the ones reported in as we use the newer implementation of the IS proposed in . 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 4, we limited the hyperparameter search to the step sizes, covering a range the values of Table 3. We choose the value performing the best in terms of IS and FID for a sample seed. All other parameters were kept the same as in .