# A Gauss-Newton Approach for Min-Max Optimization in Generative Adversarial
Networks

Neel Mishra  IIIT Hyderabad
India
<EMAIL_ADDRESS>Bamdev Mishra  Microsoft
India
<EMAIL_ADDRESS>Pratik Jawanpuria  Microsoft
India
<EMAIL_ADDRESS>Pawan Kumar  IIIT Hyderabad
India
<EMAIL_ADDRESS>
###### Abstract

A novel first-order method is proposed for training generative adversarial
networks (GANs). It modifies the Gauss-Newton method to approximate the min-
max Hessian and uses the Sherman-Morrison inversion formula to calculate the
inverse. The method corresponds to a fixed-point method that ensures necessary
contraction. To evaluate its effectiveness, numerical experiments are
conducted on various datasets commonly used in image generation tasks, such as
MNIST, Fashion MNIST, CIFAR10, FFHQ, and LSUN. Our method is capable of
generating high-fidelity images with greater diversity across multiple
datasets. It also achieves the highest inception score for CIFAR10 among all
compared methods, including state-of-the-art second-order methods.
Additionally, its execution time is comparable to that of first-order min-max
methods.

###### Index Terms:

Generative Adversarial Networks, Gauss-Newton, Optimization, Image Generation,
Deep Learning, First Order Optimization, Sherman-Morrison inversion

##  I Introduction

Generative modeling has witnessed significant progress in recent years, with
three primary categories of methods emerging: diffusion models, auto-
regressive models, and generative adversarial networks (GANs). Lately,
diffusion-based generative models have outperformed GANs in terms of image
generation quality [10]. Notably, state-of-the-art diffusion models now
trained on “open world” datasets such as LAION-5B [45] and models such as CLIP
[37] can generate high-quality synthetic images from text prompts. Prominent
recent examples include DALLE-2 by OpenAI [38], the open-source stable
diffusion model [39], and Imagen [40]. A recent auto-regressive model,
Pathways Autoregressive text-to-image (Parti), treats text-to-image generation
as a sequence-to-sequence modeling problem and employs a transformer-based
tokenizer [48].

Despite the growing popularity of diffusion and auto-regressive models, [17]
demonstrated that a GAN-based architecture called GigaGAN can scale to large-
scale text-to-image synthesis tasks while generating state-of-the-art image
quality and being orders of magnitude faster than diffusion models.
Furthermore, it supports latent space editing, including style mixing and
latent interpolation. Consequently, GANs continue to be a widely-used
generative modeling architecture due to their faster image generation and
scalability. GigaGAN builds on the generative adversarial network
architectures initially introduced in [12], followed by variants such as
Wasserstein GAN (WGAN) [1] and WGAN-GP [13]. Numerous extensions and
modifications of GAN architectures have been proposed, including conditional
GAN [30] and StyleGAN [19]. Contrary to diffusion models, which are known for
stable training but slow generation times, training GAN-based architectures
involves solving a delicate min-max problem. In this paper, we propose an
effective solver for this minmax problem that leads to improved image
generation quality and considerably faster training time.

###  I-A The min-max problem in GAN

In GANs, we model the following min-max problem

$\displaystyle\min_{x}\max_{y}f(x,y),$ (1)

where $f(x,y)$ is the utility of the min player. Since this is a zero-sum
game, $-f(x,y)$ is the utility of the max player. Both players want to
maximize their utility function. For $f(x,y)$ being the utility of the min
player we will sometimes denote $g(x,y)=-f(x,y)$ as the utility of the max
player. Many works in the literature have tried modeling the utility function
$f$. A solution to the min-max equation (1) is a local Nash equilibrium.
Specifically, a point $(\bar{x},\bar{y})$ is defined to be a local Nash
equilibrium point if there exists an epsilon ball around the point $U,$ such
that for all $(x,y)\in U$, we have

$\displaystyle f(\bar{x},y)\leq f(\bar{x},\bar{y})\leq f(x,\bar{y}).$ (2)

A simple interpretation of the equation (2) is that if $(\bar{x},\bar{y})$ is
a local Nash equilibrium point, then any perturbation in $x$ while keeping the
$y$ fixed will only increase the function value. Similarly, any perturbation
in $y$ while keeping the $x$ fixed can only decrease the function value.

In the recent work [16], the authors point out that the local Nash equilibrium
may not be a good measure of local optimality. They reason that the Nash
equilibrium relates to simultaneous games, whereas, GAN corresponds to a
sequential minimax game. Hence, they suggest using local minimax point as the
local optimal point. In Proposition 6 in [16], they show an example where
local minimax point exists, but there are no local or global Nash equilibrium
points. Nevertheless, numerous solvers were developed in past few years with a
view of considering GAN training as simultaneous minmax problem [29, 43].

###  I-B Related work on min-max solvers for GANs

The gradient descent ascent (GDA) method in which both players update their
utility greedily (by doing descent and ascent “sequentially” using existing
stochastic gradient methods such as SGD, ADAM[21], others[11, 24, 31]) may
lead to a cyclic trajectory around the Nash equilibrium [28] [43]. To counter
this cyclic behavior, the work [8] uses an optimistic variant of GDA in GANs
and shows that this variant does not exhibit cyclic behavior and converges to
the equilibrium. The authors in [9] study the limit points of two first-order
methods GDA and Optimistic Gradient Descent Ascent (OGDA); they show that the
stable critical points of OGDA are a superset of the GDA-stable critical
points, moreover, their update rules are local diffeomorphisms. Implicit
regularization has been explored in machine learning in various flavors [2, 3,
14, 16, 25, 33]. The authors of [43, 42] suggest that their solver,
Competitive Gradient Descent (CGD) [43] incorporates implicit regularization
and provide several empirical justification. The paper [29, 6] uses the fixed
point theory framework to analyze the convergence of common solvers used in
GANs, and it shows that the convergence of these solvers depend on the maximum
eigen-value of Jacobian of the gradient vector field and on the update rule
considered. Moreover, [29] proposes a new solver, namely, Consensus
Optimization (ConOPT) where they incorporate a regularizer which promotes
consensus among both players. The authors of the solver Symplectic Gradient
Adjustment (SGA) [4] build up on ConOPT and suggest that anti-symmetric part
of the Hessian is responsible for perceiving the small tendency of the
gradient to rotate at each point, and to account for it SGA only incorporates
the mixed derivative term. Some other variants include changes in
normalization’s of weights [32, 15] or changes in architectures[20, 18]. Table
I consists of update equations for the first player for various algorithms. We
note that except for GDA, all other methods shown use second-order terms.

