# Understanding Overparameterization
in Generative Adversarial Networks

Yogesh Balaji1, Mohammadmahdi Sajedi2∗, Neha Mukund Kalibhat1, Mucong Ding1,
Dominik Stöger2, Mahdi Soltanolkotabi2, Soheil Feizi1
1 University of Maryland, College Park, MD
2 University of Southern California, Los Angeles, CA First two authors
contributed equally. Correspondence to<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

A broad class of unsupervised deep learning methods such as Generative
Adversarial Networks (GANs) involve training of overparameterized models where
the number of parameters of the model exceeds a certain threshold. Indeed,
most successful GANs used in practice are trained using overparameterized
generator and discriminator networks, both in terms of depth and width. A
large body of work in supervised learning have shown the importance of model
overparameterization in the convergence of the gradient descent (GD) to
globally optimal solutions. In contrast, the unsupervised setting and GANs in
particular involve non-convex concave mini-max optimization problems that are
often trained using Gradient Descent/Ascent (GDA). The role and benefits of
model overparameterization in the convergence of GDA to a global saddle point
in non-convex concave problems is far less understood. In this work, we
present a comprehensive analysis of the importance of model
overparameterization in GANs both theoretically and empirically. We
theoretically show that in an overparameterized GAN model with a $1$-layer
neural network generator and a linear discriminator, GDA converges to a global
saddle point of the underlying non-convex concave min-max problem. To the best
of our knowledge, this is the first result for global convergence of GDA in
such settings. Our theory is based on a more general result that holds for a
broader class of nonlinear generators and discriminators that obey certain
assumptions (including deeper generators and random feature discriminators).
Our theory utilizes and builds upon a novel connection with the convergence
analysis of linear time-varying dynamical systems which may have broader
implications for understanding the convergence behavior of GDA for non-convex
concave problems involving overparameterized models. We also empirically study
the role of model overparameterization in GANs using several large-scale
experiments on CIFAR-10 and Celeb-A datasets. Our experiments show that
overparameterization improves the quality of generated samples across various
model architectures and datasets. Remarkably, we observe that
overparameterization leads to faster and more stable convergence behavior of
GDA across the board.

##  1 Introduction

In recent years, we have witnessed tremendous progress in deep generative
modeling with some state-of-the-art models capable of generating photo-
realistic images of objects and scenes (Brock et al., 2019; Karras et al.,
2019; Clark et al., 2019). Three prominent classes of deep generative models
include GANs (Goodfellow et al., 2014), VAEs (Kingma & Welling, 2014) and
normalizing flows (Dinh et al., 2017). Of these, GANs remain a popular choice
for data synthesis especially in the image domain. GANs are based on a two
player min-max game between a generator network that generates samples from a
distribution, and a critic (discriminator) network that discriminates real
distribution from the generated one. The networks are optimized using Gradient
Descent/Ascent (GDA) to reach a saddle-point of the min-max optimization
problem.

One of the key factors that has contributed to the successful training of GANs
is model overparameterization, defined based on the model parameters count. By
increasing the complexity of discriminator and generator networks, both in
depth and width, recent papers show that GANs can achieve photo-realistic
image and video synthesis (Brock et al., 2019; Clark et al., 2019; Karras et
al., 2019). While these works empirically demonstrate some benefits of
_overparameterization_ , there is lack of a rigorous study explaining this
phenomena. In this work, we attempt to provide a comprehensive understanding
of the role of _overparameterization_ in GANs, both theoretically and
empirically. We note that while _overparameterization_ is a key factor in
training successful GANs, other factors such as generator and discriminator
architectures, regularization functions and model hyperparameters have to be
taken into account as well to improve the performance of GANs.

Recently, there has been a large body of work in supervised learning (e.g.
regression or classification problems) studying the importance of model
overparameterization in gradient descent (GD)’s convergence to globally
optimal solutions (Soltanolkotabi et al., 2018; Allen-Zhu et al., 2019; Du et
al., 2019; Oymak & Soltanolkotabi, 2019; Zou & Gu, 2019; Oymak et al., 2019).
A key observation in these works is that, under some conditions,
overparameterized models experience lazy training (Chizat et al., 2019) where
optimal model parameters computed by GD remain close to a randomly initialized
model. Thus, using a linear approximation of the model in the parameter space,
one can show the global convergence of GD in such minimization problems.

In contrast, training GANs often involves solving a non-convex concave _min-
max_ optimization problem that fundamentally differs from a single
minimization problem of classification/regression. The key question is whether
overparameterized GANs also experience lazy training in the sense that
overparameterized generator and discriminator networks remain sufficiently
close to their initializations. This may then lead to a general theory of
global convergence of GDA for such overparameterized non-convex concave min-
max problems.

Figure 1: Overparameterization in GANs. We train DCGAN models by varying the
size of the hidden dimension $k$ (larger the $k$, more overparameterized the
models are, see Fig. 8 for details). Overparameterized GANs enjoy improved
training and test FID scores _(the left panel)_ , generate high-quality
samples _(the middle panel)_ and have fast and stable convergence _(the right
panel)_.

In this paper we first theoretically study the role of overparameterization
for a GAN model with a $1$-hidden layer generator and a linear discriminator.
We study two optimization procedures to solve this problem: (i) using a
conventional training procedure in GANs based on GDA in which generator and
discriminator networks perform simultaneous steps of gradient descent to
optimize their respective models, (ii) using GD to optimize generator’s
parameters for the optimal discriminator. The latter case corresponds to
taking a sufficiently large number of gradient ascent steps to update
discriminator’s parameters for each GD step of the generator. In both cases,
our results show that in an overparameterized regime, the GAN optimization
converges to a global solution. To the best of our knowledge, this is the
first result showing the global convergence of GDA in such settings. While in
our results we focus on one-hidden layer generators and linear discriminators,
our theory is based on analyzing a general class of min-max optimization
problems which can be used to study a much broader class of generators and
discriminators potentially including deep generators and deep random feature-
based discriminators. A key component of our analysis is a novel connection to
exponential stability of non-symmetric time varying dynamical systems in
control theory which may have broader implications for theoretical analysis of
GAN’s training. Ideas from control theory have also been used for
understanding and improving training dynamics of GANs in (Xu et al., 2019; An
et al., 2018).

Having analyzed overparameterized GANs for relatively simple models, we next
provide a comprehensive empirical study of this problem for practical GANs
such as DCGAN (Radford et al., 2016) and ResNet GAN (Gulrajani et al., 2017)
trained on CIFAR-10 and Celeb-A datasets. For example, the benefit of
overparamterization in training DCGANs on CIFAR-10 is illustrated in Figure 1.
We have three key observations: (i) as the model becomes more
overparameterized (e.g. using wider networks), the training FID scores that
measure the training error, decrease. This phenomenon has been observed in
other studies as well (Brock et al., 2019). (ii) overparameterization does not
hurt the test FID scores (i.e. the generalization gap remains small). This
improved test-time performance can also be seen qualitatively in the center
panel of Figure 1, where overparameterized models produce samples of improved
quality. (iii) Remarkably, overparameterized GANs, with a lot of parameters to
optimize over, have significantly improved convergence behavior of GDA, both
in terms of rate and stability, compared to small GAN models (see the right
panel of Figure 1).

In summary, in this paper

  * •

We provide the first theoretical guarantee of simultaneous GDA’s global
convergence for an overparameterized GAN with one-hidden neural network
generator and a linear discriminator (Theorem 2.1).

  * •

By establishing connections with linear time-varying dynamical systems, we
provide a theoretical framework to analyze simultaneous GDA’s global
convergence for a general overparameterized GAN (including deeper generators
and random feature discriminators), under some general conditions (Theorems
2.3 and A.4).

  * •

We provide a comprehensive empirical study of the role of model
overparameterization in GANs using several large-scale experiments on CIFAR-10
and Celeb-A datasets. We observe overparameterization improves GANs’ training
error, generalization error, sample qualities as well as the convergence rate
and stability of GDA.

##  2 Theoretical results

###  2.1 Problem formulation

Given $n$ data points of the form
$\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}\in\mathbb{R}^{m}$, the goal of GAN’s
training is to find a generator that can mimic sampling from the same
distribution as the training data. More specifically, the goal is to find a
generator mapping
$\mathcal{G}_{\bm{\theta}}(z):\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$,
parameterized by $\bm{\theta}\in\mathbb{R}^{p}$, so that
$\mathcal{G}_{\bm{\theta}}(\bm{z}_{1}),\mathcal{G}_{\bm{\theta}}(\bm{z}_{2}),\ldots,\mathcal{G}_{\bm{\theta}}(\bm{z}_{n})$
with $\bm{z}_{1},\bm{z}_{2},\ldots,\bm{z}_{n}$ generated i.i.d. according to
$\mathcal{N}(\bm{0},\bm{I}_{d})$ has a similar empirical distribution to
$\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}$111In general, the number of observed
and generated samples can be different. However, in practical GAN
implementations, batch sizes of observed and generated samples are usually the
same. Thus, for simplicity, we make this assumption in our setup. . To measure
the discrepancy between the data points and the GAN outputs, one typically
uses a discriminator mapping
$\mathcal{D}_{\widetilde{\theta}}:\mathbb{R}^{m}\rightarrow\mathbb{R}$
parameterized with $\widetilde{\theta}\in\mathbb{R}^{\widetilde{p}}$. The
overall training approach takes the form of the following min-max optimization
problem which minimizes the worst-case discrepancy detected by the
discriminator

$\displaystyle\min_{\bm{\theta}}\max_{\widetilde{\bm{\theta}}}\quad\frac{1}{n}\sum_{i=1}^{n}\mathcal{D}_{\widetilde{\bm{\theta}}}(\bm{x}_{i})-\frac{1}{n}\sum_{i=1}^{n}\mathcal{D}_{\widetilde{\bm{\theta}}}(\mathcal{G}_{\bm{\theta}}(\bm{z}_{i}))+\mathcal{R}(\widetilde{\bm{\theta}}).$
(1)

Here, $\mathcal{R}(\widetilde{\bm{\theta}})$ is a regularizer that typically
ensures the discriminator is Lipschitz. This formulation mimics the popular
Wasserstein GAN (Arjovsky et al., 2017) (or, IPM GAN) formulations. This
optimization problem is typically solved by running Gradient Descent Ascent
(GDA) on the minimization/maximization variables.

The generator and discriminator mappings $\mathcal{G}$ and $\mathcal{D}$ used
in practice are often deep neural networks. Thus, the min-max optimization
problem above is highly nonlinear and non-convex concave. Saddle point
optimization is a classical and fundamental problem in game theory (Von
Neumann & Morgenstern, 1953) and control (Gutman, 1979). However, most of the
classical results apply to the convex-concave case (Arrow et al., 1958) while
the saddle point optimization of GANs is often non convex-concave. If GDA
converges to the global (local) saddle points, we say it is globally (locally)
stable. For a general min-max optimization, however, GDA can be trapped in a
loop or even diverge. Except in some special cases (e.g. (Feizi et al., 2018)
for a quadratic GAN formulation or (Lei et al., 2019) for the under-
parametrized setup when the generator is a one-layer network), GDA is not
globally stable for GANs in general (Nagarajan & Kolter, 2017; Mescheder et
al., 2018; Adolphs et al., 2019; Mescheder et al., 2017; Daskalakis et al.,
2020).

None of these works, however, study the role of model overparameterization in
the global/local convergence (stability) of GDA. In particular, it has been
empirically observed (as we also demonstrate in this paper) that when the
generator/discriminator contain a large number of parameters (i.e. are
sufficiently overparameterized) GDA does indeed find (near) globally optimal
solutions. In this section we wish to demystify this phenomenon from a
theoretical perspective.

###  2.2 Definition of Model Overparameterization

In this paper, we use _overparameterization_ in the context of model
parameters count. Informally speaking, overparameterized models have large
number of parameters, that is we assume that the number of model parameters is
sufficiently large. In specific problem setups of Section 2, we precisely
compute thresholds where the number of model parameters should exceed in order
to observe nice convergence properties of GDA. Note that the definition of
_overparameterization_ based on model parameters count is related, but
distinct from the complexity of the hypothesis class. For instance, in our
empirical studies, when we say we _overparameterize_ a neural network, we fix
the number of layers in the neural network and increase the hidden dimensions.
Our definition does not include the case where the number of layers also
increases, which forms a different hypothesis class.

###  2.3 Results for one-hidden layer generators and random discriminators

In this section, we discuss our main results on the convergence of gradient
based algorithms when training GANs in the overparameterized regime. We focus
on the case where the generator takes the form of a single hidden-layer ReLU
network with $d$ inputs, $k$ hidden units, and $m$ outputs. Specifically,
$\mathcal{G}\left(\bm{z}\right)=\bm{V}\cdot\text{ReLU}\left(\bm{W}\bm{z}\right)$
with $\bm{W}\in\mathbb{R}^{k\times d}$ and $\bm{V}\in\mathbb{R}^{m\times k}$
denoting the input-to-hidden and hidden-to-output weights. We also consider a
linear discriminator of the form $\mathcal{D}(\bm{x})=\bm{d}^{T}\bm{x}$ with
an $\ell_{2}$ regularizer on the weights i.e.
$\mathcal{R}(\bm{d})=-\left\|\bm{d}\right\|_{\ell_{2}}^{2}/2$. The overall
min-max optimization problem (equation 1) takes the form

$\displaystyle\min_{\bm{W}\in\mathbb{R}^{k\times
d}}\max_{\bm{d}\in\mathbb{R}^{m}}\quad\mathcal{L}(\bm{W},\bm{d}):=\langle\bm{d},\frac{1}{n}\sum_{i=1}^{n}\left(\bm{x}_{i}-\bm{V}\text{ReLU}\left(\bm{W}\bm{z}_{i}\right)\right)\rangle-\frac{\left\|\bm{d}\right\|_{\ell_{2}}^{2}}{2}.$
(2)

Note that we initialize $\bm{V}$ at random and keep it fixed throughout the
training. The common approach to solve the above optimization problem is to
run a Gradient Descent Ascent (GDA) algorithm. At iteration $t$, GDA takes the
form

$\displaystyle\begin{cases}\bm{d}_{t+1}&=\bm{d}_{t}+\mu\nabla_{\bm{d}}\mathcal{L}\left(\bm{W}_{t},\bm{d}_{t}\right)\\\
\bm{W}_{t+1}&=\bm{W}_{t}-\eta\nabla_{\bm{W}}\mathcal{L}\left(\bm{W}_{t},\bm{d}_{t}\right)\end{cases}$
(3)

Next, we establish the global convergence of GDA for an overparameterized
model. Note that a global saddle point $(\bm{W}^{*},\bm{d}^{*})$ is defined as

$\displaystyle\mathcal{L}(\bm{W}^{*},\bm{d})\leq\mathcal{L}(\bm{W}^{*},\bm{d}^{*})\leq\mathcal{L}(\bm{W},\bm{d}^{*})$

for all feasible $\bm{W}$ and $\bm{d}$. If these inequalities hold in a local
neighborhood, ($\bm{W}^{*},\bm{d}^{*})$ is called a local saddle point.

###### Theorem 2.1

Let $\bm{x}_{1},\bm{x}_{2},\ldots,\bm{x}_{n}\in\mathbb{R}^{m}$ be $n$ training
data with their mean defined as
$\bar{\bm{x}}:=\frac{1}{n}\sum_{i=1}^{n}\bm{x}_{i}$. Consider the GAN model
with a linear discriminator of the form $\mathcal{D}(\bm{x})=\bm{d}^{T}\bm{x}$
parameterized by $\bm{d}\in\mathbb{R}^{m}$ and a one hidden layer neural
network generator of the form $\mathcal{G}(\bm{z})=\bm{V}\phi(\bm{W}z)$
parameterized by $\bm{W}\in\mathbb{R}^{k\times d}$ with
$\bm{V}\in\mathbb{R}^{m\times k}$ a fixed matrix generated at random with
i.i.d. $\mathcal{N}(0,\sigma_{v}^{2})$ entries. Also assume the input data to
the generator $\\{\bm{z}_{i}\\}_{i=1}^{n}$ are generated i.i.d. according to
$\sim\mathcal{N}(\bm{0},\sigma_{z}^{2}\bm{I}_{d})$. Furthermore, assume the
generator weights at initialization $\bm{W}_{0}\in\mathbb{R}^{k\times d}$ are
generated i.i.d. according to $\mathcal{N}(0,\sigma_{w}^{2})$. Furthermore,
assume the standard deviations above obey
$\sigma_{v}\sigma_{w}\sigma_{z}\geq\left\|\bm{\bar{x}}\right\|_{\ell_{2}}/(md^{\frac{5}{2}}\log{d}^{\frac{3}{2}})$.
Then, as long as

$\displaystyle k\geq C\cdot md^{4}\log\left(d\right)^{3}$

with $C$ a fixed constant, running GDA updates per equation 3 starting from
the random $\bm{W}_{0}$ above and $\bm{d}_{0}=\bm{0}$222The zero
initialization of $\bm{d}$ is merely done for simplicity. A similar result can
be derived for an arbitrary initialization of the discriminator’s parameters
with minor modifications. See Theorem 2.3 for such a result. with step-sizes
obeying $0<\mu\leq 1$ and $\eta=\bar{\eta}\frac{\mu}{324\cdot
k\cdot\frac{d+\frac{n-1}{\pi}}{n}\cdot\sigma_{v}^{2}\cdot\sigma_{z}^{2}}$,
with $\bar{\eta}\leq 1$, satisfies

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\bm{V}\text{ReLU}\left(\bm{W}_{\tau}\bm{z}_{i}\right)-\bar{\bm{x}}\right\|_{\ell_{2}}\leq
5\left(1-10^{-5}\cdot\bar{\eta}\mu\right)^{\tau}\left\|\frac{1}{n}\sum_{i=1}^{n}\bm{V}\text{ReLU}\left(\bm{W}_{0}\bm{z}_{i}\right)-\bar{\bm{x}}\right\|_{\ell_{2}}.$
(4)

This holds with probability at least
$1-\left(n+5\right)e^{-\frac{m}{1500}}-5k\cdot e^{-c_{1}\cdot
n}-\left(2k+2\right)e^{-\frac{d}{216}}-ne^{-c_{2}\cdot
md^{3}\log\left(d\right)^{2}}$ where $c_{1}$, $c_{2}$ are fixed numerical
constants.

To better understand the implications of the above theorem, note that the
objective of equation 2 can be simplified by solving the inner maximization in
a closed form so that the min-max problem in equation 2 is equivalent to the
following single minimization problem:

$\displaystyle\min_{\bm{W}}\text{
}\mathcal{L}(\bm{W}):=\frac{1}{2}\left\|\frac{1}{n}\sum_{i=1}^{n}\bm{V}\text{ReLU}\left(\bm{W}\bm{z}_{i}\right)-\bar{\bm{x}}\right\|_{\ell_{2}}^{2},$
(5)

which has a global optimum of zero. As a result equation 4 in Theorem 2.1
guarantees that running simultaneous GDA updates achieves the global optimum.
This holds as long as the generator network is sufficiently overparameterized
in the sense that the number of hidden nodes is polynomially large in its
output dimension $m$ and input dimension $d$. Interestingly, the rate of
convergence guaranteed by this result is geometric, guaranteeing fast GDA
convergence to the global optima. To the extent of our knowledge, this is the
first result that establishes the global convergence of simultaneous GDA for
an overparameterized GAN model.

While the result proved above shows the global convergence of GDA for a GAN
with 1-hidden layer generator and a linear discriminator, for a general GAN
model, local saddle points may not even exist and GDA may converge to
approximate local saddle points (Berard et al., 2020; Farnia & Ozdaglar,
2020). For a general min-max problem, (Daskalakis et al., 2020) has recently
shown that _approximate_ local saddle points exist under some general
conditions on the lipschitzness of the objective function. Understanding GDA
dynamics for a general GAN remains an important open problem. Our result in
Theorem 2.1 is a first and important step towards that.

