Training Generative Adversarial Networks via stochastic Nash games

I Introduction

Generative adversarial networks (GANs) are an example of unsupervised generative model. The basic idea is that, given some samples drawn from a probability distribution, the neural network takes a training set and learns how to obtain an estimate of such distribution. Most of the literature on GANs focuses on sample generation (especially image generation), but they can also be designed to explicitly estimate a probability distribution .

The learning process of the neural networks in GANs is made via an adversarial process, in which not only the generative model, but also the opponent, are simultaneously trained. Indeed, there are two neural network classes: the generator that creates data according to a given distribution, and the discriminator that tries to recognize if the samples come from the training data or from the generator. As an example, the generator can be considered as a team of counterfeiters, trying to produce fake currency, while the discriminative model, i.e., the police, tries to detect the counterfeit money . To succeed in this game, the former must learn to reproduce money that are indistinguishable from the original currency, while the discriminator must recognize the samples that are drawn from the same distribution as the training data. Through the competition, both teams improve their methods until the counterfeit currency is indistinguishable from the original.

Besides this simplistic interpretation, the subject has been widely studied in the literature, because it has many and various applications. In addition to the classic image generation problem , GANs have been applied in medicine, e.g., to improve the diagnostic performance of the low-dose computed tomography method and recently to detect pneumonia in potential Covid-19 patients . Moreover, they can be used for correcting images taken under adverse weather conditions (as rain) , , editing facial attributes , image inpainting as well as Pacman .

I-B Stochastic Nash equilibrium problems

The reason why these networks are called adversarial is related to the fact that they can be modeled as a game, where each agent payoff depends on the variables of the other agent . However, the players in GANs can be also considered as cooperative players since they share information with each other . Since there are only the generator and the discriminator, the problem is an instance of a two-player game and it can be also casted as a zero-sum game, depending on choice of the cost functions. From a more general point of view, the class of games that suits the GAN problem is that of stochastic Nash equilibrium problems (SNEPs) where each agent tries to minimize its expected value cost function. Given their connection with game theory, GANs have received theoretical attention as well, both on the study of the associated Nash equilibrium problem and on the design of algorithms to improve the learning and training process .

Among the available methods to solve a SNEP, an elegant approach is to recast the problem as a stochastic variational inequality (SVI) . The advantage of this approach is that there are many algorithms available for finding a solution of an SVI, some of them already applied to GANs . For instance, the most used in machine learning is the forward-backward algorithm , also known as gradient descent , which has the disadvantage that, to ensure convergence, the mapping should be cocoercive, i.e., strongly monotone and Lipschitz continuous. Since the GAN mapping is often non-convex , one would prefer an algorithm that is guaranteed to converge for at most monotone mappings. In this case, it is possible to consider the extragradient (EG) algorithm and the forward-backward-forward (FBF) algorithm . The main downside of these two methods is that they require two costly evaluations of the pseudogradient mapping, which is computationally expensive. Due to the large-scale problem size, the ideal algorithm should not be computationally demanding and it should be guaranteed to converge under non-restrictive assumption on the pseudogradient mapping.

I-C Contribution

Motivated by the need for computationally light algorithms converging under weak assumptions, we propose an algorithm that requests only one computation of the pseudogradient mapping at each iteration and we show its convergence under mere monotonicity. Specifically, our contributions are summarized next.

We propose a stochastic relaxed forward-backward (SRFB) algorithm and a variant with averaging (aSRFB) for the training process of GANs. The SRFB involves only one evaluation of the pseudogradient mapping at each iteration, therefore it is computationally cheaper than the EG and FBF algorithms.

We prove its convergence for monotone mappings, which is considered the “weakest possible” assumption on the pseudogradient mapping . Specifically, whenever only a finite number of samples are available, we prove almost sure convergence to a neighborhood of the solution, while if an increasing set of samples is available, then the algorithm reaches an equilibrium almost surely.

We apply our algorithm to the image generation problem and compare it with the extragradient scheme.