TABLE I: Various update rules for min-max optimization problems. Shown are the update rules for the first player of recent methods. Here, $\eta$ is the step size, and $\gamma$ is gradient correction hyper-parameter. Update rule | Name
---|---
$\Delta x$ = $-\nabla_{x}f$ | GDA
$\Delta x$ = $-\nabla_{x}f-\gamma\nabla_{xy}^{2}f\nabla_{y}f$ | SGA [4]
$\Delta x$ = $-\nabla_{x}f-\gamma\nabla_{xy}^{2}f\nabla_{y}f-\gamma\nabla_{xx}^{2}f\nabla_{x}f$ | ConOpt [29]
$\Delta x$ = $-\nabla_{x}f-\eta\nabla_{xy}^{2}f\nabla_{y}f+\eta\nabla_{xx}^{2}f\nabla_{x}f$ | OGDA [7]
$\Delta x$ = $(Id+\eta^{2}\nabla_{xy}^{2}f\nabla_{yx}^{2}f)^{-1}$ $\left(-\nabla_{x}f-\eta\nabla_{xy}^{2}f\nabla_{y}f\right)$ | CGD [43]
$\Delta x$ = $-\nabla_{x}f+\dfrac{1}{\lambda}\left(\nabla_{x}f-\dfrac{(\nabla_{x}f)(\nabla_{x}f)^{T}(\nabla_{x}f)+(\nabla_{x}f)(\nabla_{y}f)^{T}(\nabla_{y}f)}{\lambda+(\nabla_{x}f)^{T}(\nabla_{x}f)+(\nabla_{y}f)^{T}(\nabla_{y}f)}\right)$ | Ours

###  I-C Contributions of the paper:

  * •

We propose a new strategy for training GANs using an adapted Gauss-Newton
method, which estimates the min-max Hessian as a rank-one update. We use the
Sherman-Morrison inversion formula to effectively compute the inverse.

  * •

We present a convergence analysis for our approach, identifying the fixed
point iteration and demonstrating that the necessary condition for convergence
is satisfied near the equilibrium point.

  * •

We assess the performance of our method on a variety of image generation
datasets, such as MNIST, Fashion MNIST, CIFAR10, FFHQ, and LSUN. Our method
achieves the highest inception score on CIFAR10 among all competing methods,
including state-of-the-art second-order approaches, while maintaining
execution times comparable to first-order methods like Adam.

##  II Proposed solver

For specific loss functions, such as the log-likelihood function, the Fisher
information matrix is recognized as a positive semi-definite approximation to
the expected Hessian of this loss function [26]. It has been demonstrated that
the Fisher matrix is equivalent to the Generalized Gauss-Newton (GGN) matrix
[27, 44]. From this perspective, the Gauss-Newton (GN) method can be
considered an alternative to the natural gradient method for GAN loss
functions. Specifically, the GAN minmax objective is derived from the
minimization of KL-divergence. Minimizing KL divergence is well-known to be
equivalent to maximizing the log-likelihood of the parameterized distribution
$p_{\theta}(x)$ with respect to the parameter $\theta$, i.e.,
$\inf_{\theta}D_{KL}(p\,||\,p_{\theta})=\sup_{\theta}E_{x\sim p}[\log
p_{\theta}(x)].$ Consequently, using the Gauss-Newton approach is analogous to
employing the natural gradient for maximizing the log-likelihood function.
Similar to the Fisher matrix, the GN matrix is utilized as the curvature
matrix of choice to obtain a Hessian-Free solver. The Gauss-Newton method [34]
has been extensively explored in optimization literature. For a comprehensive
analysis and discussion on the natural gradient, we refer the reader to [26,
35, 36]. Given the effectiveness of the natural gradient method with the
Fisher matrix and its equivalence to the Gauss-Newton method, we aim to
develop efficient solvers for minmax problems in GANs. To the best of our
knowledge, Gauss-Newton type methods have not been demonstrated to be
effective for training GAN-like architectures. In this section, we adapt the
Gauss-Newton method as a preconditioned solver for minmax problems and show
that it fits within the fixed point framework [29]. As a result, we obtain a
reliable, efficient, and fast first-order solver. We proceed to describe our
method in detail. Consider the general form of the fixed point iterate, where
$v(p)$ is the combined vector of gradients of both players at point
$p=[x,y]^{T}$ (See Equation (7)).

$F(p)=p+hA(p)v(p),$ (3)

where $h$ is the step size. The matrix $A(p)$ corresponding to our method is

$\displaystyle A(p)=B(p)^{-1}-I,$ (4)

where $B(p)$ denotes the Gauss-Newton preconditioning matrix defined as
follows

$\displaystyle B(p)=\lambda I+v(p)v(p)^{T}.$ (5)

With Sherman-Morison formula to compute $B(p)^{-1}.$ We have

$A(p)=\frac{1}{\lambda}\left(I-\frac{\dfrac{v(p)v(p)^{T}}{\lambda}}{1+\dfrac{v(p)^{T}v(p)}{\lambda}}\right)-I.$
(6)

