Principal Components Bias in Deep Neural Networks
Authors: Guy Hacohen
Daphna Weinshall
Venue: NeurIPS 2021 Submitted (2021)
Keywords: Neural nework
neural networks
deep
TP-agreement
learning order
spectral bias
simplicity bias
easy examples
hard examples
principal components
machine learning
ML
linear networks
over parametrized
over-parametrized

Abstract: Recent work suggests that convolutional neural networks of different architectures learn to classify images in the same order. To understand this phenomenon, we revisit the over-parametrized deep linear network model. Our asymptotic analysis, assuming that the hidden layers are wide enough, reveals that the convergence rate of this model's parameters is exponentially faster along directions corresponding to the larger principal components of the data, at a rate governed by the singular values. We term this convergence pattern the Principal Components bias (PC-bias). We show how the PC-bias streamlines the order of learning of both linear and non-linear networks, more prominently at earlier stages of learning. We then compare our results to the spectral bias, showing that both biases can be seen independently, and affect the order of learning in different ways. Finally, we discuss how the PC-bias may explain some benefits of early stopping and its connection to PCA, and why deep networks converge more slowly when given random labels.

Principal Components Bias in Deep Neural Networks
Anonymous Author(s) Affiliation Address email
Abstract
Recent work suggests that convolutional neural networks of different architectures learn to classify images in the same order. To understand this phenomenon, we revisit the over-parametrized deep linear network model. Our asymptotic analysis, assuming that the hidden layers are wide enough, reveals that the convergence rate this model's parameters is exponentially faster along directions corresponding the larger principal components of the data, rate governed by the singular values. We term this convergence pattern the Principal Components bias (PC-bias). We show how the PC-bias streamlines the order of learning of both linear and non- linear networks, more prominently at earlier stages of learning. We then compare our results the spectral bias, showing that both biases can be seen independently, and affect the order of learning in different ways. Finally, we discuss how the PC-bias may explain some benefits of early stopping and its connection to PCA, and why deep networks converge more slowly when given random labels.
3
5
7
10
11
12
13
Introduction
14
15
The dynamics of learning deep neural networks is an intriguing subject, not yet sufficiently understood. Diverse empirical data seems to support the hypothesis that neural networks start by learning simple model, which then gains complexity as learning proceeds (Gunasekar al. 2018
18
17
18
Soudry et (018 Hu et al. Nakkiran et al. [019 Gissin et al. 2019 Heckel & Soltanol
19
2019 Ulyanov et al. 22018] Perez et al. (0188) This phenomenon is sometimes called simplicity
bias DDingle et al.) 2018 Shah et al. 2020).
21
Recent work additionally shows that neural networks learn the training examples of natural datasets in a consistent order, and further impose a consistent order on the test set (Hacohen et al. 2020 Pliushch et al., (02T). Below we call this effect Learning Order Constancy (LOC). Currently, the characteristics of visual data, which may explain this consistently imposed order, remain unclear. Surprisingly, this universal order persists despite the variability introduced into the training of different models and architectures.
22
23
24
25
26
To understand this phenomenon, we start by analyzing the deep linear network model (Saxe et al. 2013 2019), defined by the concatenation of linear operators. While not a universal approximator, nevertheless trained by minimizing non-convex objective function with a multitude of minima. The investigation of such networks is often employed to shed light on the learning dynamics when
28
29
30
31
complex geometric landscapes are explored by GD (Fukumizu 1998 Arora al. 2018
32 In Section 2] we prove that the convergence of the weights of deep linear networks is governed term PC-bias. These asymptotic
by the eigendecomposition of the raw data in phenomenon 34 results, valid when the hidden layers are wide enough, can be seen as an extension of the known behavior of the single-layer convex linear model (Le Cun et al. 1991). Our work is closely related to
36 Saxe et al. 2013 2019), where the deep linear model's dynamics is analyzed as function of the
input and input-output statistics. Importantly, the analysis in (Saxe et al. 2013 2019
Arora et al.
Submitted to 35th Conference on Neural Information Processing Systems (NeurIPS 2021). Do not distribute.

---

38
incorporates the simplifying assumption that the data's 's singular values are identical (whitened 39 data), an assumption which unfortunately obscures the main result of our analysis the direct dependence of convergence rate on the singular values of the data.
2018)
40
In Section 3
empirically show that this pattern of convergence is indeed observed in deep linear networks, validating the plausibility of our assumptions. We continue by showing that the LOC-effect in deep linear network is determined solely by their PC-bias. We prove similar (weaker) result for the non-linear two-layer ReLU model introduced by Allen-Zhu et al. (2018), where this model is presented as certain extension of NTK Qacot et al.) 2020). In this framework, convergence fastest along the largest kernel's principal components, result related to the Spectral bias discussed below.
42
43
44
45
48
In Section 4 we extend the study empirically to non-lineat networks, and investigate the relation between the PC-bias and the 1.0C-effect in general deep networks. We first show that the order by which examples are learned by linear networks is highly correlated with the order induced by prevalent deep CNN models. We then show directly that the learning order of non-linear CNN models affected by the principal decomposition of the data. Moreover, the LOC-effect diminishes when data is whitened, indicating tight connection between the PC-bias and the LOC-effect.
48
50
51
52
Our results are reminiscent of another phenomenon, termed Spectral bias (Rahaman et al. 2019 53
54
Cao et al. 2019), which associates the learning dynamics of neural networks with the Fourier decomposition of functions in the hypothesis space. [Rahaman et al. (2019) empirically demonstrated that the complexity of classifiers learned by ReLU networks increases with time. Basri et al. (2019) 2020) showed theoretically, by way of analyzing elementary neural network models, that these models first fit the data with low-frequency functions, and gradually add higher frequencies to improve the fit.
56
58
59
Nevertheless, the spectral bias and PC-bias are inherently different. Indeed, the eigendecomposition of raw images is closely related to the Fourier analysis of images as long as the statistical properties of images are (approximately) 2003]. Still, the PC-bias is guided by spectral properties of the raw data and is additionally blind to class labels. On the other hand, the spectral bias, as well as the related frequency bias that has been shown to characterize NTK models (Basri et al.] 2020), are all guided by spectral properties of the learned hypothesis, which strongly depends on label assignment.
60
61
conslation-invariaan (Simoncelli & Olshausen, 2001 Torralba & Oliva
62
64
85
66 In Section 4.3 we investigate the relation between the PC-bias, spectral bias, and the L.C-efffect. We find that the LOC-effect is very robust: (i) when we neutralize the spectral bias by using low complexity models such as deep linear networks, the effect is still observed; (ii) when we neutralize the PC-bias by using whitened data, the LOC-effect persists. We hypothesize that at the beginning of learning, the learning dynamics of neural models is controlled by the eigendecomposition of the raw
67
68
70
71 data. As learning proceeds, control of the dynamics slowly shifts to other factors.
72 The Pi-bias has implications beyond the efC-effect, as expanded in Section and Suppl. $A
73 1. Early stopping. It is often observed that when training deep networks with real data, the highest
74 generalization accuracy is obtained before convergence. Consequently, early stopping is often
75 prescribed to improve generalization. Following the commonly used assumption that in natural
76 images the lowest principal components correspond noise (Torralba & Oliva 2003), our results
77 predict the benefits of early stopping, and relate it to PCA. In Section 5 we investigate the relevance
78 of this conclusion to real non-linear networks (see, e.g., Basri et (2019): Li et al. (2020) for
79
complementary accounts).
80
2. Slower convergence with random labels. Zhang et al. (2016) showed that neural networks
81
can learn any label assignment. However, training with random label assignments is known to converge slower compared to training with the original labels (Krueger et al. 2017]. We report similar phenomenon when training deep linear networks. Our analysis shows that when the principal eigenvectors are correlated with class identity, as is often the case in natural images, the loss decreases faster when given true label assignments as against random label assignments. In Section we investigate this hypothesis empirically in linear and non-linear networks.
83
84
85
86
87
3. Weight initialization. Different weight initialization schemes have been proposed to stabilize the learning and minimize the hazard of "exploding gradients" (e.g.. |.oort & Bengio 2010 He et al.) 2015). Our analysis (see Suppl. ŞAA identifies a related variant, which eliminates the hazard when all the hidden layers are roughly of equal width. In the deep linear model, it can be proven that the proposed normalization variant in a sense minimizes repeated gradient amplification.
88
89
91

---

92 2 Theoretical analysis
Notations. Let X { v=) denote the training data, where IRY denotes the i-th data 94 point and y E 10 its corresponding label. Let nu m, denote the centroid (mean) of class with mx]" Finally, let X and denote the matrices whose 7th column 96 n, points, and M = [m_... ..m.....]]'..
96 x; and y: respectively. Σxx XXT and Σyx YX" denote the covariance matrix of X 97 and covariaove of X and Y respectively. We note that Σxx captures the structure of the data irrespective of class identity.
96
99
Definition (Principal coordinate system). The coordinate system obtained by rotating the data in R by an orthonormal matrix U where SV =(Exx)=UUDUU) Now Σxx = D, diagnoal matrix whose elements are the singular values of X arranged in decreasing order di 2 d2 .... dg 2 0. Definition 2 (Compact representation). Let f()) denote deep linear network. Then f()
100
101
T Wi)e Wx, where W E RRXx is called the compact representation of the network.
103
104
Definition 3 (Error matrix). For a deep linear network whose compact representation W, the error matrix is Er WExx - Σyx. In the principal coordinate system, Er WD W M.
Assumptions. Our analysis assumes that the learning rate μ is infinitesimal, and therefore terms of size O(r²) can be neglected. We further assume that the width of the hidden layers lies in [nn, In Mb). where m + oo denotes very large number and M, is fixed. Thus terms of size O m 108
107
can also be neglected. In Fig. [ Te show the plausibility of these assumptions, where the predicted dynamics is seen throughout the training of deep linear networks, even for small values of m.
109
110
2.1
The dynamics of deep peerparamettrzed linear networks
112
Consider deep linear network with I. layers, and let
I(X) = WX YII
W= = II Wi, W Rm I=
W
115 Above my denotes the number of neurons in layer I, where mi = q and m.. = K.
114 Theorem 1. In each time point the compact matrix representation W obeys the following dynamics,
115 when using the notation Er defined in Def. 3
W W 1 Σ Ai - BJ 0(p2)
116
Above μs denotes the learning rate. Af and B7 are called gradient scale matrices, and are defined as
1+11
1+1
A
= (II w; WI w))
E Kxk
B B II W;) "(" j=-1 J=11
II w;)
Rax9 (3)
J=L
117
The proof can be found in Suppl.
Gradient scale matrices. Some statistical properties of such matrices established in Suppl. SA Note that when the number of hidden layers is 0 (L = 1), both gradient scale matrices reduce to the identity matrix and the dynamics in (2) reduced the following known result (e.g., Le Cun et al.)
119
120
121
W++1 = W - =EEr.. Recall, however, that the focus of this paper is the pver-parameterized linarr model with 1, in which the loss is not convex. Since the difference between the convex linear model and the over- parametrized deep model boils down to these matrices, our convergence analysis henceforth focuses on the dynamics of the gradient scale matrices.
1991]:
122
123
124
125
In accordance, we analyze the evolution of the gradient scale matrices as learning proceeds. Let min (MR1,-.,,TL-) denote the size of the smallest hidden layer. Initially for O, all weight matrices W are assumed to be initialized by sampling from a distribution with mean 0 and variance
127
of = O( The specific normalization factor, alluded to in O m ), is a variant of the Glorot
128
129
initialization. Details and justification can be found in Suppl. $A.1
130
At time s, let (m)) and Bj (mn) denote sequence of random gradient scale matrices, corresponding
to networks whose smallest hidden layer has m neurons. From Suppl. $A we deduce that:
3