Our SRFB algorithm is inspired by and a preliminary heuristic application to GAN was presented in . Therein, we do not prove convergence of the SRFB algorithm nor of its aSRFB variant. Moreover, in , we only run numerical simulations on synthetic toy examples while in this paper we train the two neural networks for the popular image generation problem with real benchmark data.

I-D Related work

Due to the connection between SNEPs and SVIs, many algorithms for variational inequalities have been applied to GANs .

The first one is the forward-backward (FB) algorithm , also known as gradient descent . It is the most used, even if in many cases it has been proven to be non-convergent . From an operator-theoretic perspective, the FB is not convergent because the pseudogradient mapping should be cocoercive and this is almost never the case in GANs. From an algorithmic perspective, the iterates typically cycle in a neighbourhood of a solution without reaching it .

Therefore, research has focused on the forward-backward-forward (FBF) algorithm and on the extragradient (EG) algorithm, that are guaranteed to converge for merely monotone mappings. The FBF algorithm, first presented in and extended to the stochastic case in , involves two evaluations of the pseudogradient mapping. A first attempt to apply the FBF algorithm for GANs is presented, along with a relaxed inertial FBF algorithm, in . The extragradient (EG) method was first proposed in and extended many years later to the stochastic case in and to GANs in . The EG algorithm requires two evaluations of the pseudogradient mapping as well, therefore in , a variation is proposed. This involves an extrapolation from the past, i.e., it uses the evaluation of the mapping at previous time steps. In the authors propose also the FB and the EG algorithms with averaging.

The averaging technique was first proposed for VIs in and studied more recently in . In , the authors examine two different techniques for averaging: the moving average, which computes the time-average of the iterates, and the exponential moving average which computes an exponentially discounted sum. For both the techniques, they show that, despite convergence cannot be proven, the averaging may help stabilizing the iterates, driving them towards a neighborhood of the solution.

While has mostly a heuristic approach, theoretical convergence studies are presented in . Therein, the authors show that local convergence and stability properties of GAN training depends on the eigenvalues of the Jacobian of the associated gradient vector field.

Another theoretical aspect that has not been extensively addressed yet is the inherent relation between GANs and game theory. In , the authors formally introduce Generative Adversarial Network Games, describing (and seeking for) the Nash equilibria of the zero-sum game as saddle points in mixed strategies. The study of saddle-point problems is also studied, in connection with GANs, in . The authors in , instead, prove that Adam , a second order method for GANs, converges to a stationary local Nash equilibrium.

I-E Notation

II Generative Adversarial Networks

The idea behind generative adversarial networks (GANs) is to set up an antagonistic training process between the generator and the discriminator. Typically, the generator and the discriminator are represented by two deep neural networks, and accordingly, they are denoted by two functions, differentiable with respect to their inputs and parameters. The generator creates samples that aim at resembling the distribution of the training data. The generator is therefore trained to fool the discriminator who, in turn, examines the samples to determine whether they are real or fake. This adversarial mechanism can be modeled as a game where the generator and the discriminator represent the players, who want to improve their payoff .

Usually , the payoff of the discriminator is given by the function

Then, we can rewrite it as a minmax problem, i.e.,

In words, (3) means that the generator aims at minimizing the distance between the real value and the fake one, while the discriminator wants to maximize such a distance, i.e., $d$ aims at recognizing the generated data.

When the generator has a different payoff function from the discriminator, e.g., given by

Since the two-player game with cost functions (1) and (4) and the zero-sum game with cost function (1) and relation (2) have the same pseudogradient mapping (defined Section III), it can be proven that the two equilibria are strategically equivalent [14, Th. 10].

III Stochastic Nash equilibrium problems

In this section, let us describe the GAN game as a generic stochastic Nash equilibrium problem (SNEP).

Given the decision variable of the other agent, the aim of each agent $i$ is to choose a strategy $x_{i}$ that solves its local optimization problem, i.e.,

The solution of the coupled optimization problems in (6) that we are seeking is a stochastic Nash equilibrium (SNE) .

A stochastic Nash equilibrium is a collective strategy $\bm{x}^{*}=\operatorname{col}(x_{\text{g}}^{*},x_{\text{d}}^{*})\in\bm{\Omega}$ such that for all $i\in\mathcal{I}$