We acknowledge that the considered GAN formulation of equation 2 is very
simpler than GANs used in practice. Specially, since the discriminator is
linear, this GAN can be viewed as a moment-matching GAN (Li et al., 2017)
pushing first moments of input and generative distributions towards each
other. Alternatively, this GAN formulation can be viewed as one instance of
the Sliced Wasserstein GAN (Deshpande et al., 2018). Although the maximization
on discriminator’s parameters is concave, the minimization over the
generator’s parameters is still non-convex due to the use of a neural-net
generator. Thus, the overall optimization problem is a non-trivial non-convex
concave min-max problem. From that perspective, our result in Theorem 2.1
partially explains the role of model overparameterization in GDA’s convergence
for GANs.

Given the closed form equation 5, one may wonder what would happen if we run
gradient descent on this minimization objective directly. That is running
gradient descent updates of the form
$\bm{W}_{\tau+1}=\bm{W}_{\tau}-\eta\nabla{\cal{L}}(\bm{W}_{\tau})$ with
$\mathcal{L}(\bm{W})$ given by equation 5. This is equivalent to GDA but
instead of running one gradient ascent iteration for the maximization
iteration we run infinitely many. Interestingly, in some successful GAN
implementations (Gulrajani et al., 2017), often more updates on the
discriminator’s parameters are run per generator’s updates. This is the
subject of the next result.

###### Theorem 2.2

Consider the setup of Theorem 2.1. Then as long as

$\displaystyle k\geq C\cdot md^{4}\log\left(d\right)^{3}$

with $C$ a fixed numerical constant, running GD updates of the form
$\bm{W}_{\tau+1}=\bm{W}_{\tau}-\eta\nabla{\cal{L}}(\bm{W}_{\tau})$ on the loss
given in equation 5 with step-size
$\eta=\frac{2\bar{\eta}}{243k\cdot\frac{d+\frac{n-1}{\pi}}{n}\cdot\sigma_{v}^{2}\cdot\sigma_{z}^{2}}$,
with $\bar{\eta}\leq 1$, satisfies

$\displaystyle\left\|\frac{1}{n}\sum_{i=1}^{n}\bm{V}\text{ReLU}\left(\bm{W}_{\tau}\bm{z}_{i}\right)-\bar{\bm{x}}\right\|_{\ell_{2}}\leq\left(1-4\times
10^{-6}\cdot\bar{\eta}\right)^{\tau}\left\|\frac{1}{n}\sum_{i=1}^{n}\bm{V}\text{ReLU}\left(\bm{W}_{0}\bm{z}_{i}\right)-\bar{\bm{x}}\right\|_{\ell_{2}}.$
(6)

This holds with probability at least
$1-\left(n+5\right)e^{-\frac{m}{1500}}-5k\cdot e^{-c_{1}\cdot
n}-\left(2k+2\right)e^{-\frac{d}{216}}-ne^{-c_{2}\cdot
md^{3}\log{\left(d\right)}^{2}}$ with $c_{1}$, $c_{2}$ fixed numerical
constants.

This theorem states that if we solve the max part of equation 2 in closed form
and run GD on the loss function per equation 5 with enough
overparameterization, the loss will decrease at a geometric rate to zero. This
result holds again when the model is sufficiently overparameterized. The proof
of Theorem 2.2 relies on a result from (Oymak & Soltanolkotabi, 2020), which
was developed in the framework of supervised learning. Also note that the
amount of overparameterization required in both Theorems 2.1 and 2.2 is the
same.

(a) Discriminator trained to optimality

(b) Gradient Descent Ascent

(c) $d_{iter}$ steps of discriminator update per generator iteration

Figure 2: Convergence plot a GAN model with linear discriminator and 1-hidden
layer generator as the hidden dimension ($k$) increases. Final mse is the mse
loss between true data mean and the mean of generated distribution. Over-
parameterized models show improved convergence

###  2.4 Can the analysis be extended to more general GANs?

In the previous section, we focused on the implications of our results for
one-hidden layer generator and linear discriminator. However, as it will
become clear in the proofs, our theoretical results are based on analyzing the
convergence behavior of GDA on a more general min-max problem of the form

$\displaystyle\underset{\bm{\theta}\in\mathbb{R}^{p}}{\text{min
}}\underset{\bm{d}\in\mathbb{R}^{m}}{\text{max
}}h(\bm{\theta},\bm{d}):=\left\langle\bm{d},f\left(\bm{\theta}\right)-\bm{y}\right\rangle-\frac{\left\|\bm{d}\right\|_{\ell_{2}}^{2}}{2},$
(7)

where $f:\mathbb{R}^{p}\rightarrow\mathbb{R}^{m}$ denotes a general nonlinear
mapping.

######  Theorem 2.3 (Informal version of Theorem A.4)

Consider a general nonlinear mapping
$f:\mathbb{R}^{p}\rightarrow\mathbb{R}^{m}$ with the singular values of its
Jacobian mapping around initialization obeying certain assumptions (most
notably $\sigma_{\min}(\mathcal{J}(\bm{\theta}_{0}))\geq\alpha$). Then,
running GDA iterations of the form

$\displaystyle\begin{cases}\bm{d}_{t+1}=\bm{d}_{t}+\mu\nabla_{\bm{d}}h(\bm{\theta}_{t},\bm{d}_{t})\\\
\bm{\theta}_{t+1}=\bm{\theta}_{t}-\eta\nabla_{\bm{\theta}}h(\bm{\theta}_{t},\bm{d}_{t})\end{cases}$
(8)

with sufficiently small step sizes $\eta$ and $\mu$ obeys

$\displaystyle\left\|f(\bm{\theta}_{t})-\bm{y}\right\|_{\ell_{2}}\leq\gamma\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t}\sqrt{\left\|f(\bm{\theta}_{0})-\bm{y}\right\|_{\ell_{2}}^{2}+\left\|\bm{d}_{0}\right\|_{\ell_{2}}^{2}}.$

Note that similar to the previous sections one can solve the maximization
problem in equation 7 in closed form so that equation 7 is equivalent to the
following minimization problem

$\displaystyle\underset{\bm{\theta}\in\mathbb{R}^{p}}{\text{min
}}\mathcal{L}(\bm{\theta}):=\frac{1}{2}\left\|f(\bm{\theta})-\bm{y}\right\|_{\ell_{2}}^{2},$
(9)

with global optima equal to zero. Theorem 2.3 ensures that GDA converges with
a fast geometric rate to this global optima. This holds as soon as the model
$f(\bm{\theta})$ is sufficiently overparameterized which is quantitatively
captured via the minimum singular value assumption on the Jacobian at
initialization ($\sigma_{\min}(\mathcal{J}(\bm{\theta}_{0}))\geq\alpha$ which
can only hold when $m\leq p$). This general result can thus be used to provide
theoretical guarantees for a much more general class of generators and
discriminators. To be more specific, consider a deep GAN model where the
generator $\mathcal{G}_{\bm{\theta}}$ is a deep neural network with parameters
$\bm{\theta}$ and the discriminator is a deep random feature model of the form
$\mathcal{D}_{\bm{d}}(\bm{x})=\bm{d}^{T}\psi(\bm{x})$ parameterized with $d$
and $\psi:\mathbb{R}^{d}\rightarrow\mathbb{R}^{m}$ a deep neural network with
random weights. Then the min-max training optimization problem equation 1 with
a regularizer $\mathcal{R}(\bm{d})=-\left\|\bm{d}\right\|_{\ell_{2}}^{2}/2$ is
a special instance of equation 7 with

$\displaystyle
f(\bm{\theta}):=\frac{1}{n}\sum_{i=1}^{n}\psi(\mathcal{G}_{\bm{\theta}}(\bm{z}_{i}))\quad\text{and}\quad\bm{y}:=\frac{1}{n}\sum_{i=1}^{n}\psi(\bm{x}_{i})$

Therefore, the above result can in principle be used to rigorously analyze
global convergence of GDA for an overparameterized GAN problem with a deep
generator and a deep random feature discriminator model. However,
characterizing the precise amount of overparameterization required for such a
result to hold requires a precise analysis of the minimum singular value of
the Jacobian of $f(\bm{\theta})$ at initialization as well as other singular
value related conditions stated in Theorem A.4. We defer such a precise
analysis to future works.

Figure 3: MLP Overparameterization on MNIST.

##### Numerical Validations:

Next, we numerically study the convergence of GAN model considered in Theorems
2.1 and 2.2 where the discriminator is a linear network while the generator is
a one hidden layer neural net. In our experiments, we generate $\bm{x}_{i}$’s
from an $m$-dimension Gaussian distribution with mean $\mu$ and an identity
covariance matrix. The mean vector $\mu$ is randomly generated. We train two
variants of GAN models using (1) GDA (as considered in Thm 2.1) and (2) GD on
generator while solving the discriminator to optimality (as considered in Thm
2.2).

In Fig. 2, we plot the converged loss values of GAN models trained using both
techniques (1) and (2) as the hidden dimension $k$ of the generator is varied.
The MSE loss between the true data mean and the data mean of generated samples
is used as our evaluation metric. As this MSE loss approaches $0$, the model
converges to the global saddle point. We observe that overparameterized GAN
models show improved convergence behavior than the narrower models.
Additionally, the MSE loss converges to $0$ for larger values of $k$ which
shows that with sufficient overparamterization, GDA converges to a global
saddle point.

##  3 Experiments

(a) DCGAN, CIFAR

(b) DCGAN, CelebA

(c) DCGAN

(d) Resnet, CIFAR

(e) Resnet, CelebA

(f) Resnet

Figure 4: Overparamterization Results: We plot the FID scores (lower, better)
of DCGAN and Resnet DCGAN as the hidden dimension $k$ is varied. Results on
CIFAR-10 and Celeb-A are shown on the plots on the left and right panels,
respectively. Overparameterization gives better FID scores.

(a) CIFAR

(b) CelebA

Figure 5: DCGAN Training Results: We plot the FID scores across training
iterations of DCGAN on CIFAR-10 and Celeb-A for different values of hidden
dimension k. Remarkably, we observe that over-parameterization improves the
rate of convergence of GDA and its stability in training.

(a) DCGAN

(b) Resnet

Figure 6: Generalization in GANs: We plot the NND scores as the hidden
dimension k is varied for DCGAN (shown in (a)) and Resnet (shown in (b))
models.

In this section, we demonstrate benefits of overparamterization in large GAN
models. In particular, we train GANs on two benchmark datasets: CIFAR-10
($32\times 32$ resolution) and Celeb-A ($64\times 64$ resolution). We use two
commonly used GAN architectures: DCGAN and Resnet-based GAN. For both of these
architectures, we train several models, each with a different number of
filters in each layer, denoted by $k$. For simplicity, we refer to $k$ as the
hidden dimension. Appendix Fig. 8 illustrates the architectures used in our
experiments. Networks with large $k$ are more overparameterized.

We use the same value of $k$ for both generator and discriminator networks.
This is in line with the design choice made in most recent GAN models (Radford
et al., 2016; Brock et al., 2019), where the size of generator and
discriminator models are roughly maintained the same. We train each model till
convergence and evaluate the performance of converged models using FID scores.
FID scores measure the Frechet distance between feature distributions of real
and generated data distributions (Heusel et al., 2017). A small FID score
indicates high-quality synthesized samples. Each experiment is conducted for
$5$ runs, and mean and the variance of FID scores are reported.

Overparameterization yields better generative models: In Fig. 4, we show the
plot of FID scores as the hidden dimension ($k$) is varied for DCGAN and
Resnet GAN models. We observe a clear trend where the FID scores are high
(i.e. poor) for small values of $k$, while they improve as models become more
overparameterized. Also, the FID scores saturate beyond $k=64$ for DCGAN
models, and $k=128$ for Resnet GAN models. Interestingly, these are the
standard values used in the existing model architecures (Radford et al., 2016;
Gulrajani et al., 2017).This trend is also consistent on MLP GANs trained on
MNIST dataset (Fig. 3). We however notice that FID score in MLP GANs increase
marginally as $k$ increases from $1024$ to $2048$. This is potentially due to
an increased generalization gap in this regime where it offsets potential
benefits of over-parameterization

Overparameterization leads to improved convergence of GDA: In Fig. 5, we show
the plot of FID scores over training iterations for different values for $k$.
We observe that models with larger values of $k$ converge faster and
demonstrate a more stable behavior. This agrees with our theoretical results
that overparameterized models have a fast rate of convergence.

Generalization gap in GANs: To study the generalization gap, we compute the
FID scores by using (1) the training-set of real data, which we call _FID
train_ , and (2) a held-out validation set of real data, which we call _FID
test_. In Fig. 4, a plot of FID train _(in blue)_ and FID test _(in green)_
are shown as the hidden dimension $k$ is varied. We observe that FID test
values are consistently higher than the the FID train values. Their gap does
not increase with increasing overparameterization.

However, as explained in (Gulrajani et al., 2019), the FID score has the issue
of assigning low values to memorized samples. To alleviate the issue,
(Gulrajani et al., 2019; Arora et al., 2017) proposed Neural Net Divergence
(NND) to measure generalization in GANs. In Fig. 6, we plot NND scores by
varying the hidden dimensions in DCGAN and Resnet GAN trained on CIFAR-10
dataset. We observe that increasing the value of $k$ decreases the NND score.
Interestingly, the NND score of memorized samples are higher than most of the
GAN models. This indicates that overparameterized models have not been
memorizing training samples and produce better generative models.

##  4 Conclusion

In this paper, we perform a systematic study of the importance of
overparameterization in training GANs. We first analyze a GAN model with one-
hidden layer generator and a linear discriminator optimized using Gradient
Descent Ascent (GDA). Under this setup, we prove that with sufficient
overparameterization, GDA converges to a global saddle point. Additionally,
our result demonstrate that overparameterized models have a fast rate of
convergence. We then validate our theoretical findings through extensive
experiments on DCGAN and Resnet models trained on CIFAR-10 and Celeb-A
datasets. We observe overparameterized models to perform well both in terms of
the rate of convergence and the quality of generated samples.

##  5 Acknowledgement

M. Sajedi would like to thank Sarah Dean for introducing (Rugh, 1996). This
project was supported in part by NSF CAREER AWARD 1942230, HR00112090132,
HR001119S0026, NIST 60NANB20D134 and Simons Fellowship on “Foundations of Deep
Learning.” M. Soltanolkotabi is supported by the Packard Fellowship in Science
and Engineering, a Sloan Research Fellowship in Mathematics, an NSF-CAREER
under award 1846369, the Air Force Office of Scientific Research Young
Investigator Program (AFOSR-YIP) under award FA9550-18-1-0078, DARPA Learning
with Less Labels (LwLL) and FastNICS programs, and NSF-CIF awards 1813877 and
2008443.

## References

  * Adolphs et al. (2019) Leonard Adolphs, Hadi Daneshmand, Aurelien Lucchi, and Thomas Hofmann.  Local saddle point optimization: A curvature exploitation approach.  In _The 22nd International Conference on Artificial Intelligence and Statistics_ , pp. 486–495, 2019.
  * Allen-Zhu et al. (2019) Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song.  A convergence theory for deep learning via over-parameterization.  In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, California, USA, June 9-15, 2019_ , volume 97 of _Proceedings of Machine Learning Research_ , pp. 242–252, 2019.
  * An et al. (2018) Wangpeng An, Haoqian Wang, Qingyun Sun, Jun Xu, Qionghai Dai, and Lei Zhang.  A pid controller approach for stochastic optimization of deep networks.  In _Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition_ , pp. 8522–8531, 2018.
  * Arjovsky et al. (2017) Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein generative adversarial networks.  In _Proceedings of the 34th International Conference on Machine Learning, ICML 2017, Sydney, Australia, Aug 6-11, 2017_ , Proceedings of Machine Learning Research, pp. 214–223, 2017.
  * Arora et al. (2017) Sanjeev Arora, Rong Ge, Yingyu Liang, Tengyu Ma, and Yi Zhang.  Generalization and equilibrium in generative adversarial nets (gans).  _arXiv preprint arXiv:1703.00573_ , 2017.
  * Arrow et al. (1958) Kenneth J Arrow, Leonid Hurwicz, and Hirofumi Uzawa.  _Studies in linear and non-linear programming_.  Cambridge Univ. Press, 1958.
  * Berard et al. (2020) Hugo Berard, Gauthier Gidel, Amjad Almahairi, Pascal Vincent, and Simon Lacoste-Julien.  A closer look at the optimization landscapes of generative adversarial networks.  In _International Conference on Learning Representations_ , 2020.  URL https://openreview.net/forum?id=HJeVnCEKwH.
  * Brock et al. (2019) Andrew Brock, Jeff Donahue, and Karen Simonyan.  Large scale GAN training for high fidelity natural image synthesis.  In _International Conference on Learning Representations_ , 2019.
  * Chizat et al. (2019) Lenaic Chizat, Edouard Oyallon, and Francis Bach.  On lazy training in differentiable programming.  In _Advances in Neural Information Processing Systems_ , pp. 2937–2947, 2019.
  * Clark et al. (2019) Aidan Clark, Jeff Donahue, and Karen Simonyan.  Adversarial video generation on complex datasets.  _arXiv preprint arXiv:1907.06571_ , 2019.  URL https://arxiv.org/abs/1907.06571.
  * Daskalakis et al. (2020) Constantinos Daskalakis, Stratis Skoulakis, and Manolis Zampetakis.  The complexity of constrained min-max optimization.  _arXiv preprint arXiv:2009.09623_ , 2020.  URL https://arxiv.org/abs/2009.09623.
  * Deshpande et al. (2018) Ishan Deshpande, Ziyu Zhang, and Alexander G Schwing.  Generative modeling using the sliced wasserstein distance.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pp. 3483–3491, 2018.
  * Dinh et al. (2017) Laurent Dinh, Jascha Sohl-Dickstein, and Samy Bengio.  Density estimation using real nvp.  In _5th International Conference on Learning Representations, ICLR 2017, Toulon, France, April 24-26, 2017, Conference Track Proceedings_ , 2017.
  * Du et al. (2019) Simon S. Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh.  Gradient descent provably optimizes over-parameterized neural networks.  In _7th International Conference on Learning Representations, ICLR 2019, New Orleans, LA, USA, May 6-9, 2019, Conference Track Proceedings_ , 2019.
  * Farnia & Ozdaglar (2020) Farzan Farnia and Asuman Ozdaglar.  Gans may have no nash equilibria.  _arXiv preprint arXiv:2002.09124_ , 2020.
  * Feizi et al. (2018) Soheil Feizi, Farzan Farnia, Tony Ginart, and David Tse.  Understanding GANs: the LQG setting.  _arXiv preprint arXiv:1710.10793_ , 2018.  URL https://arxiv.org/abs/1710.10793.
  * Goodfellow et al. (2014) Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Z. Ghahramani, M. Welling, C. Cortes, N. D. Lawrence, and K. Q. Weinberger (eds.), _Advances in Neural Information Processing Systems 27_ , pp. 2672–2680, 2014.
  * Gulrajani et al. (2017) Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron C Courville.  Improved training of wasserstein gans.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), _Advances in Neural Information Processing Systems 30_ , pp. 5767–5777, 2017.
  * Gulrajani et al. (2019) Ishaan Gulrajani, Colin Raffel, and Luke Metz.  Towards GAN benchmarks which require generalization.  In _International Conference on Learning Representations_ , 2019.  URL https://openreview.net/forum?id=HkxKH2AcFm.
  * Gutman (1979) Shaul Gutman.  Uncertain dynamical systems–a lyapunov min-max approach.  _IEEE Transactions on Automatic Control_ , 24(3):437–443, 1979.
  * Heusel et al. (2017) Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter.  Gans trained by a two time-scale update rule converge to a local nash equilibrium.  In _Advances in neural information processing systems 30_ , pp. 6626–6637, 2017.
  * Karras et al. (2019) Tero Karras, Samuli Laine, and Timo Aila.  A style-based generator architecture for generative adversarial networks.  In _IEEE Conference on Computer Vision and Pattern Recognition, CVPR 2019, Long Beach, CA, USA, June 16-20, 2019_ , pp. 4401–4410. Computer Vision Foundation / IEEE, 2019.
  * Kingma & Welling (2014) Diederik P. Kingma and Max Welling.  Auto-encoding variational bayes.  In Yoshua Bengio and Yann LeCun (eds.), _2nd International Conference on Learning Representations, ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings_ , 2014.
  * Ledoux (2001) Michel Ledoux.  _The concentration of measure phenomenon_.  Number 89 in Mathematical Surveys and Monographs. American Mathematical Soc., 2001.
  * Lei et al. (2019) Qi Lei, Jason D Lee, Alexandros G Dimakis, and Constantinos Daskalakis.  Sgd learns one-layer networks in wgans.  _arXiv preprint arXiv:1910.07030_ , 2019.  URL https://arxiv.org/abs/1910.07030.
  * Li et al. (2017) Chun-Liang Li, Wei-Cheng Chang, Yu Cheng, Yiming Yang, and Barnabas Poczos.  Mmd gan: Towards deeper understanding of moment matching network.  In I. Guyon, U. V. Luxburg, S. Bengio, H. Wallach, R. Fergus, S. Vishwanathan, and R. Garnett (eds.), _Advances in Neural Information Processing Systems 30_ , pp. 2203–2213, 2017.
  * Mescheder et al. (2017) Lars Mescheder, Sebastian Nowozin, and Andreas Geiger.  The numerics of GANs.  In _Advances in Neural Information Processing Systems 30_ , pp. 1823–1833, 2017.
  * Mescheder et al. (2018) Lars Mescheder, Andreas Geiger, and Sebastian Nowozin.  Which training methods for gans do actually converge?  _arXiv preprint arXiv:1801.04406_ , 2018.  URL https://arxiv.org/abs/1801.04406.
  * Nagarajan & Kolter (2017) Vaishnavh Nagarajan and J Zico Kolter.  Gradient descent GAN optimization is locally stable.  In _Advances in Neural Information Processing Systems 30_ , pp. 5591–5600, 2017.
  * Oymak & Soltanolkotabi (2019) Samet Oymak and Mahdi Soltanolkotabi.  Overparameterized nonlinear learning: Gradient descent takes the shortest path?  In _Proceedings of the 36th International Conference on Machine Learning, ICML 2019, Long Beach, California, USA, June 9-15, 2019_ , Proceedings of Machine Learning Research, pp. 4951–4960, 2019.
  * Oymak & Soltanolkotabi (2020) Samet Oymak and Mahdi Soltanolkotabi.  Towards moderate overparameterization: global convergence guarantees for training shallow neural networks.  _IEEE Journal on Selected Areas in Information Theory_ , 2020.
  * Oymak et al. (2019) Samet Oymak, Zalan Fabian, Mingchen Li, and Mahdi Soltanolkotabi.  Generalization guarantees for neural networks via harnessing the low-rank structure of the jacobian.  _arXiv preprint arXiv:1906.05392_ , 2019.  URL https://arxiv.org/abs/1906.05392.
  * Radford et al. (2016) Alec Radford, Luke Metz, and Soumith Chintala.  Unsupervised representation learning with deep convolutional generative adversarial networks.  In Yoshua Bengio and Yann LeCun (eds.), _4th International Conference on Learning Representations, ICLR 2016, San Juan, Puerto Rico, May 2-4, 2016, Conference Track Proceedings_ , 2016.
  * Rugh (1996) Wilson J Rugh.  _Linear system theory_.  Prentice-Hall, Inc., 1996.
  * Soltanolkotabi (2019) Mahdi Soltanolkotabi.  Structured signal recovery from quadratic measurements: Breaking sample complexity barriers via nonconvex optimization.  _IEEE Transactions on Information Theory_ , 65(4):2374–2400, 2019.
  * Soltanolkotabi et al. (2018) Mahdi Soltanolkotabi, Adel Javanmard, and Jason D Lee.  Theoretical insights into the optimization landscape of over-parameterized shallow neural networks.  _IEEE Transactions on Information Theory_ , 65(2):742–769, 2018.
  * Van Veen et al. (2018) Dave Van Veen, Ajil Jalal, Mahdi Soltanolkotabi, Eric Price, Sriram Vishwanath, and Alexandros G Dimakis.  Compressed sensing with deep image prior and learned regularization.  _arXiv preprint arXiv:1806.06438_ , 2018.  URL https://arxiv.org/abs/1806.06438.
  * Von Neumann & Morgenstern (1953) John Von Neumann and Oskar Morgenstern.  _Theory of games and economic behavior_.  Princeton university press, 1953.
  * Xu et al. (2019) Kun Xu, Chongxuan Li, Huanshu Wei, Jun Zhu, and Bo Zhang.  Understanding and stabilizing gans’ training dynamics with control theory.  _arXiv preprint arXiv:1909.13188_ , 2019.
  * Zou & Gu (2019) Difan Zou and Quanquan Gu.  An improved analysis of training over-parameterized deep neural networks.  In _Advances in Neural Information Processing Systems 32_ , pp. 2055–2064, 2019.

