Year: 2019

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 = XTX with X = [x1, . . . ,xn] ∈ Rp×n and xi independent concentrated random vectors from a mixture model, behave asymptotically (as n, p → ∞) as if the xi 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.

heading: 1 INTRODUCTION
text: 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` = {φ`(xi)ᵀφ`(xj)}ni,j=1 at each layer for n input data x1, . . . ,xn, 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 7→ φ(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 = {φ(xi)ᵀφ(xj)}ni,j=1 in order to determine the information encoded (i.e., the sufficient statistics) by the representation model on a set of real data x1, . . . ,xn. 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
1For instance, spectral clustering uses the dominant eigenvectors of G, while support vector machines use functionals (quadratic forms) involving G.
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 7→ φ(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 ∈ Rn, 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‖2F = ∑p i=1 ∑n j=1 M 2 ij and its spectral norm as ‖M‖ = sup‖x‖=1 ‖Mx‖. for the Hadamard product. An application F : E → F is said to be ‖F‖lip-Lipschitz, if ∀(x,y) ∈ E2, ‖F(x)−F(y)‖F ≤ ‖F‖lip · ‖x− y‖E and ‖F‖lip is finite.

heading: 2 BASIC NOTIONS OF CONCENTRATED VECTORS
text: 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 ∈ Eq(σ |E, ‖ · ‖E). We simply write x ∈ Eq(1 |E, ‖ · ‖E) if the tail parameter σ does not depend on dim(E), and x ∈ Eq(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, Id). Then x is a 2-exponentially concentrated vector independently on the dimension d, i.e. x ∈ E2(1 |Rd, ‖ · ‖).
Concentrated vectors have the interesting property of being stable by application of Rd → Rp 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 ∈ Eq(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 ∈ Eq(1 |E, ‖ · ‖E) ⇒ G(x) ∈ Eq(‖G‖lip |F, ‖ · ‖F ). (2)
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 G1, . . . ,Gn : Rd → Rp a set of n Lipschitz applications with Lipschitz constants ‖Gi‖lip. Let G : Rd×n → Rp×n be defined for each X ∈ Rd×n as G(X) = [G1(X:,1), . . . ,Gn(X:,n)]. Then,
Z ∈ Eq(1 |Rd×n, ‖ · ‖F ) ⇒ G(Z) ∈ Eq (
sup i ‖Gi‖lip | Rp×n, ‖ · ‖F
) . (3)
Proof. This is a consequence of Proposition 2.3 since the map G is supi ‖Gi‖lip-Lipschitz with respect to (w.r.t.) the Frobenius norm. Indeed, for X,H ∈ Rd×n : ‖G(X + H) − G(X)‖2F ≤∑n i=1 ‖Gi‖2lip · ‖H:,i‖2 ≤ supi ‖Gi‖2lip · ‖H‖2F .

heading: 3 MAIN RESULTS

heading: 3.1 GAN DATA: AN EXAMPLE OF CONCENTRATED VECTORS
text: 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:
Real Data ≈ GAN Data = FN ◦ · · · ◦ F1(z), where z ∼ N (0, Id), (4)
where d stands for the input dimension of the generator model, N the number of layers, and the Fi’s either Fully Connected Layers, Convolutional Layers, Pooling Layers, Up-sampling Layers and Activation Functions, Residual Layers or Batch Normalizations. All these operations happen to be Lipschitz applications. Precisely,
• Fully Connected Layers and Convolutional Layers: These are affine operations which can be expressed as
Fi(x) = Wix + bi, for Wi the weight matrix and bi the bias vector. Here the Lipschitz constant is the operator norm (the largest singular value) of the weight matrix Wi, that is ‖Fi‖lip = supu6=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(xS1), . . . ,max(xSq )] ᵀ,
where Si’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
Fi(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 Fi 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 = {xi}bi=1 ⊂ Rd as follows: for each xk ∈ B
Fi(xk) = diag ( a√ σ2B + ) (xk − µB1d) + b
where µB = 1db ∑b k=1 ∑d i=1[xk]i, σ 2 B = 1 db ∑b k=1 ∑d i=1([xk]i − µB)2, a, b ∈ Rd 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 ‖Fi‖lip = supi | ai√σ2B+ |.
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:
W ←W − (σ1(W )− σ∗)u1(W )v1(W )ᵀ (5)
where u1(W ) and v1(W ) denote respectively the left and right largest singular vectors of W , and σ∗ is an hyper-parameter fixed during training.
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 ofN affine layers, each one of input dimension di−1 and output dimension di 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 η:
W ←W − ηE, with Ei,j ∼ N (0, 1) W ←W −max(0, σ1(W )− σ∗)u1(W )v1(W )ᵀ.
(6)
Then, ∀ε > 0, the Lipschitz constant of G is bounded at convergence with high probability as:
‖G‖lip ≤ N∏ i=1 ( ε+ √ σ2∗ + η 2didi−1 ) . (7)
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 di →∞ with didi−1 → γi ∈ (0,∞) for all i ∈ [N ] and choosing the learning rate η = O(d−10 ), 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.

heading: 3.2 MIXTURE OF CONCENTRATED VECTORS
text: In this section, we assume data to be a mixture of concentrated random vectors with controlledO(1) Lipschitz constant (e.g., DL representations of GAN-data as we discussed in the previous section). Precisely, let x1, . . . ,xn be a set of mutually independent random vectors in Rp. 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
m` = Exi∼µ` [xi], C` = Exi∼µ` [xix ᵀ i ]. (8)
For some q > 0, we consider a q-exponential concentration property on the laws µ`, in the sense that for any family of independent vectors y1, . . . ,ys sampled from µ`, [y1, . . . ,ys] ∈ Eq(1 |Rp×s, ‖ · ‖F ). Without loss of generality, we arrange the xi’s in a data matrix X = [x1, . . . ,xn] such that, for each ` ∈ [k], x1+∑`−1j=1 nj , . . . ,x∑`j=1 nj ∼ µ`, where n` stands for the number of xi’s sampled from µ`. In particular, we have the concentration of X as X ∈ Eq(1 |Rp×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 = [m1, . . . ,mk] ∈ Rp×k, J = [j1, . . . , jk] ∈ Rn×k and Z = [z1, . . . ,zn] ∈ Rp×n, where j` ∈ Rn stands for the canonical vector selecting the xi’s of distribution µ`, defined by (j`)i = 1xi∼µ` , and the zi’s are the centered versions of the xi’s, i.e. zi = xi −m` for xi ∼ µ`.

heading: 3.3 GRAM MATRICES OF CONCENTRATED VECTORS
text: Now we study the behavior of the Gram matrix G = 1pX ᵀ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
G = 1
p JMᵀMJᵀ +
1 p ZᵀZ + 1 p (JMᵀZ + ZᵀMJᵀ). (10)
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 = 1n ∑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) mL of L, which is defined for some z ∈ C \Supp(L)
mL(z) = ∫ λ dL(λ) λ− z = 1 n tr ( (G− zIn)−1 ) . (11)
Hence, quantifying the behavior of the resolvent of G defined as R(z) = (G + zIn)−1 determines the limiting measure of L throughmL(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 = [u1, . . . ,um] of G can be calculated through a Cauchy integral UUᵀ = 12π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 ∈ Rn×n and all u,v ∈ Rn of respectively bounded spectral and Eucildean norms, 1n tr(AR(z)) − 1 n tr(AR̃(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 R(z) ∈ Eq(p−1/2 |Rn×n, ‖ · ‖F ). Furthermore,∥∥∥ER(z)− R̃(z)∥∥∥ = O( √ log(p)
p
) , R̃(z) = 1
z diag
{ In`
1 + δ∗` (z) }k `=1 + 1 p z JΩzJ ᵀ (12)
with Ωz = MᵀQ̃(z)M diag { δ∗` (z)−1 δ∗` (z)+1 }k `=1 and Q̃(z) = ( 1 c k ∑k `=1 C` 1+δ∗` (z) + zIp )−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 Cj 1 + δj(z) + zIp −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 7→ R(z) is 2z−3/2p−1/2-Lipschitz w.r.t. the Frobenius norm, thus we have by Proposition 2.3 that R(z) ∈ Eq(p−1/2 |Rn×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 + zIp)−1 as R(z) = z−1(In − 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.

heading: 4 APPLICATION TO CNN REPRESENTATIONS OF GAN-GENERATED IMAGES
text: In this section, we consider n = 1500 data x1, . . . ,xn ∈ Rp as CNN representations –across popular CNN architectures of different sizes p– of 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.

heading: 5 CONCLUSION
text: 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.

heading: A PROOF OF THEOREM 3.3
text: 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̄ = Exi, C = E[xixᵀi ], X0 = X − x̄1 ᵀ n, C0 = E[X0X ᵀ 0 /n].
Let X−i = (x1, . . . ,xi−1, 0,xi, . . . ,xn)
the matrix X with a vector of zeros at its ith column.
Denote the resolvents
R =
( XᵀX
p + zIn
)−1 , Q = ( XXᵀ
p + zIp
)−1 , Q−i = ( XXᵀ
p − xix
ᵀ i
p + zIp )−1 (13)
And let
Q̃ =
( 1
c
C
1 + δ + zIp
)−1 , (14)
where δ is the solution to the fixed point equation
δ = 1
p tr
( C ( 1
c
C
1 + δ + zIp
)−1) .
A.2 BASIC TOOLS
Lemma A.1 ((Ledoux, 2005)). Let z ∈ Eq(1 |Rp, ‖ · ‖) and M ∈ Eq(1 |Rp×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 Qx̄ = (x̄x̄ᵀ + zIp)−1, we have:
Qx̄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 zQx̄ = Ip −Qx̄x̄x̄ᵀ :
zQx̄x̄ = x̄− ‖x̄‖2Qx̄x̄,
and we recover the first identity of the Lemma.
And since the matrix C0 is nonnegative symmetric, we have :
Q̃x̄ =
( 1
c
C0 + x̄x̄ ᵀ
1 + δ + zIp
)−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̄ᵀQx̄− x̄ᵀQ̃x̄∣∣∣ ≤ c−1 1 + δ ∣∣∣∣E [x̄Qxixᵀi Q̃x̄(1pxᵀiQ−ixi − δ )] + 1 p E [ x̄ᵀQ−ixix ᵀ iQCQ̃x̄ ]∣∣∣∣ Now let us consider a supplementary random vector xn+1 following the same low as the xi’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 (bn+12 c ≤
#I 1 2 ,#I 2 2 ≤ dn+12 e), we note X 12 = (xi | i ∈ I 12 ), X 22 = (xi | i ∈ I 22 ) and we introduce the diagonal matrices ∆ = diag (
1 px ᵀ iQ−ixi − δ | i ∈ I 12
) , D = diag ( 1 + 1p+1x ᵀ iQxi | i ∈ I 22 ) .
We have the bound:∣∣∣∣E [x̄Qxixᵀi Q̃x̄(1pxᵀiQ−ixi − δ )]∣∣∣∣
= ∣∣∣∣E [(1 + 1pxᵀn+1Qxn+1 ) xn+1Q+(n+1)xix ᵀ i Q̃x̄ ( 1 p xᵀiQ−ixi − δ )]∣∣∣∣ = 1
p2 ∣∣∣E [1ᵀDXᵀ2 2 Q+(n+1)X 1 2 ∆Xᵀ1 2 Q̃x̄ ]∣∣∣
≤ √∣∣∣∣E [ 1p3 1ᵀDXᵀ22Q+(n+1)X 12 ∆2Xᵀ12Q+(n+1)X 22D1 ] E [ 1 p x̄ᵀQ̃X 1 2 Xᵀ1 2 Q̃x̄ ]∣∣∣∣ ≤ √√√√∣∣∣∣∣E [∥∥∥∥1pXᵀ22Q+(n+1)X 12 ∥∥∥∥2 ‖D‖2 ‖∆‖2 ] E [ x̄Q̃CQ̃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 Rn). We can bound 1p ∣∣∣E [x̄ᵀQ−ixixᵀiQCQ̃x̄]∣∣∣ the same way to obtain the result of the proposition.
Proposition A.4. ‖E[xᵀiQ−iX−i]− x̄ᵀQ̃x̄1ᵀ 1+δ ‖ = O( √ log p)
Proof. Considering u ∈ Rn such that ‖u‖ = 1:∣∣∣∣∣E[xᵀiQ−iX−iu]− x̄ᵀQ̃x̄1ᵀu1 + δ ∣∣∣∣∣
= ∣∣∣∣∣∣∣ n∑
j=1 j 6=i
ujE
[ xᵀiQ−i−j xj
1 + 1px ᵀ jQ−j−i
xj − x ᵀ i Q̃xj 1 + δ ]∣∣∣∣∣∣∣ ≤ √ n ∣∣∣∣∣E [ xᵀiQ−i−j xj
1 + 1px ᵀ jQ−j−i
xj −
xᵀiQ−i−j xj
1 + δ ]∣∣∣∣∣+ ∣∣∣∣ 11 + δE [xᵀiQ−i−j xj − xᵀi Q̃xj] ∣∣∣∣ (where i 6= j) ≤ √ n ∣∣∣∣E [x̄ᵀQxj (1pxᵀjQ−j−i xj − δ )]∣∣∣∣+√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 7→ (XᵀX + zIn)−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
z3/2 ‖H‖F .
Therefore, given X ∈ Eq(1 |Rp×n, ‖ · ‖F ) and since the application X 7→ R = Φ(X/ √ p) is 2z−3/2p−1/2-Lipschitz, we have by Proposition 2.3 that R ∈ Eq(p−1/2 |Rn×n, ‖ · ‖F ).
The second step consists in estimating ER(z) through a deterministic matrix R̃. Indeed, by the identity (MᵀM+zI)−1Mᵀ = Mᵀ(MMᵀ+zI)−1, the resolvent R can be expressed in function
of Q as follows
R = 1
z
( In − XᵀQX
p
) , (15)
thus a deterministic equivalent for R can therefore be obtained through a deterministic equivalent of the matrix XᵀQX . However, as demonstrated in Louart & Couillet (2019), the matrix Q has as a deterministic equivalent the matrix Q̃ defined in equation 14. In the following, we aim at deriving a deterministic equivalent for 1pX
ᵀQX in function of Q̃. Let u and v be two unitary vectors in Rn, and let us estimate
∆ ≡ E [ uᵀ ( XᵀQX
p − X
ᵀQ̃X
p
) v ] = 1
p E
[ uᵀXᵀQCQ̃Xv
1 + δ − 1 p uᵀXᵀQXXᵀQ̃Xv ] With the following matrix identities (to explore the independence of the columns of X):
Q = Q−i − 1
p Q−ixix
ᵀ iQ , Qxi =
Q−ixi
1 + 1px ᵀ iQ−ixi
, A−B = A(B−1 −A−1)B
and the decomposition QXXᵀ = ∑n i=1 Qxix ᵀ i , we obtain:
∆ = 1
p2 E [ n∑ i=1 uᵀXᵀQ−iCQ̃Xv 1 + δ − u ᵀXᵀQ−ixix ᵀ i Q̃Xv 1 + 1px ᵀ iQ−ixi − 1 p uᵀXᵀQ−ixix ᵀ iQCQ̃Xv 1 + δ ]
= 1
p2 n∑ i=1 E
[ uᵀXᵀ−iQ−iCQ̃X−iv
1 + δ −
uᵀXᵀ−iQ−ixix ᵀ i Q̃X−iv
1 + 1px ᵀ iQ−ixi
+ uix
ᵀ iQ−iCQ̃X−iv
1 + δ +
viu ᵀXᵀ−iQ−iCQ̃xi
1 + δ + uivi xᵀiQ−iCQ̃xi 1 + δ
− uix ᵀ iQ−ixix ᵀ i Q̃X−iv
1 + 1px ᵀ iQ−ixi
− viu
ᵀXᵀ−iQ−ixix ᵀ i Q̃xi 1 + 1px ᵀ iQ−ixi − uivi xᵀiQ−ixix ᵀ i Q̃xi 1 + 1px ᵀ iQ−ixi
−1 p
uᵀXᵀQ−ixix ᵀ iQCQ̃Xv
1 + δ ] We can show with Holder’s inequality and the concentration bounds (mainly the fact that 1px ᵀ iQ−ixi concentrates around δ) developed in (Louart & Couillet, 2019), that most of the above quantities vanish asymptotically. As a toy example, we consider the following term:∣∣∣∣∣ 1p2 n∑ i=1 E [ uᵀXᵀ−iQ−iCQ̃X−iv 1 + δ − uᵀXᵀ−iQ−ixix ᵀ i Q̃X−iv 1 + 1px ᵀ iQ−ixi
]∣∣∣∣∣ =
∣∣∣∣∣ 1p2 n∑ i=1 E [ uᵀXᵀ−iQ−ixix ᵀ i Q̃X−iv
δ − 1px ᵀ iQ−ixi
(1 + δ)(1 + 1px ᵀ iQ−ixi) ]∣∣∣∣∣ ≤
∣∣∣∣∣ 1p2 n∑ i=1 E [ (uᵀXᵀ−iQ−ixi)(x ᵀ i Q̃X−iv) ( δ − 1 p xᵀiQ−ixi )]∣∣∣∣∣ ≤
∣∣∣∣∣∣1p n∑ i=1 ( E [( 1 √ p uᵀXᵀ−iQ−ixi )3] E [( 1 √ p xᵀi Q̃X−iv )3] E [( δ − 1 p xᵀiQ−ixi )3]) 13 ∣∣∣∣∣∣ = O ( 1 √ p
) Similarly, we can show that:∣∣∣∣∣ 1p2 n∑ i=1 E [ uix ᵀ iQ−iCQ̃X−iv 1 + δ + viu ᵀXᵀ−iQ−iCQ̃xi 1 + δ
+uivi xᵀiQ−iCQ̃xi
1 + δ − 1 p
uᵀXᵀQ−ixix ᵀ iQCQ̃Xv
1 + δ
]∣∣∣∣∣ = O ( 1 √ p )
Finally, the remaining terms in ∆ can be estimated as follows:
∆ = 1
p2 n∑ i=1 E
[ −uix ᵀ iQ−ixix ᵀ i Q̃X−iv
1 + 1px ᵀ iQ−ixi
− viu
ᵀXᵀ−iQ−ixix ᵀ i Q̃xi
1 + 1px ᵀ iQxi
− uivi xᵀiQ−ixix ᵀ i Q̃xi
1 + 1px ᵀ iQ−ixi
] +O ( 1 √ p )
= −2 p
δuᵀ1x̄ᵀQ̃x̄1ᵀv
1 + δ − δ
2uᵀv
1 + δ +O
(√ log p
p ) Where the last equality is obtained through the following estimation:
1
p2 n∑ i=1 E
[ viu ᵀXᵀ−iQ−ixix ᵀ i Q̃xi
1 + 1px ᵀ iQ−ixi
] = 1
p n∑ i=1 E
viuᵀXᵀ−iQ−ixi ( 1 px ᵀ i Q̃xi(1 + δ)− δ ( 1 + 1px ᵀ i Q̃xi )) (
1 + 1px ᵀ iQ−ixi
) (1 + δ)  + 1
p n∑ i=1 viδE[uᵀXᵀ−iQ−ixi] (1 + δ)
With the following bound:∣∣∣∣1pxᵀi Q̃xi(1 + δ)− δ ( 1 + 1 p xᵀi Q̃xi )∣∣∣∣ = ∣∣∣∣1pxᵀi Q̃xi(1 + δ)− δ(1 + δ) + δ(1 + δ)− δ ( 1 + 1 p xᵀi Q̃xi
)∣∣∣∣ ≤ ∣∣∣∣1pxᵀi Q̃xi − δ
∣∣∣∣ (1 + 2δ), we have again with Holder’s inequality and Proposition A.4:
1
p2 n∑ i=1 E
[ viu ᵀXᵀ−iQ−ixix ᵀ i Q̃xi
1 + 1px ᵀ iQxi
] = 1
p n∑ i=1 viδu ᵀ1x̄ᵀQ̃x̄ 1 + δ +O
(√ log p
p
)
Now that we estimated ∆, it remains to estimate E[ 1pX ᵀQ̃X]. Indeed, given two unit norm vectors u, v ∈ Rn we have:
E [ 1
p uᵀXᵀQ̃Xv
] = 1
p n∑ i,j=1 uivjE[xᵀi Q̃xj ] = 1 p n∑ i=1 n∑ j=1 j 6=i uivjx̄ ᵀQ̃x̄ + n∑ i=1 uiviδ
= 1 p x̄ᵀQ̃x̄uᵀ11ᵀv + (δ − 1 p x̄ᵀQ̃x̄)uᵀv = 1 p x̄ᵀQ̃x̄uᵀM1v
ᵀ + δuᵀv +O ( 1
p ) since we have x̄ᵀQ̃x̄ = O(1) by Lemma A.2; we introduced the matrix M1 = 11ᵀ. Therefore we have the following estimation:
1 p E [XᵀQX] = δ 1 + δ In + 1 p ( 1− δ 1 + δ ) x̄ᵀQ̃x̄M1 +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
( In − 1
p XᵀQX
) = 1
z
1
1 + δ In + δ − 1 pz(δ + 1) x̄ᵀQ̃x̄M1 +O‖·‖
(√ log p
p
) .

heading: B PROOF OF PROPOSITION 3.1
text: 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
W̄t = Wt − ηEt with [Et]i,j ∼ N (0, 1) Wt+1 = W̄t −max(0, σ̄1,t − σ∗) ū1,tv̄ᵀ1,t
where σ̄1,t = σ1(W̄t), ū1,t = u1(W̄t) and v̄1,t = v1(W̄t). The effect of spectral normalization is observed in the case where σ∗ > σ̄1,t, otherwise the Lipschitz constant is bounded by σ∗. We therefore have
‖W̄t‖2F ≤ ‖Wt‖2F + η2d1d0 (16) ‖Wt+1‖2F = ‖W̄t‖2F + σ2∗ − σ̄21,t (17)
• If ‖Wt+1‖F ≥ ‖Wt‖F , we have by equation 16 and equation 17 ‖W̄t‖2F ≤ ‖W̄t‖2F + σ2∗ − σ̄21,t + η2d1d0 ⇒ ‖W̄t‖ = σ̄1,t ≤ √ σ2∗ + η 2d1d0 = δ
And since ‖Wt+1‖ ≤ ‖W̄t‖, we have ‖Wt+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 = ‖Wt‖2 − δ2 and εt > 0 for all t ≥ τ . And if for all t ≥ τ , ‖Wt+1‖F ≤ ‖Wt‖F , we have by equation 16 and equation 17
‖Wt‖2F − ‖Wt+1‖2F ≥ ‖W̄t‖2 − δ2 ≥ ‖Wt+1‖2 − δ2 = εt+1 Integrating the above expression from τ to T − 1 ≥ τ , we end up with
‖Wτ‖2F − ‖WT ‖2F ≥ T−1∑ t=τ εt ⇒ 0 ≤ ‖WT ‖2F ≤ ‖Wτ‖2F − 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.

Review summaries:
The authors generalize Gaussian random vectors to a broader class of "concentrated" vectors which they use as their primary tool for analysis of the latent representations learned by GANs. They show that the spectral behavior (i.e. spectra and leading eigenspaces) of the Gram matrix computed over GAN representations is the same as those produced by a high dimensional Gaussian Mixture Models (GMMs). Furthermore, they show that the "sufficient statistics" (i.e. measures of information encoded in the latent representations) for GANs depend only on their first and second moments. Thus, for data that follows Gaussian mixture patterns, GANs and GMMs behave identically. The authors also show that common neural network operations (linear/convolutional layers, pooling, batch normalization, ReLU activations) are Lipschitz transformations, where the Lipschitz constants can be bounded using spectral normalization (this is borrowed from previous work). They also provide some empirical analysis to verify their theoretical findings.

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.