In other words, a SNE is a pair of strategies where neither the generator, nor the discriminator, can decrease its cost function by unilaterally deviating from its decision.

While existence of a SNE of the game in (6) is guaranteed, under Assumption 1 [42, Section 3.1], uniqueness does not hold in general [42, Section 3.2].

To seek for a Nash equilibrium, we rewrite the problem as a stochastic variational inequality (SVI). Let us first denote the pseudogradient mapping as

We note that the possibility to exchange the expected value and the pseudogradient is ensured by Assumption 1 .

If Assumption 1 holds, then $\bm{x}^{*}\in\bm{\Omega}$ is a Nash equilibrium of the game in (6) if and only if $\bm{x}^{*}$ is a solution of the SVI in (8) [18, Prop. 1.4.2], [42, Lem. 3.3].

IV Stochastic relaxed forward-backward algorithms

In this section, we propose two algorithms for solving the SNEP associated to the GANs process: a stochastic relaxed forward backward (SRFB) algorithm and its variant with averaging (aSRFB). The iterations read as in Algorithm 1 and Algorithm 2, respectively and they represent the steps for each agent $i\in\{\textup{g},\textup{d}\}$.

Algorithm 1 and Algorithm 2 differ, besides the presence of the averaging step, on the choice of the approximation used for the pseudogradient mapping. Moreover, we note that the averaging step in Algorithm 2, namely,

can be implemented in a first-order fashion as

Let us now describe the approximation schemes used in the definitions of the algorithms. In the SVI framework, there are two main possibilities, depending on the samples available.

Using a finite, fixed number of samples is called stochastic approximation (SA) and it is widely used in the literature of SVIs, in conjunction with conditions on the step sizes to control the stochastic error . In fact, unless the step size sequence is diminishing, it is only possible to prove convergence to a neighborhood of a solution. The stochastic approximation of the pseudogradient mapping, given one sample of the random variable reads as

$F^{\textup{SA}}$ uses one or a finite number, called mini-batch, of realizations of the random variable.

When a huge number of samples is available, one can consider using a different approximation scheme, i.e.,

V Convergence analysis

With the aim of proving convergence to a solution (or to a neighborhood of one) of Algorithms 1 and 2, we start this section with some assumptions that are common to both the algorithms.

The following monotonicity assumption on the pseudogradient mapping is standard for SVI problems , also when applied to GANs and it is the weakest possible to hope for global convergence.

Let us now define the filtration $\mathcal{F}=\{\mathcal{F}_{k}\}$, that is, a family of $\sigma$-algebras such that $\mathcal{F}_{0}=\sigma\left(X_{0}\right)$, $\mathcal{F}_{k}=\sigma\left(X_{0},\xi_{1},\xi_{2},\ldots,\xi_{k}\right)$ for all $k\geq 1,$ and $\mathcal{F}_{k}\subseteq\mathcal{F}_{k+1}$ for all $k\geq 0$. For all $k\geq 0,$ let us also define the stochastic error as

where $\hat{F}$ indicates one of the two possible approximation schemes. In words, $\epsilon_{k}$ in (15) is the distance between the approximation and the exact expected value mapping. Then, let us postulate that the stochastic error has zero mean and bounded variance, as usual in SVI .

V-B Convergence of Algorithm 1

We now state the convergence result for Algorithm 1. First, let us postulate some assumptions functional to our analysis. We start with the batch size sequence, which should be increasing to control the stochastic error.

The batch size sequence $(N_{k})_{k\geq 1}$ is such that, for some $b,k_{0},a>0$, $N_{k}\geq b(k+k_{0})^{a+1}.$ $\blacksquare$

Given $F^{\textup{VR}}$ as in (13), it can be proven that, for some $C>0$,

i.e., the error diminishes as the batch size increases. Such result is, therefore, called variance reduction. More details can be found in [23, Lemma 3.12] [31, Lemma 6]. $\blacksquare$

In addition to Assumption 2, we postulate that the pseudogradient mapping is Lipschitz continuous.

Using the variance reduced scheme in (13), we can take a constant step size, as long as it is small enough while the relaxation parameter should not be too small.