Appendix

##  Appendix A Proofs

In this section, we prove Theorems 2.1 and 2.2. First, we provide some
notations we use throughout the remainder of the paper in Section A.1. Before
proving these specialized results for one hidden layer generators and linear
discriminators (Theorems 2.1 and 2.2), we state and prove a more general
result (formal version of Theorem 2.3) on the convergence of GDA on a general
class of min-max problems in Section A.3. Then we state a few preliminary
calculations in Section A.4. Next, we state some key lemmas in Section A.5 and
defer their proofs to Appendix B. Finally, we prove Theorems 2.1 and 2.2 in
Sections A.6 and A.7, respectively.

###  A.1 Notation

We will use $C$, $c$, $c_{1}$, etc. to denote positive absolute constants,
whose value may change throughout the paper and from line to line. We use
$\phi\left(z\right)=\text{ReLU}\left(z\right)=\text{max}\left(0,z\right)$ and
its (generalized) derivative
$\phi^{\prime}\left(z\right)=\bm{1}_{\left\\{z\geq 0\right\\}}$ with $\bm{1}$
being the indicator function. $\sigma_{min}\left(\bm{X}\right)$ and
$\sigma_{max}\left(\bm{X}\right)=\left\|\bm{X}\right\|$ denote the minimum and
maximum singular values of matrix $\bm{X}$. For two arbitrary matrices
$\bm{A}$ and $\bm{B}$, $\bm{A}\otimes\bm{B}$ denotes their kronecker product.
The spectral radius of a matrix $\bm{A}\in{\mathbb{C}}^{n\times n}$ is defined
as
$\rho\left(\bm{A}\right)=\text{max}\left\\{|\lambda_{1}|,\ldots,|\lambda_{n}|\right\\}$,
where $\lambda_{i}$’s are the eigenvalues of $\bm{A}$. Throughout the proof we
shall assume $\phi:=ReLU$ to avoid unnecessarily long expressions.

###  A.2 Proof sketch of the main results

In this section, we provide a brief overview of our proofs. We focus on the
main result in this manuscript, which is about the convergence of GDA (Theorem
2.1). To do this we study the converge of GDA on the more general min-max
problem of the form (see Theorem A.4 for a formal statement)

$\displaystyle\underset{\bm{\theta}\in\mathbb{R}^{n}}{\text{min
}}\underset{\bm{d}\in\mathbb{R}^{m}}{\text{max
}}h(\bm{\theta},\bm{d}):=\left\langle\bm{d},f\left(\bm{\theta}\right)-\bm{y}\right\rangle-\frac{\left\|\bm{d}\right\|_{\ell_{2}}^{2}}{2}.$
(10)

In this case the GDA iterates take the form

$\displaystyle\begin{cases}\bm{d}_{t+1}=\left(1-\mu\right)\bm{d}_{t}+\mu\left(f\left(\bm{\theta}_{t}\right)-\bm{y}\right)\\\
\bm{\theta}_{t+1}=\bm{\theta}_{t}-\eta{\cal{J}}^{T}\left(\bm{\theta}_{t}\right)\bm{d}_{t}\end{cases}.$
(11)

Our proof for global convergence of GDA on this min-max loss consists of the
following steps.

Step 1: Recasting the GDA updates as a linear time-varying system
In the first step we carry out a series of algebraic manipulations to recast
the GDA updates (equation 11) into the following form

$\begin{bmatrix}\bm{r}_{t+1}\\\
\bm{d}_{t+1}\end{bmatrix}=\bm{A}_{t}\begin{bmatrix}\bm{r}_{t}\\\
\bm{d}_{t}\end{bmatrix},$

where $\bm{r}_{t}=f\left(\bm{\theta_{t}}\right)-\bm{y}$ denotes the residuum
and $\bm{A}_{t}$ denotes a properly defined transition matrix.

Step 2: Approximation by a linear time-invariant system
Next, to analyze the behavior of the time-varying dynamical system above we
approximate it by the following time-invariant linear dynamical system

$\begin{bmatrix}\widetilde{\bm{r}}_{t+1}\\\
\widetilde{\bm{d}}_{t+1}\end{bmatrix}=\begin{bmatrix}\bm{I}&-\eta{\cal{J}}^{T}\left(\bm{\theta}_{0}\right){\cal{J}}\left(\bm{\theta}_{0}\right)\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}\begin{bmatrix}\widetilde{\bm{r}}_{t}\\\
\widetilde{\bm{d}}_{t}\end{bmatrix},$

where $\bm{\theta}_{0}$ denotes the initialization. The validity of this
approximation is ensured by our assumptions on the Jacobian of the function
$f$, which, among others, guarantee that it does not change too much in a
sufficiently large neighborhood around the initialization and that the
smallest singular value of $\mathcal{J}\left(\bm{\theta}_{0}\right)$ is
bounded from below.

Step 3: Analysis of time-invariant linear dynamical system
To analyze the time-invariant dynamical system above, we utilize and refine
intricate arguments from the control theory literature involving the spectral
radius of the fixed transition matrix above to obtain

$\left\|\begin{bmatrix}\widetilde{\bm{r}}_{t}\\\
\widetilde{\bm{d}}_{t}\end{bmatrix}\right\|_{\ell_{2}}\lesssim\left(1-\eta\alpha^{2}\right)^{t}\left\|\begin{bmatrix}\widetilde{\bm{r}}_{0}\\\
\widetilde{\bm{d}}_{0}\end{bmatrix}\right\|_{\ell_{2}}.$

Step 4: Completing the proof via a perturbation argument
In the last step of our proof we show that the two sequences
$\begin{bmatrix}\bm{r}_{t}\\\ \bm{d}_{t}\end{bmatrix}$ and
$\begin{bmatrix}\widetilde{\bm{r}}_{t}\\\ \widetilde{\bm{d}}_{t}\end{bmatrix}$
will remain close to each other. This is based on a novel perturbation
argument. The latter combined with Step 3 allows us to conclude

$\left\|\begin{bmatrix}\bm{r}_{t}\\\
\bm{d}_{t}\end{bmatrix}\right\|_{\ell_{2}}\lesssim\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t}\left\|\begin{bmatrix}\bm{r}_{0}\\\
\bm{d}_{0}\end{bmatrix}\right\|_{\ell_{2}},$

which finishes the global convergence of GDA on equation 10 and hence the
proof of Theorem A.4.

In order to deduce Theorem 2.1 from Theorem A.4, we need to check that the
Jacobian at the initialization is bounded from below at the origin and that it
does not change too quickly in a large enough neighborhood. In order to prove
that we will leverage recent ideas from the deep learning theory literature
revolving around the neural tangent kernel. This allows us to guarantee that
this conditions are indeed met, if the neural network is sufficiently wide and
the initialization is chosen large enough.

The second main result of this manuscript, Theorem 2.2, can be deduced more
directly from recent results on overparameterized learning (see Oymak &
Soltanolkotabi (2020)). Hence, we have deferred its proof to Section A.7.

###  A.3 Analysis of GDA: A control theory perspective

In this section we will focus on solving a general min-max optimization
problem of the form

$\displaystyle\underset{\bm{\theta}\in\mathbb{R}^{n}}{\text{min
}}\underset{\bm{d}\in\mathbb{R}^{m}}{\text{max
}}h(\bm{\theta},\bm{d}):=\left\langle\bm{d},f\left(\bm{\theta}\right)-\bm{y}\right\rangle-\frac{\left\|\bm{d}\right\|_{\ell_{2}}^{2}}{2},$
(12)

where $f:\mathbb{R}^{n}\rightarrow\mathbb{R}^{m}$ is a general nonlinear
mapping. In particular, we focus on analyzing the convergence behavior of
Gradient Descent/Ascent (GDA) on the above loss, starting from initial
estimates $\bm{\theta}_{0}$ and $\bm{d}_{0}$. In this case the GDA updates
take the following form

$\displaystyle\begin{cases}\bm{d}_{t+1}=\left(1-\mu\right)\bm{d}_{t}+\mu\left(f\left(\bm{\theta}_{t}\right)-\bm{y}\right)\\\
\bm{\theta}_{t+1}=\bm{\theta}_{t}-\eta{\cal{J}}^{T}\left(\bm{\theta}_{t}\right)\bm{d}_{t}\end{cases}.$
(13)

We note that solving the inner maximization problem in equation 12 would yield

$\displaystyle\underset{\bm{\theta}\in\mathbb{R}^{n}}{\text{min
}}\frac{1}{2}\left\|f\left(\bm{\theta}\right)-\bm{y}\right\|_{\ell_{2}}^{2}.$
(14)

In this section, our goal is to show that when running the GDA updates of
equation 13, the norm of the residual vector defined as
$\bm{r}_{t}:=f\left(\bm{\theta_{t}}\right)-\bm{y}$ goes to zero and hence we
reach a global optimum of equation 14 (and in turn equation 12).

Our proof will build on ideas from control theory and dynamical systems
literature. For that, we are first going to rewrite the equations 13 in a more
convenient way. We define the average Jacobian along the path connecting two
points $\bm{x}$,$\bm{y}\in\mathbb{R}^{n}$ as

$\displaystyle{\cal{J}}\left(\bm{y},\bm{x}\right)=\int_{0}^{1}{\cal{J}}\left(\bm{x}+\alpha\left(\bm{y}-\bm{x}\right)\right)d\alpha,$

where ${\cal{J}}\left(\theta\right)\in\mathbb{R}^{m\times n}$ is the Jacobian
associated with the nonlinear mapping $f$. Next, from the fundamental theorem
of calculus it follows that

$\displaystyle\bm{r}_{t+1}=f\left(\bm{\theta}_{t+1}\right)-\bm{y}$
$\displaystyle=f\left(\bm{\theta}_{t}-\eta{\cal{J}}_{t}^{T}\bm{d}_{t}\right)-\bm{y}$
$\displaystyle=f\left(\bm{\theta}_{t}\right)-\eta{\cal{J}}_{t+1,t}{\cal{J}}_{t}^{T}\bm{d}_{t}-\bm{y}$
$\displaystyle=\bm{r}_{t}-\eta{\cal{J}}_{t+1,t}{\cal{J}}_{t}^{T}\bm{d}_{t},$
(15)

where we used the shorthands
${\cal{J}}_{t}:={\cal{J}}\left(\bm{\theta}_{t}\right)$ and
${\cal{J}}_{t+1,t}:={\cal{J}}\left(\bm{\theta}_{t+1},\bm{\theta}_{t}\right)$
for exposition purposes.
Next, we combine the updates $\bm{r}_{t}$ and $\bm{d}_{t}$ into a state vector
of the form $\bm{z}_{t}:=\begin{bmatrix}\bm{r}_{t}\\\
\bm{d}_{t}\end{bmatrix}\in\mathbb{R}^{2m}$. Using this notation the
relationship between the state vectors from one iteration to the next takes
the form

$\displaystyle\bm{z}_{t+1}=\underset{=:\bm{A}_{t}}{\underbrace{\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{t+1,t}{\cal{J}}_{t}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}}}\bm{z}_{t},~{}~{}t\geq 0,$
(16)

which resembles a time-varying linear dynamical system with transition matrix
$\bm{A}_{t}$. Now note that to show convergence of $\bm{r}_{t}$ to zero it
suffices to show convergence of $\bm{z}_{t}$ to zero. To do this we utilize
the following notion of uniform exponential stability, which will be crucial
in analyzing the solutions of equation 16. (See Rugh (1996) for a
comprehensive overview on stability notions in discrete state equations.)

###### Definition 1

A linear state equation of the form $\bm{z}_{t+1}=\bm{A}_{t}\bm{z}_{t}$ is
called uniformly exponentially stable if for every $t\geq 0$ we have
$\left\|\bm{z}_{t}\right\|_{\ell_{2}}\leq\gamma\lambda^{t}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$,
where $\gamma\geq 1$ is a finite constant and $0\leq\lambda<1$.

Using the above definition to show the convergence of the state vector
$\bm{z}_{t}$ to zero at a geometric rate it suffices to show the state
equation 16 is exponentially stable.333We note that technically the dynamical
system equation 16 is not linear. However, we still use exponential stability
with some abuse of notation to refer to the property that
$\left\|\bm{z}_{t}\right\|_{\ell_{2}}\leq\gamma\lambda^{t}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
holds. As we will see in the forth-coming paragraphs, our formal analysis is
via a novel perturbation analysis of a linear dynamical system and therefore
keeping this terminology is justified. For that, we are first going to analyze
a state equation which results from linearizing the nonlinear function
$f\left(\bm{\theta}\right)$ around the initialization $\bm{\theta}_{0}$. In
the next step, we are going to show that the behavior of these two problems
are similar, provided we stay close to initialization (which we are also going
to prove). Specifically, we consider the linearized problem

$\displaystyle\underset{\widetilde{\bm{\theta}}\in\mathbb{R}^{n}}{\text{min
}}\underset{\widetilde{\bm{d}}\in\mathbb{R}^{m}}{\text{max
}}h_{\text{lin}}\left(\widetilde{\bm{\theta}},\widetilde{\bm{d}}\right):=\left\langle\widetilde{\bm{d}},f\left(\bm{\theta}_{0}\right)+{\cal{J}}_{0}\left(\widetilde{\bm{\theta}}-\bm{\theta}_{0}\right)-\bm{y}\right\rangle-\frac{\left\|\widetilde{\bm{d}}\right\|_{\ell_{2}}^{2}}{2}.$
(17)

We first analyze GDA on this linearized problem starting from the same
initialization as the original problem, i.e.
$\widetilde{\bm{\theta}}_{0}=\bm{\theta}_{0}$ and
$\widetilde{\bm{d}}_{0}=\bm{d}_{0}$. The gradient descent update for
$\widetilde{\bm{\theta}}_{t}$ takes the form