A regularization parameter $\lambda>0$ is added in (5) to keep $B(p)$
invertible. Our analysis in next section suggests to keep $\lambda<1$ for
convergence guarantee. Hence, a recommended choice is $\lambda\in(0,1).$ To
compute the inverse of Gauss-Newton matrix $B(p),$ we use the well-known
Sherman–Morrison inversion formula to compute the inverse cheaply. Some of the
previous second-order methods that used other approximation of Hessian require
solving a large sparse linear system using a Krylov subspace solver [43, 42];
this makes these methods extremely slow. For larger GAN architectures with
large model weights such as GigaGAN [17], we cannot afford to use such costly
second-order methods.

######  Remark 1.

In standard Guass-Newton type updates, usually there is a “$-$” sign in front
of $B(p)$. In contrast, we have “$+$” sign. The implication is visible later
where our proposed fixed point operator (3) is shown to be a contractive
operator.

Algorithm 1 Proposed solver for min-max.

0: $\min_{x}\max_{y}f(x,y)$: zero-sum game objective function with parameters
$x,y$

0: $h$: Step size

0: $\lambda$: Fisher preconditioning parameter

0: Initial parameter vectors $p_{0}=[x_{0},y_{0}]$

0: Initialize time step $t\leftarrow 0$

0: Compute initial gradient $v_{0}$ at $p_{0}$

1: repeat

2: $t\leftarrow t+1$

3: $u_{t}\leftarrow\frac{1}{\sqrt{\lambda}}*v_{t}$

4:
$z\leftarrow\dfrac{1}{\lambda}*\left(v_{t}-\dfrac{u_{t}(u_{t}^{T}v_{t})}{(1+u_{t}^{T}u_{t})}\right)$

5: $\Delta\leftarrow-(v_{t}-z)$

6: Update  $\displaystyle\begin{bmatrix}x_{t}\\\
y_{t}\end{bmatrix}\leftarrow\begin{bmatrix}x_{t-1}\\\
y_{t-1}\end{bmatrix}+h*\Delta$

7: until $p_{t}=[x_{t},y_{t}]^{T}$ converged

### Algorithm

In Algorithm 1, we show the steps corresponding to our method, and in
Algorithm 2, we show our method with momentum. In the algorithms, we implement
the fixed point iteration (3) with the choice of matrix given in (6) above. We
use $v_{t}$ to denote the gradient $v(p_{t})$ computed at point
$p_{t}=[x_{t},y_{t}]^{T}$ at iteration $t.$ We use the notation $u_{t}$ in
Line 3 of Algorithm 1 to denote the gradient $v_{t}$ scaled by
$\sqrt{\lambda}.$ With these notations, our $A(p_{t})$ matrix computed at
$p_{t}$ becomes

$\displaystyle
A(p_{t})=\frac{1}{\lambda}\left(I-\frac{u_{t}u_{t}^{T}}{1+u_{t}^{T}u_{t}}\right)-I.$

Consequently, the matrix $A(p_{t})v_{t}$ now becomes

$\displaystyle
A(p_{t})v_{t}=\frac{1}{\lambda}\left(v_{t}-\frac{u_{t}u_{t}^{T}v_{t}}{1+u_{t}^{T}u_{t}}\right)-v_{t}.$

The computation of $A(p_{t})v_{t}$ is achieved in Steps 4 and 5 of Algorithm
1. Finally, the fixed point iteration:

$p_{t+1}=p_{t}+A(p_{t})v_{t}$

for $p_{t}=[x_{t},y_{t}]^{T}$ is performed in Step 6. Similarly, a momentum
based variant with a heuristic approach is developed in Algorithm 2.

Algorithm 2 Adaptive solver

0: $\min_{x}\max_{y}f(x,y)$: zero-sum game objective function with parameters
$x,y$

0: $h$: Step size

0: $\beta_{2}$: Exponential decay rates for the second moment estimates

0: $\lambda$: Fisher preconditioning parameter

0: Initial parameter vectors $p_{0}=[x_{0},y_{0}]$

0: Compute initial gradient $v_{0}$ at $p_{0}$

0: Compute $\theta_{0}=v_{0}^{2}$

0: Initialize time-step: $t\leftarrow 0$

1: repeat

2: $t\leftarrow t+1$

3: $\theta_{t}\leftarrow\beta_{2}\cdot\theta_{t-1}+(1-\beta_{2})\cdot
v_{t-1}^{2}$

4: $g_{t}\leftarrow v_{t}/(\sqrt{\theta_{t}}+\epsilon)$

5: $u_{t}\leftarrow\sqrt{\dfrac{h}{\lambda}}*g_{t}$

6:
$z\leftarrow\dfrac{1}{\lambda}*\left(v_{t}-\dfrac{u_{t}(u_{t}^{T}v_{t})}{(1+u_{t}^{T}u_{t})}\right)$

7: $\Delta\leftarrow-(g_{t}-z)$

8: Update  $\displaystyle\begin{bmatrix}x_{t}\\\
y_{t}\end{bmatrix}\leftarrow\begin{bmatrix}x_{t-1}\\\
y_{t-1}\end{bmatrix}+h*\Delta$

9: until $p_{t}=[x_{t},y_{t}]^{T}$ converged

##  III Fixed point iteration and convergence

We wish to find a Nash equilibrium of a zero sum two player game associated
with training GAN. As in [29], we define the Nash equilibrium denoted as a
point $\bar{p}=[\bar{x},\bar{y}]^{T}$ if the condition mentioned in Equation
(2) holds in some local neighborhood of $(\bar{x},\bar{y}).$ For a
differentiable two-player game, the associated vector field is given by

$\displaystyle v(x,y)=\begin{bmatrix}\nabla_{x}f(x,y)\\\
-\nabla_{y}f(x,y)\end{bmatrix},$ (7)

The derivative of the vector field is

$v^{\prime}(x,y)=\begin{bmatrix}\nabla_{xx}^{2}f(x,y)&\nabla_{xy}^{2}f(x,y)\\\
-\nabla_{yx}^{2}f(x,y)&-\nabla_{yy}^{2}f(x,y)\end{bmatrix}.$

