Stable Rank Normalization for Improved Generalization in Neural Networks and GANs
Authors: Amartya Sanyal
Philip H. Torr
Puneet K. Dokania
Venue:  (2020)
Keywords: Generelization
regularization
empirical lipschitz

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 parameter- dependant quantities: the Lipschitz constant upper bound and 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 genealization, evaluated empirically using—(a) shattering experiments (Zhang et al., 2016); and (b) 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 low empirical Lipschitz constant.

Published as a conference paper at ICLR 2020
STABLE RANK NORMALIZATION FOR IMPROVED GEN- ERALIZATION IN NEURAL NETWORKS AND GANS
Amartya Sanyal
Philip H. Torr
Department of Computer Science University of Oxford, The Alan Turing Institute ama rtaa.aa.... sanyal @cs ox. ac uk
Department of Engineering Science
University of Oxford
philip.torrer ox ac. uk
Puneet K. Dokania
Department of Engineering Science University of Oxford
puneet robots.......... ox aukuk
ABSTRACT
Exciting new work generalization bounds for neural networks (NN) given by Bartlett et al. (2017); Neyshabur et al. (2018) closely depend on two parameter- dependant quantities 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 whether controlling such quantities together could improve the generalization behaviour of NNs in practice. To this end, we propose stable rank normalization (SRN), novel, provably optimal, and computationally efficient weight-normalization scheme which minimizes the stable rank of linear operator. Surprisingly we find that SRN, despite being non-convex, can be shown to have unique optimal solution. We provide extensive analyses across wide variety of NNs (DenseNet, WideResNet, ResNet, Alexnet, VGG), where applying SRN to their linear layers leads to improved classification accuracy, while simultancously showing improvements in generalization, evaluated empirically using shattering experiments (Zhang et al., 2016); and three measures sample complexity by Bartlett et al. (2017), Neyshabur et al. (2018), Wei & Ma. Additionally, show that, when applied to the discriminator of GANs, it improves Inception, FID, and Neural divergence scores, while learning mappings with low empirical Lipschitz constant.
INTRODUCTION
Deep neural networks have shown astonishing ability in tackling a wide variety of machine learning problems including great ability to generalize under extreme aver-parameterizzaton. 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 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 al. (2018) and Bartlett et al. (2017),
O VVII (. 1.1.2.. srank ( (W)) that depend on two darameter-depenndnt quantities: a) the
ccale-dependent Lipschitz constant upper- bound II ||Wll (product of spectral norms) and b) the sum of intee-deddeeeeennt stable ranks (srank( W)). Stable rank 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 this work and based on extensive experiments across wide variety of NN architectures, show that, indeed, controlling them
'd and || represents the number of layers and the spectral of the i-th linear layer W., respectively.

---