$\displaystyle\widetilde{\bm{\theta}}_{t+1}=\widetilde{\bm{\theta}}_{t}-\eta{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{t},$
(18)

and the gradient ascent update for $\widetilde{\bm{d}}_{t}$ takes the form

$\displaystyle\begin{split}\widetilde{\bm{d}}_{t+1}&=\widetilde{\bm{d}}_{t}+\mu\left(f\left(\bm{\theta}_{0}\right)+{\cal{J}}_{0}\left(\widetilde{\bm{\theta}}_{t}-\bm{\theta}_{0}\right)-\bm{y}-\widetilde{\bm{d}}_{t}\right)\\\
&=\left(1-\mu\right)\widetilde{\bm{d}}_{t}+\mu\widetilde{\bm{r}}_{t},\end{split}$
(19)

where we used the linear residual defined as
$\widetilde{\bm{r}}_{t}=f\left(\bm{\theta}_{0}\right)+{\cal{J}}_{0}\left(\widetilde{\bm{\theta}}_{t}-\bm{\theta}_{0}\right)-\bm{y}$.
Moreover, the residual from one iterate to the next can be written as follows

$\displaystyle\begin{split}\widetilde{\bm{r}}_{t+1}&=f\left(\bm{\theta}_{0}\right)+{\cal{J}}_{0}\left(\widetilde{\bm{\theta}}_{t+1}-\bm{\theta}_{0}\right)-\bm{y}\\\
&=f\left(\bm{\theta}_{0}\right)+{\cal{J}}_{0}\left(\widetilde{\bm{\theta}}_{t}-\eta{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{t}-\bm{\theta}_{0}\right)-\bm{y}\\\
&=\widetilde{\bm{r}}_{t}-\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{t}.\end{split}$
(20)

Again, we define a new vector
$\widetilde{\bm{z}}_{t}=\begin{bmatrix}\widetilde{\bm{r}}_{t}\\\
\widetilde{\bm{d}}_{t}\end{bmatrix}\in\mathbb{R}^{2m}$ and by putting together
equations 19 and 20 we arrive at

$\displaystyle\widetilde{\bm{z}}_{t+1}=\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}\widetilde{\bm{z}}_{t}=\bm{A}\widetilde{\bm{z}}_{t},~{}~{}t\geq
0,$ (21)

which is of the form of a linear time-invariant state equation. As a first
step in our proof, we are going to show that the linearized state equations
are uniformly exponentially stable. First, recall the following well-known
lemma, which characterizes uniform exponential stability in terms of the
eigenvalues of $\bm{A}$.

###### Lemma A.1

(Rugh, 1996, Theorem 22.11) A linear state equation of the form
$\widetilde{\bm{z}}_{t+1}=\bm{A}\widetilde{\bm{z}}_{t}$ with $\bm{A}$ a fixed
matrix is uniformly exponentially stable if and only if all eigenvalues of
$\bm{A}$ have magnitudes strictly less than one, i.e.
$\rho\left(\bm{A}\right)<1$. In this case, it holds for all $t\geq 0$ and all
$\bm{z}$ that

$\|\bm{A}^{t}\bm{z}\|\leq\gamma\rho\left(\bm{A}\right)^{t}\|\bm{z}\|,$

where $\gamma\geq 1$ is an absolute constant, which only depends on $\bm{A}$.

In the next lemma, we prove that under suitable assumptions on ${\cal{J}}_{0}$
and the step sizes $\mu$ and $\eta$ the state equations 21 indeed fulfill this
condition.

###### Lemma A.2

Assume that
$\alpha\leq\sigma_{\text{min}}\left({\cal{J}}_{0}\right)\leq\sigma_{\text{max}}\left({\cal{J}}_{0}\right)\leq\beta$
and consider the matrix
$\bm{A}=\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}$. Suppose that
$\frac{\mu}{\eta}\geq 4\beta^{2}$. Then it holds that
$\rho\left(\bm{A}\right)\leq 1-\eta\alpha^{2}$.

Proof Suppose that $\lambda$ is an eigenvalue of $\bm{A}$. Hence, there is an
eigenvector $\left[\bm{x},\bm{y}\right]^{T}\neq\bm{0}$ such that

$\displaystyle\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}\begin{bmatrix}\bm{x}\\\
\bm{y}\end{bmatrix}=\lambda\begin{bmatrix}\bm{x}\\\ \bm{y}\end{bmatrix}$

holds. By a direct calculation we observe that this yields the equation

$\displaystyle\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\bm{x}=\left(\frac{-\left(1-\lambda\right)^{2}}{\mu}+\left(1-\lambda\right)\right)\bm{x}.$

In particular, $\bm{x}$ must be an eigenvector of
${\cal{J}}_{0}{\cal{J}}_{0}^{T}$. Denoting the corresponding eigenvalue with
$s$, we obtain the identity

$\frac{\left(1-\lambda\right)^{2}}{\mu}-\left(1-\lambda\right)+\eta s=0.$

Hence, we must have

$\lambda\in\left\\{1-\frac{\mu}{2}+\sqrt{\frac{\mu^{2}}{4}-\mu\eta s};\
1-\frac{\mu}{2}-\sqrt{\frac{\mu^{2}}{4}-\mu\eta s}\right\\}.$

Note that the square root is indeed well-defined, since

$\frac{\mu^{2}}{4}-\mu\eta s\geq\mu\eta\beta^{2}-\mu\eta s\geq 0,$

where in the first inequality we used the assumption $\frac{\mu}{\eta}\geq
4\beta^{2}$ and in the second line we used that $s\leq\beta^{2}$, which is a
consequence of our assumption on the singular values of ${\cal{J}}_{0}$.
Hence, it follows by the reverse triangle inequality that

$\displaystyle\left|\lambda\right|-\left(1-\frac{\mu}{2}\right)\leq\left|\lambda-\left(1-\frac{\mu}{2}\right)\right|=\sqrt{\left(\frac{\mu}{2}\right)^{2}-\mu\eta
s}<\frac{\mu}{2}-\eta s\leq\frac{\mu}{2}-\eta\alpha^{2},$

where the second inequality is valid as $\frac{\mu}{2}-\eta s\geq 0$ is
implied by $\frac{\mu}{2}\geq 2\eta\beta^{2}>\eta s$. In the last inequality
we used the fact that $\alpha^{2}\leq s$, which is a consequence of our
assumption on the singular values of ${\cal{J}}_{0}$. By rearranging terms, we
obtain that $|\lambda|<1-\eta\alpha^{2}$. Since $\lambda$ was an arbitrary
eigenvalue of $\bm{A}$, the result follows. $\blacksquare$

Since the last lemma shows that under suitable conditions it holds that
$\rho\left(\bm{A}\right)<1$, Lemma A.3 yields uniform exponential stability of
our state equations. However, this will not be sufficient for our purposes.
The reason is that Lemma A.3 does not specify the constant $\gamma$ and that
in order to deal with the time-varying dynamical system we will need a precise
estimate. The next lemma shows that for the state equations 21 we have, under
suitable assumptions, $\gamma\leq 5$.

###### Lemma A.3

Consider the linear, time invariant system of equations

$\displaystyle\widetilde{\bm{z}}_{t+1}=\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}\widetilde{\bm{z}}_{t}=\bm{A}\widetilde{\bm{z}}_{t},\quad
t\geq 0.$

Furthermore, assume that
$\alpha\leq\sigma_{\text{min}}\left({\cal{J}}_{0}\right)\leq\sigma_{\text{max}}\left({\cal{J}}_{0}\right)\leq\beta$
and suppose that the condition $\frac{\mu}{\eta}\geq 8\beta^{2}$ is satisfied.
Then there is a constant $\gamma\leq 5$ such that for all $t\geq 0$ it holds
that

$\left\|\widetilde{\bm{z}}_{t}\right\|_{\ell_{2}}\leq\gamma\left(1-\eta\alpha^{2}\right)^{t}\left\|\widetilde{\bm{z}}_{0}\right\|_{\ell_{2}}.$

Proof Denote the SVD decomposition of ${\cal{J}}_{0}$ by
$\bm{W}\bm{\Sigma}\bm{V}^{T}$ and note that

$\displaystyle\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\bm{W}&\bm{0}\\\
\bm{0}&\bm{W}\end{bmatrix}\begin{bmatrix}\bm{I}&-\eta\bm{\Sigma}\bm{\Sigma}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}\begin{bmatrix}\bm{W}^{T}&\bm{0}\\\
\bm{0}&\bm{W}^{T}.\end{bmatrix}$

This means we can write

$\displaystyle\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}$
$\displaystyle=\begin{bmatrix}\bm{W}&\bm{0}\\\
\bm{0}&\bm{W}\end{bmatrix}\bm{P}\begin{bmatrix}\bm{C}_{1}&&{\text{0}}\\\
&\ddots&\\\
{\text{0}}&&\bm{C}_{m}\end{bmatrix}\bm{P}^{T}\begin{bmatrix}\bm{W}^{T}&\bm{0}\\\
\bm{0}&\bm{W}^{T}\end{bmatrix},$

where $\bm{P}$ is a permutation matrix and the matrices $\bm{C}_{i}$ are of
the form $\bm{C}_{i}=\begin{bmatrix}1&-\eta\sigma_{i}^{2}\\\
\mu&\left(1-\mu\right)\end{bmatrix}$, for $1\leq i\leq m$, where the
$\sigma_{i}$’s denote the singular values of ${\cal{J}}_{0}$. Using this
decomposition we can deduce

$\displaystyle\left\|\widetilde{\bm{z}}_{t}\right\|_{\ell_{2}}$
$\displaystyle=\left\|\bm{A}^{t}\widetilde{\bm{z}}_{0}\right\|_{\ell_{2}}\leq\left\|\bm{A}^{t}\right\|\left\|\widetilde{\bm{z}}_{0}\right\|_{\ell_{2}}=\left(\underset{1\leq
i\leq
m}{\text{max}}\left\|\bm{C}_{i}^{t}\right\|\right)\left\|\widetilde{\bm{z}}_{0}\right\|_{\ell_{2}}.$

Now suppose that $\bm{V}_{i}\bm{D}_{i}\bm{V}_{i}^{-1}$ is the eigenvalue
decomposition of $\bm{C}_{i}$, where the columns of $\bm{V}_{i}$ contain the
eigenvectors and $\bm{D}_{i}$ is a diagonal matrix consisting of the
eigenvalues. (Note that it follows from our assumptions on $\mu$ and $\eta$
that the matrix $\bm{C}_{i}$ is diagonalizable.) We have

$\displaystyle\left\|\bm{C}_{i}^{t}\right\|=\left\|\bm{V}_{i}\bm{D}_{i}^{t}\bm{V}_{i}^{-1}\right\|\leq\left\|\bm{V}_{i}\right\|\left\|\bm{D}_{i}^{t}\right\|\left\|\bm{V}_{i}^{-1}\right\|=\kappa_{i}\cdot\rho\left(\bm{C}_{i}\right)^{t},$

where we defined
$\kappa_{i}:=\left\|\bm{V}_{i}\right\|\left\|\bm{V}_{i}^{-1}\right\|$. From
Lemma A.2 we know that the assumption $\frac{\mu}{\eta}\geq 4\beta^{2}$
results in $\rho\left(\bm{A}\right)\leq 1-\eta\alpha^{2}$. Therefore, defining
$\gamma:=\underset{1\leq i\leq m}{\text{max}}\kappa_{i}$ and noting
$\rho\left(\bm{A}\right)=\underset{1\leq i\leq
m}{\text{max}}\rho\left(\bm{C}_{i}\right)$, we obtain that

$\displaystyle\left\|\widetilde{\bm{z}}_{t}\right\|_{\ell_{2}}\leq\left(\underset{1\leq
i\leq
m}{\text{max}}\left\|\bm{C}_{i}^{t}\right\|\right)\left\|\widetilde{\bm{z}}_{0}\right\|_{\ell_{2}}\leq\gamma\left(1-\eta\alpha^{2}\right)^{t}\left\|\widetilde{\bm{z}}_{0}\right\|_{\ell_{2}}.$

In order to finish the proof we need to show that $\gamma\leq 5$. For that,
note that calculating the eigenvectors of $\bm{C_{i}}$ directly reveals that
we can represent this matrix as

$\displaystyle\bm{V}_{i}=\begin{bmatrix}\frac{1+\sqrt{1-4\frac{\eta\sigma_{i}^{2}}{\mu}}}{2}&\frac{1-\sqrt{1-4\frac{\eta\sigma_{i}^{2}}{\mu}}}{2}\\\
1&1\end{bmatrix}.$

Since
$\left\|\bm{V}_{i}\right\|=\sqrt{\lambda_{\text{max}}\left(\bm{V}_{i}\bm{V}_{i}^{T}\right)}$
and
$\left\|\bm{V}_{i}^{-1}\right\|=\sqrt{\lambda_{\text{min}}\left(\bm{V}_{i}\bm{V}_{i}^{T}\right)}$,
we calculate $\bm{V}_{i}\bm{V}_{i}^{T}$, which yields

$\displaystyle\bm{V}_{i}\bm{V}_{i}^{T}=\begin{bmatrix}1-2\frac{\eta\sigma_{i}^{2}}{\mu}&1\\\
1&2\end{bmatrix}.$

This representation allows us to directly calculate the two eigenvalues of
$\bm{V}_{i}\bm{V}_{i}^{T}$, which shows that

$\displaystyle\kappa_{i}$
$\displaystyle=\sqrt{\frac{\lambda_{\text{max}}\left(\bm{V}_{i}\bm{V}_{i}^{T}\right)}{\lambda_{\text{min}}\left(\bm{V}_{i}\bm{V}_{i}^{T}\right)}}$
$\displaystyle=\sqrt{\frac{3-2\frac{\eta\sigma_{i}^{2}}{\mu}+\sqrt{\left(1+2\frac{\eta\sigma_{i}^{2}}{\mu}\right)^{2}+4}}{3-2\frac{\eta\sigma_{i}^{2}}{\mu}-\sqrt{\left(1+2\frac{\eta\sigma_{i}^{2}}{\mu}\right)^{2}+4}}}$
$\displaystyle=\frac{3-2\frac{\eta\sigma_{i}^{2}}{\mu}+\sqrt{\left(1+2\frac{\eta\sigma_{i}^{2}}{\mu}\right)^{2}+4}}{2\sqrt{1-4\frac{\eta\sigma_{i}^{2}}{\mu}}}$
$\displaystyle\leq\frac{6}{2\sqrt{1-4\frac{\eta\sigma_{i}^{2}}{\mu}}}$
$\displaystyle<5,$

where the last inequality holds because of
$\frac{\eta\sigma_{i}^{2}}{\mu}\leq\frac{\eta\beta^{2}}{\mu}\leq\frac{1}{8}$.
Since $\gamma=\underset{1\leq i\leq m}{\max}\kappa_{i}$, this finishes the
proof. $\blacksquare$

Now that we have shown that the linearized iterates converge to the global
optima we turn our attention to showing that the nonlinear iterates 16 are
close to its linear counterpart 21. For that, we make the following
assumptions.

Assumption 1: The singular values of the Jacobian at initialization are
bounded from below

$\sigma_{\text{min}}\left({\cal{J}}\left(\bm{\theta}_{0}\right)\right)\geq\alpha$

for some positive constants $\alpha$ and $\beta$.

Assumption 2: In a neighborhood with radius $R$ around the initialization, the
Jacobian mapping associated with $f$ obeys

$\left\|{\cal{J}}\left(\bm{\theta}\right)\right\|\leq\beta$

for all $\bm{\theta}\in\mathcal{B}_{R}\left(\bm{\theta}_{0}\right)$, where
$\mathcal{B}_{R}\left(\bm{\theta}_{0}\right):=\\{\bm{\theta}\in\mathbb{R}^{p}:\left\|\bm{\theta}-\bm{\theta}_{0}\right\|_{\ell_{2}}\leq
R\\}$.

Assumption 3: In a neighborhood with radius $R$ around the initialization, the
spectral norm of the Jacobian varies no more than $\epsilon$ in the sense that

$\left\|{\cal{J}}\left(\bm{\theta}\right)-{\cal{J}}\left(\bm{\theta}_{0}\right)\right\|\leq\epsilon$

for all $\bm{\theta}\in\mathcal{B}_{R}\left(\bm{\theta}_{0}\right)$.

With these assumptions in place, we are ready to state the main theorem.

###### Theorem A.4

Consider the GDA updates for the min-max optimization problem 12

$\displaystyle\begin{bmatrix}\bm{d}_{t+1}\\\
\bm{\theta}_{t+1}\end{bmatrix}=\begin{bmatrix}\bm{d}_{t}+\mu\nabla_{\bm{d}}h(\bm{\theta}_{t},\bm{d}_{t})\\\
\bm{\theta}_{t}-\eta\nabla_{\bm{\theta}}h(\bm{\theta}_{t},\bm{d}_{t})\end{bmatrix}$
(22)

and consider the GDA updates of the linearized problem 21

$\displaystyle\begin{bmatrix}\widetilde{\bm{d}}_{t+1}\\\
\widetilde{\bm{\theta}}_{t+1}\end{bmatrix}=\begin{bmatrix}\widetilde{\bm{d}}_{t}+\mu\nabla_{\bm{d}}h_{\text{lin}}(\widetilde{\bm{\theta}}_{t},\widetilde{\bm{d}}_{t})\\\
\widetilde{\bm{\theta}}_{t}-\eta\nabla_{\bm{\theta}}h_{\text{lin}}(\widetilde{\bm{\theta}}_{t},\widetilde{\bm{d}}_{t})\end{bmatrix}.$
(23)

Set $\bm{z}_{t}:=\begin{bmatrix}\bm{r}_{t}\\\ \bm{d}_{t}\end{bmatrix}$ and
$\widetilde{\bm{z}}_{t}:=\begin{bmatrix}\widetilde{\bm{r}}_{t}\\\
\widetilde{\bm{d}}_{t}\end{bmatrix}$, where
$\bm{r}_{t}:=f\left(\bm{\theta}_{t}\right)-\bm{y}$ and
$\widetilde{\bm{r}}_{t}=f\left(\bm{\theta}_{0}\right)+{\cal{J}}_{0}\left(\widetilde{\bm{\theta}}_{t}-\bm{\theta}_{0}\right)-\bm{y}$
denote the residuals.
Assume that the step sizes of the gradient descent ascent updates satisfy
$\frac{\mu}{\eta}\geq 8\beta^{2}$ as well as $0<\mu\leq 1$. Moreover, assume
that the assumptions 1-3 hold for the Jacobian
${\cal{J}}\left(\bm{\theta}\right)$ of $f\left(\bm{\theta}\right)$ around the
initialization $\bm{\theta}_{0}\in\mathbb{R}^{n}$ with parameters $\alpha$,
$\beta$, $\epsilon$, and

$\displaystyle
R:=2\gamma\frac{\beta^{2}}{\alpha^{2}}\left\|\begin{bmatrix}{\cal{J}}_{0}^{\dagger}&0\\\
0&{\cal{J}}_{0}^{\dagger}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}+\frac{18\epsilon\beta^{2}\gamma^{2}}{\alpha^{4}}\left\|\bm{z}_{0}\right\|_{\ell_{2}},$
(24)

which satisfy $4\gamma\beta\epsilon\leq\alpha^{2}$. Here, $1\leq\gamma\leq 5$
is a constant, which only depends on $\mu$, $\eta$, and ${\cal{J}}_{0}$. By
${\cal{J}}_{0}^{\dagger}$ we denote the pseudo-inverse of the Jacobian at
initialization ${\cal{J}}_{0}$. Then, assuming the same initialization
$\bm{\theta}_{0}=\widetilde{\bm{\theta}}_{0}$,
$\bm{d}_{0}=\widetilde{\bm{d}}_{0}$ (and, hence,
$\bm{z}_{0}=\widetilde{\bm{z}}_{0}$), the following holds for all iterations
$t\geq 0$.

  * •

$\left\|\bm{z_{t}}\right\|_{\ell_{2}}$ converges to $0$ with a geometric rate,
i.e.

$\displaystyle\left\|\bm{z}_{t}\right\|_{\ell_{2}}\leq\gamma\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t}\left\|\bm{z}_{0}\right\|_{\ell_{2}}.$
(25)

  * •

The trajectories of $\bm{z}_{t}$ and $\widetilde{\bm{z}_{t}}$ stay close to
each other and converge to the same limit, i.e.

$\displaystyle\begin{split}\left\|\bm{z}_{t}-\widetilde{\bm{z}}_{t}\right\|_{\ell_{2}}&\leq
2\eta\gamma^{2}\beta\epsilon\cdot
t\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t-1}\left\|\bm{z}_{0}\right\|_{\ell_{2}}\\\
&\leq\frac{4\gamma^{2}\beta\epsilon}{e\left(15\ln\frac{16}{15}\right)\alpha^{2}}\left\|\bm{z}_{0}\right\|_{\ell_{2}}.\end{split}$
(26)

  * •

The parameters of the original and linearized problems stay close to each
other, i.e.

$\displaystyle\left\|\widetilde{\bm{\theta}}_{t}-\bm{\theta}_{t}\right\|_{\ell_{2}}\leq\frac{9\epsilon\beta^{2}\gamma^{2}}{\alpha^{4}}\left\|\bm{z}_{0}\right\|_{\ell_{2}},$
(27)

  * •

