Venue: ICLR 2022 Conference

Reviews:

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The manuscript considers the use leave-one-out error to analyse the generalization ability of one-versus-all multi-class classification models that can be expressed as multiple-output ridge regression models. As examples of such models, the authors review certain variations of neural networks. Specific attention is given on the double descent phenomenon showing that the traditionally considered U-shaped curve demonstrating the trade-off between underfitting and overfitting areas can be extended over the interpolation point after which the generalization ability again tends to improve. The spiking effect of the generalization error is derived from the closed form solutions of the leave-one-out computations for ridge regression based methods.

main_review: The main novelty of the manuscript is the characterization of the double descent behavior of ridge (or ridgeless) regression based multi-class classification in terms of its closed form leave-one-out formulations and spectral decomposition of the kernel matrix. This provides a simple and intuitive insight to this phenomenon, and demonstrates how the leave-one-out error spikes at interpolation point with quite mild assumptions.

The various forms of leave-one-out computations for ridge regression are quite well known and therefore do not provide that much novelty, see
http://128.30.100.62:8080/media/fb/ps/MIT-CSAIL-TR-2007-025.pdf
for a summary and especially the multi-class classification has been implemented in several software libraries such as
https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.676.9100&rep=rep1&type=pdf
and
http://jmlr.org/papers/v17/16-470.html
The details concerning the "ridgeless" case may be less well known.

While the authors intent is to connect the analysis to the recent deep neural networks research, it makes the overall story somewhat confusing, and focusing to the leave-one-out computations of ridge regression only, without NTK etc., would have made considerably sharper message. In addition, the results should be put into context of the other results concerning linear regression presented by Bartlett et al. (2020), Mei and Montanari (2021), etc. that the authors already cite.

summary_of_the_review: The mathematics is clear and convenient to read but the overall story is somewhat confusing due to the connections to neural networks and some other branches that do not contribute too much to the main message. The closed form solutions of the leave-one-out computations are not very novel and the most can be straightforwardly derived from the existing literature. I find the idea of considering the double descent behavior emerges from the closed form leave-one-out formulations to be interesting and it may deserve more attention.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: This paper investigates leave-one-out (LOO) error as a generalization measure for wide, deep neural networks using the correspondence to the NTK.  The authors show LOO error also shows behaviors in DNN such as random label fitting, double descent and transfer learning. 

Specific contributions claimed by the authors are: 
- Extend LOO error for multi-class setting and closed-form formula for LOO accuracy
- Demonstrate empirically LOO loss and accuracy capture generalization ability of deep learning in variety of settings
- Utility of LOO on practical networks predicting transfer performance
- Utilize the mathematical form of LOO loss to derive insights into double descent and the role of regularization

main_review: Strength:

- Understanding generalization in deep learning remains one of the most important questions in deep learning theory. Studying the generalization ability of deep neural networks through LOO error is an interesting direction opened up by correspondence to kernel methods. As authors state, the study of LOO error in deep learning is quite underexplored and could be a promising direction. 

- Demonstrated agreement is quite good and indicates LOO metrics can be useful in kernel regression. 

- The paper is clearly written with good organization of presentation. 

Weakness:

- There are many other generalization measures that could be compared to LOO error. Among all of them, why is LOO metrics preferred?This is not clearly answered since there’s no comparison. For example, pure validation split which is used in common practice (e.g. set aside 10% of the MNIST/CIFAR-10 training set). I believe all the phenomena observed by the authors could also be obtained using this metric without extra compute burden vs LOO (both still require O(n^3) computation for inference and require O(n^2) kernel element computations). In that case why is LOO a more interesting metric? (This can also extend to k-fold CV (in this case computation can be more expensive), Generalized cross validation, KARE (Jacot et al., NeurIPS 2020) … 

- Another weakness is that the author is ignoring the computational cost of kernel computation. While FC based kernels used in the experiments often have negligible compute cost to build kernel K, for more realistic convolutional kernel with pooling would require O(100)- O(1000) GPU hours for CIFAR-10, and for the examples ResNet-152 on ImageNet would be naively 30k times more considering O(d^2 N^2) scaling which is still inefficient. Moreover, considering O(N^3) computation needed for computing A, the example case of estimating LOO error is challenging in the kernel case as well. 

- One aspect I’m struggling to see is whether the observed agreement is surprising or more-or-less expected.  One source of uncertainty is that, as far as the reviewer can tell, test performance agreement comparison is made on the “kernel” side not necessarily on the finite width NN. All the good empirical agreement between A_{Test} and A_{LOO} just means that for doing ridge regression with neural kernels LOO estimates are good estimators for test performance. Predicting generalization performance of deep neural networks still hinges on test prediction with kernels matching finite networks. This works for some idealized cases but one needs to be subtle as demonstrated in [Lee et al., NeurIPS 2020]. 

- To me, first contribution regarding multi-class setting expression is a straightforward application of well known LOO prediction in kernel regression to the setting of multi-class classification as regression thus does not seems sufficiently significant. 

- The paper fails to cite the main library used for empirical evaluations: (Neural Tangents library: [Novak et al., ICLR 2020]). Few other references should be added (suggested below in corrections)

Corrections:

- In related work, for the GP correspondence, [Lee et al., 2018] should be co-cited with [Matthews et al., ICLR 2018] and [Neal 1994] (for a single hidden layer).
- Also for extension to various architectures consider citing ([Garriga-Alonso et al., ICLR 2019], [Novak et al., ICLR 2019] for Conv and [Hron et al., ICML 2020] for self-attention and [Yang 2019, 2020] with Tensor programs)
-In section 3: treating classification as a regression task for common benchmarks for infinite width kernels started in [Lee et al., 2018] where they provide justification for doing it. See also [Hui & Belkin ICLR 2021] for using squared loss in practical DL workloads. 
- Why binarize the MNIST dataset in section 4.3? (meant two digit (binary) classification? Inferring from 0.5 accuracy): note binarized MNIST often means that input pixels are binarized to 0/1.


Nit:
- Please, include references in the main submission. Instructions for ICLR 2022 submission were to include both references and the appendix in the main file. 

-----------------------------------------------
Post rebuttal: Thank you for the response. I've read the clarification by the authors and interaction with other reviewers. With some of the improvements, I'm ok to support acceptance based on authors showing interesting generalization phenomena in DL using LOO error on kernels. I've raise my score. 
summary_of_the_review: This paper studies generalization of deep learning with LOO error using neural kernels. This is a relatively novel tool that has not been thoroughly explored in deep learning theory and opens up a new window of studying generalization properties of wide neural networks. There are still some questions regarding the effectiveness or usefulness of the proposed metric detailed above.  With current limitations, the paper is borderline and leaning rejection. However if authors could clarify some of the doubts, happy to move up the score for acceptance.
review_title: null

final_score: rating: 6: marginally above the acceptance threshold
review_content: summary_of_the_paper: The paper proposes to approach the generalization prediction problem in the domain of big neural networks using the classical notion of leave-one-out (LOO) error. Such metric allows to find generalization error/accuracy using only the training dataset. The authors demonstrate, that following the results presented earlier, one can derive a closed form for LOO error/accuracy for multiclass classification tasks and kernel space, thus allowing not to run expensive calculations. Empirically, authors investigate NTK generalization properties, in the context of noisy labels and double descent investigation. They also demonstrate accuracy prediction for fine-tuning task on neural networks.
main_review: The idea to propose an alternative view on the generalization error estimation for deep learning is interesting and up to my knowledge novel. The proposed approach to avoid computational burden based on the closed form calculation of LOO error/accuracy makes sense when connected to the view of neural networks as NTK. 

It is hard to judge the novelty of the closed form for LOO error/accuracy in multi-class setup, since (i) the loss considered is very exotic, being a sum of MSE of each element of a prediction vector compared to each element of the one-hot-encoded label (ii) there are multiple works deriving bounds on LOO for kernel machines (e.g., [1], [2], [3], [4]) none of which are mentioned in the related work. (i) leads to the fact that the central theorem of the paper follows from the cited work of M.Stone (1974) since there a general regression task is considered.

The Settings and Background section requires a lot of attentive reading out since the formal definitions are very sloppy. Some of the multiple points: {i} f* and y* are never defined (ii) accuracy is defined as "number of instances with correct prediction", but formalized to be in real numbers (iii) a training set S is defined as subset of all n-length sequences of X, when it is just one element of it - and should contain targets as well (iv) compact form of writing f is changing from reducing S, then to reducing \lambda. All these inconsistencies make it very hard to follow the formal flow of the paper. Analogously, the setup with neural networks does not specify that only fully-connected networks are considered.

My main concern though is the experimental setup. All of the experiments (except for one) and all the insights in generalization and double descent are produced for the kernel machines and not for neural networks. In my opinion this renders the claim of the paper contribution as generalization insights into deep learning models incorrect. While this still can be a valuable contribution to kernel optimization, in this current formulation I cannot agree with the contribution. In particular, for double descent experiment, the conclusion is that exactly the training size defines the spike in the complexity/error curve, which does not seem to be valid for neural networks.

Also I doubt the setup of the noise experiment, where LOO error peaks into the true label - this somehow makes the setup unfair since the generalization gap is not estimated from the training set only in such case.

Finally, I wonder why transfer learning experiments do not report the test loss approximation by LOO error, but includes the random initialization experiment, which is unrelated to the current work.


[1] Strobl, Eric V., and Shyam Visweswaran. "Deep multiple kernel learning." 2013 12th International Conference on Machine Learning and Applications. Vol. 1. IEEE, 2013.

[2] Dhar, Sauptik, Vladimir Cherkassky, and Mohak Shah. "Multiclass learning from contradictions." Advances in Neural Information Processing Systems 32 (2019): 8400-8410.

[3] Passerini, Andrea, Massimiliano Pontil, and Paolo Frasconi. "From Margins to Probabilities in Multiclass Learning." ECAI 2002: 15th European Conference on Artificial Intelligence, July 21-26, 2002, Lyon France: Including Prestigious Applications of Intelligent Systems (PAIS 2002): Proceedings. Vol. 77. IOS Press, 2002.

[4] Tuda, Koji, et al. "Learning to predict the leave-one-out error of kernel based classifiers." International Conference on Artificial Neural Networks. Springer, Berlin, Heidelberg, 2001.

summary_of_the_review: Based on the concerns with the experimental setup and what exactly it shows I recommend to review the perspective at which the results are presented. In the current form the paper cannot be accepted.

---
Based on the authors' explanations and editions of the paper I change my score.
review_title: null

Meta-review: This paper proposes to use LOO to characterize the generalization error of neural networks via the connection between NN and kernel learning. The reviewers find the new results interesting. The meta reviewer agrees and thus recommend acceptance.
Decision: Accept (Poster)