Whitening and second order optimization both destroy information about the dataset, and can make generalization impossible
Authors: Neha S. Wadia
Daniel Duckworth
Samuel Stern Schoenholz
Ethan Dyer
Jascha Sohl-Dickstein
Venue:  (2021)
Keywords: whitening
second order optimization
deep networks
generalization

Abstract: Machine learning is predicated on the concept of generalization: a model achieving low error on a sufficiently large training set should also perform well on novel samples from the same distribution. We show that both data whitening and second order optimization can harm or entirely prevent generalization. In general, model training harnesses information contained in the sample-sample second moment matrix of a dataset. For a general class of models, namely models with a fully connected first layer, we prove that the information contained in this matrix is the only information which can be used to generalize. Models trained using whitened data, or with certain second order optimization schemes, have less access to this information; in the high dimensional regime they have no access at all, resulting in poor or nonexistent generalization ability. We experimentally verify these predictions for several architectures, and further demonstrate that generalization continues to be harmed even when theoretical requirements are relaxed. However, we also show experimentally that regularized second order optimization can provide a practical tradeoff, where training is accelerated but less information is lost, and generalization can in some circumstances even improve.

Under review as a conference paper at ICLR 2021
WHITENING AND SECOND ORDER OPTIMIZATION BOTH DESTROY INFORMATION ABOUT THE DATASET, AND CAN MAKE GENERALIZATION IMPOSSIBLE
Anonymous authors Paper under double-blind review
ABSTRACT
Machine learning is predicated on the concept of generalization: model achieving low error on sufficiently large training set should also perform well on novel samples from the same distribution. We show that both data whitening and second order optimization can harm or entirely prevent generalization. training harnesses information contained in the sample-sample second moment matrix of a dataset. For general class of models, namely models with a fully connected first layer, prove that the information contained in this matrix is the only information which can be used to generalize. Models trained using whitened data, with certain second order optimization schemes, have less access to this information; in the high dimensional regime they have no access at all, resulting in poor nonexistent generalization ability. We experimentally verify these predictions for several architectures, and further demonstrate that generalization continues be harmed even when theoretical requirements are relaxed. However, we also show experimentally that regularized second order optimization can provide a practical tradeoff, where training is accelerated but less information is lost, and generalization can in some circumstances even improve.
general, model
INTRODUCTION
Whitening is data preprocessing step that removes correlations between input features (see Fig. used across many scientific disciplines, including geology (Gillespie et al.. 1986), physics (Jenet et al. 2005), machine learning (Le Cun et al.] 1998). linguistics (Abney 2007). ), and chemistry (Bro Smilde| 2014). It has particularly rich history neuroscience, where it has been proposed as mechanism by which biological vision realizes Barlow's 's redundancy reduction hypothesis (Attneave)
1954; Barlow 1961 Atick & Redlich 1992. Dan ef al. 1996, (Simoncelli & Olshausen 2001).
Whitening is often recommended since, by standardizing the variances in each direction in feature space, it typically speeds up the convergence of learning algorithms (Le Cun et al. 1998, Wiesler & Ney| 2011). and causes models to better capture contributions from low variance feature directions. Whitening can also encourage models to focus on more fundamental higher order statistics in data, by removing second order statistics (Hyvärinen et al. 2009). Whitening has further been direct inspiration for deep learning techniques such as batch normalization (Ioffe & Szegedy 2015) and dynamical isometry (Pennington al. 2017: Xiao al. 2018
1.1 WHITENING DESTROYS INFORMATION USEFUL. FOR GENERALIZATION
In the high dimensional setting, for any model with a fully connected first layer, we show theoretically and experimentally that whitening the data and then training with gradient descent or stochastic gradient descent (SGD) results in model with poor or nonexistent generalization ability, depending on how the whitening transform is computed. We emphasize that, analytically, this result applies to any model whose first layer is fully connected, and is not restricted to linear models. Empirically, the results hold in an even larger context, including in convolutional networks. Here, the high dimensional setting corresponds to number of input features which is comparable to larger than the number of datapoints. While this setting does not usually arise in modern neural network applications, it is of particular relevance in fields where data collection is expensive otherwise prohibitive (Levesque)

---

Under review as a conference paper at ICLR 2021
Unwhitened
ZCA whitened
Unwhitened
ZCA whitened
8 0-
-2
-2
-2
2
(a)
X
Figure 1: Whitening removes correlations between feature dimensions in dataset. Whitening is linear transformation of dataset that sets all non-zero eigenvalues of the covariance matrix ZCA whitening a specific choice of the linear transformation that rescales the data in the directions given by the cigenvectors of the covariance matrix, but without additional rotations or flips. (a) A toy 2d dataset before and after ZCA whitening. Red arrows indicate the eigenvectors of the covariance matrix of the unwhitened data. (b) ZCA whitening of CIFARIO images preserves spatial and chromatic structure, while equalizing the variance across all feature directions.
et al.
2012), or where the data is intrinsically high dimensional (Stringer et al. 2019 Fusi et al. 2016
Shyr, 2012 Martinez-Ranne Ramón et al., 20066] Bruce et al., 2002). and is also the focus of increasing interest in statistics [Wainwright] 2019).
The loss of generalization ability for high dimensional whitened datasets is due to the fact that whitening destroys information in the dataset, and that in high dimensional datasets whitening destroys all information which can be used for prediction. This is related to investigations of information loss due PCA projection (Geiger & Kubin 2012). Our result is not restricted neural networks, and applies to any model in which the input is transformed by a dense matrix with isotropic weight initialization.
1.2 SECOND ORDER OPTIMIZATION HARMS GENERALIZATION SIMILARLY TO WHITENING
Second order optimization algorithms take advantage of information about the curvature of the loss landscape take a more direct route to a minimum (Boyd Vandenberghe 2004 Bottou al.
2018). There are many approaches to second order or quasi- second order optimization (Martens &
Grosse 2015 Dennis Jr Moré 1977; Broyden
1970 Fletcher
1970
Goldfarb 1970; [Shanno
1970
Liu & Nocedal | |Schraudolph et al. 2007 [Sunehag et al. 2009 Martens 2010 Byrd et al.
2011
Vinyals & Povey 2011 Lin in et al. 2008 Hennig 2013 Byrd al.,
2014
Sohk-Dickstein et
2014
Desjardins et al.
2015 Grosse & Martens 2016 Martens et al.
2018 George et al. 20018
Zhang et 2017 Botev ct al. | Bollapraadaa et 2018 Berahas et al. [ Gupta et al.
2018
Agarwal et al.
2016 Duchi al. [20 1 Shazeer & Stern 2018 Anil et al. 2019 Agarwal
ct al.
2019 Lu et al. 2018 Kingma & Ba| [014]] Zeiler 2012 Tieleman & Hinton 2012 Osawa
[
al. 2020). and there is active debate over whether second order optimization harms genera lizatinn
(Wilson et al. 2017 Zhang et al. 2018 2019 Amari et al. 2020 Vaswani et al. 2020). The measure of curvature used these algorithms is often related feature-feature covariance matrices of the input, and of intermediate activations (Martens & Grosse 2015). In some situations, it is already known that second order optimization equivalent steepest descent training on whitened data Martens & Grosse,2013.
(Sohl-Dickstein 2012
The similarities between whitening and second order optimization allow us to argue that pure second order optimization also prevents information about the input distribution from being leveraged during training, and can harm generalization (see Figs. regularized and carefully tuned, second order methods can lead to superior performance (Fig.) 5)
We do find, however, that when strongly
2 THEORY OF WHITENING, SECOND ORDER OPTIMIZATION, AND GENERALIZATION
Consider dataset X E dx consisting of n independent d-dimensional examples. We write F for the feature-feate second moment matrix and K for the sample-sample second moment matrix:
F= XX E Rdxd
K = x
(1)
2

---

Under review as a conference paper at ICLR 2021
Ytrain
Seet
0
8
0
f(X) (2)
0r
g++1
Zrain
Zrrain
Araain
fetl
W Z = WX
Train
2++1
K Krasn
Kerains
(b) Kerain
Xtroin
(a)
Figure 2: Activations and weights depend on the training data only through second moments. (a) Our model class consists of a linear transformation Z W X, followed by nonlincar map (Z) with parameters 8. Note that this model class includes fully connected neural networks, among other common machine learning models. (b) Causal dependencies for single gradient descent update. The changes in weights, activations, and model output depend on the training data through training sample second moment matrix, gains and targets, Yeain- (c) Causal structure for the entire training trajectory. The final weights and training activations only depend on the training data through the training sample second moment matrix Kmiin and the targets Yuain. while the test predictions (in purple) also depend on the mixed second moment matrix, Kmiix
We assume that at least one of F or K is full rank. We omit normalization factors of 1/n and 1/d in the definitions of F and K, respectively, for notational simplicity in later sections. Note that as defined, K is also the Gram matrix of X.
Definition 2.0.1 (Whitening). Any linear transformation M s.t. X MX maps the eigenspectrum of F ones and zeros, with the multiplicity of ones given by rank(F).
We consider the two cases n < d and n 2 d (when d both cases apply).
n 2 d: F pad
K = Σ aū,
i=1
n S d: F
0,0 K ma
Here, f'r and K denote the whitened second moment matrices, and the vectors ù; and 0j are orthogonal unit vectors of dimension and d respectively. Eq, follows directly from the fact that X X and XX share nonzero eigenvalues.
We are interested in understanding the effect of whitening the performance of a trained model when evaluated on a test set. We will see that for models with dense first layer (eg. fully connected neural networks), the trained model depends the training inputs only through K. In general, training dynamics and generalization performance can depend non-trivially on K. However, whitening trivializes K, and so eliminates the ability of the network and training algorithm to take advantage of information contained in it.
2.1 TRAINING DYNAMICS DEPEND THE TRAINING DATA ONLY THROUGH ITS SECOND MOMENTS
Consider model f with a dense first layer Z:
f(X) =x)==go2)) (2), 2 = WX,
(3)
where W denotes the first layer weights and 0 denotes all remaining parameters (see Fig. (()).
The structure of go (:) is unrestricted. W is initialized from isotropic distribution. We study
3

---

Under review as a conference paper at ICLR 2021
supervised learning problem. in which each vector X, corresponds to label Y:П We adopt the notation Xuain E Rd and Yuain for the training inputs and labels, and write the corresponding second moment matrices as Firin and Krain We consider models with loss L(f(X);; Y) trained by SGD. The update rules are
OL g++1 l 7) ag
OL
OL 0z
and W = W aaw = W 17
X train
(4)
where denotes the current training step, v) is the learning rate, and I," is the loss evaluated only on the minibatch used at step t.
As a result, the activations Zurin evolve as
0T.
ØI.
train
Zraain
11 az
Xrain Xurain = Zrran
K Kuain-
(5)
train
Treating the weights, activations, and function predictions as random variables, with distributions induced by the initial distribution over W the update rules (Eqs. 5) can be represented by the causal diagram in Fig. [b). We can now state one of our main results.
Theorem 2.1.1. Let fXX be a function as Eq. with linear first layer parameters 9. Let W be initialized from an isotropic distribution, Further, let f(X) be trained via gradient descent on a training dataset X main- The learned weights 6e and firtt layer activations Zinan are independent of X irain conditioned on Kinin and Ymii-- In terms of mutual information I, we have
WX,, and additional
I I(Ziriia 0¹; Xurain
K Yurii)) 0 Vt.
(6)
Proof. To establish this result, note that the first layer activation initialization, 2 is random variable due to random weight initialization, and only depends on Xirain through Kirain
I( Xtrin
Kirain) = 0.
This is a consequence of the isotropy of the initial weight distribution, explained in detail in Ap- pendix A Combining this with 4 45 the causal diagram for all of training is given by (the black part of) Fig c).. The conditional independence of 6 from this diagram.
2.2 TEST SET PREDICTIONS DEPEND ON TRAIN AND TEST INPUTS ONLY THROUGH THEIR SECOND MOMENTS
Let Nrest E Ridx and Yies be the test data. The test predictions fies = ((Xies) are determined by Zie = Xiest and 0% So far we have discussed the evolution of Zurain To identify sources of data dependence, we can write the evolution of the test set predictions Ziest over the course of training in similar fashion:
OL @Zi
Zt41 Zt
K Krrinxttssss
where Kininxtest train Xiest E Reoin X The initial first layer activations are independent of the training data, and depend on Xiese only through Kien:
I( X Kiss) =0
where X is the combined training and test data. If we denote the second moment matrix over this combined set by K, then the evolution of the test predictions is described by the (purple part of the) causal diagram in Fig.Zcc), from which we conclude the following.
Theorem 2.2.1. For a function f(X) in 3 trained with the update rules Eqs. $gs.455 from isotropic weight initialization, test predictions depend on the training data only through K and Y Yiain- This is summarized in the mutual information statement
I(Srei X K, Y 0.
(10)
We emphasize that Theorem 2.2.1 applies any model with dense first layer, and is not limited to linear models.
'Our results also apply to unsupervised learning, which can be viewed a special case of supervised learning where Y, contains information.
4

---

Under review as a conference paper at ICLR 2021
2.3 WHITENING HARMS GENERALIZATION IN HIGH DIMENSIONAL DATASETS
Full data whitening of a high dimensional dataset. We first consider a simplified setup: com- puting the whitening transform using the combined training and test data. We refer this as "full-whitening" We consider the large feature count (d 2 n) regime. In this case, by 2q.2 K T. Since K is now a constant rather than stochastic variable, T0 reducess to
we have
I(Siss
muinn) =0
(11)
That is, test set predictions contain no information about the model inputs X. Model accuracy in this regime can be no higher than chance.
Training data whitening of a high dimensional dataset. practice, we are more interested in the common setting of computing whitening transform based only the training data. We call data whitened this way 'train-whitendd.. As mentioned above, the test predictions of a model are entirely determined by the first layer activations Zes and the weights 0 From Theorem 2.1.1 we that the learned weights of depend on the training data only through Kusin and are thus independent of the training data for whitened data:
I(O";
Xtain
Virain) = 0.
(12)
It is worth emphasizing this point because in most realistic networks the majority of model parameters contained in these deeper weights 09.
Despite the deep layer weights, 0', being unable to extract information from the training distribation, the model is not entirely incapable of generalizing to test inputs. This is because the test activations Zra will interpolate between training examples, using the information in K Rrainxtest More precisely,
Z = Zlest + (Zrainn
Ziain)
Kurain
(13)
This interpolation in Z is the only way in which structure in the inputs Xurin can drive generalization. This should be contrasted with the case of full data whitening, discussed above, where Kminxtest 0. We therefore predict that when whitening is performed only on the training data, there will be some generalization, but it will be much more limited than can be achieved without whitening.
2.4 WHITENING IN LINEAR LEAST SQUARES MODELS
Linear models = W X provide intuition why whitening be harmful, which we discuss briefly here. The linear case also enables us to extend our theory to also apply to low dimensional datasets. A detailed exposition is in Appendix
For this section only, consider the low dimensional case d < n, where the loss has a unique global optimum W* The model predictions this optimum are invariant whitening. However, whitening has an effect on the dynamics of model predictions over the course of training. When training is performed with early stopping based on validation loss, predictions differ considerably for models trained on whitened and unwhitened data. These benefits from early stopping can be related to benefits from weight regularization (Yao al. 2007).
We focus on the continuous-time picture because it is the clearest, but similar statements can be made for gradient descent. Recall that vs are the eigenvectors of Fizin- Denoting the corresponding eigenvalues by X; the dynamics of W under gradient flow for a mean squared loss are given by the decomposition
-0: W(L) Σ (,))((),, mx((t) = e- w=(()) + )Ad)))
(14)
Eq. 14 shows that larger principal components of the data are learned faster than smaller ones. Whitening destroys this hierarchy by setting A; = -i... If, for example, the data has a simplicity bias (large principal components correspond to signal and small ones correspond to noise). whitening forces the learning algorithm to signal and noise directions simultaneously. which results in poorer generalization finite times during training than would be observed without whitening.
5