The parameters of the original problem stay close to the initialization, i.e.

$\displaystyle\left\|\bm{\theta}_{t}-\bm{\theta}_{0}\right\|_{\ell_{2}}\leq\frac{R}{2}.$
(28)

Theorem A.4 will be the main ingredient in the proof of Theorem 2.1. However,
as discussed in Section 2.4 we believe that this meta theorem can be used to
deal with a much richer class of generators and discriminators.

####  A.3.1 Proof of Theorem A.4

We will prove the statements in the theorem by induction. The base case for
$\tau=0$ is trivial. Now assume that the equations equation 25 to equation 28
hold for $\tau=0,\ldots,t-1$. Our goal is to show that they hold for iteration
$t$ as well.

Part I: First, we are going to show that
$\bm{\theta}_{t}\in\mathcal{B}_{R}\left(\bm{\theta}_{0}\right)$. Note that by
the triangle inequality and the induction assumption we have that

$\displaystyle\left\|\bm{\theta}_{t}-\bm{\theta}_{0}\right\|_{\ell_{2}}$
$\displaystyle\leq\left\|\bm{\theta}_{t}-\bm{\theta}_{t-1}\right\|_{\ell_{2}}+\left\|\bm{\theta}_{t-1}-\theta_{0}\right\|_{\ell_{2}}$
$\displaystyle\leq\left\|\bm{\theta}_{t}-\bm{\theta}_{t-1}\right\|_{\ell_{2}}+\frac{R}{2}.$

Hence, in order to prove the claim it remains to show that
$\left\|\bm{\theta}_{t}-\bm{\theta}_{t-1}\right\|_{\ell_{2}}\leq\frac{R}{2}$.
For that, we compute

$\displaystyle\frac{1}{\eta}\left\|\bm{\theta}_{t}-\bm{\theta}_{t-1}\right\|_{\ell_{2}}$
$\displaystyle=\left\|{\cal{J}}^{T}\left(\bm{\theta}_{t-1}\right)\bm{d}_{t-1}\right\|_{\ell_{2}}$
$\displaystyle\leq\left\|{\cal{J}}^{T}\left(\bm{\theta}_{t-1}\right)\widetilde{\bm{d}}_{t-1}\right\|_{\ell_{2}}+\left\|{\cal{J}}^{T}\left(\bm{\theta}_{t-1}\right)\right\|\left\|\bm{d}_{t-1}-\widetilde{\bm{d}}_{t-1}\right\|_{\ell_{2}}$
$\displaystyle\leq\left\|{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{t-1}\right\|_{\ell_{2}}+\left\|{\cal{J}}\left(\bm{\theta}_{t-1}\right)-{\cal{J}}_{0}\right\|\left\|\widetilde{\bm{d}}_{t-1}\right\|_{\ell_{2}}+\left\|{\cal{J}}^{T}\left(\bm{\theta}_{t-1}\right)\right\|\left\|\bm{d}_{t-1}-\widetilde{\bm{d}}_{t-1}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(i\right)}{\leq}\gamma\left\|\begin{bmatrix}{\cal{J}}_{0}^{T}&0\\\
0&{\cal{J}}_{0}^{T}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}+\epsilon\cdot\gamma\left\|\bm{z}_{0}\right\|_{\ell_{2}}+\frac{4\beta^{2}\epsilon\gamma^{2}}{e\left(15\ln\frac{16}{15}\right)\alpha^{2}}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(ii\right)}{\leq}\gamma\beta^{2}\left\|\begin{bmatrix}{\cal{J}}_{0}^{\dagger}&0\\\
0&{\cal{J}}_{0}^{\dagger}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}+\frac{3\beta^{2}\epsilon\gamma^{2}}{\alpha^{2}}\left\|\bm{z}_{0}\right\|_{\ell_{2}},$

where $\gamma\leq 5$ is a constant. Let us verify the last two inequalities.
Inequality $\left(ii\right)$ holds because $1\leq\gamma$,
$1\leq\frac{\beta^{2}}{\alpha^{2}}$, and

$\displaystyle\left\|\begin{bmatrix}{\cal{J}}_{0}^{T}&0\\\
0&{\cal{J}}_{0}^{T}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle=\left\|\begin{bmatrix}\bm{V}\bm{\Sigma}^{T}\bm{W}^{T}&0\\\
0&\bm{V}\bm{\Sigma}^{T}\bm{W}^{T}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle=\sqrt{\sum_{i=1}^{n}\sigma_{i}^{2}\left(\left\langle\bm{w}_{i},\bm{r}_{0}\right\rangle^{2}+\left\langle\bm{w}_{i},\bm{d}_{0}\right\rangle^{2}\right)}$
$\displaystyle\leq\beta^{2}\sqrt{\sum_{i=1}^{n}\frac{1}{\sigma_{i}^{2}}\left(\left\langle\bm{w}_{i},\bm{r}_{0}\right\rangle^{2}+\left\langle\bm{w}_{i},\bm{d}_{0}\right\rangle^{2}\right)}=\beta^{2}\left\|\begin{bmatrix}{\cal{J}}_{0}^{\dagger}&0\\\
0&{\cal{J}}_{0}^{\dagger}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}.$ (29)

Also $\left(i\right)$ follows from assumptions 1-3,
$\left\|\bm{d}_{t-1}-\widetilde{\bm{d}}_{t-1}\right\|_{\ell_{2}}\leq\left\|\bm{z}_{t-1}-\widetilde{\bm{z}}_{t-1}\right\|_{\ell_{2}}$
together with induction assumption equation 26,
$\left\|\widetilde{\bm{d}}_{t-1}\right\|_{\ell_{2}}\leq\left\|\widetilde{\bm{z}}_{t-1}\right\|_{\ell_{2}}\leq\left\|\bm{z}_{0}\right\|_{\ell_{2}}$,
and

$\displaystyle\left\|{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{t-1}\right\|_{\ell_{2}}$
$\displaystyle\leq\left\|\begin{bmatrix}{\cal{J}}_{0}^{T}\widetilde{\bm{r}}_{t-1}\\\
{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{t-1}\end{bmatrix}\right\|_{\ell_{2}}$
$\displaystyle=\left\|\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}^{T}{\cal{J}}_{0}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}\begin{bmatrix}{\cal{J}}_{0}^{T}\widetilde{\bm{r}}_{t-2}\\\
{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{t-2}\end{bmatrix}\right\|_{\ell_{2}}$
$\displaystyle=\left\|\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}^{T}{\cal{J}}_{0}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}^{t-1}\begin{bmatrix}{\cal{J}}_{0}^{T}\widetilde{\bm{r}}_{0}\\\
{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{0}\end{bmatrix}\right\|_{\ell_{2}}\leq\gamma\left(1-\eta\alpha^{2}\right)^{t-1}\left\|\begin{bmatrix}{\cal{J}}_{0}^{T}&0\\\
0&{\cal{J}}_{0}^{T}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}},$ (30)

where in the last inequality we applied Lemma A.3. Finally, by using
$\eta\leq\frac{1}{8\beta^{2}}$ we arrive at

$\displaystyle\left\|\bm{\theta}_{t}-\bm{\theta}_{t-1}\right\|_{\ell_{2}}$
$\displaystyle\leq\gamma\eta\beta^{2}\left\|\begin{bmatrix}{\cal{J}}_{0}^{\dagger}&0\\\
0&{\cal{J}}_{0}^{\dagger}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}+\frac{3\eta\beta^{2}\epsilon\gamma^{2}}{\alpha^{2}}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle\leq\frac{\gamma}{8}\left\|\begin{bmatrix}{\cal{J}}_{0}^{\dagger}&0\\\
0&{\cal{J}}_{0}^{\dagger}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}+\frac{3\epsilon\gamma^{2}}{8\alpha^{2}}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle\leq\frac{R}{2},$

where the last line is directly due to inequality (24), $\gamma\leq 5$, and
$\alpha\leq\beta$. Hence, we have established
$\bm{\theta}_{t}\in\mathcal{B}_{R}\left(\bm{\theta}_{0}\right)$.

Part II: In Lemma A.3 we showed that the time invariant system of state
equations $\widetilde{\bm{z}}_{t+1}=\bm{A}\widetilde{\bm{z}}_{t}$ is uniformly
exponentially stable, i.e. $\left\|\widetilde{\bm{z}_{t}}\right\|_{\ell_{2}}$
goes down to zero exponentially fast. Now by using the assumption that the
Jacobian remains close to the Jacobian at the initialization ${\cal{J}}_{0}$,
we aim to show the exponential stability of the time variant system of the
state equations 16. For that, we compute

$\displaystyle\bm{z}_{t}=\bm{A}_{t-1}\bm{z}_{t-1}$
$\displaystyle=\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{t,t-1}{\cal{J}}_{t-1}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}\bm{z}_{t-1}$
$\displaystyle=\begin{bmatrix}\bm{I}&-\eta{\cal{J}}_{0}{\cal{J}}_{0}^{T}\\\
\mu\bm{I}&\left(1-\mu\right)\bm{I}\end{bmatrix}\bm{z}_{t-1}+\begin{bmatrix}\eta\left({\cal{J}}_{0}{\cal{J}}_{0}^{T}-{\cal{J}}_{t,t-1}{\cal{J}}_{t-1}^{T}\right)\bm{d}_{t-1}\\\
\bm{0}\end{bmatrix}$ $\displaystyle=:\bm{A}\bm{z}_{t-1}+\bm{\Delta}_{t-1}.$

Now set $\lambda:=1-\eta\alpha^{2}$. By induction, we obtain the relation
$\bm{z}_{t}=\bm{A}^{t}\bm{z}_{0}+\sum_{i=0}^{t-1}\bm{A}^{t-1-i}\bm{\Delta}_{i}$.
Hence,

$\displaystyle\left\|\bm{z}_{t}\right\|_{\ell_{2}}$
$\displaystyle=\left\|\bm{A}^{t}\bm{z}_{0}+\sum_{i=0}^{t-1}\bm{A}^{t-1-i}\bm{\Delta}_{i}\right\|_{\ell_{2}}$
$\displaystyle\leq\left\|\bm{A}^{t}\bm{z}_{0}\right\|_{\ell_{2}}+\sum_{i=0}^{t-1}\left\|\bm{A}^{t-1-i}\bm{\Delta}_{i}\right\|_{\ell_{2}}$
$\displaystyle\leq\gamma\lambda^{t}\left\|\bm{z}_{0}\right\|_{\ell_{2}}+\sum_{i=0}^{t-1}\gamma\lambda^{t-1-i}\left\|\eta\left({\cal{J}}_{0}{\cal{J}}_{0}^{T}-{\cal{J}}_{i+1,i}{\cal{J}}_{i}^{T}\right)\right\|\left\|\bm{d}_{i}\right\|_{\ell_{2}}$
$\displaystyle\leq\gamma\lambda^{t}\left\|\bm{z}_{0}\right\|_{\ell_{2}}+\sum_{i=0}^{t-1}\eta\gamma\lambda^{t-1-i}\left(2\beta\epsilon\right)\left\|\bm{z}_{i}\right\|_{\ell_{2}}.$
(31)

The second inequality holds because of Lemma A.3. The last inequality holds
because by combining our assumptions 1 to 3 with
$\bm{\theta}_{t}\in\mathcal{B}_{R}\left(\bm{\theta}_{0}\right)$ and the
induction assumption 28 for $0\leq i\leq t-1$, we have that

$\displaystyle\left\|{\cal{J}}_{0}{\cal{J}}_{0}^{T}-{\cal{J}}_{i+1,i}{\cal{J}}_{i}^{T}\right\|$
$\displaystyle=\left\|{\cal{J}}_{0}{\cal{J}}_{0}^{T}-{\cal{J}}_{0}{\cal{J}}_{i}^{T}+{\cal{J}}_{0}{\cal{J}}_{i}^{T}-{\cal{J}}_{i+1,i}{\cal{J}}_{i}^{T}\right\|$
$\displaystyle\leq\left\|{\cal{J}}_{0}\right\|\left\|{\cal{J}}_{0}-{\cal{J}}_{i}\right\|+\left\|{\cal{J}}_{0}-{\cal{J}}_{i+1,i}\right\|\left\|{\cal{J}}_{i}\right\|$
$\displaystyle\leq\beta\left\|{\cal{J}}_{0}-{\cal{J}}_{i}\right\|+\beta\left\|{\cal{J}}_{0}-{\cal{J}}_{i+1,i}\right\|$
$\displaystyle\leq 2\beta\epsilon.$ (32)

In order to deal with inequality 31, we will rely on the following lemma.

###### Lemma A.5

(Rugh, 1996, Lemma 24.5) Consider two real sequences $p\left(t\right)$ and
$\phi\left(t\right)$, where $p\left(t\right)\geq 0$ for all $t\geq 0$ and

$\displaystyle\phi\left(t\right)\leq\begin{cases}\psi,&\text{if}\ t=0\\\
\psi+\eta\displaystyle\sum_{i=0}^{t-1}p\left(i\right)\phi\left(i\right),&\text{if}\
t\geq 1\end{cases}$

where $\eta$ and $\psi$ are constants with $\eta\geq 0$. Then for all $t\geq
1$ we have

$\displaystyle\phi\left(t\right)\leq\psi\displaystyle\prod_{i=0}^{t-1}\left(1+\eta\cdot
p\left(i\right)\right).$

Now we define
$\phi_{t}=\frac{\left\|\bm{z}_{t}\right\|_{\ell_{2}}}{\lambda^{t}}$ and
rewrite inequality 31 as

$\displaystyle\phi_{t}\leq\gamma\phi_{0}+\sum_{i=0}^{t-1}\frac{2\eta\gamma\beta\epsilon}{\lambda}\phi_{i}.$

Hence, Lemma A.5 yields that

$\displaystyle\phi_{t}$
$\displaystyle\leq\gamma\phi_{0}\prod_{i=0}^{t-1}\left(1+\frac{2\eta\gamma\beta\epsilon}{\lambda}\right)$
$\displaystyle=\gamma\phi_{0}\left(1+\frac{2\eta\gamma\beta\epsilon}{\lambda}\right)^{t}$
$\displaystyle\overset{\left(i\right)}{\leq}\gamma\phi_{0}\left(1+\frac{\eta\alpha^{2}}{2\lambda}\right)^{t}$
$\displaystyle\overset{\left(ii\right)}{=}\gamma\phi_{0}\left(\frac{1-\frac{\eta\alpha^{2}}{2}}{1-\eta\alpha^{2}}\right)^{t},$

where $\left(i\right)$ follows from $4\gamma\beta\epsilon\leq\alpha^{2}$ and
$\left(ii\right)$ holds by inserting $\lambda=1-\eta\alpha^{2}$. Inserting the
definition of $\phi_{0}$ and $\phi_{t}$ we obtain that

$\displaystyle\left\|\bm{z}_{t}\right\|_{\ell_{2}}\leq\gamma\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t}\left\|\bm{z}_{0}\right\|_{\ell_{2}}.$

This completes the proof of Part II.

Part III: In this part, our aim is to show that the error vector
$\bm{e}_{t}:=\bm{z}_{t}-\widetilde{\bm{z}}_{t}$ obeys inequality 26. First,
note that

$\displaystyle\bm{e}_{t}$ $\displaystyle=\bm{z}_{t}-\widetilde{\bm{z}}_{t}$
$\displaystyle\overset{\left(*\right)}{=}\left(\bm{A}\bm{z}_{t-1}+\bm{\Delta}_{t-1}\right)-\bm{A}\widetilde{\bm{z}}_{t-1}$
$\displaystyle=\bm{A}\bm{e}_{t-1}+\bm{\Delta}_{t-1},$

where in $\left(*\right)$ we used the same notation as in Part II for
$\bm{\Delta}_{t-1}$. Using a recursive argument as well as $\bm{e}_{0}=0$ we
obtain that

$\displaystyle\left\|\bm{e}_{t}\right\|_{\ell_{2}}$
$\displaystyle=\left\|\sum_{i=0}^{t-1}\bm{A}^{t-1-i}\bm{\Delta}_{i}\right\|_{\ell_{2}}$
$\displaystyle\leq\sum_{i=0}^{t-1}\eta\gamma\left(1-\eta\alpha^{2}\right)^{t-1-i}\left\|\bm{\Delta}_{i}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(i\right)}{\leq}\sum_{i=0}^{t-1}\eta\gamma\left(1-\eta\alpha^{2}\right)^{t-1-i}\left\|{\cal{J}}_{0}{\cal{J}}_{0}^{T}-{\cal{J}}_{i+1,i}{\cal{J}}_{i}^{T}\right\|\left\|\bm{d}_{i}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(ii\right)}{\leq}\sum_{i=0}^{t-1}2\eta\beta\epsilon\gamma\left(1-\eta\alpha^{2}\right)^{t-1-i}\left\|\bm{z}_{i}\right\|_{\ell_{2}}.$

The first inequality follows from the triangle inequality and Lemma A.3.
Inequality $\left(i\right)$ follows from the definition of $\bm{\Delta}_{i}$.
Inequality $(ii)$ follows from inequality 32. Setting $c:=2\eta\beta\epsilon$
we continue

$\displaystyle\left\|\bm{e}_{t}\right\|_{\ell_{2}}$
$\displaystyle\leq\sum_{i=0}^{t-1}c\gamma\left(1-\eta\alpha^{2}\right)^{t-i-1}\left\|\bm{z}_{i}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(iii\right)}{\leq}\sum_{i=0}^{t-1}c\gamma^{2}\left(1-\eta\alpha^{2}\right)^{t-i-1}\left(1-\frac{\eta\alpha^{2}}{2}\right)^{i}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(iv\right)}{\leq}\sum_{i=0}^{t-1}c\gamma^{2}\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t-1}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle=2\eta\gamma^{2}\beta\epsilon\cdot
t\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t-1}\left\|\bm{z}_{0}\right\|_{\ell_{2}}.$

Here $\left(iii\right)$ holds because of our induction hypothesis 25 and
$\left(iv\right)$ follows simply from $1-\eta\alpha^{2}\leq
1-\frac{\eta\alpha^{2}}{2}$. This shows the first part of equation 26 for
iteration t. Finally, to derive the second part of equation 26 we observe that
for all $t\geq 0$ and $0<x\leq\frac{1}{16}$ we have
$t\left(1-x\right)^{t-1}\leq\frac{1}{e\left(15\ln\frac{16}{15}\right)x}$.
Since
$\frac{\eta\alpha^{2}}{2}\leq\frac{\mu\alpha^{2}}{16\beta^{2}}\leq\frac{1}{16}$
we can use this estimate, which yields

$\displaystyle\left\|\bm{e}_{t}\right\|_{\ell_{2}}$ $\displaystyle\leq
2\eta\gamma^{2}\beta\epsilon\cdot
t\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t-1}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle\leq\frac{4\gamma^{2}\beta\epsilon}{e\left(15\ln\frac{16}{15}\right)\alpha^{2}}\left\|\bm{z}_{0}\right\|_{\ell_{2}}.$

Hence, we have shown equation 26.

Part IV: In this part, we aim to show that the parameters of the original and
linearized problems are close. For that, we compute that

