Title: RANDOM MATRIX THEORY PROVES THAT DEEP LEARNING REPRESENTATIONS OF GAN-DATA BEHAVE AS GAUSSIAN MIXTURES Anonymous

Abstract: This paper shows that deep learning (DL) representations of data produced by generative adversarial nets (GANs) are random vectors which fall within the class of so-called concentrated random vectors. Further exploiting the fact that Gram matrices, of the type G = X X with X = [x 1 , . . . , x n ] ∈ R p×n and x i independent concentrated random vectors from a mixture model, behave asymptotically (as n, p → ∞) as if the x i were drawn from a Gaussian mixture, suggests that DL representations of GAN-data can be fully described by their first two statistical moments for a wide range of standard classifiers. Our theoretical findings are validated by generating images with the BigGAN model and across different popular deep representation networks.

1. INTRODUCTION:

The performance of machine learning methods depends strongly on the choice of the data representation (or features) on which they are applied. This data representation should ideally contain relevant information about the learning task in order to achieve learning with simple models and small amount of samples. Deep neural networks (Rumelhart et al., 1988) have particularly shown impressive results by automatically learning representations from raw data (e.g., images). However, due to the complex structure of deep learning models, the characterization of their hidden representations is still an open problem (Bengio et al., 2009) .

Specifically, quantifying what makes a given deep learning representation better than another is a fundamental question in the field of Representation Learning (Bengio et al., 2013) . Relying on (Montavon et al., 2011) a data representation is said to be good when it is possible to build simple models on top of it that are accurate for the given learning problem. Montavon et al. (2011) have notably quantified the layer-wise evolution of the representation in deep networks by computing the principal components of the Gram matrix G = {φ (x i ) φ (x j )} n i,j=1 at each layer for n input data x 1 , . . . , x n , where φ (x) is the representation of x at layer of the given DL model, and the number of components controls the model simplicity. In their study, the impact of the representation at each layer is quantified through the prediction error of a linear predictor trained on the principal subspace of G .

Pursuing on this idea, given a certain representation model x → φ(x), we aim in this article at theoretically studying the large dimensional behavior, and in particular the spectral information (i.e., eigenvalues and dominant eigenvectors), of the corresponding Gram matrix G = {φ(x i ) φ(x j )} n i,j=1 in order to determine the information encoded (i.e., the sufficient statistics) by the representation model on a set of real data x 1 , . . . , x n . Indeed, standard classification and regression algorithms -along with the last layer of a neural network (Yeh et al., 2018 )-retrieve the data information directly from functionals or the eigenspectrum of G1 . To this end, though, one needs a statistical model for the representations given the distribution of the raw data (e.g., images) which is generally unknown. Yet, due to recent advances in generative models since the advent of Generative Adversarial Nets (Goodfellow et al., 2014) , it is now possible to generate complex data structures by applying successive Lipschitz operations to Gaussian random vectors. In particular, GAN-data are used in practice as substitutes of real data for data augmentation (Antoniou et al., 2017) . On the other hand, the fundamental concentration of measure phenomenon (Ledoux, 2005) tells us that Lipschitz-ally transformed Gaussian vectors satisfy a concentration property. Precisely, defining the class of concentrated vectors x ∈ E through concentration inequalities of f (x), for any real Lipschitz observation f : E → R, implies that deep learning representations of GAN-data fall within this class of random vectors, since the mapping x → φ(x) is Lipschitz. Thus, GAN-data are concentrated random vectors and thus an appropriate statistical model of realistic data.

Targeting classification applications by assuming a mixture of concentrated random vectors model, this article studies the spectral behavior of Gram matrices G in the large n, p regime. Precisely, we show that these matrices have asymptotically (as n, p → ∞ with p/n → c < ∞) the same firstorder behavior as for a Gaussian Mixture Model (GMM). As a result, by generating images using the BigGAN model (Brock et al., 2018) and considering different commonly used deep representation models, we show that the spectral behavior of the Gram matrix computed on these representations is the same as on a GMM model with the same p-dimensional means and covariances. A surprising consequence is that, for GAN data, the aforementioned sufficient statistics to characterize the quality of a given representation network are only the first and second order statistics of the representations. This behavior is shown by simulations to extend beyond random GAN-data to real images from the Imagenet dataset (Deng et al., 2009) .

The rest of the paper is organized as follows. In Section 2, we introduce the notion of concentrated vectors and their main properties. Our main theoretical results are then provided in Section 3. In Section 4 we present experimental results. Section 5 concludes the article.

Notation: In the following, we use the notation from (Goodfellow et al., 2016) .

[n] denotes the set {1, . . . , n}. Given a vector x ∈ R n , the 2 -norm of x is given as