---

Under review as a conference paper at ICLR 2021
2.5 NEWTON'S S METHOD EQUIVALENT TO TRAINING ON WHITENED DATA FOR LINEAR LEAST SQUARES MODELS AND FOR WIDE NEURAL NETWORKS
Though in practice unregularized Newton's method is rarely used as an optimization algorithm due to computational complexity, a poorly conditioned Hessian, or poor generalization performance, serves as the basis of and limiting case for most second order methods. Furthermore, in the case of linear least squares models or wide neural networks, it is equivalent to Gauss-Newtee descent. In this context, by relating Newton's 's method to whitening linear models and wide networks, we are able to give an explanation for why unregularized second order methods have poor generalization performance. We find that our conclusions also hold empirically in a deep CNN (see Figs.
We now compare a pure Newton update step unwhitened data with a gradient descent update step on whitened data a linear least squares model. The Newton update step uses the model's Hessian H preconditioner for the gradient:
ØL
W Newlon
W Newton
HH
(15)
OW
Here we allow for general step size, 7,, with 17= 1 giving the canonical Newton update. It should be noted that this canonical update achieves the optimal solution to the least squares problem a single step. When H is rank deficient, we take H to be pseudoinverse. For a linear model with mean squared error (MSE) loss, the Hessian is equal to the second moment matrix Fizain and the model output evolves as
OL.
Newton (X) SNewion (X) 17 0f Newton
X train
F--1 X. Irain"
(16)
We can compare this with the evolution of a linear model f(X) - W M trained via gradient descent on whitened data X = XX with mean squared loss:
aL X M MX = P(x) " af train P X.
OL
(x+ = (x) a
(17)
Eqs. 16 and 17 give identical update rules. Thus if both functions are initialized to have the same output, Newton updates give the same predictions as gradient descent on whitened data. While this correspondence is known in the literature, we now it to say something further, namely that by applying the argument in Section 2.1 we expect Newton's 's method to produce lincar models that generalize poorly. Our theory results for second order optimization assume mean squared loss, but we find experimentally that generalization also harmed with a cross entropy loss in Fig. d)..
Finally, many neural network architectures, including fully connected and convolutional architectures, behave as linear models in their parameters throughout training in the large width limit (Lee et al. 2019). The large width limit occurs when the number of units channels in intermediate layers of the network grows towards infinity, Because of this, second order optimization harms wide neural networks in the same way harms linear models (see Appendix C).
EXPERIMENTS
Model and task descriptions and detailed methods are given in Appendix
E
Whitening and second order optimization impair generalization. In agreement with theory, in Fig) a) and (b), linear models and MI.s trained on fully whitened data generalize at chance levels until the size of the dataset exceeds the dimensionality of the data, and models trained on mein-whitened data perform strictly worse than those trained on unwhitened data. Furthermore, the generalization ability of these models recovers only gradually the dataset grows. On CIFAR-10, 20% gap in performance between MLPs trained on whitened and unwhitened data persists even at the largest dataset size, suggesting that whitening can remain detrimental even when the number of training examples exceeds the number of features by an order of magnitude.
In Fig. 3) we generalization gap in the high dimensional regime between WRNs trained on

---

Under review as a conference paper at ICLR 2021
linear model
MLP
0.50
best aroP
0.48
test error
0.46
GD: unwhitened
0.4
GD: whitened
10P
10
10
102
10
10
GD: full whitened
(a)
dataset size
(b)
dataset size
NGD: unwhitened
WRN
CNN
input dimension
1,0
2.5
GD: training loss
NGD: training lass
0.8
test (train) loss
tast cror
2.5
2.0
0.4
10
10P 10a 101
10'
18
10'
(c)
training size
(d)
training size
Figure 3: Whitening and second order optimization reduce prevent generalization. (a)-(e) Models trained on both fully whitened data (blue: panes a.b) and train- whitened data (green; panes a-c) consistently underperform models trained by gradient descent on unwhitened data (purple: all panes). In (a), Newton's 's method on unwhitened data (pink circles) behaves identically to gradient descent on whitened data. (d) Second order optimization in convolutional network results in poorer generalization properties than steepest descent. Points plotted correspond to the Icarning rate and training step with the best validation loss for each method. Data for this experiment was unwhitened. CİFAR-ID used for all experiments (see Appendix [i experiments on MNIST). In (c) and (d) we use a cross entropy loss (see Appendix for details).
thiteend versus unwhitened data, which persists when the size of the dataset grows beyond its dimensionality. This is despite the fact that the convolutional input layer violates the requirements of our theory, and that used a Xavier initialization scheme, therefore also violating the theoretical requirement for an isotropic weight initialization. We note that these results are consistent with the whitening experiments in the original WRN paper (Zagoruyko & Komodakis 2016). Generalization ability begins to recover before the size of the training set reaches its input dimensionality, suggesting that the effect of whitening can be countered by engineering knowledge of the data statistics into the model architecture.
In Fig. B Ba), we demonstrate experimentally the correspondence we proved in Section 2.5 In Fig. we observe that pure second order optimization similarly harms generalization even in a convolutional network. Despite training lower values of the training loss, CNN trained with unregularized Gauss-Newer method exhibits higher test loss (at the training step with best validation loss) than the same model trained with gradient descent.
Whitening and second order optimization accelerate training In Figs, 4 a) and App. linear models trained on whitened data or with a second order optimizer converge to their final loss faster than models trained on unwhitened data, but their best test performance is always worse. In Fig. (bb. MLPs trained on whitened CIFAR- 10 data take fewer epochs to reach to the same training accuracy cutoff than models trained on unwhitened data, except at very small (< 50) dataset sizes. The effect stark at large dataset sizes, where the gap in the number of training epochs is two orders of magnitude large. Second order optimization similarly speeds up training in convolutional network. In Fig. (c), c), unregularized Gauss-Newton descent achieves its best validation loss two orders of magnitude faster (as measured in the number of training steps) than gradient descent.
Regularized second order optimization can simultaneously accelerate training and improve generalization. In Fig. we perform full batch second order optimization with preconditioner ((1 - X)B + XT) where À [o. 1] is regularization coefficient, and B-1 is the unregularized Gauss-Newton preconditioner. = 0 corresponds to unregularized Gauss-Newton descent, while = 1 corresponds to full batch steepest descent. At all values of X, regularized Gauss-Newton
7

