GENERALIZATION GUARANTEES FOR NEURAL NETS VIA HARNESSING THE LOW-RANKNESS OF JACOBIAN
Authors: Samet Oymak
Zalan Fabian
Mingchen Li
Mahdi Soltanolkotabi
Venue:  (2020)
Keywords: Theory of neural nets
low-rank structure of Jacobian
optimization and generalization theory

Abstract: Modern neural network architectures often generalize well despite containing many more parameters than the size of the training dataset. This paper explores the generalization capabilities of neural networks trained via gradient descent. We develop a data-dependent optimization and generalization theory which leverages the low-rank structure of the Jacobian matrix associated with the network. Our results help demystify why training and generalization is easier on clean and structured datasets and harder on noisy and unstructured datasets as well as how the network size affects the evolution of the train and test errors during training. Specifically, we use a control knob to split the Jacobian spectum into ``information" and ``nuisance" spaces associated with the large and small singular values. We show that over the information space learning is fast and one can quickly train a model with zero training loss that can also generalize well. Over the nuisance space training is slower and early stopping can help with generalization at the expense of some bias. We also show that the overall generalization capability of the network is controlled by how well the labels are aligned with the information space. A key feature of our results is that even constant width neural nets can provably generalize for sufficiently nice datasets. We conduct various numerical experiments on deep networks that corroborate our theoretical findings and demonstrate that: (i) the Jacobian of typical neural networks exhibit low-rank structure with a few large singular values and many small ones leading to a low-dimensional information space, (ii) over the information space learning is fast and most of the labels falls on this space, and (iii) label noise falls on the nuisance space and impedes optimization/generalization.

Under review as a conference paper at ICLR 2020
GENERALIZATION GUARANTEES FOR NEURAL NETS VIA HARNESSING THE LOW-RANKNES, OF JACOBIAN
Anonymous authors Paper under double-blind review
ABSTRACT
Modern neural network architectures often generalize well despite containing many more parameters than the size of the training dataset. This paper explores the generalization capabilities of neural networks trained via gradient descent. We de- velop data-dependent optimization and generalization theory which leverages the low-rank structure of the Jacobian matrix associated with the network. Our results help demystify why training and generalization is casier on clean and structured datasets and harder on noisy and unstructured datasets well as how the network size affects the evolution of the train and test errors during training. Specifically, we use control knob to split the Jacobian spectum into "information" and "nuisance" spaces associated with the large and small singular values. We show that over the information space learning is fast and one can quickly train model with zero training loss that can also generalize well. Over the nuisance space training is slower and early stopping can help with generalization at the expense of some bias. We also show that the overall generalization capability of the network is controlled by how well the labels are aligned with the information space. key feature of our results is that even constant width neural nets can provably generalize for suffi- ciently nice datasets. We conduct various numerical experiments on deep networks that corroborate our theoretical findings and demonstrate that: (i) the Jacobian of typical neural networks exhibit low-rank structure with a few large singular values and many small ones leading to low-dimensional information space, (ii) over the information space learning is fast and most of the labels falls on this space, and (iii) label noise falls the nuisance space and impedes optimizationngeeealliaaoo..
INTRODUCTION
1.1
MOTIVATION AND CONTRIBUTIONS
Deep neural networks (DNN) are ubiquitous in a growing number of domains ranging from computer vision to healtheare. State-of-the-art DNN models are typically overparameterized and contain more parameters than the size of the training dataset. It is well understood that in this overparameterized regime, DNNs are highly expressive and have the capacity to (over)fit arbitrary training datasets including pure noise Zhang et al. (2016). Mysteriously however neural network models trained via simple algorithms such as (stochastic) gradient descent continue to predict well or generulize on yet unseen test data. In this paper we wish to take a step towards demystifying this phenomenon and help explain why neural nets can overfit to noise yet have the ability to generalize when real data sets used for training. In particular gradient descent. Using the Jacobian mapping associated with the neural network we characterize directions where learning is fast and generalizable versus directions where learning is slow and leads to overfitting. The main contributions of this work are as follows.
explore the generalization dynamics of neural nets trained via
Leveraging dataset structure: We develop new optimization and generalization results that can harness the low-rank representation of semantically meaningful datasets via the Jacobian mapping of the neural net. This sheds light as to why training and generalization is easier using datasets where the features and labels are semantically linked versus others where there is no meaningful relationship between the features and labels (even when the same network is used for training).
Bias-variance tradeoffs: We develop a generalization theory based on the Jacobian which decou- ples the learning process into information and nuisance spaces. We show that gradient descent almost perfectly interpolates the data over the information space (incurring only a small bias). In contrast, optimization over the nuisance space is slow and results in overfitting due to higher variance.

---

