Title: STABLE RANK NORMALIZATION FOR IMPROVED GEN-ERALIZATION IN NEURAL NETWORKS AND GANS

Abstract: Exciting new work on generalization bounds for neural networks (NN) given by Bartlett et al. (2017) ; Neyshabur et al. (2018) closely depend on two parameterdependant quantities a) the Lipschitz constant upper bound and b) the stable rank (a softer version of rank). Even though these bounds typically have minimal practical utility, they facilitate questions on whether controlling such quantities together could improve the generalization behaviour of NNs in practice. To this end, we propose stable rank normalization (SRN), a novel, provably optimal, and computationally efficient weight-normalization scheme which minimizes the stable rank of a linear operator. Surprisingly we find that SRN, despite being non-convex, can be shown to have a unique optimal solution. We provide extensive analyses across a wide variety of NNs (DenseNet, WideResNet, ResNet, Alexnet, VGG), where applying SRN to their linear layers leads to improved classification accuracy, while simultaneously showing improvements in generalization, evaluated empirically using shattering experiments (Zhang et al., 2016) ; and three measures of sample complexity by Bartlett et al. (2017 ), Neyshabur et al. (2018), & Wei & Ma. Additionally, we show that, when applied to the discriminator of GANs, it improves Inception, FID, and Neural divergence scores, while learning mappings with a low empirical Lipschitz constant.

1. INTRODUCTION:

Deep neural networks have shown astonishing ability in tackling a wide variety of machine learning problems including a great ability to generalize under extreme over-parameterization. Within this work we leverage very recent, and important, theoretical results on the generalization bounds of deep networks to yield a practical low cost method to normalize the weights within a network using a scheme -which we call Stable Rank Normalization (SRN). The motivation for SRN comes from the generalization bound for NNs given by Neyshabur et al. (2018) and Bartlett et al. (2017) ,

O d i W i 2 2 d i=1 srank(W i ) 1

, that depend on two parameter-dependent quantities: a) the scale-dependent Lipschitz constant upper-bound d i W i 2 (product of spectral norms) and b) the sum of scale-independent stable ranks (srank(W)). Stable rank is a softer version of the rank operator and is defined as the squared ratio of the Frobenius norm to the spectral norm. Although these two terms appear frequently in these bounds, the empirical impact of simultaneously controlling them on the generalization behaviour of NNs has not been explored yet possibly because of the difficulties associated with optimizing stable rank. This is precisely the goal of this work and based on extensive experiments across a wide variety of NN architectures, we show that, indeed, controlling them simultaneously improves the generalization behaviour, while improving the classification performance of NNs. We observe improved training of Generative Adversarial Networks (GAN) Goodfellow et al. (2014) as well.

To this end, we propose Stable Rank Normalization (SRN) which allows us to simultaneously control the Lipschitz constant and the stable rank of a linear operator. Note that the widely used Spectral Normalization (SN) (Miyato et al., 2018) allows explicit control over the Lipschitz constant, however, as will be discussed in the paper, it does not have any impact on the stable rank. We would like to emphasize that, as opposed to SN, the SRN solution is optimal and unique even in situations when it is non-convex. It is one of those rare cases where an optimal solution to a provably non-convex problem could be obtained. Computationally, our proposed SRN for NNs is no more complicated than SN, just requiring computation of the largest singular value which can be efficiently obtained using the power iteration method (Mises & Pollaczek-Geiringer, 1929) .

Experiments Although SRN is in principle applicable to any problem involving a sequence of affine transformations, considering recent interests, we show its effectiveness when applied to the linear layers of deep neural networks. We perform extensive experiments on a wide variety of NN architectures (DenseNet, WideResNet, ResNet, Alexnet, VGG) for the analyses and show that, SRN, while providing the best classification accuracy (compared against standard, or vanilla, training and SN), consistently shows improvement on the generalization behaviour. We also experiment with GANs and show that, SRN prefers learning discriminators with low empirical Lipschitz while providing improved Inception, FID and Neural Divergence scores (Gulrajani et al., 2019) .

We would like to note that although SN is being widely used for the training of GANs, its effect on the generalization behaviour over a wide variety of NNs has not yet been explored. To the best of our knowledge, we are the first to do so.

Contributions:

• We propose SRN-a novel normalization scheme for simultaneously controlling the Lipschitz constant and the stable rank of a linear operator. • Optimal and unique solution to the provably non-convex stable rank normalization problem.

• Efficient and easy to implement SRN algorithm for NNs.

2. BACKGROUND AND INTUITIONS:

Neural Networks Consider f θ : R m → R k to be a feed-forward multilayer NN parameterized by θ ∈ R n , each layer of which consists of a linear followed by a non-linear2 mapping. Let a l-1 ∈ R n l-1 be the input (or pre-activations) to the l-th layer, then the output (or activations) of this layer is represented as a l = φ l (z l ), where z l = W l a l-1 + b l is the output of the linear (affine) layer parameterized by the weights W l ∈ R n l-1 ×n l and biases b l ∈ R n l , and φ l (.) is the element-wise non-linear function applied to z l . For classification tasks, given a dataset with input-output pairs denoted as (x ∈ R m , y ∈ {0, 1} k ; j y j = 1)3 , the parameter vector θ is learned using back-propagation to optimize the classification loss (e.g., cross-entropy).

Singular Value Decomposition (SVD) Given W ∈ R s×r with rank k ≤ min(s, r), we denote {σ i } k i=1 , {u i } k i=1 , and {v i } k i=1 as its singular values, left singular vectors, and right singular vectors, respectively. Throughout this work, a set of singular values is assumed to be sorted σ 1 ≥ • • • ≥ σ k . σ i (W) denotes the i-th singular value of the matrix W. Using singular values, the matrix 2-norm W 2 and the Frobenius norm W F can be computed as σ 1 and i σ 2 i , respectively.

Stable Rank Below we provide the formal definition and some properties of stable rank. Definition 2.1. The Stable Rank (Rudelson & Vershynin, 2007) of an arbitrary matrix W is defined

as srank(W) = W 2 F W 2 2 = k i=1 σ 2 i (W) σ 2 1 (W)

, where k is the rank of the matrix. Stable rank is

• a soft version of the rank operator and, unlike rank, is less sensitive to small perturbations.

• differentiable as both Frobenius and Spectral norms are almost always differentiable.

• upper-bounded by the rank:

srank(W) = k i=1 σ 2 i (W) σ 2 1 (W) ≤ k i=1 σ 2 1 (W) σ 2 1 (W)

= k.

• invariant to scaling, implying, srank(W) = srank( W η ), for any η ∈ R \ {0}.

Lipschitz Constant Here we describe the global and the local Lipschitz constants. Briefly, the Lipschitz constant is a quantification of the sensitivity of the output with respect to the change in the input.

A function f : R m → R k is globally L-Lipschitz continuous if ∃L ∈ R + : f (x i ) -f (x j ) q ≤ L x i -x j p , ∀(x i , x j ) ∈ R m

, where • p and • q represents the norms in the input and the output metric spaces, respectively. The global Lipschitz constant L g is:

EQUATION

The above definition of the Lipschitz constant depends on all pairs of inputs in the domain R m × R m , (thus, global). However, one can define the local Lipschitz constant based on the sensitivity of f in the vicinity of a given point x. Precisely, at x, for an arbitrarily small δ > 0, the local Lipschitz constant is computed on the open ball of radius δ centered at x. Let h ∈ R m , h p < δ, then, similar to L g , the local Lipschitz constant of f at x, L l (x), is greater

EQUATION

A function is said to be locally Lipschitz with local Lipschitz constant L l if for all x ∈ R m he function is L l locally-Lipschitz at x. Thus, L l = sup x∈R m L l (x). Notice that the Lipschitz constant (global or local), greatly depends on the chosen norms. When p = q = 2, the upperbound on the local Lipschitz constant at x boils down to the 2-matrix norm (maximum singular value) of the Jacobian J f (x) (see last equality of (2)). With these preliminary definitions, in Section 3, we discuss more optimistic (or empirical) estimates of L l and L g , its link with generalization and then in Section 5,we show empirically the effect of SRN on them and on generalization.

The local Lipschitz upper-bound for Neural Networks As mentioned earlier (2), L l (x) = J f (x) p,q , where, in the case of NNs (proof along with why it is loose in Appendix C)

EQUATION

3. WHY STABLE RANK NORMALIZATION?:

Lipschitz alone is not sufficient Although learning low Lipschitz functions has been shown to provide better generalization (Anthony & Bartlett, 2009; Bartlett et al., 2017; Neyshabur et al., 2018; 2015; Yoshida & Miyato, 2017; Gouk et al., 2018) , enable stable training of GANs (Arjovsky et al., 2017; Gulrajani et al., 2017; Miyato et al., 2018) and help provide robustness against adversarial attacks (Cisse et al., 2017) , controlling Lipschitz upper bound alone is not sufficient to provide assurance on the generalization error. One of the reasons is that it is scale-dependent, implying, for example, even though scaling an entire ReLU network would not alter the classification behaviour, it can massively increase the Lipschitz constant and thus the theoretical generalization bounds. This suggests that either the bound is of no practical utility, or at least one should regulate both-the Lipschitz constant, and the stable rank (scale-independent)-in a hope to see improved generalization in practice.