---

Under review as a conference paper at ICLR 2021
llnear model
MLP
CNN
150
validation (train) loss
0.50
training epechs
test ertor
0.48
1.00
unwhitoned
0.46
GD: train whitened
CD: full whitened.
NGD: unwhittneed training loss
0.46
10:4
102
10P
10'
162
10a
10
10
10a
104
1ca
10"
10"
(8)
training
(b)
dataset
training step
Figure 4: Models trained on whitened data or with second order optimizers converge faster. (a) Linear models trained on whitened data optimize faster, their best test accuracy was always worse. Data plotted here is for a training set of size 2560. Similar results for smaller training set sizes are given in Fig.AApp.] (b) Whitening the data significantly lowers the number of epochs needed to train an MLP to fixed cutoff in training accuracy, when the learning rate and all other training parameters are kept constant. Discrete jumps in the plot data correspond to points at which the (constant) learning rate was changed. See Appendix [ for details. (c) Second order optimization accelerates training on unwhitened data a convolutional network, compared to gradient descent. Data shown is for a training set of size 10240. Stars correspond to values of the validation loss which test and training losses are plotted in Fig. d..
achieves its lowest validation loss in fewer training steps than steepest descent (Fig. (()). For some values of X, the regularized Gauss-Newton method additionally produces lower test loss values than steepest descent (Fig. a)).
Writing the preconditioner in terms of the eigenvectors, é, and eigenvalues, A of B
(11 - 1)-A\)++A)) xI -
(18)
we see that regularized Gauss optimization acts similarly to unregularized Gauss-Newtor in the subspace spanned by eigenvectors with eigenvalues larger than A/ A). and similarly to steepest descent in the subspace spanned by eigenvectors with cigenvalues smaller than A/(1 X). We therefore suggest that regularized Gauss-Newton should be viewed as discarding information in the large-eigenvector subspace, though our theory does not formally address this case. As À increases from zero to one, the ratio A/(1- - A) increases from zero to infinity. Regularized Gauss-Newton method therefore has access to information about the relative magnitudes of more and more of the principal components in the data as À grows larger. We interpret the improved test performance with regularized Cauus-Newton about within the leading subspace is actually beneficial for the model on this dataset, likely due to aspects of the model's 's inductive bias which are actively harmful on this task.
0.5 in Flg. as suggesting that this loss of information
DISCUSSION
Are whitening and second order optimization good idea? Our work suggests that whitening and second order optimization come with costs - likely reduction in the best achievable generaliza- tion. However, both can drastically decrease training time an effect we also see our experiments. As compute is often a limiting factor on performance (Shallue et al., 2018). there are many scenarios where faster training may be worth the reduction generalization. Additionally, the negative effects may be largely resolved if the whitening transform or second order preconditioner are regularized, as often done practice (Grosse & Martens 2016). We observe benefits from regularized second order optimization in Fig. 5 and similar results have been observed for whitening (Lee et al. 2020).
Directions for future work. The practice of whitening has, in the machine learning community, largely been replaced by batch normalization, for which it served inspiration (loffe & Szegedy 2015). Studying connections between whitening and batch normalization, and especially understand- ing the degree which batch normalization destroys information about the data distribution, may be particularly fruitful. Indeed, some results already exist in this direction (Huang et al. 2018).
Most second order optimization algorithms involve regularization, structured approximations the
8

---

Under review as a conference paper at ICLR 2021
CNN
1.70
10*
GD: unwhitened
1.65
NGD: unwhitened,
training steps
regularized
1.60
1.55
107
1.50
10'
1.45
10-4
10
0.5
1
10
1-10
10-
10-4
10-3
0.3
1-10-9
1- 1--0
(NGD regularizer strength)
(NGD regularizer strength)
(a)
(b)
Figure 5: Regularized second order methods train faster than gradient descent, with minimal even positive impact on generalization. Models were trained on a size 10240 subset of CIFAR-I0 by minimizing cross entropy loss. Error bars indicate twice the standard error the mean. (a) Test loss as a function of regularizer strength. At intermediate values of X, the second order optimizer produces lower values of the test loss than gradient descent. Test loss is measured the training step corresponding to the best validation performance for both algorithms. See text for further discussion. (b) At all values of À < 1, the second order optimizer requires fewer training steps to achieve best validation performance.
Hessian, and often non-stationary online approximations to curvature. Understanding the implications of theory results for practical second order optimization algorithms should prove be extremely fruitful direction for future work. It is our suspicion that more mild loss of information about the training inputs will occur for many of these algorithms.
Recent work analyzes deep neural networks through the lens of information theory (Tishby &
Zaslavsky 2015 Bassily et al. 2017 Banerjee 2006 Shwartz-Ziv Tishby 2017 Achille & Soatto
2017]Achhil Achille & Soatto, 2019 Amjad & Geiger 2018 Saxe et al., 22199; Kolchinsky et al. 2018
Alemi 2016 (Schwartz- Ziv & Alemi 2019). often computing measures of mutual information
similar to those we discuss. Our result that the only usable information in a dataset is contained in its sample-sample second moment matrix may inform or constrain this type of analysis.
REFERENCES
Steven Abney. Semisupervised learning for computational linguistics. Chapman and Hal//CRC, 2007.
A. Achille and S. Soatto. Emergence of Invariance and Disentangling in Deep Representations. Proceedings of the ICML Workshop on Principled Approaches to Deep Learning, 2017.
Alessandro Achille and Stefano Soatto. Where is the information in deep neural network? arXiv preprint arXiv: 1905. 13, 2019.
Naman Agarwal, Brian Bullins, and Elad Hazan. Second-order stochastic optimization for machine learning in linear time. arXiv preprint arXiv:1602.03943, 2016.
Naman Agarwal, Brian Bullins, Xinyi Chen, Elad Hazan, Karan Singh, Cyril Zhang, and Yi Zhang Efficient full-matrix adaptive regularization. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Proceedings of Machine Learning Research, pp. 102-110, Long Beach, California, USA, 09-15 Jun 2019. PMLR.
Kyle Aitken and Guy Gur-Ari. On the asymptotics of wide networks with polynomial activations. To appear.
Alexander A Alemi, Ian Fischer, Joshua Dillon, and Kevin Murphy. Deep variational information bottleneck. arXiv: (afh::1612004111 2016.
Shun-ichi Jimmy Ba, Roger Grosse, Xuechen Li, Atsushi Nitanda, Taiji Suzuki, Denny Wu, and Ji Xu. When does preconditioning help or hurt generalization?, 2020.
Rana Ali Amjad and Bernhard Geiger. How (not) to train your neural network using the information bottleneck principle. arXiv preprint arXiv: 1802.09766 2018.

---

Under review as a conference paper at ICLR 2021
Anders Andreassen and Ethan Dyer. Asymptotics of wide convolutional neural networks. To appear.
Rohan Anil, Vineet Gupta, Tomer Koren, and Yoram Singer. Memory-efficient adaptive optimization for large-scale learning, arXiv preprint arXiv: 19900111100 2019.
Joseph J. Atick and A. Norman Redlich. What does the retina know about natural scenes? Newral Comput., 4(2):1962200, March 1992.
Fred Attneave. Some informational aspects of visual perception. Psychol. Rev, pp- 183-193, 1954.
Arindam Banerjee. On bayesian bounds. In Proceedings of the 23rd international conference on Machine learning, pp. 81-88. ACM, 2006.
Horace Barlow. Possible principles underlying the transformations sensory messages. Sensory Communication, 1, 01 1961.
Raef Bassily, Shay Moran, Ido Nachum, Jonathan Shafer, and Amir Yehudayoff. Learners that use little information. arXiv preprint arXiv: 2017.
Anthony J. Bell and Terrence J. Sejnowski. The "independent components" of natural scenes edge filters. Vision Research, 37(23):3327 - 3338, 1997.
Albert S. Berahas, Majid Jahani, and Martin Takáč. Quasi-newton methods for deep learning: Forget the past, just sample. arXiv preprint arXiv:1901009997, 2019.
Raghu Bollapragada, Jorge Nocedal, Dheevatsa Mudigere, Hao-Jun Shi, and Ping Tak Peter Tang. A progressive batching I-BFGS method for machine learning. In Jennifer Dy and Andreas Krause (eds.), Proceedings of the 35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pp. 620 (29,,29,555 Stockholmsmässan, Stockholm Sweden, 10-15 Jul 2018. PMLR.
Aleksandar Botev, Hippolyt Ritter, and David Barber. Practical gauss-newton optimisation for deep learning. Proceedings of the 34th International Conference on Machine Learning Volume 70, ICML' 17, pp. 557-565. JMLR.org, 2017.
Léon Bottou, Frank F. Curtis, and Jorge Nocedal. Optimization methods for large-scale machine learning. SIAM Review, 60(2):223-311, 2018.
Stephen Boyd and Lieven Vandenberghe. Convex Optimization. Cambridge University Press, USA, 2004. ISBN 0521833787.
Rasmus Bro and Age Smilde. Principal component analysis. Analytical Methods, 6(9):2812-22) 2213,,,,,, 2014.
CG Broyden. The convergence of a class of double-rank minimization algorithms The new algorithm. IMA Journal of Applied Mathematics, 1970.
L. M. Bruce, C. H. Koger, and Jiang Li. Dimensionality reduction of hyperspectral data using discrete wavelet transform feature extraction. IEEE Transactions on Geoscience and Remote Sensing, 40 (10):2331-2333 Oct 2002.
RH Byrd, SL Hansen, Nocedal, and Y Singer. A Stochastic Quasi-Newton Method for Lerge-Seale Optimization. arXiv preprint arXiv: /401.700 2014.
Richard H Byrd, Gillian M Chin, Will Neveitt, and Jorge Nocedal. On the use of stochastic hessian information in optimization methods for machine learning. SIAM Journal on Optimization, 21(3): 977-995, 2011.
Yang Dan, Joseph J. Atick, and R. Clay Reid. Efficient coding of natural scenes in the lateral geniculate nucleus: Experimental test of computational theory. Journal of Neuroscience, 16(10): 3351-3362, 1996.
John E Dennis Jr and Jorge Moré. Quasi-Newton methods, motivation and theory. SIAM review, 19 (1):46-89, 1977.
10

---

Under review as a conference paper at ICLR 2021
Guillaume Desjardins, Karen Simonyan, Razvan Pascanu, and koray kavukcuoglu. Natural neural networks. C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Gareet (eds.), Advances in Neural Information Processing Systems 28, pp. 2071 2071-220 1-279. Curran Associates, Inc., 2015.
John Duchi, Elad Hazan, and Yoram Singer. Adaptive subgradient methods for online learning and stochastic optimization. Journal of Machine Learning Research, 12(ul))2121-2155: 2011.
Ethan Dyer and Guy Gur-Ari. Asymptotics of wide networks from feynman diagrams. ArXiv, abs/1909. 1304, 2020.
Fletcher. A new approach to variable metric algorithms. The computer journal, 1970.
Stefano Fusi, Earl K Miller, and Mattia Rigotti. Why neurons mix: high dimensionality for higher cognition. Current Opinion in Neurobiology, 37:66 74, 2016.
Bernhard C Geiger and Gernot Kubin. Relative information loss the pea. 2012 IEEE Information Theory Workshop, pp. 562-566. IEEE, 2012.
Thomas George, César Laurent, Xavier Bouthillier, Nicolas Ballas, and Pascal Vincent. Fast approximate natural gradient descent in a Kronecker-factore eigenbasis. In Proceedings of the 32nd International Conference on Neural Information Processing Systems, NIPS' 18, pp. 9573-9583, Red Hook, NY, USA, 2018. Curran Associates Inc.
Alan R Gillespie, Anne B Kahle, and Richard E Walker. Color enhancement of highly correlated images. i. decorrelation and hsi contrast stretches. Remote Sensing of Environment, 20(3):209-235, 1986.
D Goldfarb. A family of variable-metric methods derived by variational means. Mathematics of computation, 1970.
Roger Grosse and James Martens. A kronecker-factored approximate fisher matrix for convolution layers. arXiv preprint arXiv: /602. 01700,440000 2016.
Vineet Gupta, Tomer Koren, and Yoram Singer. Shampoo: Preconditioned stochastic tensor optimiza- tion. CoRR, abs/1802.09568, 2018.
Hennig. Fast probabilistic optimization from noisy gradients. International Conference on Machine Learning, 2013.
Jiaoyang Huang and H B Yau. Dynamics of deep neural networks and neural tangent hierarchy. ArXiv, abs/1999.08144 2019.
Lei Huang, Dawei Yang, Bo Lang, and Jia Deng. Decorrelated batch normalization. 2018 IEEE/CVF Conference Computer Vision and Pattern Recognition, pp. 791-800, 2018.
Aapo Hyvärinen, Jarmo Hurri, and Patrick O. Hoyer. Natural Image Statistics: A Probabilistic Approach to Early Computational Vision. Springer Publishing Company, Incorporated, 1st edition, 2009.
Sergey loffe and Christian Szegedy. Batch normalization: Accelerating deep network training by reducing internal covariate shift. In Proceedings of the 32Nd International Conference on International Conference on Machine Learning Volume 37, ICML' 15, pp. 448-456. JMLR.org. 2015.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernl:: Convergence and generalization in neural networks. In Advances in neural information processing systems, pp. 8571-8580, 2018.
Fredrick Jenet, George B Hobbs, KJ Lee, and Richard Manchester. Detecting the stochastic gravitational wave background using pulsar timing. The Astrophysical Journal Letters, 625(2): L123, 2005.
Diederik P Kingma and Jimmy Ba. Adam: method for stochastic optimization. arXiv preprint arXiv:1412.60 1412.6980) 2014.
11