x 2 = n i=1 x 2 i . Given a p × n matrix M , its Frobenius norm is defined as M 2 F = p i=1 n j=1 M 2 ij and its spectral norm as M = sup x =1 M x . for the Hadamard product. An application F : E → F is said to be F lip -Lipschitz, if ∀(x, y) ∈ E 2 , F(x) -F(y) F ≤ F lip • x -y E and F lip is finite.

2. BASIC NOTIONS OF CONCENTRATED VECTORS:

Being the central tool of our study, we start by introducing the notion of concentrated vectors. While advanced concentration notions have been recently developed in (Louart & Couillet, 2019 ) in order to specifically analyze the behavior of large dimensional sample covariance matrices, for simplicity, we restrict ourselves here to the sufficient so-called q-exponentially concentrated random vectors. Definition 2.1 (q-exponential concentration). Given a normed space (E, • E ) and a real q, a random vector x ∈ E is said to be q-exponentially concentrated if for any 1-Lipschitz real function f : E → R, there exists C ≥ 0 independent of dim(E) and σ > 0 such that for all t ≥ 0

P {|f (x) -Ef (x)| > t} ≤ C e -(t/σ) q (1) which we denote x ∈ E q (σ | E, • E ). We simply write x ∈ E q (1 | E, • E ) if the

tail parameter σ does not depend on dim(E), and x ∈ E q (1) for x a scalar real random variable.

Therefore, concentrated vectors are defined through the concentration of any 1-Lipschitz real scalar "observation". One of the most important examples of concentrated vectors are standard Gaussian vectors. Precisely, we have the following proposition. See (Ledoux, 2005)) for more examples such as uniform and Gamma distribution. Proposition 2.2 (Gaussian vectors (Ledoux, 2005) ). Let d ∈ N and x ∼ N (0, I d ). Then x is a 2-exponentially concentrated vector independently on the dimension d, i.e.

x ∈ E 2 (1 | R d , • ).

Concentrated vectors have the interesting property of being stable by application of R d → R p vector-Lipschitz transformations. Indeed, Lipschitz-ally transformed concentrated vectors remain concentrated according to the following proposition. Proposition 2.3 (Lipschitz stability (Louart & Couillet, 2019) ). Let x ∈ E q (1 | E, • E ) and G : E → F a Lipschitz application with Lipschitz constant G lip which may depend on dim(F ). Then the concentration property on x is transferred to G(x), precisely

x

EQUATION

Note importantly for the following that the Lipschitz constant of the transformation G must be controlled, in order to constrain the tail parameter of the obtained concentration.

In particular, we have the coming corollary to Proposition 2.3 of central importance in the following.

Corollary 2.4. Let G 1 , . . . , G n : R d → R p a set of n Lipschitz applications with Lipschitz constants G i lip . Let G : R d×n → R p×n be defined for each

EQUATION

Proof. This is a consequence of Proposition 2.3 since the map G is sup i G i lip -Lipschitz with respect to (w.r.t.) the Frobenius norm. Indeed, for X,

H ∈ R d×n : G(X + H) -G(X) 2 F ≤ n i=1 G i 2 lip • H :,i 2 ≤ sup i G i 2 lip • H 2 F .

3. MAIN RESULTS:

3.1 GAN DATA: AN EXAMPLE OF CONCENTRATED VECTORS Concentrated random vectors are particularly interesting from a practical standpoint for real data modeling. In fact, unlike simple Gaussian vectors, the former do not suffer from the constraint of having independent entries which is quite a restrictive assumption when modeling real data such as images or their non-linear features (e.g., DL representations). The other modeling interest of concentrated vectors lies in their being already present in practice as alternatives to real data. Indeed, adversarial neural networks (GANs) have the ability nowadays to generate random realistic data (for instance realistic images) by applying successive Lipschitz operations to standard Gaussian vectors (Goodfellow et al., 2014) .

A GAN architecture involves two networks, a generator model which maps random Gaussian noise to new plausible synthetic data and a discriminator model which classifies real data as real (from the dataset) or fake (for the generated data). The discriminator is updated directly through a binary classification problem, whereas the generator is updated through the discriminator. As such, the two models are trained alternatively in an adversarial manner, where the generator seeks to better deceive the discriminator and the former seeks to better identify the fake data (Goodfellow et al., 2014) .

In particular, once both models are trained (when they reach a Nash equilibrium), DL representations of GAN-data -and GAN-data themselves-are schematically constructed in practice as follows: • Fully Connected Layers and Convolutional Layers: These are affine operations which can be expressed as

EQUATION

F i (x) = W i x + b i ,

for W i the weight matrix and b i the bias vector.

Here the Lipschitz constant is the operator norm (the largest singular value) of the weight matrix W i , that is

F i lip = sup u =0 Wiu 2 u 2 .

• Pooling Layers and Activation Functions: Most commonly used activation functions and pooling operations are