Stable rank controls the noise-sensitivity As shown by Arora et al. (2018) , one of the critical properties of generalizable NNs is low noise sensitivity-the ability of a network to preferentially carry over the true signal in the data. For a given noise distribution N , it can be quantified as

Φ f θ ,N = max x∈D Φ f θ ,N (x) , where Φ f θ ,N (x) := E η∼N f θ (x + η x ) -f θ (x) 2 f θ (x) 2 .

For a linear mapping with parameters W and the noise distribution being normal-N (0, I), it can be shown that Φ f W ,N ≥ srank(W) (c.f. Proposition 3.1 in Arora et al. (2018) ). Thus, decreasing the stable rank directly decreases the lower bound of the noise sensitivity. In Figure 1 , we show Φ f θ ,N of a ResNet110 trained on CIFAR100. Note that although the Lipschitz upper bound of SRN and SN are the same, SRN (algorithmic details in Section 4) is much less sensitive to noise as the constraints imposed enforce the stable rank to decrease to 30% of its original value, which in effect reduces the noise sensitivity.

Figure 1 : Noise Sensitivity (lower the better). Test accuracy: SRN (73.1%), SN (71.5%), and Vanilla (72.4%).

Stable rank impacts empirical Lipschitz constant It is apparent that the Lipschitz constant upper bound (

d i W i 2 )

, along with being scale-dependent, also is data-independant and hence, provides a pessimistic estimate of the behaviour of a model on a particular task or dataset. Considering this, a relatively optimistic estimate of the model's behaviour would be an empirical estimate of the Lipschitz constant (L e ) on a task-specific dataset5 . Note that local L e is just the norm of the Jacobian at a given point6 . Empirically, Novak et al. (2018) provided results showing how local L e (in the vicinity of train data) is correlated with the generalization error of NNs. This observation is further supported by the work of Wei & Ma; Nagarajan & Kolter (2019) ; Arora et al. (2018) whereby the variants of L e are used to derive generalization bounds. Thus, a tool that favours low L e is likely to provide better generalization behaviour in practice.

To this end, we first consider a simple two layer linear-NN example in Appendix B.2 and show that low rank mappings do favour low L e . Since direct minimization of rank for NNs is non-trivial, the expectation is that learning low stable rank (softer version of rank) might induce similar behaviour. We experimentally validate this hypothesis by showing that, as we decrease the stable rank, the empirical Lipschitz decreases. This shows SRN indeed prefers mappings with a low empirical Lipschitz constant.

4. STABLE RANK NORMALIZATION:

Here we provide a theoretically sound procedure to do SRN. A big challenge in stable rank normalization comes from the fact that it is scale-invariant (refer Definition 2.1), thus, any normalization scheme that modifies W = i σ i u i v i to W = i σi η u i v i will have no effect on the stable rank, making SRN non-trivial. Examples of such schemes are SN (Miyato et al., 2018) where η = σ 1 , and Frobenius normalization where η = W F . As will be shown, our approach to stable rank normalization is optimal and efficient. Note, the widely used SN (Miyato et al., 2018) is not optimal (proof in Appendix A.2).

The SRN Problem Statement Given a matrix W ∈ R m×n with rank p and spectral partitioning index k (0 ≤ k < p), we formulate the SRN problem as:

EQUATION

)

where, 1 ≤ r < srank(W) is the desired stable rank, λ i s and σ i s are the singular values of W k and W, respectively. The partitioning index k is used for the singular value (or the spectrum) preservation constraint. It gives us the flexibility to obtain W k such that its top k singular values are exactly the same as that of the original matrix. Note, the problem statement is more general in the sense that putting k = 0 removes the spectrum preservation constraint.

The Solution to SRN The optimal unique solution to the above problem is provided in Theorem 1 and proved in Appendix A.1. Note, at k = 0, the problem (4) is non-convex, otherwise convex.

Theorem 1. Given a real matrix W ∈ R m×n with rank p, a target spectrum (or singular value) preservation index k (0 ≤ k < p), and a target stable rank of r (1 ≤ r < srank(W)), the optimal solution W k to problem (4) is

W k = γ 1 S 1 + γ 2 S 2 , where S 1 = max(1,k) i=1 σ i u i v i and S 2 = W -S 1 . {σ i } k i=1 , {u i } k i=1

and {v i } k i=1 are the top k singular values and vectors of W, and, depending on k, γ 1 and γ 2 are defined below. For simplicity, we first define γ =

√ rσ 2 1 -S1 2 F S2 F , then

a) If k = 0 (no spectrum preservation), the problem becomes non-convex, the optimal solution to which is obtained for

γ 2 = γ + r -1 r and γ 1 = γ 2 γ , when r > 1. If r = 1, then γ 2 = 0 and γ 1 = 1. Since, in this case, S 1 2 F = σ 2 1 , γ = √ r-1σ1 S2 F . b) If k ≥ 1, the problem is convex. If r ≥ S1 2 F σ 2 1

the optimal solution is obtained for γ 1 = 1, and γ 2 = γ and if not, the problem is not feasible. c) Also, W k -W F monotonically increases with k for k ≥ 1.

Intuitively, Theorem 1 partitions the given matrix into two parts, depending on k, and then scales them differently in order to obtain the optimal solution. The value of the partitioning index k is a design choice. If there is no particular preference to k, then k = 0 provides the most optimal solution. We provide a simple example to better understand this. Given W = I 3 (rank = srank(W) = 3), the objective is to project it to a new matrix with stable rank of 2. Solutions to this problem are:

EQUATION

Here, W 1 is obtained using the standard rank minimization (Eckart-Young-Mirsky (Eckart & Young, 1936) ) while W 2 and W 2 are the solutions of Theorem 1 with k = 1 and k = 0, respectively. It is easy to verify that the stable rank of all the above solutions is 2. However, the Frobenius distance (lower the better) of these solutions from the original matrix follows the order

W -W 1 F > W -W 2 F > W -W 3 F

. As evident from the example, the solution to SRN, instead of completely removing a particular singular value, scales them (depending on k) such that the new matrix has the desired stable rank. Note that for W 1 (true for any k ≥ 1), the spectral norm of the original and the normalized matrices are the same, implying, γ 1 = 1. However, for k = 0, the spectral norm of the optimal solution is greater than that of the original matrix. It is easy to verify from Theorem 1 that as k increases, γ 2 decreases. Thus, the amount of scaling required for the second partition S 2 is more aggressive. In all situations, the following inequality holds:

γ 2 ≤ 1 ≤ γ 1 . Algorithm 1 Stable Rank Normalization Require: W ∈ R m×n , r, k ≥ 1 1: S1 ← 0, β ← W 2 F , η ← 0, l ← 0 2: for i ∈ {1, • • • , k} do 3: {ui, vi, σi} ← SV D(W, i) 4:

Power method to get i-th singular value 5:

if r ≥ σ 2 i + η /σ 2 1 then 6: S1 ← S1 + σiuiv i 7: η ← η + σ 2 i , β ← β -σ 2 i 8: l ← l + 1 9: else 10: break 11: end if 12: end for 13: η ← rσ 2 1 -η 14: return W l ← S1 + η β (W -S1), l

Algorithm 2 SRN for a Linear Layer in NN

Require: W ∈ R m×n , r, learning rate α, mini- batch dataset D 1: Initialize u ∈ R m with a random vector. 2: v ← W u W u , u ← W v W v 3: Perform power iteration 4: σ(W) = u Wv 5: W f = W/σ(W) Spectral Normalization 6: W = W f -uv 7: if W F ≤ √ r -1 then 8: return W f 9: end if 10: W f = uv + W √ r-1 W F Stable Rank Normalization 11: return W ← W -α∇ W L(W f , D)

Algorithm for Stable Rank Normalization We provide a general procedure in Algorithm 1 to solve the stable rank normalization problem for k ≥ 1 (the solution for k = 0 is straightforward from Theorem 1). Claim 2 provides the properties of the algorithm. The algorithm is constructed so that the prior knowledge of the rank of the matrix is not necessary. Claim 2. Given a matrix W, the desired stable rank r, and the partitioning index k ≥ 1, Algorithm 1 requires computing the top l (l ≤ k) singular values and vectors of W. It returns W l and the scalar l such that srank( W l ) = r, and the top l singular values of W and W l are the same. If l = k, then the solution provided is the optimal solution to the problem (4) with all the constraints satisfied, otherwise, it returns the largest l up to which the spectrum is preserved.

Combining Stable Rank and Spectral Normalization for NNs Following the arguments provided in Section 1 and 3, for better generalizability, we propose to normalize both the stable rank and the spectral norm of each linear layer of a NN simultaneously. To do so, we first perform approximate SN (Miyato et al., 2018) , and then perform optimal SRN (using Algorithm 1). We use k = 1 to ensure that the first singular value (which is now normalized) is preserved. Algorithm 2 provides a simplified procedure for the same for a given linear layer of a NN. Note, the computational cost of this algorithm is exactly the same as that of SN, which is to compute the top singular value using the power iteration method.