---

Under review as a conference paper at ICLR 2021
Artemy Kolchinsky, Brendan D Tracey, and Steven Van Kuyk. Caveats for information bottleneck in deterministic scenarios. arXiv preprint arXiv: 07593, 2018.
Hanspeter Kraft and C. Procesi. Classical invariant theory: a primer. 1996.
Yann Le Cun, Léon Bottou, Genevieve B. Orr, and Klaus-Robert Müller. Efficient backprop. In Neural Networks, Tricks of the Trade, Lecture Notes in Computer Science LNCS 1524. Springer Verlag, 1998.
Jachoon Lee, Lechao Xiao, Samuel Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve linear models under gradient descent. In Advances in neural information processing systems, pp. 8570-8581, 2019.
Jachoon Lee, Samuel S. Schoenholz, Jeffrey Pennington, Ben Adlam, Lechao Xiao, Roman Novak, and Jascha Sohl-Dickstein. Finite versus infinite neural networks:an empirical study, in preparation, 2020.
Hector J. Levesque, Ernest Davis, and Leora Morgenstern. The winograd schema challenge. In 13th International Conference on the Principles of Knowledge Representation and Reasoning, KR 2012, pp. 552-561, 2012.
Chih-Jen Lin, Ruby C Weng, and S Sathiya Keerthi. Trust region newton method for logistic regression. The Journal of Machine Learning Research, 9:627-650, 2008.
Etai Littwin, Tomer Galanti, and L. Wolf. On the optimization dynamics of wide hypernetworks. ArXiv, abs/2003.12193, 2020.
Dong DC Liu and Jorge Nocedal. On the limited memory BFGS method for large scale optimization. Mathematical programming, 45(1-3):503-522 1989.
Yao Lu, Mehrtash Harandi, Richard I. Hartley, and Razvan Pascanu. Block mean approximation for efficient second order optimization. ArXiv, abs/l 1118800400455 2018.
James Martens. Deep learning via Hessian- free optimization. In Proceedings of the 27th International Conference Machine Learning (ICML), volume 951, 2010.
James Martens and Roger Grosse. Optimizing neural networks with kronecker- approximate curvature. In International conference machine learning, pp. 2408-2417, 2015.
James Martens, Jimmy Ba, and Matt Johnson. Kronecker-factored curvature approximations for recurrent neural networks. In International Conference on Learning Representations, 2018.
Manel Martinez- Ramón, Vladimir Koltchinskii, Gregory L. Heileman, and Stefan Posse. fMRI pattern classification using neuroanatomically constrained boosting. Neurolmage, 31(3):1129 1141, 2006.
K. Osawa, Tsuji, Y. Ueno, A. Naruse, C. Foo, and R. Yokota. Scalable and practical natural gradient for large-scale deep learning. IEEE Transactions on Pallern Analysis and Machine Intelligence, pp. 1-1, 2020.
Jeffrey Pennington, Samuel Schoenholz, and Surya Ganguli. Resurrecting the sigmoid in deep learning through dynamical isometry: theory and practice. In Advances in neural information processing systems, pp. 4785-4795, 2017.
Nasim Rahaman, Aristide Baratin, Devansh Arpit, Felix Draxler, Min Lin, Fred A Hamprecht, Yoshua Bengio, and Aaron Courville, On the spectral bias of neural networks. arXiv preprini arXiv:1806.1 08734, 2018
Basri Ronen, David Jacobs, Yoni Kasten, and Shira Kritchman. The convergence rate of neural net- works for learned functions of different frequencies. In H. Wallach, H. Larochelle, A. Beygelzimer, F. d' d'Alché Buc, E. Fox, and R. Gamett (eds.), Advances in Neural Information Processing Systems 32, pp. 4761-4771. Curran Associates, Inc., 2019.
12

---

Under review as a conference paper at ICLR 2021
Andrew M. Saxe. James L. McClelland, and Surya Ganguli. Exact solutions to the nonlinear dynamics of learning in deep linear neural networks. In Yoshua Bengio and Yann LeCun (eds.), 2nd International Conference Learning Representations. ICLR 2014, Banff, AB, Canada, April 14-16, 2014, Conference Track Proceedings, 2014.
Andrew M Saxe, Yamini Bansal, Joel Dapello, Madhu Advani, Artemy Kolchinsky, Brendan D Tracey, and David D Cox. On the information bottleneck theory of deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2019(12):1 Dec 2019.
Nicol Schraudolph, Jin Yu, and Simon Günter. A stochastic quasi-Newton method for online convex optimization. Alstats, 2007.
Ravid Schwartz-Ziv and Alexander A Alemi. Information in infinite ensembles of infinitely-wide neural networks. arXiv preprint 191 2019.
Christopher J Shallue, Jaehoon Lee, Joseph Antognini, Jascha Sohl-Dickstein, Roy Frostig, and George Dahl. Measuring the effects of data parallelism on neural network training. arXiv preprint arXiv: 1.03600, 2018.
DF Shanno, Conditioning of quasi-Newton methods for function minimization. Mathematcss of computation, 1970.
Noam Shazeer and Mitchell Stern. Adafactor: Adaptive learning rates with sublinear memory cost. arXiv preprint arXiv: 1804.04235, 2018.
Ravid Shwartz-Ziv and Naftali Tishby. Opening the black box of deep neural networks via information. arXiv preprint arXiv: 700000000,,0... 2017.
Yu Shyr. Rigorous quantitative sciences integration - the foundation high figh-dimensional genomic research. Clinical and Experimental Metastasis, 29:641-644 143,,, 2012.
Eero P Simoncelli and Bruno A Olshausen. Natural image statistics and neural representation. Annual Review of Neuroscience, 24(1):1193-125 2001.
Jascha Sohl-Dickstein. The natural gradient by analogy to signal whitening, and recipes and tricks for its use. arXiv preprint arXiv: /828, 2012.
Jascha Sohl-Dickstein, Ben Poole, and Surya Ganguli. Fast large-scale optimization by unifying stochastic gradient and quasi-newton methods. International Conference on Machine Learning, pp. 604-612, 2014.
Carsen Stringer, Marius Pachitariu, Nicholas Steinmetz, Matteo Carandini, and Kenneth D. Harris. High-dimensional geometry of population responses in visual cortex. Nature, 571:361-365, 2019.
Peter Sunehag, Jochen Trumpf, S V N Vishwanathan, and Nicol Schraudolph. Variable metric stochastic approximation theory. arXiv preprint arXiv:0908.33 3529, August 2009.
RmsProp: Divide the gradient by a running average of its recent magnitude. COURSERA: Neural Networks for Machine Learning, 2012.
Tieleman and G. Hinton. Lecture 6.5
Naftali Tishby and Noga Zaslavsky. Deep learning and the information bottleneck principle. In 2015 IEFE Information Theory Workshop (ITW), pp. 1-5. IEFF, 2015.
Sharan Vaswani, Reza Babanezhad, Jose Gallego, Aaron Mishkin, Simon Lacoste-Julien, and Nicolas Le Roux. To each optimizer norm, to each norm its generalization, 2020.
Oriol Vinyals and Daniel Povey. Krylov subspace descent for deep learning. arXiv preprint arXiv:1111.4259, 2011.
Martin J. Wainwright. High-Dimensionae Statistics: A Non-Asymptotic Viewpoint. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2019.
Simon Wiesler and Hermann Ney. A convergence analysis of log-linear training. In Proceedings of the 24th International Conference on Neural Information Processing Systems, NIPS' 11, pp. 657-665, USA, 2011 1. Curran Associates Inc.
13