We can finally state our first convergence result.

V-C Convergence of Algorithm 2

In this section, we state the convergence result (and the required assumptions) for Algorithm 2.

First, the bound on the relaxation parameter is wider in this case (compared to Assumption 6).

The relaxation parameter in Algorithm 2 is such that $\delta\in$. $\blacksquare$

Next, we postulate an assumption on the SA approximation in (12), reasonable in our game theoretic framework . We also assume an explicit bound on the feasible set.

The local constraint set $\bm{\Omega}$ is such that $\max\limits_{\bm{x},\bm{y}\in\bm{\Omega}}\|\bm{x}-\bm{y}\|^{2}\leq R^{2}$, for some $R\geq 0$. $\blacksquare$

To measure how close a point is to the solution, let us introduce the gap function,

which is equal 0 if and only if $\bm{x}$ is a solution of the (S)VI in (8) [18, Eq. 1.5.2]. Other possible measure functions can be found in .

We are now ready to state our second convergence result.

The average defined in Theorem 2 is not in conflict with the definition in (9) because if we consider a fixed step size, it holds that

VI Numerical simulations

Let us present some numerical experiments to validate the analysis. We show how GANs are trained using our SRFB algorithm and we propose a comparison with one of the most used algorithms for GANs. Specifically, we compare our SRFB algorithm with the extragradient (EG) algorithm (Algorithm 3) . We note that, compared to Algorithm 1, Algorithm 3 involves two projection steps and two evaluations of the pseudogradient mapping. For the simulations we use Adam (Algorithm 4) instead of the stochastic gradient . In Algorithm 5 we propose the Relaxed Adam, i.e., the SRFB algorithm with Adam; the EG algorithm with Adam can be derived similarly [17, Algorithm 4]. All the simulations are performed on Matlab R2020a with 128G RAM and 2 * Intel(R) Xeon(R) Gold 6148 CPU @ 2.40GHz (20 cores each).

We train two DCGAN architectures (presented in Table I) on the CIFAR10 dataset with the GAN objective . We choose the hyperparameters of Adam as $\beta_{1}=0.5$ and $\beta_{2}=0.9$. We compute the inception score to have an objective comparison: the higher the inception score, the better the image generation. In Figure 1, we show how the inception score increases with time; the solid lines represent a tracking average over the previous and following 50 values of the inceptions score, which is averaged over 20 runs. The transparent area indicated the maximum and minimum values obtained in the 20 runs.

We note that the SRFB algorithm is computationally less demanding than the EG algorithm. Specifically, in Figure 1, after 24 hours (86400 seconds), the SRFB has performed approximatively 130000 iterations while the EG 90000. The averaged aSRFB shows worse performances (after approximatively 110000 iterations), but this is to be expected since we have convergence only to a neighborhood of the solution (Theorem 2). In Figure 2, we show the mean to variance ratio (average Inception Score divided by its variance) at each time instant of the three algorithms. As one can see, from Figure 1 and 2 the SRFB algorithm has a similar performance to the EG algorithm but with a smaller variance, hence a higher reproducibility.

VII Conclusion

The stochastic relaxed forward-backward algorithm is a very promising algorithm for training Generative Adversarial Networks. If an increasing number of samples is available and the pseudogradient mapping of the game is monotone, convergence to the exact solution holds. Instead, with only a finite, fixed mini-batch and the same monotonicity assumption, convergence to a neighborhood of the solution can be proven by using an averaging technique. Our numerical experience shows a similar performance compared to the extragradient scheme, widely used in the literature for GANs.

For the future, it would be interesting to extend the convergence result to an exact solution also in the case of a small mini-batch. Since the cost function associated to GAN is often non-convex, it would also worth finding algorithms converging under weaker assumptions than monotonicity.

Appendix A Preliminary results

We here recall some facts about norms, some properties of the projection operator and a preliminary result. Some results find inspiration from where the algorithm is presented in the deterministic case. We start with the norms. We use the cosine rule

Concerning the projection operator, by [47, Proposition 12.26], it satisfies the following inequality: let $C$ be a nonempty closed convex set, then, for all $x,y\in C$