Published as a conference paper at ICLR 2020
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 simultancously control the Lipschitz constant and the stable rank of 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 the paper, it does not have any impact the stable rank. We would like to emphasize that, as opposed to SN, the SRN solution is optimal and unique even in situations when is non-convex. is one of those rare cases where an optimal solution 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 & Tollaczek-GGerrnger 1929).
Experiments Although SRN is in principle applicable to any problem involving a sequence of affine transformations, considering recent interests, show its effectiveness when applied to the linear layers of deep neural networks. We perform extensive experiments on a wide variety 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 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 wide variety 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 Lips- chitz 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.
BACKGROUND AND INTUITIONS
Neural Networks Consider fo Rm - R& to be a feed-forward multilayer NN parameterized by 0 IR" each layer of which consists of linear followed by non-linear mapping. Let as-1 E R be the input (or pre-activations) to the 1-th layer, then the output (or activations) of this layer represented as a &i (zi), where z = W + b, the output of the linear (affine) layer parameterized by the weights W, E P=--1xm and biases b, R"4, and (.).) is the element-wer wise non-linear function applied to Z₁. For classification tasks, given dataset with input-output pairs denoted as (x E R y (0, 1)²; E, Mj 1) 3, the parameter vector 0 is learned using back poo--propagttion to optimize the classification loss (e.g.. cross-entropy).
Singular Value Decomposition (SVD) Given W E Raxr with rank k s min(s, r), we denote (a.)/= {u,}* j==1 and [v:),=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 σ ... Tk- o.( denotes the i-th singular value of the matrix W. Using singular values, the matrix 2-norm | can be computed as di and V.. respectively.
||]]] and the Frobenius norm
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 [ <((W)
E (f(W) where ls 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.
Pegg. ReLU, tanh, sigmoid, and maxout.
Yy is the j-th element of vector y. Only class assigned the ground-truth label each
2

---

Published as a conference paper at ICLR 2020
differentiable both Frobenius and Spectral norms are almost always differentiable.
upper-bounded by the rank: srank( W) Σ:_; c?(
of(W) I Eing (f
(WW) = k.
invariant to scaling, implying, srank( = =srank( wh for any R {0}-
17
Lipschitz Constant Here describe the global and the local Lipschitz constants. Briefly, the Lip- schitz constant is a quantification of the sensitivity the output with respect to the change in the input. A function
I + Bh is globally L-Lipschitz continuous if 3L E R4 ll.f f(xy >ll Σ ||x - xxy pllp V(x,, X,) E R" where II-Ilp and I1-II, represents the norms in the input and the output metric spaces, respectively. The global Lipschitz constant Ly is:
1x,)),) - [(x))ll
bg max ERT |X: - x1|1p. ox;=-
X, x
The above definition of the Lipschitz constant depends on all pairs of inputs in the domain Rm R (thus, global). However, one can define the local Lipschitz constant based the sensitivity of f in the vicinity a given point x. Precisely. at x, for an arbitrarily small 5 O, the local Lipschitz constant is computed E RR", ||bllp < 6, then, similar to T.g. the local Lipschitz constant of f at x, [x(x), is greater
the open ball of radius d centered at Let
(fx++h) ((x))l,
Assuming f to be Fréchet differentiable, as h + 0, using f(x + h) f(x) (x)x,,, [xxx is the matrix (operator) norm of the Jacobian
than equal to suPhş40, /ihll, <6
[h
(Jz(x) _ xx E 12
follows:*
1 [hlp
[| bll,
[(xx)
(a)
lim 6-1
sup hz0
(
sup
= [1,r(x)))
hy
[bll, <6
hER"
function said be locally Lipschitz with local Lipschitz constant Lj if for all x E R he function is Lı locally--ipschitz at Thus, L1 SuPxcRm L1 (x). Notice that the Lipschitz constant (global or local), greatly depends on the chosen norms. When p = 2, the upperbound on the local Lipschitz constant at x boils down to the 2-matrix norm (maximum singular value) of the Jacobian (x) (see last equality of (2)). With these preliminary definitions, Section 3, we discuss more optimistic (or empirical) estimates of L, and Lg. its link with generalization and then in Section 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((x)
[x]]())]l where, in the case of NNs (proof along with why it is loose in Appendix C)
(x(x) = (x)] p-a S [iillp .-. -../////l and Li = (xx)
(3)
3 WHY STABLE RANK NORMALIZATION?
Lipschitz alone not sufficient Although learning low Lipschitz functions has been shown to
provide better generalization (Anthony & Bartlett, 2009; Bartlett al., 2017; Neyshabur et al., 2018; 2015; Yoshida & Miyato, 2017; Gouk et al., 2018) 8), enable stable training of GANs (Arjovsky et al., 2017: Guirajani al., 2017: Miyato 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 eиror. 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 meaall-inddeendent--inn a hope to see improved generalization in practice.
'Here, (a) is by definition of local lipschitzness and (b) is due to the property of norms that for any non- negative scalar e, ||cx|| ||x||-
3

---

Published as a conference paper at ICLR 2020
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 given noise distribution .,, it can be quantified
[l (x + ||x So (x)ll
Q fo.NN
max T forN (x), where 1 fo.N (x) == Bypss xED
Ilfe (x)]l
For linear mapping with parameters W and the noise distribution being normal-NV (0, I), can be shown that @ fw 2 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 2 fooV of a ResNet 10 trained on CIFARIO0 Note that although the Lipschitz upper bound of SRN and SN are the same, SRN (algorithmic details in Section 4) 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.
Stable rank impacts empirical L Lipschitz constant It is apparent
that the Lipschitz constant upper bound ( [12)),) along with being scale-depender also is data- inta-inndependant and hence, provides a pessimistic estimate of the behaviour of a model on a partieular task or dataset. Considering this, a relatively optimistic estimate of the model's s behaviour would be an empirical estimate of the Lipschitz constant (L,) on task-specific dataset Note that local Le is just the norm of the Jacobian at a given point" 6. Empirically, Novak et al. (2018) provided results showing how local Le (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, are used derive generalization bounds. Thus, tool that favours low Le 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 Le- Since direct minimization of rank for NNs 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.
3.5
3.0
2.5
2.0
1.5
SRN
SN
Vanilla
Figure 1: Noise Sensitivity (lower the better). Test ac- curacy: SRN (73.1%), SN (71.5%), and Vanilla (72.4%).
4 STABLE RANK NORMALIZATION
Here we provide theoretically sound procedure to do SRN. A big challenge in stable rank normal- ization comes from the fact that it scale-invarian (refer Definition 2.1), thus, any normalization scheme that modifies W = E. v. to W E. = u.v will have no effect on the stable rank, making SRN non-trivial. Examples of such schemes are SN (Miyato et al., 2018) where 7 ai, and Frobenius normalization where 7 = WI As will be shown, our approach 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 e mmxx with rank p and spectral partitioning index 7: (0 < l < p), we formulate the SRN problem as:
arg min W. CRmmx
|W
WR
s.t. srank
\ - Vi (
(4)
stable constraint
spectrum preservation constraints
where, < (rank(()) is the desired stable rank, x; and 0,s are the singular values of W and W, respetivelly. The partitioning index l: used for the singular value (or the spectrum) preservation
'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 I. in Proposition B.1.
4

---

Published as a conference paper at ICLR 2020
constraint. It gives us the flexibility obtain We & such that its top k singular values 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.I. Note, at & = O, the problem (4) is non-convex, otherwise convex.
Theorem 1. Given real matrix W E R with rank p. target spectrum (or singular value) preservation index (0 S k < p). and target stable rank of r (1 S < srank ()), the optimal solution We problem (4) is W. S1 22S, where S 2i=1
max(11,) D, and
S = S1. {or {u, [ and ) the top k singular values and vectors of W, and,
/
S S then
depending on k. 711 and "/2 are defined below. For simplicity, we first define
a) If = 0 (no spectrum preservation), the problem becomes non-convex, the optimal solution and 71
72 when 1. Ifr 1, then 72
which is obtained for
r
and 71 = 1. Since, in this case, || of y=
Vr-lon
1221
b) If l 2 1, the problem is convex. Ifr |8: the optimal solution is obtained for 71
of
and 72 7 and if not, the problem is not feasible.
c) Also, W W
monotonically increases with for k 2 1.
Intuitively, Theorem 1 partitions the given matrix into two parts, depending k; and then scales them differently in order to obtain the optimal solution. The value of the partitioning index k is design choice. there no particular preference k. then k 0 provides the most optimal solution. We provide simple example to better understand this. Given W Il (rank = srank W) 3), the objective is to project it to new matrix with stable rank of Solutions to this problem are:
1
0
0
0
V
0
W
1 0
W2
0
0
W
0
0
(5)
2/2
0 0
vz
0
v
2v2
Here, W, is obtained using the standard rank minimization (Bckart- Bickart-Young-Misth (Eckart & Young, 1936)) while WN and W, are the solutions of Theorem with k and k 0, respectively. It 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 W1
w ww/l 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, (true for any & > 1), the spectral norm of the original and the normalized matrices are the same, implying, 7/2 = However, for k = 0, the spectral norm of the optimal solution is greater than that of the original matrix. It is easy verify from Theorem that as increases, 7/2 decreases. Thus, the amount of scaling required for the second partition S2 more aggressive. In all situations, the following inequality holds: 72 1 S 71.
W W2
5

---

Published as a conference paper at ICLR 2020
Algorithm 1 Stable Rank Normalization
Algorithm 2 SRN for a Linear Layer in NN
Require: W Rmxn S1 f- 0, 9 + W
k
Require: W Rm=x r, learning rate a, mini-
7 0
batch dataset DD
2: for i [1, .k do
I: Initialize u E IR"" with random vector.
3:
{u., vz,o; SVD(W,
v
|w uI
WT
W
4:
Power method get i-th singular value
5:
ifr 2 (o) + /oj then
3:
Perform power iteration
4: (W) Wv
6:
S1 S1 +
W, W W/a
Spectral Normalization
7:
1- - o
W W uv
8:
1+1+1
9: else
7: if W S VV
then
10:
break
8:
return W
end
end
12: end for
10: W
=
Stable Rank
13: + roi
14:
return W. Si + / - S.).
Normalization
11: return + W WVWL(WW,D)
Algorithm for Stable Rank Normalization We provide a general procedure in Algorithm 1 to solve the stable rank normalization problem for & 1 (the solution for A = 0 is straightforward from Theorem 1). Claim 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 matrix W, the desired stable rank v, and the partitioning index k 2 Algorithm I requires computing the top (I k) singular values and vectors of W. It returns W1 and the scalar I such that srank( Wi) = r, and the top singular values of W and W are the same. If then the solution provided is the optimal solution to the problem (4) with all the constraints satisfied, otherwise, returns the largest I up to which the spectrum preserved.
Combining Stable Rank and Spectral Normalization for NNs Following the arguments pro- vided in Section and 3, for better generalizability. we propose to normalize both the stable rank and 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 given linear layer of NN. Note, the computational cost of this algorithm is exactly the same as that of SN, which to compute the top singular value using the power iteration method.
EXPERIMENTS
Dataset and Architectures For classification, we perform experiments on ResNet- (He et al., 2016), WideResNeet28-110 (Zagoruyko & Komodakis, 2016), DenseNet-100 (Huang et al., 2017), VGG-19 (Simonyan Zisserman, 2014), and AlexNet (Krizhevsky & Hinton, 2009) using CIFAR (Krizhevsky & Hinton, 2009) dataset. We present further experiments with CIFAR10 in Appendix D.I in Figure and 11. We train them using standard training recipes with SGD, using learning rate of 0.1 (except AlexNet where with batch size of 128 (further details 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.
learning rate of 0.01), and momentum of 0.9
For GAN experiments, we use CIFAR100, CIFARIO, and CelebA (Liu et al., 2015) datasets. We show results on both, conditional and unconditional GANs. Please refer Appendix E. for further details about the training setup.
Choosing stable rank Given a matrix W E R M the desired stable rank r controlled using a single hyperparameter as min(m, n), where (0, 1). For simplicity, we the same for

---

Published as a conference paper at ICLR 2020
(a) Resnet 10
(b) WideResnet-28
(c)
Alexnet
(d) Densenet- 100
(e) VGG-19
Figure& 2: Test accuracies on CIFARI00 for clean data. Higher better.
all the linear layers. is trivial to note that if 1, or for given if srank W) S then SRN boils down to SN. For classification, we choose = {0.3, 0.5), and compare SRN against standard training (Vanilla) and training with SN. For GAN experiments, compare SRN-GAN against SN-GAN (Miyato et al., 2018), WGAN-GP (Gulrajani et al., 2017), and orthonormal regularization GAN (Ortho-GAN) (Brock et 2016).
choose {0.1, 0.3, 0.5, 0.7, 0.9), and
Result Overview
SRN improves classification accuracy 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
SRN-GAN provides much improved Neural divergence score (ND) (Gulrajani et al., 2019) compared to SN-GAN, proving that it robust to memorization 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 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 SRN, on a wide variety NNs, is always higher than the Vanilla and SN (except for SRN-50 Alexnet where SRN and SN are almost equal). However, SN performs slightly worse than Vanilla for WideResNet-22 and ResNetl 10. 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 significantly in order for SRN to outperform Vanilla. For example, in the case of ResNetl 10, 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 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 non-trivial and there no clear answer 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 shat- tering experiment (Zhang al., 2016). It is test of whether the network can fit the training data well but not a label-randomized version of it (each image of the dataset assigned a random label). As there is no correlation of the labels with the data points P (3/xx) is essentially uninformative because it is uniformly random. Thus, the test accuracy on this task is almost 1%. A high training accuracy which indicates high generalization gap (difference between train and test accuracy) can be achieved
7

---

Published as a conference paper at ICLR 2020
Opentea
(a) Resnet 10
(b) WideResNet-228
(c) Alexnet
(d) Densenet-
(e) VGG-19
Figure 3: Train accuracies on CIFAR100 for shattering experiment. Lower indicate less memorization, thus, better.
04
Soadle Varilo
0.4
13
802
0.0
0.
0.g
(a) RI 10-Jac-Norm
(b) 1-10-Spee-Ly L1
(c) RI 1-0------FFrooo
0:30
2.25
Spectiol Stilee 30
Spectral
Spectrul
g0.23
Stabk: 50
2.11
643
0.00
12
14
14
30
35
20
(d) WRN-Jac Norm
(c) WRN- Spec-L1
(f) WRN-Spee-
Stale in
Soate Staree 90
Spectral
Suati 50
Stable 20
Varila
02
5.0 125
0.
(g) D100-I1a--J--e Jac-oomm
(h) L1
(i) 1100-Spec-Fro
Figure 4: (log) Sample complexity (Catg) of ResNet- 10 (Figure 4a 4c), WideResNet-28-10 10 (Fig- ure 4d to 4f), and Densenet-100 100 (Figure 4g to 4i) quantified using the three measures discussed in the paper. Left is better. Vanilla is omitted from Figure 4b, 4c, 4h and 4i is too far the right. Also, in situations where SRN-50 and SN performed the same, we removed the histogram to avoid clutter.
only by memorizing the train data 7. 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.
SRN-50
SRN-30
Spectral (SN)
Vanilla
WD 12.02 1 1.77
11.87 1 0.57
11.13 2.56
10.56 1 2.32
w/o WD 17.71 1 2.30
19.04 1 4.53
17.22 1 1.94
13.49 1 1.93
Table 1: Highly non-generalizable setting. Training error for ResNet-110 CIFAR100 with randomized labels, low Ir= 0.01, and with and without weight decay. (Higher is better.) The clean test accuracy for this setting is shown in Appendix D.I.
We also look specifically highly non non-genrralizable settings low learning rate and without weight decay. As shown in Table 1, 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.I.
7 Thhe training of all the models of architecture were stopped after the same numher of epochs double the number epochs the model were trained on the clean dataset. 'These result are reported after 200 epochs. It can he looked on as combined with early stopping, which is powerful way of avoiding memorizing random labels (Li et al.).
8

---

Published as a conference paper at ICLR 2020
CAN
20
Stable
20
Spectral
incy
Mognitate Effect vo Lppchitz vonatle
0.6
0.2
Magnitude Ellective Lipeontz vanaatl
3.4
0.5
0.5
(a) Varying stable rank constraints
(b) Comparison against different approaches
Figure 5: eLhist for unconditional GAN on CIFARIO. 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 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. ar- chitecture, dataset, optimizer, among other) as in SRN SN Vanilla, fixed, and the only variability is in the normalization, the generalization error can be written as [Train Err - Test Err S
δ V /oref/m) where δ (-) ignores the logarithmic terms, m is the number of samples in the dataset, and Cate denotes measure of sample complexity for given algorithm. Lower the value of Calg. the better is the generalization. Before we give various expressions for Calg. we first define common quantity in all these expressions, called the margin ? Se (x) [y] max So (x) [i]. 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 quantify the generalization behaviour with further descriptions in Appendix D.1:
Spec-Fro: 11f ||W, 11 - srank( W. 1/2 (Neyshabur et al., 2018).
Spec-L.1: ITE I/W.13
/4² (Bartlett et al., 2017), 11-112, is the matrix 2-1 norm. Jac-Norm: El= [|b. ||b:laa|l:laa/ (Wei & Ma), where h is the jth hidden layer and J.
J[ 11
0>
Histogram of the Empirical Lipschitz Constant heitis We evaluate above mentioned sample complexity measures on 10, 000 points from the dataset and plot the distribution of the log using 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. As the plots and the table show, both SRN and SN produces much smaller quantity than a Vanilla network and in 7 out of the 9 cases, SRN 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 Section 3.
Above experiments indicate that SRN, while providing enough capacity for the standard classification task, remarkably less prone to memorization and provides improved generalization. 5.3 TRAINING OF GENERATIVE ADVERSARIAL NETWORKS (SRN-GAN)
In GANs, there is 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 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 al., 2019), we use histograms of the empirical Lipschitz constant, refered to as eLhist from now onwards,
Results taken from Miyato al. (2018). The rest of the results in the tables generated by us.

---

Published as a conference paper at ICLR 2020
for the purpose of analyses. For given trained GAN (unconditional), create 2, 000 pairs of samples, where each pair x,) consists of x; (randomly sampled from the 'real' dataset) and x, (randomly sampled from the generator). Each pair is then passed through the discriminator to compute (lx( //l/// [Xx///x which we then use to create the histogram. In the conditional setting, sample class from discrete uniform distribution, and then follow the same approach as described for the unconditional setting.
Effect of Stable Rank on ehhist and Inception Score As shown in Fig- ure 5a, lowering the value of с (ag- gressive reduction in the stable rank) moves the histogram towards zero, im- plying, lower empirical Lipschitz con- stant. This validates our arguments provided Section 3. Lowering e also improves inception score, how- ever, extreme reduction in the stable rank (c 0.1) dramatically collapses the histogram to zero and also drops the inception score significantly. This
Algorithm
Inception Score
FID
Intra-FID
Orthonormal
7.92 = .04
23.8
Uncond.
WGAN-GP
7.86 = .07
21.7
SN-GAN'
8.22 = .04
20.67
SRN-70-GAN
8.53 = 0.04
19.83
SRN-50-GAN
8.33 0.06
19.57
SN-GAN
8.71 = .04
16.04
26.24
Cond.
SRN-70-GAN
8.93 + 0.12
15.92
24.01
SRN-50-GAN
8.76 = 0.09
16.89
27.3
Table 2: Inception and FID score on CIFARIO.
is due to the fact that at 0.1, the
capacity of the discriminator is reduced the point that it not able learn differentiate between the real and the fake samples anymore.
Table 2 and show that SRN-GAI consistently provide better FID score and an extremely competi- tive inception score on CIFARIO (both conditional and unconditional setting) and CIFAR100 (uncon- ditional setting). In Table 4, we compare the ND) loss on CIFARIO 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.I. 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 both datasets. For qualitative analysis of the images, we compare generations both conditional and unconditional setting in Appendix F.
Comparing different approaches In addition, in Fig- ure 5b, we provide eLhist for comparing different ap- proaches. Random-GAN as expected, has low empirical Lipschitz constant and extremely poor inception score. Un-
Model IS
FID
SN-GAN 9.04
23.2
surprisingly, WGAN-GP has a lower Le 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 bet- ter inception score- highlliigiig the flexibility provided by SRN. Additional experiments in Appendix E.2 show more detailed behaviour of GANs in regards to empirical lipschitz in variety of settings.
SRN-GAN (Our)8.85
19.55
Table 3: CIFAR100 experiments.
Model
CIFARIO
CclebA
SN-GAN
10.69
0.36
SRN-GAN (Our)
11.97
0.64
Table 4: Neural Discriminator Loss (Higher the better).
CONCLUSION
We proposed a new normalization (SRN) that allows us to constrain the stable rank of each affine layer of 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.
7 ACKNOWLEDGEMENTS
The authors would like to thank Leonard Berrada and Pawan Kumar for helpful discussions. AS acknowledges support from The Alan Turing Institute under the Turing Doctoral Studentship grant TU/C/000023. PHS and PD are supported by the ERC grant ERC-2012-AdG 321162-HELIOS EPSRC grant Seebibyte EP/M013774/1 and EPSRC/MURI grant EP/N019474/1. PHS and PD also acknowledges the Royal Academy of Engineering and FiveAl.
10

---

Published as a conference paper at ICLR 2020
REFERENCES
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundatioon. cambridge university press, 2009.
Martin Arjovsky, Soumith Chintala, and Léon Bottou. Wasserstein gan. 2017.
Sanjeev Arora and Yi Zhang. Do gans actually learn the distribution? an empirical study. arXiv preprint xrXiv: 776.002224... 2017.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 254-263, Stockholmsmässann Stockholm Sweden, 10-15 Jul 2018. PMLR. URL http: ppw.ceednnsseeesoseoooe.. mlr wttppp/seeeerrssaaaaaaaa 18b. html.
Peter L Bartlett, Dylan Foster, and Matus J Telgarsky. ppectrally-normallinn margin bounds for neural networks. In Advances in Neural Information Processing Systems, pp. 6240-6249, 2017.
Andrew Brock, Theodore Lim, J. M. Ritchie, and Nick Weston. Neural photo editing with introspec- tive adversarial networks. International Conference on Learning Representations, 2016.
Moustapha Cisse, Piotr Bojanowski, Edouard Grave, Yann Dauphin, and Nicolas Usunier. Parseval networks: Improving robustness to adversarial examples. In Doina Precup and Yee Whye Teh (eds.), Proceedings of the 34th International Conference on Machine Learming, volume 70 of Proceedings of Machine Learning Research, pp.
International Convention Centre, Sydney, Australia, 06-11 1 Aug 2017. PMLR. URL http: : /ttp///pceeeenns..///e/. mlr press/v70 http////////ssss//eeeess html.
Vincent Dumoulin, Jonathon Shlens, and Manjunath Kudlur. A learned representation for artistic style. Proc. of ICLR, 2017.
Carl Eckart and Gale Young. The approximation of one matrix by another of lower rank. Psy- chometrika, 133)2211-218, sep 1936. ISSN 0033-3123. doi: 10. 10.10077/F02228333 URL
http://link www.sspr. com/ 10000000222886377777
Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio. Generative adversarial nets. In Advances in neural informa- tion processing systems, pp. 2672-2680, 2014.
Henry Gouk, Eibe Frank, Bernhard Pfahringer, and Michael Cree. Regularisation of neural networks by enforcing lipschitz continuity. arXiv preprint arXiv: 8044644444 2018.
Ishaan Gulrajani, Faruk Ahmed, Martin Arjovsky, Vincent Dumoulin, and Aaron Courville. Improved training of wasserstein gans. 2017.
Ishaan Gulrajani, Colin Raffel, and Luke Metz. Towards GAN benchmarks which require gen- eralization. In International Conference on Learning Representations, 2019. URL https: //openreview wwweeeewweeeeeeeeeeeeeeeeeeeeeee http://rrrm....aa//HAAAAAAAA
Kaiming Hc, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep Residual Learning for Image Recognition. In 2016 IEEE Conference Computer Vision and Pattern Recognition (CVPR), pp. 770-778. IEEE, jun 2016. ISBN 978-1-4673-8851--1 doi: 10.1109/CVPR.2016..0 URL http: httt://ieeexppooeeee ieee. wwtp///ccmee//////00880
Martin Heusel, Hubert Ramsauer, Thomas Unterthiner, Bernhard Nessler, and Sepp Hochreiter. Gans trained by a two time-scale update rule converge to a local nash equilibrium. In Advances in Neural Information Processing Systems, pp. 6626 6637, 2017.
Gao Huang, Zhuang Liu, Laurens van der Maaten, and Kilian Q. Weinberger. Densely connected convolutional networks. In 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR). IEBE, jul 2017. doi: 10. 10.11099cp:.2211..24..
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv: 1412.6980 2014.
11

---

Published as a conference paper at ICLR 2020
Naveen Kodali, James Hays, Jacob Abernethy, and Zsolt Kira. On convergence and stability of GANs, 2018. URL https::p.... http:: http:/:://///////eeeeeee http://www..ee.ooo/////eeee/p/pp
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
Mingchen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks.
Jae Hyun Lim and Jong Chul Ye. Geometric gan. 2017.
Ziwei Liu, Ping Luo, Xiaogang Wang, and Xiaoou Tang. Deep learning face attributes the wild. In Proceedings of International Conference Computer Vision (ICCV), 2015.
Leon Mirsky. Symmetric gauge functions and unitarily invariant norms. The quarterly journal of mathematics, 11(1):50-59, 1960.
Mehdi Mirza and Simon Osindero. 2014.
Conditional generative adversarial nets.
arXiv preprint
arXiv:
R. V. Mises and H. Pollaczek- Geiriige. Praktische verfahren der gleichungsauflösung ZAMM Zeitschrift für Angewandte Mathematik und Mechanik, 9(2):152-164 1929. doi: 10. 10.1002/zamm. 19290090206.
Takeru Miyato and Masanori Koyama. egans with projection discriminator, International Conference on learning Representations, 2018.
Takeru Miyato, Toshiki Kataoka, Masanori Koyama, and Yuichi Yoshida. Spectral normalization for generative adversarial networks. International Conference on Learning Representations, 2018. net hett/foouumddddBBQRee
URL
Vaishnavh Nagarajan and Zico Kolter. Deterministic PAC-bayesian generalization bounds for deep networks via generalizing resilerese In International Conference on Learning Representa- fions, 2019. URL https: httttt::/pppeeeeaiiiiie httpp//areeii..eeeeerroooeeeeeee www.:eeeooooommddid/meemeom
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. In Conference on Learning Theory, pp. 1376-1401, 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A PAC-bayesian approach to spectrally-normaaiieed margin bounds for neural networks. International Conference Learning Representutions, 2018. URL https: http:://ppeeeeieeee httpe/wwwwwweweeeeeeeeeeeeeeeeee
Roman Novak, Yasaman Bahri, Daniel A Abolafia, Jeffrey Pennington, and Jascha Sohl- Dickstein. Sensitivity and generalization in neural networks: an empirical study, arXiv preprint arXiv:1802.08760, 2018.
Henning Petzka, Asja Fischer, and Denis Lukovnikov. On the regularization of wasserstein GANs. In International Conference on Learning Representations, 2018. URL https: //tpen/evie....ee////ee bet/EForum?idd=BlhrRMM.
Prajit Ramachandran, Barret Zoph, and Quoe V. Le. Searching for activation functions, 2018 URL /ttpee///peereeviee net/forum?ide SkBYYyZRZ.
Mark Rudelson and Roman Vershynin. Sampling from large matrices. Journal of the ACM, 54(4):
21 21-es, jul 2007. doi: 10.1 (0.1145/12554431125544
Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, and Xi Chen. Improved techniques for training gans. In Advances in Neural Information Processing Systems, pp. 2016.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 1409. 1556, 2014.
Dustin Tran, Rajesh Ranganath, and David M. Blei. Hierarchical implicit models and likelihood-free variational inference. 2017.
12

---

Published as a conference paper at ICLR 2020
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:
Yuichi Yoshida and Takeru Miyato. Spectral norm regularization for improving the generalizability of deep learning. arXiv preprint arXiv: 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.0.887
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference Learning Representations (ICLR), nov 2016. URL http: http///xxxvvv.// org/ ha//abbss11111 1111103111.0.....
Han Zhang, Ian Goodfellow, Dimitris Metaxas, and Augustus Odena. Self-attention generative adversarial networks. 2018.
13

---

Published as a conference paper at ICLR 2020
A TECHNICAL PROOFS
Here we provide an extensive proof of Theorem 1 (Appendix A.1), We also provide the optimal solution the spectral norm problem in Appendix A.2. Auxiliary lemmas which our proof depends are provided in Appendix A.3.
A.1 PROOF FOR OPTIMAL STABLE RANK NORMALIZATION (MAIN THEOREM)
Theorem 1, Given real matrix W E Rmxx with rank p, a target spectrum (or singular value) preservation index k (0 I k < p), and target stable rank of r (1 S < srank( (W), the optimal solution W to problem (4) is We S1 + Y25,, where S Ei=1 max(11,) o.u,V, and
S = S1. {ai {u:}im and {vi).m are the top l singular values and vectors of W, and,
depending on k. and ?/2 are defined below. For simplicity, we first define /ra
then S S 1
a) If (no spectrum preservation), the problem becomes non-convex, the optimal solution and 711 when r 1. Ifr 1, then 722 =
72
to which is obtained for 7/2 r
and 7i = 1. Since, in this case, || of. 7- b) If l 2 1, the problem is convex. Ifr 2 |
Vo-
12
of E the optimal solution is obtained for 1,
and 7/2 7 and not, the problem is not feasible.
c) Also, W w
monotonically increases with l for l. 2 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 We be the optimal solution the problem for any of the two cases. From Lemma 5, the SVD of W and We & can be written as W UΣVT and
Wx = UAV respectively. Then, L W Wx = ( -, A)p. From now onwards, we denote Σ and as vectors consisting of the diagonal entries, and (.. as the vector inner product
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 o. r. Let us assume Σ = (ai, ;p)) Σg = (02, .. op)) A = (A1," Ap)
and A2 (22,-* Ap). Using these notations, we can write L as:
L - Σ) + (A, - (E,
-2, Σ) + X A2) 20 (22, A2)
(6)
Using the stable rank constraint srank W+) = which r =
X
Case for If > we obtain the following equality constraint, making the problem non- convex.
(A2, A2)
X
However, will show that the solution obtain is optimal and unique. Substituting (7) into (6) get
L 1= A2) (A2, 201
(A2, A2) 2 A2)
(8)
r-
10 (.. .) represents the Frobenius inner product of two matrices, which in the case of diagonal matrices is the the inner product of the diagonal vectors.
14

---

Published as a conference paper at ICLR 2020
aL
Setting
0 get the family of critical points
2A₂
2A2
+A2
-2
r
2
1) (A2,A2
1
01
De = A
+
(9)
1 - () (Az, A2)
M | do i
01
visisp
(10)
1 (A2, A2)
72
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 Σg. implying, A₂ Lz Note that the domain of A2 are all strictly positive
vectors and thus, we can ignore the critical point at A2 O. Substituting this into (9) we obtain
1
Σg D2
+1
72 72 1) (22,, Σni
Using the fact that (E22, Σ2) || f in the above equality and with some algebraic manipulations,
we obtain 7/2 = 7 where, ?
v/-1o1 Note, 2 1, y 2 0, and Σ 2 0, implying, A2 =
S
L2 O.
Now, we will show that A2 is indeed a minima of (8). To show this, we compute the hessian of T.. Recall that
Local minima:
aL
2r
2
2Σ
0A
r
( 1) 1111
H
LL
2r
201
||A I
1
AAT)
r
V(r 1) ||A1/
||
=
r
01 ||A||2
I+
20
(AAT)
vrr- - 1) ||Al
Vr - ||A1
Now we need to show that H at the solution Ag is PSD i.c. V RP-1,
x H (A2)xx 20 0
r σ1 ||A
201
2 x Hx =2
||x]|
x (AAT) x
r vrr
||A
Vr-
1 ||Al|
σ1 ||A|||
2
||x12
r- v(r 1) ||A1? 2
2
σ1
||x1| (0)
2r
+r+ 11) 1x
r-1
(r- 1) An
2r
||x|2 = 2| 0
(1+r-1)
Here (a) is due to the fact that the matrix AAT is an outer product matrix and is hence PSD. (b) follows due to (7) and (c) follows by substituting X n and then the value of 71 Finally (d)
follows 1 (7 + r 1)
is decreasing with respect to 7 and we know that 7 < due the
assumption that srank ()) Thus, expression. This concludes our proof that Ag is indeed a local minima of
substitute 7 1 to find the minimum value of the
Uniqueness: The uniqueness of A2 solution to (8) is shown in Lemma 6 and is also guaranteed by the fact that 7/2 has unique value. Using A₂ = L2 and A₁ = Yi in (7), we obtain a unique solution 71 72
7
15

---

Published as a conference paper at ICLR 2020
Now, we need to show that it is also an unique solution to Theorem 1.
For all solutions to Theorem that have singular vectors which are different than that 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 solution with different singular values than W k. 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 WR. R. WR is strictly better in terms of W - W This requires further assumption that every non-zero singular value of 22 has a multiplicity of i.e. they are distinctly unique, Intuitively, this doesn't allow to create different matrix by simply interchanging the singular vectors associated with the equal singular values. As the elements of Σg are distinct, the elements of A2 = L2 are also distinct
and thus by the second part of Lemma 5, We is strictly better, in terms of [w Ww than all
Wx
matrices which have the same singular values as that of W.. This concludes our discussion on the uniqueness of the solution.
Σj=2 A
Case for r 1: Substituting r = in the constraint r = 14
we get
X
1 Σ X
Σ 2 = 0
=
-=
As it is sum of squares, each of the individual elements is also zero i.c. X3 = < S p. Substituting this into (6), we get the following quadratic equation in X1
20121
(11)
which is minimized at A σ1, thus proving that m1 1 and 72
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 Σ (01.... .kk. Σg = (Øk+1, ... .op). A (A1, Ak),
A2 = (AR+1, Ap).. Since satisfying all the constraints imply Σn = A1, thus, 2
T=
w
(Ee - A2, E2 - A2). From the stable rank constraint srank Wx) k)) = r. we
k:
have F
r A1) + (A2, A2)
X2
(A2, A2) = r (AI, = ro² Ei)
(12)
The above equality constraint makes the problem non-convex. Thus, we relax it to srank (w)) to
make it a convex problem and show that the optimality is achieved with equality. Let (E1, Σn) n.. Then, the relaxed problem can be written as
min
L := E2
A2, Ez A2)
s.t.
A₂ 2 0, (Az, A2) Sn
We introduce the Lagrangian dual variables r E RD-k and μ corresponding the positivity and the stable rank constraints, respectively. The Lagrangian can then be written as
L (A2, -, T,1)
(Eg A2. Eg A2) + + ((A2, - 77 (T,
(13)
ac
Using the primal optimality condition
O^₂ = 0, we obtain
2A₂ 25g + 2uA2 T=
r + 252
Ag 2(1 + p))
(14)
16

---

Published as a conference paper at ICLR 2020
Using the above condition A2 with the constraint (A2, A2) S 7. combined with the stable rank constraint of the given matrix W that comes with the problem defimition, srank( > (which implies (E2, Σz) > 7), the following inequality must be satisfied for any r 2 0
1 E2 E2) E2, <1+
(15)
For the above inequality to satisfy, the dual variable i must he greater than zero, implying, (Ag, A2) -1 must be zero for the complementary slackness satisfy. Using this with the optimality condition (14) we obtain
T 25,, r + 252)
(1 + (1+1)²²= 1))
4n
Substituting the above solution back into the primal optimality condition we get
Vi
A₂ = (T+EE)
(16)
+ 25,, r +2
Finally, the complimentary slackness condition as follows
T A2
0ll get rid of the dual variable r
r O (T+ 2Σ2)
0
(T 2E,, 25
It is easy to see that the above condition is satisfied only when r 0 as Eg 2 0 and v) >> 0. Therefore,
using I in (16) we obtain the optimal solution of Ag as
vof - |S
v1 Le
A2 =
D2 = 720
(17)
V /E,, Ex)
|
Proof for Case (c): The monotonicity of WR w/ for k 2 is shown in Lemma 3.
Note that by the assumption that srank W) < we can say that y < 1. Therefore all the cases
12 1. Let us look the required conditions for 71 to hold. When k 2 1, 7 holds. When k = 0, for ?1 > 1 to be true, 72 < 7 should hold, implying, (1 - < (7 - 1), which is always true
(by the definition of stable rank).
Lemma 3. For k: 2 1, the solution to the optimizution problem (4) obtained using Theorem 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 E (1,.... .P). W. = + be the matrix obtained using Theorem 1. We use the superscript i along with S and S2 to denote that this
refers to the partieular solution of Wa. &. Plugging the value of y and using the fact that || p A we can write
W We
= -1- 1|
= =||s || V - |
|| V - |W + || p
Thus, W Wx can be written a simplified form as f(x) = r - Va x², where x = ||S
and rof W Note, a I 0 as <r < srank(W), and x² > because of the condition in Theorem 1. Under these settings, it is trivial to verify that f is a monotonically decreasing function of Using the fact that as the partition index & increases, æ decreases, is straightforward to conclude that the minimum of f(r) is obtained at k = 1.
1 is the hadamard product
17

---

Published as a conference paper at ICLR 2020
A.2 PROOF FOR OPTIMAL SPECTRAL NORMALIZATION
The widely used spectral normalization (Miyato et al., 2018) where the given matrix W E | 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
(18)
S
where o (W) denotes the maximum singular value and 0 is hyperparameter. The optimal solution to this problem shown in Algorithm In what follows we provide the optimality proof
Algorithm Spectral Normalization
Require: W E R
Wi 0. p.p min,m, n)
2: for k E (1,... pP) do
3: {uk, Vk + SVD(W,
& perform power method get k-th singular value
4:
of 2 then
5:
+ W V
6:
W - W 0k U
7: else
8:
break
> exit for loop
9: end if
10: end for
11: return W + k.WWio W
of Algorithm 3 for the sake of completeness. Let SVD (W) UEV and let us assume that = SAT is solution to the problem 18. Trivially, = UAV also satisfies o (X) S s. Now, IW | | (Σ A) VT || A)ll < IWW- - I 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 solving the following problem
arg min NERmiulmmn m..
|| - E1E s.t. A < Ei {0, min (m,, n)).
(19)
Here, without loss of generality, we abuse notations by considering A and to represent the diagonal vectors of the original diagonal matrices A and E, and A [i] as its i-th index. It is trivial to see that the optimal solution with minimum Frobenius norm achieved when
Σ E if Σ [ 8,
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, E mxn with singular values 01 on and P1 2 2 Pno respectively
A
B
(0 pi)
1=1
Proof. Consider the following symmetric matrices
0
A
B
X
Y
A
0
0
(A - B)
0
18

---

Published as a conference paper at ICLR 2020
Let 2 ... In be the singular values of Z. Then the set of characteristic roots of X, Y and in descending order are {pI.... Pn. Pm. -P1). foi.... ,On. -n. -0 and " Fax Tn." -Ti). respectively. By Lemma 2 in Wielandt (1955)
o1 P ... on - Pn: Pn. - On," 'n ,1 σ1 = [n, : Tas -ux - TT
which implies that
(ai
pa)² S >5* - | BIF
(20)
1=1
i=1
Lemma 5. Let A, E mmxx where SVD(A) = UEVT and B is the solution to the following problem
B = arg min IW - A
(21)
srank( W)
Then, (B) UAV where A is a diagonal matrix with non- non-negative entries. Implying. and B will have the same singular vectors.
Proof. Let assume that Z SAT is solution the problem 21 where S U and T * V. Trivially, X UAVT also lies in the feasible set as it satisfies srank(X) = (note stable rank only depends on the singular values). Using the fact that the Frobenius
is invariant unitary transformations, we can write | X = U A) VT F |(E - A) Combining this ド [ A)II A ZlI- Since, S &f U and T + V,
with Lemma 4, we obtain A X can further change I to strict inequality <. This completes the proof.
Generally speaking, the optimal solution problem 21 with constraints depending only 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, both Σ and A have no repeated values, then B is the only solution to (21) that has the singular values of A.
Lemma 6. Let y1 = ax1 + b&, and y2 = ax2 + bb2, where X1 and &2 denotes the unit vectors.
Then, y1 y2 x X2.
B EMPIRICAL LIPSCHITZ CONSTANT
B. RELATING EMPIRICAL LOCAL AND GLOBAL LIPSCHITZ CONSTANTS
Proposition B.1. Let f R + be a Fréchet differentiable function, D the dataset, and Conv (Xi, xj) denotes the convex combination of a pair of samples x; and Xj, then Vp,q [o] such that + =1 p
1f(x;) f(x,)
max ED
max X. M.EEEDD ED x XECom (x:x))
|x; - xillp
19