5. EXPERIMENTS:

Dataset and Architectures For classification, we perform experiments on ResNet-110 (He et al., 2016) , WideResNet-28-10 (Zagoruyko & Komodakis, 2016) , DenseNet-100 (Huang et al., 2017) , VGG-19 (Simonyan & Zisserman, 2014) , and AlexNet (Krizhevsky & Hinton, 2009) using the CIFAR100 (Krizhevsky & Hinton, 2009) dataset. We present further experiments with CIFAR10 in Appendix D.1 in Figure 10 and 11. We train them using standard training recipes with SGD, using a learning rate of 0.1 (except AlexNet where we use a learning rate of 0.01), and a momentum of 0.9 with a batch size of 128 (further details in Appendix D). In addition to training for a fixed number of epochs, we also present results in the Appendix in Figure 8 and 9 where the training accuracy (as opposed to number of iterations) is used as a stopping criterion to show that our regularizor performs well with a range of stopping criterions.

For GAN experiments, we use CIFAR100, CIFAR10, and CelebA (Liu et al., 2015) datasets. We show results on both, conditional and unconditional GANs. Please refer to Appendix E.1 for further details about the training setup.

Choosing stable rank Given a matrix W ∈ R m×n , the desired stable rank r is controlled using a single hyperparameter c as r = c min(m, n), where c ∈ (0, 1]. For simplicity, we use the same c for Miyato et al., 2018) , WGAN-GP (Gulrajani et al., 2017) , and orthonormal regularization GAN (Ortho-GAN) (Brock et al., 2016) .

Result Overview:

• SRN improves classification accuracy on a wide variety of architectures.

• Normalizing stable rank improves the learning capacity of spectrally normalized networks.

• SRN shows remarkably less memorization, even on settings very hard to generalize.

• SRN shows much improved generalization behaviour evaluated using recently proposed sample complexity measures. • As we decrease the stable rank, the empirical Lipschitz of SRN-GAN decreases. Proving our arguments provided in Section 3. • SRN-GAN provides much improved Neural divergence score (ND) (Gulrajani et al., 2019) compared to SN-GAN, proving that it is robust to memorization in GANs as well.

• SRN-GAN also provide improved Inception and FID scores in all our experiments (except one where SN-GAN is better).

5.1. CLASSIFICATION EXPERIMENTS:

We perform each experiment 5 times using a new random seed each time and report the mean, and the 75% confidence interval for the test error in Figure 2 . These experiments show that the test accuracy of SRN, on a wide variety NNs, is always higher than the Vanilla and SN (except for SRN-50 on Alexnet where SRN and SN are almost equal). However, SN performs slightly worse than Vanilla for WideResNet-28 and ResNet110. The fact that SRN does involve SN, combined with the above statement, indicate that even though SN reduced the learning capability of these networks, normalizing stable rank must have improved it significantly in order for SRN to outperform Vanilla. For example, in the case of ResNet110, SN is 71.5% accurate whereas SRN provides an accuracy of 73.2%. In addition to this, we would like to note that even though SN is being used extensively for the training of GANs, it is not a popular choice when it comes to training standard NNs for classification. We suspect that this is because of the decrease in the capacity, which we have shown to be increased by the stable rank normalization, proving the worth of SRN for classification tasks as well.

5.2. STUDY OF GENERALIZATION BEHAVIOUR:

Our last set of experiments established that SRN provides improved classification accuracies on various NNs. Here we study the generalization behaviour of these models. Quantifying generalization behaviour is non-trivial and there is no clear answer to it. However, we utilize recent efforts that explore the theoretical understanding of generalization and use them to study it in practice.

Shattering Experiments To inspect the generalization behaviour in NNs we begin with the shattering experiment (Zhang et al., 2016) . It is a test of whether the network can fit the training data well but not a label-randomized version of it (each image of the dataset is assigned a random label). As there is no correlation of the labels with the data points P (y|x) is essentially uninformative because it is uniformly random. Thus, the test accuracy on this task is almost 1%. A high training accuracywhich indicates a high generalization gap (difference between train and test accuracy) can be achieved only by memorizing the train data7 . Figure 3 shows that SRN reduces memorization on random labels (thus, reduces the estimate of the Rademacher complexity (Zhang et al., 2016) ). Note, as shown in the classification experiments, the same model was able to achieve the highest training accuracy when the labels were not randomized. • Spec-L1: Bartlett et al., 2017) , . 2,1 is the matrix 2-1 norm.

L i=1 Wi 2 2 L i=1 W i 2 /3 2,1 W i 2 /3 2 3 /γ 2 (

• Jac-Norm:

L i=1 hi 2 Ji 2/γ (Wei & Ma)

, where h i is the i th hidden layer and

J i = ∂γ ∂hi

Histogram of the Empirical Lipschitz Constant (eLhist) We evaluate above mentioned sample complexity measures on 10, 000 points from the dataset and plot the distribution of the log using a histogram shown in Figure 4 . The more to the left the histogram, the better is the generalization capacity of the network.

For better clarity, we provide the 90 percentile for each of these histograms in Table 5 in Appendix D.1.

As the plots and the table show, both SRN and SN produces a much smaller quantity than a Vanilla network and in 7 out of the 9 cases, SRN is better than SN. The difference between SRN and SN is much more significant in the case of Jac-Norm. As this depend on the empirical lipschitzness, it provides the empirical validation of our arguments in Section 3.

Above experiments indicate that SRN, while providing enough capacity for the standard classification task, is remarkably less prone to memorization and provides improved generalization.

5.3. TRAINING OF GENERATIVE ADVERSARIAL NETWORKS (SRN-GAN):

In GANs, there is a natural tension between the capacity and the generalizability of the discriminator. The capacity ensures that if the generated distribution and the data distribution are different, the discriminator has the ability to distinguish them. At the same time, the discriminator has to be generalizable, implying, the class of hypothesis should be small enough to ensure that it is not just memorizing the dataset. Based on these arguments, we use SRN in the discriminator of GAN which we call SRN-GAN, and compare it against SN-GAN, WGAN-GP, and orthonormal regularization based GAN (Ortho-GAN).

Along with providing results using evaluation metrics such as Inception score (IS) (Salimans et al., 2016) , FID (Heusel et al., 2017) , and Neural divergence score (ND) (Gulrajani et al., 2019) , we use histograms of the empirical Lipschitz constant, refered to as eLhist from now onwards, for the purpose of analyses. For a given trained GAN (unconditional), we create 2, 000 pairs of samples, where each pair (x i , x j ) consists of x i (randomly sampled from the 'real' dataset) and x j (randomly sampled from the generator). Each pair is then passed through the discriminator to compute f (xi)-f (xj ) 2/ xi-xj 2 , which we then use to create the histogram. In the conditional setting, we sample a class from a discrete uniform distribution, and then follow the same approach as described for the unconditional setting. 5a , lowering the value of c (aggressive reduction in the stable rank) moves the histogram towards zero, implying, lower empirical Lipschitz constant. This validates our arguments provided in Section 3. Lowering c also improves inception score, however, extreme reduction in the stable rank (c = 0.1) dramatically collapses the histogram to zero and also drops the inception score significantly. This is due to the fact that at c = 0.1, the capacity of the discriminator is reduced to the point that it is not able to learn to differentiate between the real and the fake samples anymore.

Table 2 and 3 show that SRN-GAN consistently provide better FID score and an extremely competitive inception score on CIFAR10 (both conditional and unconditional setting) and CIFAR100 (unconditional setting). In Table 4 , we compare the ND loss on CIFAR10 and CelebA datasets. Note, ND has been looked as a metric more robust to memorization than FID and IS in recent works (Gulrajani et al., 2019; Arora & Zhang, 2017) . We report our exact setting to compute ND in Appendix E.1. We essentially report the loss incurred by a fresh classifier trained to discriminate the generator distribution and the data distribution. Thus higher the loss, the better the generated images. As evident, SRN-GAN provides better ND scores on both datasets. For a qualitative analysis of the images, we compare generations in both conditional and unconditional setting in Appendix F. 5b , we provide eLhist for comparing different approaches. Random-GAN, as expected, has a low empirical Lipschitz constant and extremely poor inception score. Unsurprisingly, WGAN-GP has a lower L e than Random-GAN, due to its explicit constraint on the Lipschitz constant, while providing a higher inception score. On the other hand, SRN-GAN, by virtue of its softer constraints on the Lipschitz constant, trades off a higher Lipschitz constant for a better inception score-highlighting the flexibility provided by SRN. Additional experiments in Appendix E.2 show more detailed behaviour of GANs in regards to empirical lipschitz in a variety of settings.

6. CONCLUSION:

We proposed a new normalization (SRN) that allows us to constrain the stable rank of each affine layer of a NN, which in turn learns a mapping with low empirical Lipschitz constant. We also provide optimality guarantees of SRN. On a variety of neural network architectures, we showed that SRN improves the generalization and memorization properties of a standard classifier. In addition, we show that SRN improves the training of GANs and provide better inception, FID, and ND scores. 

A TECHNICAL PROOFS:

Here we provide an extensive proof of Theorem 1 (Appendix A.1). We also provide the optimal solution to the spectral norm problem in Appendix A.2. Auxiliary lemmas on which our proof depends are provided in Appendix A.3.

A.1 PROOF FOR OPTIMAL STABLE RANK NORMALIZATION. (MAIN THEOREM)

Theorem 1. Given a real matrix W ∈ R m×n with rank p, a target spectrum (or singular value) preservation index k (0 ≤ k < p), and a target stable rank of r (1 ≤ r < srank(W)), the optimal solution W k to problem (4) is

W k = γ 1 S 1 + γ 2 S 2 , where S 1 = max(1,k) i=1 σ i u i v i and S 2 = W -S 1 . {σ i } k i=1 , {u i } k i=1

and {v i } k i=1 are the top k singular values and vectors of W, and, depending on k, γ 1 and γ 2 are defined below. For simplicity, we first define γ =

√ rσ 2 1 -S1 2 F S2 F , then

a) If k = 0 (no spectrum preservation), the problem becomes non-convex, the optimal solution to which is obtained for