The general update rule in the framework of fixed-point iteration is described
in [29, Equation (16)]. Our method uses the fixed point iteration shown in
(3). Recall that $p=(x,y).$ For the minmax problem (1), with minmax gradient
$v(p)$ defined in (7), the fixed point iterative method in (3) well defined.

######  Remark 2.

We remark here that in the following a given matrix (possibly unsymmetric) is
called negative (semi) definite if the real part of the eigenvalues is
negative (or nonpositive), see [29].

######  Lemma 1.

For zero-sum games, $v^{\prime}(p)$ is negative semi-definite if and only if
$\nabla_{xx}^{2}f(x,y)$ is negative semi-definite and $\nabla_{yy}^{2}f(x,y)$
is positive semi-definite.

###### Proof.

See [29, Lemma 1 of Supplementary]. $\blacksquare$ ∎

######  Corollary 1.

For zero-sum games, $v^{\prime}(\bar{p})$ is negative semi-definite for any
local Nash equilibrium $\bar{p}.$ Conversely, if $\bar{p}$ is a stationary
point of $v(p)$ and $v^{\prime}(\bar{p})$ is negative-definite, then $\bar{p}$
is a local Nash equilibrium.

###### Proof.

See [29, Corollary 2 in Appendix]. $\blacksquare$ ∎

######  Proposition 1.

Let $F:\Omega\rightarrow\Omega$ be a continuously differentiable function on
an open subset $\Omega$ of $\mathbb{R}^{n}$ and let $\bar{p}\in\Omega$ be so
that

  1. 1.

$F(\bar{p})=\bar{p}$, and

  2. 2.

the absolute values of the eigenvalues of the Jacobian $F^{\prime}(\bar{p})$
are all smaller than 1 .

Then, there is an open neighborhood $U$ of $\bar{p}$ so that for all $p_{0}\in
U$, the iterates $F^{(k)}\left(p_{0}\right)$ converge to $\bar{p}$. The rate
of convergence is at least linear. More precisely, the error
$\left|F^{(k)}\left(p_{0}\right)-\bar{p}\right|$ is in
$\mathcal{O}\left(\left|\lambda_{\max}\right|^{k}\right)$ for
$k\rightarrow\infty,$ where $\lambda_{\max}$ is the eigenvalue of
$F^{\prime}(\bar{p})$ with the largest absolute value.

###### Proof.

See [5, Proposition 4.4.1]. $\blacksquare$ ∎

The Jacobian of the fixed point iteration 3 is given as follows

$\displaystyle F^{\prime}(p)=I+hA(p)v^{\prime}(p)+hA^{\prime}(p)v(p)$ (8)

At stationary point $p=\bar{p},$ $v(\bar{p})=0,$ hence from (4), we have
$A(\bar{p})=(1/\lambda-1)I,$ hence, at equilibrium, the Jacobian of the fixed
point iteration (8) reduces to

$\displaystyle F^{\prime}(\bar{p})=I+hA(\bar{p})v^{\prime}(\bar{p})=I+\sigma
v^{\prime}(\bar{p}),$ (9)

where

$\displaystyle\sigma=h(1/\lambda-1).$ (10)

######  Lemma 2.

If $\bar{p}$ is a stationary point of $v(\bar{p})$ and $A(\bar{p})$ is defined
as in equation 6, then $A(\bar{p})v^{\prime}(\bar{p})$ is negative definite
for some $\lambda<1$.

###### Proof.

$\displaystyle A(\bar{p})v^{\prime}(\bar{p})$
$\displaystyle=\left(\dfrac{1}{\lambda}\left(\dfrac{I-\dfrac{v(\bar{p})v(\bar{p})^{T}}{\lambda}}{1+\dfrac{v(\bar{p})^{T}v(\bar{p})}{\lambda}}\right)-I\right)v^{\prime}(\bar{p}).$

At the fixed point, we have $v(\bar{p})=0,$ hence, from above

$\displaystyle A(\bar{p})v^{\prime}(\bar{p})$
$\displaystyle=\left(\frac{1}{\lambda}\left(I\right)-I\right)v^{\prime}(\bar{p}).$

From Corollary 1, $v^{\prime}(\bar{p})$ is negative definite at the local Nash
equilibrium $\bar{p}$, hence, for $\lambda<1$ the proof is complete.
$\blacksquare$ ∎

At the stationary point, we do have $F(\bar{p})=\bar{p},$ which satisfies the
first item of Proposition 1. In the Corollary below, we show that for $\sigma$
in (9) small enough, we satisfy the Item 2 of Proposition 1. To this end, we
use the following Lemma.

######  Lemma 3.

Let $U\in\mathbb{R}^{n\times n}$ only has all eigenvalues with negative real
part, and let $h>0$ (in Equation (10)), then the eigenvalues of the matrix
$I+\sigma U$ lie in the unit ball if and only if

$\displaystyle\sigma<\dfrac{1}{|R(\xi)|}\dfrac{2}{1+\left(\dfrac{I(\xi)}{R(\xi)}\right)^{2}}$
(11)

for all eigenvalues $\xi$ of $U.$ Here, $I(\xi)$ and $R(\xi)$ denote the real
and imaginary eigenvalues of the matrix $U.$

###### Proof.

The proof can be found in [29, Lemma 4 in Supplementary]. $\blacksquare$ ∎

######  Corollary 2.

Let $\bar{p}$ be a stationary point. If $v^{\prime}(\bar{p})$ has only
eigenvalues with negative real part, then the iterative method with the fixed
point iteration (3), with (4) and (5) is locally convergent to $\bar{p}$ for
$\sigma$ defined in (9).

###### Proof.