ReLU(x) = max(0, x), MaxPooling(x) = [max(x S1 ), . . . , max(x Sq )] ,

where S i 's are patches (i.e., subsets of [dim(x)]). These are at most 1-Lipschitz operations with respect to the Frobenius norm. Specifically, the maximum absolute sub-gradient of the ReLU activation function is 1, thus the ReLU operation has a Lipschitz constant of 1. Similarly, we can show that the Lipschitz constant of MaxPooling layers is also 1.

• Residual Connections: Residual layers act the following way

F i (x) = x + F (1) i • • • • • F ( ) i (x),

where the F (j) i 's are Fully Connected Layers or Convolutional Layers with Activation Functions, and which are Lipschitz operations. Thus F i is a Lipschitz operation with Lipschitz constant bounded by 1 + j=1 F (j) i lip .

• Batch Normalization (BN) Layers: They consist in statistically standardizing (Ioffe & Szegedy, 2015) the vectors of a small batch

B = {x i } b i=1 ⊂ R d as follows: for each x k ∈ B F i (x k ) = diag a σ 2 B + (x k -µ B 1 d ) + b where µ B = 1 db b k=1 d i=1 [x k ] i , σ 2 B = 1 db b k=1 d i=1 ([x k ] i -µ B ) 2 , a, b ∈ R d are

parameters to be learned and diag(v) transforms a vector v to a diagonal matrix with its diagonal entries being those of v. Thus BN is a Lipschitz transformation with Lipschitz constant

F i lip = sup i | ai √ σ 2 B + |.

Therefore, as illustrated in Figure 1 , since standard Gaussian vectors are concentrated vectors as mentioned in Proposition 2.2 and since the notion of concentrated vectors is stable by Lipschitz transformations thanks to Proposition 2.3, GAN-data (and their DL representations) are concentrated vectors by design given the construction in Equation (4). Moreover, in order to generate data belonging to a specific class, Conditional GANs have been introduced (Mirza & Osindero, 2014) ; once again data generated by these models are concentrated vectors as a consequence of Corollary 2.4. Indeed, a generator of a Conditional GAN model can be seen as a set of multiple generators where each generates data of a specific class conditionally on the class label (e.g., BigGAN model (Brock et al., 2018) ).

Yet, in order to ensure that the resulting Lipschitz constant of the combination of the above operations does not scale with the network or data size, so to maintain good concentration behaviors, a careful control of the learned network parameters is needed. This control happens to be already considered in practice in order to ensure the stability of GANs during the learning phase, notably to generate realistic and high-resolution images (Roth et al., 2017; Brock et al., 2018) . The control of the Lipschitz constant of representation networks is also needed in practice in order to make them robust against adversarial examples (Szegedy et al., 2013; Gulrajani et al., 2017) . This control is particularly ensured through spectral normalization of the affine layers (Brock et al., 2018) , such as Fully Connected Layers, Convolutional Layers and Batch Normalization. Indeed, spectral normalization (Miyato et al., 2018) consists in applying the operation W ← W /σ 1 (W ) to the affine layers at each backward iteration of the back-propagation algorithm, where σ 1 (W ) stands for the largest singular value of the weight matrix W . Brock et al. (2018) , have notably observed that, without spectral constraints, a subset of the generator layers grow throughout their GAN training and explode at collapse. They thus suggested the following spectral normalization -which happens to be less restrictive than the standard spectral normalization W ← W /σ 1 (W ) (Miyato et al., 2018) -to the affine layers: where u 1 (W ) and v 1 (W ) denote respectively the left and right largest singular vectors of W , and σ * is an hyper-parameter fixed during training.

EQUATION

To get an insight about the influence of this operation and to ensure that it controls the Lipschitz constant of the generator, the following proposition provides the dynamics of a random walk in the space of parameters along with the spectral normalization in Equation ( 5). Indeed, since stochastic gradient descent (SGD) consists in estimating the gradient of the loss function on randomly selected batches of data, it can be assimilated to a random walk in the space of parameters (Antognini & Sohl-Dickstein, 2018) . Proposition 3.1 (Lipschitz constant control). Let σ * > 0 and G be a neural network composed of N affine layers, each one of input dimension d i-1 and output dimension d i for i ∈ [N ], with 1-Lipschitz activation functions. Assume that the weights of G at layer i + 1 are initialized as U([-

1 √ di , 1 √ di ]),

and consider the following dynamics with learning rate η:

EQUATION

Then, ∀ε > 0, the Lipschitz constant of G is bounded at convergence with high probability as:

EQUATION

Proof. The proof is provided in Appendix B.

Proposition 3.1 shows that the Lipschitz constant of a neural network is controlled when trained with the spectral normalization in Equation ( 5). In particular, recalling the notations in Proposition 3.1, in the limit where