---

Theorem 2. Using 2x to denole convergence in probability I - oc, and Vs, L:
132
(m) P var(B (m)) O m
A (m) 2 I, (m)) 0
133
Proof. Proof by induction on 8. Initially when 8 = 0, the claim follows from Thm
4 Hnd Corr 5.1
The induction step validity follows from Thm and Thm T (see Suppl. $A.2).
134
135
The detailed proof shows that the relevant constants are amplified with While they remain moderate and m is sufficiently large, (m) Rs I and A (m) A / Vl. In this case, the dynamics of the over- parameterized model is identical the dynamics of the convex linear model, W W .EEr..
136
137
138
Convergence rate. In A.2 we show that the convergence of By (m) to I is governed to some extent by O K while the convergence of A (m) is governed by O ( ())) Recall that while m + oc, q is the dimension of the data space which is fixed in advance and can be fairly large, while K is the number of classes which is fixed and quite small. Typically, K < q. Thus we expect the right gradient scale matrices B1 (mn to remain approximately much longer than the left matrices Af (m).
139
141
142
143
Empirical validation. Since the results above are asymptotic, and to envision the difference between resort to simulations whose results shown in These empirical results, recounting linear networks with 4 hidden layers of width 1024, clearly show that during significant part of the training both gradient scale matrices remain approximately
convergence governed by O (x) vs. O (%),,
145
Fig. |
147
T. The difference between the convergence rate of Bf and A is seen later on, when AAf starts to increase shortly before convergence, while A BB remains essentially 0 throughout.
ning 4]
urd
100
goggtto col mm
Of--iaa-0 A!
(a) Diagonal layer 3 (b) Off-diagonal layer
Epoch
Spoch
(a) Linear Network
(b) ReLU Network
Figure 1: The dynamics of Aj and B when training 10 5-layered linear networks the small-mammals dataset. (a) Mcan distance of the diagonal elements of Aj and Bi from of and 5 (as defined in Thm B A..I). (b) Mean value of the off-diagonal elements of AT and Bf. The networks reach maximal test accuracy at epoch s 100, before the divergence of Aţ. All layers behave similarly.
Figure 2: Empirical confirmation of the thcoretical re- sults reported below, showing the std of w, over 10 in- dependently trained networks as function of the epoch, for 6 specific principal components (identified in the leg- end). Left: two-layer linear network. Right: two-layer non-linear network with ReLU activation.
2.2
Weight evolution
150
K < 9 entails that Bf(m) remains approximately equal to much longer than Af This is substantiated by the simulation results in Fig. Consequently, while earlier on it is safe to assume that both A
152
and Bi x I, as learning proceeds only Bf As I safe to assume.
153
With this in mind, we obtain expressions for the evolution of W separately for earlier and later in learning. We first shift to the principal coordinate system defined in Def[I] In this system we can analyze each column of W separately, where w and m, denote the respective columns of W and
154
155
156
M. At the beginning of learning when both Ai R I and B z 1 (see BB.3 for detailed derivation):
w wi+h = uf + - (2,) mi
\ = - HdjL
(4)
dz
158
i reminiscent of the well understood dynamics training the convex one layer linear model. composed of two additive terms, revealing two parallel and independent processes:
160
The dependence on random initialization tends to exponentially with decline rate Aj-
181
2. The final value is the sum of a geometrical series with a common ratio Ay-
162
In either case, convergence is fastest for the largest singular eigenvalue, or the first column of W. and slowest for the smallest singular value. This behavior visualized Fig. [2a] Importantly, the rate of convergence depends the singular value dy. the number of layers L, and the learning rate p.
163