---

Under review as a conference paper at ICLR 2021
Ashia C Willon, Rebecca Roelofs, Mitchell Stern, Nati Srebro, and Benjamin Recht. The marginal value of adaptive gradient methods in machine learning. In Advances in Neural Information Processing Systems, pp. 4148 -4588, 2017.
Lechao Xiao, Yasaman Bahri, Jascha Sohl-Dickstein, Samuel S Schoenholz, and Jeffrey Penning- ton. Dynamical isometry and mean field theory of CNNs: How to train 10,000-layer vanilla convolutional neural networks. arXiv preprint arXiv:1806.0553 053933 2018.
Yuan Yao, Lorenzo Rosasco, and Andrea Caponnetto. On early stopping in gradient descent learning. Constructive Approximation, 26(2):289-315, 2007.
Sergey Zagoruyko and Nikos Komodakis. Wide residual networks. CoRR, abs/1 2016.
Matthew D. Zeiler. ADADELTA: an adaptive learning rate method. CoRR, abs/1212..500 2012.
Guodong Zhang, Chaoqi Wang, Bowen Xu, and Roger Grosse. Three mechanisms of weight decay regularization. arXiv preprint arXiv: 12281, 2018.
Guodong Zhang, James Martens, and Roger B Grosse. Fast convergence of natural gradient descent for over-parameterized neural networks. In Wallach, H. Larochelle, A. Beygelzimer, F. d'Alché- Buc, E. Fox, and R. Garnett (eds.), Advances in Neural Information Processing Systems 32, pp. Curran Associates, Inc., 2019.
Huishuai Zhang, Caiming Xiong, James Bradbury, and Richard Socher. Block-diagonal hessian-free optimization for training neural networks. CoRR, abs/1712.07296, 2017.
14

---