---

Published as a conference paper at ICLR 2020
Proof. Let f: R + R be differentiable function open set containing x, and x, such that X; 7 x,. By applying fundamental theorem of calculus
(x.) - (xx))
f (x, + (x, - -xi)) (xy x.) 00
V (x: + 0 0xx -xx)) (xj xx) 00
IVV (x: + 0 (x, - x,))1l, (xx; - x1)11p 00
max 1E(0,1) |V (x: + 0x3 - -xi))ll, [1(x; - xx)1 00
|V (x; + 0 0(x; x1)))l 11 - xi) L. 00
max (E(U,1)
(xx)) - 1xx)] [1xx; - xi)llp
max (E(1).)
VV (x: 0 0xx; xx1i)ll x.Com (x),x)
max
|VV (x)
The inequality (a) is due to Hölder's inequality.
B.2 EFFECT OF RANK ON THE EMPIRICAL LIPSCHITZ CONSTANTS
Let f(x) = W W ix be a two-layer linear NN with weights W1 and W2. The Jacobian in this case independent of x. Thus, the local Lipschitz constant the same for all x E RT implying, local The = (x) I, = W < |/al Will- 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 Le.
Let x; and x; be random pairs from D and Ax + 0 be the difference x; - Xj, then, the global Le is max(xx,;)e0 [[,WW Let h; and hn be the ranks, and 01 2 ... 2 0k, and λ 2 ... 2 Ava the singular values of the matrices W, and W2, respectively. Let P; = u. be the orthogonal projection matrix corresponding to u, and ū, the left and the right singular vectors of W, Similarly, we define Qi for W2 corresponding to v, and v. Then, W2W; = Σナz Σラ= \.o,Q.Pj. The upperbound. A can be achieved if and only if Ax = ú₁ || and u = Vi (a perfect alignment), which is highly unlikely. In practice, not just the maximum singular values, is the case with the Lipschitz opper-bound, rather the combination the projection matrices and the singular values play erucial role in providing equivalent to minimizing the rank (or stable rank), will directly affect Le- For example, assigning o = O, which in effect will reduce the rank of W1 by one, will nullify its influence on all projections associated with P,, Implying, all the k projections o, (><e, 1- x₂Q.) that would propagate the input via Pj will be blocked. This, in effect, will influence W W2Ax||; hence the global Le- In a more general setting, let k; be the rank of the i-th linear layer, then, each singular value of a j-th layer can influence the maximum of II k; IT' k; many paths through which an input can be propagated. Thus, mappings with low rank (stable) will greatly reduce the global L., Similar arguments can be drawn for local L, in the case of NN with non-linearity
estimate of global L,, Thus, reducing the singular values, which is
C THE LOCAL LIPSCHITZ
FOR NEURAL NETWORKS
As mentioned in Section 2, (x) = p. where, in the case of NN, the Jacobian is:
0f 0f (x) Oz (zl(z)) Ozj (z))
J (x
(22)
8x
Ozi
da Ozi
Using Jai-1
Wr (affine transformation), and applying submultiplicativity of the matrix norms:
(2))(2))
[Jr(x))|lpa
|| p.g
|
(23)
Oz1
dzi
20