---

185
In later stages of learning, when we can only assume that Bj = I, the dynamic becomes:
a E II (1-nd, AM my
II (T- Ad)o P
(5)
1=1+1
186
where A = Ei=1 A7. The proof is provided in BB.
Although the dynamics now depends on matrices A as well, it is still the case that the convergence of each column is governed by its singular value d,. This suggests that while the PC-bias is more pronounced in earlier stages of learning, its effect persists throughout.
167
168
189
170
The analysis above is extended to a simple non-linear ReI.U model (cf. Arora et al. 2019) as detailed in (B.2] with qualitatively similar results (albeit under unrealistic assumptions). Empirical results, shown in Fig. 2b. indicate that the results are indicative beyond the assumed circumstances.
172
3 PC-bias: empirical study
173
In this section, first analyze deep linear networks, showing that the convergence rate is indeed governed by the principal singular values of the data, which demonstrates the plausibility of the assumptions made in Section We continue by extending the scope of the investigation non-linear neural networks, finding there evidence for the PC-bias mostly in the earlier stages of learning.
175
176
177
178
3.1 Methodology
We say that linear network is L-layered when it has I, - hidden fully connected (FC) layers (without convolutional layers). our empirical study we relaxed some assumptions of the theoretical study, in order to increase the resemblance of the trained networks to networks in common use. Specifically, we changed the initialization to the commonly used Glorot initialization, replaced the Le loss with the cross-entropy loss, and employed SGD instead of the deterministic GD. Notably, the original assumptions yielded similar results. The results presented summarize experiments with networks of equal width across all hidden layers, specifically the moderate value of m 1024, keeping in mind that we test the relevance of asymptotic results for m - cc. Using a different width for each layer yielded similar qualitative results. Details regarding the soper-parameters, architectures, and datasets can be found in D..I $D. and respecccci....
180
182
184
186
188
189
3.2
PC-bias in deep linear networks
190
In this section, we train L-layered linear networks, then compute their compact representations W rotated to align with the canonical coordinate system (Def. TT. Note that each row w, in W essentially defines the one-vs-all separating hyper-pland corresponding to class
191
192
193
To examine both the variability between models and their convergence rate, inspect w, at different time points during learning. The rate of convergence can be measured directly, by observing the changes in the weights of each element in w,, These weight values] should be compared with the optimal values in each row of Wopt = (Xxx) The variability between models is measured by calculating the standard deviation (std) of each w, across N models.
194
195
196
197
198
We begin with linear networks. We trained 10 5-layered FC linear networks, and 10 linear st- VGG convolutional networks. When analyzing the compact representation of such networks observe similar behavior weights corresponding to larger principal components converge faster to the optimal value, and their variability across models converges faster 0 (Figs. [3 3b). Thus, while the theoretical results are asymptotic, PC-bias is empirically seen throughout the entire learning process of deep linear networks.
200
201
202
203
204 W Whitened data. The PC-bias is neutralized when the data is whitened, at which point Σxx is the scaled identity matrix. In Fig. 3c plot the results of the same experimental protocol while using ZCA-whitena whitened dataset. As predicted, the networks no longer show any bias towards any principal direction. Weights in all directions are scaled similarly, and the std over all models is the same in
206
208
each epoch, irrespective of the principal direction. (Additional experiments show that this is not an artifact of the lack of uniqueness when deriving the principal components of white signal).
We note that the weights tend to start larger for smaller principal components, be seen in Fig, 3a left.
5

---

Componee
Companent
Clrl porerss
Compenert
Compenert
Contoraar
(a) 5 5ayeeed lincar network
(b)
Linear convolutional network
Conprren
Componer
Component
Componere
Comboneen
(c) 5-Layered linear network, whitened data
(d) Non linear convolutional network
Figure 3: Convergence of the compact representation along the principal directions in different epochs. The value the Xaaiss corresponds to the index of a principal eigenvalue, from the most significant the least significant. (a) 10 5-layered linear networks trained on the cats and dogs dataset. 3 plots are provided, corresponding to snapshots taken at different stages of learning: the beginning (epoch O, left), intermediate stage (middle), and close convergence (right). Bottom panel: average distance of the weights in W; from the optimal linear classifier: top panel: respective std. (b) Similarly, for 10 linear st- VGG convolutional networks, trained on CIFAR-10. (c) Similarly. for 10 5-layered linear networks, trained on the cats and dogs dataset. with ZCA- whitening- (d) Similarly, for 10 non-linear st- st-GG networks trained on the cats and dogs dataset. Here the distance to the optimal solution is not well defined and we therefore only show the std.
210
3.3
PC-bias in general CNNs
211
In this section, we investigate the manifestation of the PC-bias in non-linear deep convolutional networks. As we cannot directly track the learning dynamics separately in each principal direction of non-linear networks, we adopt two different evaluation mechanisms:
212
213
L Linear approximation. We considered several linear approximations, but since all of them showed the same qualitative behavior, we report results with the simplest one. Specifically, to obtain a linear approximation of non-linear network, without max-pooling or batch notch-normalization layers, follow the definition of the compact representation from Section 2 while ignoring any non-linear activation. We then align this matrix with the canonical coordinate system (Def. []. and observe the evolution of the weights and their std across models along the principal directions during learning.
215
217
219
Note that now the networks do not converge the same compact representation, which is not unique. Nevertheless, we see that the PC-bias governs the weight dynamics to a noticeable extent.
221
More specifically, in these networks large fraction of the lowest principal components hardly changes during learning, as good as being ignored. Nevertheless, the PC-bias affects the higher principal components, most notably at the beginning of training (see Fig, 3d). Thus weights corresponding to higher principal components converge faster, and the std across models of such weights decreases faster for higher principal components.
223
225
227
Projection to higher PC's. We created modified test-set, by project- ing each test example on the span of the first P principal components. This is equivalent redueing the dimensionality of the test set to P us-
228
Accuracy
229
0.4
ing PCA. We trained an ensemble of N=100 st-V stG networks on the
231
original small mammals training set, then evaluated these networks dur- ing training on 4 versions of the test-set, reduced to P=1,10, 1000 dimensions respectively. Mean accuracy is plotted in Fig. 4 Similar
02
50
100
150
Epoch
233
Figure 4: Mean accuracy of 10 st- VGG networks evaluated on test data projected to dimen- sionality (1. 10, 100, 1000).
results are obtained when training VGG- 19 networks on CIFAR-10,
235
see
Taking a closer look at Fig. we see that when evaluated on lower 236
237
dimensionality dast- (P=I,10). the networks' accuracy peaks after
238
a few epochs, at which point performance starts to decrease. This result suggests that the networks
239
rely more heavily on these dimensions in the earlier phases of learning, and then continue to learn other things. In contrast, when evaluated on higher dimensionality test-data (P=100,1000) accuracy continues to rise, longer so for larger P. This suggests that significant learning of the additional dimensions continues in later stages of the learning.
241

---

4
PC-bias: Learning Order Constancy
243
244
In this section, we show that the PC-bias is significantly correlated with the learning order of deep neural networks, and can therefore partially account for the LOC-effect described in Section [
246
Following Hacohen et al. (2020), we measure the "speed of learning" of each example by computing
247
its uccessibility score. This score is given per example, and characterizes how fast an ensemble of
248
N networks learns it. Formally, accessibilily((a = E [ (f = y()))). where f (x:) denotes the outcome of the i-th network trained over epochs, and the mean is taken over networks and epochs. For the set of datapoints {[2,,
249
250
(((z,,;))3 y;) 1j)] Learning Order Constancy is manifested by the high correlation between 2 instances of accessibilityy (x),, each computed from a different ensemble.
251
-iaa is shown to pertain LOC in two ways: First, in Section 4.1 we show high correlation between the learning order in deep linear and non- networks. Since the PC-bias fully accounts for LOC in deep linear networks, this suggests it also accounts (at least partially) for the observed LOC in non-linear networks. Comparison with the critical principal component verifies this assertion. Second, we show in Section 4.2 that when the PC-bias is neutralized, L.C diminishes as well. In we discuss the relationship between the spectral bias, PC-bias and the 1.0C-effect.
253
255
256
257
Section 4.3
4.1
PC-Bias is correlated with LOC
259
We first compare the order of learning of non-linear models and deep linear networks by computing the correlation between the accessibility scores of both models. This comparison reveals high
260
correlation (r = 0.85. p < 10 10-45), as seen in Fig. 5a To investigate directly the connection between the PC-bias and LOC, we define the critical principal component of an example be the first principal component P. such that a linear classifier trained on the original data can classify the example correctly when projected to P principal components. We trained N=100 st- VGG networks on the cats and dogs dataset, and computed for each example its accessibility score and critical principal component. In Fig. 5bl see strong negative correlation between the two scores 10-33
261
262
263
264
285
286
r < 10 *), suggesting that the PC-bias affects the order of learning as measured by accessibility.
287
125
1.2
5400
Whitered
Moan compoooon
Acreostbiity
2200
0.76
0.75
0.4
2300
0.50
0.90
0.0
1900
0.00
0.00
02
04
0.5
2.0
Lea hed fnnl
Aldata
Lesereed List
All daddea
Accessibility linear network
Mean accessiiityy
(a) Lincar networks
(b) Non-linear networks
(a)
(b)
Figure 6: LOC measured with and without PC-bias. Each bar represents the correlation between the learning order of 2 collections of 10 networks trained on CIFAR- 10. Orange bars represent natural images, in which the PC-bias is present, while blue bars represent whitened data, in which the PC-hias is eliminated. As PC-hias is more prominent earlier on, compare these correla- tions for the entire data (right bars), and for the subset of 20% "fastest learned" examples (left bars).
Figure 5: (a) Correlation between the accessibility score of N=100 st-VGG networks trained with low learning ratef] and N=100 linear st- LGG networks, trained on small mammals. (b) Correlation hetween the accessi- bility score of =N100 st-VGG networks trained on cats and dogs, and the critical principal component score. The accessibility plot is smoothed by moving average of width 10, Error bars indicate standard error.
288 4.2
Neutralizing the PC-bias leads to diminishing LOC
269
Whitening the data eliminates the PC-bias as shown in Fig. 3c since all the singular values are now identical. Here we use this observation to further probe into the dependency of the Learning Order Constancy on the PC-bias. Starting with the linear case, we train ensembles of N=10 2-layered linear networks on the cats and dogs dataset, 2 with and 2 without ZCA-whitenigg We compute the accessibility score for each ensemble separately, and correlate the scores of the ensembles each test case. Each correlation captures the consistency of the LOC-effect for the respective condition. This correlation expected to be very high for natural images. Low correlation implies that the LOC-effect is weak, as training the same network multiple times yields a different learning order.
270
271
273
275
2 As non- -ineiiner models achieve the accuracy of linear models within an epoch or 2, low learning rate is used.
7

---

277
Fig. 6a shows the results for deep linear networks. As expected, the correlation when using natural images very high. However, when using whitened images, correlation plummets, indicating that the 1.0C-effect is highly dependent on the PC-bias. We note that the drop in the correlation is much higher when considering only the 20% "fastest learned" examples, suggesting that the PC-bias affects learning order more evidently at earlier stages of learning.
278
280
282
Fig. 6b shows the results when repeating this experiment with non-linear networks, training collections of N=10 VGG-19 networks on CIFAR-I0. We find that the elimination of the PC-bias
283
284
in this case affects LOC much less, suggesting that the PC-bias can only partially account for the -efeeffect in the non-linear case. However, we note that at the beginning of learning, when the PC- C--bias is most pronounced, once again the drop much larger and very significant (half).
285
206
287
4.3
Spectral bias, PC-bias and LOC
288
The spectral bias (Rahaman et al. 2019) characterizes the dynamics of learning in neural networks differently, asserting that initially neural models can be described by low frequencies only. This may
289
280
provide an alternative explanation to LOC. Recall that LOC is manifested in the consistency of the accessibilityy score across networks. To compare between the spectral bias and accessibility score,
281
292
we first need to estimate for each example whether it can be correctly classified by low frequency model. Accordingly, we define for each example discriminability measure the percentage out
293
294
of its k neighbors that share with it class identity. Intuitively, an example has a low discriminability score when it is surrounded by examples from other classes, which forces the learned boundary to incorporate high frequencies. In $C.2 we show that in the 2D case analyzed by Rahaman et al. (2019).
295
296
2
this measure strongly correlates (r= 0.8, p < 10 10-2) 2) with the spectral bias.
297
298
We trained several networks (VGG-19 and st-VGG) on several real datasets, including small- mammals, STL-10, CIFAR-10/100 and subset of ImageNet-20. For each network and dataset,
289
300
we computed the accessibility score as well as the discriminability of each example. The vector space, in which discriminability is evaluated, is either the data or the network's perceptual space (penultimate layer activation). The correlation between these scores is shown in Table
302
Table I: Correlation between accessibility and discrim- inability.
0.400
accureyy
0.375
0.36
0.350
0.25
0.34
Argertio high
Dataset
Raw data
Penultimate
0.32
102
50eps
107
10
Steps
107
Small mammals ImageNet 20
0.46
0.85
0.01
0.54
(a) linear network
(b) non-linear network
CIFAR-100
0.51
0.85
Figure 7: Effects of amplifying the highest (blue) and lowest (orange) principal components.
STLI0
0.44
0.7
303
Using raw data, low correlation is still seen between the accessibility and discriminability scores when inspecting the smaller datasets (small mammals, CIFAR- 100 and STL10). This correlation vanishes when considering the larger Imt dataset. It would appear that on its own, the spectral bias cannot adequately explain the 1.OC-effect. On the other hand, in the perceptual space, the correlation between discriminability and accessibility is quite significant for all datasets. Contrary to our supposition, seems that networks learn representation where the spectral bias evident, but this bias does not necessarily govern its learning before the representation has been learned.
305
306
307
308
309
5
PC-bias: further implications
310
311
Early Stopping and the Generalization Gap. Considering natural images, it often assumed that the least significant principal components of the data represent noise (Torralba & Oliva 2003). In such cases, our analysis predicts that as noise dominates the components learned later in learning.
312
313
314
early stopping is likely to be beneficial. To test this hypothesis directly, we manipulated CIFAR-10
315
to amplify the signal in either the 1.5% most significant (higher) or 1.5% least significant (lower) principal components (see examples in Fig. T6 Suppl. $D). Accuracy over the original test set,
317
after training 10 st-VGG and linear st-V VGG networks on these manipulated images, can be seen
in Fig. 7
Both in linear and non-lincar networks, carly stopping is more beneficial when lower
8

---

319
principal components are amplified, and significantly less so when higher components are amplified, as predicted by the PC-bias.
320
321
Slower Convergence with Random Labels. Deep neural models can learn any random label assignment to given training set (Zhang al.. 20T6). However, when trained randomly labeled data, convergence appears to be much slower (Krueger et al. 2017). Assume, as before, that in natural images the lower principal components are dominated by noise. We argue that the PC-bias now predicts this empirical result, since learning randomly labeled examples requires signal present in lower principal components. To test this hypothesis directly, we trained 10 2-layered linear networks
322
323
324
325
326
327
on datasets of natural images. Indeed, these networks converge slower with random labels (see Fig. Sa). In Fig. [8b] we repeat this experiment after having whitened the images, to neutralize the DC-bias. Now convergence rate is identical, whether the labels are original or shuffled. Clearly, in
328
329
330
deep linear networks the PC-bias gives a full account of this phenomenon.
0.
1.00
1.0
30
0.75
W0
0.
0.50
02
Rondomibe labels
0.5
Original
Randemize lobels
0.
10
10
20
10
20
Steps
Steps
Steps
(a) original data
(b) whitened data
(a) Original labels
(b) Shuffled labels
Figure 8: Learning curves of 10 2-layered linear net- works, with real and shuffled labels, (a) before and (b) after whitening.
Figure 9: Learning curves of st- VGG networks trained on datasets, which are linearly separable after projec- tion to the highest P principal components (see legend).
331
To further check the relevance of this account to non-linear networks, we artificially generate datasets where only the first P principal components are discriminative, while the remaining components become noise by design. We constructed two such datasets: in one the labels are correlated with the original labels, in the other they are not. Specifically, PCA is used reduce the dimensionality of
332
333
334
335
two-class dataset to P, and the optimal linear separator in the reduced representation is computed.
336
Next, all the labels of points that are incorrectly classified by the optimal linear separator are switched,
337
so that the train and test sets are linearly separable by this separator. Note that the modified labels are still highly correlated with the original labels (for P- 500: p = 0.82, r < 10-11). The second dataset is generated by repeating the process while starting from randomly shuffled labels.
338
339
340
This dataset is likewise fully separable when projected to the first P components, but its labels are uncorrelated with the original labels (for P = 500: p = 0.06, r < 10 10-19).
341
342
The mean training accuracy of 10 non-linear networks with P=10,50,500 is plotted in Fig. 9a (first dataset) and Fig- (ss(cond dataset). In both cases, the lower P is (namely, only the first few principal components are discriminative), the faster the data is learned by the non-linear network. Whether the labels are real or shuffled makes little qualitative difference, as predicted by the PC-bias.
343
344
345
346
6
Summary and discussion
347
When trained with gradient descent, the convergence rate of the over-parameterized deep linear network model is provably governed by the eigendecomposition of the data, and specifically, pa- rameters corresponding to the most significant principal components converge faster than the least significant components. Empirical evidence is provided for the relevance of these results to more realistic non-lineat networks. We term this effect PC-bias. This result provides a complementary account for some prevalent empirical observations, including the benefit of early stopping and the slower convergence rate with shuffled labels.
348
349
351
353
354
We use the PC-bias to explicate the Learning Order Constancy (LOC), showing that examples learned at earlier stages are more distinguishable by the higher principal components, demonstrating that networks' training relies more heavily on higher principal components early on. A causal link
355
356
357
between the PC-bias and the LOC-effect is demonstrated, as the LOC-effect diminishes when the
PC-bias is eliminated by whitening the images. We analyze these findings in view of related
359
phenomenon termed spectral bias. While the PC-bias may be more prominent early on, the spectral
bias may be more important in later stages of learning.
9

---

References
361
362
Allen-Zhu, Z., Li, Y., and Liang. Y. Learning and generalization in overparameterizee neural
363
networks, going beyond two layers. arXiv preprint arXiv: 10::::111440 1.04918, 2018.
384
Arora, S., Cohen, N., and Hazan, E. On the optimization of deep networks: Implicit acceleration by
365
overparameterization. In International Conference on Machine Learning, pp. 244-2552 253,253, 2018.
Arora, S., Du, S., Hu, W., Li, Z., and Wang, R. Fine- tine-grained amalysis of optimization and generaliza- tion for overparameterized two-layer neural networks. In International Conference on Machine Learning, pp. 322-332, 2019.
367
368
369
Basri, R., Jacobs, D. W., Kasten, Y., and Kritchman, S. The convergence rate of neural networks for learned functions of different frequencies. In Advances in Neural Information Processing Systems, pp. 17711, 2019.
371
372
Basri, R., Galun, M., Geifman, A., Jacobs, D., Kasten, Y., and Kritchman, S. Frequeecy bias in neural networks for input of non-uniform density. In International Conference on Machine Learning, pp.
373
374
685-694. PMLR, 2020.
Cao, Y., Fang, Z., Wu, Y., Zhou, D.-.., and Gu, Q. Towards understanding the spectral bias of deep learning. arXiv preprint urXiv: 198, 2019.
376
377
Dingle, K., Camargo, C. Q., and Louis, A. A. Input-output maps are strongly biased towards simple outputs. Nature communications, 9(1):177, 2018.
378
379
Fukumizu, K. Effect of batch learning in multilayer neural networks. Gen, 1(04)) 1998.
380
Gissin, D., Shalev-Shwartz, S., and Daniely, A. The implicit bias of depth: How incremental learning drives generalization. arXiv preprint arXiv: 12051, 2019.
381
382
Glorot, X. and Bengio, Y. Understanding the difficulty of training deep feedforward neural networks. In Proceedings of the thirteenth international conference artificial intelligence and statistics, pp. 249-256, 2010.
384
385
Gunasekar, S., Lee, J., Soudry, D., and Srebro, N. Implicit bias of gradient descent on linear convolutional networks. arXiv preprint 106.04880..00468, 2018
386
387
Hacohen, G., Choshen, L., and Weinshall, D. Let's agree to agree: Neural networks share classification order real datasets. In International Conference on Machine Learning, pp. 3950-39900 3960. PMLR, 2020.
389
390
He, K., Zhang, X., Ren, S., and Sun, J. Delving deep into rectifiers: Surpassing human-level performance on imagenet classification. In Proceedings of the IEEE International Conference on Computer Vision (ICCV), December 2015.
391
Heckel, R. and Soltanolkotabi, M. Denoising and regularization via exploiting the structural bias of convolutional generators. arXiv preprint arXiv: 19/0. 14634, 2019.
394
385
Hu, W., Xiao, L., Adlam, B., and Pennington, J. The surprising simplicity of the early-time learning dynamics of neural networks. arXiv preprint arXiv:2006. 14599, 2020.
396
397
Jacot, A., Gabriel, F. and Hongler, C. Neural tangent kernel: Convergence and generalization in neural networks, 2020.
389
Krueger, D.,, Ballas, N., Jastrzebski, S., Arpit, D., Kanwal, M. S., Maharaj. T., Bengio, E., Fischer, A., and Courville, A. Deep nets don't 't learn via memorization. 2017.
400
Le Cun, Y., Kanter, I., and Solla, A. S. Second order properties of error surfaces learning time and generalization. Advances in neural information processing systems, 3:918-924, 1991.
402
Li, M., Soltanolkotabi, M., and Oymak, S. Gradient descent with early stopping is provably robust to label noise for overparameterized neural networks. International Conference on Artificial Intelligence and Statistics, pp. 4314-4324. PMLR, 2020.
404
10

---

408
Nakkiran, P., Kaplun, G., Kalimeris, D., Yang, T., Edelman, B. L., Zhang, F., and Barak, B. Sgd on neural networks learns functions of increasing complexity. arXiv preprint 1xXvv:905.116044 2019.
407
Pliushch, I. Mundt, M., Lupp. N., and Ramesh, V. When deep classifiers agree: Analyzing correlations between learning order and image statistics. arXiv preprint arXiv:2105.08997 2021.
410
411
Rahaman, N., Baratin, A., Arpit, D., Draxler, F., Lin, M., Hamprecht, F., Bengio, Y., and Courville,
A. On the spectral bias of neural networks. In International Conference Machine Learning, pp. 5301-5310. PMLR, 2019.
413
414
Saxe, A. M.. McClelland, J. L.. and Ganguli, S. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. arXiv preprint arXiv:1312.6120, 2013.
415
416
Saxe, A. M., McClelland, J. I.,, and Ganguli, S. mathematical theory of semantic development in deep neural networks. Proceedings of the National Academy of Sciences, 116(23):15337-11544 2019.
418
419
Shah, H., Tamuly, K., Raghunathan, A., Jain, P., and Netrapalli, P. The pitfalls of simplicity bias in neural networks. arXiv preprint arXiv:2006.07710. 2020.
Simoncelli, E. P. and Olshausen, B. A. Natural image statistics and neural representation. Annual review of neuroscience, 24(1):1 193-1216, 2001.
422
423
Soudry, D., Hoffer, E., Nacson, M. S., Gunasekar, S., and Srebro, N. The implicit bias of gradient descent on separable data. The Journal of Machine Learning Research, 19(1):2822 2878, 2018.
424
425
Torralba, and Oliva, A. Statistics of natural image categories. Network: computation neural
426
systems, 14(3):391-412, 2003.
Ulyanov, D., Vedaldi, A., and Lempitsky, V. Deep image prior. In Proceedings of the IEEE conference 2018.
428
on computer vision and pattern recognition, pp.
429
Valle-Perez, G., Camargo, C. Q. and Louis, A. A. Deep learning generalizes because the parameter- function map biased towards simple functions. arXiv preprint 1.XYv:8805.085222 2018
430
Zhang, C., Bengio, S., Hardt, M., Recht, B., and Vinyals, O. Understanding deep learning requires rethinking generalization. arXiv preprint 03.55006 2016.
432

---

Checklist
433
434
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
436
contributions and scope? [Yes]
437
(b) Did you descrihe the limitations of your work? [Yes]
438
(c) Did you discuss any potential negative societal impacts of your work? [N/A]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
440
441
2. If you are including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes] See the "Assumptions" paragraph as Section
443
444
(b) Did you include complete proofs of all theoretical results? [Yes] Each theorem reference its proof. Proofs can be found in Suppl. S
445
448
3.
If you ran experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main ex- perimental results (either in the supplemental material or as a URL)? [No] All data, instructions and syper-parameters Suppl. (see DD44..4). The code itself will be provided once the anonymity will be lifted.
448
explictly written in the main paper and/or in the
450
452
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes]
453
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
455
456
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [N/A]
457
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
459
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as URL? [N/A]
462
463
(d) Did you discuss whether and how consent was obtained from people whose data you'le 're using/curating? [N/A]
464
465
(e) Did you discuss whether the data you are using/curating contains personally identifiable information or offensive content? [N/A]
467
5. If you used crowdsourcing or conducted research with human subjects...
488
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
469
470
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent on participant compensation? [N/A]
473
12