d i → ∞ with di di-1 → γ i ∈ (0, ∞) for all i ∈ [N ] and choosing the learning rate η = O(d -1 0 ), the Lipschitz constant of G is of order O(1)

if it has finitely many layers N and σ * is constant. Therefore, with this spectral normalization, it can be assumed that G lip = O(1) when dimensions grow. Figure 2 depicts the behavior of the Lipschitz constant of a linear layer with and without spectral normalization in the setting of Proposition 3.1, which confirms the obtained bound.

3.2. MIXTURE OF CONCENTRATED VECTORS:

In this section, we assume data to be a mixture of concentrated random vectors with controlled O(1) Lipschitz constant (e.g., DL representations of GAN-data as we discussed in the previous section). Precisely, let x 1 , . . . , x n be a set of mutually independent random vectors in R p . We suppose that these vectors are distributed as one of k classes of distribution laws µ 1 , . . . , µ k with distinct means {m } k =1 and "covariances" {C } k =1 defined receptively as

EQUATION

For some q > 0, we consider a q-exponential concentration property on the laws µ , in the sense that for any family of independent vectors y 1 , . . . , y s sampled from µ , [y 1 , . . . , y s ] ∈ E q (1 | R p×s , • F ). Without loss of generality, we arrange the x i 's in a data matrix X = [x 1 , . . . ,

x n ] such that, for each ∈ [k], x 1+ -1 j=1 nj , . . . , x j=1 nj ∼ µ , where n stands for the number of x i 's sampled from µ . In particular, we have the concentration of X as

X ∈ E q (1 | R p×n , • F ).

(9) Such a data matrix X can be constructed through Lipschitz-ally transformed Gaussian vectors (q = 2), with controlled Lipschitz constant, thanks to Corollary 2.4. In particular, DL representations of GAN-data are constructed as such, as shown in Section 3.1. We further introduce the following notations that will be used subsequently.

M = [m 1 , . . . , m k ] ∈ R p×k , J = [j 1 , . . . , j k ] ∈ R n×k and Z = [z 1 , . . . , z n ] ∈ R p×n

, where j ∈ R n stands for the canonical vector selecting the x i 's of distribution µ , defined by (j ) i = 1 xi∼µ , and the z i 's are the centered versions of the x i 's, i.e. z i = x i -m for x i ∼ µ .

3.3. GRAM MATRICES OF CONCENTRATED VECTORS:

Now we study the behavior of the Gram matrix G = 1 p X X in the large n, p limit and under the model of the previous section. Indeed, G appears as a central component in many classification, regression and clustering methods. Precisely, a finer description of the behavior of G provides access to the internal functioning and performance evaluation of a wide range of machine learning methods such as Least Squares SVMs (AK et al., 2002) , Semi-supervised Learning (Chapelle et al., 2009) and Spectral Clustering (Ng et al., 2002) . Indeed, the performance evaluation of these methods has already been studied under GMM models in (Liao & Couillet, 2017; Mai & Couillet, 2017; Couillet & Benaych-Georges, 2016) through RMT. On the other hand, analyzing the spectral behavior of G for DL representations quantifies their quality -through its principal subspace (Montavon et al., 2011)-as we have discussed in the introduction. In particular, the Gram matrix decomposes as

EQUATION

Intuitively G decomposes as a low-rank informative matrix containing the class canonical vectors through J and a noise term represented by the other matrices and essentially Z Z. Given the form of this decomposition, RMT predicts -through an analysis of the spectrum of G and under a GMM model (Benaych-Georges & Couillet, 2016) -the existence of a threshold ξ function of the ratio p/n and the data statistics for which the dominant eigenvectors of G contain information about the classes only when M M ≥ ξ asymptotically (i.e., only when the means of the different classes are sufficiently distinct).

In order to characterize the spectral behavior (i.e., eigenvalues and leading eigenvectors) of G under the concentration assumption in Equation ( 9) on X, we will be interested in determining the spectral distribution L = 1 n n i=1 δ λi of G, with λ 1 , . . . , λ n the eigenvalues of G, where δ x stands for the Dirac measure at point x. Essentially, to determine the limiting eigenvalue distribution as p, n → ∞ and p/n → c ∈ (0, ∞), a conventional approach in RMT consists in determining an estimate of the Stieltjes transform (Silverstein & Choi, 1995) 

EQUATION

)

Hence, quantifying the behavior of the resolvent of G defined as R(z) = (G + zI n ) -1 determines the limiting measure of L through m L (z). Furthermore, since R(z) and G share the same eigenvectors with associated eigenvalues 1 λi-z , the projector matrix corresponding to the top m eigenvectors U = [u 1 , . . . , u m ] of G can be calculated through a Cauchy integral U U = 1 2πi γ R(-z)dz where γ is an oriented complex contour surrounding the top m eigenvalues of G.