γ 2 = γ + r -1 r and γ 1 = γ 2 γ , when r > 1. If r = 1, then γ 2 = 0 and γ 1 = 1. Since, in this case, S 1 2 F = σ 2 1 , γ = √ r-1σ1 S2 F . b) If k ≥ 1, the problem is convex. If r ≥ S1 2 F σ 2 1

the optimal solution is obtained for γ 1 = 1, and γ 2 = γ and if not, the problem is not feasible. c) Also, W k -W F monotonically increases with k for k ≥ 1.

Proof. Here we provide the proof of Theorem 1 (in the main paper) for all the three cases with optimality and uniqueness guarantees. Let W k be the optimal solution to the problem for any of the two cases. From Lemma 5, the SVD of W and W k can be written as W = UΣV and

W k = UΛV , respectively. Then, L = W -W k 2 F = Σ -Λ, Σ -Λ F . From now onwards,

we denote Σ and Λ as vectors consisting of the diagonal entries, and ., . as the vector inner product10 .

Proof for Case (a): In this case, there is no constraint enforced to preserve any of the singular values of the given matrix while obtaining the new one. The only constraint is that the new matrix should have the stable rank of r. Let us assume Σ

= (σ 1 , • • • , σ p ), Σ 2 = (σ 2 , • • • , σ p ), Λ = (λ 1 , • • • , λ p ) and Λ 2 = (λ 2 , • • • , λ p ).

Using these notations, we can write L as:

EQUATION

Using the stable rank constraint srank(

W k ) = r, which is r = 1 + p j=2 λ 2 j λ 2 1 .

Case for r > 1 If r > 1 we obtain the following equality constraint, making the problem nonconvex.

EQUATION

However, we will show that the solution we obtain is optimal and unique. Substituting ( 7) into (6) we get

EQUATION

Setting ∂L ∂Λ 2 = 0 to get the family of critical points

2Λ 2 r -1 + 2Λ 2 - 4σ 1 Λ 2 2 (r -1) Λ 2 , Λ 2 -2Σ 2 = 0 =⇒ Σ 2 = Λ 2 1 r -1 + 1 - σ 1 1 (r -1) Λ 2 , Λ 2 (9) =⇒ Σ 2 [i] λ 2 [i] = 1 r -1 + 1 - σ 1 1 (r -1) Λ 2 , Λ 2 = 1 γ 2 ∀ 1 ≤ i ≤ p (10)

As the R.H.S. of 10 is independant of i, the above equality implies that all the critical points of ( 8) are a scalar multiple of Σ 2 , implying, Λ 2 = γ 2 Σ 2 . Note that the domain of Λ 2 are all strictly positive vectors and thus, we can ignore the critical point at Λ 2 = 0. Substituting this into (9) we obtain

Σ 2 = γ 2 Σ 2 1 r -1 + 1 - σ 1 γ 2 (r -1) Σ 2 , Σ 2

Using the fact that Σ 2 , Σ 2 = S 2 2 F in the above equality and with some algebraic manipulations, we obtain

γ 2 = γ+r-1 r where, γ = √ r-1σ1 S2 F . Note, r ≥ 1, γ ≥ 0, and Σ ≥ 0, implying, Λ 2 = γ 2 Σ 2 ≥ 0.

Local minima: Now, we will show that Λ 2 is indeed a minima of (8). To show this, we compute the hessian of L. Recall that

∂L ∂Λ = 2r r -1 Λ - 2σ 1 Λ (r -1) Λ 2 2 -2Σ 2 H = ∂ 2 L ∂ 2 Λ = 2r r -1 I - 2σ 1 (r -1) Λ 2 2 Λ 2 I - 1 Λ 2 ΛΛ = 2 r r -1 - σ 1 Λ 2 (r -1) Λ 2 2 I + 2σ 1 √ r -1 Λ 3 2 ΛΛ Now we need to show that H at the solution Λ 2 is PSD i.e. ∀ x ∈ R p-1 , x H (Λ 2 )x ≥ 0 x Hx = 2 r r -1 - σ 1 Λ 2 (r -1) Λ 2 2 x 2 2 + 2σ 1 √ r -1 Λ 3 2 x ΛΛ x (a) ≥ 2 r r -1 - σ 1 Λ 2 (r -1) Λ 2 2 x 2 2 (b) ≥ 2 r r -1 - σ 1 (r -1) λ 1 x 2 2 (c) = 2r r -1 1 - γ (γ + r -1) x 2 2 (d) ≥ 2r r -1 1 - 1 (1 + r -1) x 2 2 = 2 x 2 2 ≥ 0

Here (a) is due to the fact that the matrix ΛΛ is an outer product matrix and is hence PSD. (b) follows due to ( 7) and (c) follows by substituting λ 1 = γ 1 σ 1 and then the value of γ 1 . Finally (d)

follows as 1 - γ (γ + r -1)

is decreasing with respect to γ and we know that γ < 1 due to the assumption that srank(W) < r. Thus, we can substitute γ = 1 to find the minimum value of the expression. This concludes our proof that Λ 2 is indeed a local minima of L.

Uniqueness::

The uniqueness of Λ 2 as a solution to (8) is shown in Lemma 6 and is also guaranteed by the fact that γ 2 has a unique value. Using Λ 2 = γ 2 Σ 2 and λ 1 = γ 1 σ 1 in (7), we obtain a unique solution γ 1 = γ2 γ . Now, we need to show that it is also an unique solution to Theorem 1.

For all solutions to Theorem 1 that have singular vectors which are different than that of W, by Lemma 5, the matrix formed by replacing the singular vectors of the solution with that of W is also a solution. Thus, if there were a solution with different singular values than W k , it should have appeared as a solution to (8). However, we have shown that (8) has a unique solution.

Now, we need to show that among all matrices with the same singular values as that of W k , W k is strictly better in terms of W -W k . This requires a further assumption that every non-zero singular value of Λ 2 has a multiplicity of 1 i.e. they are all distinctly unique. Intuitively, this doesn't allow to create a different matrix by simply interchanging the singular vectors associated with the equal singular values. As the elements of Σ 2 are distinct, the elements of Λ 2 = γ 2 Σ 2 are also distinct and thus by the second part of Lemma 5, W k is strictly better, in terms of W -W k , than all matrices which have the same singular values as that of W k . This concludes our discussion on the uniqueness of the solution.

Case for r = 1: Substituting r = 1 in the constraint r = 1

+ p j=2 λ 2 j λ 2 1 we get r -1 = p j=2 λ 2 j λ 2 1 = 0 =⇒ p j=2 λ 2 j = 0

As it is a sum of squares, each of the individual elements is also zero i.e. λ j = 0 ∀2 ≤ j ≤ p. Substituting this into (6), we get the following quadratic equation in λ 1

EQUATION

which is minimized at λ 1 = σ 1 , thus proving that γ 1 = 1 and γ 2 = 0.

Proof for Case (b): In this case, the constraints are meant to preserve the top k singular values of the given matrix while obtaining the new one. Let

Σ 1 = (σ 1 , • • • , σ k ) , Σ 2 = (σ k+1 , • • • , σ p ) , Λ 1 = (λ 1 , • • • , λ k ) , Λ 2 = (λ k+1 , • • • , λ p ).

Since satisfying all the constraints imply Σ 1 = Λ 1 , thus,

EQUATION

The above equality constraint makes the problem non-convex. Thus, we relax it to srank( W k ) ≤ r to make it a convex problem and show that the optimality is achieved with equality. Let rσ 2 1 -Σ 1 , Σ 1 = η. Then, the relaxed problem can be written as