Reviews:
[{"review_id": "ZNvuhx9pru", "reviewer": "Reviewer_9zUU", "summary": "This work studies the training dynamics of over-parameterized deep linear networks. The authors propose the Principal Components bias (PC-bias) convergence pattern that characterizes the convergence behavior of deep linear networks training, which is supported by theoretical analysis and empirical results. This works also investigates the Learning Order Constancy effect (LOC-effect) and identified the connection between PC-bias and LOC-effect. Empirically, the authors also study several implications of PC-bias, including early stopping, convergence behavior under label noise, and provide interesting observations.", "questions": "", "limitations": "", "rating": 5, "confidence": 3, "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": "This paper identifies several interesting phenomenons for deep (non-)linear neural networks, including the effect of whitened data, connections between the PC-bias, LOC-effect, and spectral bias. \nPros:\n1. Theoretically, this paper provides precise characterizations of the training dynamics of deep linear networks in Section 2.\n2. Empirically, the authors investigated the proposed PC-bias in several settings as well as its connections to LOC-effect and spectral bias.\n\nCons:\n1. The theoretical and empirical results are somehow limited to simple linear models, and some of the interesting observations have been studied in previous works, for example, [1] studied the dynamics of deep linear network training and found that the 'networks sequentially learn the solutions of a reduced-rank regression with a gradually increasing rank'. \n2. The connection between whitened data, label noise, and convergence speed is interesting, it would be better to precisely characterize this phenomenon in a lemma/theorem by making some reasonable assumptions.\n\n[1]. Implicit Regularization of Discrete Gradient Dynamics in Linear Neural Networks. Gauthier Gidel, Francis Bach, and Simon Lacoste-Julien, NeurIPS 2019.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "N.A.", "review_text": "", "extra_scores": {"ethical_concerns": "N.A.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "ReRFWgRdaa", "reviewer": "Reviewer_NiJh", "summary": "The authors study a principal component bias of deep linear neural networks when trained with gradient descent using a small learning rate. They show that when the network is sufficiently wide, deep linear networks behave like single layer linear networks during the first phase of training, where the rate of convergence is governed by the largest principled components of the data. It is further shown that at later stages of training, under some assumptions, the PC bias remains to some extent.", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "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": "My main concern with the paper is that it is overall quite incremental over previous results:\nIt is known for some time at this point that sufficiently wide networks evolve linearly, where convergence rate is governed by the principled components of the neural tangent kernel (NTK). For deep linear networks, the NTK itself is given by the Gram matrix of the data (\\Sigma_xx using the notations in the paper) scaled by the depth L, which is identical to the NTK of a single layer linear networks up to scale. Hence, it is trivial that when the width M is large, the convergence rate in both shallow and deep linear models will exhibit the PC bias as detailed by the authors. In other words, the large width assumption when applied to linear models strips it of all the interesting properties provided by depth and relegates it to a 1 layer linear network. \nFor the second phase of training, i find the assumptions made by the authors quite unrealistic. I would argue that in most tasks of interest k/m cannot be considered small. Moreover, the presented results show no explicit dependency on training time, which makes it difficult to understand the regimes in which the results hold. \n\nIn general, i find the PC bias as described in the paper lacking in its ability to explain any interesting phenomena in deep learning since it is inherently present in shallow networks as well.  In addition, it does not trivially apply to deep nonlinear models. Even when only considering linear models, the incremental technical novelty in the paper does not meet the threshold for acceptance in my opinion.\n\nQuestion:\n\n1) The experimental section includes results on VGG style linear architectures, however the theoretical section does not deal with convolutions. How should the PC bias be interpreted in this case? Shouldnt the gram matrix \\Sigma_xx be computed differently for convolutional architectures? \n\n\n_____________________Post Rebuttal______________________\n\nI appreciate the authors response to my review. However, my score remains unchanged for the following reasons. In my view the theoretical contribution is a restatement of known results - Theorem 2 discusses leading corrections to the infinite width limit, which have been discussed in numerous papers [1,2], and theorem 1 should be relegated to a proposition. Moreover, the actual claimed theoretical contribution - namely the O(q/m) and O(K/m) corrections, is not formally presented, and seems to be brushed aside due to technical issues (it is not clearly presented in the supplementary either). \nIn general i find the empirical section intriguing, however i doubt the claim of the paper carries over to larger datasets, and i feel this should be addressed in future versions of the paper. \n\n[1] Wide Neural Networks of Any Depth Evolve asLinear Models Under Gradient Descent\n\n[2] Asymptotics of Wide Networks from Feynman Diagrams\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I would encourage the author to address the limitation detailed in the review. ", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "Oru0YQamE9_", "reviewer": "Reviewer_QgKK", "summary": "The paper argues for the existence of the so-called “principal component bias” in the learning of deep wide nets, with the main focus on linear networks. This refers to the phenomenon that the learning that is associated with larger PCs of the data is typically faster. The paper does so via a theoretical analysis of the early stage of learning in linear nets and a series of experiments, involving both linear and nonlinear models.", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "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": "This is a paper with quite very interesting experiments. Understanding deep nets is difficult, so the ability to have a partial understanding via a simple pattern like PC bias is valuable, even though PC bias does not give the full picture as admitted in the paper. The theoretical analysis is non-rigorous and appears to be the weaker part; it is the series of small but informing experiments that give useful insights. Specifically the paper draws a nice connection between PC bias and common techniques like PC amplification, whitening and random labelling, demonstrating that PC bias can be a useful guide for subsequent studies that involve these techniques.\n\nMy main criticism lies in the theoretical part. Certain parts are not rigorous; for example:\n- In the use of big O notation, this notation hides a lot of important dependencies on e.g. time, weight magnitude, etc. This has serious implication to Theorem 2; for example, if the conclusion can only hold until time $\\sim O(1/m^{99})$, this implies Theorem 2 is not very useful (even though Fig. 1 is).\n- The proof of Theorem 5 is actually bad: from line 515 (which is an entry-wise bound as written) to line 516, one requires a certain union bounding over $m^2$ entries, and so the correct probability bound becomes void. This would have been avoided if the metric of interest (denoted by $|\\cdot |$ as in the paper) is not entry-wise absolute value, but some appropriate norm.\n\nThese can be fixed, though I think this is the less important part of the paper. Moreover previously there have been rigorous theoretical results that convey a certain sense of PC bias, by solving the complete solution of the learning dynamics, in linear networks (e.g. Gidel et al 2020) as well as nonlinear networks (e.g. Nguyen 2021), without the whitened data assumption just like this paper, but of course in tractable theoretical settings. As such, despite the weakness in the theoretical part, I would not say PC bias has no (or unreliable) theoretical basis, and I would rather emphasize on the experimental findings.\n\nWhile I do not know the experimental literature sufficiently well to judge on novelty, supposing there is no issue with that and unless there are flaws in experimental designs spotted by other reviewers, I think the paper is a worthy contribution to the broader community.\n\nReferences:\n\nGidel, Bach, Lacote-Julien, “Implicit regularization of discrete gradient dynamics in linear neural networks”, 2020.\n\nNguyen, “Analysis of feature learning in weight-tied autoencoders via the mean field lens”, 2021.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "Yes", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "Gg42IadWWs8", "reviewer": "Reviewer_aYkS", "summary": "The paper studies the evolution of a deep over-parametrized linear network under gradient descent.  The main claim of the paper is that the convergence rate of the weights is faster along directions corresponding to the larger principal components of the data, at a rate governed by the singular values. The paper also supports its argument in an extensive experimental study.", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "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": "The paper touches on an important question about the inductive bias of neural nets. This problem has paramount importance to the deep learning community. Moreover, the motivation of the results is clearly explained in the paper. \nHowever, I'm not sure whether the theoretical side is strong enough to justify a new publication. Specifically:\n\n1. Thm 1 is a direct calculation of the update at each iteration, its contribution is limited. Moreover, it seems to me like a minor modification of the update presented in \"Width Provably Matters in Optimization for Deep Linear Neural Networks\" by Du and Hu\n\n2. Thm 2 (which is the main theoretical claim of the paper) presenters a new result as far as I know. However, I'm not sure about its novelty given the techniques that are used in standard over-parametrized literature (for example \"Width Provably Matters in Optimization for Deep Linear Neural Networks\" by Du and Hu or \"Gradient descent finds global minima of deep neural networks\" by Du et al). I'll be happy if the authors can address the novelty of their proof techniques and compare it to standard lazy training technique.\n\n3. I would suggest rearranging section 2.2 to be formulated as formal theorems where the condition and results are rigorously organized. Moreover, separating more accurately between the two phases of learning might add to the paper's contribution.\n\n4. I think it is important to include the results of the nonlinear case (section B.2 in the appendix) in the main paper. Although additional assumptions are required. These results might hint that the phenomena presented in the paper happens also outside the linear network world. \n\nRegarding the empirical side, I think that the empirical study is impressive and definitely contributes to the paper. My main concern on the empirical side is why are the settings were changed in the empirical part? (specifically the loss and initialization). I suspect that the theory doesn't hold in practice which might weaken the paper. \n\nTo summarize my review, I didn't find major flaws in the paper. In my opinion, each part alone (the empirical and the theoretical) doesn't enough for a new publication. However, since both parts were combined together, I find the total contribution of the paper on the borderline for a top-tier conference. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "None", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "One day"}, "extra_text": {}}]

Author rebuttal:

Meta-review: Reviews of this paper were mixed. On the upside, several reviewers commended the insightfulness of its empirical investigation.  On the other end, concerns were raised regarding the novelty and significance of its theoretical contribution in light of known results in the ultra width (NTK) regime.  The latter point does not seem to be clearly delineated in the text.  Overall, while this work clearly has potential to be of interest to the community, due to the aforementioned drawback, it currently falls short of the (extremely competitive) NeurIPS acceptance threshold. I encourage the authors to clearly distill the novelty of their theory, reconsider how much weight is allocated to this theory in light of the distilled novelty, modify the text accordingly, and resubmit to a future conference.
Decision: Reject