---

Published as a conference paper at ICLR 2020
Note, most commonly used activation functions ((.) such as ReLU, sigmoid, tanh and maxout known to have Lipschitz constant of 1 (if scaled appropriately)" thus, the upper bound can further be written only using the operator norms of the intermediate matrices
(24) Furthermore L (x) can be substituted by L the local Lipschitz constant, as the upper bound (Eq. (24)) independent x. Note that this is one of the main reasons why we con- sider the empirical Lipschitz to better reflect the true behaviour of the function as the NN is never exposed to the entire domain R but only a small subset dependant on the data distribution.
(x(x)= & (1 p.g I |/ p.g ... ....--WWlppp. p.9.
The other reason why this upper bound is bad estimate is that the inequality in Eq (23) is tight only Da.
Pz. 8z when the partial derivatives are aligned, implying, 8mg Oz; 2
022+1
v <
< I. This problem has been referred as the problem of mis-alignment and similar to quantities like layer cushion in Arora et al. (2018).
D EXPERIMENTAL DETAILS
WideResNet-225 10 We use standard WideResNet with 28 layers and 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 trained with weight decay of le 4. The learning rate was multiplied by 0.2 after 60, 120, and 160 epochs respectively.
ResNet- 110 The ResNet- 1 10 is standard 110 layered ResNet with batch Norm and ReLU and has 1, 973, 236 multiplied 0.1 after 150 and 250 epochs respectively, a weight decay of 5e 4 and momentum of 0.9.
236 parameters. The network trained with SGD, an initial learning rate of 0.1, which is
Densenet- The DenseNet-100 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 multiplied by 0.1 after 150 and 250 epochs respectively. a weight decay of 1e and momentum of 0.9.
VGG19 The VGG19 model is the standard 19-layered VGG model with Batchnorm and ReLU, has total of 20, 548, 392 trainable parameters and is trained with SGD with 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 large learning rate.
The Alexnet model is the standard ALexNet model with 4, 965, 092 trainable parameters. It was trained with SGD, with momentum of 0.9, with 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.
AlexNet
D. ADDITIONAL EXPERIMENTS ON GENERALIZATION
Complexity measures In this section, we provide more details about the various complexity measures we used in Figure 4.
I W srank W.) (Neyshabur et al., 2018). This bound is the
Srec-Fro:
722
main motivation of this paper; the two quantities used normalize the margin (7) is the product of spectral norm i.e. I | (or worst case lipschitzness) and sum of stable rank i.e., Ele srank(W, (or an approximate parameter count like rank of matrix).
Pimplying, max, Oz
Boi(z)
21

---

Published as a conference paper at ICLR 2020
2/3 Iw w. 2
E
where Il-Il2,1 the matrix 2-1 norm. As showed by Bartlett et al. (2017), Spec-LI is the spectrally normalized margin, and unlike just the margin, is good indicator of the generalization properties of network.
Spec-L1:
Or. ||h:l|2 |Jلll2 (Wei & Ma), where h, is the 7t hidden layer and J, ah, Jac-Norm: El=
i.e., the Jacobian of the margin with respect to the 8t 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-Fio 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 Vanilla network and in 7 out of the 9 cases, SRN is better than SN. The difference between SRN and SN 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.
Model
Algorithm
Jac-Norm
Spec-
Spec-Fro
Vanilla
17.7
00
00
ResNet-110
Spectral (SN)
17.8
10.8
7.4
SRN-30
17.2
10.7
7.2
Vanilla
16.2
14.60
11.18
Spectral (SN)
16.13
7.23
4.5
WideResNet-28-10
SRN-50
15.8
7.3
4.5
SRN-30
15.7
7.20
4.4
Vanilla
19.2
00
Spectral (SN)
17.8
12.2
9.4
Densenct-
SRN-50
17.6
9.2
SRN-30
17.7
11.8
9.0
Table 5: Values of 90 percentile of log complexity measures from Figure 4. Here oo refers to the situations where the product of spectral norm blows up. This the case in deep networks like ResNet- 1 10 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 better.
Alexnet experiments: Figure shows the test error and generalization error of Alexnet trained with large learning rate of 0.1. Note that, the model fails to learn completely without weight decay. Generalisation Error decreases monotonically with decreasing in the stable rank constraint. Test error is the lowest for 0.5. The constraint becomes too aggressive for even lower than that. The slightly more interesting observation is that having a weight decay actually hurts generalization error while it has slightly positive effect on test error.
Low Learning Rate Here, we train a WideResnnt-28. an Ir = 0.01 and weight decay of 5 x 10-4 on randomly labelled CIFAR 100. for 50 epochs. The results are shown in Table 6 and it further supports that SRN is more robust to random noise than SN or vanilla methods.
with SRN, SN, and vanilla methods with
Stable-30
Spectral
Vanilla
29.04
17.24
1.22
Table 6: Training Error for WideResNet-28-111 10 CIFAR100 with randomized labels, low Ir= 0.01, and with weight decay. (Higher is better.)
With and without weight decay In Figure 7a, we show the training error of Alexnet trained with SGD with and without weight decay (= 5e 4) with learning rate of 0.01. Again, that
22

---

Published as a conference paper at ICLR 2020
Generalization Error
100
w/o WD
w/ WD
40
WD
Test Error
WD
80
20
60
Vanilla
Stable 10
Stable 30
Stable 50
Spectral
Vanilla
Stable 10
Stable 30
Stable 50
Spectral
(a) Generalization Error
(b) Test Error
Figure 6: Test Error and Generalization Error of AlexNet trained with SGD with 0.1 on (clean)
CIFAR-100. (Lower better
more aggressive stable rank constraint decreases fitting the random data ResNet- 110 in Figure 7b.
Similar results seen for
Wd
Training Error
20
100
w/o Wd
Training Error
w/o WD
WD
10
Vanilla
Stable 50
Stable 30
Spectral
Vanilla
Stable 10
Stable 30
Stable 50
Spectral
(a) AlexNet
(b) ResNet110
Figure 7: Training on randomly labelled CIFAR-100 with learning rate of 0.01 and with/ with
out weight decay, (Higher is better.
Low Learning Rate, with and without weight decay clean CIFAR100 In Appendix D.I, show the test accuracies for the clean data with the same confifuration as Table This corresponds to the hihgly nonegenerll learning setting.
Vanilla
Spectral
Stable-50
Stable-30
W/o WD
69.2 + 0.5
69-1..1
69.1 =0.85
69.3 +0.4
With WD
70.4 0.3
71.35 +0.25
40.1
70.6 +0.1
Table 7: Clean Test Accuracy on CIFARIO.
The learning configuration corresponds to the non-
generelizable settings with high learning rate. The corresponding shattering experiments for this setting are shown in Table I.
Training Accuracy 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 train accuracy of
criterion. For Resnetll0 10, WideResnet-28.1 www.ee2....eeeeeeleeee 100, and VGG-19 99% as stopping criterion and report the test accuracy when that train accuracy was achieved for the first time. For Alexnet, SRN-30 never achieves train accuracy higher than 55%, use 55%
23

---

Published as a conference paper at ICLR 2020
3730
260
72
(a) Resnet 10
(b) WideResnet-28
(c) Alexnet
(d) Densenet- 100
(e) VGG-19
Figure 8: Test accuracies on CIFAR100 for clean data using a stopping criterion based on train accuracy. Higher is better.
64.25
Gan
Gen
Gen
94.00
Veniae
Sparand
Stantesp
Statarto
Venata
Speater
Shiieeo
Stakied
Vanill
Specieal
Staisadd
Statelp
Vanilla
Speane
Statiad
Shibeep
(a) Resnetl 10
(b) WideResnet-22 28
(c) Alexnet
(d) Densenet 100
Figure 9: Test accuracies CIFARIO for clean data using stopping criterion based 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 CIFARIO.
CIFARIO experiments In this section, plot results CIFARIO trained using ResNet- 10, Desnenet100, 000, WideResNet-288, 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 99% training accuracy as the criterion and for Alexnet we use 85%. In Figure 10, we plot the test accuracy on clean CIFAR 10 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 I, we plot the training accuracy on CIFARIO when the labels are randomized for Resnet100, and Alexnet. SRN-50 and SRN-30 -00 are much better than Vanilla and SN in this case.
Accuracy
30
Accuracy
96
80
10
Vanilia
Spectral
Stable 50
Stable 30
Vanilla
Spectral
Stable50
Stable-30 30
Resnet 10
(b) Alexnet
Figure 11: Training accuracy on randomly labelled CIFAR-10 (Lower is better).
E ADDITIONAL EXPERIMENTS ON GANS
E.I GAN EXPERIMENTAL SETUP
Datasets and Network Architectures Each of the CIFAR datasets contain total of 50, 000 RGB images in the training set, where each image of size 32 x 32, and further 10, 000 RGB images of the same dimension in the test set. The CelebA dataset contains more than 200K images scaled to size 64 x 64. The model architecture for both the generator and the discriminator was chosen to be 32 layered ResNet (He et al., 2016) due its previous superior performance in other works (Miyato et al., 2018). use Adam optimizer (Kingma & Ba, 2014) which depends on three main hyper- parameters the initial learning rate, 31- the first order moment decay rate and 82- the second
24

---

Published as a conference paper at ICLR 2020
94
Accunty
Accurot
80
Venis
Speciaal
Staskso
Stalaco
Vansla
Opectral
Stasle- 90
Statle 10
Spettral
Staale500 50
Stade Ap
Speatra
Stable
Stable
(a) Resnerl 10
(b) WideResnet-28
(c)
Alexnet
(d) Densenet- 100
Figure 10: Test accuracies on CIFARIO for clean data using the number of epochs as stopping
criterion. Higher is better.
order moment decay rate. We cross-validate these parameters in the set a E {0.0002, 0.0005), ,, 31 E (0,,. B2 E {0.9, 0.999} and chose 0.0002, 31 0.0 and 83 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 the latent variable for the generator was set to 128 and was sampled from 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 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 Dis- tance (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. the case of conditional image generation, also measure Intra-FID FID (Miyato et al., 2018), which is the mean of the FID of the generator, when is conditioned over different classes. Let FID(g, c) be the FID of the generator when it is conditioned the class E C (where C is the set of classes), then, Intra FID = [e| e))
Neural Divergence Setup We train new classifier inline with the architecture in Gulrajani et al. (2019). includes three convolution layers with 16, 32 and 64 channels, a kernel size of 5 x and a stride of 2. Each of these layers are followed by 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 a = 0.0002, 31 = O., 32 = 0.9 for a total of 100, 000 iterations with minibatch of 128 generated samples and 128 samples from the test Set We use the standard WGAN-GP loss function, log (1 + exp (ʃ (x)ak)))) + log (1 + exp
(x (-Xrent)). where I represents the network described above. Finally, we generate 1 Million samples from the generator and report the average log (1 + exp (f (x) over these samples. Higher average value implies better generation as the network in this case is unable distinguish the generated and the real samples.
F.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
For CelebA, used the training set.
25

---

Published as a conference paper at ICLR 2020
Jacobian in Figure 15 and 16 in Appendix E.2 and observe mostly similar trend. In Appendix E.3 (Figure 17), we also show that the discriminator training of SRN-GA REN-GAN is more stable than SN-GAN.
Conditional GANs Figure 12 shows the eLihst of conditional GANs with projection discrimina- lor (Miyato & Koyama, 2018).
Stable Soctral
7.
7.
6.0
4.2
-10
-0.
0.3
0.5
Magniuide of Effective Upochitz vartstre
Figure 12: Comparison: eLhist of the discriminator in the conditional GAN setting with projection discriminator CIFAR100.
Empirical Lipschitzness between real samples and between fake samples. Figure 13 shows the histogram of ehiist of the discriminator for pairs of fake samples i.e. samples generated by the generator. Figure 14 shows eLhist the discriminator when samples came from the dataset.
8.5
Stable
7.5
WGAN-GP
7..5
Frequency
Spectral
6.5 6.5
Frequency
Stable
Spectral
5.5 g
5.5
4.5
4.5
3.5 208
-2.5
2.5
-0.10 0.05 0.00 0.05 0.10 0.15 0.20
-0.1
0.0
Magnitude of Effective Lipschitz variable
Magnitude of Effective Lipschitz variable
(a) Conditional GAN with projection discriminator.
(h) Unconditional GAN setting.
Figure 13: Comparison: eLhist of the discriminator for pairs of samples selected from the generator CIFAR10
ndom
8.5
Randem
Stabin
7.5 2
WGAN-GE GP
77.5 e
Frequency
Spectral
6.5
Frequency
Stable
Spectral
5.5
5..5
-4.5
3.5
-3.5
-2.5
-2.5
0.3 0.6
-0.1 0.1 0.2 0.3 0.4 0.5 0.6 0.7 0.8
Magnitude of Effective Lipschitz variable
Magnitude of Effective Lipschitz variable
(a) Conditional GAN with projection discriminator
Unconditional GAN setting.
Figure 14: Comparison: ehhist of the discriminator for pairs of samples from the real distribution CIFAR10.
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 penalized measure in various algorithms Guirajani et al. (2017); Petzka et al. (2018) (often referred local perturbations) and was independently proposed by Kodali al. (2018). Figure 15
26

---

Published as a conference paper at ICLR 2020
and Figure 16 show the histogram of the 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 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) well for WGAN-GP whereas it varies between fake and real samples for Spectral Normalization GAN (SN-GAN).
Rer Mm GAN
8.5
Randen G
8.5
Stable
7.5
WGAN--P
-7.5
Frequency
6.5
Stable
Speciial
-6.5 g
55.5 5
5.5
-4.5
4.5
3.5
3.5
2.5
2.5
Magnitude Effective Lipschitz variable
Magnitude Effective Lipschitz variable
(a) Conditional GAN with projection discriminator.
(b) Unconditional GAN setting.
Figure 15: Jacobian norm the discriminator the neighhourhood of samples from the generator trained on 10
Random GMA
8.5
Random GAN
8.55
7.5
-7.5
Frequency
Spectral
6.5
Frequency
Stable
Spectral
6.5
5
5.5
4.5
.4.5
.3.5
2.5
-2.5
2
0
4
Magnitude of Effective Lipschitz variable
Magnitude of Effective Lipschitz variable
(a) Conditional GAN with projection discriminator
(b) Unconditional GAN setting.
Figure 16: Jacobian norm of the discriminator in the neighhourhood of the samples from the real dataset (C)
E.3 TRAINING STABILITY
Unconditional GAN
Conditional GAN
Discriminator Loss (Shifted)
Discriminator Loss (Shifted)
Stable 50
Stable 50
Stable 70
Stable 70
Spectral
Spectral
Iteration
Iteration
Figure 17: Loss incurred by the discriminator. The loss of SRN- SRN-GAN GAN with the stable rank constraint of 70 shifted upwards by 0.2 so that we can compare the change of the loss during training opposed to the absolute magnitude of the loss.
27

---

Published as a conference paper at ICLR 2020
Training Stability In Figure 17 we show the discriminator loss during the course of the training as an indicator of whether the generator gets sufficient gradient during training or not. These plots clearly suggest that the discriminator loss is more consistent for SRN than the SN.
F EXAMPLES OF GENERATED IMAGES
F.1 CELEBA IMAGES
For these images, we generated 100 images from the respective models and hand-picked the 10 best images terms of visual quality.
Figure 18: Image samples generated from the unconditional SRN-GAN.
Figure 19: Image samples generated from the unconditional SN-GAN.
28

---

Published as a conference paper at ICLR 2020
F.2 CIFARIO-UNCONDTTION GAN
(a)
(b) SRN-50-GAN
(c) SN-GAN
(d) WGAN-GP
Figure 20: Image samples generated from the unconditional SRN-GAN, SN-GAN, and WGAN-GP.
29

---

Published as a conference paper at ICLR 2020
F.3 MAARIO-CONDITONAL SRN-GAN
(a) Air- hir-planes
(b) Cars
(c) Birds
(d) Cats
(c) Deers
(f) Dogs
Figure 21: Image samples generated from the conditional SRN-GAN with projection discriminator.
30


Reviews:
[{"review_id": "rylcn0iiYB", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Stable Rank Normalization for Improved Generalization in Neural Networks and GANs\n\nSummary:\n\nThis paper proposes to normalize network weights using the Stable Rank, extending the method of spectral normalization. The stable rank is the ratio of the squared frobenius norm to the squared spectral norm (the top singular value). The authors motivate this decision in the context of lipschitz constraints and noise sensitivity. The proposed method (combined with spectral norm as SRN alone does not explicitly subsume SN) is tested for both classification (using a wide range of popular models on CIFAR) and GAN training. Performance (classification accuracy and FID/IS) is measured and several auxiliary investigations are performed into generalization bounds, sample complexity, and sensitivity to hyperparameters.\n\nMy Take:\n\nThis paper motivates and presents an interesting extension of spectral norm, and evaluates it quite well with thorough experiments in a range of settings. The method looks to be reasonably accessible to implement, although its compute cost is not properly characterized and some details (like the orthogonalization step necessary in power-iteration for more than one SV) seem to be omitted. My two main concerns are that the results, while good, are not especially strong (the relative improvement is not very high) and that the paper could be made substantially more concise to fit within the 8 page soft limit (I felt there was plenty of material that could be moved to the appendix). All in all this is a reasonably clear accept to me (7/10) that with some cleanup could be a more solid 8, and I argue in favor of acceptance.\n\nNotes\n\n-The paper should characterize the runtime difference between SRN and SN. It is presently unclear how computationally intensive the method is. What is the difference in time per training iteration? The authors should also indicate their hardware setup and overall training time.\n\n-I found table 1 confusing as it lacks the test error. Are the test errors the same for all these models and the authors are just showing that for certain settings the SRN models have higher training error? If there is a difference in testing error, then this table is misleading, as one cares little about the training error if the test errors vary. If the test errors are approximately the same, then why should I care if the training error is higher? This would just be a way to decrease the stated “generalization gap,” which is not necessarily indicative of a better model (vis-à-vis the commonly held misconception that comparing training error between models is properly indicative of relative overfitting). \n\n-Nowhere (that I could spot) in the body of the paper is it explained what “Stable-50”, “SRN-50”, and “SRN-50%” are. I assume these all mean the same thing and it refers to the choice of the c hyperparameter, but this should be explicitly stated so that the reader knows which model corresponds to which settings.\n\nMinor\n\n-The footnotes appear to be out of order,  footnote 1 appears on page 9\n\n-There are typos such as “simiplicity,” please proofread thoroughly.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly."}, "extra_text": {}}, {"review_id": "rJgwtQhPFH", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 8, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "While spectral normalization is often used to improve generalization by\ndirectly bounding the Lipschitz constant of linear layers, recent works have\nhighlighted alternate methods that aim to reduce generalization error.  This\npaper shows how to implement these \"stable rank\" normalizations with little\ncomputational overhead.  The authors then apply the method to a wide variety of\nclassification and GAN problems to show the benefits of stable rank\nnormalization.\n\nThis is a good paper and can be accepted.  The added value comes from their\nThm. 1, where they detail precisely how to project a real matrix onto one of\nlower srank while preserving the largest k eigenvalues.  The spectral preservation\nk seems to be a new feature of their method. Full proofs and additional results are\nprovided in appendices.  There seems to be enough information to implement\nthe described methods.\n\nThe paper is carefully written and introductory sections do a great job of putting\nthe problem in perspective.  Very few typos (\"calssification\", run a spell check).\n\n--------- Fun to think about ------ here are some extra comments\n\nSome related older introductory approaches could also be quickly mentioned:\n - linear layers represented as \"bottlenecks\" to enforce low rank explicitly\n - or solving in manifold of reduced-rank matrices directly\n\nFor simplicity, they target the same srank r=c*min(m,n) for all layers, even though only the sum\nof sranks is important.  For CNNs with only a few linear layers is there any observable\ndifference by lightly deviating from this?  Does the first linear layer typically contribute\nthe lion's share to the sum of sranks?\n\nIt is interesting that by only addressing the linear layers of deep CNNs they\nare able to see consistent improvements. [i.e. 3 linear layers after 101 CNN layers].\n This makes me wonder whether future work will also address how \"stable rank\"\nconcepts might be extended to the convolutional layers.  As a starting point, spectral\nvalues of the block-circulant matrices corresponding to convolutions have been\ndescribed [ Sedghi et al. \"Singular Values of Convolutional Layers\" ].\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper at least twice and used my best judgement in assessing the paper."}, "extra_text": {}}, {"review_id": "BkepTNsk5H", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "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.\n\nStable 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?\n\nMy 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:\n\n- 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. \n\n- 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.\n\n\nOverall, 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. \n\n\n*************************\n\nAfter author rebuttals:\n\nAuthors have address my concerns adequately in the last revision and improved the experiment section. Therefore, I increase my score to 6.", "extra_scores": {"experience_assessment": "I have published in this field for several years.", "review_assessment:_checking_correctness_of_experiments": "I carefully checked the experiments.", "review_assessment:_thoroughness_in_paper_reading": "I read the paper thoroughly.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}]

Author rebuttal:

Meta-review: The authors propose stable rank normalization, which minimizes the stable rank of a linear operator and apply this to neural network training. The authors present techniques for performing the normalization efficiently and evaluate it empirically in a range of situations. The only issues raised by reviewers related to the empirical evaluation. The authors addressed these in their revisions. 
Decision: Accept (Spotlight)