$\displaystyle\frac{1}{\eta}\left\|\bm{\theta}_{t}-\widetilde{\bm{\theta}}_{t}\right\|_{\ell_{2}}$
$\displaystyle=\left\|\sum_{i=0}^{t-1}\nabla_{\bm{\theta}}h\left(\bm{\theta}_{i},\bm{d}_{i}\right)-\nabla_{\bm{\theta}}h_{\text{lin}}\left(\bm{\theta}_{i},\bm{d}_{i}\right)\right\|_{\ell_{2}}$
$\displaystyle=\left\|\sum_{i=0}^{t-1}{\cal{J}}^{T}\left(\bm{\theta}_{i}\right)\bm{d}_{i}-{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{i}\right\|_{\ell_{2}}$
$\displaystyle\leq\sum_{i=0}^{t-1}\left\|\left({\cal{J}}^{T}\left(\bm{\theta}_{i}\right)-{\cal{J}}_{0}^{T}\right)\widetilde{\bm{d}}_{i}\right\|_{\ell_{2}}+\sum_{i=0}^{t-1}\left\|{\cal{J}}^{T}\left(\bm{\theta}_{i}\right)\left(\bm{d}_{i}-\widetilde{\bm{d}}_{i}\right)\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(i\right)}{\leq}\sum_{i=0}^{t-1}\epsilon\left\|\widetilde{\bm{z}}_{i}\right\|_{\ell_{2}}+\beta\sum_{i=0}^{t-1}\left\|\bm{e}_{i}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(ii\right)}{\leq}\gamma\epsilon\sum_{i=0}^{t-1}\left(1-\eta\alpha^{2}\right)^{i}\left\|\bm{z}_{0}\right\|_{\ell_{2}}+2\eta\gamma^{2}\beta^{2}\epsilon\sum_{i=0}^{t-1}i\left(1-\frac{\eta\alpha^{2}}{2}\right)^{i-1}\left\|\bm{z}_{0}\right\|_{\ell_{2}}.$

Here $\left(i\right)$ follows from assumptions 2 and 3, and $\left(ii\right)$
holds because of Lemma A.3 and our induction hypothesis 26. Hence, using the
formula
$\sum_{i=0}^{t}ix^{i}=\frac{x\left(1+tx^{t+1}-\left(t+1\right)x^{t}\right)}{\left(x-1\right)^{2}}$
we obtain that

$\displaystyle\frac{1}{\eta}\left\|\bm{\theta}_{t}-\widetilde{\bm{\theta}}_{t}\right\|_{\ell_{2}}$
$\displaystyle\leq\gamma\epsilon\left\|\bm{z}_{0}\right\|_{\ell_{2}}\left(\frac{1-\left(1-\eta\alpha^{2}\right)^{t}}{\eta\alpha^{2}}+2\eta\beta^{2}\gamma\frac{1-t\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t-1}+\left(t-1\right)\left(1-\frac{\eta\alpha^{2}}{2}\right)^{t}}{\left(\frac{\eta\alpha^{2}}{2}\right)^{2}}\right)$
$\displaystyle\leq\gamma\epsilon\left\|\bm{z}_{0}\right\|_{\ell_{2}}\left(\frac{1}{\eta\alpha^{2}}+2\eta\beta^{2}\gamma\frac{1}{\left(\frac{\eta\alpha^{2}}{2}\right)^{2}}\right)$
$\displaystyle\overset{\left(iii\right)}{\leq}\gamma\epsilon\left\|\bm{z}_{0}\right\|_{\ell_{2}}\left(\frac{\beta^{2}\gamma}{\eta\alpha^{4}}+\frac{8\beta^{2}\gamma}{\eta\alpha^{4}}\right)$
$\displaystyle=\frac{9\epsilon\beta^{2}\gamma^{2}}{\eta\alpha^{4}}\left\|\bm{z}_{0}\right\|_{\ell_{2}},$

where $\left(iii\right)$ holds due to $1\leq\gamma$ and
$1\leq\frac{\beta^{2}}{\alpha^{2}}$. Hence, we have established inequality 27
for iteration $t$.

Part V: In this part, we are going to prove equation 28 for iteration $t$.
First, it follows from the triangle inequality that

$\displaystyle\left\|\bm{\theta}_{t}-\bm{\theta}_{0}\right\|_{\ell_{2}}$
$\displaystyle\leq\left\|\widetilde{\bm{\theta}}_{t}-\bm{\theta}_{0}\right\|_{\ell_{2}}+\left\|\bm{\theta}_{t}-\widetilde{\bm{\theta}}_{t}\right\|_{\ell_{2}}$
$\displaystyle\leq\left\|\widetilde{\bm{\theta}}_{t}-\bm{\theta}_{0}\right\|_{\ell_{2}}+\frac{9\epsilon\beta^{2}\gamma^{2}}{\alpha^{4}}\left\|\bm{z}_{0}\right\|_{\ell_{2}},$

where in the second inequality we have used Part IV. Now we bound
$\left\|\widetilde{\bm{\theta}}_{t}-\bm{\theta}_{0}\right\|_{\ell_{2}}$ from
above as follows

$\displaystyle\left\|\widetilde{\bm{\theta}}_{t}-\bm{\theta}_{0}\right\|_{\ell_{2}}$
$\displaystyle=\eta\left\|\sum_{i=0}^{t-1}{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{i}\right\|_{\ell_{2}}$
$\displaystyle\leq\eta\sum_{i=0}^{t-1}\left\|{\cal{J}}_{0}^{T}\widetilde{\bm{d}}_{i}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(i\right)}{\leq}\eta\gamma\sum_{i=0}^{t-1}\left(1-\eta\alpha^{2}\right)^{i}\left\|\begin{bmatrix}{\cal{J}}_{0}^{T}&0\\\
0&{\cal{J}}_{0}^{T}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle=\eta\gamma\frac{1-\left(1-\eta\alpha^{2}\right)^{t}}{\eta\alpha^{2}}\left\|\begin{bmatrix}{\cal{J}}_{0}^{T}&0\\\
0&{\cal{J}}_{0}^{T}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(ii\right)}{\leq}\gamma\frac{\beta^{2}}{\alpha^{2}}\left\|\begin{bmatrix}{\cal{J}}_{0}^{\dagger}&0\\\
0&{\cal{J}}_{0}^{\dagger}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}},$

where $\left(i\right)$ holds by equation 30 and $\left(ii\right)$ holds by
equation 29. Hence, it follows from the definition of $R$ (equation 24) that

$\displaystyle\left\|\bm{\theta}_{t}-\bm{\theta}_{0}\right\|_{\ell_{2}}$
$\displaystyle\leq\gamma\frac{\beta^{2}}{\alpha^{2}}\left\|\begin{bmatrix}{\cal{J}}_{0}^{\dagger}&0\\\
0&{\cal{J}}_{0}^{\dagger}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}+\frac{9\epsilon\beta^{2}\gamma^{2}}{\alpha^{4}}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle=\frac{R}{2}.$

This completes the proof.

###  A.4 preliminaries for proofs of results with one-hidden layer generator
and linear discriminator

In this section, we gather some preliminary results that will be useful in
proving the main results i.e. Theorems 2.1 and 2.2. We begin by noting that
Theorem 2.1 is an instance of Theorem A.4 with
$f\left(\bm{W}\right)=\frac{1}{n}\sum_{i=1}^{n}\bm{V}\cdot\phi\left(\bm{W}\bm{z}_{i}\right)$.
We thus begin this section by noting that $f\left(\bm{W}\right)$ can be
rewritten as follows

$f\left(\bm{W}\right)=\bm{V}\cdot\begin{bmatrix}\frac{1}{n}\sum_{i=1}^{n}\phi\left(\bm{w}_{1}^{T}\bm{z}_{i}\right)\\\
.\\\ .\\\ .\\\
\frac{1}{n}\sum_{i=1}^{n}\phi\left(\bm{w}_{k}^{T}\bm{z}_{i}\right)\end{bmatrix}.$

Furthermore, the Jacobian of this mapping $f\left(\bm{W}\right)$ takes the
form

${\cal{J}}(\bm{W})=\frac{1}{n}\sum_{i=1}^{n}\left(\bm{V}\cdot\text{diag}\left(\phi^{\prime}\left(\bm{W}\bm{z}_{i}\right)\right)\right)\otimes\bm{z}_{i}^{T}.$
(33)

To characterize the spectral properties of this Jacobian it will be convenient
to write down the expression for ${\cal{J}}(\bm{W}){\cal{J}}(\bm{W})^{T}$
which has a compact form

$\displaystyle{\cal{J}}(\bm{W}){\cal{J}}(\bm{W})^{T}$
$\displaystyle\overset{(i)}{=}\frac{1}{n^{2}}\sum_{i,j=1}^{n}\Big{(}\left(\bm{V}\cdot\text{diag}\left(\phi^{\prime}\left(\bm{W}\bm{z}_{i}\right)\right)\right)\otimes\bm{z}_{i}^{T}\Big{)}\Big{(}\text{diag}\left(\phi^{\prime}\left(\bm{W}\bm{z}_{j}\right)\right)\bm{V}^{T}\otimes\bm{z}_{j}\Big{)}$
$\displaystyle\overset{(ii)}{=}\frac{1}{n^{2}}\sum_{i,j=1}^{n}\Big{(}\bm{V}\text{diag}\left(\phi^{\prime}\left(\bm{W}\bm{z}_{i}\right)\right)\text{diag}\left(\phi^{\prime}\left(\bm{W}\bm{z}_{j}\right)\right)\bm{V}^{T}\Big{)}\otimes\Big{(}\bm{z}_{i}^{T}\bm{z}_{j}\Big{)}$
$\displaystyle=\frac{1}{n^{2}}\bm{V}\underset{\ell=1,\ldots,k}{\text{diag}}\left(\left\|\sum_{i=1}^{n}\bm{z}_{i}\phi^{\prime}\left(\bm{w}_{\ell}^{T}\bm{z}_{i}\right)\right\|_{\ell_{2}}^{2}\right)\bm{V}^{T}$
$\displaystyle=\frac{1}{n^{2}}\bm{V}\cdot\bm{D}^{2}\cdot\bm{V}^{T},$

where $\bm{D}$ is a diagonal matrix with entries

$D_{\ell\ell}=\left\|\sum_{i=1}^{n}\bm{z}_{i}\phi^{\prime}(\bm{w}_{\ell}^{T}\bm{z}_{i})\right\|_{\ell_{2}}=\left\|\bm{Z}^{T}\phi^{\prime}(\bm{Z}\bm{w}_{\ell})\right\|_{\ell_{2}},$
(34)

and $\bm{Z}\in\mathbb{R}^{n\times d}$ contains the $\bm{z}_{i}$’s in its rows.
Note that we used simple properties of kronecker product in (i) and (ii),
namely $(A\otimes B)^{T}=A^{T}\otimes B^{T}$ and $(A\otimes B)(C\otimes
D)=(AC)\otimes(BD)$. The next lemma establishes concentration of the diagonal
entries of matrix $\bm{D}^{2}$ around their mean, which will be used in the
future lemmas regarding the spectrum of the Jacobian mapping. The proof is
deferred to Appendix B.1.

###### Lemma A.6

Suppose $\bm{w}\in\mathbb{R}^{d}$ is a fixed vector,
$\bm{z}_{1},\bm{z}_{2},\cdots,\bm{z}_{n}\in\mathbb{R}^{d}$ are distributed as
$\mathcal{N}(0,\sigma_{z}^{2}\bm{I}_{d})$ and constitute the rows of
$\bm{Z}\in\mathbb{R}^{n\times d}$. Then for any $0\leq\delta\leq\frac{3}{2}$
the random variable
$D=\left\|\bm{Z}^{T}\phi^{\prime}\left(\bm{Z}\bm{w}\right)\right\|_{\ell_{2}}$
satisfies

$\left(1-\delta\right)\mathbb{E}\left(D^{2}\right)\leq
D^{2}\leq\left(1+\delta\right)\mathbb{E}\left(D^{2}\right)$

with probability at least
$1-2\left(e^{-\frac{n\delta^{2}}{18}}+e^{-\frac{d\delta^{2}}{54}}+e^{-c_{1}n\delta}\right)$
where $c_{1}$ is a positive constant. Moreover we have

$\mathbb{E}\left(D^{2}\right)=\sigma_{z}^{2}\left(\frac{nd}{2}+\frac{n(n-1)}{2\pi}\right).$

Furthermore, using the above equation we have

$\mathbb{E}\left[{\cal{J}}(\bm{W}){\cal{J}}(\bm{W})^{T}\right]=\frac{\sigma_{z}^{2}\left(d+\frac{n-1}{\pi}\right)}{2n}\bm{V}\bm{V}^{T}.$

###  A.5 Lemmas regarding the initial misfit and the spectrum of the Jacobian

In this section, we state some lemmas regarding the spectrum of the Jacobian
mapping and the initial misfit, and defer their proofs to Appendix B. First,
we state a result on the minimum singular value of the Jacobian mapping at
initialization.

###### Lemma A.7

(Minimum singular value of the Jacobian at initialization) Consider our GAN
model with a linear discriminator and the generator being a one hidden layer
neural network of the form $\bm{z}\rightarrowtail\bm{V}\phi(\bm{W}z)$, where
we have n independent data points
$\bm{z}_{1},\bm{z}_{2},\cdots,\bm{z}_{n}\in\mathbb{R}^{d}$ distributed as
$\mathcal{N}(0,\sigma_{z}^{2}\bm{I}_{d})$ and aggregated as the rows of a
matrix $\bm{Z}\in\mathbb{R}^{n\times d}$, and $\bm{V}\in\mathbb{R}^{m\times
k}$ has i.i.d $\mathcal{N}(0,\sigma_{v}^{2})$ entries. We also assume that
$\bm{W}_{0}\in\mathbb{R}^{k\times d}$ has i.i.d
$\mathcal{N}(0,\sigma_{w}^{2})$ entries and all entries of $\bm{W}_{0}$,
$\bm{V}$, and $\bm{Z}$ are independent. Then the Jacobian matrix at the
initialization point obeys

$\begin{split}\sigma_{min}\left({\cal{J}}(\bm{W}_{0})\right)\geq\left(\sqrt{\left(1-\delta\right)^{2}k-\left(1+\delta\right)^{2}}-\sqrt{m}\left(1+\eta\right)\left(1+\delta\right)\right)\sigma_{v}\sigma_{z}\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}},~{}~{}~{}0\leq\delta\leq\frac{3}{2}\end{split}$

with probability at least
$1-3e^{-\frac{\eta^{2}m}{8}}-2k\cdot\left(e^{-\frac{n\delta^{2}}{18}}+e^{-\frac{d\delta^{2}}{54}}+e^{-c_{1}n\delta}\right)$,
where $c_{1}$ is a positive constant.

Next lemma helps us bound the spectral norm of the Jacobian at initialization,
which will be used later to derive upper bounds on Jacobian at every point
near initialization.

###### Lemma A.8

(spectral norm of the Jacobian at initialization) Following the setup of
previous lemma, the operator norm of the Jacobian matrix at initialization
point $\bm{W}_{0}\in\mathbb{R}^{k\times d}$ satisfies

$\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|\leq\left(1+\delta\right)\sigma_{v}\sigma_{z}\left(\sqrt{k}+2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}},~{}~{}~{}~{}~{}~{}0\leq\delta\leq\frac{3}{2}$

with probability at least
$1-e^{-\frac{m}{2}}-k\cdot\left(e^{-\frac{n\delta^{2}}{18}}+e^{-\frac{d\delta^{2}}{54}}+e^{-c_{1}n\delta}\right)$,
with $c_{1}$ a positive constant.

The next lemma is adapted from Van Veen et al. (2018) and allows us to bound
the variations in the Jacobian matrix around initialization.

###### Lemma A.9

(single-sample Jacobian perturbation) Let $\bm{V}\in\mathbb{R}^{m\times k}$ be
a matrix with i.i.d. $\mathcal{N}\left(0,\sigma_{v}^{2}\right)$ entries,
$\bm{W}\in\mathbb{R}^{k\times d}$, and define the Jacobian mapping
${\cal{J}}(\bm{W};z)=\left(\bm{V}\text{diag}\left(\phi^{\prime}\left(\bm{W}z\right)\right)\right)\otimes
z^{T}$. Then, by taking $\bm{W}_{0}$ to be a random matrix with i.i.d.
$\mathcal{N}\left(0,\sigma_{w}^{2}\right)$ entries, we have

$\left\|{\cal{J}}(\bm{W};z)-{\cal{J}}(\bm{W}_{0};z)\right\|\leq\sigma_{v}\left\|z\right\|_{\ell_{2}}\left(2\sqrt{m}+\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\right)$

for all $\bm{W}\in\mathbb{R}^{k\times d}$ obeying
$\left\|\bm{W}-\bm{W}_{0}\right\|\leq R$ with probability at least
$1-e^{-\frac{m}{2}}-e^{-\frac{\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}{6}}$.

Our final key lemma bounds the initial misfit
$f(\bm{W}_{0})-\bm{y}:=\frac{1}{n}\sum_{i=1}^{n}\bm{V}\phi\left(\bm{W}_{0}\bm{z_{i}}\right)-\bm{\bar{x}}$.

###### Lemma A.10

(Initial misfit) Consider our GAN model with a linear discriminator and the
generator being a one hidden layer neural network of the form
$\bm{z}\rightarrowtail\bm{V}\phi(\bm{W}z)$, where we have n independent data
points $\bm{z}_{1},\bm{z}_{2},\cdots,\bm{z}_{n}\in\mathbb{R}^{d}$ distributed
as $\mathcal{N}(0,\sigma_{z}^{2}\bm{I}_{d})$ and aggregated as the rows of a
matrix $\bm{Z}\in\mathbb{R}^{n\times d}$, and $\bm{V}\in\mathbb{R}^{m\times
k}$ has i.i.d $\mathcal{N}(0,\sigma_{v}^{2})$ entries. We also assume that the
initial $\bm{W}_{0}\in\mathbb{R}^{k\times d}$ has i.i.d
$\mathcal{N}(0,\sigma_{w}^{2})$ entries. Then the following event

$\left\|\frac{1}{n}\sum_{i=1}^{n}\bm{V}\phi\left(\bm{W}_{0}\bm{z_{i}}\right)-\bm{\bar{x}}\right\|_{\ell_{2}}\leq(1+\delta)\frac{1}{\sqrt{2\pi}}\sigma_{v}\sigma_{w}\sigma_{z}\sqrt{kdm}+\left\|\bm{\bar{x}}\right\|_{\ell_{2}},~{}~{}~{}0\leq\delta\leq
3$

holds with probability at least $1-\left(k\cdot
e^{-c_{2}n\left(\delta/27\right)^{2}}+e^{-\frac{\left(\delta/9\right)^{2}m}{2}}+e^{-\frac{\left(\delta/3\right)^{2}kd}{2}}\right)$,
with $c_{2}$ a fixed constant.

###  A.6 Proof of Theorem 2.1

In this section, we prove Theorem 2.1 by using our general meta Theorem A.4.
To do this we need to check that Assumptions 1-3 are satisfied with high
probability. Specifically, in our case the parameter $\bm{\theta}$ is the
matrix $\bm{W}$ and the non-linear mapping $f$ is given by
$f\left(\bm{W}\right)=\frac{1}{n}\sum_{i=1}^{n}\bm{V}\phi\left(\bm{W}\bm{z_{i}}\right)$.
We note that in our result $\bm{d}_{0}=\bm{0}$ and thus
$\left\|\bm{z}_{0}\right\|_{\ell_{2}}=\left\|\bm{r}_{0}\right\|_{\ell_{2}}$,
which simplifies our analysis.
To prove Assumption 1 note that by setting $\delta=\frac{1}{2}$ and
$\eta=\frac{1}{3}$ in Lemma A.7, we have

$\displaystyle\sigma_{\text{min}}\left({\cal{J}}\left(\bm{W}_{0}\right)\right)$
$\displaystyle\geq\sigma_{v}\sigma_{z}\left(\frac{1}{2}\sqrt{k-9}-2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}$
$\displaystyle=:\alpha.$

This holds with probability at least $1-3e^{-\frac{m}{72}}-4k\cdot e^{-c\cdot
n}-2k\cdot e^{-\frac{d}{216}}$, concluding the proof of Assumption 1. Next, by
setting $\delta=\frac{1}{2}$ in Lemma A.8 we have

$\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|\leq\zeta:=\frac{3}{2}\sigma_{v}\sigma_{z}\left(\sqrt{k}+2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}$

with probability at least $1-e^{-\frac{m}{2}}-2k\cdot e^{-c\cdot n}-k\cdot
e^{-\frac{d}{216}}$. Now to bound spectral norm of Jacobian at $\bm{W}$ where
$\left\|\bm{W}-\bm{W}_{0}\right\|\leq R$ (the value of R is defined in the
proof of assumption 3 below), we use triangle inequality to get