min Λ2∈R p-k L := Σ 2 -Λ 2 , Σ 2 -Λ 2 s.t. Λ 2 ≥ 0, Λ 2 , Λ 2 ≤ η.

We introduce the Lagrangian dual variables Γ ∈ R p-k and µ corresponding to the positivity and the stable rank constraints, respectively. The Lagrangian can then be written as

L (Λ 2 , Γ, µ) Γ≥0,µ≥0 = Σ 2 -Λ 2 , Σ 2 -Λ 2 + µ ( Λ 2 , Λ 2 -η) -Γ, Λ 2 (13)

Using the primal optimality condition ∂L ∂Λ 2 = 0, we obtain

EQUATION

Using the above condition on Λ 2 with the constraint Λ 2 , Λ 2 ≤ η, combined with the stable rank constraint of the given matrix W that comes with the problem definition, srank(W) > r (which implies Σ 2 , Σ 2 > η), the following inequality must be satisfied for any Γ ≥ 0

1 < Σ 2 , Σ 2 η ≤ Γ + Σ 2 , Γ + Σ 2 η ≤ (1 + µ) 2 (15)

For the above inequality to satisfy, the dual variable µ must be greater than zero, implying, Λ 2 , Λ 2 -η must be zero for the complementary slackness to satisfy. Using this with the optimality condition ( 14) we obtain

(1 + µ) 2 = Γ + 2Σ 2 , Γ + 2Σ 2 4η

Substituting the above solution back into the primal optimality condition we get

Λ 2 = (Γ + 2Σ 2 ) √ η Γ + 2Σ 2 , Γ + 2Σ 2 (16)

Finally, we use the complimentary slackness condition Γ Λ 2 = 011 to get rid of the dual variable Γ as follows

Γ (Γ + 2Σ 2 ) √ η Γ + 2Σ 2 , Γ + 2Σ 2 = 0

It is easy to see that the above condition is satisfied only when Γ = 0 as Σ 2 ≥ 0 and η > 0. Therefore, using Γ = 0 in ( 16) we obtain the optimal solution of Λ 2 as

Λ 2 = √ η Σ 2 , Σ 2 Σ 2 = rσ 2 1 -S 1 2 F S 2 2 F Σ 2 = γΣ 2 (17) Proof for Case (c): The monotonicity of W k -W F for k ≥ 1 is shown in Lemma 3.

Note that by the assumption that srank(W) < r, we can say that γ < 1. Therefore in all the cases γ 2 < 1. Let us look at the required conditions for γ 1 ≥ 1 to hold. When k ≥ 1, γ 1 = 1 holds. When k = 0, for γ 1 > 1 to be true, γ 2 < γ should hold, implying, (γ -1) < r (γ -1), which is always true as r > 1 (by the definition of stable rank). Lemma 3. For k ≥ 1, the solution to the optimization problem (4) obtained using Theorem 1 is closest to the original matrix W in terms of Frobenius norm when only the spectral norm is preserved, implying, k = 1.

Proof. For a given matrix W and a partitioning index k ∈ {1, • • • , p}, let W k = S k 1 + γS k 2 be the matrix obtained using Theorem 1. We use the superscript k along with S 1 and S 2 to denote that this refers to the particular solution of W k . Plugging the value of γ and using the fact that S k 2 F = 0, we can write

W -W k F = (1 -γ) S k 2 F = S k 2 F -rσ 2 1 -S k 1 2 F = S k 2 F -rσ 2 1 -W 2 F + S k 2 2 F . Thus, W -W k F can be written in a simplified form as f (x) = x - √ a + x 2 , where x = S k 2 F

and a = rσ 2 1 -W 2 F . Note, a ≤ 0 as 1 ≤ r ≤ srank(W), and a + x 2 ≥ 0 because of the condition in Theorem 1. Under these settings, it is trivial to verify that f is a monotonically decreasing function of x. Using the fact that as the partition index k increases, x decreases, it is straightforward to conclude that the minimum of f (x) is obtained at k = 1.

A.2 PROOF FOR OPTIMAL SPECTRAL NORMALIZATION:

The widely used spectral normalization (Miyato et al., 2018) where the given matrix W ∈ R m×n is divided by the maximum singular value is an approximation to the optimal solution of the spectral normalization problem defined as

arg min W W -W 2 F (18) s.t. σ( W) ≤ s,

where σ( W) denotes the maximum singular value and s > 0 is a hyperparameter. The optimal solution to this problem is shown in Algorithm 3. In what follows we provide the optimality proof Algorithm 3 Spectral Normalization

Require: W ∈ R m×n , s 1: W 1 ← 0, p ← min(m, n) 2: for k ∈ {1, • • • , p} do 3: {u k , v k , σ k } ← SV D(W, k)

perform power method to get k-th singular value 4:

if σ k ≥ s then 5: end if 10: end for 11: return W ← W 1 + W of Algorithm 3 for the sake of completeness. Let SVD (W) = UΣV and let us assume that Z = SΛT is a solution to the problem 18. Trivially, X = UΛV also satisfies σ (X) ≤ s. Now, W -

W 1 ← W 1 + s u k v k 6: W ← W -σ k u k v k 7:

X 2 F = U (Σ -Λ) V 2 F = (Σ -Λ) 2 F ≤ W -Z 2 F

, where the last inequality directly comes from Lemma 4. Thus the singular vectors of the optimal solution must be the same as that of W. This boils down to solving the following problem

EQUATION

)

Here, without loss of generality, we abuse notations by considering Λ and Σ to represent the diagonal vectors of the original diagonal matrices Λ and Σ, and Λ [i] as its i-th index. It is trivial to see that the optimal solution with minimum Frobenius norm is achieved when

Λ [i] = Σ [i] , if Σ [i] ≤ s s, otherwise.

This is exactly what Algorithm 3 implements.

A.3 AUXILIARY LEMMAS:

Lemma 4. [Reproduced from Theorem 5 in Mirsky (1960) ] For any two matrices A, B ∈ R m×n with singular values as

σ 1 ≥ • • • ≥ σ n and ρ 1 ≥ • • • ≥ ρ n , respectively A -B 2 F ≥ n i=1 (σ i -ρ i ) 2

Proof. Consider the following symmetric matrices

X = 0 A A 0 , Y = 0 B B 0 , Z = 0 A -B (A -B) 0 Let τ 1 ≥ • • • ≥ τ n be the singular values of Z.