The projection is also firmly non expansive [47, Prop. 4.16], and consequently, quasi firmly non expansive [47, Def. 4.1].

The Robbins-Siegmund Lemma is widely used in literature to prove a.s. convergence of sequences of random variables.

The next lemma collects some properties that follow from the definition of the SRFB algorithm.

Given Algorithm 1, the following statements hold.

$\bm{x}^{k}-\bar{\bm{x}}^{k-1}=\frac{1}{\delta}(\bm{x}^{k}-\bar{\bm{x}}^{k})$

$\bm{x}^{k+1}-\bm{x}^{*}=\frac{1}{1-\delta}(\bar{\bm{x}}^{k+1}-\bm{x}^{*})-\frac{\delta}{1-\delta}(\bar{\bm{x}}^{k}-\bm{x}^{*})$

$\frac{\delta}{(1-\delta)^{2}}\|\bar{\bm{x}}^{k+1}-{\bm{x}}^{k}\|^{2}=\delta\|\bm{x}^{k+1}-{\bm{x}}^{k}\|^{2}$

Appendix B Proof of Theorem 1

Using the property of projection operator (20) we have

Then, by reordering and substituting in (24), we obtain:

Similarly we can bound the term involving the stochastic errors:

By substituting in (26), we conclude that

Now, we consider the residual function of $\bm{x}^{k}$:

where we added and subtracted $\bm{x}^{k+1}=\operatorname{proj}(\bar{\bm{x}}_{k}-\lambda F^{\textup{VR}}(\bm{x}^{k}))$ in the first inequality and used the firmly non expansiveness of the projection and (19). It follows that

Finally, by taking the expected value, grouping and using Remark 2 and Assumptions 3 and 6, we have

Appendix C Proof of Theorem 2

We start by using the fact that the projection is firmly quasinonexpansive.

Now we apply Lemma 2.2 and Lemma 2.3 to $\|\bm{x}^{k+1}-\bm{x}^{*}\|$:

Then, by the definition of $\epsilon^{k}$, reordering leads to

Next, we sum over all the iterations, hence inequality (32) becomes

Using Assumption 2 and resolving the sums, we obtain

Now, we note that $\langle\epsilon^{k},\bm{x}^{k}-\bm{x}^{*}\rangle=\langle\epsilon^{k},\bm{x}^{k}-\bm{u}^{k}\rangle+\langle\epsilon^{k},\bm{u}^{k}-\bm{x}^{*}\rangle.$ We define $\bm{u}^{0}=\bm{x}^{0}$ and $\bm{u}^{k+1}=\operatorname{proj}(\bm{u}^{k}-\lambda_{k}\epsilon^{k})$, thus

Therefore, $2\lambda_{k}\langle\epsilon^{k},\bm{x}^{k}-\bm{x}^{*}\rangle=2\lambda_{k}\langle\epsilon^{k},\bm{x}^{k}-\bm{u}^{k}\rangle+\|\bm{u}^{k}-\bm{x}^{*}\|^{2}+\lambda_{k}\|\epsilon^{k}\|^{2}-\|\bm{u}^{k+1}-\bm{x}^{*}\|^{2}.$ By including this in (34) and by doing the sum, we obtain

By definition, $\|\bm{u}^{0}-\bm{x}^{*}\|^{2}=\|\bm{x}^{0}-\bm{x}^{*}\|^{2}$. Then, tby aking the expected value in (36) and using Assumption 3, we conclude that

Let us define $S=\sum\nolimits_{k=1}^{K}\lambda_{k}$, $\bm{X}^{K}=\frac{\sum\nolimits_{k=1}^{K}\lambda_{k}\bm{x}^{k}}{\sum\nolimits_{k=1}^{K}\lambda_{k}}=\frac{1}{S}\sum\nolimits_{k=1}^{K}\lambda_{k}\bm{x}^{k}$. Then,

Finally, it holds that if $\lambda_{k}$ is constant, $S=K\lambda$ and $\sum\nolimits_{k=1}^{K}\lambda_{k}^{2}=K\lambda^{2}$

References