$\left\|{\cal{J}}\left(\bm{W}\right)\right\|\leq\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|+\left\|{\cal{J}}\left(\bm{W}\right)-{\cal{J}}\left(\bm{W}_{0}\right)\right\|.$

This last inequality together with assumption 3, which we will prove below,
yields

$\left\|{\cal{J}}\left(\bm{W}\right)\right\|\leq\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|+\epsilon\leq\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|+\frac{\alpha^{2}}{4\gamma\beta}\leq\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|+\frac{\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|^{2}}{4\beta}.$

Therefore by choosing $\beta=2\zeta$ we arrive at

$\displaystyle\left\|{\cal{J}}\left(\bm{W}\right)\right\|$
$\displaystyle\leq\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|+\frac{\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|^{2}}{4\beta}$
$\displaystyle=\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|+\frac{\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|^{2}}{8\zeta}$
$\displaystyle\leq\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|+\frac{\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|^{2}}{8\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|}$
$\displaystyle\leq 2\left\|{\cal{J}}\left(\bm{W}_{0}\right)\right\|$
$\displaystyle\leq 2\zeta=\beta,$

establishing that assumption 2 holds with

$\beta=3\sigma_{v}\sigma_{z}\left(\sqrt{k}+2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}$

with probability at least $1-e^{-\frac{m}{2}}-2k\cdot e^{-c\cdot n}-k\cdot
e^{-\frac{d}{216}}$.

Finally to show that Assumption 3 holds, we use the single-sample Jacobian
perturbation result of Lemma A.9 combined with the triangle inequality to
conclude that

$\displaystyle\left\|{\cal{J}}\left(\bm{W}\right)-{\cal{J}}\left(\bm{W}_{0}\right)\right\|$
$\displaystyle=\left\|\frac{1}{n}\left(\sum_{i=1}^{n}{\cal{J}}\left(\bm{W};z_{i}\right)-{\cal{J}}\left(\bm{W}_{0};z_{i}\right)\right)\right\|$
$\displaystyle\leq\frac{1}{n}\sum_{i=1}^{n}\left\|{\cal{J}}\left(\bm{W};z_{i}\right)-{\cal{J}}\left(\bm{W}_{0};z_{i}\right)\right\|$
$\displaystyle\leq\frac{\sigma_{v}}{n}\left(\sum_{i=1}^{n}\left\|z_{i}\right\|_{\ell_{2}}\right)\left(2\sqrt{m}+\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\right)$
$\displaystyle\overset{(i)}{\leq}\sigma_{v}\frac{\left\|\bm{Z}\right\|_{F}}{\sqrt{n}}\left(2\sqrt{m}+\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\right)$
$\displaystyle\overset{(ii)}{\leq}\frac{5}{4}\sigma_{v}\sigma_{z}\sqrt{d}\left(2\sqrt{m}+\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\right),$
(35)

where $\left(i\right)$ holds by Cauchy–Schwarz inequality, and
$\left(ii\right)$ holds because for a Gaussian matrix
$\bm{Z}\in\mathbb{R}^{n\times d}$ with $\mathcal{N}(0,\sigma_{z}^{2})$ entries
the following holds

$\displaystyle\mathbb{P}\left(\left\|\bm{Z}\right\|_{F}\leq\frac{5}{4}\sigma_{z}\sqrt{nd}\right)\geq\mathbb{P}\left(\left\|\bm{Z}\right\|_{F}^{2}\leq\frac{3}{2}\sigma_{z}^{2}nd\right)\geq
1-e^{-\frac{nd}{24}}.$

Now we set $\epsilon=\frac{\alpha^{2}}{4\gamma\beta}$ and show that Assumption
3 holds with this choice of $\epsilon$ and with radius $\widetilde{R}$, whose
value will be defined later in the proof. First, note that

$\displaystyle\epsilon$ $\displaystyle=\frac{\alpha^{2}}{4\gamma\beta}$
$\displaystyle=\frac{\sigma_{v}^{2}\sigma_{z}^{2}\left(\frac{1}{2}\sqrt{k-9}-2\sqrt{m}\right)^{2}\left(\frac{d+\frac{n-1}{\pi}}{2n}\right)}{12\gamma\sigma_{v}\sigma_{z}\left(\sqrt{k}+2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}}$
$\displaystyle\overset{\left(i\right)}{\geq}\frac{\sigma_{v}\sigma_{z}\left(\frac{1}{8}\sqrt{k}\right)^{2}\cdot\sqrt{\frac{1}{4\pi}}}{60\left(3\sqrt{k}\right)}$
$\displaystyle\geq\frac{\sigma_{v}\sigma_{z}\sqrt{k}}{42000},$

where $\left(i\right)$ holds by assuming $k\geq C\cdot m$ with $C$ being a
large positive constant. Combining the last inequality with equation 35, we
observe that a sufficient condition for assumption 3 to hold is

$\displaystyle\frac{5}{4}\sigma_{v}\sigma_{z}\sqrt{d}\left(2\sqrt{m}+\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\right)\leq\frac{\sigma_{v}\sigma_{z}\sqrt{k}}{42000},$

which is equivalent to

$\displaystyle
105000\sqrt{md}+52500\cdot\sqrt{d}\cdot\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\leq\sqrt{k}.$

Now the first term in the L.H.S. is upper bounded by $\frac{1}{2}\sqrt{k}$ if
$k\geq\left(210000\right)^{2}md$, and for the second term we need

$\displaystyle
105000\cdot\sqrt{d}\cdot\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\leq\sqrt{k},$

which by defining
$x=3d\left(\frac{2R}{\sigma_{w}\sqrt{k}}\right)^{\frac{2}{3}}$ is equivalent
to

$\displaystyle x\log\frac{d}{x}\leq\frac{1}{2\cdot 105000^{2}}.$

This last inequality holds for $x\leq\frac{c}{\log d}$ with $c<1$ a
sufficiently small positive constant, which translates into

$\displaystyle R\leq c\frac{\sigma_{w}\sqrt{k}}{\left(d\log
d\right)^{\frac{3}{2}}}.$ (36)

So far we have shown that Assumption 3 holds with
$\epsilon=\frac{\alpha^{2}}{4\gamma\beta}$ and with radius $\widetilde{R}$
defined as $\widetilde{R}:=c\frac{\sigma_{w}\sqrt{k}}{\left(d\log
d\right)^{\frac{3}{2}}}$, and we conclude that it holds for any radius $R$
less than $\widetilde{R}$ as well. Now we work with the definition of $R$ in
equation 24 to show that $R\leq\widetilde{R}$:

$\displaystyle\frac{R}{2}$
$\displaystyle=\gamma\frac{\beta^{2}}{\alpha^{2}}\left\|\begin{bmatrix}{\cal{J}}_{0}^{\dagger}&0\\\
0&{\cal{J}}_{0}^{\dagger}\end{bmatrix}\bm{z}_{0}\right\|_{\ell_{2}}+\frac{9\epsilon\beta^{2}\gamma^{2}}{\alpha^{4}}\left\|\bm{z}_{0}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(i\right)}{\leq}\gamma\frac{\beta^{2}}{\alpha^{3}}\left\|\bm{r}_{0}\right\|_{\ell_{2}}+\frac{9\frac{\alpha^{2}}{4\gamma\beta}\beta^{2}\gamma^{2}}{\alpha^{4}}\left\|\bm{r}_{0}\right\|_{\ell_{2}}$
$\displaystyle=\gamma\left\|\bm{r}_{0}\right\|_{\ell_{2}}\left(\frac{\beta^{2}}{\alpha^{3}}+\frac{9}{4}\frac{\beta}{\alpha^{2}}\right)$
$\displaystyle\overset{\left(ii\right)}{\leq}20\frac{\beta^{2}}{\alpha^{3}}\left\|\bm{r}_{0}\right\|_{\ell_{2}}$
$\displaystyle=20\frac{\left(3\sigma_{v}\sigma_{z}\left(\sqrt{k}+2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}\right)^{2}}{\left(\sigma_{v}\sigma_{z}\left(\frac{1}{2}\sqrt{k-9}-2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}\right)^{3}}\left\|\bm{r}_{0}\right\|_{\ell_{2}}$
$\displaystyle\overset{\left(iii\right)}{\leq}C\cdot\frac{1}{\sigma_{v}\sigma_{z}\sqrt{k}}\cdot\left(\frac{2}{3}\sigma_{v}\sigma_{w}\sigma_{z}\sqrt{k\cdot
d\cdot m}+\left\|\bm{\bar{x}}\right\|_{\ell_{2}}\right)$

where $\left(i\right)$ holds because
$\left\|{\cal{J}}_{0}^{\dagger}\right\|\leq\frac{1}{\alpha}$ and
$4\gamma\beta\epsilon=\alpha^{2}$, $\left(ii\right)$ holds as
$1\leq\frac{\beta}{\alpha}$ and as we substitute $\gamma=5$ from Lemma A.3,
and $\left(iii\right)$ follows from $k\geq C\cdot m$ and using
$\delta=\frac{1}{3}$ in Lemma A.10. Now a sufficient condition for equation 36
to hold is that

$\displaystyle\frac{1}{\sigma_{v}\sigma_{z}\sqrt{k}}\cdot\left(\frac{2}{3}\sigma_{v}\sigma_{w}\sigma_{z}\sqrt{k\cdot
d\cdot m}+\left\|\bm{\bar{x}}\right\|_{\ell_{2}}\right)\leq
c\frac{\sigma_{w}\sqrt{k}}{\left(d\log d\right)^{\frac{3}{2}}},$

which is equivalent to

$\displaystyle\frac{2}{3}\sigma_{v}\sigma_{w}\sigma_{z}\cdot\left(d\log
d\right)^{\frac{3}{2}}\sqrt{k\cdot d\cdot m}+\left(d\log
d\right)^{\frac{3}{2}}\left\|\bm{\bar{x}}\right\|_{\ell_{2}}\leq c\cdot
k\sigma_{v}\sigma_{w}\sigma_{z}.$

Finally, this inequality is satisfied by assuming $k\geq C\cdot
md^{4}\log\left(d\right)^{3}$ and setting
$\sigma_{v}\sigma_{w}\sigma_{z}\geq\frac{\left\|\bm{\bar{x}}\right\|_{\ell_{2}}}{md^{\frac{5}{2}}\log{d}^{\frac{3}{2}}}$.
This shows that assumption 3 holds with probability at least
$1-ne^{-\frac{m}{2}}-ne^{-c\cdot md^{3}\log\left(d\right)^{2}}-k\cdot
e^{-c\cdot n}-e^{-\frac{m}{1500}}-e^{-\frac{kd}{162}}$, concluding the proof
of Theorem 2.1.

###  A.7 Proof of Theorem 2.2

Consider a nonlinear least-squares optimization problem of the form

$\underset{\theta\in\mathbb{R}^{p}}{\text{min
}}\mathcal{L}{\left(\theta\right)}:=\frac{1}{2}\left\|f\left(\theta\right)-y\right\|_{\ell_{2}}^{2}$

with $f:\mathbb{R}^{p}\mapsto\mathbb{R}^{m}$ and $y\in\mathbb{R}^{m}$. Suppose
the Jacobian mapping associated with $f$ satisfies the following three
assumptions.

Assumption 1 We assume
$\sigma_{min}\left({\cal{J}}\left(\theta_{0}\right)\right)\geq 2\alpha$ for a
fixed point $\theta_{0}\in\mathbb{R}^{p}$.

Assumption 2 Let $\|\cdot\|$ be a norm dominated by the Frobenius norm i.e.
$\|\theta\|\leq\left\|\theta\right\|_{F}$ holds for all
$\theta\in\mathbb{R}^{p}$. Fix a point $\theta_{0}$ and a number $R>0$. For
any $\theta$ satisfying $\|\theta-\theta_{0}\|\leq R$, we have
$\|{\cal{J}}\left(\theta\right)-{\cal{J}}\left(\theta_{0}\right)\|\leq\frac{\alpha}{3}$.

Assumption 3 We assume for all $\theta\in\mathbb{R}^{p}$ obeying
$\|\theta-\theta_{0}\|\leq R$, we have
$\left\|{\cal{J}}\left(\theta\right)\right\|\leq\beta$.

With these assumptions in place we are now ready to state the following result
from Oymak & Soltanolkotabi (2020):

###### Theorem A.11

Given $\theta_{0}\in\mathbb{R}^{p}$, suppose assumptions 1, 2, and 3 hold with

$\displaystyle
R=\frac{3\left\|f\left(\theta_{0}\right)-y\right\|_{\ell_{2}}}{\alpha}.$ (37)

Then, using a learning rate $\eta\leq\frac{1}{3\beta^{2}}$, all gradient
descent updates obey

$\begin{split}\left\|f\left(\theta_{\tau}\right)-y\right\|_{\ell_{2}}\leq\left(1-\eta\alpha^{2}\right)^{\tau}\left\|f\left(\theta_{0}\right)-y\right\|_{\ell_{2}}.\end{split}$
(38)

We are going to apply this theorem in our case where the parameter is
$\bm{W}$, the nonlinear mapping is
$f\left(\bm{W}\right)=\frac{1}{n}\sum_{i=1}^{n}\bm{V}\phi\left(\bm{W}\bm{z_{i}}\right)$
with $\phi=ReLU$, and the norm $\|\cdot\|$ set to the operator norm.

Similar to previous part, by using Lemma A.7 we conclude that with probability
at least $1-3e^{-\frac{m}{72}}-4k\cdot e^{-c\cdot n}-2k\cdot
e^{-\frac{d}{216}}$, assumption 1 is satisfied with

$\displaystyle
2\alpha:=\sigma_{v}\sigma_{z}\left(\frac{1}{2}\sqrt{k-9}-2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}.$

Next we show that assumption 2 is valid for $\alpha$ as defined in the
previous line and for radius $\widetilde{R}$ defined later. First we note that

$\frac{\alpha}{3}\geq c\cdot\sigma_{v}\sigma_{z}\cdot\sqrt{k},$

where the inequality holds by assuming $K\geq C\cdot m$ for a sufficiently
large positive constant $C$. Now by using equation 35 assumption 2 holds if

$\frac{5}{4}\sigma_{v}\sigma_{z}\sqrt{d}\left(2\sqrt{m}+\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\right)\leq
c\cdot\sigma_{v}\sigma_{z}\cdot\sqrt{k},$

which is equivalent to

$C\sqrt{md}+C\sqrt{d}\cdot\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\leq\sqrt{k}.$

The first term in the L.H.S. of the inequality above is upper bounded by
$\frac{1}{2}\sqrt{k}$ if $k\geq C\cdot md$. For upper bounding the second term
it is sufficient to show that

$C\sqrt{d}\sqrt{6\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}\text{log}\left(\frac{k}{3\cdot\left(\frac{2kR}{\sigma_{w}}\right)^{\frac{2}{3}}}\right)}\leq\sqrt{k},$

which by defining
$x=3d\left(\frac{2R}{\sigma_{w}\sqrt{k}}\right)^{\frac{2}{3}}$ is equivalent
to $x\cdot\text{log}\left(\frac{d}{x}\right)\leq C$. Now this last inequality
holds if we have $x\leq\frac{c}{\text{log}\left(d\right)}$ for a sufficiently
small constant $c$, which by rearranging terms amounts to showing that $R\leq
c\cdot\frac{\sigma_{w}\sqrt{k}}{\left(d\cdot\text{log}\left(d\right)\right)^{\frac{3}{2}}}$.
Hence up to this point, we have shown that assumption 2 holds with radius
$\widetilde{R}:=c\cdot\frac{\sigma_{w}\sqrt{k}}{\left(d\cdot\text{log}\left(d\right)\right)^{\frac{3}{2}}}$,
and this implies that it holds for all values of $R$ less than
$\widetilde{R}$. Therefore, we work with the definition of $R$ in equation 37
to show that $R\leq\widetilde{R}$ as follows:

$\displaystyle R$
$\displaystyle=\frac{3\left\|f\left(\theta_{0}\right)-y\right\|_{\ell_{2}}}{\alpha}$
$\displaystyle\overset{\left(i\right)}{\leq}\frac{3}{\alpha}\left(\frac{2}{3}\sigma_{v}\sigma_{w}\sigma_{z}\sqrt{k\cdot
d\cdot m}+\left\|\bm{\bar{x}}\right\|_{\ell_{2}}\right)$
$\displaystyle=\frac{2\left(2\sigma_{v}\sigma_{w}\sigma_{z}\sqrt{k\cdot m\cdot
d}+3\left\|\bar{\bm{x}}\right\|_{\ell_{2}}\right)}{\sigma_{v}\sigma_{z}\left(\frac{1}{2}\sqrt{k-9}-2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}},$

where in $\left(i\right)$ we used Lemma A.10 with $\delta=\frac{1}{3}$. Hence
for showing $R\leq\widetilde{R}$ it suffices to show that

$\frac{2\left(2\sigma_{v}\sigma_{w}\sigma_{z}\sqrt{k\cdot m\cdot
d}+3\left\|\bar{\bm{x}}\right\|_{\ell_{2}}\right)}{\sigma_{v}\sigma_{z}\left(\frac{1}{2}\sqrt{k-9}-2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}}\leq
c\cdot\frac{\sigma_{w}\sqrt{k}}{\left(d\cdot\text{log}\left(d\right)\right)^{\frac{3}{2}}},$

which by assuming $k\geq C\cdot m$ simplifies to

$\sigma_{v}\sigma_{w}\sigma_{z}\left(d\cdot\text{log}\left(d\right)\right)^{\frac{3}{2}}\sqrt{k\cdot
m\cdot
d}+\left(d\cdot\text{log}\left(d\right)\right)^{\frac{3}{2}}\left\|\bm{\bar{x}}\right\|_{\ell_{2}}\leq
C\cdot k\cdot\sigma_{v}\sigma_{w}\sigma_{z}.$

Now this last inequality holds if $k\geq C\cdot md^{4}\log\left(d\right)^{3}$
and by setting
$\sigma_{v}\sigma_{w}\sigma_{z}\geq\frac{\left\|\bm{\bar{x}}\right\|_{\ell_{2}}}{md^{\frac{5}{2}}\log{d}^{\frac{3}{2}}}$.
Therefore Assumption 2 holds for radius $R$ defined in equation 37 with
probability at least $1-ne^{-\frac{m}{2}}-ne^{-c\cdot
md^{3}\log{\left(d\right)}^{2}}-k\cdot e^{-c\cdot
n}-e^{-\frac{m}{1500}}-e^{-\frac{kd}{162}}$.

Finally to show assumption 3 holds, we note that for all $\bm{W}$ satisfying
$\left\|\bm{W}-\bm{W}_{0}\right\|\leq R$, where the value of $R$ is defined in
equation 37, it holds that

$\displaystyle\left\|{\mathcal{J}}\left(\bm{W}\right)\right\|$
$\displaystyle\leq\left\|{\mathcal{J}}\left(\bm{W}_{0}\right)\right\|+\left\|{\mathcal{J}}\left(\bm{W}\right)-{\mathcal{J}}\left(\bm{W}_{0}\right)\right\|$
$\displaystyle\leq\left\|{\mathcal{J}}\left(\bm{W}_{0}\right)\right\|+\frac{\alpha}{3}$
$\displaystyle\leq\left\|{\mathcal{J}}\left(\bm{W}_{0}\right)\right\|+\frac{\sigma_{\text{min}}\left({\mathcal{J}}\left(\bm{W}_{0}\right)\right)}{6}$
$\displaystyle\leq 2\left\|{\mathcal{J}}\left(\bm{W}_{0}\right)\right\|$
$\displaystyle\leq
3\sigma_{v}\sigma_{z}\left(\sqrt{k}+2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}},$

where the last inequality holds by using lemma A.8, hence establishing that
assumption 3 holds with