Then the set of characteristic roots of X, Y and Z in descending order are {ρ

EQUATION

Lemma 5. Let A, B ∈ R m×n where SVD(A) = UΣV and B is the solution to the following problem

EQUATION

Then, SVD (B) = UΛV where Λ is a diagonal matrix with non-negative entries. Implying, A and B will have the same singular vectors.

Proof. Let us assume that Z = SΛT is a solution to the problem 21 where S = U and T = V.

Trivially, X = UΛV also lies in the feasible set as it satisfies srank(X) = r (note stable rank only depends on the singular values). Using the fact that the Frobenius norm is invariant to unitary transformations, we can write A -

X 2 F = U (Σ -Λ) V 2 F = (Σ -Λ) 2 F . Combining this with Lemma 4, we obtain A -X 2 F = (Σ -Λ) 2 F ≤ A -Z 2 F .

Since, S = U and T = V, we can further change ≤ to a strict inequality <. This completes the proof.

Generally speaking, the optimal solution to problem 21 with constraints depending only on the singular values (e.g. stable rank in this case) will have the same singular vectors as that of the original matrix.

Further the inequality in (20) can be converted into a strict inequality if neither of A and B have repeated singular values. Using that strict inequality, if both Σ and Λ have no repeated values, then B is the only solution to (21) that has the singular values of Λ. Lemma 6. Let y 1 = ax 1 + bx 1 and y 2 = ax 2 + bx 2 , where x1 and x2 denotes the unit vectors. Then,

y 1 = y 2 if x 1 = x 2 .

B EMPIRICAL LIPSCHITZ CONSTANT B.1 RELATING EMPIRICAL LOCAL AND GLOBAL LIPSCHITZ CONSTANTS:

Proposition B.1. Let f : R m → R be a Fréchet differentiable function, D the dataset, and Conv (x i , x j ) denotes the convex combination of a pair of samples x i and x j , then ∀p,

q ∈ [1, ∞] such that 1 p + 1 q = 1 max xi,xj ∈D |f (x i ) -f (x j )| x i -x j p ≤ max xi,xj ∈D x∈Conv (xi,xj ) J f (x) q

Proof. Let f : R m → R be a differentiable function on an open set containing x i and x j such that x i = x j . By applying fundamental theorem of calculus

|f (x i ) -f (x j )| = 1 0 ∇f (x i + θ (x j -x i )) (x j -x i ) ∂θ ≤ 1 0 ∇f (x i + θ (x j -x i )) (x j -x i ) ∂θ (a) ≤ 1 0 ∇f (x i + θ (x j -x i )) q (x j -x i ) p ∂θ ≤ 1 0 max θ∈(0,1) ∇f (x i + θ (x j -x i )) q (x j -x i ) p ∂θ = max θ∈(0,1) ∇f (x i + θ (x j -x i )) q (x j -x i ) p 1 0 ∂θ ∴ |f (x i ) -f (x j )| (x j -x i ) p ≤ max θ∈(0,1) ∇f (x i + θ (x j -x i )) q = max x∈Conv (xi,xj ) ∇f (x) q .

The inequality (a) is due to Hölder's inequality.

B.2 EFFECT OF RANK ON THE EMPIRICAL LIPSCHITZ CONSTANTS:

Let f (x) = W 2 W 1 x be a two-layer linear NN with weights W 1 and W 2 . The Jacobian in this case is independent of x. Thus, the local Lipschitz constant is the same for all x ∈ R m , implying, local

L e = L l (x) = L l = W 2 W 1 ≤ W 2 W 1 .

Note, in the case of 2-matrix norm reducing the rank will not affect the upperbound. However, as will be discussed below, rank reduction greatly influences the global L e .

Let x i and x j be random pairs from D and ∆x = 0 be the difference x i -x j , then, the global L e is max {xi,xj }∈D W2W1∆x ∆x

. Let k 1 and k 2 be the ranks, and σ 1 ≥ • • • ≥ σ k1 and λ 1 ≥ • • • ≥ λ k2 the singular values of the matrices W 1 and W 2 , respectively. Let P i = u i ū i be the orthogonal projection matrix corresponding to u i and ūi , the left and the right singular vectors of W 1 . Similarly, we define Q i for W 2 corresponding to v i and vi . Then, W 2 W 1 = k2 i=1 k1 j=1 λ i σ j Q i P j . The upperbound, λ 1 σ 1 , can be achieved if and only if ∆x = ū1 ∆x and u 1 = v1 (a perfect alignment), which is highly unlikely. In practice, not just the maximum singular values, as is the case with the Lipschitz upper-bound, rather the combination of the projection matrices and the singular values play a crucial role in providing an estimate of global L e . Thus, reducing the singular values, which is equivalent to minimizing the rank (or stable rank), will directly affect L e . For example, assigning σ j = 0, which in effect will reduce the rank of W 1 by one, will nullify its influence on all projections associated with P j . Implying, all the k 2 projections σ j ( k2 i=1 λ i Q i )P j that would propagate the input via P j will be blocked. This, in effect, will influence W 2 W 2 ∆x ; hence the global L e . In a more general setting, let k i be the rank of the i-th linear layer, then, each singular value of a j-th layer can influence the maximum of j-1 i=1 k i l i=j+1 k i many paths through which an input can be propagated. Thus, mappings with low rank (stable) will greatly reduce the global L e . Similar arguments can be drawn for local L e in the case of NN with non-linearity.

C THE LOCAL LIPSCHITZ UPPER-BOUND FOR NEURAL NETWORKS:

As mentioned in Section 2, L l (x) = J f (x) p,q , where, in the case of NN, the Jacobian is:

EQUATION

Using ∂z l ∂a l-1 = W l (affine transformation), and applying submultiplicativity of the matrix norms:

EQUATION

Note, most commonly used activation functions φ(.) such as ReLU, sigmoid, tanh and maxout are known to have Lipschitz constant of 1 (if scaled appropriately) 12 , thus, the upper bound can further be written only using the operator norms of the intermediate matrices as

EQUATION

Furthermore L l (x) can be substituted by L l , the local Lipschitz constant, as the upper bound (Eq. ( 24)) is independent of x. Note that this is one of the main reasons why we consider the empirical Lipschitz to better reflect the true behaviour of the function as the NN is never exposed to the entire domain R m but only a small subset dependant on the data distribution.

The other reason why this upper bound is a bad estimate is that the inequality in Eq ( 23) is tight only when the partial derivatives are aligned, implying, ∂z ∂z -1

∂z +1 ∂z 2 = ∂z ∂z -1 2 ∂z +1 ∂z 2

∀l-2 ≤ ≤ l. This problem has been referred to as the problem of mis-alignment and is similar to quantities like layer cushion in Arora et al. (2018) .

D EXPERIMENTAL DETAILS:

WideResNet-28-10 We use a standard WideResNet with 28 layers and a growth factor of 10. In total, the network has 36,539,124 trainable parameters. The network is the standard configuration with batchnorm and ReLU activations and is trained with a weight decay of 1e -4. The learning rate was multiplied by 0.2 after 60, 120, and 160 epochs respectively.

ResNet-110:

The ResNet-110 is a standard 110 layered ResNet with batch Norm and ReLU and has 1, 973, 236 parameters. The network is trained with SGD, an initial learning rate of 0.1, which is multiplied 0.1 after 150 and 250 epochs respectively, a weight decay of 5e -4 and a momentum of 0.9.

Densenet-100:

The DenseNet-100 is a standard 100-layered densenet with Batchnorm and ReLU and has a total of 800, 032 trainable parameters. The network is trained with SGD, an initial learning rate of 0.1, which is multiplied by 0.1 after 150 and 250 epochs respectively, a weight decay of 1e -4, and a momentum of 0.9.

VGG19 The VGG19 model is the standard 19-layered VGG model with Batchnorm and ReLU. It has a total of 20, 548, 392 trainable parameters and is trained with SGD with a momentum of 0.9 and a weight decay of 5e -4. The initial learning rate is 0.1 and is multiplied by 0.1 after 150 and 250 epochs respectively. For the shattering experiments, we used the same architecture and the same training recipe except the initial learning rate, which was deceased to 0.01 as the model failed to learn the random labels with a large learning rate.

AlexNet The Alexnet model is the standard ALexNet model with 4, 965, 092 trainable parameters. It was trained with SGD, with a momentum of 0.9, with an initial learning rate is 0.01, which is multiplied by 0.1 after 150 and 250 epochs respectively. The optimizer was further augmented with a weight decay rate of 5e -4. Please refer to the next section for results on different learning rates and with and without weight decay.

D.1 ADDITIONAL EXPERIMENTS ON GENERALIZATION:

Complexity measures In this section, we provide more details about the various complexity measures we used in Figure 4 .

• Spec-Fro: Neyshabur et al., 2018) . This bound is the main motivation of this paper; the two quantities used to normalize the margin (γ) is the product of spectral norm i.e.