As mentioned above, $F(\bar{p})=\bar{p}$ at stationary point $\bar{p}$ thereby
satisfying item 1 of Proposition 1. We use Lemma 3 with $\sigma$ same as in
(9) and $U=v^{\prime}(\bar{p}).$ From corollary 1, we have that $U$ has all
eigenvalues with negative real part. Moreover, we can change $h$, and
$\lambda$ such that $\sigma$ satisfies the upper bound (11), and we will have
the eigenvalues of $F^{\prime}(\bar{p})=I+\sigma U=I+\sigma
v^{\prime}(\bar{p})$ lie in a unit ball, hence, we also satisfy item 2 of
Proposition 1. Thereby, we have local convergence due to Proposition 1.
$\blacksquare$ ∎

TABLE II: Generator architecture for MNIST and FashionMNIST experiments. Here Conv1, Conv2, and Conv3 are convolution layers with batch normalization and ReLU activation, Conv4 is a convolution layer with Tanh activation. Module | Kernel | Stride | Pad | Shape
---|---|---|---|---
Input | N/A | N/A | N/A | $z\in\mathbb{R}^{100}\sim\mathcal{N}(0,I)$
Conv1 | $4\times 4$ | 1 | 0 | $100\rightarrow 1024$
Conv2 | $4\times 4$ | 2 | 1 | $1024\rightarrow 512$
Conv3 | $4\times 4$ | 2 | 1 | $512\rightarrow 256$
Conv4 | $4\times 4$ | 2 | 1 | $256\rightarrow 3$
TABLE III: Discriminator architecture for MNIST and FashionMNIST experiments. Here Conv1 is a convolution layer with LeakyReLU activation, Conv2, and Conv3 are convolution layers with batch normalization and ReLU activation, Conv4 is a convolution layer with sigmoid activation. Module | Kernel | Stride | Pad | Shape
---|---|---|---|---
Input | N/A | N/A | N/A | $z\in\mathbb{R}^{100}\sim\mathcal{N}(0,I)$
Input | N/A | N/A | N/A | $x\in\mathbb{R}^{3{\times}32{\times}32}$
Conv1 | $4\times 4$ | 2 | 1 | $3\rightarrow 256$
Conv2 | $4\times 4$ | 2 | 1 | $256\rightarrow 512$
Conv3 | $4\times 4$ | 2 | 1 | $512\rightarrow 1024$
Conv4 | $4\times 4$ | 1 | 0 | $1024\rightarrow 1$

##  IV Numerical results

###  IV-A Experimental setup

(a) CIFAR10: Inception score over an extended training run.

(b) CIFAR10: Time comparison.

(c) CIFAR10: Variance in inception scores for multiple runs.

Figure 1: Results for CIFAR10.

In the following, we refer to Algorithm 2 as “ours”. We compare our proposed
method with ACGD [43] (a practical implementation of CGD), ConOpt [29], and
Adam (GDA with gradient penalty and Adam optimizer). ACGD and ConOpt are
second-order optimizers, whereas Adam is a first-order optimizer. We do not
compare with other methods including SGA [4] and OGDA [7] as ACGD [43] has
already been shown to be better than those.

