Venue: ICLR 2021 Conference

Reviews:

final_score: rating: 4: Ok but not good enough - rejection
review_content: 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. 

- 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. 

- 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. 

- 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. 

- 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. 

- 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. 

- 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. 

- 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?

- In Figure 5, the paper shows "Regularized second-order methods can train faster than gradient descent, with minimal or
even 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. 
review_title: Under *some* conditions, whitening and second order methods *may* not generalize well

final_score: rating: 4: Ok but not good enough - rejection
review_content: Topic: whitening destroys generalization


main contribution

This work offers a mutual information perspective to explain the relations between whitening/second-order optimization and generalization.

Strength

- The perspective is interesting and a bit intriguing. But many discrepancies may need clarifications.

Weakness

- 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.

- 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.

- 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

min_theta ||y-X*theta||^2 with whitened X

the 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)?

- 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

     grad = X’*X theta – X’*y

where 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. 

- 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.

- 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.

It 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.

- 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. 

The 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.
 

------- after the discussion period ------

I 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.


review_title: Derivation seems suspicious; needs clarification

final_score: rating: 7: Good paper, accept
review_content: Summary

The 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.

Major comments
- The article is well written, the arguments are well presented and easily understood.
- The main message of the paper, contained in Fig. 3, is easily reproduced with a few lines of code.
- The paper sheds an interesting light on the generalization properties of second order methods.
Thm.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.
- 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.
- 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.

Minor comments
- 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.
- In fig.4.b, does training epochs mean ‘number of epochs to reach the best test error’?

Misc
- What does WRNs mean?

review_title: An interesting analysis of why whitening and second order methods usually lead to worse generalization than first order methods.

final_score: rating: 7: Good paper, accept
review_content: ## Overview
---
In 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.

**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,
- **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
- **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. 

*(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

## Clarifications
---
- **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?
- **Page 8**: *"We therefore believe that regularized Gauss-Newton should be viewed as discarding information in the
large-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. 


## Minor Comments (which did not influence my score but could improve clarity)
---
- **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"* 
 should read *dense matrix with isotropic weight initialization*?
- **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
- **Page 7, Figure 4**: *"Linear models trained on whitened data optimize faster, but their best test accuracy is always worse"*. 
This 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
- **Page 8**: 
 *"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 − λ)"*
This 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)
- **Page 14, appendix A**: The integral notation here is unclear to me; what kind of integral is this supposed to be? what is delta?

review_title: The paper is well-executed and has interesting implilcations, but I have concerns that the results might already exist under different terminology

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