L i=1 W i 2 2 L i=1 srank(W i ) γ 2 (

L i=1 W i 2 2 (or worst case lipschitzness) and sum of stable rank i.e., L i=1 srank(W i ) (or an approximate parameter count like rank of a matrix).

12 implying, maxz ∂φ(z) ∂z p = 1.

• Spec-L1:

L i=1 W i 2 2 L i=1 Wi 2 /3 2,1 Wi 2 /3 2 3 γ 2

, where . 2,1 is the matrix 2-1 norm. As showed by Bartlett et al. (2017) , Spec-L1 is the spectrally normalized margin, and unlike just the margin, is a good indicator of the generalization properties of a network.

• Jac-Norm:

L i=1 h i 2 J i 2 γ (Wei & Ma)

, where h i is the i th hidden layer and J i = ∂γ ∂hi i.e., the Jacobian of the margin with respect to the i th hidden layer (thus, a vector). Note, Jac-Norm depends on the norm of the Jacobian (local empirical Lipschitz) and norm of the hidden layers -additional data-dependent terms compared to Spec-Fro and Spec-L1, thus captures a more realistic (and optimistic) generalization behaviour.

For better clarity regarding Figure 4 , we provide the 90 percentile for each of these histograms in Table 5 . As the plots and the table show, both SRN and SN produces a much smaller quantity than a Vanilla network and in 7 out of the 9 cases, SRN is better than SN. The difference between SRN and SN is much more significant in the case of Jac-Norm. As this depend on the empirical lipschitzness, it provides the empirical validation of our arguments in Section 3. 1 .

Training Accuracy as Stopping Criterion:

In this section we show that our regularizor performs consistently for a different stopping criterion. In particular, we use the train accuracy as a stopping criterion. For Resnet110, WideResnet-28,Densenet-100, and VGG-19 we use a train accuracy of 99% as a stopping criterion and report the test accuracy when that train accuracy was achieved for the first time. For Alexnet, as SRN-30 never achieves a train accuracy higher than 55%, we use 55% Figure 9 : Test accuracies on CIFAR10 for clean data using a stopping criterion based on train accuracy. Higher is better.

as the stopping criterion and plot the test accuracies in Figure 8 . Our results show that SRN-30 and SRN-50 outperform SN and vanilla consistently. In Figure 9 , we show similar plots for CIFAR10.

CIFAR10 experiments In this section, we plot results on CIFAR10 trained using ResNet-110, Desnenet100, WideResNet-28, and Alexnet. In Figure 9 , we plot the test accuracy on clean CIFAR-10 with the training accuracy as the stopping criterion. For all models other than Alexnet, we use 99% training accuracy as the criterion and for Alexnet we use 85%. In Figure 10 , we plot the test accuracy on clean CIFAR10 using the number of epochs as the stopping criterion.The results here are consistent with those in the main paper in that SRN outperforms the vanilla and SN.

In Figure 11 , we plot the training accuracy on CIFAR10 when the labels are randomized for Resnet100, and Alexnet. SRN-50 and SRN-30 are much better than Vanilla and SN in this case. 

E ADDITIONAL EXPERIMENTS ON GANS E.1 GAN EXPERIMENTAL SETUP:

Datasets and Network Architectures Each of the CIFAR datasets contain a total of 50, 000 RGB images in the training set, where each image is of size 32 × 32, and a further 10, 000 RGB images of the same dimension in the test set. The CelebA dataset contains more than 200K images scaled to a size of 64 × 64. The model architecture for both the generator and the discriminator was chosen to be a 32 layered ResNet (He et al., 2016) due to its previous superior performance in other works (Miyato et al., 2018) . We use Adam optimizer (Kingma & Ba, 2014) which depends on three main hyperparameters αthe initial learning rate, β 1 -the first order moment decay rate and β 2 -the second Figure 10 : Test accuracies on CIFAR10 for clean data using the number of epochs as a stopping criterion. Higher is better.

order moment decay rate. We cross-validate these parameters in the set α ∈ {0.0002, 0.0005}, β 1 ∈ {0, 0.5}, β 2 ∈ {0.9, 0.999} and chose α = 0.0002, β 1 = 0.0 and β 2 = 0.999 which performed consistently well in all of the experiments.

GAN objective functions In the case of conditional GANs (Mirza & Osindero, 2014) , we used the conditional batch normalization (Dumoulin et al., 2017) to condition the generator and the projection discriminator (Miyato & Koyama, 2018) to condition the discriminator. The dimension of the latent variable for the generator was set to 128 and was sampled from a zero mean and unit variance Gaussian distribution. For training the model, we used the hinge loss version of the adversarial loss (Lim & Ye, 2017; Tran et al., 2017) in all experiments except the experiments with WGAN-GP.

The hinge loss version was chosen as it has been shown to give consistently better performance in previous works (Zhang et al., 2018; Miyato et al., 2018) . For training the WGAN-GP model, we used the original loss function as described in Gulrajani et al. (2017) .

Evaluation Metrics We use Inception (Salimans et al., 2016) and Frechet Inception Distance (FID) (Heusel et al., 2017) scores for the evaluation of the generated samples. For measuring the inception score, we generate 50, 000 samples, as was recommended in Salimans et al. (2016) . For measuring FID, we use the same setting as Miyato et al. (2018) where we sample 10, 000 data points from the training set and compare its statistics with that of 5, 000 generated samples. In addition, we use a recent evaluation metric called Neural divergence score Gulrajani et al. (2019) which is more robust to memorization. The exact set-up for the same is discussed below. In the case of conditional image generation, we also measure Intra-FID (Miyato et al., 2018) , which is the mean of the FID of the generator, when it is conditioned over different classes. Let FID(G, c) be the FID of the generator G when it is conditioned on the class c ∈ C (where C is the set of classes), then, Intra FID(G) = 1 |C| FID(G, c)

Neural Divergence Setup We train a new classifier inline with the architecture in Gulrajani et al. (2019) . It includes three convolution layers with 16, 32 and 64 channels, a kernel size of 5 × 5 and a stride of 2. Each of these layers are followed by a Swish activation (Ramachandran et al., 2018) and then finally a linear layer that gives a single output. The network is initialized using normal distribution with zero mean and the standard deviation of 0.02, and trained using Adam optimizer with α = 0.0002, β 1 = 0., β 2 = 0.9 for a total of 100, 000 iterations with minibatch of 128 generated samples and 128 samples from the test set13 . We use the standard WGAN-GP loss function, log (1 + exp (f (x fake ))) + log (1 + exp (-x real )), where f represents the network described above. Finally, we generate 1 Million samples from the generator and report the average log (1 + exp (f (x fake ))) over these samples. Higher average value implies better generation as the network in this case is unable to distinguish the generated and the real samples.

E.2 MORE EMPIRICAL LIPSCHITZ PLOTS:

For the purpose of analysis, Figure 13b and 14b shows eLhist for pairs where each sample either comes from the true data or from the generator, and we observe a similar trend. To verify that same results hold in the conditional setup, we show comparisons for GANs with projection discriminator (Miyato & Koyama, 2018) in Figure 12 , 13a and 14a, and observe a similar trend. Further, to see the value of the local Lipschitzness in the vicinity of real and generated samples we also plot the norm of the Jacobian in Figure 15 and 16 in Appendix E.2 and observe mostly a similar trend. In Appendix E.3 (Figure 17 ), we also show that the discriminator training of SRN-GAN is more stable than SN-GAN.

Conditional GANs Figure 12 shows the eLihst of conditional GANs with projection discriminator (Miyato & Koyama, 2018) . Empirical Lipschitzness between real samples and between fake samples. Figure 13 shows the histogram of eLhist of the discriminator for pairs of fake samples i.e. samples generated by the generator. Figure 14 shows eLhist of the discriminator when samples came from the dataset. Jacobian norm in the vicinity of the points Here we compare the Jacobian of the discriminator of the trained models in the vicinity of the samples from the generator and the real dataset. This is a penalized measure in various algorithms Gulrajani et al. (2017); Petzka et al. (2018) (often referred to as local perturbations) and was independently proposed by Kodali et al. (2018) . Figure 15 and Figure 16 show the histogram of the norm of the Jacobian of the discriminator in the vicinity of the generated and the real samples, respectively. To generate these plots, 2, 000 samples were used from the respective distributions. It is interesting to note that the norm is the same for the points in the vicinity of the real data points and the generated data points for the Stable Rank Normalization GAN (SRN-GAN) as well for WGAN-GP whereas it varies between fake and real samples for Spectral Normalization GAN (SN-GAN). 

:

d and Wi

represents the number of layers and the spectral norm of the i-th linear layer Wi, respectively.

e.g. ReLU, tanh, sigmoid, and maxout.

yj is the j-th element of vector y. Only one class is assigned as the ground-truth label to each x.

Here, (a) is by definition of local lipschitzness and (b) is due to the property of norms that for any nonnegative scalar c, cx = c x .

It can be the train-/test-data, the generated data (e.g., in GANs), or some interpolated data points.

For completeness, we provide the relationship between the global and the local Le in Proposition B.1.

The training of all the models of one architecture were stopped after the same number of epochs -double the number of epochs the model were trained on the clean dataset.

These result are reported after 200 epochs. It can be looked on as combined with early stopping, which is a powerful way of avoiding memorizing random labels(Li et al.).

Results are taken fromMiyato et al. (2018). The rest of the results in the tables are generated by us.

., . F represents the Frobenius inner product of two matrices, which in the case of diagonal matrices is the same as the inner product of the diagonal vectors.

is the hadamard product

For CelebA, we used the training set.

Figures and Tables:

Figure 2: Test accuracies on CIFAR100 for clean data. Higher is better.

Figure 3: Train accuracies on CIFAR100 for shattering experiment. Lower indicate less memorization, thus, better.

Figure 5: eLhist for unconditional GAN on CIFAR10. Dashed vertical lines represent 95th percentile. Solid circles and crosses represent the inception score for each histogram. Figure 5a shows SRN-GAN for different stable rank constraints (e.g. 90 implies c = 0.9). Figure 5b compares various approaches. Random-GAN represents random initialization (no training). For SRN-GAN, we use c = 0.7. Empirical Evaluation of Generalization Behaviour When all the factors in training (eg. architecture, dataset, optimizer, among other) as in SRN vs SN vs Vanilla, are fixed, and the only variability is in the normalization, the generalization error can be written as |Train Err -Test Err| ≤ O C alg/m where O (•) ignores the logarithmic terms, m is the number of samples in the dataset, and C alg denotes a measure of sample complexity for a given algorithm. Lower the value of C alg , the better is the generalization. Before we give various expressions for C alg , we first define a common quantity in all these expressions, called the margin γ = f θ (x) [y] -max j =y f θ (x) [j]. It measures the gap between the output of the network on the correct label and the other labels. Now we define three recently proposed sample complexity measures useful to quantify the generalization behaviour with further descriptions in Appendix D.1: • Spec-Fro: L i=1 Wi 2 2

Figure 6: Test Error and Generalization Error of AlexNet trained with SGD with lr = 0.1 on (clean) CIFAR-100. (Lower is better

Figure 7: Training error on randomly labelled CIFAR-100 with a learning rate of 0.01 and with/ with out weight decay. (Higher is better.

Figure8: Test accuracies on CIFAR100 for clean data using a stopping criterion based on train accuracy. Higher is better.

Figure 11: Training accuracy on randomly labelled CIFAR-10 (Lower is better).

Figure 12: Comparison: eLhist of the discriminator in the conditional GAN setting with projection discriminator on CIFAR100.

(a) Conditional GAN with projection discriminator. (b) Unconditional GAN setting.

Figure 13: Comparison: eLhist of the discriminator for pairs of samples selected from the generator on CIFAR10

Figure 14: Comparison: eLhist of the discriminator for pairs of samples from the real distribution on CIFAR10.

(a) Conditional GAN with projection discriminator. (b) Unconditional GAN setting.

Figure 15: Jacobian norm of the discriminator in the neighbourhood of the samples from the generator trained on CIFAR10.

Figure 16: Jacobian norm of the discriminator in the neighbourhood of the samples from the real dataset (CIFAR10).



Figure 21: Image samples generated from the conditional SRN-GAN with projection discriminator.

Highly non-generalizable setting. Training error for ResNet-110 on CIFAR100 with randomized labels, low lr= 0.01, and with and without weight decay. (Higher is better.) The clean test accuracy for this setting is shown in Appendix D.1.We also look specifically at highly non-generalizable settings -low learning rate and without weight decay. As shown in Table1, SRN consistently achieves lower generalization error (by achieving a low train error) both in the presence and the absence of weight decay 8 . Similar results are reported for Alexnet and WideResNet in Appendix D.1.

Table content: <table><tr><td/><td>SRN-50</td><td>SRN-30</td><td>Spectral (SN)</td><td>Vanilla</td></tr><tr><td>WD</td><td colspan="4">12.02 ± 1.77 11.87 ± 0.57 11.13 ± 2.56 10.56 ± 2.32</td></tr><tr><td colspan="5">w/o WD 17.71 ± 2.30 19.04 ± 4.53 17.22 ± 1.94 13.49 ± 1.93</td></tr></table>

Inception and FID score on CIFAR10.

Table content: <table><tr><td>Effect of Stable Rank on eLhist and</td><td/><td/><td/><td/></tr><tr><td>Inception Score As shown in Fig-ure</td><td>Algorithm</td><td>Inception Score</td><td>FID</td><td>Intra-FID</td></tr><tr><td/><td>Orthonormal 1</td><td>7.92 ± .04</td><td>23.8</td><td>-</td></tr><tr><td>Uncond.</td><td>WGAN-GP SN-GAN 1 SRN-70-GAN</td><td>7.86 ± .07 8.22 ± .04 8.53 ± 0.04</td><td>21.7 20.67 19.83</td><td>---</td></tr><tr><td/><td>SRN-50-GAN</td><td>8.33 ± 0.06</td><td>19.57</td><td>-</td></tr><tr><td>Cond.</td><td>SN-GAN SRN-70-GAN SRN-50-GAN</td><td>8.71 ± .04 8.93 ± 0.12 8.76 ± 0.09</td><td>16.04 9 15.92 16.89</td><td>26.24 24.01 27.3</td></tr></table>

CIFAR100 experiments.

Table content: <table><tr><td>Model</td><td colspan="2">CIFAR10 CelebA</td></tr><tr><td>SN-GAN</td><td>10.69</td><td>0.36</td></tr><tr><td colspan="2">SRN-GAN (Our) 11.97</td><td>0.64</td></tr><tr><td>Table 4:</td><td colspan="2">Neural Discriminator</td></tr><tr><td colspan="2">Loss (Higher the better).</td><td/></tr></table>

Colin Wei and Tengyu Ma. Data-dependent sample complexity of deep neural networks via lipschitz augmentation. Helmut Wielandt. An extremum property of sums of eigenvalues. Proceedings of the American Mathematical Society, 6(1):106-106, jan 1955. doi: 10.1090/s0002-9939-1955-0067842-9. Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprint arXiv:1705.10941, 2017., 2017. Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. In Procedings of the British Machine Vision Conference 2016. British Machine Vision Association, 2016. doi: 10.5244/c.30.87.

Table content: <table><tr><td>Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep</td></tr><tr><td>learning requires rethinking generalization. International Conference on Learning Representations</td></tr><tr><td>(ICLR), nov 2016. URL http://arxiv.org/abs/1611.03530.</td></tr><tr><td>Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena. Self-attention generative</td></tr><tr><td>adversarial networks. 2018.</td></tr></table>

Values of 90 percentile of log complexity measures from Figure4. Here ∞ refers to the situations where the product of spectral norm blows up. This is the case in deep networks like ResNet-110 and Densenet-100 where the absence of spectral normalization (Vanilla) allows the product of spectral norm to grow arbitrarily large with increasing number of layers. Lower is better. Figure6shows the test error and generalization error of Alexnet trained with a large learning rate of 0.1. Note that, the model fails to learn completely without weight decay. Generalisation Error decreases monotonically with decreasing c in the stable rank constraint. Test error is the lowest for c = 0.5. The constraint becomes too aggressive for even c lower than that. The slightly more interesting observation is that having a weight decay actually hurts generalization error while it has a slightly positive effect on test error.Low Learning Rate Here, we train a WideResnet-28-10 with SRN, SN, and vanilla methods with an lr = 0.01 and weight decay of 5 × 10 -4 on randomly labelled CIFAR100. for 50 epochs. The results are shown in Table6and it further supports that SRN is more robust to random noise than SN or vanilla methods.

Table content: <table><tr><td>Model</td><td colspan="2">Algorithm</td><td colspan="3">Jac-Norm Spec-L1 Spec-Fro</td></tr><tr><td/><td colspan="2">Vanilla</td><td>17.7</td><td>∞</td><td>∞</td></tr><tr><td>ResNet-110</td><td colspan="2">Spectral (SN)</td><td>17.8</td><td>10.8</td><td>7.4</td></tr><tr><td/><td colspan="2">SRN-30</td><td>17.2</td><td>10.7</td><td>7.2</td></tr><tr><td/><td colspan="2">Vanilla</td><td>16.2</td><td>14.60</td><td>11.18</td></tr><tr><td>WideResNet-28-10</td><td colspan="2">Spectral (SN) SRN-50</td><td>16.13 15.8</td><td>7.23 7.3</td><td>4.5 4.5</td></tr><tr><td/><td colspan="2">SRN-30</td><td>15.7</td><td>7.20</td><td>4.4</td></tr><tr><td/><td colspan="2">Vanilla</td><td>19.2</td><td>∞</td><td>∞</td></tr><tr><td>Densenet-100</td><td colspan="2">Spectral (SN) SRN-50</td><td>17.8 17.6</td><td>12.2 12</td><td>9.4 9.2</td></tr><tr><td/><td colspan="2">SRN-30</td><td>17.7</td><td>11.8</td><td>9.0</td></tr><tr><td colspan="4">Alexnet experiments: Stable-30 Spectral Vanilla</td><td/></tr><tr><td/><td>29.04</td><td>17.24</td><td>1.22</td><td/></tr></table>



Table content: <table/>

This corresponds to the hihgly non-generelizable learning setting.

Table content: <table><tr><td>Vanilla</td><td>Spectral</td><td>Stable-50</td><td>Stable-30</td></tr><tr><td>W/o WD 69.2 ± 0.5</td><td>69±0.1</td><td colspan="2">69.1 ±0.85 69.3 ±0.4</td></tr><tr><td colspan="4">With WD 70.4± 0.3 71.35 ±0.25 70.6 ±0.1 70.6 ±0.1</td></tr></table>

Clean Test Accuracy on CIFAR10. The learning configuration corresponds to the nongenerelizable settings with high learning rate. The corresponding shattering experiments for this setting are shown in Table

Table content: <table/>

Peer review (iclr2020):
This paper proposes normalizing the stable rank (ratio of the Frobenius norm to the spectral norm) of weight matrices in neural networks. They propose an algorithm that provably finds the optimal solution efficiently and perform experiments to show the effectiveness of this normalization technique. Stable rank of the weight matrix is an interesting quantity that shows up in several generalization bounds. Therefore, regularizing such measure could potentially help with generalization. Authors discuss this clearly and they provide an algorithm that provably finds the projection. I enjoyed reading this part of the paper. The only question that I have from this part is the role of partitioning index. It looks like it is not really being used in the experiments later. Is that right? What is the importance of adding it to the paper if it is not being used? My main issue is with the empirical evaluation of the normalization technique. I am not an expert in GANs so I leave that to other reviewers to judge. Experiments on random labels and looking at different generalization measures are all nice but they are not sufficient for showing that this normalization technique is actually useful in practice. Therefore, I suggest authors to put more emphasize at showing how their regularization can improve generalization in practice. My suggestions: - Authors only provided experiments on CIFAR100 dataset to support their claim on improving generalization. I suggest adding at least one other dataset (CIFAR10, or even better imagenet) to improve their empirical results. - Unfortunately, there are two major issues with the current CIFAR100 results: 1) the accuracies reported for ResNet and DenseNet are too low compare what is reported in the literature. Please resolve this issue. 2) The current result is with training with a fixed number of epochs. Instead, train with a stopping criterion based on the cross-entropy loss on the training set and use the same stopping criterion for all models. Also, add the plots that show training and test errors based on the #epochs. Overall, I think the paper is interesting but the empirical results are not sufficient to support the main claim of the paper (improving generalization). I*m willing to increase my score if authors apply the above suggestions. ************************* After author rebuttals: Authors have address my concerns adequately in the last revision and improved the experiment section. Therefore, I increase my score to 6.