To study the behavior of R(z), we look for a so-called deterministic equivalent (Hachem et al., 2007 ) R(z) for R(z), which is a deterministic matrix that satisfies for all A ∈ R n×n and all u, v ∈ R n of respectively bounded spectral and Eucildean norms, 1 n tr(AR(z)) -1 n tr(A R(z)) → 0 and u (R(z) -R(z))v → 0 almost surely as n → ∞. In the following, we present our main result which gives such a deterministic equivalent under the concentration assumption on X in Equation ( 9) and under the following assumptions. Assumption 3.2. As p → ∞,

1. p/n → c ∈ (0, ∞), 2. The number of classes k is bounded, 3. m = O( √ p).

Theorem 3.3 (Deterministic Equivalent for R(z)). Under the model described in Section 3.2 and Assumptions 3.2, we have

EQUATION

)

with

Ω z = M Q(z)M diag δ * (z)-1 δ * (z)+1 k =1 and Q(z) = 1 c k k =1 C 1+δ * (z) + zI p -1 , where δ * (z) = [δ * 1 (z), . . . , δ * k (z)]

is the unique fixed point of the system of equations

δ (z) = 1 p tr   C   1 c k k j=1 C j 1 + δ j (z) + zI p   -1    for each ∈ [k].

Sketch of proof. The first step of the proof is to show the concentration of R(z). This comes from the fact that the application X → R(z) is 2z -3/2 p -1/2 -Lipschitz w.r.t. the Frobenius norm, thus we have by Proposition 2.

3 that R(z) ∈ E q (p -1/2 | R n×n , • F ).

The second step consists in estimating ER(z) through a deterministic matrix R(z). Indeed, R(z) can be expressed as a function of

Q(z) = (XX /p + zI p ) -1 as R(z) = z -1 (I n -X Q(z)X/p),

and exploiting the result of (Louart & Couillet, 2019) which shows that EQ(z) can be estimated through Q(z), we obtain the estimator R(z) for ER(z). A more detailed proof is provided in Section A.3 of the Appendix.

This result allows specifically to (i) describe the limiting eigenvalues distribution of G, (ii) determine the spectral detectability threshold mentioned above, (iii) evaluate the asymptotic "content" of the leading eigenvectors of G and, much more fundamentally, (iv) infer the asymptotic performances of machine learning algorithms that are based on simple functionals of G (e.g., LS-SVM, spectral clustering etc.). Looking carefully at Theorem 3.3 we see that the spectral behavior of the Gram matrix G computed on concentrated vectors only depends on the first and second order statistics of the laws µ (their means m and "covariances" C ). This suggests the surprising result that G has the same behavior as when the data follow a GMM model with the same means and covariances.

The asymptotic spectral behavior of G is therefore universal with respect to the data distribution laws which satisfy the aforementioned concentration properties (for instance DL representations of GAN-data). We illustrate this universality result in the next section by considering data as CNN representations of GAN generated images.

GAN Images:

Real Images 



Real Images:



4. APPLICATION TO CNN REPRESENTATIONS OF GAN-GENERATED IMAGES:

In this section, we consider n = 1500 data x 1 , . . . , x n ∈ R p as CNN representations -across popular CNN architectures of different sizes pof GAN-generated images using the generator of the Big-GAN model (Brock et al., 2018) . We further use real images from the Imagenet dataset (Deng et al., 2009) for comparison. In particular, we empirically compare the spectrum of the Gram matrix of this data with the Gram matrix of a GMM model with the same means and covariances. We also consider the leading 2-dimensional eigenspace of the Gram matrix which contains clustering information as detailed in the previous section. Figure 3 depicts some images generated using the Big-GAN model (Top) and the corresponding real class images from the Imagenet dataset (Bottom).

The Big-GAN model is visually able to generate highly realistic images which are by construction concentrated vectors, as discussed in Section 3.1.

Figure 4 depicts the spectrum and leading 2D eigenspace of the Gram matrix computed on CNN representations of GAN generated and real images (in gray), and the corresponding GMM model with same first and second order statistics (in green). The Gram matrix is seen to follow the same spectral behavior for GAN-data as for the GMM model which is a natural consequence of the universality result of Theorem 3.3 with respect to the data distribution. Besides, and perhaps no longer surprisingly, we further observe that the spectral properties of G for real data (here CNN representations of real images) are conclusively matched by their Gaussian counterpart. This both theoretically and empirically confirms that the proposed random matrix framework is fully compliant with the theoretical analysis of real machine learning datasets.

5. CONCLUSION:

Leveraging on random matrix theory (RMT) and the concentration of measure phenomenon, we have shown through this paper that DL representations of GAN-data behave as Gaussian mixtures for linear classifiers, a fundamental universal property which is only valid in high-dimension of data. To the best of our knowledge, this result constitutes a new approach towards the theoretical understanding of complex objects such as DL representations, as well as the understanding of the behavior of more elaborate machine learning algorithms for complex data structures. In addition, the article explicitly demonstrated our ability, through RMT, to anticipate the behavior of a wide range of standard classifiers for data as complex as DL representations of the realistic and surprising images generated by GANs. This opens the way to a more systematic analysis and improvement of machine learning algorithms on real datasets by means of large dimensional statistics.

A PROOF OF THEOREM 3.3

A.1 SETTING OF THE PROOF For simplicity, we will only suppose the case k = 1 and we consider the following notations that will be used subsequently.

x = Ex i , C = E[x i x i ], X 0 = X -x1 n , C 0 = E[X 0 X 0 /n].

Let X -i = (x 1 , . . . , x i-1 , 0, x i , . . . , x n ) the matrix X with a vector of zeros at its ith column.

Denote the resolvents:

EQUATION

And let

EQUATION

)

where δ is the solution to the fixed point equation

δ = 1 p tr C 1 c C 1 + δ + zI p -1

.

A.2 BASIC TOOLS Lemma A.1 ((Ledoux, 2005) ). Let z ∈ E q (1 | R p , • ) and M ∈ E q (1 | R p×n , • F ). Then, for some numerical constant C > 0

• E z ≤ Ez + C √ p, E z ∞ ≤ Ez ∞ + C √ log p. • E M ≤ EM + C √ p + n, E M F ≤ EM F + C √ pn.

Lemma A.2. Denote Q x = ( x x + zI p ) -1 , we have:

Q x x = x x 2 + z and Q x , x Q x = O(1). Moreover, if x ≥ √ p, Q x = O(p -1/2 ).

Proof. Since zQ x = I p -Q x x x :

zQ x x = x -x 2 Q x x,

and we recover the first identity of the Lemma.

And since the matrix C 0 is nonnegative symmetric, we have :

Q x = 1 c C 0 + x x 1 + δ + zI p -1 x ≤ c(1 + δ) x x 2 + zc(1 + δ) .

Therefore, x Q x = c(1+δ) x 2 x 2 +zc(1+δ) = O(1) and:

Q x = c(1 + δ) x x 2 + zc(1 + δ) ≤        x z = O(1) if x ≤ 1, c(1 + δ) x = O(1) if x ≥ 1. Proposition A.3. x E[Q] x = x Q x + O log p p

Proof. Let us bound:

x Q x -x Q x ≤ c -1 1 + δ E xQx i x i Q x 1 p x i Q -i x i -δ + 1 p E x Q -i x i x i QC Q x

Now let us consider a supplementary random vector x n+1 following the same low as the x i 's and independent of X. We divide the set I = [n + 1] into two sets I 1 2 and I 2 2 of same cardinality ( n+1

2 ≤ #I 1 2 , #I 2 2 ≤ n+1 2 ), we note X 1 2 = (x i | i ∈ I 1 2 ), X 2 2 = (x i | i ∈ I 2

2 ) and we introduce the diagonal matrices

∆ = diag 1 p x i Q -i x i -δ | i ∈ I 1 2 , D = diag 1 + 1 p+1 x i Qx i | i ∈ I 2 2 .

Under review as a conference paper at ICLR 2020

We have the bound:

E xQx i x i Q x 1 p x i Q -i x i -δ = E 1 + 1 p x n+1 Qx n+1 x n+1 Q +(n+1) x i x i Q x 1 p x i Q -i x i -δ = 1 p 2 E 1 DX 2 2 Q +(n+1) X 1 2 ∆X 1 2 Q x ≤ E 1 p 3 1 DX 2 2 Q +(n+1) X 1 2 ∆ 2 X 1 2 Q +(n+1) X 2 2 D1 E 1 p x QX 1 2 X 1 2 Q x ≤ E 1 p X 2 2 Q +(n+1) X 1 2 2 D 2 ∆ 2 E x QC Q x ≤ O log p p ,

thanks to Lemma A.1 and Lemma A.2 (the spectral norm of ∆ and D is just an infinity norm if we see them as random vectors of R n ). We can bound 1 p E x Q -i x i x i QC Q x the same way to obtain the result of the proposition.

Proposition A.4. E[x i Q -i X -i ] -x Q x1 1+δ = O( √ log p) Proof. Considering u ∈ R n such that u = 1: E[x i Q -i X -i u] - x Q x1 u 1 + δ = n j=1 j =i u j E x i Q -i -j x j 1 + 1 p x j Q -j -i x j - x i Qx j 1 + δ ≤ √ n E x i Q -i -j x j 1 + 1 p x j Q -j -i x j - x i Q -i -j x j 1 + δ + 1 1 + δ E x i Q -i -j x j -x i Qx j (where i = j) ≤ √ n E x Qx j 1 p x j Q -j -i x j -δ + √ n E x Q -i -j x -x Q x ,