Under review as a conference paper at ICLR 2020
Network size vs prediction bias: We obtain data-dependent tradeoff's between the network size and prediction bias. Specifically, we show that larger networks result in smaller prediction bias, but small networks still generalize well, especially when the dataset is sufficiently structured, but typically incur a larger bias. This compares favorably with recent literature on optimization and generalization of neural networks Jacot et al. (2018); Arora al. (2019); Du et al. (b); Allen-Zhu et al. (2018b); Cao & Gu (2019); Ma et al. (2019); Allen-Zhu et al. (201 20); Brutzkus et al. (2017) where guarantees only hold for very wide networks with the width of the network growing inversely proportional to the class margins or related notions. See Section 3 for further detail.
Pretrained models: Our framework does not require random initialization and our results con- tinue apply even with arbitrary initialization. Therefore, our results may shed light on the generalization capabilities of networks initialized with pre-trained models commonly used in meta/transfer learning. Our extensive experiments strongly suggest Jacobian adapts over time in favorable and data-dependent fashion shedding light on the properties of (pre)trained models.
1.2 MODEL AND TRAINING
Our theoretical analysis will focus on neural net- works consisting of one hidden layer with in- put features, k hidden neurons and K outputs as depicted in Figure 1. We use W Rexd and V é R denote the input-to-hidden and hidden- to-output weights. The overall input-output relation- ship of the network a function [(: W)+ Rdd R-K that maps an input a e IR' to an output via (1.1)
IX
outpun luyer label
x f(; W) == (W.).
Impu: Layer
Given a dataset consisting of n feature/label pairs (z,, y/) with x; Rd representing the features and Yi RR the associated labels representing one of K classes with one-hot encoding (i.e. yı e {e), e2,..., where e₁ R has all zero en- tries except for the 9th entry which is equal to one). To learn this dataset, we fix the output layer and train over W via'
layer
Figure I: Illustration of a one-hidden layer neu- ral net with d inputs, & hidden units and K outputs along with a one-hot encoded label.
min We
L(W)
V
(Wa;) - yi 1
(1.2)
It will be convenient to concatenate the labels and prediction vectors follows
y
Vf W)
y E Rak
and f(W)= = V (a W)
RRn
(1.3)
yn
Using this shorthand we can rewrite the loss (1.2) as
min Wekkod
L(W): If(W) y11
(1.4)
To optimize this loss starting from an initialization Wo run gradient descent iterations of the form
W W, -VV (WW+)
(1.5)
with step size n, In this paper we wish to explore the theoretical properties of the model found by such iterative updates with an emphasis on the generalization ability.
1.3 INFORMATION AND NUISANCE SPACES
In order to understand the generalization capabilities of models trained via gradient descent need to develop better insights into the form of the gradient updates and how it affects the training dynamics. To this aim let aggregate the weights each iteration into large vector w, :=vect( W,) Ridd define the misfit/residual vector r r(w) := s(w) y and note that the gradient updates take the form
1c++1 wy 7/ vV ((ww) where
vL(w) vL(w)= I (ww T
For clarity of exposition, we focus only on optimizing the input layer. However, as shown in the supplementary. the technical approach is quite general and applies arbitrary multiclass nonlinear least-squares problems. In particular, the proofs stated apply one-hidden layer networks where both layers trained.
2

---

Under review as a conference paper at ICLR 2020
1. Large singulars
1. Small singulars lonening goncralize
Jacobian spectrum
3. Rasy to generalize
2. Fast learuing
Learning slows down nussance space
W
Fast learning over info space Wo
W Wearly
epectrum cut-off
leval
At Wearly residual on info space is almost 0
Info space
Nuisance space
(a) Depiction via the Jacobian spectrum
(b) Depiction parameter space
Figure 2: Depiction of the training and generalization dynamics of gradient methods based on the information and nuisance spaces associated with the neural net Jacobian.
Here, J(w) E RnKxkd denotes the Jacobian mapping associated with f defined as J(w) @f(w) Eve Due to the form of the gradient updates the dynamics of training is dictated by the spectrum of the Jacobian matrix as well as the interaction between the residual vector and the Jacobian. If the residual vector is very well aligned with the singular vectors associated with the top singular values of J [(w). (w). the gradient update significantly reduces the misfit allowing substantial reduction in the train error. Thus to provide more precise understanding of the training dynamics and generalization capabilities of neural networks it is crucial to develop better understanding of the interaction between the Jacobian and the misfit and label vectors. To capture these interactions we require a few definitions.
Definition 1.1 (Information & Nuisance Spaces) Consider matrix J e RaKsp with singular value decomposition given by
nk
J J= Euu = Udiag (A1, .an)) VT:
with X 2 A2 2 ... An denoting the singular values of J in decreasing order and {u,)nk \nk Rak and (v,) (,.)nk IRP the corresponding left and right singular vectors forming the orthonormal basis matrices U Rakknn and V RRxnk For spectrun cutoff a obeying 0 S X1 let r(a) denote the index of the smallest singular value above a. We define the information and nuisance spaces associated with J as I == span( (u,))-1) and N span {u.) Kn. s
In this paper we shall use either the expected value of the Jacobian at the random initialization the Jacobian at one of the iterates define the matrix J and the corresponding information/nuisancee
spaces. More, specifically we will J either Therefore, one can effectively think of the information space as the span of the prominent singular vectors of the Jacobian and the nuisance space as its complement. In particular, as we demonstrate in Section 4 the Jacobian mapping associated with neural networks exhibit low-rank structure with few large singular values and many small ones leading natural choices for the cut-off value a as well as the information and nuisance spaces. Furthermore, we demonstrate both (empirically and theoretically) that learning fast over the information space leading significant reduction in both train/test accuracy in the early stages of training. However, after a certain number of iterations learning shifts to the nuisance space and reduction the training error significantly slows down (see Fig. 2). Furthermore, subsequent iterations in this stage lead to slight increase in test error.
(L[J(WW)TT ((Wo))) or =J (W,).
MAIN RESULTS
Our main results establish multi-class generalization bounds for neural networks trained via gradient descent. First, we will focus on networks where both layers are randomly initialized. Next we will provide guarantees for arbitrary initialization with the goal of characterizing the generalization ability of subsequent iterative updates for a given (possibly pre-trained) network in terms of Jacobian mapping. In this paper focus activations which smooth and have bounded first and
3

---

iåd. Under review as a conference paper at ICLR 2020
second order derivatives. This would for instance apply the softplus activation ((2) log (1 + (1+ We note that utilizing a proof technique developed in Oymak & Soltanolkotabi (2019) for going from smooth to ReLU activations it is possible to extend results to ReLU activations with proper modifications. We avoid doing this in the current paper for clarity of exposition. Before we begin discussing main results discuss some notation used throughout the paper. For matrix X RRaxd we use mmin (X) and & max (X) )= | to denote the minimum and maximum singular value of X. For two matrices A and B we use A @ B and A B denote their Hadamard and Kronecker products, respectively. For PSD matrix A É Raxa with eigenvalue decomposition A = Ei=1 A,u,u," the square root matrix is defined as A == Σ Vu,uu?" We also use A to denote the pseudo-inverse of A. In this paper we mostly focus on label vectors y which are one-hot encoded i.c. all entries are zero except one of them. For subspace S = R" and point æ e R", (x)) denotes the projection of x onto S. Finally, before stating our results we need to provide quantifiable measure of performance for trained model. Given a sample (æ, y) R R from distribution D, the classification enror of the network W with respect to D is defined as
EnD (W)= = P( arg max Ye arg max Se( W))
(2.1)
1stsk
1stsk
2.1 RESULTS FOR RANDOM INITIALIZATION
To explore the generalization of randomly initialized networks, we utilize the neural tangent kernel.
Definition 2.1 (Multiclass Neural Tangent Kernel (M-NTK) Jacot et al. (2018)) Lef R² be a vector with (O, Ia) distribution. Consider a set of n input data points 21, 22.-... Ey e IRd aggregated into the rows of a data matrix X e Ruad Associated to the activation & and the input data matrix X we define the multiclass kernel matrix
E(X) Ix @ [[(00 (Xw)
(X o ( (Xw)))
where Ix is the identity matrix of size K. Here, the E th diagonal block of Σ(X) corresponds to the kernel matrix associated with the E th network output for 1 s E K. This kernel is intimately related to the multiclass Jacobian mapping. In particular, suppose the initial input weights Wo are distributed i.i.d. (0,11) 1) and the output layer V has i.i.d. zero-mean entries with v²/K K variance. Then E[J (W)(W)) (W)) = (X). We use the square root of this multiclass kernel matrix (i.e. 1/3 to define the information and nuisance spaces for our random initialization result.
The following theorem (non-rigorous) simplification of our main result Theorem 6.24 where we ignore constants and log factors, and state weaker but simpler generalization bound.
Fix numbers I 2 1 and O. Consider i.i.d. training dataset ((x,, y:) Rd R with unit length input samples and one-hot encoded labels. Consider the neural net in (1.1) parameterized by W and initialized with Wo ~ N(001) entries. Set V with i.i.d. Rademacher entries (properly scaled). Define the information I and nuisance N spaces with respect to Σ 2(X)11
Theorem 2.2
no/ with spectrum cutoff on nK per Definition 1.1. Furthermore, assume
r Lloggn
k2
(2.2)
a
Then after oc o/22 gradient iterations of (1.5), with high probability, training loss obeys
[[((W)) el1a2 & [w(yy) + VT,
(2.3)
Furthermore, the classification error obeys
[I
r
Erro (WT)
Vn
ayn
This theorem shows that even networks of moderate width achieve small generalization error if (I) the data has low-dimensional representation i.e. the kernel is approximately low-rank and (2) the inputs and labels semantically-linked i.e. the label vector y mostly lies the information space.
4

---

Under review as a conference paper at ICLR 2020
The generalization error has two core components: bias and variance. The bias component (v)lle/// e arises from the training loss and corresponds to the portion of the labels that falls over the nuisance space. The variance component T/ay/n corresponds to the Rademacher complexity of the model space which connects to the distance |/ Wol r--
Generalization bound:
If y is aligned with the information space, the bias term (y) will be small. Additionally, if the kernel matrix is low-rank, we can pick a large a to ensure small variance as well as small network width. In partieular with constant the required network width is logarithmic in n.
We note however that our results continue to apply even when the kernel is not approximately low-rank. In particular, consider the extreme case where we select av vx== V (E(X))
This sets I= = RKK and [y) 1t₂ = O. For this case, the more general Theorem 6.24 yields
K
K' K'n log (2.4)
ETT (WT)& S
V 'X)y while requiring a width of k Vn
X1
We note that in this special case our results improve upon the required width in recent literature Arora et al. (2019)² that focuses on K = 1 and a conclusion of the form (2.4). However, as we demonstrate in our numerical experiments in practice À is very small or even zero (e.g. the toy model in Section 2.3) so that requirements of the form (2.4) may require unrealistically (or even infinitely) wide networks. In contrast, our results apply all Jacobian spectrums, however can further harness the low-rank structure of the Jacobian to give even stronger bounds.
Small width is sufficient for generalization: Based on our simulations the M-NTK indeed has low-rank structure with a few large cigenvalues and many smaller ones. As a result a reasonable scaling choice of is constant. In that case our result states that as soon as the number of hidden nodes are logarithmic in n, good generalization can be achieved. This favorably compares to related works Jacot et al. (2018); Arora et al. (2019); Du et al. (2018b); Allen-Zhu et al. (2018b); Cao & Gu (2019) where network size is required to grow polynomial with n and inversely with the distance between the inputs or other notions of margin.
Network size-Bias tradeoff:: Based on the requirement (2.2) if the network is large (in terms of # of hidden units k), we can choose a small cut-off a. This in turn allows us to enlargen the information space and reduce the training bias further. In summary, as the network capacity grows, we can gradually interpolate finer detail and reduce bias.
Fast convergence: Note that the number of gradient iterations is upper bounded by r/a². Hence, the training speed is dictated by and is inversely proportional to the the smallest singular value over the information space. Specifically, picking a be a constant, convergence on the information space will be fast requiring only constant number of iterations to reach any fixed accuracy (see (2.3)).
2.2 GENERALIZATION GUARANTEES WITH ARBITRARY INITIALIZATION
Our next result provides generalization guarantees from an arbitrary initialization which applies to pre-trained networks (e.g. those that arise transfer learning applications) as well as intermediate gradient iterates as the weights evolve. This result has a similar flavor to Theorem 2.2 with the key difference that the information and nuisance spaces are defined with respect to any arbitrary initial Jacobian. This shows that if pre- pre-trained model' provides a better low-rank representation of the data in terms of its Jacobian, is more likely to generalize well. Furthermore, given its deterministic nature the theorem can be applied at any iteration, implying that if the Jacobians of any of the iterates provides a better low-rank representation of the data then one can provide sharper generalization guarantees. The following theorem is a mon-rigorous) simplification of Theorem 6.21.
Theorem 2.3 Let l 2 1,a be arbitrary sealars. Consider i...d. training data {(x,, y: E &R with unit length inputs and one-hot encoded labels. Also consider a neural net with k hidden nodes as in (1.1) parameterized by W. Let Wo be an arbitrary initial weight matrix and assume the output matrix has bounded entries obeying [Vlle. S "TEK Define the nuisance space N associated
with I ((W)) based on spectrum cutoff av/n. Set the initial residual ro ((W)) - y Rak and assume ||rolles lg $ vú. Suppose l k2 /' After T x T/a² iterations (1.5) with constant learning rate, training loss obeys: (l. yll,, & [[T
Bassdd on our understanding Arora et al. (2019) requires the number of hidden units to be on the order of I 2 n² //a. Hence our result reduces the dependence on width by a factor of at least n /X2.. Peg. obtained by training with data in a related problem is common in transfer learning.
5

---

Under review as a conference paper at ICLR 2020
Also with high probability, classification error obeys: Erro (r) s
[ vn
+ +e" +e
As with the random initialization result, this theorem shows that as long as the initial residual is sufficiently correlated with the information space, then high accuracy can be achieved for neural networks with reasonable size. As with its randomized counterpart this result also allows us to study various tradeoffs between bias- and network size-bias. Crucially however this result does not rely on random initialization. The reason this is partieularly important is two fold. First, in many scenarios neural networks are not initialized at random. For instance, in transfer learning the network is pre-trained via data from a different domain. Second, as we demonstrate in Section 4 as the iterates progress the Jacobian mapping develops more favorable properties with the labels/initial residuals becoming more correlated with the information space of the Jacobian. As mentioned earlier, due to its deterministic nature the theorem above applies in both of these scenarios. particular, if a pre-trained model provides better low-rank representation of the data via its Jacobian, it is more likely to generalize well. Furthermore, given its deterministic nature the theorem can be applied at any iteration by setting Wn WF. implying that if the Jacobians of any of the iterates provides better low-rank representation then one can provide better generalization guarantees. Our numerical experiments demonstrate that the Jacobian of the neural network adapts to the dataset over time with a more substantial amount of the labels lying on the information space. While we defer the rigorous theory of this adaptation to future, Section D provides proof sketch of evolution of Jacobian rank for a simple dataset model. Such a result when combined with our result above can potentially provide significantly tighter bounds. This is particularly important in light of recent literature Chizat & Bach (2018b); Ghorbani et al. (2019c); Yehudai & Shamir (2019) suggesting a significant generalization gap between kernel methoos/limearized neural nets when compared with neural nets operating beyond the linearized regime (e.g. mean field regime). As a result we view our deterministic result as a first step towards moving beyond the NTK regime.
2.3 CASE STUDY: GAUSSIAN MIXTURE MODEL
To illustrate concrete example, we consider a distribution based on multiclass mixture models.
Definition 2.4 (Gaussian mixture model) Consider size n dataset { y:) W E R² RK We assume this dataset consists of K classes each comprising of clusters with a total of KC clusters. We index each cluster with (e, denoting the Eth cluster from the fth class. We assume the dataset in cluster (f, E) is centered around a cluster center P2,77 IRd with unit Euclidian norm. We assume the dataset is generated i..dd with the cluster membership assigned uniformly of the clusters with 1 and the input samples associated with the cluster (E, E) are generated i.i.d. according to N (ur,,, Ial with the corresponding label set to the one-hot encoding of the class E i.e. eg. Note that the cluster indexed by (I,T) contains म data points satisfying E[A 7 n//n/KK..
probability KG
This distribution is an ideal candidate to demonstrate why the Jacobian of the network exhibits low-rank or bimodal structure. Let consider the extreme case 0 where we have discrete input distribution over the cluster centers. In this scenario, the multi-class Jacobian matrix is at most rank
K²C # of output nodes # of distinct inputs.
as there are (i) only KC distinct input vectors and (ii) K output nodes. We can thus set the information space to be the top C²C eigenvectors of the multiclass kernel matrix E(X). As formalized in the appendix, it can be shown that
The singular values of the information space grow proportionally with n/KC.
The concatenated label vector y perfectly lies on the information space.
In Figure 3 we numerically verify that the approximate rank and singular values of the Jacobian indeed scale as above even when > O. The following informal theorem leverages these observations to establish generalization bound for this mixture model. This informal statement is for exposition purposes. See Theorem A.3 in Appendix A for a more detailed result capturing the exact dependencies (e.g. Ç, B, log.). In this theorem we use 2 to denote inequality up to constan//lggarthmii factors.
Theorem 2.5 (Generalization for Gaussian Mixture Midile-simplified) Consider a data set of size n consisting of input/label pairs (x,, } | Rd x RK generated according to Def. 2.4 with the standard deviation obeying o S K. Let M = [M4,1 ... Mx,c]" I be the matrix obtained by aggregating all the cluster centers and let g NO, Ia). Also les E(M) RCCK be the M-NTK

---

Under review as a conference paper at ICLR 2020
associated with the cluster centers M per Def. 2.1. Furthermore, set AM Ammma ( (MM)), and
assume AM > O. If the number of hidden nodes obeys l. 2 T'K"c", after T = 2KK'C gradient iterations, with high probability, the model obeys Erro (T) S T
AM
Am
K²C
nAM
We note that AM captures how diverse the cluster centers are. In this sense XM 0 intuitively means that neural network. specifically the neural tangent kernel, is sufficiently expressive to interpolate the cluster centers. In fact when the cluster centers are in generic position XM scales like constant Oy- mak & Soltanolkotabi (2019). This theorem focuses on the regime where the noise level a is small. In this case one can achieve good generalization as soon as the sample size scales as n 2 K2C which is the effective rank of the M-NTK matrix. This result follows from our main result with random ini- tialization by setting the cutoff at a² ~ K3C. demonstrates that in this model a does indeed scale as constant. Finally, the required network width is independent of n and only depends on K and C specifically k 2. K* This compares favorably with Arora et al. (2019) which concerns the case. In particular, Arora et al. (2019) requires k 2 n² <>> which depends on n (in lieu of K and C)) and the minimum eigenvalue Ax of the NTK matrix E(X) ) (rather than AM). Furthermore, as O, E becomes rank deficient and A - 0 so that Arora et al. (2019) requires infinite width.
C=
10a
20
C== 25
O= 40
C'= 50
10'
10
AM. This
90 180
360 450
Singular value index (x-axis marks K²C)
Figure 3: The singular values of the normalized Jacobian spectrum / KC ((W)) of a neural network with K = 3. Here, the data is gener- ated according to the Def. 2.4 with K classes and a = 0.1. The cluster centers are picked so that the distance between any two is at least 0.5. We consider two cases: n = 30C (solid line) and n 60C (dashed line). These plots demonstrate that the top KC singular values grow proportional to vni.
n
PRIOR ART
Neural networks have impressive generalization abilities even when they are trained with more parameters than the data Zhang et al. (2016). Thus, optimizatiin//eneerllzaaaa nets have been the topic of recent literature Zhang et al. (2016). Below we discuss the works on statistical learning, optimization, and implicit bias.
properties of neural
Statistical learning theory: Statistical properties of neural networks have been studied since 1990's Anthony& & Bartlett (2009); Bartlett al. (1999); Bartlett (1998). With the success of deep networks, there is a renewed interest in understanding capacity of the neural networks under different norm constraints or network architectures Dziugaite & Roy (2017); Arora al. (2018); Neyshabur et al. (2017b); Golowich et al. (2017). Bartlett et al. (2017); Neyshabur et al. (2017a) established tight sample complexity results for deep networks based on spectral norms. See also Nagarajan & Kolter (2019) for improvements via leveraging various properties of the inter-layer Jacobian and Long & Sedghi (2019) for results with convolutional networks. Related, Arora et al. (2018) leverages compression techniques for constructing tighter bounds. Yin et al. (2018) jointly studies statistical learning and adversarial robustness. These interesting results, provide generalization guarantees for the optimal solution to the empirical risk minimizer.
Properties of gradient descent: There a growing understanding that solutions found by first-order methods such as gradient descent have often favorable properties. Generalization properties of stochastic gradient descent is extensively studied empirically Keskar et al. (2016); Hardt al. (2015); Sagun et al. (2017); Chaudbari et al. (2016); Hoffer et al. (2017); Goel & Klivans (2017); Goel et al. (2018). For linearly separable datasets, Soudry et al. (2018); Gunasekar et al. (2018); Brutzkus et al. (2017); Ji & Telgarsky (201 8a;b) show that first-order methods find solutions that generalize well without an explicit regularization for logistic regression. An interesting line of work establish connection between kernel methods and neural networks and study the generalization abilities of kernel methods when the model interpolates the training data Dou & Liang (2019); Belkin et al. (2018a;b: 2019); Liang& & Rakhlin (2018); Belkin et al. (2018c). Chizat & Bach (2018a); Song et al. (2018); Mei et al. (2018); Sirignano & Spiliopoulos (2018); Rotskoff & Vanden Vanden-Eijnden (2018) relate the distribution of the network weights Wasserstein gradient flows using mean field analysis.
7

---

Under review as a conference paper at ICLR 2020
Global convergence and generalization of neural nets: Closest to our work, recent literature Cao & Gu (2019); Arora et al. (2019); Ma et al. (2019); Allen-Zhu et al. (2) provides generalization bounds for overparameterized networks trained via gradient descent. Also see Li et al. (2018); Huang et al. (2019) for interesting visualization of the optimization and generalization landscape. Jacot al. (2018) introduced NTK and observed that principal directions of NTK is optimized faster than smaller eigendirections for infinitely wide networks. In connection to this, our Def 1.1 helps quantify the low-rankness and bimodality of the Jacobian spectrum (same as NTK for random initialization). Similar to Thm 2.2, Arora et al. (2019) uses the NTK to provide generalization guarantees in a similar framework to Jacot et al. (2018) (see (2.4) for comparison). Li et al. (2019a) leverages low-rank Jacobian structure to establish robustness to label noise. Very recent work Su & Yang (2019) uses low-rankness to better capture approximation power of neural nets. These works build on global convergence results of randomly initialized networks Du et al. (201 8b;a); Allen-Zhu et al. (201 8b); Chizat & Bach (2018b); Zhang et al. (2019); Nitanda & Suzuki (2019); Oymak & Soltanolkotabi (2018); Zou et al. (2018) which study the gradient descent trajectory via comparisons to a NTK linearization. These results however typically require unrealistically wide networks for optimization where the width grows poly in and poly-inversely proportional to the distance between the input samples. Example distance measures are class margin for logistic loss and minimum eigenvalue of the NTK matrix for least-squares. Our work circumvents this issue by allowing a sspacity-dependent interpolation. We prove that even small networks (e.g. of constant width) can interpolate the data over -owdiimesiional information space without making restrictive assumptions on the input. This approach also leads to faster convergence rates. In terms of generalization, our work has three distinguishing features: (a) bias- variance tradeoffs by identifying information/nuisance spaces, (b) no margin/distance/minimum eigenvalue assumptions on data, (c) the bounds apply to multiclass classification as well as pre-trained networks (Theorem 2.3).
Finally, low-rankness of the Jacobian plays central role in this work. Hessian and Jacobian of neural nets are investigated by multiple papers which contain related findings on the bimodal (approximately low-rank) spectrum Papyan (2018); Ghorbani et al. (2019b); Papyan (2019b); Sagun al. (2017); Li et al. (2019b); Javadi et al. (2019). Our key empirical contribution is establishing (in great detail) that multiclass Jacobian adapts over time to align its information space with the labels better represent the data. This alignment leads to tighter generalization bounds in our analysis shedding light on representation learning and gradient dynamics beyond NTK.
At Inttinlization
NUMERICAL EXPERIMENTS
10a
tradning
We present experiments demonstrating our theoretical findings on two popular image classification datasets. In this section we focus on a set of CIFAR- 10 exper- iments and discuss how our theory is strongly sup- ported by what we observe in practice. To provide more detail and show that our theory holds across different datasets, in addition to the experiments dis- cussed in this section we perform additional experi- ments on a modified 3-class version of CIFAR-10 10 and MNIST in Appendix C.
Hisoogon
10
10"
10P
10a
10a
10a
Top 1030 singular values
Experimental setup. The CIFAR- 10 dataset consists of 50k training images and 10k test images in 10 classes. We demonstrate our results on ResNer20, a state-of-the-art architecture with a fairly low test error on this dataset (8. 75% test error reported) and relatively few parameters (0.27M). In all of our experiments we set the information space to be the span of the top 50 singular vectors (out of total dimension of Kn s 500000) of the neural network Jacobian. In order to be consistent with our theoretical formulation we make the following modifications to the default ResNet20 architecture: (1) we scale the output of the final fully connected layer to ensure that the output is small, consistent with Theorem 2.2 (2) we turn off batch normalization and (3) we do not pass the network output through a soft-max function. We train the network with SGD on least-squares loss with batch size 128 and without any form of data augmentation. We set the initial learning rate to 0.1 and adjust the learning rate schedule and number of epochs depending quickly. The figures in this section depict the minimum error over a window consisting of the last 10 epochs for visual clarity. We also conduct two sets of experiments to illustrate the results on
Figure 4: Histogram of the top 1000 Jacobian singular values on the CIFARIO dataset.
the particular experiment so
achieve good fit to the training data
8

---

Under review as a conference paper at ICLR 2020
lle eg
Trolez
Trolez
J frasn
0.38081
0.92465
0.37114
0.92858
0.9869
0.16131
0.98669
0.1626
Table I: Depiction of the alignment of the initial residual with the information/nuisancee
space using uncorrupted data and a Multi-class ResNet20 model trained with SGD.
10P
100
Residaal ewerg
Teeehtal energy
Tril
10rl
Fall
0.5
10"2
004
10ra
10-4
100
100
200
Epucllo
Elpoclss
Epucia
(a) Final train Jacobian.
(b) Final test Jacobian.
(c) Training and test error.
Figure Evolution of the residual (r, f(W,)- y) along the informaation/nuisance spaces of the final Jacobian on (a) the training data and (b) the test data and c)
misclassification error on training and test. This experiment uses uncorrupted labels.
uncorrupted and corrupted data, In this section we highlight some of these results and relate them to theoretical framework. For the complete set of experiments refer the reader to Appendix C. Jacobian eigenstructure. Calculating the exact full singular value decomposition of the Jacobian at this scale (500k 270k) is not tractable due to computation/memory limitations. In order to verify the bimodal structure of the Jacobian with exact singular values we plot the histogram of the top 1000 singular values of the Jacobian mapping at initalization and after training in Figure 4. This figure clearly demonstrates that the Jacobian has low-rank structure. both cases we observe that singular values are concentrated around zero with relatively small density distributed over higher singular values. This observation serves as a natural basis for decomposition of the label space into information I (large singular values, low-dimensional) and nuisance space A/ (small singular values, nigh-dimensional). We note that while calculating all the eigenvalues is not possible, we verify the bimodal structure of the entire Jacobian spectrum by approximating its spectral density in App. C.
Experiments without label corruption. First, we present experiments on the original training data described above with no label corruption. We train the network for 400 epochs to achieve a good fit to the training data. Our theory predicts that the sum of | and [Iv (1) determines the classification eтror (Theorems 2.2 and 6.24). Table I collects these values for the initial and final Jacobian. These values demonstrate that the label vector is indeed correlated with the top eigenvectors of both the initial and final Jacobians. An interesting aspect of these results is that this correlation increases from the initial to the final Jacobian so that more of the label energy lies on the information space of the final Jacobian in comparison with the initial Jacobian. Stated differently, we observe significant adaptation of the Jacobian to the labels after training compared to the initial Jacobian so that our predictions become more and more accurate as the iterates progress. In particular, the first column of Table shows that the fraction of label energy lying on the information subspace of the Jacobian drastically increases after training (from 0.38 to 0.99). Consequentially. less energy falls on the nuisance space (decreases from 0.92 to 0.16 after training), while J.yll,, remains relatively small resulting in better generalization. Towards explaining these, Section provides a preliminary analysis showing Jacobian spectrum indeed adapts to data.
We also track the projection of the residual r- on the information and nuisance subspaces throughout training on both training and test data and depict the results in Figures 5a and 5b. In agreement with our theory, these plots show that learning on I is fast and the residual energy decreases rapidly on this space. On the other hand, residual energy on N goes down rather slowly and the decrease in total residual energy is overwhelmingly governed by I. suggesting that most information relevant to learning lies in this space. We also plot the training and test error in Figure Sc. We observe that as learning progresses, the residual on both spaces decrease in tandem with training and test error.
9

---

Under review as a conference paper at ICLR 2020
10
10.8
Rositcal enarg?
Rosidtal corege
20"
11 111111011
0.4
10
Inall
0.2
10
In
10a1
Placiead
10
Frale
2/0
100
601
200
200
100
0000
80.0
0
2010
400
600
200
Epochs
Epochs
Epochs
(a) epochs train Jacobian.
(b) 50 epochs test Jacobian.
(c) Training and test error
Figure Evolution of the residual (r, f(W+) y) along the informatiin/nuiiaance spaces of the Jacobian at 50 epochs on (a) training data and (b) test data and (c) misclassification error on training and test data. 50% of the labels have been corrupted.
[z((r))
[
lole,
lole,
Trole,
Trale,
J Jerann
0.32762
0.94481
0.32152
0.9469
Enet
trasn
0.8956
0.44487
0.89597
0,44412
Final
Table 2: Depiction of the alignment of the initial residual with the informatioo/nnuisacee space using 50% label corrupted data and a Multi-class ResNet20 trained with SGD.
Experiments with label corruption. corruption. Specifically. label from a (strictly) different class. We train the network for 800 epochs and divide the learning rate by 10 epoch 760 fit to the training data. We again track the projection of the residual r, on the information/nuisance spaces throughout training on both training and test data and depict the results in Figs 6a and 6b. We also track the train and test errors in Figure 6c. From Figure 6c it is evident that while the training error steadily decreases, test error exhibits very different behavior compared to the uncorrupted experiment. the first phase, test error drops rapidly as the network learns from information contained in the uncorrupted data, accompanied by corresponding decrease in residual energy the information subspace on the training data (Figure 6a). The lowest test error is observed at epoch 50 after which steady increase follows. In the second phase, the network overfits to error the
Our next experiments study the effect of corrupt 50% of the labels by randomly picking
0.4
0
0.25
0.5
0.75
Label comruption
Figure 7: Fraction of the energy of the label vector that lies on the nuisance space of the initial Jacobian and final Jacobian well as the test error as a function of the amount of label corruption.
the corrupted data resulting in more uncorrupted test data (Figure 6b). More importantly, the increase of the test error is due to the nuisance space as the error over information space is stable while it increases over the nuisance. partieular the residual on W slowly increases while residual on drops sharply creating dip in both test error and total residual energy around epoch 50. This phenomenon further explained the appendix (see Sec. 5.1) via linear model.
In Table we again depict the fraction of the energy of the labels and the initial residual that lies on the information/nuisance spaces. The Jacobian continues to adapt to the labels/initial residual even in the presence of label corruption, albeit to smaller degree. We note that due to corruption, labels are less correlated with the information space of the Jacobian and the fraction of the energy on the generalization (as predicted by our theory).
nuisance space is higher which results in
To demonstrate the connection between generalization and information/nuisance spaces, we repeat the experiment with 25%, 75% and 100% label corruption and depict the results after 800 epochs in Fig. 7. As expected, the test error increases with the corruption. Furthermore, the corrupted labels become less correlated with the information space with more of the label energy falling onto the nuisance space. This is consistent with our theory which predicts worse generalization in this case.
10

---

Under review as a conference paper at ICLR 2020
REFERENCES
Zeyuan Allen-Zhu, Yuanzhi Li, and Yingyu Liang. Learning and generalization in overparameterized neural networks, going beyond two layers. arXiv preprint arXiv:1811.049/ 2018a.
Zeyuan Allen-Zhu, Yuanzhi Li, and Zhao Song. A convergence theory for deep learning via over- parameterization. arXiv preprint arXiv: 03962, 2018b.
Martin Anthony and Peter L Bartlett. Neural network learning: Theoretical foundationss cambridge university press, 2009.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. arXiv preprint arXiv:/802.05296. 2018.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. arXiv preprint arXiv:1901.08844 2019.
Peter Bartlett, Dylan J. Foster, and Matus Telgarsky. Spectrally-normmalizedd margin bounds for neural networks. 06 2017. URL https: http//awwwv...ooooaaaa// /1706. 08498.
Peter L Bartlett.
The sample complexity of pattern classification with neural networks: the size of the weights is more important than the size of the network. IEEE transactions on Information Theory, 44(2):525-536, 1998.
Peter L Bartlett and Shahar Mendelson. Rademacher and gaussian complexities Risk bounds and structural results. Journal of Machine Learning Research, 3(Nov):463 482, 2002.
Peter L Bartlett, Vitaly Maiorov, and Ron Meir. Almost linear ve dimension bounds for piecewise polynomial networks. In Advances in Neural Information Processing Systems, pp. 190-196, 1999.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine learning and the bias-variance trade-off. arXiv preprint arXiv:1812.111 2018a.
Mikhail Belkin, Daniel Hsu, and Partha Mitra. Overfitting or perfect fitting? risk bounds for classification and regression rules that interpolate. 06 2018b. pdff1806 05161.
Mikhail Belkin, Alexander Rakhlin, and Alexandre B. Tsybakov. Does data interpolation contradict statistical optimality? 06 2018c. URL https://s//aat //tp:///axivvii http:ppp:/aaatttooorg/////////// 1806. 71.
Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. arXiv preprint arXiv: 190300077. 2019.
Alon Brutzkus, Amir Globerson, Eran Malach, and Shai Shalev-Shwartz. Sgd learns over- parameterized networks that provably generalize on linearly separable data. arXiv preprint a7Xiv: /0/74, 2017.
Yuan Cao and Quanquan Gu. A generalization theory of gradient descent for learning over- parameterized deep relu networks. arXiv preprint arXiv:1902.01384. 2019.
Pratik Chaudhari, Anna Choromanska, Stefano Soatto, Yann LeCun, Carlo Baldassi, Christian Borgs, Jennifer Chayes, Levent Sagun, and Riccardo Zecchina. Entropy-sgd: Biasing gradient descent into wide valleys. arXiv preprint arXiv:1611.018.. 2016.
Lenaic Chizat and Francis Bach. On the global convergence of gradient descent for over-parameterized models using optimal transport. arXiv preprint arXiv:1805.09545. 2018a.
Lenaic Chizat and Francis Bach. A note on lazy training in supervised differentiable programming. arXiv preprint arXiv: 18/2.0795. 2018h.
Xialiang Dou and Tengyuan Liang. Training neural networks as learning data-ad kernels:
Provable representation and approximation benefits. arXiv preprint arXiv: /4,14,15 2019.
11

---

Under review as a conference paper at ICLR 2020
Simon S Du, Jason D Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global 038044, 2018a.
minima of deep neural networks. arXiv preprint
Simon S Du, Xiyu Zhai, Barnabas Poczos, and Aarti Singh. Gradient descent provably optimizes over-parameterized neural networks. arXiv preprint urXiv:1810.0205. 2018b.
Gintare Karolina Dziugaite and Daniel M Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. arXiv preprint arXiv:1703.11008 2017.
Behrooz Ghorbani, Shankar Krishnan, and Ying Xiao. An investigation into neural optimization via hessian eigenvalue density. Proceedings of the 36th International Conference on Machine Learning, 2019a.
Behrooz Ghorbani, Shankar Krishman, and Ying Xiao. An investigation into neural net optimization via hessian eigenvalue density, arXiv preprint urXiv:1901.10133 2019b.
Behrooz Ghorbani, Song Mei, Theodor Misiakiewicz, and Andrea Montanari. Linearized two-layers neural networks in high dimension. arXiv preprint arXiv: 12191, 2019c.
Surbhi Goel and Adam Klivans. Learning neural networks with two nonlinear layers in polynomial time. arXiv preprint 170.00000 2017.
Surbhi Goel, Adam Klivans, and Raghu Meka. Learning one convolutional layer with overlapping patches. arXiv preprint arXiv: 2018.
Noah Golowich, Alexander Rakhlin, and Ohad Shamir. Size-independent sample complexity of neural networks. arXiv preprint arXiv:1712.06654,, 2017.
Suriya Gunasckar, Jason D Lee, Daniel Soudry, and Nati Srebro. Implicit bias of gradient descent on linear convolutional networks. In Advances in Neural Information Processing Systems, pp. 9461-9471, 2018
Moritz Hardt, Benjamin Recht, and Yoram Singer. Train faster, generalize better: Stability of stochastic gradient descent. arXiv preprint 100.::1509001240, 2015.
Elad Hoffer, Itay Hubara, and Daniel Soudry. Train longer, generalize better: closing the generaliza- tion gap in large batch training of neural networks. In Advances in Neural Information Processing Systems, pp. 1731-1741 2017.
W. Ronny Huang, Zeyad Emam, Micah Goldblum, Liam Fowl, Justin K. Terry. Furong Huang, and Tom Goldstein. Understanding generalization through visualizations. 2019.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571-8580 2018
Hamid Javadi, Randall Balestriero, and Richard Baraniuk. A hessian based complexity measure for deep networks. arXiv preprint arXiv:1905.11639 2019.
Ziwei Ji and Matus Telgarsky. Gradient descent aligns the layers of deep linear networks. arXiv preprint arXiv: 1et000000..0000 2018a
Ziwei Ji and Matus Telgarsky. Risk and parameter convergence of logistic regression. arXiv preprint 10X3::1803007:00. 2018b.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Peter Tang. On latch-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv:1609.04833 2016.
Comelius Lanezos. An iteration method for the solution of the eigenvalue problem of linear differen- tial and integral operators. Journal of Research of the National Bureau of Standards 45: 255-282. 1950.
12

---

Under review as a conference paper at ICLR 2020
M. Ledoux. The concentration of measure phenomenon. volume 89 of Mathematical Surveys and Monographs. American Matheamtical Society, Providence, RI, 2001.
R. B. Lehoucq. D. C. Sorensen, and C. Yang. Arpack users guide: Solution of large scale eigenvalue problems by implicitly restarted arnoldi methods. SIAM, Philadelphia, PA, 1998, 1998.
Hao Li, Zheng Xu, Gavin Taylor, Christoph Studer, and Tom Goldstein. Visualizing the loss landscape of neural nets. In Advances in Neural Information Processing Systems, pp. 6389-6399, 2018.
Mingehen Li, Mahdi Soltanolkotabi, and Samet Oymak. Gradient descent with early stopping is prov- ably robust to label noise for overparameterized neural networks. arXiv preprint arXiv:1903.1168) 2019a.
Xinyan Li, Qilong Gu, Yingxue Zhou, Tiancong Chen, and Arindam Banerjee. Hessian based analysis of sgd for deep nets: Dynamics and generalization. arXiv preprint arXiv:1907.10732 2019b.
Yuanzhi Li and Yingyu Liang. Learning overparameterized neural networks via stochastic gradient descent on structured data. NeurlPS, 2018.
Tengyuan Liang and Alexander Rakhlin. Just interpolate: Kernel "ridgeless" regression can generalize. 08 2018. URL ptttt:ps///aaxi..ooo////p//
00387.
Philip M Long and Hanie Sedghi. Size-free generalization bounds for convolutional neural networks. arXiv preprini arXiv:
2019.
Chao Ma, Lei Wu, et al. comparative analysis of the optimization and generalization property of two-layer neural network and random feature models under gradient descent dynamics. arXiv preprint (iXxxvv944 04326, 2019.
Andreas Maurer. vector-contraction inequality for rademacher complexities. In International
Conference on Algorithmic Learning Theory, pp. 3-17. Springer, 2016.
Song Mei, Andrea Montanari, and Phan-Minh Nguyen. A mean field view of the landscape of two-layers neural networks. arXiv preprint arXiv:1804.0656/ 2018.
Vaishnavh Nagarajan and Zico Kolter. Deterministic pac-bayesian generalization bounds for deep networks via generalizing noise-resilience. arXiv preprint arXiv: 13344, 2019.
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nathan Srebro. A pac- bayesian approach to spectrally-normaaiieed margin bounds for neural networks. arXiv preprint arXiv: 1007.00977 2017a
Behnam Neyshabur, Srinadh Bhojanapalli, David McAllester, and Nati Srebro. Exploring general- ization in deep learning. In Advances in Neural Information Processing Systems, pp. 5947-5956, 2017b.
Atsushi Nitanda and Taiji Suzuki. Refined generalization analysis of gradient descent for over- parameterized two-layer neural networks with smooth activations on classification problems. arXiv preprint arXiv: 1975009770 2019.
Samet Oymak and Mahdi Soltanolkotabi. Overparameterized nonlinear learning: Gradient descent takes the shortest path? 12 2018. URL httpss://arxvv.orrgg. 1tt.//1...000.000
Samet Oymak and Mahdi Soltanolkotabi. Towards moderate overparameterization: global con- vergence guarantees for training shallow neural networks. arXiv preprint 1rXiv:1902.04677 2019.
Vardan Papyan. The full spectrum of deep net hessians at scale: Dynamics with sample size, arXiv preprint arXiv:I81I.00 1.00622 2018.
Vardan Papyan. The full spectrum of deepnet hessians at scale: Dynamics with sgd training and sample size. arXiv preprint arXiv:1811.07062v2 2019a.
Vardan Papyan. Measuring the spectrum of deepnet hessians. 2019b.
13

---

Under review as a conference paper at ICLR 2020
Grant M. Rotskoff and Eric Vanden-Eijnden Neural networks interacting particle systems: Asymptotic convexity of the loss landscape and universal scaling of the approximation error. 05 2018. URL https: : www.aaavvvv..........a...... wwtp://pgpppppaaaeeeeoeeeeeeettt wttppaaa////// 00915.
Levent Sagun, Utku Evci, V Ugur Guney, Yann Dauphin, and Leon Bottou. Empirical analysis of the
hessian of over-paramettrized neural networks. arXiv preprint arXiv: 04454, 2017.
Bernhard A Schmitt. Perturbation bounds for matrix square roots and pythagorean sums. Linear algebra and applications, 174:215-222 1992.
Schur. Bemerkungen zur theorie der beschränkten bilinearformen mit unendlich vielen verän- derlichen. Journal für die reine und angewandte Mathematik, 140:1-28, 1911. URL http:
//eudml.org/ /tc/
Justin Sirignano and Konstantinos Spiliopoulos. Mean field analysis of neural networks: A central limit theorem. 08 2018. URL https: //app:s://axxiv wrtgp/f/gaaaeeeeeoee www.//////..... 09372.
Mei Song, A Montanari, and Nguyen. mean field view of the landscape two-layers neural networks. In Proceedings of the National Academy of Sciences, volume 115, pp. E7665-E7671, 2018.
Daniel Soudry, Elad Hoffer, Mor Shpigel Nacson, Suriya Gunasekar, and Nathan Srebro. The implicit bias of gradient descent separable data. The Journal of Machine Learning Research, 19(1): 2822-2878, 2018.
Lili Su and Pengkun Yang. On learning over-parameterrzedd neural networks: A functional approxi- mation prospective. arXiv preprint arXiv:1905.10825 2019.
Gilad Yehudai and Ohad Shamir. On the power and limitations random features for understanding neural networks. arXiv preprint arXiv:1904.00687, 2019.
Dong Yin, Kannan Ramchandran, and Peter Bartlett. Rademacher complexity for adversarially robust generalization. arXiv preprint arXiv: /9/4, 2018.
Yi Yu, Tengyao Wang, and Richard Samworth. A useful variant of the davin theorem for statisticians. Biometrika, 102(2):315-333, 2014.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. arXiv preprint 16 2016.
Huishuai Zhang, Da Yu, Wei Chen, and Tie- Yan Liu. Training over-paramettrrized deep resnet is almost as easy as training a two-layer network. arXiv preprint 1rXiv: 2019.
Difan Zou, Yuan Cao, Dongruo Zhou, and Quanquan Gu. Stochastic gradient descent optimizes over-parameterized deep relu networks, arXiv preprint arXiv18811.08888 2018.
14

---

Under review as a conference paper at ICLR 2020
4.5
ELN(w++
Test error
Test enror
2
FLI(WiT)
3.5
2.5
0
50
100
150
200
50
100
150
200
Iterations (7)
Iterations (T)
(a) Total test eтror
(b) Test error along information and nuisance spaces
Figure 8: Plots of the (a) total test error and (b) the test error components for the model in Section 5.1. The test error decreases rapidly over the information subspace but slowly increases over the nuisance subspace.
TECHNICAL APPROACH AND GENERAL THEORY
5.1 PRELUDE: FITTING A LINEAR MODEL
To gain better insights into what governs the generalization capability of gradient based iterations let us consider the simple problem of fitting linear model via gradient descent. This model maps input/feature vector & E Rd into one-dimensional output/label via x + f(x, w) == w æ. We wish to fit a model of this form to n training data consisting of input/label pairs {(x,, y: k Rd R. Aggregating this training data as rows of a feature matrix X e Rpaxd and label vector e R", the training problem takes the form
X [(w) = 2
1 yli..
(5.1)
We focus on an overparameterized model where there are fewer training data than the number of parameters ie. n S d. We assume the feature matrix can be decomposed into the form X X + Z where is low-rank (i.c. rank(X) = r << n) with singular value decomposition X UEVT with [Raxd a matrix with i.i.d. (O /2/n) entries. We shall
U E [R Σ E (RT*", V e [Raxr, and also assume the labels are equal to y y z with y = Xw" for some w" e Range(V) and e IR" linear regression
Gaussian random vector with i.i.d. i. (O /g/n) entries. One think of this model where the features and labels are corrupted with Gaussian noise. The goal of course is to learn model which fits the clean uncorrupted data and not the corruption. In this case the population loss (i.e. test error) takes the form
E [[[(w)]= 1 X yy 200²
1
1 5
w
Now let us consider gradient descent iterations with step size 17 which take the form
-++1 w, ((w,) = (I (I-n xx w, +
(5.2)
To gain further insight into the generalization capabilities of the gradient descent iterations shall consider an instance this problem where the subspaces and V are chosen uniformly at random, Σ I, with 200, 500, 5, and ar 0.2, og In Figure 8a plot the population loss evaluated at different iterations. We observe an interesting phenomenon, in the first few iterations the test error goes down quickly but then slowly increases. To better understand this behavior we decompose the population loss into two parts by tracking the projection of the misfit Xw on the column space of the uncorrupted portion of the input data (U) and its complement. That is,
E [(w) EZ E (w))
15

---

Under review as a conference paper at ICLR 2020
where
ELz(w) := E [ (X w
y)(2. -x--y)1,,
Xw Tlie Xw-Vll
0² |
|
2n o y
2n
E (L)((w) := F \T (Xw y) 1e,
- 1 Ti :
Iw|l le,
o
with =1 U and =I==I- - -U- In Figure 8b plot these two components. This plot clearly shows that E Cz( () goes down quickly while E Cv ( (w) slowly increases with their sum creating the dip in the test error. Since U is basis for the range of the uncorrupted portion of the features (X) one can think of span(U) as the "information" subspace and IE Cz (w) as the test error on this information subspace. Similarly, one can think of the complement of this subspace as the "nuisance" subspace and E (w) Figure 8a as the test error decreasing rapidly in the first few iterations over the information subspace but slowly increasing due the contributions of the nuisance subspace.
the test error on this nuisance subspace. Therefore,
can interpret
To help demystify this behavior note that using the gradient descent updates from (5.2) the update in terms of the misfit/residual r, X w. y takes the form
(I- (xw- noise
Tr+1
Based on the form of this update when the information subspace is closely aligned with the prominent singular vectors of X the test eπrоr on the information subspace (ECr(w) |Xw, w T quickly decreases in the first few iterations. However, the further we iterate the parts of the residual aligned with the less prominent eigen dirrectons of X (which correspond to the nuisance subspace) slowly pick up more energy contributing to a larger total test error. In this section, we outline our approach to proving robustness of wver-parameterized neural networks. Towards this goal, formulation where we aim to fit a general nonlinear model of the form æ + f(x; 0) with æ e IRd denoting the input features, A E IP denoting the parameters, and f(:; 0) E R the outputs of the model denoted by fi(x:; (x; 0), fa( (x; 0). ..... fx fx(=; 0). For instance in the case of neural networks O represents its weights. Given a data set of input/label pairs {(V,, y:) Rd RK we fit to this data by minimizing a nonlinear lqaat-squares loss of the form
consider general
(())=
Σ | (x;; 0) y:
(5.3)
2
To continue let us first aggregate the predictions and labels into larger vectors based on class. In particular define
fe( E RR and
(1)));
f(( = fe(xni 0)
(0) =
6 RR for f 1,1,2.... ..,K.
(3)),
Concatenating these vectors we arrive at
f1 (0)
(1))
((0) =
E RRn
and
y
e RRnn
(5.4)
(0)
(K)
Using the latter we can rewrite the optimization problem (5.3) into the more compact form
1 [l) y12.-
L(
(5.5)
To solve this problem run gradient descent iterations with learning rate 7 starting from initial point 0g. These iterations take the form
0,+1=00 = -V)(0)) with =0))
(5.6)
As mentioned earlier due to the form of the gradient the convergeneeegenerriiiattoon of gradient descent naturally depends the spectral properties of the Jacobian. To capture these spectral properties we will use a reference Jacobian (formally defined below) that is close to the Jacobian at initialization J(O,).
16

---

Under review as a conference paper at ICLR 2020
Definition 5.1 (Reference Jacobian and its SVD) Consider an initial point 0g RP and the Jaco- bian mapping I (0o) RKaxp, For Eo, 3 O, we call J IR K Kn.p)) an (co. 33 reference Jacobian matrix if obeys the following conditions,
| 3 3, (I(0)) JJJ s cg. and [J(00) - [J]] seo
where [(o) (KKxmax(Kn.)) is matrix obtained by augmenting J I(0s) with max(0, Kn -p) zero columns. Furthermore, consider the singular value decomposition of J given by
Kn
J U A)V*
Σ Xxu.o
(5.7)
where X RR are the vector of singular values and u, RRn and Uy RP the left/rihtt singular vectors.
One natural choice for this reference Jacobian is ((p). However, we shall also use other reference Jacobians in our results. We will compare the gradient iterations (5.6) to the iterations associated with fitting linearized model around O defined fin (0) f(0n) ( 0o), where 0, (n.p)(Kn.p) is obtained from 0, by adding max p. 0) zero entries the end of 0g. The optimization problem for fitting the linearized problem has the form
Lun (0) 2
f -
(5.8)
Thus starting from 0, = On the iterates 0, on the linearized problem take the form
ū,.1 0. V/V (0+),
(5.9)
= θ. nJ" (f(Op) J(Ø, ((0--60) (0) y)).
0, - JJt J(O, 0u) - (f(O)) yy)
The iterates based on the linearized problem will provide useful reference to keep track of the evo- lution of the original iterates (5.6). Specifically we study the evolution of misfit/residuals associated with the two problems
Original residual: r- f(0,) y.
(5.10)
Linearized residual: F, = fim( y (I-nJJ") To.
(5.11)
To better understand the dynamics of convergence the linearized iterates next we define two subspaces associated with the reference Jacobian and its spectrum.
Definition 5.2 (Iformattoon/Nussnnc Subspaces) Let J denote the reference Jacobian per Defini- tion 5.1 with eigenvalue decomposition Udiagg (R) per (5.7). For a spectrum cutoff a obeying 0 d let ra)) denote the index of the smallest singular value above the threshold a, that is.
r(a) min (fs nK) such that X 2,2
We define the information and nuisance subspaces associated with as I (aul and N span( (u,) grr.). We also define the truncated reference Jacobian
Kn
U2 ... Mr]ddag (A1, )2)...,;x)((s))
U2
v,
which is the part of the reference Jacobian that acts on the information subspace I.
We will show rigorously that the information and nuisance subspaces associated with the reference Jacobian dictate the directions where learning is fast and generalizable versus the directions where learning slow and overfitting occurs. Before make this precise we list assumptions that will be utilized in our result.
Assumption (Bounded spectrum) For any RP the Jacobian mapping associated with the nonlinearity f: Rº - Rn has bounded spectrum, i.e. [T((O) < B.
17

---

Under review as a conference paper at ICLR 2020
Assumption 2 (Bounded perturbation) Consider point 0, RP and positive scalars E, R O. Assume that any obeying |0 Bolle, s R, we have
IT(0) [(o)) 2
With these assumptions in place we are now ready to discuss our meta theorem that demonstrates that the misfit/residuals associated the original and linearized iterates do in fact track each other rather closely.
Theorem 5.3 (Meta Theorem) Consider nonlinear least squares problem of the form ((0) (l)( -yl?, with f RP RRnK the multi-class nonlinear mapping, O IP the parameters of the model, and & Rak the concatenated labels as in (5.4). Let 0 be zero sero-padding of 0 rill size max (n,P) p). Also, consider a point 0g e RP with J an (4o: (3) reference Jacobian associated with I(0)) per Definition 5.1 and fitting the linearized problem fün (0) - f(0n) + J@ - 0o) via the loss Cun () = ff ()) yulez Furthermore, define the information I and nuisance N subspaces and the truncated Jacobian JI associated with the reference Jacobian based on a cut-off spectrum value of a per Definition 5.2. Furthermore, assume the Jacobian mapping J [(0)= E RRnK*p xp associated
with f obeys Assumptions and 2 for all O RP obeying
00- - Oole, S RR 2 +
|TT (ro) + 8- |roles))
(5.12)
around a point 0u e RPP for a tolerance level obeying 0 < 5 s and stopping time I obeying I 2 1. Finally, assume the following inequalities hold
min(ōa, //ba//T3 and E ES
Eo S
(5.13)
5
5T
We run gradient descent iterations of the form ,,.1 0, V LV and θ 1 - - I (Ø,) on the original and linearized problems starting from Oo with step size n obeying 1) 1/3². Then for all iterates T obeying 0 T qa and the corresponding residuals T. f(0,) y and F, := fun (0,) y closely track each other. That is,
F the iterates of the original (0,) and linearized (0,) problems
3 8a
|r, F Ile
s
rroles
and 10, 0. le, s
rrolle
(5.14)
5
B
Furthermore, for all iterates obeying 0 S S
r S
naz
R 2
r |l (ro)
r + + rroles
100 Sole,
|
+-
(5.15)
82
a
and after T iteration we have
|rTlle, se (17(()))))) +1Ux(ro)) + da
||ollle.
(5.16)
6 PROOFS
Before we proceed with the proof let us briefly discuss some notation used throughout. For matrix W kexd we use veet(W) e R&d to denote vector obtained by concatenating the rows
W1, W2...., Wi Rd of W. That is, vect(W) [wo] why mat(w) w) Rlxd to denote a x matrix obtained by reshaping the vector w Rkd across its rows. Throughout, for differentiable function Φ: IR + R we use d and ø" to denote the first and second derivative.
"[ Similarly, we
6.1 PROOFS FOR GENERAL THEORY (PROOF OF THEOREM 5.3)
In this section we prove our result for general nonlinearities. We begin with few notations and definitions and preliminary lemmas in Section 6.1.1. Next in Section 6.1.2 we prove some key lemmas regarding the evolution of the linearized residuals F, In Section 6.3 establish some key Rademacher complexity results used in our generalization bounds. Finally, Section 6.3.3 we use these results complete the proof of Theorem 5.3.
18

---

Under review as a conference paper at ICLR 2020
6.1.1 PRELIMINARY DEFINITIONS AND LEMMAS
Throughout we use
Ur -r=(u U2 u,]e R=Axr and = Ux+2 Unk R=nKx(nKr))
to denote the basis matrices for the information and nuisance subspaces from Definition 5.2. Similarly, we define the information and nuisance spectrum as
Az = [ A Ar1" and Av = [dre1 Ana2
Xnn]]
We also define the diagonal matrices
= (A), A diag(())), and AN
Definition 6.1 (early stopping value and distance) Consider Definition 5.2 and let T > be a y and the information/nuisaacee
positive scalar. Associated with subspaces of the reference Jacobian J (with a cut-off level o:) we define the (ax, I') early stopping value
the initial residual ro f(00) yy
((u,, ro))) 1/2
a² ((u,, rol) + +2
ak X Σ
Ba
Σ
(6.1)
5-1 X
sur+1 a
We also define the early stopping distance as
Bar
Da.r
The goal of early stopping value/distance is understanding the behavior of the algorithm at particular stopping time that depends on I and the spectrum cutoff a. In particular, as we will see later on the early stopping distance characterizes the distance from initialization at an appropriate early stopping time. We continue by stating and proving a few simple lemmas. The first Lemma provides upper/lower bounds the early stopping value.
Lemma 6.2 (Bounds on Early-Stopping Value) The early stopping value Ba,r from Definition 6. obeys
Barr S (1112 + (ro)) 12 s |rolle,
(6.2)
Ba.r 2 a X [z(rr))
(6.3)
Proof To prove the upper bound we use the fact that a s X₂ for 8 S and 2 A for 2 r to conclude that
1/2
nk
B Bar
Σ (us,
ro))² (()))
D Σ ((u))))))²)
s=rt1
=(1TZ((0)) +2 [To 1/2
$ &T||rolles
To prove the lower bound, we use the facts that a²/2² a²/xī to conclude that
1/2
Barr
Σ a²
((),,
ro)) +
nk X² Σ
a² (o))))
X2
1/2 (Luz, rol))
2
Σ
X
M1 (ro)lles
A1
is of course well known that the mapping (I AAAA) is contraction for sufficiently small values of 1). The next lemma shows that if we replace one of the A matrices with a matrix B which is close A the resulting matrix (I-m (."..".). while may not be contractive, too expansive.
19

---

Under review as a conference paper at ICLR 2020
Lemma 6.3 (Asymmetrie PSD increase) Let A, Rexp be matrices obeying
|||| s B, |B] s,, and |B-A] A-A SE.
Then, for all r e RR and 1) 1/3² we have
I(r 7)AB") r/1e, $ (1+ nE²) 1
Proof Note that using 1) 1/32 and |B All & & we conclude that
[ - (l-AABrrrll
[| "BB (1(A ( B3BB)BBBB rlle
Fr- B B)B -
|m|es -21p"" (A- B B) B)B" B" r
+" rn
AB r
1r 2n
[1r r12, + 2n/ (A- (A-B)" rll1,
|B" rle, + 1 B rlle.
|mle, 7/ B²" rle, 2n (A] B)" rlle,
1 + (1/14 A Bd r 7) 1
7S1/82 $
|m| 1) BB r r12,, 2n (A B)"
B"rrlle
s| S
|m| 7) B rl? 2mp BT r'rllea 1rles
=(1+ |r| (5 - -IB ll.))
Irlle
s(1 nE |rles
completing the proof.
The next lemma shows that if two PSD matrices are close to each other then an appropriate square root of these matrices will also be close.
Lemma 6.4 Let A and B be n x n positive semi-definite matrices satisfying || | - B S a² for scalar a 2 0. Then for any X e (Ruxp with 2 n obeying A = XXT there exists a matrix Y Rexp
obeying B YYT such that
Y
X s 2xx
a² Proof First we note that for any two PSD matrices A,, B. RRxx obeying A., B, 4 "n, Lemma 2.2 of Schmitt (1992) guarantees that
A B 14-BB.1
In the above for PSD matrix A Rax* with eigenvalue decomposition A UAUT we use 1/2 to denote the square root of the matrix given by A = UA! 1/? We shall use this result with
A. A+ a² In and B, + + a² In to conclude that
4
A!!² B
A. B,
A
B
a
a
Furthermore, using the fact that the eigenvalues of A, and B, are just shifted versions of the cigenvalues of A and B by a//4 we can conclude that
A
a 1/2 and |B B 5 an
2
Combining the latter two inequalities with the assumption that ||A - B|| s a² we conclude that
1/2 B
!
B 1/2
A A 1/2
|B!²2 B
A
0 a
2
2
<20=
(6.4)
20

---

Under review as a conference paper at ICLR 2020
Suppose p and assume the matrices A and B have eigenvalue decompositions given by A UAAAUT U and B UBABUZ Then, any X Rexp with p 2 n has the form X UAA 1/2 V with VA e Rpx orthonormal matrix. Now pick
Y= UBBB BUAVA
Then clearly YYT = B. Furthermore, we have
X Y
U UBA B
U U
-IUAAA - UBAB B
U
1 BB (
A -B
Combining the latter with (6.4) completes the proof.
6.1.2 KEY LEMMAS FOR GENERAL NONLINEARITIES
Throughout this section assume J is the reference Jacobian per Definition 5.1 with eigenvalue decomposition J UAV" ΣKΙ Xyu, va with A diag( A). We also define U ro UTT Rak be the coefficients of the initial residual in the span of the column space of this reference Jacobian.
We shall first characterize the evolution of the linearized parameter 0, and residual P, vectors from (5.11) in the following lemma.
Lemma 6.5 The linearized residual vector Fr can be written in the form
7, U.= a= nk (1- - a Ug.
(6.5)
Furthermore, assuming 1 1/2; the linear updates O, obey
nk
10, 0o113
Lg
(6.6)
Proof Using the fact that JJJJ = -UA? we have
(I-nJJ')) U(I- UT
Using the latter combined with (5.1 we thus have
F- -I - n.J o ro:
-U [ nA?) UT ru:
=U(1 - ')/a2²² a.
nk
Σ (1 - () a. u
completing the proof of (6.5).
We now turn our attention to proving (6.6) by tracking the representation of 0, in terms of the right singular vectors of J. To do this note that using (6.5) we have
JT VA VA (I --)))' a.
Using the latter together with the gradient update on the linearized problem have
0, 0 --n
Σ v Lin (0.)
=
JT = =
r-1
Σ A (I 7
a
1=0
1=
21

---

Under review as a conference paper at ICLR 2020
Thus for any E (1.2...... nk}
- 100--6--110 = = of -0,- Noting that i/ 1/1| s 1/13 we have
T-1
Σ t=0
(1 (1- an =
1- (- ))
1- (1 n)
= =- As
77
- -1112 2 0, the latter identity implies that
a.
[1 (0, -bo]l s
(6.7)
A
Furthermore, using the fact that 1 1-1 s 1 we have
T (Ø, 0 n1>o lag1
Σ
(1 - (1-)) s smdalast
(6.8)
1=0
Combining (6.7) for 1 s r and (6.8) for r we have
nk
nk
0, -oll,
Σ
o (0,
T.) Σ
2 17
Σ X30
s-1+1
completing the proof of (6.6).
For future also state simple corollary of the above Lemma below.
Corollary 6.6 Consider the setting and assumptions of Lemma 6.5. Then, after iterations we have |rrlez s (1 (1- na²)" [[Llz(r))ee, + [[oy())))e=
(6.9)
Furthermore, after T= = na iterations we have
Frille se S- [T] + [Iv(r))]le.
(6.10)
and
nk
Xa
B
Ør -
a
a²
with B..r given by (6.1) per Definition 6.2.
Proof To prove the first bound on the residual (n.e that using (6.5) we have
UÍr (I- nA Ufr and UKF =(I - (I-nAR) U
Thus, using the fact that for we have A 2 have (1 n s (1 n of and for r have (1 - ?7 S 1, we can conclude that
|ufFrll, s (1 na? |lFfrole and 1UXTrl1, s >|URrolles.
Combining these with the triangular inequality we have
|Frle
|Uffrlle, +IU s(1 (1= roll,, -Ubrrolee
concluding the proof of (6.9). The second bound on the residual simply follows from the fact that (1 (1-na?)T =T" The bound on Ø 0bll² is trivially obtained by using T
r² न.ा in (6.6).
The lemma above shows that with enough iterations, gradient descent on the linearized problem fits the residual over the information space and the residual (in the worst case) unchanged over the nuisance subspace N. Our hypothesis is that, when the model is generalizable the residual mostly lies on the information space Z which contains the directions aligned with the top singular vectors. Hence, the smaller term IIIv (ro) [|z over the nuisance space will not affect generalization significantly. To make this intuition precise however we need to connect the residual of the original problem to that of the linearized problem. The following lemma sheds light the evolution of the original problem (5.6) by characterizing the evolution of the difference between the residuals the original and linearized problems from iteration the next.
22

---

Under review as a conference paper at ICLR 2020
Lemma 6.7 (Keeping track of perturbation step) Assume Assumptions I and hold and 0, and 7,+1 are within an R neighborhood of 8., that is,
10, 0 8ole, S R and |10+11 -ulle, S
Then with learning rate obeying 1 1/3², the deviation in the residuals of the original and linearized problems e--1 T F++1 obey
|| le. S T ( 1e, + (1+ ([+n="))le )|e,
(6.11)
Proof For simplicity, denote B = J 0,), B2 = J(,), A = J(0)) where
J(b.a)= L J(lb+ (1-1)a)dl.
We write the predictions due 0,+1 as
f(0.+1) f(e, 1/ (V)))-)) f(0.) (000))+n01 (.)
f(0)) n (0++1, (1) (f:)(()))))
This implies that
Pr-1 f((++1))++). y (1- )r,
Similarly, for linearized problem we have T++ (I-1JJ² yr.. Thus,
1 = [I - iy B )r (I-nJJ )
|I n B ( JJJJ )F
< BB BB) e 7/ (B, JJ T
$ I - [I- e,l(, + ( - JJJ' F llez
(6.12)
We proceed by bounding each of these two terms. For the first term, we apply Lemma 6.3 with B B₂ s conclude that
A B₁ and B B2 and use
-I- n le, S (1 + nn"))ler
(6.13)
Next we turn our attention to bounding the second term. To this aim note that
| BT - JJJ
[ AAT + AAT JJ"
< |B,B AA
|AA" JJ
$ ((BI-A)B]
|A(B; - AA) -
- -JJTI
$ | A
[B, AI|A| -
- JJ
$ $ E + 3f+ 2
2
83.
(6.14)
In the last inequality we the fact that per Assumption we have BB - Al 8/2 and BB- B2-A| e/2 as well the fact that per Definition 5.1 |AA" - JJ s e Plugging (6.13) and (6.14) in 12) completes the proof.
Next we prove a result about the growth of sequences obeying certain assumptions. As we will see later on in the proofs this lemma allows control the growth of the perturbation between the original and linearized residuals (e, = ||e le,)-
Lemma 6.8 (Bounding residual perturbation growth for general nonlinearities) Consider posi- live scalary D, E, > O. Also assume S 1/a² and e and set T T_z Assume the scalar sequences e, (with en 0) and F, obey the following identities
7, 501-1aaa) na²)" p. P-:
e, s(1 + M7E ) 1
(6.15)
for all 0 S S T and non-negative values p., p+ 2 O. Then, for all 0 ST ST.
e, 5 SA holds with A= 2(T'p + p.)
(6.16)
a2
23

---

Under review as a conference paper at ICLR 2020
Proof We shall prove the result inductively. Suppose (6.16) holds for all t 7- 1. Consequently, have
G++1 s(1 + n)=)) )e + + r/0F:
set 178 et 1/00 ((1 )/a2)"/pp p+ p-)
set (e A (1 (1 )022)10000 p+ + p-).
Thus
c+ - sn (: (1 (1-na²) p+ p-).
(6.17)
Summing up both sides of (6.17) for 0 st we conclude that
e
C++1 Ct
θ
+
E0
$ Mt (eAA+ + 17p+
Σ (1 na n)
1 (1 na
= (6"A + p-) +1p++
na2
Sn TE A+ P= TTp_)
na2
= p-)
a²
STT(EEA++ p-)
Pt
Te +p+
a²
A
A
a 2
SA
where in the last inequality we used the fact that a² 21'.. This completes the proof of the induction step and the proof of the lemma.
6.1.3 COMPLETING THE PROOF OF THEOREM 5.3
With the key lemmas in place in this section we wish to complete the proof of Theorem 5.3. We will use induction to prove the result. Suppose the statement true for some -- < T 1. particular, assume the identities (5.14) and (5.15) hold for all 0 s 5 7 1. We aim to prove these identities continue to hold for iteration т. We will prove this result in multiple steps.
Step I: Next iterate obeys 0,-00lle s R. We first argue that 0, lies in the domain of interest dictated by (5.12). i.e. 00 -0ule R. To do this note that per the induction assumption (5.15) holds for iteration 7 and thus |0,-1 - -ollez S 2,. As result using the triangular inequality show |0, Oole, / holds it suffices show
24

---

Under review as a conference paper at ICLR 2020
that 10, -0 S R/2 holds. To do this note that
- 00--0-11 le2 =ni v ((
(0,00-111) 1)--))r-11 6g
1 | (0--1) (r--))r-11
(0) "nll"" (0 l2 + nnlJ" (1rii)
(6)
3 3/||5" "n||J"Fr111 -rllle, + +1 (0.--))) -J F +1| (( |r - -Fr-1
( |n||5'r F/ -lle= + ED +
11F7-111s + 3 || - Fre
||
B2
( 5n 1r + 25a
1
I
+
||r-11 - -Fr-llez
5,92
B
(2) (
28a
35a
|rolle
+
5 role
5,3
da
"n||J"F
rrolles
32
(n)
Barr
da
$113
|rol
32
a
(0)
Ba.r
8a
Tolle
32
(h)
B.,r
8T
|rlle
R
2
Here, (a) and (b) follow from a simple application of the triangular inequality, (c) from the fact that
[J()))- JIl s co. (d) from combining the bounds in (5.13). (e) from the induction hypothesis that postulates (5.14) holds for iteration T 1, (f) from
[T(0,-)-- Jil [[( - J(O))
considering the SVD J UAV UAV" which implies that
F l2 = Jd (I - --=) ro
= VA - U ro
A|A (I- - 11-)))=111 U ro
=
23(1 - 11l-nn222(1111 ((us,
23 (lu,, ro))²
$
nk
Xa (o))+
Σ
X2 (uu, ro))²
s-4+1
nk
(uu (o)s)
Σ
X3 ru))
X
sur+1
nk
X²
5.84
Σ
2
Σ a (oo)))
X
s=r+1
=34 Ba.
(g) from the fact that 7) S 32, and (h) from the fact that a S 3 and I' 1.
1.
Step I: Original and linearized residuals are close (first part of (5.14))
In this step we wish to show that the first part of (5.14) holds for iteration T. Since we established in
25

---

Under review as a conference paper at ICLR 2020
the previous step that 10, - Bulu, R. the assumption of Lemma 6.7 holds for iterations and Hence, using Lemma 6.7 equation (6.11) we conclude that
lerlle, s n =B) + (1 + nE² ) ler-1lee.
This combined with the induction assumption implies that
|eelle, $ ( [t-lle (1 + nE² |
(6.18)
holds for all T Furthermore, using Lemma 6.5 equation (6.9) for all s 7 S 7 we have
File, $ (1 - na²) [TZz (ro)
(6.19)
To proceed, we shall apply Lemma 6.8 with the following variable substitutions
θ E + =B, P- [roz(r)))le, p
E, ||erlle. T, := ||Fr llez- (6.20)
We note that Lemma 6.8 is applicable since (i) z 1/32 z 1/a", (ii) based on (5.13) we have 6r 3d 8 .7 2 21, (iii) 7 obeys T T _ and (iv) (6.15) holds based on (6.18) and (6. 19). Thus using Lemma 6.8 we can conclude that
(rorll + (F(lv(r))lee)
lerle S2(E) + +B)
a²
(E) + +Tollo
(6.21)
a²
2 da s(
3 6a
rolle
$5 3 |rol
(6.22)
25
B
where in the last inequality we used (5.13). This completes the first part of (5.14) via induction.
Step III: Original and linearized parameters are close (second part of (5.14)).
In this step wish to show that the second part of (5.14) holds for iteration To do this begin by noting that by the fact that J is reference Jacobian J augments J(o)) by padding (T(()) - J(0n) 2- Combining the latter two via the triangular inequality we conclude that
have [[T(0u) JJ J|l Eo where columns match size of J. Also by Assumption 2 we have
[T,)) - J]| S 6o + e.
(6.23)
Let 0 and V VZ( vectors augmented by zero padding 0, VC(0) so that they have dimension max Kn,p) p). Now, we track the difference between and linearized f as follows
0, Tlllez
vλ(0.) VLin
J(0)) -J
[J((,) JTFiler
((T(0)) -J) Fille (rr
(TT(0.) - JJ) + 1J())) eel
(8 6o) e0) | + + 1
(6.24)
In the last inequality we used the fact that IT(0,) - J $ E Eo and || s 3. We proceed by bounding each of the two terms in (6.24) above. For the first term we use the fact that 1F | to conclude
Tl|rolee na²
5 sTrolle, STirrlle
(6.25)
26

---

Under review as a conference paper at ICLR 2020
To bound the second term in (6.24) use (6.21) together with S S 2 + + Σ eelle 1
r
conclude that
2r
Eg)
|rollez-
(6.26)
a²
naa
Combining (6.25) and (6.26) (6.24), we conclude that
0 0e 5
(E + +)3)
E ED
rol &
a
a
3r
3
8 &0
22
(0)
2
8
3
E
|rolez
5
a
(
2
2
8
E0
0
+
rrlles
5
25 2
2
2
8
-
1
50
r
roll
25
5
a 0
a
(4)
2
2
0
0
5
roll
5
25
5
5
22 8
r rrllee
25 a
Here, (a) follows from
óa
per Assumption (5.13), (b) from co S V ra per Assumption
6a
5
(5.13), (c) from E
3 br
s da
< bα
per Assumption (5.13), and (d) from ED s 5 per Assumption
5r
5
(5.13). Thus,
10--011le, rroole.
Combining the latter with the fact that 110, 10,-0 S Barr (which follows from Lemma 6.5 equation (6.6)) we conclude that
Bar
+ 8 rrrolls |Jgrolle, I =I (ro) - Irolle
0, Ool 0 Roll,, s 0 00l1, 0 0- 0.1,,
a a
The completes the proof of the bound (5.15).
Step V: Bound on residual with early stopping.
In this step we wish to prove (5.16). To this aim note that
(a)
|rT l.
|rrles
1 rr les
+ da
|r
le.
|rollez
3
-e (elolll + [[Lw())))c,+++++ 8a
rrllle
where (a) follows from the triangular inequality, (b) from the conclusion of Step II (first part of (5.14)), and (c) from Corollary 6.6 equation (6. 10). This completes the proof of (5.16).
6.2 KEY LEMMAS AND IDENTITIES FOR NEURAL NETWORKS
In this section we prove some key lemmas and identities regarding the Jacobian of one-hidden layer networks as well as the size of the initial residual that when combined with Theorem 5.3 allows us to prove theorems involving neural networks. We begin with some preliminary identities and calculations in Section 6.2.1. Next, in Section 6.2.2 we prove a few key properties of the Jacobian mapping of one-hidden layer neural network. Section 6.2.3 focuses few further properties of the Jacobian at a random initialization. Finally, in Section 6.2.4 we provide bounds on the initial misfit.
27

---

Under review as a conference paper at ICLR 2020
For two matrices
A1
B1
A2
B₂
A
R
and
B
[
:
Ap
Bp
define their Khatri-Rao product A B [A1 the Kronecker product.
Bi..... A, Bp] Roxma, where @ denotes
6.2.1 PRELIMINARY IDENTITIES AND CALCULATIONS
We begin by discussing few notations. Throughout we use wo and de denote the éth row of input and output weight matrices W and V. Given a matrix M we use |M 2, to denote the largest Euclidean norm of the rows of M. We begin by noting that for a one-hidden layer neural network of the form æ + V ( (Wæ), the Jacobian matrix with respect to vect (ect(W) e IR takes the form
(WW
J(W)
e IR RRakdd
(6.27)
(W)
where J(W is the Jacobian matrix associated with the éth class. In particular, J+(W) given by (((W) [Te(w1) Je(w:))] Ruokdd with Je(ws) Vi, (X w.)) X.
Alternatvelyy using Khatri-Rao products this can be rewritten in the more compact form Je(W)- (o' (XW*) diag(v:)) X.
(6.28)
An alternative characterization of the Jacobian is via its matrix representation. Given vector u e RRnn let us partition it into K size n subvectors so that u = [u] "k We have
mat (W)))=
vz) (wx') diag( u.)
(6.29)
6.2.2 FUNDAMENTAL PROPERTIES OF THE JACOBIAN OF THE NEURAL NETWORK
In this section we prove few key properties of the Jacobian mapping of a one-hidden layer neural network.
Lemma 6.9 (Properties of Single Output Neural Net Jacobian) Let K = that VT R".. Suppose & is an activation obeying (0(z) for all z. Then, for any W |Rexd and any unit length vector we have
SB
XI
and
|mma (J ((T(W))) 12,00 SBllule-1
(6.30)
Furthermore, suppose & is twice differentiable and (Ø"(() ) B for all z. Also assume all data points have unit Euclidean norm (|æxile, 1). Then the Jacobian mapping is Lipschitz with respect to spectral norm i.e. for all W. W Rlx we have
J ((W) - [W)]] s B Blule |X| W
W
F
Proof The result on spectral norm and Lipschitzness of J(W) have been proven in Oymak & Soltanolkotabi (2019). To show the row-wise bound (6.30), we use (6.29) to conclude that
|mt (W) = |diag(v) (W x diag( u) X 2|,,00
< |10| max Iseck
O (w)) X²) diag (u) X 1z
< |0||__. X
max Leeck
1 (w) x² diag(u)lle,
< Bl( [e,
X
= Bl l. X
Next extend the lemma above the multi-class setting.
28

---

Under review as a conference paper at ICLR 2020
Lemma 6.10 (Properties of Multiclass Neural Net Jacobian) Suppose & is activation obeying (x)) B for all z. Then, for any W e R and any unit length vector u. we have
BVW))
(6.31)
and
|mat (J² 00 S BBKKI IX|.
(6.32)
Furthermore, suppose o is twice differentiable and (=)) for all Also assume all data points have unit Euclidean norm (|æille, 1). Then the Jacobian mapping is Lipschitz with respect to spectral norm ie. for all W W IRood we have
J J(W) BBK |X| W W
Proof The proof will follow from Lemma 6.9. First, given A [A] [B]
A and B
B" observe that
| S K sup A and |A - B S K sup Istsk
A BB
Isesk
These identities applied the components ( and (+(W) (WW completes the proof of the bound on the spectral norm and the perturbation. To prove the bound in (6.32) we use the identity (6.29) to conclude that
K 1 E=1
|mat (JT (W)u)l220 1200
diag( (WXx) diag us) ) X 2,,00
(diag())) (WX*) diag us) X 2,00
$
B Fl
X
uelles
E=1
= B V
|/ X
Σ 1=1
rellees
1/2
$ B V
X
K
uuel
= B |X||
where the penultimate inequality follows from Cauchy Schwarz, completing the proof.
6.2.3 PROPERTIES OF THE JACOBIAN AT RANDOM INITIALIZATION
In this section we prove few lemmas characterizing the properties of the Jacobian at the random initialization.
Lemma 6.11 (Multiclass covariance) Given input and output layer weights V and W, consider the Jacobian described in (6.27). Given an Kn Kn matrix M, for 1 e, K, let M denote the (e, E)th submatrix. For C(W)= J(W)J
have
E(xx) o (Ve, Vr, (Xw,) (Xx.)) C(W)(E,
3-1
Suppose W Lid. (O, 1) and V has i.i.d. zero-mean entries with v² variance. Then E[C(W)) is block diagonal matrix given by the Kronecker product
E[C(W)) kv
where E(X) is equal to Ix ((XX) o E[Øl (Xw.)d (X (x.))
29

---

Under review as a conference paper at ICLR 2020
Proof The (t, submatrix of C(W) is given by
[(w) - ((diag ( (WW))) x (ddag())) x2)=
Σ [{(
Ve, (f
Vi, V 1.
(X
[xx*) VL. Vy, 6 (Xw, (X
(6.33)
Setting W Lid N(0, 1) and with i.i.d. zero-mean and 2² -variance entries, we conclude that
[[C(W] = [xxx) o
(((- o
k5(e ((te-T))>E(X-
where 8(x) is the discrete d function which 0 for and for x and E(X) is single output kernel matrix which concludes the proof.
Next state useful lemma from Schur (1911) which allows us to bound the eigenvalues of the Hadamard product of the two PSD matrices.
Lemma 6.12 (Schur (1911)) Let B Ruxn be two Positive Semi- Semi-Definite (PSD) matrices. Then,
Amin (AoB) B)
min Bis) Amia (A),
Amax (A B) max Bú; Amaax (A).
Next we state lemma regarding concentration of the Jacobian matrix at initialization.
Lemma 6. (Concentration the Jacobian at initialization) Consider a one-hidden luyer neu- ral network model of the form æ + Vo wx) where the activation 6 obeys lØ(0) B and (=)) B for all z. Also assume we have 2 K data points æ ........ e Rd with unit euclidean norm (|æ; =1) aggregated as the rows of matrix X Ruxd Furthermore, suppose V has i..dd v-scaled Rademacher entries (i.e. =v equally-likely). Then, the Jacobian matrix random point Wo E RRlxd with i.i.d. N 1) entries obeys
[WW)) [[J(W))
30K
log(n).
100, In particular, long as with probability at least 1 - 1/0
k 1000 2 x|| log(n)
82
with the same probability, we have that
kv2 JWo)) -
I(X) 5o.
Proof Define C = J(W))J(Wo)) We begin by showing that the diagonal blocks of C' are concentrated. To do this first for s define the random matrices
A, (6' (Xw.) o (Xw.)") @ (xx*).
30

---

Under review as a conference paper at ICLR 2020
Now consider n diagonal blocks of C' (denoted by C[e,e] and note that we have c[e, 4 = (Ø' (XW") diag( ve diag) (WX*) ( (xx*)
A s=1
A..
s-1
Furthermore, using Lemma 6.12
|A,1 s max (d(TT,))) |X| B² |x|²
Also, using Jensen's inequality
[E[A,]] E|lal B² x
Combining the latter two identities via the triangular inequality we conclude that
|[(A, F[A.]) = ||
=[". & (1 [E[A.]I)** (2
(6.34)
To proceed, will bound the weighted
S Σ 1² (A. (A.,)[A..) a-1
in spectral norm. To this aim utilize the Matrix Hoeffding inequality which states that
S[| t) 2ne 2A
where 2 is an upper bound on |Σ (AA, E[A,1) 1) Using (6.34) we can pick A Et (2v2 12 4kv Bd1 X
Setting t 30 B²| X 1 log(n), we conclude that x||
P( |C[ E[C(] 2 P(| 2 1) -002
concluding the proof of concentration of the diagonal blocks of C. For the off- off-diagonal blocks C[e, 2] using (6.33) from the proof of Lemma 6.11 we have that
C[C,7 = Σ V..
Note that by construction (V. Vr, == are i..d. +1² Rademacher variables and thus C[e, is sum of zero-mean i.i.d. matrices and we are again in the position to apply Hoeffding's inequality. To this aim note that
Σ ΣV..
V2 4
Su
Σ
IA.l
AKAB X
a-1
so that take have
A
v*BB |
and again conclude that for t = 30v kud Bd llgg))
30
[[[[[[e,]] ( 1) s
102
Using the fact that E[C[,, = and K n, combined with a union bound over all sub-matrices 1 1 E K we conclude that
P [[[C[e,]] [[CC,]]
2 21 s K2n 102 sn -100
All that remains to combine the concentration results for the sub-matrices to arrive at the complete bound. In mathematical terms need to bound D : |C [[C]]] To this aim define D[e,:] to denote the éth block row of D. Standard bounds on spectral norm in terms of sub-matrices allow us to conclude that
SVK sup |
D[C S Ktt
1sスsK
D
SV sup
|[ee:]] & Kt= 30K x log(n), (
1SESK
concluding the proof. The result in terms of is obtained by using the population covariance Lemma 6.
31

---

Under review as a conference paper at ICLR 2020
6.2.4 UPPER BOUND ON INITIAL RESIDUAL
In this section we prove a lemma concerning the size of the initial misfit. The proof of this lemma (stated below) follows from a similar argument in the proof of (Oymak & Soltanolkotabi, 2019, Lemma 1.).).
Lemma 6.14 (Upper bound on initial residual) Consider one-hidden layer neural network model of the form a + V (Wx) where the activation 6 has bounded derivatives obeying (())), jo' (=)] S B. Also assume we have n data points 21, 22,22,,..., Un Rd with unit euclidean norm (1 ma e, = 1) aggregated as rows of a matrix X Raxd and the corresponding labels given by y RK", Furthermore, assume the entries of V are i.i.d. Rademacher variables scaled by elulee
50B (2g2kkkn and the entries of W Bloxd are i..dd. (0, Then,
(V(x")) s
holds with probability al least 1 - (2K)-100.
Proof We begin the proof by noting that
K oo
V [ ||
a x
We will show that for any row of V. with probability least 1 (2K)-101
oo o (WX*)
(6.35)
VK
so that simple union bound can conclude the proof. Therefore, all that remains is to show (6.35) holds. To prove the latter, note that for any two matrices W, W RRexd we have
|10 (XW") olle, - 10 ( v
o (XW7) 0- o (XWT)
sl0 -6 - (X(W |1/0
< - (xXW") )[r lolles
XW + (1ixn S) 0 XW o ((WW-)))ll lolle
- sB X - F /10/,,
<B xB X lole, W w/| |
where in (a) we used the mean value theorem with S a matrix with entries obeying 0 s SJ,, S 1 and Ixn the matrix of all ones. Thus, || (XWTT) vile, is a B X [|le, -Lipschitz function of W. Thus, fixing v, for matrix W with i.i.d. Gaussian entries
و (XWT) rlle, s =E[llo e 6, 1+t,
(6.36)
holds with probability at least 1-e
2nd 10l
|
Next given ~ N N(, 1), we have
[[((())] [[[+()]] [[((() (0)] B B B(llo]] s 2B and Var( s B². (6.37)
where the latter follows from Poincare inequality (e.g. (Ledoux, 2001, p. 49)). Furthermore, since has i...d. Rademacher entries, applying Bernstein bound, event
E. (|1" v12 250 log K [01)))
(6.38)
32

---

Under review as a conference paper at ICLR 2020
holds with probability
1 (-22K) Conditioned Ev, upper bound the expectation via
E| o (XW7) v to S E [l(((W7)
[g- [ (o (o)))))))
|olli Eg-r((.1) (6(1) (F0
0 250 4B2 log( B²
<32 (l ||
Here, (a) follows from Jensen's inequality. (b) from linearity of expectation and the fact that for æ;
with unit Euclidean norm W (N, I&), (c) from simple algebraic manipulations, (d) from the
inequalities (6.38) and (6.37). Thus using t = 18 n log(()) lolle in (6.36), conditioned on E, conclude that
v elllle es 50B K log(2K)kn
1 w lez
b (XW") ulle, $50 n log( lolle,
VK
(6.39)
holds with probability at least 1 Using a union bound over E, and the conditional concentration over W, the overall probability of success in (6.39) is at least (2K)- 101 concluding the proof of (6.35) and the Lemma.
{ (2K) where used |
6.3 RADEMACHER COMPLEXITY AND GENERALIZATION BOUNDS
In this section state and prove some Rademacher complexity results that will be used in our generalization bounds. We begin with some basic notation regarding Rademacher complexity. Let F maps Rd to RR Let {e, be i.id. vectors in R with
IF be function class. Suppose i..dd Rademacher variables. Given i...d. samples S {(x;, y: H ~ DD we define the empirical Rademacher complexity to be
Rs(F) - sup f()) feJ [-1
n
We begin by stating vector contraction inequality by Maurer Maurer (2016). This is obtained by setting ha (x:)) h h(y, (x::) ) in Corollary 4 of Maurer (2016).
Lemma 6.15 Let f() Rd RK and let é: IRK x R be 1 Lipschitz loss function with respect 1 be i.i.d. Rademacher variables. Given i.i.d samples {(x,, y:) V
to second variable. Let { define
(e, E sup feF
ell ( (m:))
We have that
Rs (e, S (2)
Combining the above result with standard generalization bounds based Rademacher complexity Bartlett & Mendelson (2002) allows us to prove the following result.
Lemma 6.16 Let E(.,-) R RK [0, 1] be 1 Lipschitz loss function. Given i.i.d. samples
((x,, Yo consider the empirical loss
1 Elyy,
C(f.e)
n. 1-1
With probability over the samples, for all f we have that
/
5 (2g(2
E[C(F,) ((),0)
71
33

---

Under review as a conference paper at ICLR 2020
Proof Based on Bartlett & Mendelson (2002),
5 (2g()
F[C(T,0) 2Rs(e,F) 2Rs())
n
holds with 1-6 probability. Combining the latter with Lemma 6.15 completes the proof.
Lemma 6.17 Consider a neural network model of the form æ [(;; V, w) V x) with W Rixd and V RR denoting the input and output weight matrices. Suppose Vo RK** is matrix obeying Vole sv/VkK. Also let Wo Rkxd be reference input weight matrix. Furthermore, we define the neural network network,function space parameterized by the weights as follows
M Kk
Fv.w = V W) such that VEV and W with
V
V: V Vol F S
R VTa
and W= W W|W:|WWWWW Wol S Mw and I Woll2, S
(6.40)
Additionally, assume the training data (a:;, yi [ are generated i..dd with the input data points of unit Euclidean norm (i.e. || 1). Also, define the average energy at Wo
1/2
n kn Σ (o(oo>)))
E
Also let {E:)i R be i.i.d. vectors with ii.d Rademacher entries and define the empirical Rademacher complexity
sup Ecf feFv.w
Rs (Fv.w)
E
n
1=1
Then,
Mw + EMy
R² Mw-My V/.
Rs (Fv.w) SuB
(6.41)
Vni
Proof We shall use wy to denote the rows of W (same for Wo, V, Vo). We will approximate & ((wr, ax)) by its linear approximation & (( (ww) ax:) ø' ((w), ax)) ((we wp æ.)) via the second order Taylor's mean value theorem. We thus have
Rs (Fv.)) s E
Σ 1-1
& Vo (Woz;)
n
E
Σ ? Vodiag (ò' (Wox,)) (W- - Wo)
WeW
x
K Σ
2n
E
idd
WeW
sup
s=1
Σ
y=1
v Veed" ((1 - (w0 x.)) bel x.)) ((w) fo mx))
R₂
a (V Vo)( - o0 ((Wo:))
sup Vev.WeW
1=1
R3
sup Σ $ (V Vo) (o)x(Woz;)
1=1
R4
34

---

Under review as a conference paper at ICLR 2020
We proceed by bounding each of these four terms. For the first term note that Σ diag (v) 0' (Wox,) x
R1 5-
sup
t Vodiag (o' (Woz;)) (w Wo) xz
(W-lll s
Σ diag (ø' (Woz;)) Vo E:a, W Wal
<-
sup pW
Mw
1/2
Mw
Σ diag (v) Ø (Woz;) x
1/2
Mw
Σ E diag (V) d' (Woz,) x.
F
1/2
Mw
Σ F diag (V) ø (Woz;)
1/2
BMw
Σ V Ei
BMw
VVll
BMw
Vn
where in the last inequality we used the fact that || VolF For the second term note that
R₂ <
E
sup
Σ
Σ
Σ
En
v0, ((1 twe x.) twe x.1) (lwe - wi xx,1)
2n
I W s.
s=1 1-15=1
A:
K
E
sup
Σ
Ein Vo
10" ((1 li (w0 an) + bie ker, ax:)) ((w) (w,:-w/w,aa w))
2n
| sR
1
Σ
ΣE
E
Σ Vo
R²B
2km
F-11-1
BR
I
2k
BR
2/k
35

---

Under review as a conference paper at ICLR 2020
In the above we used | for matrix M to denote the sum of the Euclidean norm of the rows of M. We also used the fact that VV22 11l,1 mvk. To bound the third term note that
1
R₂
-
E
sup Σ E (V - -
n
VeV.WeWis
$
-
E
sup
Volr116i1, (()(Wx,) - of Wo
Vev.WeW
1=1
DMv
sup Σ nvkK WeW
E
E (ollslo((Wa))) (Wozi)ll,,
vMy.
sup Σ
(W) o (Wnoz))l
nvk WeW ==1
vBMy
sup
(W - -Wo)z,lle.
nvk Wew
vBMy
Σ (I Wo)ll
sup
nvk weW i=1
vBMy
sup IIW Woll
Vk
WeW
vBMyMM
Vk
Finally, to bound the fourth term note that we have
R4
E
sup Σ
(V vo)o(Woz))
72
VeV i-1
1
Σ (Woo))) ,V -V-))
E
sup
IV Vo IV-
Myy
vMy
Σ Φ W
n/kK
12 1/2
vMy
8 (Woz; E
nyKK
1/2
vMy
Σ
nvkk
BMy
1
Σ E
lo(Woz))
1/
))
1/2
Vn.
km
PEMy
Vn
vBEMy
s
Vn
Combining these four bounds we conclude that
Mw
R²
MyMw EMy n
Rs (Fvw) SBB
VT:
Vi.
concluding the proof (6.41).
Next we state a crucial lemma that connects the test error measured by any Lipschitz loss to that of the quadratic loss the training data.
Lemma 6.18 Consider a one-hidded layer neural network with input to output mapping of the form e Rd fæ; V. W) V (Wx:) R.K with W Rkxd denoting the input-to-hidden weights and
36

---

Under review as a conference paper at ICLR 2020
Ve Rixk the hidden-to- toseen--toooee to-ouppu weights. Suppose Vo R is matrix obeying VVolee sv/VkK KK. Also let Wo Rkxd be reference input weight matrix. Also define the empirical losses
- 3 y: f(0; V, 2)
L(V,W)
1-1
and
((f,2) - - V n
with f:: &:R+ RRK RRK [0, 1] a one Lipschitz loss function obeying [yy y)= 0. Additionally, assume the training data { 1 are generated i.i.d. according to a distribution 'D with the input data
points of unit Euclidean norm (i.e. |0 1). Also, define the average energy at Wo
1/2
E=
len Σ (oo
Then for all f in the function class Fw given by (6.40)
Mw
R²
uBMyMw
EMy vn
log( (//))
E[CU,0) & VDVV, W) 20B Vn
+
Vk
V
(6.42)
holds with probability at least 1- 6. Furthermore, Suppose labels are one-hot encoded and thus unit Euclidian norm. Given sample (z. y) Rd x R generated according the distribution D, define
the population classification error
Errp (W) P(arg max yt arg max [i( W)). 1stck
kctc
Then, we also have
Mw R
uBMyMw
FMy /n
5 (og((//)
Erro 22
W) + 2/2BB
+
Vk
Vk
(6.43)
Proof To begin first note that any I-Lipschitz E with {(y. y) 0 obeys E(y. 9) s y Ulle.- Thus, have
C(S,0) El saa; V, w) b2 VCV, W),
where the last inequality follows from Cauchy-Schwarr Schwarz. Consequently, applying Lemmas 6.16 and 6.17 we conclude that
5log(2/0)
E[C(f,0 S -(1)))
Mw R²
vBMy
EMy
log(2/8)
VVC()) +2/2rB
V
VE
/n
which yields the first statement.
To prove the second statement classification accuracy, pick the l function follows E(y. ù) min(1, ly 1n--le Úlle.).
Note that, given sample (æ, y) Rd R with one-hot encoded labels, if
arg max # arg max fe(æ; V, W), Isek
Isesk
this implies
(y, fx: V, W)) ) 2 0.5.
Combining the latter with Markov inequality we arrive at
Eryp (W)+ s (x f() V. w))] = 2 E[ W)].
Now since l Lipschitz and bounded, it obeys (6.42), which combined with the above identity yields (6.43), completing the proof.
37

---

Under review as a conference paper at ICLR 2020
6.4 PROOFS FOR NEURAL NETS WITH ARBITRARY INITIALIZATION (PROOF OF THEOREM 2.3)
In this section we prove Theorem 2.3. We first discuss preliminary optimization result Section 6.4.1. Next, in Section 6.4.2 we build upon this result to prove main optimization result. Finally, in Section 6.4.3 we use these optimization results to prove our main generalization result, completing the proof of Theorem 2.3.
6.4.1 PRELIMINARY OPTIMIZATION RESULT
Lemma 6.19 (Deterministic convergence guarantee) Consider one-hidden layer neural net of the form fa; W) := (V(Wa) Wa)
with input weights W RRlxd and output weights V RKxk and an activation & obeying (0))) 2 B, (z)) B, and 16d (=)l B for all z. Also assume V is and we Irain over W based on the loss
fixed with all entries bounded by VV S VEK
Σ (1((;;;;) W) villé. ((W) 2
Also, consider point Wo (Roxd with J an (co, BB reference Jacobian associated with J(Wo) per Definition 5.1. Furthermore, define the information and nuisance N subspaces and the truncated Jacobian Jz associated with the reference Jacobian J based cut-off spectrum value of a per Definition 5.2. Let the initial residual vector be ro y (00--/(0 s(Wo) RRnK Furthermore, assume
8a
Eo min
6,
(6.44)
TuBI
and
1 BB
|
k 2 400
(Ba,r ST (rloe)))
(6.45)
52a.8
with 5 8 I'2 1. We run gradient descent iterations of the form W = W, -))((W starting from Wo with step size y obeying 1) S =² Then for all iterates T obeying S T r
na
B..
r
W Wo F
8
ro
roloz
(6.46)
a
a
2v BB
X
W. Wol
|rolle
(6.47)
kka²
Furthermore, after T = T iteration we have
da
|rtlle, S SE- ((l()ll + [[Lv(ro)lle) + vB x
rrllea.
(6.48)
Proof To prove this lemma wish apply Theorem 5.3. We thus need to ensure that the assumptions of this theorem are satisfied. To do this note that by Lemma 6.10 Assumption holds with 8 vB |X|. Furthermore, pick 5r x
da
bf which together with (6.44)
5a
guarantees (5. 13) holds. now turn our attention to verifying Assumption 2. To this aim note that for all W pied obeying
Bar + |nolla.)
W Wolls s R
38

---

Under review as a conference paper at ICLR 2020
as long as (6.45) holds by Lemma 6.10 we have
(W) J(W)) SBVK IV le..
| R
X
Vk
20T B x
(Bo.r rrll))
100 U² B2 |X|
Vh
dc
100 Ba| X
E 2
Thus, Assumption 2 holds with |W- - WW-Wl.- R := 2 BuI 8 (rolee) Now that we have
(
verified that the assumptions of Theorem 5.3 hold so do its conclusions and thus (6.46) and (6.48) hold.
We now turn our attention to proving the row-wise bound (6.47). To this aim let un denote the éth
row of W,, Also note that
VL(w:) = éth row of (WW)) r,))
Hence, using Lemma 6.10 equation (6.32) conclude that
[v( 11, s Bv BB K V
X
1r
S
vB X
|r,les-
V
Consequently, for any row 1 8 S k. we have
| (+)
w (0))
BB X
Σ
(6.49)
l2
Vk
To bound the right-hand side we use the triangular inequality combined with (6.25) and (6.26) to conclude that
9 1-
Σ
12
S1
Σ Fll + + Σ
rr
Frllez
1-0
[-0
r |role,
2 +0)
r
EiS) a² a
2T
rlroleez
at
r 52 |rollea
(6.50)
a
where in the last inequality used the fact that si choice of e. Combining (6.49) and (6.50), we obtain
a 25T per (6.44) and
eB
da
5T8
5T
per our
|o
(T)
||,
2v X
|rolez
2ka2
completing the proof of (6.47) and the theorem.
6.4.2 MAIN OPTIMIZATION RESULT
Lemma 6.20 (Deterministic optimization guarantee) Consider the setting and assumptions of Lemma 19. Also assume [TT lle 2 cirollle for a constant c. > O if co > O. Furthermore, assume
a
Bara
222
X
6
< min
25
'BI2 rollez
X
a²
T
(6.51)
39

---

Under review as a conference paper at ICLR 2020
and
a
r ro &2 Barr
2
v
|
1
T
o.r
k 1600
(6.52)
CvB
X
a
and T 2 1. We run gradient descent iterations of the form 1T1 W, -r)((W, starting from Then for all iterates obeying 5 <T:=
Wo with step size n) obeying $ -
2B..r
I WollF S
(6.53)
2v |
W Woll2.00 s
Vka² |rolle.
(6.54)
Furthermore, after TT iteration we have
If(W)) - -ylle, S ([ [[ow())))e + cltrolee
(6.55)
Proof To prove this lemma we aim to substitute
[vB
X| a
Bar 'Foolll
8 min
1,
(6.56)
in Theorem 69. To do this we need to verify the assumptions of Theorem 6.19. To this aim note that the choice of 5 from (6.56) combined with (6.52) ensures that
rorllc
G B6
|X|
1
21600
CNB XX] |I
Bo.r
a
T l|rollea
2 1600 D
X 2
a.r
2 max
CvB X
Barr
a
1600 B6 |X||
r2
1
a.
[uB|Xx
B..r Tirallea
a
min
2
B |
B
o.
8288
22 B6
|X|
(Ba.r + Ba.r)²
400
8
12
1
B6
X 6
(B..r + oTlllol
2400
8a8
so that (6.45) holds. We thus turn our attention proving (6.44). Eu 0, the statement already holds. Otherwise, note that based on Lemma 6.2 equation (6.3) we have
a [lI[(ro))
allll(ro)ll x
car calrrolez
Bar crrle
Barr 2
(6.57)
A1
vB X|
vB X
Recall that a
vog VK'
which implics that
If 8 Cb XI.
[
For (6.44) to hold it suffices to have so min
a
40

---

Under review as a conference paper at ICLR 2020
Iff 8 Bo.r Trrlle
For (6.44) to hold it suffices have Eo S /
C PBI
Ba aa Troley [X
based on
(6.57) we have
Go PBT
S
VB
X
a
cB cBa,ra
5
vB
rolle
X
Vb
ca
rз
a V8
ca V6,
min
5
T3
da
min
6.
rB
Combining the latter two cases as long as
a²
Bara I
22 |
c 25
min
(6.51),
a²
then (6.44) holds. As result when (6.51) and (6.52) hold with ō = min [ Ba. both
F to assumptions of Theorem 6.19 also hold and so do conclusions. In particular, (6.53) follows from (6.46) by noting that based on our choice of 5 we have 6_ |role, & B (6.54) follows immediately from (6.47), and (6.55) follows from (6.48) by noting that based choice of å åa S 5. have x
6.4.3 MAIN GENERALIZATION RESULT (COMPLETING THE PROOF OF THEOREM 2.3)
We state the following rigorous and stronger version of Theorem 2.3. The differences (besides constant terms) are the use of X rather than /n (we always have |X| ||| S vn) and use the tighter bound Jfrolle, rather than [[l (ro))le), /a.
Theorem 6.21 Let G,T,ā be scalars obeying S 1/2, T 1, and ā 2 O which determine the overall precision, cut-off and learning duration, respectively." Consider training data set distribution D where the input samples have
(.), Rd RK generated i.i.d. according unit Euclidean norm. Also consider a neural net with k hidden nodes as described in (1.1) parame- terized by W where the activation function ó obeys l0 (z)),lo"(=)) { $ B. Let Wo be an arbitrary initial weight matrix. Also assume the output matrix has bounded entries obeying [V "JEK" Furthermore, set J == J (Wo) and define the information and nuisance N subspaces and the truncated Jacobian Jz associated with the reference/initiial Jacobian J based cut-off spectrum value vBa V TV | Also define the initial residual ro ((W) y RRK and pick C, > that |rllzz Cr. Suppose number of hidden nodes lo obeys /
C.T
1: kZ @i:222''
(6.58)
with 2 1 and tolerance level Ç. Run gradient descent updates (1.5) with learning rate 17 iterations, training loss obeys
Then, after T nje?
I
If(Wr) yle, [Il + C, ( Vm.
and with probability least the generalization error obeys
Errp (W)) s (ro
12vB n
(Is/rolls,
F -FII((r)lle)) +5V
log(2/6)
2C, + +C).
bias term
pariance term
"Note that this theorem and its conclusions hold for any choice of these parameters in the specified range.
41

---

Under review as a conference paper at ICLR 2020
Theorem 6.21 immediately follows from Theorem 6.22 below by upper bounding Da, (see Definition 6.1) using Lemma 6.2 equation (6.2).
Theorem 6.22 Consider training data set ((as; (=))= IR IRK generated i..d. according to distribution 'D where the input samples have unit Euclidean norm. Also consider a neural net with & hidden nodes as described in (1.1) parameterized by W where the activation function o obeys (Ø' lo)
B. Let Wo be arbitrary initial weight matrix. Also assume the output matrix has bounded entries obeying [Vlle_. $ 'EE Furthermore, set := J (W and define the information I and nuisance N subspuces and the truncated Jacobian JI associated with the reference/initial Jacobian J based on cut-off spectrum value vBä /Ba//v// / Also define the initial residual ro f(Wo) y Rnk and pick C₁ > 0 so that Irole number of hidden nodes k obeys
vn & Cr.. Also assume, the
C
k2 25600
(6.59)
B
with r 2 1 and tolerance level S S Run gradient descent updates (1.5) with learning rate iterations, with probability at least 1- the generalization error 75 S 1x Then, after T qa? obeys
(ro)lle
12vBDo,r Vn
log log(2/6) 2C, +
Errp (WT) &
+5
(6.60)
n
term
varsance term
where Da,r the early stopping distance as in Def. (6.1).
Proof First, note that using a 3 vB |
Bar
T
s Irole, per (6.2), and l|rolle S Cryni we have
a
P/role
L/=
S ls
s Cr
B X
Bar
Bar
This together with s implies that
Tlllle Bar
r
3BB X
2 B X x2
Bar
Trolee
Ba.r
C₁ r
Vn.
(6.61)
Barr
Thus when
C21
k 225600
Q2
C,T
2
B6
|X|
=6400
a
V
C,1
ny G B
X
6400
a
C, r
B2
Bar 8 Bd 1x1
=1600
2
Vn
B.r
a
(6.61)
l'lrolle BAr
B
a. 1
B6
|x|
1600
SB X
42

---

Under review as a conference paper at ICLR 2020
Thus, (6.52) holds. Also (6.51) trivially holds for Ev. Thus applying Theorem 6.20 with Eu 0 the following three conclusions hold
2 2D
W Wolfs
(6.62)
a
and
2xBT X
W Woll2.00
|rollez
Vka²
(6.63)
Vka²
and
(I((W)) - ylle, se Te + [To S Irolles
<|[lv(ro)le= + (eT+ + : Iroollz
|rollesSC.vm [r)(ro) + Cr (et + Vm.
(6.64)
Furthermore, using the assumption that |V S VEER Lemma 6.18 applies and hence equation (6.43) with W Wr. VC(WT) implies that
1s(wr) Mw 2Da,r. My O, and R 2/TCC, x
Vn
[S(W)) Ul1
2Da.r
R²
5log
Emp Wr) 2
+ +3BB
(6.65)
vn
Vn
Vkl
Also note that using (6.59) we have
BrRR
12
Ban XI2
S C S
S
(6.66)
le
Via
2
Plugging (6.64) and (6.66) into (6.65) completes the proof.
6.5 PROOFS FOR NEURAL NETWORK WITH RANDOM INITIALIZATION (PROOF OF THEOREM 2.2)
In this section we prove Theorem 2.2. We first discuss and prove an optimization result Section 1. Next, in Section 6.5.2 we build upon this result to complete the proof of Theorem 2.2.
6.5.1 OPTIMIZATION RESULT
Theorem 6.23 (Optimization guarantee for random initialization) Consider a training data set ((x, y IRa x R generated i.i.d. according to a distribution where the input samples have unit Euclidean norm and the concatenated label vector obeys 1/yle = /n (e.g. one-hot encoding). Consider a neural net with hidden layers as described (1.1) parameterized by W where the activation function obeys (o'(2) (z)), "ollo"""20 (0"(2) S B. Let Wo be the initial weight matrix with i..d. (0, entries. Fix a precision level and set
(6.67)
50B (0BBllo((2))
Also assume the output layer V has i.i.d. Rademacher entries scaled by 'kK"' Furthermore, set E( and define the information I and nuisance N spaces and the truncated Jacobian JI associated with the reference Jacobian based on a cut-off spectrum value of ag = ā / s BVK [X] per Definition 1.1 so as to ensure [1r(z)le, 2 clyle, for constani Assume
43

---

Under review as a conference paper at ICLR 2020
1 K 1 áÇaa
k 2 12x 10
(6.68)
with I' 2 1 and < 5. We run gradient descent iterations of the form (1.S) with a learning rate iterations, the following identities 7) 0² 2² Then, after T = q
IK
I((W T..) - yle, s (IIN( + - (111 (1100)l++400 +4CVn,
(6.69)
2v 2vK(B.n. m...no..(2 ((V) +TvMm
W, Wolle
(6.70)
V/10
W, - Woll2,00
4DBK| X
T
(6.71)
vag
k
hold with probability least (2K))-100
Proof To prove this result we wish to apply Theorem 6.20. To this we need to verify the assumptions of this theorem. To start with, using Lemma 6.14 with probability at least 1 1- 100 the initial prediction vector f(W) obeys
ll((W))les s Slvlle, = <VV V 2
(6.72)
Hence the initial residual obeys |role2 s 22/n. Furthermore, using < c/2
Iru yle, scllvlle, [[Iz(ro y) s Elylle..
(6.73)
Thus,
[[z(r)) 21117(())le, [| + y)
21117 </
2 (c- <) Iylle
2 ll
(6.74)
(6.75)
Thus the assumption on the ratio of information to total energy of residual holds and we can replace with & in Theorem 6.20. Furthermore, since (.)) is --Lipschitz function of its input vector & norm hence we also have
(ro) s BB). + -r y1,,3 s Byo.r(y) [C]lgrl
(6.76)
Next we wish to show that (6.51) holds. In particular we will show that there exists an Eg- reference Jacobian J for J(W) satisfying JJ = E[J(WW)) (W,)"") Note that, such a J will have exactly same inforrmation/nuiaance spaces as the square-root of the multiclass kernel matrix Le. ([
since these subspaces are governed by the left eigenvectors. Applying Lemmas 6.13 (with a scaling of the Jacobian by 1/VkK due to the different scaling of V), we find that if
1000 Ba X log(())
k>
(6.77)
82
then,
5v
(6.78)
K
Let J(W) be obtained by adding max Kn -p. 0) zero columns to JWW). Then, using (6.78) and Lemma 6.4, there exists J satisfying JJ" = -I(J(WW) ((W)) and
5v2
[J(w)) J J s $
K
44

---

Under review as a conference paper at ICLR 2020
Therefore, J is ei 4 Bv² and note that using a
k reference Jacobian. Now set
CBVK
θ = min
BT X| | Vnk
VK ay and rroll, $ $2vn
B r
CBVK X1
C
= =min
BT X Vnk
(T)
B ra
VCB
min
vBT2
X
'T)
Ba
C2 |
2
22.min
(6.79)
VBBT2 X
a²
To continue further, note that Boo.r calculated with respect to 2x2 with cutoff og is ex- actly same as Bar calculated with respect to J with cutoff
which is square-root of E[J(W)) Thus, using (6.79) ensure (6.51) holds it suffices show
vR
8v2 a θ r2ag O.
2
K
25
50K
Hence, ensure (6.51) holds we need to ensure that obeys
5 ag θ
200
Thus using 5 θ to ensure (6.51) we need to make sure is sufficiently large so that (6.77) holds with this value of 6. Thus it suffices to have
200
1 K 8
X n log(n)
k 212 x 10?
(6.80)
I B
X log(n)
212 x 107
4K2BBTT |
1
K B |
X 4 log(n)
24x 10
Aad
Ç7
2
ap X (lg(n)
[KKBT |
K B4
24
ag r
AAKBTT |
kd B
X
(n)
20x
Aaf
C*B*K² K2
X
Ç2
ap K B |
(0)
nKB2T |
an
log(n)
2 4x 107.
+
B2 0
B2 |X||
a
4
24 107 max
nKB414 |
2
ag
1
2R2 B3 X | (n))
CB
B2BKK2 |
C2
a
4
K²B*
log(n)
=4 x 10?
cBa Br
(BVK
0 min
1000 2 Bd X llo(n))
(6.81)
82
Here, (a) follows from the fact that E(X) \1 < X|X equation (6.3), and [Tz(())
||y/ = Vn which combined imply
B. Ba.r X1
[1x(r))) 2 B|
[lr 0gc 1 1y 0g
One
/n
(6.82)
X
B
X
45

---

Under review as a conference paper at ICLR 2020
To be able to apply Theorem 6.20 must also ensure (6.52) holds. Therefore, it suffices have
K Bº
x
log(n)
à 2644
100
(6.83)
(1)
K$ R |X|
nn
25600
(6.84)
5²v200
aj
K |
n
A: 212800
B2 |X|
v²ag
(6)
4 n 1
KABO
|| |
1
2 3200
C² |
v2ag
T2 Prole 2
KAB B
|
6 B
3200
D.
C2 |
B
v20
| 6 T
ag
F 1t
a.r
21600
CvKBI X
Bar
V2a
a
Tomole
B6
X
6
r
a.r
-1600
(6.85)
CuB |X||
Barr
a
Here, (a) follows from the fact that n. 2 K and the relationship between and v per (6.88) and (b) follows from the fact that per equation (6.2) have
Bar ST [rolle, vn
Note that (6.80) and (6.84) are implied by
1 K B X 1 log(n)
k 12x 10"
(6.86)
ACta
which is the same as (6.68). What remains is stating the optimization bounds in terms of the labels y. This follows by substituting (6.72), (6.76), and the fact that ||rolle, s 22/n into (6.55), (6.53), and (6.54), respectively.
6.5.2 GENERALIZATION RESULT (COMPLETING THE PROOF OF THEOREM 2.2)
The theorem below is the formal statement and a more general version of Theorem 2.2. The differences (besides constant terms) are the use of X rather than v (we always have |X| s vn) and use of the tighter bound J/yl 62 rather than [T)ll))
Theorem 6.24 Let Ç,T, ā be sealars obeying Ç 1/2, P 1, and ā O which determine the overall precision, cut-off and learning duration, respectively.' Consider a training data set {( y: H distribution D where the input samples have unit Euclidean
Rd RK generated i...d. according norm and the concatenated label vector obeys yy v (e.g. one-hot encoding). Consider neural net with k hidden nodes as described in (1.1) parameterized by W where the activation function & obeys (o'(2), (=)))(("((2) S. B. Let Wy be the initial weight matrix with i.i.d. N(O. 1) entries. Fix precision level Ç and set (/t////////// /log(2))) Also assume the output layer V has i.i.d. Rademacher entries scaled by v information and nuisance N spaces and the truncated Jacobian Jr associated with the Jacobian X
"KK" Furthermore, set (E(X)) 12 and define the
J based on cut-off spectrum value of ao ā V/v K B per Definition 1.1, Assume
log 5
k
(6.87)
NNote that this theorem and its conclusions hold for any choice of these parameters in the specified range.
46

---

Under review as a conference paper at ICLR 2020
with r 1. We gradient descent iterations of the form (1.5) with learning rate 17 -= iterations, training loss obeys (6.69) and classification error Errp(WT) is
Then, after T upper bounded by
TK
qu
12BVK vn
_ [ +12
log (2/)) (+5)
+20
Vn
Coo
à a/nl X
n
biax
variance
holds with probability at least 1 (2K)-100) -.
The theorem below is restatement of Theorem 6.24 after substituting the upper bound on the early stopping distance D P of Def. (6.1).
Theorem 6.25 (Neural Net - Generalization)) Consider training data set {(,,, ( y:) e R generated i..d. according to a distribution D where the input samples have unit Euclidean norm and the concatenated label vector obeys |lylle, Va (e.g. one-hot encoding). Consider neural net with hidden nodes as described (1.1) parameterized by W where the activation function & obeys lo' (2)1, (z)l B. Let Wo be the initial weight matrix with i..dd (0, 1) entries. Fix a precision level ( S & and set
(6.88)
50B /lgg/)
Also assume the output layer V has i..dd Rademacher entries scaled by 'kK"
2 Furthermore,
J = E(X)12 1/2 and define the information I and nuisance N spaces and the truncated Jacobian Jr associated with the Jacobian based on cut-off spectrum value of org = â t/n K || | B X per Definition 1.1 chosen to ensure [Iz(y) lez c) clyllee for some constant 0. Assume
1 K B
X 2n2 log(n)
k 12 x 10
(6.89)
ACt
with r 1. We run gradient descent iterations of the form (1.5) with a learning rate 1j S y2 1²
Then, after T qprao iterations, classification error Errp (W)) is upper bounded by
тK
(1) le, + + [1 lez 12B/K
log(2/5)
Erpp WT) 2
D r
(+ 10
Vn.
Vn
avn
holds with probability at least (2K) (2K)-110) 1100- 5.
Proof Under the stated assumptions, Theorem 6.23 holds with probability 1 (2K)-100 1 proof
will condition on outcomes the Theorem 6.23. Specifically, we shall apply (6.43) of Lemma
6.18 with My and R dictated by Theorem 6.23 where the output layer V is fixed. Observe that
[V] VKkl lem = v, we have
IS(Wr) -yles
Mw
R22
5 (lg(22
Emp WT) $
BuB Vn
+
(6.90)
vn
/k
Theorem 6.23 yields
(S(W)) vlle vn
[w) +e [1)(()) -
4Ç.
(6.91)
Vn
Using (6.70) for Mw
vBMw
2B KD (B))
2BVKTÇ
(6.92)
Vn
Vn
Cu
47

---

Under review as a conference paper at ICLR 2020
Using (6.71) on row bound R and lower bound on k
Rd
4 K2
x
BvB
Vk
vagVk
c²²²
B (l)((n)
SÇ.
(6.93)
Plugging in (6.91), (6.92), and (6.93) into (6.90) concludes the proof.
A THE JACOBIAN OF THE MIXTURE MODEL IS LOW-RANK (PROOFS FOR SECTION 2.3)
The following theorem considers simple noiseless mixture model and proves that its Jacobian is low-rank and the concatenated multiclass label vectors lie on rank K2C information space associated with this Jacobian.
Theorem A.1 Consider data set of size n consisting of input/label pairs y:) RR x R generated according to the Gaussian mixture model of Definition 2.4 with K classes each consisting of (K.C)
C' clusters with the cluster centers given by (1r,z) (1,1)=(1,1) ((,)))() and 0. Let E(X) be the multiclass neural tangent kernel matrix associated with input matrix X = = deviation of the output layer set
xn," with the standard V Also define the information space be the range space of E(X). Also let M [[1,11.. ... #x,c]' be the matrix obtained by aggregating all the cluster centers rows and let g be Gaussian random vector with distribution (0, Ia). Define the neural tangent kernel matrix associated with the cluster centers as
Ê(M) (MM*) o g- (MM)) (Mg) (Mggg((Mg))))) (Mg)*) RCCKK
and ussume that {M full rank. Then, the following properties hold with probubility KC "Ceep(=> SKC
I is K2C dimensional subspace.
The concatenated label vector y - [3T
J lies on
The nonzero eigenvalues (top K2G eigenvalues) of Σ(X) are between 2KC 8min (E(X)) and 2n KC [. Hence the eigenvalues of the information space grow with n KC-
Proof First, we establish that each cluster has around the same size. Applying Chernoff bound and union bound, we find that with probability KC ('C'exp(==a ('''epp(=kk' (
0.5m < म7 2ñ.
Note that based on Lemma 6. the multiclass covariance is given by
Σ(X) =v² Σ(X).
where E(X) (XXT)) @ un w(.,)) o (Xg) (" Due to this Kronecker product represen- tation, the range space E(X) is separable. particular, note that with
7= Range (5(X))
we have I I I which also implies rank(I)= K rank (ī). Hence, this identity allows to reduce the problem to single output network. To complete the proof we will prove the following three identities:
7 has rank KCC
48

---

Under review as a conference paper at ICLR 2020
The nonzero eigenvalues of Σ (X) are between 0.5Ms (E(M) to 27 [(M)
The portion of the label vector associated with class i.e. (0) R" (see (5.4)) lies I. Hence, the concatenated vector y lies on I Ix @ I.
To prove these statements let [2(:; Wo) and J:MM:W be the Jacobian associated with the fth output of the neural net (see (5.4)) for data matrices X and M. Observe that the columns of [x Wo) are chosen from Te( (M;; Wo) and in particular each column of (M; Wo) is repeated between 0.57 to 27 times. To mathematically relate this, define the KC' dimensional subspace S of R" where for any v S, entries v and ey of are equal iff data point H; and 2 are equal (i.e. belong to the same class/cluster pair). Now, we define the orthonormal matrix Us R as the 0-1 matrix with orthogonal rows that map RRC to as follows. Assume the ith data point æ, belongs to the class/cluster pair (L,, E.). We then set the ith row of Us as vect( Ct. eT,) Using Us we have
UsJ Wo) Wo).
Now note that using the above identity we have
Us UM) = (X))
Since Us is tall and orthogonal, the range of E(X) is exactly the range of Us I S which KC dimensional. Furthermore, nonzero eigenvectors of E(x lie S and any eigenvector satisfies
0 oT TEX)o Smin (Us)² min (E()) 8.5 (É(M))
and similarly
8d (X)x v & 2n {(M)
which follows from the fact that snnomm-quuardd of columns of U are between 0.5m to 2n. Finally, we will argue that label vector y lies on S. Note that for all samples i that belong to the same (2) will be the same (either zero or one), thus (f) S.
cluster y
Next lemma provides perturbation analysis when there is noise.
Lemma A.2 Consider the single-outpe NTK kernel given by
-(X) E [''o((Xw) [w) (xxx)
and assume that this matrix has rank that Ar+1 Also assume a noise corrupted version of X given by
(Σ(X))= Xn12 (E(X))= An (E(X))
x
Vd
with Z a matrix consisting of ( 1) entries. Then,
[Σ(X) E(X) s A where
= o² B² logn n
X + o² B² (n/d+ 1)+ Vlogn B² |x|] + oB vn/d+ 1 |X|
(A.1)
holds with probability at least - 2ne Whenever as Vlogn'
1 A is upper bounded as
$ B
(A.2)
Furthermore, let V, V e RRax be orthonormal matrices corresponding to the top r eigenvalues of E(X) and (XX). Then,
A
VV -VV
X (X)) A
Proof Note that
diag (o' (Xw)) X diag (6' (Xw)) X =dag (9' (Xw)) X diag (ø' (Xw)) x diag (6' (Xw) 03 (Xw)) X
diag (o' (Xw)) (8 -X)
49

---

Under review as a conference paper at ICLR 2020
Now define M diag (d' (X(w)) X and M diag (x)) X and note that using the above can conclude that
M M s diag @6' (Xw) - of (Xw)) x||
+ diag (o' ( w (X X)
BB (X X)w w l._ |
X X
Now using the fact that
M MM M M +2 M
M
|M]]
we conclude that
- - = MM TMM-MMM MM'
s B ( |X| + B X x1)²
+ +B || X (B|X X)w(
| B X | x
$2 |X| E [ x)w |/- /,n 2B2 X-x x
+ 2
X -
2B X x |
To proceed further, with probability 1 - exp( exxp(dd/2). each row of X X is upper bounded by 2a. Hence, using a standard tail bound over supremum of Gaussian random variables (which follows by union bounding) we have
tm E[][(X X)w 1
20 2lggn
holds with the same probability. Furthermore, spectral norm bound on Gaussian random matrix implies that
| x|| < (2(V va))2 s 8(n/d++ 1)o²,
holds with probability at least - o (m+d)) Plugging these two probabilistic bounds into the chain of inequalities we conclude that
[X(X) Š(X) s o² B² logn X 2 o² B² (n/d+ 1) Vlogn- B X + aB² oB² Vn/d+ |X|
To establish (A.2), observe that B² /og X dominates over other terms in the regime /. Vlog small. The final bound is standard application of Davis-Kahan Theorem Yu et al. (2014) when we use the fact that ((X) is low-rank.
The following lemma plugs in the critical quantities of Theorem 2.2 for our mixture model to obtain generalization bound.
Theorem A.3 (Generalization for Mixture Model) Consider a dataset (0;, Vi) generated i..d. from the Gaussian mixture model in Definition 2.4. Let Am Amin (E(M)) where M &Cxd is the matrix of cluster centers. Suppose imput noise level obeys
B2KCvoog
Consider the setup of Theorem 2.2 with quantities Ç and I. Suppose network width obeys
p'p8KK 8
logn
k Z
1x min
With probability - 4/2 KC exeepp WKC
(2K) 5, running gradient descent for
C with learning rate 17 x we have that Anmin
a MognB2KC TBKVC
log(2/6)
Erro(Wy)
12 + 5
+ -
Amnin
/ Vndmin
n
50

---

Under review as a conference paper at ICLR 2020
Proof The proof is application of Lemma A.2 and Theorem A.1. Let I' be the information space corresponding to noiseless dataset where input samples are identical to cluster centers. Let P P correspond to the projection matrices to I and I', First, using Lemma A.2 and the bound have
P Pl sc o VlognBBKK
Ami
for some constant c Next we quantify (y) using the fact that (i) (Tz via Theorem A.1 follows
Hr le 2 (x)ll, - (y) (1) 2 vn(1- o WlognB
(A.3)
Amin
In return, this implies that
no no Ml
[ $
Amin
To proceed, we pick oo find that, classification error is upper bounded by
Amint 2RC
and corresponding a V /
Amin
and apply (??)
2B=K"C
aVlonBBKKC TBKVC
log (2g(2/5)
Erep (WT)
12Ç 5V
2e
Amin
Vndmin
n
B JOINT INPUT-OUTPUT OPTIMIZATION
In this section we wish to provide the ingredients necessary to prove a result for the case where both set of input and output weights W and V trained. To this aim, we consider the combined neural net Jacobian associated with input and output layers given by
(a; V. W) Vo(Wx).
(B.1)
Denoting the Jacobian associated with (B.1) by J(V, W) we have that
J(V, -)= = (V() J [W)] Knxk(K++))
Here, J(W) is as before whereas ((V) is the Jacobian with respect V and is given by
J(V) (J(m) (v2) [(Kk]]
(B.2)
where J(ve) Raxk is so that its l'th block rows of size is nonzero for s E K i.e.
?th block row of J(v))
((XW")
else
Hence, J(V) is K x K block diagonal with blocks equal o( (XWT). The following theorem summarizes the properties of the joint Jacobian.
Theorem B.1 (Properties of the Combined Input/Output Jacobian) J(V, W) satisfies the fol- lowing properties.
Upper bound: ( VV).)
Row-bound: For unit length u: |mat
(J ( (JT BB 1e_ |X|.
Entry-bound: For unit length u: ||mat (J ( (V) i- &BI 12,00 |X]
Lipschitzness: Given inputs V. V and outputs W. W
[J(V, W)-J(V)'V W X KK
V V + MLL++KIIVI VVIV W W W W'
51

---

Under review as a conference paper at ICLR 2020
Proof First, we prove results concerning JVV). First, note that
[V] & |0 X w B|
Next, note that for u = [[u ux] E RR we have
(V)llle max 1 W )uellew
max (0 X )uul Isesk
B| W 2,00 |
Let J2,T2 be the Jacobian matrices restricted to V and W of J(V. W). To prove Lipschitzness, first observe that
- ( - -))
(V2(V w) J2(' W')l
Next, observe that
[V W) (V'. w')| (
W'
We decompose J2 via
||Ja(V, W) -2 W (V, W) J2(V, W ) (V W J2(V W')l $ Bv V |x| W Wl, [ (V. W - J2("
To address the second term, note that, Jacobian is linear with respect to output layer hence
|[ W') JVV', W || V W'll Combining the latter two identities we arrive at
BV KA BVKk
V V'Ila x
[J2(VV W) - J2(",, W s (v (K V V'
+ +V V
W Wl
completing the proof.
C FURTHER NUMERICAL EXPERIMENTS
We depict the approximate eigenstructure in Section C.I. Complementary to Section 4, in Appendix C.2 we provide the complete set of experiments we performed on the original 10-class CIFAR- 10 dataset covering various levels of label corruption. In Appendix C.3 we show numerical results on sub-sampled 3-class version of CIFAR-10. Moreover, we demonstrate that our theory holds across different datasets by providing experimental results on MNIST in Appendix C.4.
C.1 EXPERIMENTS ON FULL (10-CLASS) CIFAR-10 10
As mentioned earlier while calculating all the cigenvalues is not possible, we also verify the bimodal structure of the Jacobian using the entire spectrum by approximating its spectral density using the method recently described in Ghorbani et al. (2019a) and Papyan (2019a) for Hessian eigenvalue density estimation. We detail the parameters of the algorithm in Appendix C.5. Figure 9 depicts the estimated spectrum before and after training. We observe similar bimodal spectrum with a few outliers. Moreover, both depictions of the Jacobian eigenstructure we observe increasing separation between the low and high end of the spectrum after training.
C.2 EXPERIMENTS ON FULL (10-CLASS) CIFAR- 10
In addition to what has been described in Section here disclose the complete set of experiments performed on the CIFAR-10 10 dataset. We trained the modified ResNet20 model described Section with SGD as longs as it was necessary achieve good fit to the training data. Information subspace
52

---

Under review as a conference paper at ICLR 2020
10a
10
10
Scaled dousily
10a
Scaled density
10a
10a
10
10
10
10-1
10-1
10-2
10-1
10
10
10a
10a
10a
10a
10a
Singular value
Singular values
(a) Scaled spectral density of initial train Jacobian
(b) Scaled spectral density final train Jacohian
Figure 9: Scaled spectral densities of the full train Jacobian different stages of training
[x)ill)
[[Tx())) liyle
[Tx(())) ||ralle
[[Tr((P))(2)
J k2
[nolle,
Irolez
J train
0.38081
0.92465
0.027224
0.37114
0.92858
0.027293
Enxt
J train
0.9869
0.16131
0.00070893
0.98669
0.1626
0.00070354
final
test
0.38 884
0,92423
0.060229
0.37227
0.92812
0.06037
irui
J Test
0.80926
0.58746
0.0013734
0.80912
0.58764
0.0013716
Table Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using uncorrupted CIFAR-10 data.
spanned by the top 50 singular vectors. We marked figures and table entries also included in Section 4 by asterisk.
Experiments without label corruption. We trained the modified ResNet20 model described in Section 4 with SGD for 400 epochs with learning rate 0.1 on the original dataset without any form of data augmentation. The network output after the last layer has been scaled by s 0.025 in all experiments to follow.
Experiments with label corruption. We corrupt the labels in the training data by switching each label to a strictly different (incorrect) class. We train the network the corrupted dataset for 800 epochs with initial step size 0.1 decayed to 0.01 after 760 epochs.
[1)
[
[
[w((r))e
Jorrole,
19l2,
1yl,,
Tvl.
Troles
Trales
Trolles
J
tras
0.35328
0.93552
0.021592
0.36954
0.92921
0.021568
Ereit Tras
0.92214
0.38685
0.00087246
0.92324
0.38423
0.00087304
Table Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 25% label corruption CIFAR-10 data.
53

---

Under review as a conference paper at ICLR 2020
I trali
10
10"
Pollz Marteel 28
10-2
Resitaal energy
Resistal eaungy
10
Pulli
10"*
10
10-3
100
200
300
400
100
200
300
400
Epochs
Epochs
Residual projection on initial train Jacobian
Residual projection final train Jacobian
109
10"
Residuud enengy
10a
Residnal energy
10-1
Tralig
10-2
Poli
Polls
100
200
300
400
100
200
300
400
Epochs
Epochs
(c) Residual projection initial test Jacobian
(d) Residual projection final test Jacobian
0.8
Choisiing mine
Dror
0.4
300
Epochs
(e) Training and test of experiment*
Figure 10: Experiments on the original, uncorrupted CIFAR-10 dataset. *: we discuss these plots in Section
|
[
[Mz(r
[[T))))))
J L2
lttle,
|
|role,
|rolls,
|ro
Trann
0.32762
0.94481
0.017556
0.32152
0.9469
0.017521
enst.
Ftrain
0.8956
0.44487
0.00096413
0.89597
0.44412
0.00096652
Final
Lest
0.38013
0.92493
0.080777
0.37454
0.92721
0.080766
inst
Fest
0.7041
0.7101
0.0040147
0.70229
0.71189
0.0040423
Jlest
0.44774
0.89416
0.0012216
0.44409
0.89598
0.0012157
[snal
Table 5: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 50% label corruption on CIFAR-10 data.
54

---

Under review as a conference paper at ICLR 2020
10-1
Residhu energgy
Resishal energye
10.2
10-2
10-3
10
Feel Trali
10-4
10-4
paytesil
10"6
10
10-6
100
600
Epocks
Epochs
(a) Residual projection initial train Jacobian
(b) Residual projection on final train Jacobian
Traising
0.8
Text
Error
0.4
200
1000
600
800
Epochs
(c) Training and test error of experiment
Figure 11: Experiments with 25% label corruption on CIFAR-10 data
[1
[
[
[n
Twlez
Tylez
rrlle
rraley
|rollez
J snit
0.31756
0.94824
0.0056031
0.325
0.94571
0.005592
fram final
0.50238
0.86465
0.00047518
0.50718
0.86184
0.00047967
Table 6: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 75% label corruption on CIFAR-10 data.
55

---

Under review as a conference paper at ICLR 2020
10a
109
10"
10"
Resichal energg
Residaal enangy
10
10-2
10
10-1
Lreif
10-
Traliy
10
Patte IE
10
Trale
10-3
payte. IE
10
10
200
4010
600
800
200
400
600
800
Epochs
Epocks
(b) Residual projection train Jacohian 50 epochs (dip))
(a) Residual projection on initial train Jacobian
10c
10P
10"
Resithua enengy
Ma of AAHUILAA
Rosichal caurgy
10-2
Trilig iigteelle
10-3
10-1
Truily y
10-4
10-2
10a5
10-2
0
200
100
600
800
200
100
600
800
Epachs
Epochs
Residual projection on final train Jacobian
(d) Residual projection on initial test Jacobian
10P
10"
Rosidud caang
Residual energy
Froll jrggeenle Troils (naeteoll Inuily
10-1
nut t
10-1
10-2
2010
100
600
800
200
400
800
Epochs
Epochs
(e) Residual projection test Jacobian at 50 epochs (dip)*
(f) Residual projection on final test Jacobian
0.8
Brror
0.4
0.2
200
4010
600
800
Epochs
(g) Training and test error of experiment"
Figure 12: Experiments with 50% label corruption on CIFAR-10 data. *: we discuss these plots in Section
56

---

Under review as a conference paper at ICLR 2020
109
10a
Residual euergy
10
Resishal enargy
10"
10
hu Saguen
10-2
I Traliz
10-4
jugereili Prils
10-4
200
400
600
800
Epochs
Epochs
(a) Residual projection initial train Jacobian
(b) Residual projection final train Jacobian
The
Error
0.4
600
Epochs
(c) Training and test error of experiment
Figure 13: Experiments with 75% label corruption on CIFAR-10 data
10a
10a
Residual enengy
10-2
Resihnal energy
10-1
14th hh amypamy
10-2
M Mi Myy
10-2
10
Pullig
10-3
molf,
10
200
600
800
Epochs
Epochs
(a) Residual projection initial train Jacobian
(b) Residual projection final train Jacobian
0.8
Tlisk
0.6
Drror
0.4
0.2
Epochs
(c) Training and test error of experiment
Figure 14: Experiments with 100% label corruption on CIFAR-10 data
57

---

Under review as a conference paper at ICLR 2020
[Tx l2z
[T)lll
[
[
12
[ralzz
|ralzz
|rollez
0.31581
0.94882
0.0094479
0.31854
0.94791
0.0094092
Ttrvv final
0.47747
0.87865
0.00045241
0.47921
0.8777
0.00045344
Table 7: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 100% label corruption on CIFAR-10 data.
0.8
0.6
0.4
Swinlls
0.2
0.25
0.75
Label corruption
Figure 15: Test error vs. final projection of labels on nuisance subspace for CIFAR-10 experiments. See discussion of this plot in Section
C.3 EXPERIMENTS ON SUBSAMPLED 3-CLASS CIFAR-10
We created a new dataset of 3 classes by sub-sampling the original CIFAR-10 dataset. To do this, discarded all training and test data except those belonging to classes (airplane), 1 (automobile) and 2 (bird) and sampled 3333 examples of each classes for total of 9999 training images. We trained the neural network model described in Section with no output scaling using SGD and Adam. We applied standard data augmentation (random crop and flip) to increase generalization. Information subspace is spanned by the top 50 singular vectors.
Experiments without label corruption. First trained the network the sub-sampled 3-class dataset keeping the original labels. For the SGD experiments, we used initial learning rate 0.01 decreased by factor of 10 at epochs 260 and 360 for total of 400 epochs with batch size 128. For the Adam experiment learning rate 0.01 for 400 epochs was sufficient for good fit to the training data. We observed better Jacobian adaptation using Adam compared to SGD this dataset (0.98743 from Table 8 vs. 0.9969 from Table 9).
Experiments with label corruption. We corrupt the training labels by the corruption model de- scribed in C.2. We train the network on the corrupted dataset for 800 epochs with initial step size 0.01 and batch size 128. We decrease the learning rate by factor of at the following epochs: at 500 epochs for 25% corruption, at 700 epochs for 50% and 75% corruption and at 500 and 700 for 100% corruption.
58

---

Under review as a conference paper at ICLR 2020
10
10a
Residuad energy
Residnal onergy
10"1
10.
IPoliz
10-2
10-5
10
10-4
1010
200
300
100
100
2010
400
Epocks
Epochs
(a) Residual projection initial train Jacobian
(b) Residual projection 200 epochs train Jacobian
10a
10
Residual energy
10-2
Resisnal energy
10-1
10-2
Tull, Iraiz F
10-2
" nnn u4h,
10
10-3
Pall
10-1
100
200
300
400
Epocas
Epochs
(c) Residual projection final train Jacobian
(d) Residual projection on initial test Jacobian
Training
Truli
Tost
0.6
Mrtr-M2
Residial enang
rroli
myde-
10-2
0.4
Iro
0.2
11
200
300
100
Epochs
Epochs
(e) Residual projection on final test Jacobian
(1) Training and test error of experiment
Figure 16: Experiments on 3-class uncorrupted CIFAR-10 dataset
[1)
[1l()))
[1lx()))
[1lx()))
J/rrol
lyle,
Iyle,
Talle,
Iraley
Tralle,
Traley
frosh
0.7239
0.68991
0.0054426
0.88552
0.4646
0.0040958
init.
tracn
0.97266
0.23224
0.0026234
0.96849
0.24905
0.0030069
200epoche
trad
Fenal
0.98743
0.15804
0.0031639
0.97606
0.21749
0,0034312
J Test
0.73366
0.67951
0.010328
0.88827
0.45932
0,0077364
inêt
Teat
0.8974
0.44123
0.0027082
0.89772
0.44057
0.0029383
final
Table 8: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 3-class uncorrupted CIFAR-10 data.)
59

---

Under review as a conference paper at ICLR 2020
reli
10
10
Trull Milt-Dli
Resilual enarg
Residual maargy
10
Troliz [
10.2
Inoli
10-2
10-3
MLn u
10
10-4
10 5
100
200
300
400
100
200
300
400
Epochs
Epochs
(a) Residual projection on initial train Jacobian
(b) Residual projection on final train Jacobian
Figure 17: Experiments on 3-class uncorrupted CIFAR-10 data, trained with Adam
[
[
[
[
J
Tylle
Tylle
1Brl eg
Trolez
Trolez
Troles
Jrain 0.7025
0.71169
0.0053554
0.8135
0.5815
0.0044353
Irain
0.9969
0.078332
0.0030954
0.9907
0.1361
0.0030632
Table Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space on 3-class uncorrupted CIFAR-10 data, trained with Adam.
10a
10P
Fully
Residhal enengy
10-1
Residbal enargy
10-1
[ralf
10-2
M yl Yapull
10-2
10-4
10-3
2013
400
6000
800
2110
4010
8000
Epochs
Epochs
(a) Residual projection on initial train Jacobian
(b) Residual projection on final train Jacobian
Figure 18: Experiments with 25% label corruption 3-class CIFAR-10 data
[1)(2)
[
[ Troley
[Tw(ro)
Iylle
Ivlles
[ ey
Troley
Troles
Jrain 0.63965
0.76866
0.0047649
0.76602
0.64282
0.0043665
Train
0.90862
0.41763
0.0023974
0.9254
0.379
0.0021731
Table 10: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 25% label corruption on 3-class CIFAR-10 data.
60

---

Under review as a conference paper at ICLR 2020
10a
10
Resichal energy
10-1
Residual enengy
10-3
10:2
10-2
10-3
10-4
IralE [nyrte-1
10-1
10-4
Irall
2010
400
6000
800
Epochs
Epochs
(b) Residual projection on train Jacobian at 100 epochs (dip)
(a) Residual projection on initial train Jacobian
10a
10
Residual energ
Residnal caargy
rulp paze off, Ii
2
10
10-1
M
/
M Am
200
100
600
800
200
400
Epochs
Epochss
(c) Residual projection final train Jacobian
(d) Residual projection on initial test Jacobian
10"
Residhal energy
Residual energy
Trali Halteaal
My M s
w My Aylermmatt
10-1
10
2010
100
600
800
200
400
600
800
Epocks
Epochs
(e) Residual projection on test Jacobian at 100 epochs (dip)
(f) Residual projection on final test Jacobian
Training eroor Tet error
Error
0.4
0.2
200
400
600
800
Epochs
Training and test enror of experiment
Figure 19: Experiments with 50% label corruption on 3-class CIFAR-10 data
61

---

Under review as a conference paper at ICLR 2020
(2
[
[11x(r
[[
| |
Iulle,
lolle,
rrlle
rrlle,
rrole,
Jrram
0.58664
0.80985
0.0017197
0.64281
0.76602
0.0019814
inst
Jraa
0.61125
0.79144
0.0026809
0.65671
0.75415
0.0031267
dip
J Jirain
0.75143
0.65981
0.0018702
0.76311
0.64627
0.0012039
Final
Teest
0.7236
0.69021
0.012765
0.7594
0.65062
0.01235
init
Jest
dsp
0.81473
0.57984
0.009931
0,8322
0.55447
0,010515
J.
0.75362
0.65731
0.0033476
0.77225
0.63532
0.0021479
finot
Table 11: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 50% label corruption on 3-class CIFAR-IO data.
10
10a
Residual energy
Resibnal enargy
10"1
meap M whlh
10-2
10
10-3
10-3
10
200
400
600
Epochs
Epochs
(a) Residual projection initial train Jacobian
(b) Residual projection final train Jacobian
Figure 20: Experiments with 75% label corruption on 3-class CIFAR-10 data
[T)(()))
[Tw
JJ
lvle,
Tyle,
To
|role
Trol
0.58032
0.81439
0.0014306
0.68898
0.72478
0.0015956
Trasn fénal
0.64704
0.76246
0.0015808
0.78391
0.62088
0.00091715
Table 12: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 75% label corruption on 3-class CIFAR-10 data.
62

---

Under review as a conference paper at ICLR 2020
10
10"
Residual energy
10"
Residaal energy
10-1
yan Ihh Nully
10
10
10-3
relli Irale
10-1
0
2000
400
600
800
200
400
600
800
Epochs
Epochs
(a) Residual projection on initial train Jacobian
(b) Residual projection on final train Jacobian
Figure 21: Experiments with 100% label corruption on 3-class CIFAR-10 data
[
1aaille Twl.
[lz(ro)le
pprrole
Trolex
Trolz,
Tral
Jtrasn 0.614
0.78931
0.0024274
0.78608
0.61813
0.0022444
J Jtran 0.60094
0.7993
0.001845
0.7657
0.6432
0.00098981
final
Table 13: Depiction of the alignment the initial label/residual with the informa- tion/nuisance space using 100% label corruption on 3-class CIFAR-10 data.
C.4 EXPERIMENTS ON MNIST
The MNIST dataset contains handwritten digits in 10 classes divided into 60k training and 10k test images. To demonstrate our theoretical findings on dataset different from CIFAR-10 we repeat all experiments on MNIST under various levels of label corruption. We run SGD with batch size 128 on least-squares loss using the modified ResNet20 model from Section 4. In all of the following MNIST experiments the model output after the last layer has been scaled by 0.1. Information subspace is spanned by the top 50 singular vectors
Experiments without label corruption. We train the network on the original dataset 100 epochs with initial step size 0.1 decayed to 0.01 after 60 epochs.
Experiments with label corruption. We corrupt various portions of the labels in the training data by switching the labels to random incorrect class. We train the network on the corrupted dataset for 400 epochs with initial step size 0.1 decayed to 0.01 after 360 epochs.
[Tz [Tz leg
[1x(3))
Jyaulee
[1z(()))
[
Tyle,
Tyle,
Tvl
Truley
Traley
Trolles
J
Jrasn
0.43598
0.89996
0.028665
0.48168
0.87635
0.027921
Enit
Frusn
0.9946
10375
0.00066394
0.99321
0.11633
0.00076602
Final
J Jeest
0.43964
0.89817
0.071577
0.48474
0.87466
0.069724
Enit
J Final
0.99188
0.12716
0.0016387
0.99044
0.13796
0.0018745
Table 14: Depiction of the alignment the initial label/residual with the informa- tion/nuisance space using uncorrupted MNIST data.
63

---

Under review as a conference paper at ICLR 2020
10
10"
Frill Bgtelfi Pull BarteD
10-2
Reiiuul energy
Resical energe
10-2
10
10
10-3
10-4
100
20
10
60
Epochs
Epochs
(a) Residual projection initial train Jacobian
(b) Residual projection final train Jacobian
Bate If
tolls Bytto
Rosiduu emergy
Residhal energy
10-1
moliy
10-2
10-a
10-1
10-1
10-3
10-3
100
60
Epochs
Epochs
(c) Residual projection initial test Jacohian
(d) Residual projection on final test Jacobian
10P
10
Erron
10
10
20
Epochs
(c) Training and test error of experiment
Figure 22: Experiments on uncorrupted MNIST data
64

---

Under review as a conference paper at ICLR 2020
10
10a
10-
10"
Residuul emergy
Residaal energy
10.2
10-2
y M
10-3
Freifa
10'-8
Truley
10-1
Frali
10-4
[ayte-ll
10-3
0
100
200
300
400
100
200
300
400
Epochs
Epochs
(a) Residual projection on initial train Jacobian
(b) Residual projection on final train Jacobian
0.8
0.6
Droo
0.2
100
2010
300
400
Epochs
(c) Training and error of experiment
Figure 23: Experiments with 25% label corruption on MNIST data
[1l(w)), 2
[L((y))
J.yl
[11((r))
(r)r))
Jyrroll
Iylle
1 cg
Troles
rrlley
Troles
Jraan Eramm Fine!
0.38906
0.92121
0.02197
0.38586
0.92256
0,022028
0.94093
0.33861
0,0010507
0.9391
0.34365
0.0010331
Table 15: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 25% label corruption on MNIST data.
[1)
[1x(1))
JiMilez
[
[w((r))ee
Ivle,
Tyle,
Trole,
Trale,
Trolle,
J tras
0.34434
0.93885
0.013931
0.35864
0.93347
0.013967
Ereit
J Trasn
0.83136
0.55573
0.00081502
0.83235
0.55425
0.00081616
test
0.44458
0.89574
0.076224
0.45366
0.89117
0.076101
Jest
0.97007
0.24284
0.0043166
0.9705
0.24109
0.0043041
J Jestt
0.71536
0.69876
0.0018554
0.71632
0.69777
0.0018564
Table 16: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 50% label corruption MNIST data.
65

---

Under review as a conference paper at ICLR 2020
10
10
10a2
Residual enargy
Residnal onangy
10-1
10-2
Irelaa
10-2
Trily
Piyerelli
10-3
Troli
10-1
Inytril Ieali
0
100
200
300
400
100
200
300
400
Epochs
Epochs
(a) Residual projection on initial train Jacobian
(b) Residual projection on final train Jacobian
10"
10a
nussidual courgy
Rosidua eaang
mull Frolf Hegtrwily
10
100
200
300
400
200
300
100
Epochs
Epochs
(d) Residual projection Jacobian at 50 epochs (dip)
(c) Residual projection on initial test Jacobian
108
0.8
Traieing srro mone
Resiital euargy
0.6
Trali
0.1
0.2
0-
100
200
300
400
100
200
300
400
Epochs
Epochs
(e) Residual projection on final test Jacobian
(f) Training and test error of experiment
Figure 24: Experiments with 50% label corruption on MNIST data
[Tz(2)) leg
(1)ll
|
[Tz(ro))e
[[w(ro))e
Tyle,
Tyle,
T
Troles
Troley
Tnolles
J frain
0.31995
0.94744
0.0061168
0.32072
0.94718
0.0061618
knit.
Truin Final
0.56007
0.82844
0.00063427
0.55869
0.82938
0.00062509
Table 17: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 75% label corruption MNIST data.
66

---

Under review as a conference paper at ICLR 2020
10
10a
Residual enargy
10"
Resibnal enargy
10-1
10 2
Trulg
10
Trili
Poytr- Irale
10-3
10
100
200
300
400
Epochs
Epochs
(a) Residual projection initial train Jacobian
(b) Residual projection final train Jacobian
Error
0.4
300
Epochs
(c) Training and test error of experiment
Figure 25: Experiments with 75% label corruption on MNIST data
10a
10a
Residual enengy
10-2
Residnal energy
10-1
10-2
10-2
10
Frilly [ittrell Frali
10
10-1
300
Epochs
Epochs
(a) Residual projection initial train Jacobian
(b) Residual projection final train Jacobian
Drror
0.6
0.4
0.2
2010
Epochs
(c) Training and test error of experiment
Figure 26: Experiments with 100% label corruption on MNIST data
67

---

Under review as a conference paper at ICLR 2020
(1)
[
[
12
19le,
1912,
rralzz
rralz
|rollez
0.31793
0.94811
0.00501 14
0.34633
0.93811
0.0050949
Ttrav final
0.57769
0.81626
0.00060636
0.59174
0.80613
0.00062812
Table 18: Depiction of the alignment of the initial label/residual with the informa- tion/nuisance space using 100% label corruption on MNIST data.
0.8
0.6
0.4
0.2
ixtall final 1ble,
Test error
0
0
0.25
0.5
0.75
Label corruption
Figure 27: Test error vs. final projection of labels nuisance subspace for MNIST experiments
C.5 SINGULAR VALUE DECOMPOSITION OF THE JACOBIAN
The matrix representation of the Jacobian arising in the numerical experiments is in general very large and pose a computational challenge. In particular, the Jacobian matrix for ResNet20 model is 500k 270k: (or 540 GB memory with float32 entries, more than TB with float64) on the CIFAR-10 training data. Storing these matrices in memory for singular value decomposition is not feasible and therefore other methods are necessary to approximate the singular values and singular vectors.
The Lanczos algorithm Lanezos (1950) is an adaptation of power methods, which guarantees fast convergence to the largest eigenvalues of hermitian matrix. More importantly, it only requires matrix-vector products to estimate the top eigenvectors and therefore resolves the memory issues with large Jacobians. Using the ARPACK implementation of the implicitly restarted Lanezos method Lehoucq et al. (1998) it takes about hour on 64 cores to find the top 50 eigenvalues and eigenvectors of the 500A 500k symmetric matrix J for CIFAR-I0 training data. The same algorithm has been used to calculate the histogram of top 1000 singular values.
The required computation time for Lanczos method dominated by large Jacobian-vector products, which increases linearly with the number of calculated eigenvalues. Therefore it is necessary to depart from deterministic power iteration type algorithms and take a different approach. Stochastic Lanczos quadrature algorithm has been recently introduced to the machine learning community in Ghorbani et al. (2019a) and Papyan (2019a) 9a) to approximate the eigenvalue density of large neural network Hessians. Finding the exact spectral density might be difficult therefore first the problem is relaxed by approximating the spectrum convolved with Gaussian density of variance o² 10 As described in Ghorbani et al. (2019a), we draw k = 10 i.i.d. Gaussian random vectors and run 80 steps of the Lanczos algorithm starting from each random vector to estimate the parameters of the spectral density. We modified the algorithm by replacing Hessian- products by -vector products. Finally, we normalize the density and scale it by the dimension of the Jacobian output space.
68

---

Under review as a conference paper at ICLR 2020
D JACOBIAN ADAPTATION FOR LINEAR DATA
In this section, we will (non-rigorously) argue that Jacobian and its singular value spectrum indeed adapts to the data for simple linear datasets. Specifically, we will show that the very first gradient iteration from a random initialization is already powerful enough to encourage an approximately low-rank Jacobian.
Dataset: Let (2:4) i.d. (O, Ia) and fix 0 IR.. Fix labels y, 0 xz and the dataset (#;, Vs V:)
Neural net: Let Wo Rkxd iid. (0,1 1) and fix v e R with half +o and half -a entries. Set activation to be ReLU.
(Non-rigorous) Statement: With small initialization (a 0) and single large gradient step, Wi Wo - 7)VL(WW) has (properly scaled) Jacobian matrix with approximately rank 2d. Instead, at random initialization Wo. Jacobian has full rank (assuming kd >> n))
Specifically, at WT, we have
2dd+ (J(X, & Vd/n and o2a(J(X, 1.
(D.1)
where oj the ith largest singular value. In words, J(X, Wi) is approximately rank 2d when n 2 d.
This is in stark contrast to the properties of Jacobian at random initialization. For instance Li & Liang (2018); Zou et al. (2018); Oymak & Soltanolkotabi (2019) actually show that Jacobian is well conditioned with minimum singular value lower bounded by the minimum separation between the samples (implying full rank of n2). Such separation (independent of n) holds for Gaussian data even when n polynomially larger than via standard concentration packing bounds (also see Oymak & Soltanolkotabi (2019); Li & Liang (2018)). Hence, as further formalized below, we argue that even single step of gradient descent can lead to an approximately low-rank Jacobian.
D.1 APPROACH
Fixing weights of Wo. study the gradient of the random data. Let w, be rth row of Wo. Fixing hidden node r, let a = æ; x w, 2 0 (i.e. the rth node is active) and else. The gradient of the node at Wo is given by
VC(W) (f{x,, Wo) -y:)x'
Sw,
If initialization small enough (a 0), we can approximate f(x,, Wo) y4 y hence we study
VL(W)
ye
Own
n
We will show that gradients of each row are 2o0 in expectation. Decompose a sample æ ~ ~N Ia)
g
lwrlle
where g is standard normal vector over the orthogonal complement of vector w, and g (( 1).
Denoting label associated to æ by y, consequently, we find
ya' ] = [[y
- ww 2 0]P(2= w, 2 20)
(D.2)
E[(g
+ (gw, 0 0] 1rrles
wr
(D.3)
2
Elgg" "00 + [[9g² g 2 w.
(D.4)
2
0
(D.5)
2
Hence
VL(W)
[
v,0/2.
Owk
69

---

Under review as a conference paper at ICLR 2020
This implies that, in population (n oo), gradient vector has extremely simple rank-one form:
Ex(vL(W) w: ==]==200'
Standard results on non-asymptotic statistics then yield that with exponentially high-probability (i.e. 1 cxp(-cn)),
VC(W)
Ex(
Ile, & dd/n
Swk
Owy
As long as k $ poly(n), union bounding over all rows, we find the spectral norm bound
(C(()
Wi -EX(V[(W) wolll s o ko/k//n
On the other hand, Ex wo is rank with nonzero singular value ov kk/2. Consequently, a large gradient step will ensure that
W Wo (VL(W) Wo
approximately rank one as well. Specifically, set the rank one matrix
W1 = Ex ==x()](((W) wo..
Then the tail of the spectrum is at most W[ W1 d/nl W1l (i.e. vd/n large as the spectral norm).
Finally, need to move from showing low-rankness of the weight matrix low-rankness of Jacobian. Define the Jacobians associated with data at W1 and W1 by
J Wi) diag( v)o' (WWWX")) + X". J J= Wi) diag(v) (WiX²) x
The Jacobian associated with J is exactly rank 2d since matrix (o)g())'((W>))))
has exactly two distinct rows and kronecker producting with X will yield d rank for each (adding to 2d). Since X is well-conditioned with high probability (as is <(, 1) and fat with 2 d), top 2d singular values and (2) are strictly positive with lower bound independent of and a (after scaling by | X|).
Finally, using smoothness of ø' (which excludes ReLU but includes smoother versions of ReLU such as softplus), using Jacobian perturbation bound (6.31), we have (after scaling by 1/a X
J J & WW Wil vd/n.
Together, this leads to the desired conclusion (D.1) since singular value perturbation inequality yields (2)+1(J) s | -J s vd/n (as 0za+1 (J)) 0).
70


Reviews:
[{"review_id": "rkgb8JyCKr", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "The authors use the empirically supported assumption of the low-rank nature of the neural network Jacobian to provide new elements of data-dependent optimization and generalization theory. By modelling the data as a low-rank object itself, they analytically study the evolution of the train and test errors. The paper divides the space of weights and biases into the “information” and “nuisance” subspaces, spanned by the top largest and the remaining singular vectors of the Jacobian respectively. They use this division and its alignment with the low-rank structure of the data to talk about convergence speed. Finally, they provide numerical experiments to back their claims.\n\nI enjoyed the paper, however, there were many points where I was unclear on the precise nature of the assumptions used / the strength of the results.\n\nDisclaimer: I didn’t manage to read through the proofs in the appendix and cannot therefore vouch for its correctness.\n\n-- Point 1 --\nLeveraging the data structure\n\nI am unclear on how exactly you were modelling the structure of the data. From your proofs, it seems that you have been dealing with the matrix X comprising the concatenated flatted vectors of the raw input features (e.g. pixels) of the input data [x1,x2,...,x_datasetsize]^T. In particular, the only place where I see data explicitly enter is in Definition 2.1, where you look at the X X^T and fi’(w X) fi’(w X)^T.\n\nIf the data is linearly separable in the raw input space on its own, then I see that the matrix X X^T will be low-rank (related to the number of classes). I also see your point about the connection of the y to the relevant (semantic) clusters. The same argument could by applied to fi’(w X) fi’(w X)^T -- provided that the features produced are again linearly separable, we will observe this object to have a low (number of classes - 1) rank. \n\nWhat is unclear to me is whether these assumptions are warranted. I understand that some simple datasets, e.g. MNIST, are essentially linearly separable in the raw pixels, and therefore the X X^T indeed is low rank. However, I doubt anything like that is true for big datasets, such as ImageNet. For deep networks that are used on these big datasets, such a modelling assumptions would likely not be true. I wonder how this relates to your results, since the low-rank nature of the Hessian is observed even for those networks, which is in turn related to the low rank nature of the Jacobian.\n\n-- Point 2 --\nData implicitly present in the Jacobian tensor.\n\nI wonder how you modelled the Jacobian tensor that you started using on page 3. Since the Jacobian -- the derivative of the output logits with respect to the weights, has to be evaluated at a particular input X, the assumptions you make on the data are in turn having an effect on the Jacobian, and vice versa.\n\nI am unclear on exactly what assumptions you make about the object, and whether you are actually saying that its low rank structure comes from the data, is empirical observed and therefore assumed, or due to the network regardless of the data.\n\nI recently saw a new arXiv submission that seems to be looking into this on real networks: https://arxiv.org/pdf/1910.05929.pdf Their model explicitly assumes that logit gradients cluster in the weight space in a particular way.\n\n-- Point 3 --\nSquare loss vs softmax\n\nYou are using the square loss |f(X) - y|^2 throughout your work. Many of the empirical low-rank observations of the Hessian (related to the JJ^T) are performed on real networks with the cross-entropy loss. While the Hessian with the square loss is of the form JJ^T + terms, the softmax in the cross-entropy loss introduces an additional cross-term (let us call it P for now), which in turn makes it JP(PJ)^T + terms. Do you know how this relates to your results?\n\nMore generally, does the square loss you use make the results significantly different from what we would get for a softmax?\n\n-- Point 4 --\nNeural Tangent Kernel (NTK) -- assumptions\n\nUnder the NTK assumption, you still need to model the derivatives of each logit with respect to each weight on each input in order to obtain the Jacobian matrix and in turn JJ^T. I am therefore very confused by “Based on our simulations the M-NTK indeed haslow-rank structure with a few large eigenvalues and many smaller ones. “ on page 5. What assumptions exactly do you use in your model?\n\n-- Point 5 --\nNeural Tangent Kernel (NTK) -- validity\n\nBy assuming the NTK holding, do you limit the validity of your results? I think it is believed that NTK might not, generally speaking, be enough to capture the complexity of DNNs, and therefore assuming it might limit the range of applicability of any results derived assuming it.\n\n-- Conclusion --\nIn general, my points of confusion often stem from being unsure as to what parts of the argument were assumed and based on what empirical / theoretical evidence, and what parts were generically true. While the paper seems interesting, I am not sure what its novel contribution is and how broad the claims made actually are in their applicability.\n\nAppendix: I was not able to judge the proofs in the appendix.\n", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "review_assessment:_thoroughness_in_paper_reading": "I made a quick assessment of this paper.", "review_assessment:_checking_correctness_of_experiments": "I assessed the sensibility of the experiments.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "Syer94DpFS", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "Note: The template used in this paper is of ICLR 2019, not ICLR 2020.\n\nThis paper identifies the information space and nuisance space by thresholding the singular values of the network's jacobian and shows that generally the residuals projected to the information space can be effectively optimized to zero, thus leading to efficient optimization and good generalization.\n\nI believe this paper should be rejected because its motivation and technical framework are not novel enough in that 1) the motivation of decomposition along gradient matrix is already well-founded by a series of paper related to neural tangent kernel 2) the techniques used here also fall in a similar framework. The following is the detailed comments.\n\nFirst, this paper's motivation is to employ the singular decomposition of the jacobian. Actually, the motivation is essentially the same as (Arora et al. 2019) and many other works. The neural tangent kernel matrix defined there is exactly the inner product of two jacobian (or gradient) described here and to employ the singular decomposition is actually corresponding to employing the eigendecomposition of the neural tangent kernel, which appears first in (Arora et al. 2019). The logic behind dividing the singular space into information space and nuisance space is that gradient descending along different directions has different speeds, determined by the eigenvalues.\n\nThe framework presented in this paper is based on the assumption that the parameters will not be far away from the starting point. Such an assumption further guarantees the trajectory won't be far away from the linearized trajectory, leading to an optimization guarantee. This approach is widely used by many works, and well-known for a considerably long time. Also, the paper's proof is complicated and lengthy which hinders its clarity.\n\nTo summarize, this paper definitely contains some rigorous analysis which I appreciate, but it doesn't provide new insights into optimization and generalization for deep nets. The motivation and logic behind are not novel enough, the main theorem neither. So I suggest a weak rejection to this paper in its current form.\n\n[1] Arora, Sanjeev, et al. \"Fine-grained analysis of optimization and generalization for over-parameterized two-layer neural networks.\" arXiv preprint arXiv:1901.08584 (2019).\n\n****** Post-rebuttal response ******\n\nThanks to the authors' response. I have read the rebuttal and unfortunately, I feel it is still not strong enough to  justify this paper's novelty issue and I will keep my rating unchanged.", "extra_scores": {"experience_assessment": "I have read many papers in this area.", "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.", "review_assessment:_checking_correctness_of_derivations_and_theory": "I assessed the sensibility of the derivations and theory."}, "extra_text": {}}, {"review_id": "BygXbD0n5B", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 new (data dependent) generalization guarantees based on the Jacobian of the model. The authors suggest that if the desired outputs lie into the information space (the subspace spanned by the largest eigenvectors of the NTK), the model will train faster and better generalization will be achieved.\n\nThe faster convergence of the model in the information space is not surprising and was observed by Jacot 2018. The authors make improvements over this result:\n - They present a generalization result, whereas Jacot 2018 focuses only on the convergence on the training set. It is also formulated as a classification problem instead of a regression one.\n- It doesn’t need JJ^t to stay constant during the training.\n\nHowever, the setting considered by the authors to derive their theoretical contributions is too restrictive. The model exposed in section 1 is extremely simplified, as only W can be learned and V is fixed. As a result, the model is in essence completely linear: the goal is, for a given V, to learn a “good” hidden layer using a linear model and the loss L : h -> ||V phi(h) - y ||. \n\nThe experiment on cifar10 is interesting, especially the section regarding label corruption. A more extensive empirical investigation is this direction would be of great value. The results uncovered are not surprising and predicted by Jacot 2018 (granted, it is interesting to see that the result holds for finite width and non-continuous gradient flow).\n\nI think this paper in its current state is not good enough for two reasons. First, the major contribution is a generalization bound that is derived for a model that is too simple (even simpler than a standard one hidden layer network). Beside this result, the rest of the paper is  incremental, as the link between convergence rate and the projection of the desired outputs on the information space was already made in Jacot 2018\n\nNB: I did not check the derivation of the results in annexes.\n\nNitpick:\n\nPage 2: “our results may shed light on the generalization capabilities of networks initialized with pre-trained models commonly used in meta/transfer learning” seems like a bit of a stretch. While I agree that theories that requires random initialization won’t work for transfer learning, the results presented by the authors don’t really leverage anything particular about pre-training.\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": {}}]

Author rebuttal:

Meta-review: This submission investigates the properties of the Jacobian matrix in deep learning setup. Specifically, it splits the spectrum of the matrix into information (large singulars) and ``nuisance (small singulars) spaces. The paper shows that over the information space learning is fast and achieves zero loss. It also shows that generalization relates to how well labels are aligned with the information space.

While the submission certainly has encouraging analysis/results, reviewers find these contributions limited and it is not clear how some of the claims in the paper can be extended to more general settings. For example, while the authors claim that low-rank structure is suggested by theory, the support of this claim is limited to a case study on mixture of Gaussians. In addition, the provided analysis only studies two-layer networks. As elaborated by R4, extending these arguments to more than two layers does not seem straighforward using the tools used in the submission. While all reviewers appreciated author's response, they were not convinced and maintained their original ratings.

Decision: Reject