Under review as a conference paper at ICLR 2021
A ISOTROPY OF WEIGHT INITIALIZATION IMPLIES CONDITIONAL INDEPENDENCE
In this section show that for isotropic initial weight distributions,
P(W R) P(W") A R O(d).
(19)
the training activations Zuain depend on the training data X only through the second moment matrix Kirain- This is summarized in Eq. reepeate here for convenience:
I(Z Xuain K
0.
The argument is as follows, the isotropy of the weight distribution implies that the distribution of first layer activations conditioned on the training data is invariant under orthogonal transformations.
P P(Z tiin R.raani)) = P(Z m VR E O(d).
(20)
To derive this we can write the distribution over 70 in terms of the distribution over initial weights, P( P(Z iinnn) = DW P(W)))) Z W Xirain). Here DWO is the uniform measure over the components of W DW We then have
P(Z (rann
D(W)(W W: RXirain))
(OPP((WRT))8(2. W X(rin))
(21)
D Xuain) = P(ZarinnXerann))
Here, 5 denotes the Dirac delta function. To arrive at the second line we defined W := W R and used the invariance of the measure DW The third line follows from the (d)) invariance of the initial weight distribution. Now that we have established the rotational invariance of the distribution over first layer activations we can derive Eq.
By the first fundamental theorem of invariant theory (Kraft & Procesi 1996), the only O(d) invari- ant functions of vectors dimensions are the n² inner products Krain X Jrain Xurain Thus
P P(Z uuain) h (uain) for some function h, and P( P(Z (Xrann K P P(Z Kuain). Eq.
then follows from the definition conditional mutual information.
1 (Z Xuran Kurain)
E Kmm
[PxL Xusinl K || PP (u Kuain ( P(Xuain [uain))]
E Kmm [P(Xenin K DKL (P (Z X K I [{aan)))]]
0.
(22)
B WHITENING IN LINEAR MODELS
Linear models are widely used for regression and prediction tasks and provide instructive laboratory to understand the effects of data whitening. Furthermore, linear models provide additional intuition for why whitening harmful- whitening puts signal and noise directions in the data second moment matrix, F, on equal footing (see Fig. []. For data with a good signal to noise ratio, unwhitened models leamn high signal directions early during training and only overfit noise late times. For models trained on whitened data, the signal and noise directions are fit simultaneously and thus the models overfit immediately.
Consider linear model with mean squared error loss
S(X) Wx, L= -11())
(23)
This loss function is convex. Here we focus the low dimensional case, d < n,, where the loss has a unique global optimum W = X Ymai. The model predictions at this global optimum, fx( = W X, invariant under any whitening transform (2.0.Ip As result, any quality metric
15

---

Under review as a conference paper at ICLR 2021
(loss, accuracy, etc...) for this global minimum is the same for whitened and unwhitened data.
The story more interesting, however, during training. Consider a model trained via gradient flow (similar statements can be made for gradient descent stochastic gradient descent). The dynamics of the weights are given by
dW OL OW W(t) = e W(0) (1 e W
(24)
dt
The evolution in Eq. implies that the information contained the trained weights (t) about the training data X is entirely determined by F and W*. In terms of mutual information, we have
[(W(t); X Frain W*) 0.
(25)
As whitening sets Fanin T, a linear model trained on whitened data does not benefit from the information Firin-
At a more microscopic level, we can decompose Eq. 24 in terms of the eigenvectors, Us of F:
((t) Σ (t), wx(() = w. (1 - e-di)
(26)
We see that for unwhitened data the eigen-modes with larger eigenvalue converge more quickly towards the global optimum, while the small cigen-directions converge slowly. For centered X, F is the feature covariance and these cigen-directions As a result, training on unwhitened data is biased towards learning the top principal directions at early times. This bias is often beneficial for generalization. Similar simplicity biases have been found empirically in deep linear networks (Saxe et al. (014) and in deep networks trained via SGD (Rahaman al., 2018; Ronen et 2019) where networks learn low frequency modes before high. In contrast, for whitened data, F ini and the evolution of the weights takes the form
exactly the principle components of the data.
w (t = e ' (0) + (1 (
(27)
All hierarchy between the principle directions has been removed, thus training fits all directions at similar rate. For this reason linear models trained on unwhitened data can generalize significantly better at finite times than the same models trained on whitened data. Empirical support for this in linear image classification task with random features is shown in Fig B(a)
B. THE GLOBAL OPTIMUM
At the global optimum, W* F-1 X Inin Yurain: the network predictions points be written in few equivalent ways,
fo (Xiea) YT XT F-1
F X Y K+ K test
train Krainxtest
(28)
Here, the + superscript is the pseudo-inverse, and Krainxtes is the whitened train-test data-data second moment matrix. These expressions make manifest that the test predictions at the global optimum only depend on the training data through Kirin and K Kminnxtest
B.2 HIGH DIMENSIONAL LINEAR MODELS
The discussion is very similar in the high dimensional case, d > n. In this case, there is no longer a unique solution to the optimization problem, but there is unique optimum within the span of the data.
W =
X train
Vinin W = (1)
(29)
train
Here, we have introduced the notation || for directions in the span of the training data and 1L for orthogonal directions. Explicitly, if we denote by Vil = {v) ,,,....,,,, E Raxd the non-null eigenvectors of Fazin and V = {Va+1. Unt2, Vd E R(d-n)xd the null eigenvectors, then X Train Vll X WI: WVll, W. WV- and Fl Irain V (VllT.
16

---

Under review as a conference paper at ICLR 2021
The model predictions at this optimum can be written
fa (Xistt = (Xictt - (Xtrin) - Xuaii) T K Xtainxxtsst This is the solution found by GD, SGD, and projected Newton's method.
(30)
The evolution approaching this optimum can be written (again assuming gradient flow for simplicity)
Wi (t)
= t (0) + +(1
(1- - (1-e-tFiie - - Wii W1(t) = W0)
(31)
In terms of the individual components,
e - + (1--
As above, the hierarchy in the spectrum allows for the possibility of beneficial early stopping, while whitening the data results immediate overfitting.
B.3 SUPPLEMENTARY EXPERIMENTS WITH LINEAR LEAST SQUARES
In App.1 we present the same experiment as in Fig. 4 a) at three additional dataset sizes. In all cases, the best test performance achievable by early stopping whitened data worse than unwhitened data.
In Fig. App.2 we study the effect generalization of using the entire dataset of 60000 CIFAR- 10 images to compute the whitening transform regardless of training set size. We call this type of whitening 'distribution whitening' indicate that we interested in what happens when the whitening matrix is approaches its ensemble limit.
In App.3 we compare generalization performance of models trained whitened versus whitened data from two different parameter initializations. Initial distributions with larger variance produce models that generalize worse, but for a fixed initial distribution, models trained on whitened data generally underperform models trained on unwhitened data.
C SECOND ORDER OPTIMIZATION OF WIDE NEURAL NETWORKS
Here consider second order optimization for wide neural networks. In recent years much progress has been made in understanding the dynamics of wide neural networks (Jacot et al. 2018). in particular has been realized that wide networks trained via GD, SGD or gradient flow evolve linear model with static, nonlinear features given by the derivative of the network map at initialization (Lee et al. 2019).
In this section we extend the connection between linear models and wide networks to second order methods. In particular we argue that wide networks trained via a regularized Newton's method evolve as linear models trained with the same second order optimizer.
We consider a regularized Newton update step.
0L
g++1 = 0t - -n--n nn(c11 H)
(32)
00
This diagonal regularization is common generalization of Newton's method. One motivation for such an update rule in the case of very wide neural networks is that the Hessian necessarily rank deficient, and so some form of regularization is needed.
For a linear model, [ineer(x)) 0 g(x).. with fixed non-linear features, g(x), the regularized newton update rule in weight space leads to the function space update.
OL
M (x:) Minncrr (x)
Σ Za. Ximi
1inear (x,, Fa) (el Oiiear ab a ftnneu
(33)
Here, Olinear, is constant kernel, Otineur (2,, xr)
01 05
9 T(x) (()))g(x)))
36
17

---

Under review as a conference paper at ICLR 2021
training examples
training examples
unwhitened whitened
test MSE
768 training examples
2560 training examples
1.2
test MSE
1.0
0.40
0.6
10
10
20
10a
10' 10
101
10'
10*
10'
training time
training
Figure App.1: Whitening data speeds up training reduces generalization in linear models. Here we show representative examples of the evolution of test error with training time in a linear least-squares model where the training set consists of 460, 768, 2560 examples, as labeled. In all cases, while models trained train-whitee whitened data (in green) reach their optimal mean squared errors in smaller number of epochs, they do no better than models trained on unwhitened data of models are indistinguishable as measured by test error. The y-axis in the top row of plots is in log scale for clarity. In all cases, the input dimensionality of the data was 512.
purple). In the large time limit of training,
kinds
For deep neural network, the function space update takes the form.
(z) -f)(x)
Σ
0 x.) (cl Q)
n
of
Iu Pu.2sE Xuis
(34)
112 8
A0 A0'
00,
Mmu=l
Here we have indexed the model weights by = 1... P, denoted the change in weights by A and introduced the neural tangent kernel (NTK), (zx, 05 0f
39
In general Eqs. 33 and 34 lead to different network evolution due to the non-constancy of the NTK and the higher order terms the learning rate. For wide neural networks, however, it realized that the NTK is constant (Jacot et al.) (0188) and the higher order terms in appearing on the second line
vanish large width (Dyer & Gur-Ari 2020 Huang & Yau. 2019 Littwin 2020 Andreassen
& Dyer, Aitken & Gur-Ari)
With these simplifications, the large width limit of Eq. 34 describes the same evolution as linear model trained with fixed features g(x)=
0f(w) 29 1==0, trained via a regularized Newton update.
"These simplifications were originally derived for gradient flow, gradient descent and stochastic gradient descent, but hold equally well for the regularized Newton updates considered here. This can he seen, for example, by applying Theorem I of (Dyer& & Gur-Ari 2020
18

---

Under review as a conference paper at ICLR 2021
linear model with distribution whitening
0.52
GD: unwhitened
GD: train whitened
0.50
GD: full whitened
GD: distribution whitened
test error
0.48
input dimension
0.44
0.42
10a
10a
10
training set size
Figure App.2: Whitening using the entire dataset behaves similarly to conventional whitening, with only slight improvement in performance. Whitening using whitening transform computed the entire CIFAR- 10 dataset of 50000 training and 10000 test images (distribution whitening) improves performance over train and whitening, but does not close the performance gap with unwhitened data. With the exception of the "distribution whitened' line, gradient descent data in this plot is identical to Fig. Ba)
D MLP ON MNIST
Here we present the equivalent of Fig.B(() for an MI. trained on MNIST. Experimental details are given in Appendix[E] Similar to the results in Fig. 3() CIFAR-IO, in Fig.App.4. find that models trained on fully whitened data generalize at chance levels (indicated by test error of 0.9) in the high dimensional regime. Because MNIST is highly rank deficient, this result holds until the size of the dataset exceeds its input rank. Models trained on train-whitened data also exhibit reduced generalization when compared with models trained on unwhitened data, which exhibit steady improvement generalization with increasing dataset size.
E METHODS
E.
MODEL AND TASK DESCRIPTIONS
We describe basic experiment structure, and follow this with descriptions of the four types of models we studied and associated experimental variations. Details are provided the rest of this appendix.
The kernel of all our experiments is as follows: From dataset, we draw a number of subsets, tiling range of dataset sizes. Each subset is divided into train, test, and validation examples, and three copies are made, two of which are whitened. In one case the whitening transform is computed using only the training examples, and in the other using all the data. Note that the test size must be reduced in order to run experiments dataset for full-whitee whiteniinn Models are trained from random initialization on each of the three copies of the data using the same training algorithm and stopping criterion. Test errors and the number of training epochs are recorded and plotted as functions of dataset size.
small datasets, since the test set is considered part of the
Linear Model. We study CIFAR-I0 classification learned by optimizing mean squared error loss, where the model outputs are linear map between the 512-dimensional outputs of four layer convolutional network at random initialization on CIFAR- -0, and their 10-dimensional one-hot labels. This setup is in part motivated by analogy to training the last layer of deep neural network. We solve the gradient flow equation for the time at which the MSE on the validation set is lowest, and report the test error at that time. The experiment was repeated using Newton's 's method.
19

---

Under review as a conference paper at ICLR 2021
linear model with larger variance initializations
GD: unwhitened, variance 0
GD: unwhitened, variance 1/d
GD: train whitened, variance
GD: train whitened, variance 1/d
Input dimension
test error
0.8
0.6
0.4
10a
10a
training set size
Figure App.3: The effect of whitening linear models with non-zero paramefer initialization. Linear models are initialized
parameter variances or 1/d. all cases the test loss is reported for the time during gradient flow training when the model achieves the lowest validation loss. Unwhitened data was scaled to have the same norm accumulated over all samples in the training set as whitened data, for each training set size, to avoid artifacts due to overall input scale. A model output of zero corresponds to test loss of 0.5. All configurations with loss greater than 0.5 doing worse than uninformative prediction of 0. At both initialization scales, the model trained on whitened data performs worse than the model trained on unwhitened data for almost all dataset sizes, while for one dataset size they perform similarly. Data for the variance 0 initialization is identical to Fig. B(a.
Multilayer perceptron. We study fully connected three-layer MLPs MNIST and CIFAR-I0 classification tasks. Training is accomplished using SGD with constant step size until the training accuracy reaches fixed cutoff threshold, at which point test accuracy is measured.
Convolutional networks. Since our theoretical results on the effect whitening apply only to models with fully connected first layer, trained from isotropic initial weight distribution, test whether the same qualitative behavior observed in CNNs trained from a Xavier initialization. We chose the popular wide residual (WRN) architecture (Zagoruyko Komodakis 2016). trained on CIFAR-10. Training was performed using full batch gradient descent with cosine learning rate schedule for a fixed number of epochs. Full batch training was used remove experimental confounds from choosing minibatch sizes at different dataset sizes. A validation set was split from the CIFAR-10 10 training set. Test error corresponding to the parameter values with the lowest validation ептог was reported.
We also trained a smaller CNN (a ResNet-50 convolutional block followed by an average pooling layer and dense linear layer) on unwhitened data with full batch gradient descent and with the Gauss-Newton method (with and without a scaled identity regularizer) to compare their respective generalization performances. A grid search was performed over learning rate, and step sizes were chosen using a backoff line search initialized at that learning rate. Test and training losses corre- sponding the best achieved validation loss were reported. Note that this experiment is relatively large scale: because we perform full second order optimization to avoid confounds due to choosing a quasi-Newton approximation, iterations cubic in the number of model parameters.
20

---

Under review as a conference paper at ICLR 2021
MLP on MNIST
1.0
unwhitened
train whitened
0.8
whitened
dataset size Input rank
test error
0.6
Input dimension
0.4
0.2
0.0
10A
10a
10
10
10a
dataset size
Figure App.4: Whitening MNIST before training negatively impacts generalization in MLPs. Models trained fully whitened data (in blue) unable generalize until the size of the dataset exceeds its maximal input rank of 276, indicated by the solid black vertical line. Regardless of how the whitening transform computed, models trained on whitened data (blue and green) consistently underperform those trained on unwhitened data (in purple).
E.2 WHITENING METHODS
E.2.1 PCA WHITENING
Consider a dataset X E Rdx=, PCA whitening can be viewed two-step operation involving rotation X into the PCA basis, followed by the normalization of all PCA components to unity. We implement this transformation as follows. First, compute the the singular value decomposition of the unnormalized feature-feature second moment matrix XXX
XxT = U.VT,
(35)
where the rank of Σ is min(n,d) d). The PCA whitening transform is then computed as M -- 1/2 VT, where the dot signifies element-wise multiplication between the whitening coefficients, Σ 1/2 and their corresponding singular vectors. When Σ is rank deficient (n d), methods to stabilize the computation of the inverse square root: the addition of noise, or manual rank control. In the former, small jitter is added to the diagonal elements of before inverting it. This was implemented in the experiments in linear models. In the latter, the last d n diagonal elements of 1/1 are explicitly set to unity. This method was implemented in the MLP experiments.
of two
E.2.2 ZCA WHITENING
ZCA (short for pero-phase components analysis) (Bell & Sejnowski 1997) can be thought of as PCA whitening followed by a rotation back into the original basis. The ZCA whitening transform ZCA whitening produces images that look like real images, preserving local structure, For this reason, it is used in the CNN experiments.
M 1/2 VT
E.3 LINEAR MODEL
Dataset composition. The dataset for this experiment was modified version of CIFAR-10, where the images were first processed by putting them through an off-the-shelf (untrained) four layer convolutional network with tanh nonlincarities and collecting the outputs of the penultimate layer. This resulted in a dataset of 512-dimensional images and their associated labels. Both the CIFAR- 10 training and test sets processed in this way. The linear estimator trained to predict one-hot (ten dimensional) labels.
Training sizes ranged from 128 to 5120 examples, randomly sampled from the preprocessed CIFAR- 10 data. For experiments on unwhitened and train- wriie-whtenedd data, a validation set of 10000 images was split from the CIFAR-10 training set, and test error measured the CIFAR-10 test
21

---

Under review as a conference paper at ICLR 2021
set. For experiments on fully whitened data, validation and test sets of 10 images each were split from the CIFAR-10 10 training and test sets, respectively.
Whitening. At each training set size, four copies of the data were made, and three were whitened using the PCA whitening method. For wrainnwhitened data, the whitening transform was computed using only the training examples. For fully whitened data, the twenty validation and test images were included the computation of the whitening transform. For distribution whitened data (Fig.[App.2) the entire CIFAR-10 dataset of 60000 images (train as well test) was used to compute the whitening transform.
Training and Measurements. We used mean squared error loss function. Weights were initialized to all-zeros, except for the data in Fig. App.3] for which initial weights were drawn from a Gaussian with variance 1/d. At each training set size, fifty models (initialized with different random seeds) were trained with full-batch gradient descent, with the optimization path defined by the gradient flow equation. Writing the model parameters as Φ this equation is
(t) x" + tCB t (Ø" (000)
for preconditioner B, feature-feature correlation matrix C. infinite-time solution 6*, and initial iterate g(0), In the case of gradient descent, the preconditioner B is simply the identity matrix.
In order generate the plot data for Fig. 3 a), solved the gradient flow equation for the parameters é that achieved the lowest validation error, and calculated the test error achieved by those parameters. Mean test errors and their inner 80th percentiles across the twenty different initializations and across whitening states were computed and plotted. To make the plots in Fig. (a) and App. we tracked test performance over the course of training on unwhitened and Frain-whitene data.
On writeewh datasets, we also implemented Newton's ' Method. This was done by putting the preconditioner B in the gradient flow equation equal to the inverse Hessian, i.e. (XXT)= The preconditioner was computed once using the whole training set, and remained constant over the course of training. For experiments on whitened data, the data was whitened before computing the preconditioner.
E.4 MULTILAYER PERCEPTRON
E.4.1 ON MNIST
Architecture. We used 784 x 512 x 512 x 10 fully connected network with rectified linear nonlinearity in the hidden layers and a softmax function at the output layer. Initial weights were sampled from normal distribution with variance 10-4
Dataset composition. The term "dataset size" here refers to the total size of the dataset, i.e. counts the training as well test examples. We did not use validation sets in the MLP experiments. Datasets of varying sizes were randomly sampled from the MNIST training and test sets. Dataset sizes were chosen tile the available range (0 to 70000) evenly in log space. The smallest dataset size was 10 and the two largest were 50118 and 70000. For all but the largest size. the ratio of training to test examples was 2. The largest dataset size corresponded the full MNIST dataset, with its training set of 60000 images and test set of 10000 images.
The only data preprocessing step (apart from whitening) that we performed was to normalize all pixel values to lie in the range [0. 1].
Whitening, At each dataset size, three copies of the dataset were made and two were whitened. Of these, one was train- whitened and the other fully whitened. PCA whitening was performed. The same whitening transform was always applied to both the training and test sets.
Training and Measurements. We used sum of squares loss function. Initial weights were drawn from a Gaussian with mean zero and variance 10-4, Training was performed with SGD using a constant learning rate and batch size, though these were both modulated according to dataset size. Between a minimum of 2 and a maximum of 200, batch size was chosen to be a hundredth of the number of training examples. We chose learning rate of 0.1 if the number of training examples was < 50, 0.001 if the number of training examples was 2 10000, and 0.01 otherwise. Models trained to 0.999 training accuracy, at which point the test accuracy was measured, along with
22

---

Under review as a conference paper at ICLR 2021
the number of training epochs, and the accuracy the full MNIST test set of 10000 images. This procedure was repeated twenty times, using twenty different random seeds, for each dataset. Means and standard errors across random seeds were calculated and are plotted in Fig. App.4
For example, at the smallest dataset size of 10, the workflow was as follows. Eight training images were drawn from the MNIST training and two as test images were drawn from the MNIST test set. From this dataset, two more datasets were constructed by whitening the images. In one case the whitening transform was computed using only the eight training examples, and in another by using all ten images. Three copies of the MLP were initialized and trained on the eight training examples of each of the three datasets to a training accuracy of 0.999. Once this training aceuracy was achieved, the test accuracy of each model on the two test examples, and on the full MNIST test set, was recorded, along with the number of training epochs. This entire procedure was repeated twenty times.
Computation of the input rank of MNIST data. MNIST images are encoded by 784 pixel values. However, the input rank of MNIST is much smaller than this. To estimate the maximal input rank of MNIST, at each dataset size (call it n) we constructed twenty samples of n images from MNIST. For each sample, we computed the 784 x 784 feature-feature second moment matrix F and its singular value decomposition, and counted the number of singular values larger than some cutoff. The cutoff was 10 5 times the largest singular value of F for that sample. We averaged the resulting number, call it r, over the twenty samples. If r = n, we increased n and repeated the procedure, until we arrived at the smallest value of where > n, which was 276. This is what call the maximal input rank of MNIST, and is indicated by the solid black line in the plot in Appendix D
E.4.2 ON CIFAR-10
The procedure for the CIFAR- 10 experiments was almost identical to the MNIST experiments described above. The differences are given here.
The classifier was of shape 3072 x 2000 x 2000 x 10 - slightly larger in the hidden layers and of necessity in the input layer.
The learning rate schedule was as follows: 0.01 if the number of training examples was S 504, then dropped to 0.005 until the number of training examples exceeded 2008, then dropped to 0.001 until the number of training examples exceeded 10071, and 0.0005 thereafter.
The CIFAR-10 dataset is full rank the sense that the input rank of any subset of the data equal to the dimensionality, 3072, of the images.
E.4.3
FIG. B), APP.4 PLOT DETAILS
In Figs. 3b) and App.4. for models trained on unwhitened data and train- data, we have plotted test error evaluated on the full CIFAR- 10 and MNIST test sets of 10000 images. For models trained on fully whitened data, have plotted the errors on the test examples that were included in the computation the whitening transform.
E.5 CONVOLUTIONAL NETWORKS
E.5.1 WRN
Architecture. We use the ubiquitous Wide ResNet 28- architecture from (Zaoruykoo & Komodakis 2016). This architecture starts with convolutional embedding layer that applies a 3 x 3 convolution with 16 channels. This is followed by three "groups", each with four residual blocks. Each residual block features two instances of a batch normalization layer, a convolution, and a ReLUU activation. The three block groups feature convolutions of 160 channels, 320 channels, and 640 channels, respectively. Between each group, a convolution with stride 2 is used to downsample the spatial dimensions. Finally, global-average pooling is applied before a fully connected readout layer.
Dataset composition. We constructed thirteen datasets from subsets of CIFAR-10 The thirteen training sets ranged in size from 10 to 40960, and consisted of between 2 and 2 examples per class. In addition, we constructed a validation set of 5000 images taken from the CIFAR- 10 training set which used for early stopping. Finally, we use the standard CIFAR-10 test set to report
23

---

Under review as a conference paper at ICLR 2021
performance.
Whitening, We performee ZCA whitening using only the training examples to compute the whitening
transform.
Training and Measurements. We used a cross entropy loss and the Xavier weight initialization. We performed full-batch gradient descent training with learning rate of 10-3 until the training error was less than 10-3 3 We use TPUv2 accelerators for these experiments and assign one image class to each chip. Care must be taken aggregate batch normalization statistics across devices during training. After training, the test accuracy at the training step corresponding to the highest validation accuracy was reported. At each dataset size, this procedure repeated twice, using two different random seeds. Mcans and standard errors across seeds were calculated and are plotted in Fig. 3(c).
E.5.2 CNN
Architecture. The network consisted of single ResNet-50 convolutional block followed by a flattening operation and two fully connected layers of sizes 100 and 200, successively. Each dense layer had a lanh nonlinearity and was followed by a layer norm operation.
Dataset composition. Training sets were of eleven sizes: 10, 20, 40, 80, 160, 320, 640, 1280, 2560, 5120, and 10240 examples. A validation set of 10000 images was split from the CIFAR-10 training set.
Training and Measurements. We used a cross entropy loss. Initial weights were drawn from Gaussian with mean zero and variance 10-4, Training was accomplished once with the Gauss-Newton method (see (Botev et al. 2017) for details), once with full batch gradient descent, and once with a regularized Newton method. With a regularizer À E [o, 1], the usual preconditioning matrix B This method interpolates between pure Gauss-Newtor (A 0) and gradient descent (A 1). In the Gauss-Newton experiments, used conjugate gradients to solve for update directions; the sum of residuals of the conjugate gradients solution was required to be at most 10
of the Gauss-Newton update was modified as ((1 B) + A1)
For the gradient descent and unregularized Gauss-Newton experiments, at each training set size, ten CNNs were trained beginning with seven different initial learning rates: 2-8 2-6 2,,,,-2,,,, 1, 4, and 16. After the initial learning rate, backtracking line search was used to choose subsequent step sizes. Models were trained until they achieved 100% training accuracy. The model with the initial learning rate that achieved the best validation performance of the seven was then selected. Its test performance on the CIFAR-10 10 test set was evaluated at the training step corresponding to its best validation performance. The entire procedure was repeated for five random seeds. In Fig.33dl we have plotted average test and validation losses over the random seeds as functions of dataset size and training algorithm. In Fig. c)., we have plotted an example of the validation and training performance trajectories over the course of training for training set of size 10240.
For the regularized Gauss-Newton experiment, the only difference is that we trained one CNN at each initial learning rate per random seed, and then selected the model with the best validation performance. In Fig.5] we have plotted average metrics over the five random seeds. Errorbars and shaded regions indicate twice the standard error in the mean.
24


Reviews:
[{"review_id": "pAITO92RrT", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Summary\n\nThe authors analyse the training dynamics of a machine learning model consisting in a linear unit, followed by any parametrized function. The authors in particular focus on the impact of whitening  the data beforehand or using second order methods. They show that the learned parameters of the model only depend on the training data through its Gram matrix. Since whitening trivializes the Gram matrix, the authors argue that whitening destroys important information.\n\nMajor comments\n- The article is well written, the arguments are well presented and easily understood.\n- The main message of the paper, contained in Fig. 3, is easily reproduced with a few lines of code.\n- The paper sheds an interesting light on the generalization properties of second order methods.\nThm.2.2.1 and 2.2.2 treat the initialization of the weights as random variables. I believe that it makes them rather useless for practical applications, because in practice the machine learning model will only be initialized once. Of course, the theorems also apply if we assume that the initial weights are zero (or close to zero), which is still a very interesting case. In the experiments description of fig.3. it would be worthwhile to better describe the initialization strategy for the linear weights. For instance, I used as X the load_digits dataset in scikit-learn, as Y a one hot encoding of the target, and a simple linear model with MSE loss $f(W) = \\|WX - Y\\|^2$, and managed to get the same fig.3.a as the authors, but only if I initialize the weights very close to 0, or at 0.\n- I think that Sec.2.4 is too shallow. First, it should be clearly stated that eq.14 only works for MSE loss with a purely linear model. Second, I think that another important concept which is not mentioned in the article is that early stopping is similar to regularization of the parameters, which is why the reported ‘test error’ in the experiments is lower than the test error obtained by perfectly minimizing the train error. See e.g. Yao, Yuan, Lorenzo Rosasco, and Andrea Caponnetto. \"On early stopping in gradient descent learning.\" Constructive Approximation 26.2 (2007): 289-315.\n- In Sec.2.5, the authors consider Newton’s method with MSE loss on a linear problem, which converges in just one step with $\\eta=1$. This should be acknowledged, and maybe it would be easier to defend the point by letting $\\eta \\to 0$ instead.\n\nMinor comments\n- The meaning of ‘test error’ in the figure legend is a bit vague, and I think it should rather be replaced by ‘best test error during training’ or something similar.\n- In fig.4.b, does training epochs mean ‘number of epochs to reach the best test error’?\n\nMisc\n- What does WRNs mean?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "kzhkon3fu7X", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 7, "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "## Overview\n---\nIn supervised learning tasks, it is common in practice to apply a *whitening* transformation to remove correlations between input features. This can improve the conditioning of the underlying data manifold, enabling faster convergence. This paper shows  that for a large class of models --- models $f$ consisting of a fully-connected layer followed by an arbitrary parameterized function, $f(X) = g_\\theta(WX)$ --- data whitening removes all information that is relevant for generalization. Furthermore, this has implications for the generalization ability of second-order methods such as Newton's method due to a well-known equivalence between Newton's method and steepest-descent applied to whitened data. The effects suggested by the presented theory are verified empirically, and the are additionally observed in convolutional neural networks, suggesting that the phenomenon could apply more broadly to more complicated connectionist models as well.\n\n**Overall, I recommend that the paper be accepted**. The theoretical results are interesting and potentially high-impact, and the writing clarity was excellent throughout. My main reservation about the paper is that it's not clear to me which insights are being proposed as novel, and among those, which actually are novel. In particular,\n- **Section 2.5**: The relationship between Newton's method and data whitening is well-known. Does section 2.5 include any novel insights, or is this included for completeness? If it's the latter it seems like it would be better-placed in an appendix; the fact that the main results relate also to second-order methods could then be noted in the discussion\n- **Generally** speaking, how does what's already known from e.g. dimensionality reduction and PCA play into this? As mentioned in the paper, whitening is essentially putting the signal and noise in the data on equal footing. From a principal components perspective, it's as if you're forcing the model to consider all components to be equally predictive, which would clearly harm generalization when the data has strong feature correlations. Is there truly no prior result of this kind in that literature? It seems quite fundamental, and my concern is that this phenomenon might be already well-known under different terminology in another literature. \n\n*(The following question is out of scope but I think could potentially increase the impact of the paper a great deal)* Do you suspect these issues hold also for the online second-order methods, such as Online Newton Step and AdaGrad? If so, adding some discussion about this could potentially increase the impact of this work since AdaGrad (and it's heuristic descendants Adam, RMSProp etc.) are by-far the most common algorithms used for optimizing neural networks in practice\n\n## Clarifications\n---\n- **Page 4**: W is isotropic, and whitening makes X isotropic, so that Z is isotropic, so intuitively the combination of whitening and isotropic initialization results in trying to make predictions from isotropic noise. Is it specifically the *combination* of whitening and isotropic initialization that's the problem? The paper seems to be really centered around the whitening, when it seems to be the specific combination of the two rather than whitening alone. Or is there a nuance I'm missing here?\n- **Page 8**: *\"We therefore believe that regularized Gauss-Newton should be viewed as discarding information in the\nlarge-eigenvector subspace\"*. I'm not sure I understand what is being said here. Wouldn't this suggest that discarding principle components is beneficial? this seems to run contrary to a lot of the dimensionality reduction literature. \n\n\n## Minor Comments (which did not influence my score but could improve clarity)\n---\n- **Page 2**: *\"Our result is not restricted to neural networks, and applies to any model in which the input is transformed by a dense matrix multiply with isotropic weight initialization\"* \n should read *dense matrix with isotropic weight initialization*?\n- **Page 2**: It is not really necessary to list 34 (!!) papers on second-order optimization in a single sentence; there are plenty of surveys on the topic that could be linked instead\n- **Page 7, Figure 4**: *\"Linear models trained on whitened data optimize faster, but their best test accuracy is always worse\"*. \nThis could use some minor rephrasing to say that the best test accuracy *was* always worse, as this conclusion is about this specific problem rather than for all problems generally\n- **Page 8**: \n *\"Regularized Gauss-Newton optimization acts similarly to unregularized Gauss-Newton in the subspace spanned by eigenvectors with eigenvalues larger than λ/(1 − λ), and similarly to steepest descent in the subspace spanned by eigenvectors with eigenvalues smaller than λ/(1 − λ)\"*\nThis fact is not immediately obvious, so a citation would be helpful here (or potentially a link to an appendix if it's not a well-known result)\n- **Page 14, appendix A**: The integral notation here is unclear to me; what kind of integral is this supposed to be? what is delta?\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "FwgXvV30lBO", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 5, "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 shows theoretical and empirical evidence that under some conditions, whitening the input data and second-order methods may hurt the generalization performance. The paper is well written with good intuitions but overclaims its results. The theoretical results are limited to specific cases, and the experimental results would benefit from systematic ablation studies. All in all, I do not think that the paper provides sufficient evidence that justifies its title and main message of the paper. Detailed review below. \n\n- In Section 2.1, \"the trained model depends on the training data only through K\", this is technically incorrect, since there is a dependence on y_train and the Z_train is independent of X_train, only when conditioned on both K_train and y_train. Since whitening only affects K_train, there still might be some information in y_train, especially for the case of data realizable by the model. Please clarify this. \n\n- In Section 2.3, the statement \"whitening hurts generalization\" is true only for high-dimensional datasets, where the input dimension > number of samples. I agree that such datasets (arising for example in genetics) are important, this is not the typical case where neural networks are used. For example, for all vision tasks, d < n. Please explicitly say this. \n\n- In Section 2.4, please also consider d > n case. This is more important because there are multiple solutions, even in the linear case, and whitening may hurt generalization. For the d < n case analyzed in the paper, for a linear model, for most losses, the optimization problem is strictly convex and a unique solution. This is hardly a claim justifying that \"whitening hurts generalization\", it is an optimization problem and is orthogonal to the paper. For convex problems with a unique solution, there is no reason to early stop the optimization. The convergence rate is linear implying that the solution is reached quickly and this result is not interesting, either from an optimization/generalization perspective. Moreover, such a claim is only valid for the squared loss, and not, for example, the logistic loss. Please clearly explain this. \n\n- In Section 2.5, the paper claims that \"unregularized second-order methods have poor generalization\", but as the authors admit themselves, second-order methods are rarely used without regularization, again making this result not practically important. Moreover, there have been second-order methods (KFAC for example) that employ regularization, approximations to the Hessian and generalize well. The statement \"second-order information destroys generalization\" is therefore an overclaim. \n\n- Moreover, this section focuses on the squared loss with a linear model. If n > d, then Newton's method converges to the min-norm solution, same as GD. For d > n, the solution of Newton's method lies in the span of the training data (if we use the pseudo-inverse for the Hessian or add a small regularizer) and also converges to the min-norm solution, meaning in both cases, its generalization is as good as GD. Again, the behaviour for other losses is not clear. \n\n- In Section 3, for the experimental results, there are numerous confounding factors that need to be controlled for. For example, is the optimization deterministic or stochastic? We know that stochastic methods typically generalize better. How is the learning rate selected? Is there a warmup phase? These factors play an important role in the generalization. Similarly, both the optimization method and the loss function also influence the generalization. Is there regularization, either L2 or L1 in the case when d > n (this is typically done for high dimensional datasets). Please explain how did you control for these factors. \n\n- In Figure 3(a), what is the effect of using a regularized Newton method? What if you run a more standard second-order method like KFAC?\n\n- In Figure 5, the paper shows \"Regularized second-order methods can train faster than gradient descent, with minimal or\neven positive impact on generalization\". This contradicts the paper's title. As the authors claim, when done without regularization, second-order methods can harm generalization, but when used with proper regularization, second order methods help. Like I said before, there are a number of confounding factors and the story is not as simple. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "-dwA5KqjxVC", "reviewer": "AnonReviewer2", "summary": "", "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": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "Topic: whitening destroys generalization\n\n\nmain contribution\n\nThis work offers a mutual information perspective to explain the relations between whitening/second-order optimization and generalization.\n\nStrength\n\n- The perspective is interesting and a bit intriguing. But many discrepancies may need clarifications.\n\nWeakness\n\n- The title and the sentiment of the paper may be misleading. It is scary at first glance, but the conclusion and experiments do not really support the claim “destroy”. It may be important to keep the title accurate other than eye-catching.  The authors may argue “can” is the key in the title, but the reviewer feels this may be a bit too subtle.\n\n- Conditional independence and generalization. The theorems established a certain conditional independence between training features, the model, and the test data. The conditional independence is derived using gradient descent of the whitened data. This is understandable, but the implication on generalization is not crystal clear.\n\n- The claims may need more explanation and be better represented; some simple examples may suggest different conclusion. For example, the reviewer considered a simple least squares problem\n\nmin_theta ||y-X*theta||^2 with whitened X\n\nthe solution is theta_opt = X^T*y, which is clearly dependent with X, even if y is revealed.  If the training set changes, the learned theta changes.  The reviewer wonders if this can be explained by the theorems in the paper – or did the reviewer miss something (response is welcome here)?\n\n- The above leads to another question: The derivation of the work relies on (4) and (5), but either of which fully expressed the gradient. The impression from there is the updates are dominated by the covariance matrices and if the covariance matrices are identity, then there is no information about the training data passed through the training process. This may not be true, if, again, consider the least squares problem, where the gradient is\n\n     grad = X’*X theta – X’*y\n\nwhere the second term is still data-dependent. In particular, the claim “To establish this result, we note that the first layer activation at initialization, Z0 train, is a random variable due to random weight initialization, and only depends on Xtrain through Ktrain:” The last sentence is a bit questionable to the reviewer. \n\n- There may be some clarity issues. For example, (8) is not easy to understand. In the test stage, why is there still a gradient step performed? The test stage should not involve any optimization. This may be clarified.\n\n- Basic generalization theorem suggests that generalization is only related to function class’s complexity, but not the correlation among the coordinates of the data samples. As long as the training and test data are sampled from the same distribution, it is hard to see, from classic generalization analysis viewpoint, why using whitening or second-order methods can destroy generalization. The claim from this work is contradicting to what we learn from textbooks, e.g., Shalev-Shwartz, Shai, and Shai Ben-David. Understanding machine learning: From theory to algorithms. Cambridge university press, 2014.\n\nIt may be good that the authors compare their results with classic results, e.g., those based on uniform convergence, under some function hypothesis complexity measures (e.g., finite class, VC dimension or even Radamacher complexity). The classic proofs of generalization are insensitive to data whitening or algorithm design, and thus the reviewer feel that there may be a big gap to fill if the claims of this work holds.\n\n- The main results claim that whitening is harmful, the simulation may have suggested otherwise. From most of the figures, the generalization error becomes better and better when the sample size increases. Note that when the sample size increases, the sample correlation matrix converges in probability to the ensemble mean, and the whitening could be performed in a more accurate way. This set of results may suggest that, if whitening is done accurately, then it is fine. When the sample size is small, whitening cannot be done very accurately since sample correlation is not accurately estimated. \n\nThe reviewer’s understanding is that the high test error with small sample size is unlikely an effect of whitening, but *inaccurate* whitening, since more noise was brought into the training process. But when the whitening step is performed without too much noise, generalization only depends on function class used and the number of samples, per classic generalization theories. This interpretation seems more consistent with classic generalization theory. The authors may hope to comment on this.\n \n\n------- after the discussion period ------\n\nI would like to thank the authors for the reply, clarification, and additional experiments. Although I do like the perspectives revealed in this work, many points are still quite unclear to me. For example, the theory seems not be able to explain why whitening does not hurt testing when sample size is large, as demonstrated in the paper.  This work also does not draw connection between sample size and generalization error, which may make the claims a bit incredible. I would encourage the authors to work towards this direction and solidify the contribution.\n\n", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper suggests that whitening the data harms generalization and optimization performance when learning models of the form h(W x) i.e. those that are based on a linear projection of the inputs (which includes DNNs for instance). The main concern of the reviewers is that their theoretical developments were not that convincing; it seemed more along the lines of providing some specific anecdotes. But more broadly, the caveat is that their development seems very simple: their results in high-dimensional settings (where d = dim(x) > number of samples n) is not that relevant since vanilla whitening is anyway fraught in such high-dimensions, since the sample covariance matrix is not a good estimator in high dimensions anyway. And when n > d, their result focuses on linear models, where they say that whitening reduces information about the singular vector directions where the input data might mostly lie on. But if the data lies on a lower dimensional linear manifold, then whitening is again fraught: the covariance matrix is singular. The linear manifold assumption also seems very specific given the general title of the paper. Overall, the paper needs to narrow their focus on specific settings where whitening is harmful, but the specific settings above in and of themselves do not necessarily say anything other than to estimate the covariance matrix carefully before doing whitening.

Decision: Reject