$\beta=3\sigma_{v}\sigma_{z}\left(\sqrt{k}+2\sqrt{m}\right)\sqrt{\frac{d+\frac{n-1}{\pi}}{2n}}$

with probability at least $1-e^{-\frac{m}{2}}-2k\cdot e^{-c\cdot n}-k\cdot
e^{-\frac{d}{216}}$, finishing the proof of Theorem 2.2.

##  Appendix B Proofs of the auxiliary lemmas

In this section, we first provide a proof of Lemma A.6 and next go over the
proofs of the key lemmas stated in Section A.5.

###  B.1 Proof of Lemma A.6

Recall that

$\displaystyle{\cal{J}}(\bm{W}){\cal{J}}(\bm{W})^{T}$
$\displaystyle=\frac{1}{n^{2}}\sum_{i,j=1}^{n}\left(\bm{V}diag(\phi^{\prime}(\bm{W}\bm{z}_{i}))\text{diag}(\phi^{\prime}(\bm{W}\bm{z}_{j})\bm{V}^{T}\right)(\bm{z}_{i}^{T}\bm{z}_{j})$
$\displaystyle=\frac{1}{n^{2}}\bm{V}\underset{\ell=1,\ldots,k}{\text{diag}}\left(\left\|\sum_{i=1}^{n}\bm{z}_{i}\phi^{\prime}(\bm{w}_{\ell}^{T}\bm{z}_{i})\right\|_{\ell_{2}}^{2}\right)\bm{V}^{T}=\frac{1}{n^{2}}\bm{V}\cdot\bm{D}^{2}\cdot\bm{V}^{T},$

where $\bm{D}$ is a diagonal matrix with entries

$D_{\ell\ell}=\left\|\sum_{i=1}^{n}\bm{z}_{i}\phi^{\prime}(\bm{w}_{\ell}^{T}\bm{z}_{i})\right\|_{\ell_{2}}=\left\|\bm{Z}^{T}\phi^{\prime}(\bm{Z}\bm{w}_{\ell})\right\|_{\ell_{2}}.$
(39)

The matrix $\bm{Z}\in\mathbb{R}^{n\times d}$ contains the $\bm{z}_{i}$’s in
its rows. In order to proceed we are going to analyze the entries of the
diagonal matrix $\bm{D}^{2}$. We observe that

$\begin{split}\left\|\bm{Z}^{T}\phi^{\prime}(\bm{Z}\bm{w})\right\|_{\ell_{2}}^{2}&=\underbrace{\left\|(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{Z}^{T}\phi^{\prime}(\bm{Z}\bm{w})\right\|_{\ell_{2}}^{2}}_{A}+\underbrace{\left\|\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}}\bm{Z}^{T}\phi^{\prime}(\bm{Z}\bm{w})\right\|_{\ell_{2}}^{2}}_{B}.\end{split}$

First, we compute the expectation of $A$. We observe that

$A=\left\|\sum_{i=1}^{n}(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{z}_{i}\phi^{\prime}(\bm{w}^{T}\bm{z}_{i})\right\|_{\ell_{2}}^{2}.$

Conditioned on $\bm{w}$,
$\left(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{\|\bm{w}\|^{2}}\right)\bm{z}_{i}$ is
distributed as
$\mathcal{N}\left(0,\sigma_{z}^{2}\left(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{\|\bm{w}\|^{2}}\right)\right)$
and $\bm{w}^{T}\bm{z}_{i}$ has distribution
$\mathcal{N}\left(0,\sigma_{z}^{2}\|\bm{w}\|^{2}\right)$. Moreover, these two
random variables are independent, because $\bm{w}$ is in the null space of
$\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}}$. This observation yields

$\begin{split}\mathbb{E}(A)&=\mathbb{E}\left\|\sum_{i=1}^{n}(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{z}_{i}\phi^{\prime}(\bm{w}^{T}\bm{z}_{i})\right\|_{\ell_{2}}^{2}\\\
&=\sum_{i=1}^{n}\sum_{j=1}^{n}\mathbb{E}\left(\left\langle(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{z}_{i},(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{z}_{j}\right\rangle\phi^{\prime}(\bm{w}^{T}\bm{z}_{i})\phi^{\prime}(\bm{w}^{T}\bm{z}_{j})\right)\\\
&=\sum_{i=1}^{n}\mathbb{E}\left(\left\|(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{z}_{i}\right\|_{\ell_{2}}^{2}\right)\mathbb{E}\left(\left[\phi^{\prime}(\bm{w}^{T}\bm{z}_{i})\right]^{2}\right)\\\
&=\sum_{i=1}^{n}\frac{1}{2}(d-1)\sigma_{z}^{2}=\frac{n}{2}(d-1)\sigma_{z}^{2}.\end{split}$

Next we show that $A$ is concentrated around its mean. Because
$\left(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}}\right)\bm{z}_{i}$ is
independent from $\bm{w}^{T}\bm{z}_{i}$, we use $\bm{z^{\prime}}_{i}$ as an
independent copy of $\bm{z}_{i}$. Hence we can write

$\begin{split}A&=\left\|(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{Z}^{T}\phi^{\prime}(\bm{Z}\bm{w})\right\|_{\ell_{2}}^{2}\\\
&=\left\|(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{Z}^{T}\phi^{\prime}(\bm{Z^{\prime}}\bm{w})\right\|_{\ell_{2}}^{2}\\\
&=\left\|\sum_{i=1}^{n}(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}})\bm{z}_{i}\phi^{\prime}\left(\bm{w}^{T}\bm{z^{\prime}}_{i}\right)\right\|_{\ell_{2}}^{2}=\left\|\sum_{i=1}^{n}\bm{g}_{i}u_{i}\right\|_{\ell_{2}}^{2},\end{split}$

where
$\bm{g}_{i}=\left(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{\|\bm{w}\|^{2}}\right)\bm{z}_{i}\sim\mathcal{N}\left(0,\sigma_{z}^{2}\left(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{\|\bm{w}\|^{2}}\right)\right)$
and $u_{i}=\phi^{\prime}\left(\bm{w}^{T}\bm{z^{\prime}}_{i}\right)\sim
bern(\frac{1}{2})$,444Here, $bern(\frac{1}{2})$ means that the random variable
takes values $0$ and $1$ each with probability $1/2$. and these are all
independent from each other. Note that
$\left\|\sum_{i=1}^{n}\bm{g}_{i}u_{i}\right\|_{\ell_{2}}^{2}$ has the same
distribution as
$\left\|\bm{g}\right\|_{\ell_{2}}^{2}\cdot\left\|\bm{u}\right\|_{\ell_{2}}^{2}$,
where
$\bm{g}\sim\mathcal{N}\left(0,\sigma_{z}^{2}\left(\bm{I}-\frac{\bm{w}\bm{w}^{T}}{\|\bm{w}\|^{2}}\right)\right)$
and $\bm{u}$ is a vector with entries $u_{i}$. Note that for the norm of
$\bm{u}$, the event

$\frac{n}{2}\left(1-\delta\right)\leq\left\|\bm{u}\right\|_{\ell_{2}}^{2}\leq\frac{n}{2}\left(1+\delta\right)$

holds with probability at least $1-2e^{-\frac{n\delta^{2}}{2}}$. Recall that
for $\bm{g}\sim\mathcal{N}(0,\sigma^{2}\bm{I}_{d})$ and
$0<\delta\leq\frac{1}{2}$ we have

$\begin{split}\mathbb{P}\left(\left\|\bm{g}\right\|_{\ell_{2}}^{2}\geq(1+\delta)\mathbb{E}\left(\left\|\bm{g}\right\|_{\ell_{2}}^{2}\right)\right)\leq
e^{-\frac{d\delta^{2}}{6}},\\\
\mathbb{P}\left(\left\|\bm{g}\right\|_{\ell_{2}}^{2}\leq(1-\delta)\mathbb{E}\left(\left\|\bm{g}\right\|_{\ell_{2}}^{2}\right)\right)\leq
e^{-\frac{d\delta^{2}}{4}}.\\\ \end{split}$ (40)

By applying the union bound and noting that
$\mathbb{E}\left(\left\|\bm{g}\right\|_{\ell_{2}}^{2}\right)=\left(d-1\right)\sigma_{z}^{2}$,
for $0<\delta\leq\frac{3}{2}$, we obtain that the event

$|\left\|\bm{g}\right\|_{\ell_{2}}^{2}\left\|\bm{u}\right\|_{\ell_{2}}^{2}-\frac{n}{2}(d-1)\sigma_{z}^{2}|\leq\delta\frac{n}{2}(d-1)\sigma_{z}^{2}$

holds with probability at least
$1-2e^{-\frac{n\delta^{2}}{18}}-2e^{-\frac{d\delta^{2}}{54}}$.
In order to analyze $B$, we first note that

$\begin{split}B=\left\|\frac{\bm{w}\bm{w}^{T}}{||\bm{w}||^{2}}\bm{Z}^{T}\phi^{\prime}(\bm{Z}\bm{w})\right\|_{\ell_{2}}^{2}&=\left|\frac{\bm{w}^{T}}{||\bm{w}||}\bm{Z}^{T}\phi^{\prime}(\bm{Z}\bm{w})\right|^{2}\\\
&=\left|\left\langle\bm{Z}\frac{\bm{w}}{||\bm{w}||},\phi^{\prime}(\bm{Z}\bm{w})\right\rangle\right|^{2}\\\
&=\Big{|}\left\langle\bm{g},\phi^{\prime}(||\bm{w}||\bm{g})\right\rangle\Big{|}^{2}\\\
&=\left|\sum_{i=1}^{n}\bm{g}_{i}\cdot\mathbbm{1}_{(\bm{g}_{i}\geq
0)}\right|^{2}=\left(\sum_{i=1}^{n}ReLU(\bm{g}_{i})\right)^{2},\end{split}$

where
$\bm{g}_{i}=\bm{z}_{i}^{T}\frac{\bm{w}}{\|\bm{w}\|}\sim\mathcal{N}\left(0,\sigma_{z}^{2}\right)$.
It follows that

$\begin{split}\mathbb{E}\left(B\right)&=\mathbb{E}\left(\sum_{i=1}^{n}ReLU(\bm{g}_{i})\right)^{2}\\\
&=\sum_{i=1}^{n}\mathbb{E}\Big{(}ReLU^{2}(\bm{g}_{i})\Big{)}+\sum_{i\neq
j}\mathbb{E}\Big{(}ReLU(\bm{g}_{i})ReLU(\bm{g}_{j})\Big{)}\\\
&=\sigma_{z}^{2}\left(\frac{n}{2}+\frac{n(n-1)}{2\pi}\right),\end{split}$

which results in

$\mathbb{E}\left(\bm{D}_{\ell\ell}^{2}\right)=\mathbb{E}\left(A\right)+\mathbb{E}\left(B\right)=\sigma_{z}^{2}\left(\frac{nd}{2}+\frac{n(n-1)}{2\pi}\right),~{}~{}~{}1\leq\ell\leq
k.$

Next, in order to show that $B$ concentrates around its mean, we note that
$ReLU\left(\bm{g}_{i}\right)$ is a sub-Gaussian random variable with
$\psi_{2}-$norm $C\sigma_{z}$, where $C$ is a fixed constant. Therefore
$X=\sum_{i=1}^{n}ReLU\left(\bm{g}_{i}\right)$ is sub-Gaussian with
$\psi_{2}-$norm $C\sqrt{n}\sigma_{z}$. By the sub-exponential tail bound for
$X^{2}-\mathbb{E}(X^{2})$ we obtain

$\mathbb{P}\Big{(}\left|B-\mathbb{E}\left(B\right)\right|\geq t\Big{)}\leq
2e^{-c\frac{t}{n\sigma_{z}^{2}}}.$

Finally by putting these results together and using union bounds we have

$\mathbb{P}\left\\{\left|\bm{D}_{\ell\ell}^{2}-\mathbb{E}\left(\bm{D}_{\ell\ell}^{2}\right)\right|\geq\delta\mathbb{E}\left(\bm{D}_{\ell\ell}^{2}\right)\right\\}\leq
2e^{-\frac{n\delta^{2}}{18}}+2e^{-\frac{d\delta^{2}}{54}}+2e^{-c_{1}n\delta},~{}~{}~{}~{}~{}0\leq\delta\leq\frac{3}{2},$

finishing the proof of Lemma A.6.

###  B.2 Proof of lemma A.7

Our main tool for bounding the minimum singular value of the Jacobian mapping
will be the following lemma from Soltanolkotabi (2019):

###### Lemma B.1

Let $\bm{d}\in\mathbb{R}^{k}$ be a fixed vector with nonzero entries and
$\bm{D}=diag\left(\bm{d}\right).$ Also, let $\bm{A}\in\mathbb{R}^{k\times m}$
have i.i.d. $\mathcal{N}\left(0,1\right)$ entries and
$\mathcal{T}\subseteq\mathbb{R}^{m}$. Define

$b_{k}\left(\bm{d}\right)=\mathbb{E}\left[\left\|\bm{D}\bm{g}\right\|_{\ell_{2}}\right],$

where $\bm{g}\sim\mathcal{N}\left(\bm{0},\bm{I}_{k}\right).$ Also define

$\sigma\left(\mathcal{T}\right):=\underset{\bm{v}\in\mathcal{T}}{\text{max
}}\left\|\bm{v}\right\|_{\ell_{2}}.$

Then for all $\bm{u}\in\mathcal{T}$ we have

$\left|\left\|\bm{D}\bm{A}\bm{u}\right\|_{\ell_{2}}-b_{k}\left(\bm{d}\right)\left\|\bm{u}\right\|_{\ell_{2}}\right|\leq\left\|\bm{d}\right\|_{\ell_{\infty}}\omega\left(\mathcal{T}\right)+\eta$

with probability at least
$1-6e^{\frac{-\eta^{2}}{8\left\|\bm{d}\right\|_{\ell_{\infty}}^{2}\sigma^{2}\left(\mathcal{T}\right)}}.$

In order to apply this lemma, we set the elements of $\bm{d}$ to be
$D_{\ell\ell}$ as in equation 39 and choose $\mathcal{T}=S^{m-1}$ and
$\bm{A}=\bm{V}^{T}\in\mathbb{R}^{k\times m}$ with
$\mathcal{N}(0,\sigma_{v}^{2})$ entries. It follows that

$b_{k}\left(\bm{d}\right)=\mathbb{E}\left\|\bm{D}\bm{g}\right\|_{\ell_{2}}=\sqrt{\mathbb{E}\left(\left\|\bm{D}\bm{g}\right\|_{\ell_{2}}^{2}\right)-\text{Var}\left(\left\|\bm{D}\bm{g}\right\|_{\ell_{2}}\right)},$

where

$\mathbb{E}\left(\left\|\bm{D}\bm{g}\right\|_{\ell_{2}}^{2}\right)=\left\|\bm{d}\right\|_{\ell_{2}}^{2}=\sum_{\ell=1}^{k}\bm{D}_{\ell\ell}^{2}.$

We are going to use the fact that for a $B$-Lipschitz function $\phi$ and
normal random variable $g\sim\mathcal{N}(0,1),$ based on the Poincare
inequality (Ledoux, 2001) we have Var$\left(\phi\left(g\right)\right)\leq
B^{2}.$ By noting that for a diagonal matrix $\bm{D}$

$\left|\left\|\bm{D}x\right\|_{\ell_{2}}-\left\|\bm{D}y\right\|_{\ell_{2}}\right|\leq\left\|\bm{D}\bm{x}-\bm{D}\bm{y}\right\|_{\ell_{2}}\leq\left\|\bm{d}\right\|_{\ell_{\infty}}\left\|\bm{x}-\bm{y}\right\|_{\ell_{2}},$

we get

$\displaystyle\mathbb{E}\left\|\bm{D}\bm{g}\right\|_{\ell_{2}}$
$\displaystyle=\sqrt{\mathbb{E}\Big{(}\left\|\bm{D}\bm{g}\right\|_{\ell_{2}}^{2}\Big{)}-\text{Var}(\left\|\bm{D}\bm{g}\right\|_{\ell_{2}})}$
$\displaystyle\geq\sqrt{\left\|\bm{d}\right\|_{\ell_{2}}^{2}-\left\|\bm{d}\right\|_{\ell_{\infty}}^{2}}.$

This combined with $\omega\left(S^{m-1}\right)\leq\sqrt{m}$ and Lemma B.1
yields that the event

$\sigma_{min}\left(\bm{VD}\right)\geq\sigma_{v}\left(\sqrt{\left\|\bm{d}\right\|_{\ell_{2}}^{2}-\left\|\bm{d}\right\|_{\ell_{\infty}}^{2}}-\left\|\bm{d}\right\|_{\ell_{\infty}}\sqrt{m}-\eta\right)$
(41)

holds with probability at least
$1-3e^{\frac{-\eta^{2}}{8\left\|\bm{d}\right\|_{\ell_{\infty}}^{2}}}.$
Next, using the concentration bound for $\bm{D}_{\ell\ell}^{2}$, which we
obtained in Section B.1, we bound $\left\|\bm{d}\right\|_{\ell_{2}}^{2}$ and
$\left\|\bm{d}\right\|_{\ell_{\infty}}$, where we have set
$\bm{d}_{i}=\bm{D}_{ii}$ for $1\leq i\leq k.$ For $0\leq\delta\leq\frac{3}{2}$
we compute that

$\begin{split}\mathbb{P}\left(\underset{1\leq i\leq k}{\text{max
}}\bm{d}_{i}\geq\left(1+\delta\right)\sqrt{\mathbb{E}\left[\bm{d}_{i}^{2}\right]}\right)&=\mathbb{P}\left(\bigcup\limits_{i=1}^{k}\bm{d}_{i}^{2}\geq\left(1+\delta\right)^{2}\mathbb{E}\left[\bm{d}_{i}^{2}\right]\right)\\\
&\leq
k\cdot\mathbb{P}\left(\bm{d}_{i}^{2}\geq\left(1+\delta\right)^{2}\mathbb{E}\left[\bm{d}_{i}^{2}\right]\right)\\\
&\leq
k\cdot\mathbb{P}\left(\bm{d}_{i}^{2}\geq\left(1+\delta\right)\mathbb{E}\left[\bm{d}_{i}^{2}\right]\right)\leq
k\cdot\left(e^{-\frac{n\delta^{2}}{18}}+e^{-\frac{d\delta^{2}}{54}}+e^{-c_{1}n\delta}\right),\end{split}$
(42)

as well as

$\begin{split}\mathbb{P}\left(\left\|\bm{d}\right\|_{\ell_{2}}\leq\left(1-\delta\right)\sqrt{k}\sqrt{\mathbb{E}\left[\bm{d}_{i}^{2}\right]}\right)&\leq\mathbb{P}\left(\bigcup\limits_{i=1}^{k}\bm{d}_{i}^{2}\leq\left(1-\delta\right)^{2}\mathbb{E}\left[\bm{d}_{i}^{2}\right]\right)\\\
&\leq
k\cdot\mathbb{P}\left(\bm{d}_{i}^{2}\leq\left(1-\delta\right)^{2}\mathbb{E}\left[\bm{d}_{i}^{2}\right]\right)\\\
&\leq
k\cdot\mathbb{P}\left(\bm{d}_{i}^{2}\leq(1-\delta)\mathbb{E}\left[\bm{d}_{i}^{2}\right]\right)\leq
k\cdot\left(e^{-\frac{n\delta^{2}}{18}}+e^{-\frac{d\delta^{2}}{54}}+e^{-c_{1}n\delta}\right).\end{split}$
(43)

Finally by replacing $\eta$ with
$\eta\left\|\bm{d}\right\|_{\ell_{\infty}}\sqrt{m}$ in equation 41, combined
with equation 42 and equation 43, for a random $\bm{W}_{0}$ with i.i.d.
$\mathcal{N}\left(0,\sigma_{w}^{2}\right)$ entries we have:

$\begin{split}\sigma_{min}\left({\cal{J}}(\bm{W}_{0})\right)&=\frac{1}{n}\sigma_{min}\left(\bm{VD}\right)\\\