where the first term is treated the same way as we did in the proof of Proposition A.3 and the second term is bounded thanks to Proposition A.3

A.3 MAIN BODY OF THE PROOF:

Proof of Theorem 3.3. Recall the definition of the resolvents R and Q in Equation ( 13). The first step of the proof is to show the concentration of R. This comes from the fact that the application Φ : X → (X X + zI n ) -1 is 2z -3/2 -Lipschitz w.r.t. the Frobenius norm. Indeed, by the matrix identity

A -B = A(B -1 -A -1 )B, we have Φ(X) -Φ(X + H) = Φ(X)(H X + (X + H) H)Φ(X + H)

And by the bounds AB:

F ≤ A • B F , Φ(X)X ≤ z -1/2 and Φ(X) ≤ z -1 , we have Φ(X + H) -Φ(X) F ≤ 2 z 3/2 H F . Therefore, given X ∈ E q (1 | R p×n , • F ) and since the application X → R = Φ(X/ √ p) is 2z -3/2 p -1/2 -Lipschitz, we have by Proposition 2.3 that R ∈ E q (p -1/2 | R n×n , • F ).

The second step consists in estimating ER(z) through a deterministic matrix R. Indeed, by the identity (M M +zI) -1 M = M (M M +zI) -1 , the resolvent R can be expressed in function

1 p 2 n i=1 E u X -i Q -i C QX -i v 1 + δ - u X -i Q -i x i x i QX -i v 1 + 1 p x i Q -i x i = 1 p 2 n i=1 E u X -i Q -i x i x i QX -i v δ -1 p x i Q -i x i (1 + δ)(1 + 1 p x i Q -i x i ) ≤ 1 p 2 n i=1 E (u X -i Q -i x i )(x i QX -i v) δ - 1 p x i Q -i x i ≤ 1 p n i=1 E 1 √ p u X -i Q -i x i 3 E 1 √ p x i QX -i v 3 E δ - 1 p x i Q -i x i 3 1 3 = O 1 √ p

Similarly, we can show that:

1 p 2 n i=1 E u i x i Q -i C QX -i v 1 + δ + v i u X -i Q -i C Qx i 1 + δ +u i v i x i Q -i C Qx i 1 + δ - 1 p u X Q -i x i x i QC QXv 1 + δ = O 1 √ p

Finally, the remaining terms in ∆ can be estimated as follows:

∆ = 1 p 2 n i=1 E - u i x i Q -i x i x i QX -i v 1 + 1 p x i Q -i x i - v i u X -i Q -i x i x i Qx i 1 + 1 p x i Qx i -u i v i x i Q -i x i x i Qx i 1 + 1 p x i Q -i x i + O 1 √ p = - 2 p δu 1 x Q x1 v 1 + δ - δ 2 u v 1 + δ + O log p p

Where the last equality is obtained through the following estimation:

1 p 2 n i=1 E v i u X -i Q -i x i x i Qx i 1 + 1 p x i Q -i x i = 1 p n i=1 E   v i u X -i Q -i x i 1 p x i Qx i (1 + δ) -δ 1 + 1 p x i Qx i 1 + 1 p x i Q -i x i (1 + δ)   + 1 p n i=1 v i δE[u X -i Q -i x i ] (1 + δ)

With the following bound:

1 p x i Qx i (1 + δ) -δ 1 + 1 p x i Qx i = 1 p x i Qx i (1 + δ) -δ(1 + δ) + δ(1 + δ) -δ 1 + 1 p x i Qx i ≤ 1 p x i Qx i -δ (1 + 2δ),

we have again with Holder's inequality and Proposition A.4:

1 p 2 n i=1 E v i u X -i Q -i x i x i Qx i 1 + 1 p x i Qx i = 1 p n i=1 v i δu 1 x Q x 1 + δ + O log p p

Now that we estimated ∆, it remains to estimate E[ 1 p X QX]. Indeed, given two unit norm vectors u, v ∈ R n we have:

E 1 p u X QXv = 1 p n i,j=1 u i v j E[x i Qx j ] = 1 p n i=1 n j=1 j =i u i v j x Q x + n i=1 u i v i δ = 1 p x Q xu 11 v + (δ - 1 p x Q x)u v = 1 p x Q xu M 1 v + δu v + O 1 p

since we have x Q x = O(1) by Lemma A.2; we introduced the matrix M 1 = 11 . Therefore we have the following estimation:

1 p E [X QX] = δ 1 + δ I n + 1 p 1 -δ 1 + δ x Q xM 1 + O • log p p

where A = B +O • (α(p)) means that A-B = O(α(p)). Finally, since R concentrates around its mean, we can then conclude:

R = 1 z I n - 1 p X QX = 1 z 1 1 + δ I n + δ -1 pz(δ + 1) x Q xM 1 + O • log p p .