All experiments were carried out on an Intel Xeon E5-2640 v4 processor with 40
virtual cores, 128GB of RAM, and an NVIDIA GeForce GTX 1080 Ti GPU equipped
with 14336 CUDA cores and 44 GB of GDDR5X VRAM. The implementations were done
using Python 3.9.1 and PyTorch (torch-1.7.1). Model evaluations were performed
using the Inception score, computed with the inception_v3 module from
torchvision-0.8.2. The WGAN loss with gradient penalty was employed. We tuned
the methods on a variety of hyperparameters to ensure optimal results,
following the recommendations provided in the official GitHub repositories or
papers. For ACGD, we used the code provided in the official GitHub repository
as a solver (https://github.com/devzhk/cgds-package), and followed their
default recommendation for the $maxiter$ parameter. The step size $h$ was
tested across multiple values
$({10}^{-1},{10}^{-2},{10}^{-3},{10}^{-4},{10}^{-5},8\times{10}^{-5},2\times{10}^{-4})$,
and the gradient penalty constant $\lambda_{\text{gp}}$ was varied as
$(10,1,{10}^{-1},0)$. The best result for ACGD in our experimental setup was
obtained with $h={10}^{-4}$ and $\lambda_{\text{gp}}=1$. In the case of
ConOpt, we tried the step size $h$ across
${10}^{-1},{10}^{-2},{10}^{-3},{10}^{-4},{10}^{-5},2\times{10}^{-5},8\times{10}^{-6}$,
varied $\lambda_{\text{gp}}$ as $(10,1,{10}^{-1},0)$, and adjusted the ConOpt
parameter $\gamma$ across $10,1,{10}^{-1}$. ConOpt performed best in our setup
with $h={10}^{-5}$, $\lambda_{\text{gp}}=1$, and $\gamma=e^{-1}$. For Adam, we
tested the same step sizes as with ConOpt and used the default parameter
values recommended by PyTorch. Adam’s best performance was achieved with a
step size of $lr={10}^{-5}$. Our proposed method performed best with
regularization parameter $\lambda={10}^{-1}$, step size $h={10}^{-5}$, and
gradient penalty constant for WGAN $\lambda_{\text{gp}}=10$.

TABLE IV: Generator architecture for CIFAR10 experiments. Here Conv1, Conv2, and Conv3 is a convolution layer with batch normalization and ReLU activation, Conv4 is a convolution layer with Tanh activation. Module | Kernel | Stride | Pad | Shape
---|---|---|---|---
Input | N/A | N/A | N/A | $z\in\mathbb{R}^{100}\sim\mathcal{N}(0,I)$
Conv1 | $4\times 4$ | 1 | 0 | $100\rightarrow 1024$
Conv2 | $4\times 4$ | 2 | 1 | $1024\rightarrow 512$
Conv3 | $4\times 4$ | 2 | 1 | $512\rightarrow 256$
Conv4 | $4\times 4$ | 2 | 1 | $256\rightarrow 3$
TABLE V: Discriminator architecture for CIFAR10 experiments. Here Conv1 is a convolution layer with LeakyReLU activation, Conv2 and Conv3 is a convolution layer with batch normalization, and LeakyReLU activation, Conv4 is a convolution layer with sigmoid activation. Module | Kernel | Stride | Pad | Shape
---|---|---|---|---
Input | N/A | N/A | N/A | $z\in\mathbb{R}^{100}\sim\mathcal{N}(0,I)$
Input | N/A | N/A | N/A | $x\in\mathbb{R}^{3{\times}32{\times}32}$
Conv1 | $4\times 4$ | 2 | 1 | $3\rightarrow 256$
Conv2 | $4\times 4$ | 2 | 1 | $256\rightarrow 512$
Conv3 | $4\times 4$ | 2 | 1 | $512\rightarrow 1024$
Conv4 | $4\times 4$ | 1 | 0 | $1024\rightarrow 1$

###  IV-B Image generation on grey scale images

(a) CIFAR10: Inception score.

(b) CIFAR10: Time comparison.

(c) CIFAR10: Variance in inception scores for multiple runs.

Figure 2: Results for CIFAR10.

We investigate grayscale image generation using public datasets MNIST [23] and
FashionMNIST [46], with the discriminator and generator architectures shown in
Tables II and III, respectively. In Figure 3, we present the MNIST dataset
comparison. A careful inspection of the generated images reveals that the
first-order optimizer Adam can produce high-fidelity images closely resembling
the original dataset shown in Figure 3(a). However, Adam has a drawback: it
tends to generate images with characters of the same mode/class, such as 0 and
2, which might indicate mode-collapse. Additionally, Adam maintains a uniform
style across all images in Figure 3c. We highlighted the similar samples with
white boxes to illustrate mode-collapse for Adam. The second-order optimizer
ACGD offers an alternative solution to this issue, as shown in Figure 3(d).
Although the images contain some minor artifacts, they display high quality.
ACGD mitigates the consistent character style observed in first-order
optimizers. This enables increased diversity in generated images while
preserving visual fidelity to the original dataset. Our proposed method
balances the advantages of both Adam and ACGD. By utilizing this approach, we
can generate characters in 3(b) that closely mimic the original dataset and
remain computationally efficient, similar to Adam, a first-order optimizer.
Although some minor artifacts may be present in the generated images, our
method overall provides a promising solution achieving high-quality and
diverse results. As depicted in Figure 4, the generation of FashionMNIST
images displays a trend similar to that observed in MNIST. For grey-scale
images, ConOpt’s performance is found to be suboptimal. We note that the
ConOpt paper [29] did not present results for grey-scale images; thus, we
acknowledge that we may not know the appropriate hyperparameters for these
datasets.

(a) Real

(b) Ours

(c) Adam

(d) ACGD

(e) ConOpt

Figure 3: Images generated for MNIST. Samples inside white box show mode-
collapse.

(a) Real

(b) Ours

(c) Adam

(d) ACGD

(e) ConOpt

Figure 4: Images generated for Fashion MNIST. Samples inside white box show
mode-collapse.

###  IV-C Image generation on color images

For color image datasets, we examine the well-known and widely-used datasets
CIFAR10 [22], FFHQ [19], and LSUN bridges, tower, and classroom datasets [47].
A comparison for the CIFAR10 dataset [22] is displayed in Figure 2. Our method
generates images of comparable quality to those produced by ACGD. A widely
accepted metric for comparing methods on the CIFAR10 dataset is the inception
score[41], which evaluates the quality and diversity of generated images using
a pre-trained Inception v3 model. We analyze the inception scores of ACGD,
Adam, ConOpt, and our method in Figure 2(a) and Figure 2(c). The former
demonstrates the performance over extended training durations, while the
latter illustrates the performance variations across multiple runs. The
generator and discriminator architectures for CIFAR10 are presented in Tables
IV and V, respectively. Table VI(a) displays the average time taken per epoch,
while Table VI(b) showcases the maximum inception scores across multiple runs.
Our method achieves the highest inception score of 5.82, followed closely by
Adam with a score of 5.76, and then ConOpt and ACGD.

ACGD has a long runtime due to the costs involved in solving linear systems.
However, it may achieve a higher inception score if allowed to run for an
extended period. To investigate this, we conducted experiments for a long
runtime of approximately eight days, as illustrated in Figure 2(a). We used
the same experimental setting as ACGD, including testing different values of
GP and a case where GP was not used. For our architecture, ACGD gave better
results than the results reported on a smaller architecture in ACGD paper; as
shown in [42, Figure 9]. However, we find that Adam demonstrated better
performance than ACGD on this architecture.

Figure 6(a) displays our generated images of FFHQ, created using a training
dataset of FFHQ thumbnails downscaled to 64x64x3 dimensions. Our images
demonstrate a high level of detail and texture in the skin and realistic
facial features. Figure 6(b) shows our results on the LSUN classroom dataset,
where our model successfully learned significant features, capturing the
essence of classroom scenes. In Figure 5, the generated images of LSUN-tower
and LSUN-bridges exhibit recognizable characteristics, such as the distinct
shape of a tower and the features typical of bridges.

(a) LSUN-tower.

(b) LSUN-bridges.

Figure 5: Images generated by our method on LSUN-tower and LSUN-bridges.

(a) FFHQ.

(b) Classroom.

Figure 6: Images generated by our method on FFHQ and LSUN-classroom. TABLE VI:
Timings and inception scores across multiple runs.

Method | Average time per epoch
---|---
ACGD | 35.34
Adam | 0.186
ConOpt | 0.25
Ours | 0.184
(a) Average time in seconds.

Method | Run1 | Run2 | Run3
---|---|---|---
ACGD | 5.55 | 5.52 | 5.60
Adam | 5.38 | 5.65 | 5.58
ConOpt | 5.73 | 5.72 | 5.76
Ours | 5.82 | 5.77 | 5.79
(b) Max inception scores across runs.

###  IV-D Computational complexity and timing comparisons

Assuming $x\in\mathbb{R}^{m},y\in\mathbb{R}^{n},$ then due to the terms
$\nabla_{xy}^{2}$, and $\nabla_{yx}^{2}$ involved in ConOpt, there is
additional computational cost of the order $O(m^{2}n^{2})$, $O(m^{3})$ and
$O(n^{3})$, these costs are associated with constructing these terms and for
matrix-vector operation required. On the other hand, for ACGD, there are
additional cost of order $O(m^{3}n^{3})$ for solving the linear system with
matrix of order $mn\times mn$ if direct method is used, and of order $O(mn)$
if iterative methods such as CG as in [43] is used. For empirically verifying
the time complexity, for CIFAR10 dataset, in Figure 2(b), we observe that ACGD
is the slowest, and ConOpt is also costlier than our method. Our method has
similar complexity to that of Adam the first order methods. To compute the
order of complexity of Algorithm 1, we have $m+n$ cost for scaling, $2(m+n)$
cost for $u(u^{T}g_{t})$ computation, and $m+n$ cost for $u^{T}u$ computation,
then subtraction with $g_{t}$ costs $(m+n)$. The total cost per epoch is
$O(m+n),$ which is same order as any first-order method such as Adam.

Table 2(b) displays a comparison of the time taken per epoch for various
methods, including ACGD. It is noteworthy that ACGD consumes a significantly
greater amount of time compared to other methods. Specifically, ACGD takes 35
seconds per epoch, which is approximately 200 times more than our method that
takes only 0.184 seconds per epoch. Notably, this is almost identical to the
time taken by Adam, which is 0.186 seconds per epoch.

##  V Code Repository

The code for the experiments is available in an anonymous GitHub repository,
accessible at: https://github.com/NeelMishra/Gauss-Newton-Based-Minimax-
Solver.

##  VI Conclusion

We have introduced a novel first-order method for solving the min-max problems
associated with generative adversarial networks (GANs) using a Gauss-Newton
preconditioning technique. Our proposed method achieves the highest inception
score among all state-of-the-art methods compared for CIFAR10, while
maintaining a competitive time per epoch. We evaluate our method on popular
grayscale and color benchmark datasets and demonstrate its superior
performance. Furthermore, we prove that the fixed-point iteration
corresponding to our proposed method is convergent. As a future work, one may
look at more powerful architectures for generators and discriminators that
will likely increase the quality of images generated.

##  VII Acknowledgment

This work was completed and funded at IIIT-Hyderabad, India under a Microsoft
Academic Partnership (MAPG) Grant.

## References

  * [1] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In International conference on machine learning, pages 214–223. PMLR, 2017.
  * [2] S. Arora, N. Cohen, W. Hu, and Y Luo.  Implicit regularization in deep matrix factorization.  arXiv:1905.13655, 2019.
  * [3] N. Azizan, S. Lale, and B. Hassibi.  Stochastic mirror descent on overparameterized nonlinear models: Convergence, implicit regularization, and generalization.  arXiv:1906.03830, 2019.
  * [4] D. Balduzzi, S. Racaniere, J. Martens, J. Foerster, K. Tuyls, , and T. Graepel.  The mechanics of n-player differentiable games.  arXiv:1802.05642, 2018.
  * [5] D.P. Bertsekas.  Nonlinear Programming.  Athena Scientific, 1999.
  * [6] Sachin Kumar Danisetty, Santhosh Reddy Mylaram, and Pawan Kumar.  Adaptive consensus optimization method for gans.  In 2023 International Joint Conference on Neural Networks (IJCNN), pages 1–8, 2023.
  * [7] C. Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training gans with optimism.  ArXiv, abs/1711.00141, 2018.
  * [8] Constantinos Daskalakis, Andrew Ilyas, Vasilis Syrgkanis, and Haoyang Zeng.  Training gans with optimism, 2018.  arXiv: 1711.00141.
  * [9] Constantinos Daskalakis and Ioannis Panageas.  The limit points of (optimistic) gradient descent in min-max optimization.  Advances in neural information processing systems, 31, 2018.
  * [10] Prafulla Dhariwal and Alex Nichol.  Diffusion models beat gans on image synthesis, 2021.  arXiv 2105.05233.
  * [11] John Duchi, Elad Hazan, and Yoram Singer.  Adaptive subgradient methods for online learning and stochastic optimization.  Journal of Machine Learning Research, 12(61):2121–2159, 2011.
  * [12] Ian J. Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial networks, 2014.  arXiv: 1406.2661.
  * [13] Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville.  Improved training of wasserstein gans, 2017.  arXiv: 1704.00028.
  * [14] S. Gunasekar, B. E. Woodworth, S. Bhojanapalli, B. Neyshabur, and N. Srebro.  Implicit regularization in matrix factorization.  NIPS, page 6151–6159, 2017.
  * [15] Andi Han, Bamdev Mishra, Pratik Jawanpuria, Pawan Kumar, and Junbin Gao.  Riemannian hamiltonian methods for min-max optimization on manifolds.  SIAM Journal on Optimization, 33(3):1797–1827, 2023.
  * [16] Chi Jin, P. Netrapalli, and I. M. Jordan.  What is local optimality in nonconvex-nonconcave minimax optimization?  ICML, pages 4880–4889, 2019.
  * [17] Minguk Kang, Jun-Yan Zhu, Richard Zhang, Jaesik Park, Eli Shechtman, Sylvain Paris, and Taesung Park.  Scaling up gans for text-to-image synthesis.  In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2023.
  * [18] Minguk Kang, Jun-Yan Zhu, Richard Zhang, Jaesik Park, Eli Shechtman, Sylvain Paris, and Taesung Park.  Scaling up gans for text-to-image synthesis, 2023.
  * [19] Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In Proceedings of the IEEE/CVF conference on computer vision and pattern recognition, pages 4401–4410, 2019.
  * [20] Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks, 2019.
  * [21] Diederik P. Kingma and Jimmy Ba.  Adam: A method for stochastic optimization, 2017.
  * [22] Alex Krizhevsky.  Cifar-10 (canadian institute for advanced research).  Technical report, University of Toronto, 2009.
  * [23] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  Proceedings of the IEEE, 86(11):2278–2324, 1998.
  * [24] Ilya Loshchilov and Frank Hutter.  Decoupled weight decay regularization, 2019.
  * [25] C. Ma, K. Wang, Y. Chi, and Y Chen.  Implicit regularization in nonconvex statistical estimation: Gradient descent converges linearly for phase retrieval, matrix completion, and blind deconvolution.  arXiv:1711.10467, 2017.
  * [26] James Martens.  New insights and perspectives on the natural gradient method.  The Journal of Machine Learning Research, 21(1):5776–5851, 2020.
  * [27] James Martens and Ilya Sutskever.  Training deep and recurrent networks with hessian-free optimization.  Neural Networks: Tricks of the Trade: Second Edition, pages 479–535, 2012.
  * [28] E. Mazumdar and L. J. Ratliff.  On the convergence of gradient-based learning in continuous games.  arXiv:1804.05464, 2018.
  * [29] Lars Mescheder, Sebastian Nowozin, and Andreas Geiger.  The numerics of GANs.  In Proceedings of the 31st International Conference on Neural Information Processing Systems, NIPS’17, page 1823–1833, Red Hook, NY, USA, 2017. Curran Associates Inc.
  * [30] Mehdi Mirza and Simon Osindero.  Conditional generative adversarial nets.  Technical report, arXiv:1411.1784, 2014.
  * [31] Neel Mishra and Pawan Kumar.  Angle based dynamic learning rate for gradient descent.  In 2023 International Joint Conference on Neural Networks (IJCNN), pages 1–8, 2023.
  * [32] Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida.  Spectral normalization for generative adversarial networks, 2018.
  * [33] Behnam Neyshabur.  Implicit regularization in deep learning, 2017.  arXiv: 1709.01953.
  * [34] Jorge Nocedal and Stephen J Wright.  Numerical optimization.  Springer, 1999.
  * [35] Yann Ollivier, Ludovic Arnold, Anne Auger, and Nikolaus Hansen.  Information-geometric optimization algorithms: A unifying picture via invariance principles.  The Journal of Machine Learning Research, 18(1):564–628, 2017.
  * [36] Razvan Pascanu and Yoshua Bengio.  Revisiting natural gradient for deep networks.  arXiv preprint arXiv:1301.3584, 2013.
  * [37] Alec Radford, Luke Metz, and Soumith Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks, 2016.
  * [38] Aditya Ramesh, Prafulla Dhariwal, Alex Nichol, Casey Chu, and Mark Chen.  Hierarchical text-conditional image generation with clip latents, 2022.  arXiv: 1704.00028.
  * [39] Robin Rombach, Andreas Blattmann, Dominik Lorenz, Patrick Esser, and Björn Ommer.  High-resolution image synthesis with latent diffusion models, 2022.
  * [40] Chitwan Saharia, William Chan, Saurabh Saxena, Lala Li, Jay Whang, Emily Denton, Seyed Kamyar Seyed Ghasemipour, Burcu Karagol Ayan, S. Sara Mahdavi, Rapha Gontijo Lopes, Tim Salimans, Jonathan Ho, David J Fleet, and Mohammad Norouzi.  Photorealistic text-to-image diffusion models with deep language understanding, 2022.  arXiv: 2205.11487.
  * [41] Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen.  Improved techniques for training gans.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, Advances in Neural Information Processing Systems, volume 29. Curran Associates, Inc., 2016.
  * [42] Florian Schaefer, Hongkai Zheng, and Animashree Anandkumar.  Implicit competitive regularization in GANs.  In Hal Daume III and Aarti Singh, editors, Proceedings of the 37th International Conference on Machine Learning, volume 119 of Proceedings of Machine Learning Research, pages 8533–8544. PMLR, 13–18 Jul 2020.
  * [43] Florian Schäfer and Anima Anandkumar.  Competitive gradient descent.  In Proceedings of the 33rd International Conference on Neural Information Processing Systems, Red Hook, NY, USA, 2019. Curran Associates Inc.
  * [44] Nicol N Schraudolph.  Fast curvature matrix-vector products for second-order gradient descent.  Neural computation, 14(7):1723–1738, 2002.
  * [45] Christoph Schuhmann, Romain Beaumont, Richard Vencu, Cade Gordon, Ross Wightman, Mehdi Cherti, Theo Coombes, Aarush Katta, Clayton Mullis, Mitchell Wortsman, Patrick Schramowski, Srivatsa Kundurthy, Katherine Crowson, and Schmidt L.  Laion-5b: An open large-scale dataset for training next generation image-text models.  arXiv preprint arXiv:2109.03889, 2021.
  * [46] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [47] Fisher Yu, Ari Seff, Yinda Zhang, Shuran Song, Thomas Funkhouser, and Jianxiong Xiao.  Lsun: Construction of a large-scale image dataset using deep learning with humans in the loop.  In arXiv preprint arXiv:1506.03365, 2015.
  * [48] Jiahui Yu, Yuanzhong Xu, Jing Yu Koh, Thang Luong, Gunjan Baid, Zirui Wang, Vijay Vasudevan, Alexander Ku, Yinfei Yang, Burcu Karagol Ayan, Ben Hutchinson, Wei Han, Zarana Parekh, Xin Li, Han Zhang, Jason Baldridge, and Yonghui Wu.  Scaling autoregressive models for content-rich text-to-image generation, 2022.  arXiv:2206.10789.