B PROOF OF PROPOSITION 3.1

Proof. Since the Lipschitz constant of a composition of Lipschitz functions is bounded by the product of their Lipschitz constants, we consider the case N = 1 and a linear activation function. In this case, the Lipschitz constant corresponds to the largest singular value of the weight matrix. We consider the following notations for the proof Wt = W t -ηE t with [E t ] i,j ∼ N (0, 1) W t+1 = Wt -max(0, σ1,t -σ * ) ū1,t v 1,t where σ1,t = σ 1 ( Wt ), ū1,t = u 1 ( Wt ) and v1,t = v 1 ( Wt ). The effect of spectral normalization is observed in the case where σ * > σ1,t , otherwise the Lipschitz constant is bounded by σ * . We therefore have

EQUATION

• If W t+1 F ≥ W t F , we have by equation 16 and equation 17

Wt

2 F ≤ Wt 2 F + σ 2 * -σ2 1,t + η 2 d 1 d 0 ⇒ Wt = σ1,t ≤ σ 2 * + η 2 d 1 d 0 = δ

And since W t+1 ≤ Wt , we have W t+1 ≤ δ.

• Otherwise, if there exits τ such that W τ +1 F < W τ F , then for all ε > 0 there exists an iteration τ ≥ τ such that W τ ≤ δ + ε. Indeed, otherwise we denote ε t = W t 2 -δ 2 and ε t > 0 for all t ≥ τ . And if for all t ≥ τ , W t+1 F ≤ W t F , we have by equation 16 and equation 17

W t 2 F -W t+1 2 F ≥ Wt 2 -δ 2 ≥ W t+1 2 -δ 2 = ε t+1

Integrating the above expression from τ to T -1 ≥ τ , we end up with

W τ 2 F -W T 2 F ≥ T -1 t=τ ε t ⇒ 0 ≤ W T 2 F ≤ W τ 2 F - T -1 t=τ ε t ,

therefore, when T → ∞, ε t has to tend to 0 otherwise the right hand-side of the last inequality will tend to -∞ which is absurd.

:

For instance, spectral clustering uses the dominant eigenvectors of G, while support vector machines use functionals (quadratic forms) involving G.

Figures and Tables:

Figure 1: Deep learning representations of GAN-data are constructed by applying successive Lipschitz operations to Gaussian vectors, therefore they are concentrated vectors by design, since Gaussian vectors are concentrated and thanks to the Lipschitz stability in Proposition 2.3.

Figure 2: Behavior of the largest singular value of a weight matrix in terms of the iterations of a random walk (see proposition 3.1), without spectral normalization in (blue) and with spectral normalization in (red). The (black) lines correspond to the theoretical bound σ 2 * + η 2 d 1 d 0 for different σ * 's. We took d 0 = d 1 = 100 and η = 1/d 0 .

Figure 3: (Top) GAN generated images using the BigGAN model Brock et al. (2018). (Bottom) Real images selected from the Imagenet dataset Deng et al. (2009). We considered n = 1500 images from k = 3 classes which are Mushroom, Pizza and Hamburger.

Figure 4: (Top) Spectrum and leading eigenspace of the Gram matrix for CNN representations of GAN generated images using the BigGAN model Brock et al. (2018). (Bottom) Spectrum and leading eigenspace of the Gram matrix for CNN representations of real images selected from the Imagenet dataset Deng et al. (2009). Columns correspond to the three representation networks (Resnet50, VGG16 and Densenet201).

Peer review (iclr2020):
In this paper, the authors claim to establish a Lipschitz bound on neural networks, initialized randomly, and trained until convergence. They also claim to establish probabilistic concentration of the resolvent of the Gram matrix from a mixture of k distributions with varying means and covariances. The authors also present the spectrum and leading eigenspace of the Gram matrix for representations by CNNs of images generated by a GAN. It is not clear to this reviewer what exactly the authors have proved and what significance it has. For example, in Proposition 3.1, the authors talk about dynamics with a learning rate, where W <- W - eta E where E has standard normal entries and eta is a learning rate. It is unclear what the learning problem is, or why the learning rate is modifying a random modification. I understand the general idea that Lipschitz functions of random-quantities-that-enjoy-concentration-estimates also enjoy concentration estimates. This is well known from the random matrix theory literature. The authors need to make a claim about how this informs either the development or understanding of deep learning technologies. The authors should consider what the implications of their results could be, and then do the research to establish that those implications hold up. The authors claim that their results constitute *a first step towards the theoretical understanding of complex objects such as DL representations.* This claim is false. This very conference is on Learning Representations, and presumably at least one paper in the past 7 years makes progress towards the theoretical understanding of Deep Learning representations. Because of the overly bold claims with insufficient clarity and justification, I recommend that this paper be rejected.