Generalization Through the Lens of Leave-One-Out Error
Authors: Gregor Bachmann
Thomas Hofmann
Aurelien Lucchi
Venue: ICLR 2022 Poster (2022)

Abstract: Despite the tremendous empirical success of deep learning models to solve various learning tasks, our theoretical understanding of their generalization ability is very limited. Classical generalization bounds based on tools such as the VC dimension or Rademacher complexity, are so far unsuitable for deep models and it is doubtful that these techniques can yield tight bounds even in the most idealistic settings~\citep{nagarajan2019uniform}. In this work, we instead revisit the concept of leave-one-out (LOO) error to measure the generalization ability of deep models in the so-called kernel regime. While popular in statistics, the LOO error has been largely overlooked in the context of deep learning. By building upon the recently established connection between neural networks and kernel learning, we leverage the closed-form expression for the leave-one-out error, giving us access to an efficient proxy for the test error. We show both theoretically and empirically that the leave-one-out error is capable of capturing various phenomena in generalization theory, such as double descent, random labels or transfer learning.
Our work therefore demonstrates that the leave-one-out error provides a tractable way to estimate the generalization ability of deep neural networks in the kernel regime, opening the door to potential, new research directions in the field of generalization.

Published as a conference paper at ICLR 2022
GENERALIZATION THROUGH THE LENS OF LEAVE- ONE-OUT ERROR
Gregor Bachmann" 9 Thomas Hofmann", and Aurélien Lucchi
*Department of Computer Science, ETH Zürich, Switzerland Department of Mathematics and Computer Science, University of Basel, (gregor. baachaann thomas moffammm@@innaa ethz. ch aurelien. lucchi@uniiaar ch
ABSTRACT
Despite the tremendous empirical success of deep learning models to solve vari- ous learning tasks, our theoretical understanding of their generalization ability is very limited. Classical generalization bounds based on tools such as the VC di- mension Rademacher complexity,
far unsuitable for deep models and it is doubtful that these techniques can yield tight bounds even in the most idealistic settings (Nagarajan & Kolter, 2019). In this work, instead revisit the concept of leave-one-out (LOO) error to measure the generalization ability of deep models in the so-called kernel regime. While popular in statistics, the LOO error has been largely overlooked in the context of deep learning. By building upon the recently established connection between neural networks and kernel learning, leverage the closed-form expression for the lcave-one-out error, giving us access to an effi- cient proxy for the test error. We show both theoretically and empirically that the leave-one-ous out error is capable of capturing various phenomena in generalization theory, such as double descent, random labels or transfer learning. Our work there- fore demonstrates that the leave-one-out error provides tractable way to estimate the generalization ability of deep neural networks the kernel regime, opening the door to potential, new research directions in the field of generalization.
INTRODUCTION
Neural networks have achieved astonishing performance across many learning tasks such as in com- puter vision (He et al., 2016), natural language processing (Devlin et al., 2019) and graph learning (Kipf & Welling, 2017) among many others. Despite the large overparametrized nature of these models, they have shown a surprising ability to generalize well to unseen data. The theoretical un- derstanding of this generalization ability has been an active area of research where contributions have been made using diverse analytical tools (Arora et al., 2018; Bartlett et al., 2019; 2017; Neyshabur et al., 2015; 2018). Yet, the theoretical bounds derived by these approaches typically suffer from one or several of the following limitations: i) they are known to be loose or even vacuous (Jiang et al., 2019), ii) they only apply to randomized networks (Dziugaite & Roy, 2018; 2017), and iii) they rely on the concept of uniform convergence which was shown to be non-robust against adversarial perturbations (Nagarajan & Kolter, 2019).
In this work, we revisit the concept of leave-one-out error (LOO) and demonstrate its surprising ability to predict generalization for deep neural networks in the so-called kernel regime. This object is an important statistical estimator of the generalization performance of an algorithm that is the- oretically motivated by a connection to the concept of uniform stability (Pontil, 2002). It has also recently been advocated by Nagarajan & Kolter (2019) potential substitute for uniform conver- gence bounds. Despite being popular in classical statistics (Cawley Talbot, 2003; Vehtari et al., 2016; Fukunaga & Hummels, 1989; Zhang, 2003), LOO has largely been overlooked in the context of deep learning, likely due to its high computational cost. However, recent advances from the neural tangent kernel perspective (Jacot et al., 2018) render the LOO error all of sudden tractable thanks to the availability of a closed-for form expression due to Stone (1974, Eq. 3.13). While the role of the 1,0 error an estimator of the generalization performance is debated in the statistics community

---

Published as a conference paper at ICLR 2022
(Zhang & Yang. 2015; Bengio & Grandvalet, 2004; Breiman, 1996; Kearns & Ron, 1999). the recent work by Patil et al. (2021) established a consistency result in the case of ridge regression, ensuring that LOO converges to the generalization enror in the large sample limit, under mild assumptions the data distribution.
Inspired by these recent advances, in this work, investigate the use of LOO generalization measure for deep neural networks in the kernel regime. We find that LOO is a surprisingly rich descriptor of the generalization error, capturing a wide range of phenomena such as random label fitting, double descent and transfer learning. Specifically, we make the following contributions:
We extend the LOO expression for the multi-class setting to the case of zero regularization and derive a new closed-form formula for the resulting LOO accuracy.
We investigate both the LOO loss and accuracy in the context of deep learning through the lens of the NTK, and demonstrate empirically that they both capture the generalization ability of networks in the kernel regime in a variety of settings.
We showcase the utility of LOO for practical networks by accurately predicting their trans- fer learning performance.
We build on the mathematically convenient form of the LOO loss to derive some novel insights into double descent and the role of regularization.
Our work is structured as follows. We give an overview of related works in Section 2. In Section we introduce the setting along with the LOO error and showcase our extensions to the multi-class case and LOO accuracy. Then, in Section 4 we analyze the predictive power of LOO in various settings and present our theoretical results on double descent. We discuss our findings and future work in Section 5. We release the code for our numerical experiments on Github'.
2 RELATED WORK
Originally introduced by Lachenbruch (1967); Mosteller & Tukey (1968), the leave-one-out error is standard tool in the field of statisties that has been used to study and improve variety of mod- els, ranging from support vector machines (Weston, 1999), Fisher discriminant analysis (Cawley & Talbot, 2003), linear regression (Hastie et al., 2020; Patil et al., 2021) to non non-parametric density estimation (Fukunaga & Hummels, 1989). Various theoretical perspectives have justified the use of the LOO error, including for instance the framework of uniform stability (Bousquet & Elisseeff, 2002) or generalization bounds for KNN models (Devroye & Wagner, 1979). Elisseeff et al. (2003) focused on the stability of a learning algorithm to demonstrate a formal link between LOO error and generalization. The vanilla definition of the LOO requires access to a large number of trained models which is typically computationally expensive. Crucially, Stone (1974) derived an elegant closed-form formula for kernels, completely removing the need for training multiple models. In the context of deep learning, the LOO error remains largely unexplored. Shekkizhar & Ortega (2020) propose fit polytope interpolators Alaa & van der Schaar (2020) rely on a Jackknife estimator, applied in LOO fashion to obtain better confidence intervals for Bayesian neural networks. Finally, we want to highlight the concur- rent work of Zhang & Zhang (2021) who analyze the related concept of influence functions in the context of deep models.
given neural network and estimate its resulting LOO error.
Recent works have established a connection between kernel regression and deep learning. Sur- prisingly, it is shown that an infinitely-wide fully-connected network behaves like a kernel both at initialization (Neal, 1996; Lee et al., 2018; de G. Matthews et al., 2018) as well as during gradient flow training (Jacot et al., 2018). Follow-up works have extended this result to the conmasymtt setting (Arora et al., 2019a; Lee et al., 2019), proving that wide enough networks trained with small learning rates are in the so-called kernel regime, i.e. essentially evolving like their corresponding tangent kernel. Morcover, the analysis has also been adapted to various architectures (Arora et al., 2019a; Huang et al., 2020; Du et al., 2019; Hron et al., 2020; Yang, 2020) as well as discrete gradient descent (Lee et al., 2019). The direct connection the field of kernel regression enables the usage of the closed-form expression for LOO error in the context of deep learning, which to the best of our knowledge has been explored yet.
'https:/ //gii thub. com www./ggegrbbaccaaaaeoooooooommee htwpa/chccmaaaaaaaeeeeeeeee LeaveOneOut
2

---

Published as a conference paper at ICLR 2022
3 SETTING AND BACKGROUND
In the following, we establish the notations required to describe the problem interest and the setting we consider. We study the standard learning setting, where are given dataset input-
S = { (if1:,9),.... yi)....: (I Dn.} where each (#:; Us) L.ddd DD for i = ...... n is distributed according to some probability measure DD We refer to 2; E X C R as the input and to y E y C R the target. We will often use matrix notations to obtain more compact formulations, thus summarizing all inputs and targets as matrices X E Rnxd and Y E RaxC" We will mainly be concerned with the task of multiclass classification, where targets y; encoded one-hot vectors. We consider a function space F and an associated loss function L X' x y - R that measures how well given function / F performs predicting the targets, More concretely, we define the regularized empirical error as
1 F JH T Σ
Ly Mi) AN((),
where À > 0 is a regularization parameter and Ω F RR is functional. For any vector v E RCC let v² argmax*şc Uk- Using this notation, let az y) ((=())==")- We then define the empirical accuracy As as the average number of instances for which f E F provides the correct prediction. i.e.
F 10 f Σ a (z., Uc)
1=1
Finally, we introduce a learning algorithm 27 (X' x 3)" + F, that given function class JF
and training set S E (X' x )))", chooses a function f E F. We will exclusively be concerned with learning through empirical risk minimization, i.e.
(+())= = fs == argmin if((),
and use the shortcut is : 13= In practice however, the most important measures are given by the generalization loss and accuracy of the model, defined as
L F:
+ I, f f Bay (x,( ()), A: - [0, (HPPay)) (f (x)= = =y)).
A central goal in machine learning is control the difference between the empirical error Ls(s) and the generalization error L(f). In this work, we mainly focus on the mean squared loss,
1 (f((()) - -y)) L,(x, y) 2
and also treat classification as regression task, as commonly done in the literature (Lee et al., 2018; Chen et al., 2020; Arora et al., 2019a; Hui & Belkin, 2021; Bachmann et al., 2021). Finally, consider the function spaces induced by kernels and neural networks, presented in the following.
3.1 KERNEL LEARNING
A kernel K X x X + IR is symmetric, positive semi-definite function, i.c. K(x, x') = K('', x) V x, x' E X and for any set (x1,,..,,n)) C X, the matrix K Iaxx with entries Kij = K( æ,) is positive semi-definite. It can be shown that a kernel induces a reproducing kernel Hilbert space, a function space equipped with an inner product (rr),, containing elements
H. cl (If fa(:) = Σ Ka 2.) for R"XC x. x})
where cl is the closure operator. Although H. is an infinite dimensional space, it turns out that the minimizer I's can be obtained in closed form for mean squared loss, given by
[x) KT K + Aln) -Y A x -
fs(x)) kty
3

---

Published as a conference paper at ICLR 2022
where the regularization functional is induced by the inner product of the space, {2f)) = I1fll
K x has entries Kaj K (z) and K R" has entries (K²), K (æ, 2,). A' denotes the pseudo-inverse
E Rax", We will analyze both the regularized (f$) and unregularized model (fs) and their associated LOO errors in the following. For a more in-depth discussion of kernels, we refer the reader Hofmann et al. (2008); Paulsen & Raghupathi (2016).
3.2 NEURAL NETWORKS AND ASSOCIATED KERNELS
Another function class that has seen rise in popularity is given by the family of fully-connected neural networks of depth N,
FNN = { fo(x) w (W(L-1)... .... (ww))..... for W E Bdxxd-1
for di E N. do d, dz C and o + is an element-wise non-linearity. We denote by 0 R. the concatenation of parameters (w(i)... w( : where m = Σi=o d,d++1 initialized randomly according to
is the number of parameters of the model. The parameters wil ~V(0 for ow > 0 and then adjusted to optimize the empirical error Ls. usually through an iterative procedure using variant of gradient descent. Typically, the entire vector 0 optimized via gradient descent, leading to a highly non-convex problem which does not admit a closed-form solution f, in contrast to kemel learning. Next, we will review settings under which the output of deep neural network can be approximated using kernel formulation.
Random Features. Instead of training all the parameters 0, we restrict the function space by only
optimizing over the top layer ( and freezing the other variables W ...., ((L-1) to their value at initialization. This restriction makes the model linear its parameters and induces a finite- dimensional feature map
ΦRF IRd Rdd-1, - (W(1) ...d (w(m)
Originally introduced by Rahimi & Recht (2008) to enable more efficient kernel computations, the random feature model has recently seen a strong spike in popularity and has been the topic of many theoretical works (Jacot et al., 2020; Mei & Montanari, 2021).
Infinite Width. Another, only recently established correspondence emerges in the infinite- width scenario. By choosing Tw Va, for each layer, Lee al. (2018) showed that initialization, the network exhibits Gaussian process behaviour in the infinite-width limit. More precisely, holds that fk i.ddd GP (0, EX4)), for k I,..., C, where ( Rd x Rd - IR is a kernel, coined NNGP, obeying the recursive relation
(0) x') = B [0(
with base ()1) =²) - o x and )(1-)) |, R2x2 is 1)- evaluated on the set {ar, x'): Vid
To reason about networks trained with gradient descent, Jacot et al. (2018) extended this framework and proved that the empirical neural tangent kernel converges to constant kernel O. The so-called neural tangent kernel θ : Rdd x Rd + R is also available through a recursive relation involving the NNGP:
(1+1) (x, x' = (1)) (x), x' ) ((41) (x, x') ) + (1+1) (x, x'),
with base ( x²) ( (x. x²) and 1 (x, x') = (0 E0-0 I.. (0(2) Training infinitely-wicd wide networks with gradient descent thus reduces to kernel learning with the NTK (1.) Arora et al. (2019a); Lee al. (2019) extended this result non-asymptotic setting, showing that very wide networks trained with small learning rates become indistinguishable from kernel learning.
3.3 LEAVE-ONE-OUT ERROR
The goal learning is to choose a model f E F with minimal generalization error L(f). Since the data distribution D is usually not known, practitioners obtain estimate for I(f) by using an
4

---

Published as a conference paper at ICLR 2022
additional test set See {(ol yi)...................... ..... (zr v6)) not used as input to the learning algorithm Qr, and calculate
b az v.)
Lest = Σ (e) v!),
Ares Σ
(I)
While this is a simple approach, practitioners cannot always afford to put a reasonably sized test set aside. This observation led the field of statistics to develop the idea of a leave-one-out error (LOO), allowing one to obtain an estimate of Lff) without having to rely on additional data (Lachenbruch, 1967: Mosteller & Tukey, 1968). We give a formal definition below.
Definition 3.1. Consider a learning algorithm 25 and training sei = {(x; )=))) Let S-i S' {( } be the training set without the i-th data point (æi, y.) and define p=; 27 (S_i). the corresponding model obtained by training on S-i.
i. The leave-one-oul loss/accuracy of 27 on S then defined as the average loss/accuracy of f-i incurred on the left out point (æ: yi), given by
(2, Ve), = 1 Σ (x 1=1
1 Σ of- (x,, y:)
LLo0 (2F;S)=
ALoo(2r;5)
==1
Notice that calculating L1.00 can indeed be done solely based the training set. On the other hand, using the training set to estimate L(f) comes at a cost. Computing f for i ...... . n requires fitting the given model class times. While this might be feasible for smaller models such as random forests, the method clearly reaches its limits for larger models and datasets used in deep learning- For instance, evaluating L1o0 for ResNet-152 on ImageNet requires fitting model with 6 x 10" parameters 10" times, which clearly becomes extremely inefficient. At first glance, the concept of leave-one-out error therefore seems to be useless in the context of deep learning. However, will now show that the recently established connection between deep networks and kernel learning gives us efficient way to compute I..0-- Another common technique is K-fold validation, where the training set is split into K equally sized folds and the model is evaluated in a leave-one-out fashion on folds. While more efficient than the vanilla leave-one-out error, K-fold does not admit closed- form solution, making the leave-one-out eтror more attractive in the setting we study.
In the following, we will use the shortcut I == fA. Surprisingly, it turns out that the space of kernels using 2 with mean-squared loss admits closed-form expression for the leave-one-out error, only relying single model obtained the full training set (X,Y):
Theorem 3.2. Consider a kernel K RR xR" + R and the associated objective with regularization parameter X > O under mean squared loss. Define A = K (K + A1,)) Then it holds that
LL00 (07)
2
ALOO (o))
1 n
Σ
1
(2)
=
Yu Yu- f (wo))
where the residual A E TR for
n, k k= ===1, 1, C is given by A
1-Aii
For the remainder of this text, we will use the shorteut L2000 == Loo0 (Q)). While the expression for L for = 1 has been known in the statistics community for decades (Stone, 1974) and more recently for general C' (Tacchetti et al., 2012: Pahikkala & Airola, 2016), the formula for Al.o is to the best of our knowledge a novel result. We provide a proof of Theorem 3.2 in the Appendix A. Notice that Theorem 3.2 not only allows for an efficient computation of L and AÑoo but also provides us with simple formula assess the generalization behaviour of the model. It turns out that L,00 captures great variety of generalization phenomena, typically encountered in deep learning. Leveraging the neural tangent kernel together with Theorem 3.2 allows us investigate their origin.
As first step, consider the zero regularization limit À + i.e. L since this is the standard setting considered in deep learning. A quick look at the formula reveals however that care has to be taken; soon the kernel is invertible, we have Jf situation.
5

---

Published as a conference paper at ICLR 2022
Corollary 3.3. Consider the eigendecomposition K V dia for V (n) and e R.". Denote its rank by r = rank( K). Then it holds that the residuals A E R can be expressed as
A2 = 1000=Emo II Ej V4, + プド= Xtwy
VigV
2j V/J + Lÿ=1 Xtw, Vi
Moreover the zero regularization limit, i.e. X 0, it holds that
Yiu Ej ViJVi
ifr <n
Ejsr+1 V
(1 + Ax(r))=
iml
=
2 mj Σ Vi
VisVis
Yiu
=
Remark. At first glance for À = 0, a distinct phase transition appears to take place when moving from = n - 1 to r = n. Notice however that small eigenvalue wn will allow for a smooth interpolation, i.e. (n) Wn ~0 an 1) for i ..... n, k C.
similar result for the special case linear regression and r = n has been derived in Hastie et al. (2020). We now explore how well these formulas describe the complex behaviour encountered in deep models in the kernel regime.
4 LEAVE-ONE-ON AS A GENERALIZATION PROXY
In this section, we study the derived formulas in the context of deep learning, through the lens of the neural tangent kernel and random feature models. Through empirical studies, we investigate LOO for varying sample sizes, different amount of noise in the targets as well as different regimes of overparametrization,
the case of infinitely-wide networks. We evaluate the models on the benchmark vision datasets MNIST (LeCun & Cortes, 2010) and CIFARIO (Krizhevsky & Hinton, 2009). To estimate the true generalization error, we employ the test sets as detailed in equation 1. We provide theoretical insights into double descent, establishing the explosion in loss around the interpolation threshold. Finally, we demonstrate the utility of LOO for state-of-the-ar networks by predicting their transferability new tasks. All experiments performed in Jax (Bradbury al., 2018) using the neural-tangents library (Novak et al., 2020).
4.1 FUNCTION OF SAMPLE SIZE
While known to exhibit only a small amount bias, the LOO error may have a high variance for small sample sizes (Varoquaux, 2018). Motivated by the consistency results obtained for ridge regression in Patil et al. (2021), we study how the LOO error (and its variance) of an infinitely-wide network behaves
function of the sample size n. In the following thus interpret LOO function of n. In order to quantify how well LOO captures the generalization error for different sample regimes, we evaluate 5-layer fully-connected NTK model for varying sample sizes on MNIST' and CIFARIO. /0. We display the resulting test and LOO losses in Figure 1. We plot the average result of runs along with confidence intervals. We observe that both Loo0 and ALoo closely follow their corresponding test quantity, even for very small sample sizes of around As we increase the sample size, the variance the estimator decreases and the quality of both LOO loss and accuracy improves even further, offering very precise estimate at 20000.
500.
4.2 RANDOM LABELS
Next study the behaviour of the generalization error when portion of the labels is randomized. deep neural networks is
In Zhang et al. (2017), the authors investigated how the performance affected when the functional relationship between inputs and targets y is destroyed by replacing y by a random label. More specifically, given a dataset X E a and one-hot targets y = e, for k (I,...,C) C), we fix noise level p [0, 1] and replace subset of size pm of the targets with

---

Published as a conference paper at ICLR 2022
035
043
300
0:40
0.0
0.0
01
Sceples
Sempien
(a) L.o0, MNIST
(b) ALco, MNIST
(c) LLoo. CIFARIO
(d) ALOo. CIFARIO
Figure I: Test and LOO losses (a.c) and accuracies (b, d) as a function of sample size n. We use a 5-layer fully-connected NTK model on MNIST and CIFARIO.
random ones, i.e. y - ez for h ~ U([L, C}). We then train the model using the noisy targets ý while measuring the generalization error with respect to the clean target distribution. As observed in Zhang et al. (2017); Rolnick et al. (2018), neural networks manage to achieve very small empirical error even for p = 1 whereas their generalization consistently worsens with increasing p. Random labels has become a very popular experiment to assess the quality of generalization bounds (Arora al.. 2019;; 2018; Bartlett et al., 2017). We now show how the leave-one-out error exhibits the same behaviour as the test сгтоr under label noise, thus serving as an ideal test bed to analyze this phenomenon. In the following, we consider the leave-one-out error as function of the labels, i.c. LLO0 = (y). The phenomenon of noisy labels is of particular interest when the model has enough capacity to achieve zero empirical error. For kernels, this equivalent rank (K) = n and we will thus assume in this section that the kernel matrix has full rank. However, direct application of Theorem 3.2 is not appropriate, since randomizing some of the training labels also randomizes the "implicit" test set. In other words, our aim is not to evaluate fz against ÿ, since ÿ; might be
one of the randomized labels. Instead, we want to compare f/² with the true label yes in order to preserve a clean target distribution. To fix this issue, we derive a formula for the leave-one-out error for a model trained on labels Y but evaluated on Y:
Proposition 4.1. Consider a kernel with spectral decomposition K diag(w)VT for V Raxn orthogonal and w E RR. Assume that rank (K) = Then it holds that the leave-oneoout error LinO(Y Y; for model trained on S (1;; ) but evaluated on S = (x) y1 )= is given by
K n Σ
LLoo (1:00Y;Yo Y; =
(i
+ Vik
Vit) 2
A (Y:) A
I (i::-:)''==s
1=1 1=1
where Â = (Y) IR is defined as in Corollary 3.3.
We defer the proof to the Appendix A.4. Attentive readers will notice that we indeed recover The- orem 3.2 when Y = Y. Using this generalization of LOO, we can study the setup in Zhang et al. (2017) to test whether LOO indeed correctly reflects the behaviour of the generalization error. To this end, we perform a random label experiment on MNIST and CIFARIO with n = 20000 for a NTK model of depth 5, where track test and LOO losses while increasingly perturbing the targets with noise. We display the results in Figure 2. We see an almost perfect match between test and LOO loss well test and LOO accuracy, highlighting how precisely LOO reflects the true error.
4.3 DOUBLE DESCENT
Originally introduced by Belkin et al. (2019), the double descent curve describes the peculiar shape of the generalization error as a function of the model complexity. The error first follows the classical U-shape, where an increase in complexity is beneficial until a specific threshold. Then, increas- ing the model complexity induces overfitting, which leads to worse performance and eventually a strong spike around the interpolation threshold. However, as found in Belkin et al. (2019), further increasing the complexity again reduces the error, often leading to the overall best performance. A large body of works provide insights into the double descent curve but most of them rely on very
7

---

Published as a conference paper at ICLR 2022
60
54
L1,0, MNIST
(b) ALo0, MNIST
(c) LLoo, CIFARIO
(d) ALoo, CIFARIO
Figure 2: Test and LOO losses (a. c) and accuracies (b, d) as a function of noise. We use 5-layer fully-connected NTK model on MNIST and CIFARIO with n 20000.
restrictive assumptions such as Gaussian input distributions (Harzli et al., 2021; Adlam & Penning- ton, 2020; Ascool al., 2020) or teacher models (Bartlett al., 2020; Harzli al., 2021; Adlam & Pennington, 2020; Mei & Montanari, 2021; Hastie et al., 2020). Here we show under arguably weaker assumptions that the LOO loss also exhibits spike at the interpolation threshold.
In order to reason about the effect of complexity, we have to consider models with a finite di- mensional feature map pm I2 R" Increasing the dimensionality of the feature space R" naturally overparametrizes the model and induces dynamic in the rank r(m) := rank K) = rank (pm (X)). We restrict our attention to models that admit an interpolation point, i.e. 3m* e N such that r(m")
While the developed theory holds for any kernel, we focus the empirical evaluations largely to the random feature model due to its aforementioned connection neural net- works. In the following.
will interpret the leave-one catee-ouu-rroot LLo0 = Looo (m). Notice that ["oo(m) measures the generalization error a model trained on points, instead of n. The underlying interpolation point thus shifts, i.e. denote m N such that r(m²) = n In the following we will show that Loo (m)"m) 2=0000 DO.
function of m and n, ie.
Intuition. We give high level explanation for our theoretical insights in this paragraph. For m < m² the dominating term in [o (m) is
rr; A)
V + Ei= Xtay Σ Ei
A V2
We observe a blow-up for small X due to the unit vector nature of both V.. and Vaj. For instance, considering the interpolation point where r = n 1 and = O, we get g(n - 1,0) Σ PT. the sum the elements of V.n. which likely has small entry due to its unit the other hand, reducing or increasing À has dampening effect as we combine multiple positive terms together, increasing the likelihood to move away from the singularity. A similar dampening behaviour in Li (m) can also be observed for m > m when Wn >> 0. In order to formalize this argument, we need the following assumption:
nature. Ön
Assumption 4.2. For K diag (w) V impose that the orthogonal matrix V follows
(O,))
where U (Ox) is the Haar measure the orthogonal group O..
Under Assumption 4.2, we can prove that at the interpolation point, the leave-one-out error exhibits spike, which worsens increase the amount of data:
Theorem 4.3. For large enough N and X 0, it holds that
L"Lo(mm)) 2nA
where A ~ r(2, 1) is independent of L (mo) hence diverges a.s. with -
is surprising that Assumption 4.2 suffices to prove Theorem 4.3, highlighting the universal nature of double descent. We provide empirical evidence for the double descent behaviour of LOO in Figure 3. We fit a 1-layer random feature model of varying width to the binary (labeled) MNIST dataset with sample size of 5000. We observe that the LOO error indeed closely follows the
8

---

Published as a conference paper at ICLR 2022
1.0
0.4
0.5
0.4
6.0
2000
8200
10000
2000
8200
10000
(a) Loss
(b) Accuracy
Figure 3: (a) Train, Test and LOO losses (a) and accuracies (b) function of width. We use random feature model on binary MNIST' with n 5000.
test error, exhibiting the spike as predicted by Theorem 4.3, The location of the spike indeed exactly matches the interpolation threshold which is situated around m 2 n.
4.4 TRANSFER LEARNING
Finally, we study more realistic networks often employed for large-scare scale computer vision tasks. We study the task of transfer learning (Yosinski et al., 2014) by considering classifiers trained on ImageNet (Krizhevsky et al., 2012) and fine-tuning their top-layer to the CIFARIO dataset. Notice that this corresponds to training a kernel with a data-dependent feature map Qdma induced by the non- output layers. Our experiments on ResNet18 (He et al., 2016), AlexNet (Krizhevsky et al., 2012), VGG (Simonyan & Zisserman, 2015) and DenseNet (Huang et al., 2017) demonstrate that also for transferring between tasks we have a very precise estimation the test accuracy. We display the results in Table 1. We consider small data regime where practice for transfer learning tasks. In order to highlight the role of pre-training, we also evaluate random feature maps crand where use standard initialization for all the parameters the network. Indeed we clearly observe the benefits of pre-training, leading to a high increase in performance for all considered models. For both settings, pre-trained and randomly initialized, we observe an excellent agreement between test and lcave-one-out accuracies across all architectures.
10000, as often encountered in
MODEL
APEST(
ALoo (dua)s
Arest (dRASD)
ALoo (PAAND)
RESNETI8
67.2 0.1
67.5 0.4
37.7 0.2
37.1 1 0.1
ALEXNET
57.6
58.2 0.2
24.2 1 0.2
23.7
VGG16
56.6 + 0.2
56.8
29.3 + 0.5
29.2 = 0.8
DENSENET161
72.5 0.2
0.3
51.7 + 0.3
49.9 = 0.3
Table I: Test and LOO accuracies for models pre-trained on ImageNer and transferred to CIFARIO by re-training the top layer. We use runs, each with different training set of size n 10000. We compare the pre-trained networks with random networks to show the benefits of transfer learning.
CONCLUSION
We investigated the concept of leave-one-out deep learning. Through the use of NTK, we derive new expressions for the LOO loss and accuracy of deep models in the kernel regime and observe that they capture the generalization behaviour for a variety of settings. Moreover, we mathematically prove that LOO exhibits a spike at the interpolation threshold, needing only minimal set of theoretical tools. Finally, we demonstrated that LOO accurately predicts the performance of deep models in the setting of transfer learning.
measure for generalization in the context of
Notably, the simple form of LOO might open the door new types of theoretical analyses to better understand generalization, allowing for a disentanglement of the roles of various factors at play such overparametrization, noise and architectural design.

---

Published as a conference paper at ICLR 2022
REFERENCES
Ben Adlam and Jeffrey Pennington. Understanding double descent requires fine-grained bias- variance decomposition. 34th Conference on Neural Information Processing Systems (NeurIPS 2020), 2020.
Ahmed M. Alaa and Mihaela van der Schaar. Discriminative jackknife: Quantifying uncertainty in deep learning via higher-order influence functions. Proceedings of the 37th International Confer- ence on Machine Learning (ICML), 2020.
Sanjeev Arora, Rong Ge, Behnam Neyshabur, and Yi Zhang. Stronger generalization bounds for deep nets via a compression approach. Proceedings of the 35th International Conference on Machine Learning (ICMI.), 2018.
Sanjeev Arora, Simon S. Du, Wei Hu, Zhiyuan Li, Ruslan Salakhutdinov, and Ruosong Wang. On exact computation with an infinitely wide neural net. 33rd Conference on Neural Information Processing Systems (NeurIPS), 2019a.
Sanjeev Arora, Simon Du, Wei Hu, Zhiyuan Li, and Ruosong Wang. Fine-grained analysis of optimization and generalization for overparameterized two-layer neural networks. Proceedings of the 36th International Conference on Machine Learning (ICML), 2019b.
Gregor Bachmann, Seyed-Mohsen Moosavi-Dezfoolli and Thomas Hofmann. Uniform conver- gence, adversarial spheres and simple remedy, Proceedings of the 38th International Conference on Machine Learning (ICML), 2021.
Peter Bartlett, Dylan Foster, and Matus Telgarsky. Spectrally-normaaizer margin bounds for neural networks. 31st Conference on Neural Information Processing Systems (Neurips), 2017.
Foster,
Peter L. Bartlett, Nick Harvey, Chris Liaw, and Abbas Mehrabian. Nearly-tight ve-dimension and pseudodimension bounds for piecewise linear neural networks. Journal of Machine Learning Research 20, pp. 1-17, 2019.
Peter I.. Bartlett, Philip M. Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, Iireee,,,1166, 117745):30063-3077 2020. ISSN 0027-8424.
Mikhail Belkin, Daniel J. Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine- learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences, 116: 15849 15854, 2019.
Yoshua Bengio and Yves Grandvalet. No unbiased estimator of the variance of k-fold cross- validation. J. Mach. Learn. Res., 5: 5:1089-1100 105, December 2004. ISSN 1532-4435.
Olivier Bousquet and André Elissefff. Stability and generalization. The Journal of Machine Learn- ing Research, 2:499- 2002.
K. O. Bowman, L. R. Shenton, and Paul C. Gailey. Distribution of the ratio of gamma variates. Communications in Statistics Simulation and Computation, 27(1):1-19, 1998.
James Bradbury, Roy Frostig, Peter Hawkins, Matthew James Johnson, Chris Leary, Dougal Maclaurin, George Necula, Adam Paszke, Jake VanderPlas, Skye Wanderman-Milnn and Qiao Zhang. JAX: composable transformations of Python+NumPy programs, 2018. URL http:
//github. com/ ggoogle//t jax.
Leo Breiman. Heuristics of instability and stabilization in model selection. The Annals of Statistics, 24(6):2350 2383, 1996.
Gavin C. Cawley and Nicola I.C. Talbot. Efficient leave-one-out cross-validation of kernel fisher discriminant classifiers. Pattern Recognition, 36(1 1):25)5-2559 2003. ISSN 0031-3203.
Shuxiao Chen, Hangfeng He, and Weijie J. Su. Label-aware neural tangent kernel: Toward better generalization and local elasticity. 34th Conference on Neural Information Processing Systems (NeurIPS). 2020.
10

---

Published as a conference paper at ICLR 2022
Stéphane d' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance(s) in the lazy regime. Proceedings of the 37th International Confer- ence on Machine Learning (ICML), 2020.
Alexander G. de G. Matthews, Mark Rowland, Jiri Hron, Richard E. Turner, and Zoubin Ghahra- mani. Gaussian process behaviour in wide deep neural networks. International Conference on Learning Representations (ICLR), 2018.
Jacob Devlin, Ming- Wei Chang, Kenton Lee, and Kristina Toutanova. Bert: Pre-training of deep bidirectional transformers for language understanding. Proceedings of NAACL-HLT, 2019.
Luc Devroye and Terry Wagner. Distribution-free inequalities for the deleted and holdout error estimates. IEEE Transactions on Information Theory, 25(2):202-207, 1979.
Simon S. Du, Kangcheng Hou, Barnabás Póczos, Ruslan Salakhutdinov, Ruosong Wang, and Keyulu Xu. Graph neural tangent kernel: Fusing graph neural networks with graph kernels. 34nd Confer- ence on Neural Information Processing Systems (NeurIPS), 2019.
Gintare Karolina Dziugaite and Daniel M. Roy. Computing nonvacuous generalization bounds for deep (stochastic) neural networks with many more parameters than training data. Proceedings of the Thirty-Third Conference on Uncertainty in Artificial Intelligence, 2017.
Gintare Karolina Dziugaite and Daniel M Roy. Data-dependent pac-bayes priors via differential privacy. S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett (eds.), 32nd Conference on Neural Information Processing Systems (NeurIPS 2018), volume 31. Curran Associates, Inc., 2018.
André Elisseeff, Massimiliano Pontil, et al. Leave-one-out error and stability of learning algorithms with applications. NATO science series sub series ii computer and systems sciences, 190:111- 130, 2003.
K. Fukunaga and D.M. Hummels. Leave-one-oue procedures for nonparametric error estimates. IEEE Transactions on Pattern Analysis and Machine Intelligence, 11(4):421 421, 1989.
Ouns El Harzli, Guillermo Valle-Pérez, and Ard A. Louis. Double-descent curves in neural net- works: a new perspective using gaussian processes, 2021.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J. Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation, 2020.
Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. Deep residual learning for image recog- nition. IEEE Conference on Computer Vision and Pattern Recognition (CVPR), 2016.
Thomas Hofmann, Bemhard Schölkopf, and Alexander J. Smola. Kernel methods in machine learn- ing. The Annals of Statistics, 36(3), Jun 2008. ISSN 0090-5364.
Jiri Hron, Yasaman Bahri, Jascha Sohl-DDckstein, and Roman Novak. Infinite attention: Nugp and ntk for deep attention networks. Proceedings of the 37th International Conference on Machine Learning (ICML), 2020.
Gao Huang, Zhuang Liu, and Kilian Q Weinberger. Densely connected convolutional networks. 2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR), pp. 2261-2269, 2017.
Kaixuan Huang, Yuqing Wang, Molei Tao, and Tuo Zhao. Why do deep residual networks generalize better than deep feedforward networks? a neural tangent kernel perspective. 34rd Conference on Neural Information Processing Systems (NeurIPS), 2020.
Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross- entropy in classification tasks, 2021.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernl:: Convergence and
generalization in neural networks. 32rd Conference on Neural Information Processing Systems (NeurIPS). 2018.
11

---

Published as a conference paper at ICLR 2022
Arthur Jacot, Berfin Simşek, Francesco Spadaro, Clément Hongler, and Franck Gabriel. Implicit regularization of random feature models. Proceedings of the International Conference on Ma- chine Learning (ICML), 2020.
Yiding Jiang, Behnam Neyshabur, Hossein Mobahi, Dilip Krishnan, and Samy Bengio. Fantastic generalization measures and where to find them. International Conference on Learning Repre- sentations (ICLR), 2019.
Michael Kearns and Dana Ron. Algorithmic stability and sanity-check bounds for leave-one-out cross-validation. Neural Computation, 11(6):1277-153, 1999.
Thomas N. Kipf and Max Welling. Semi-supervised classification with graph convolutional net- works. Proceedings of the Sth International Conference on Learning Representations, 2017.
Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Tech- nical Report University of Toronto, Toronto, Ontario, 2009.
Alex Krizhevsky, Nya Sutskever, and Geoffrey E Hinton. Imagenet classification with deep convo- lutional neural networks. In F. Pereira, C. J. C. Burges, L. Bottou, and K. Q. Weinberger (eds.), Advances in Neural Information Processing Systems, volume 25, Curran Associates, Inc., 2012.
PA Lachenbruch. An almost unbiased method of obtaining confidence intervals for the probability of misclassification in discriminant analysis. Biometrics, 1967.
Yann LeCun and Corinna Cortes. MNIST handwritten digit database, 2010.
Jaehoon Lee, Yasaman Bahri, Roman Novak, Samuel S. Schoenholz, Jeffrey Pennington, and Jascha Sohl-Dickstein. Deep neural networks as gaussian processes. International Conference on Learn- ing Representations (ICLR), 2018.
Jachoon Lee, Lechao Xiao, Samuel S. Schoenholz, Yasaman Bahri, Roman Novak, Jascha Sohl- Dickstein, and Jeffrey Pennington. Wide neural networks of any depth evolve as linear models under gradient descent. 33rd Conference on Neural Information Processing Systems (NeurIPS), 2019.
Song Mei and Andrea Montanari. The generalization error of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 06 2021. doi: (00002/p..22000
Mosteller and J. Tukey. Data analysis, including statistics. Handbook of Social Psychology, 2. 1968.
Vaishnavh Nagarajan and J. Zico Kolter. Uniform convergence may be unable to explain general- ization in deep learning. 33rd Conference on Neural Information Processing Systems (NeurIPS), 2019.
Radford M. Neal. Priors for Infinite Networks, pp. 29-53. Springer New York, New York, NY, 1996. ISBN 978-1-4612-0745-0, doi: 10.1107/978-114000 1-612-0755---.
Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. Norm-based capacity control in neural networks. Proceedings The
The 28th Conference Learning Theory (PMLR), 2015.
Behnam Neyshabur, Srinadh Bhojanapalli, and Nathan Srebro. A pac-bayesian approach to spectrally margin bounds for neural networks. International Conference on Learning Representations (ICLR), 2018
Roman Novak, Lechao Xiao, Jiri Hron, Jachoon Lee, Alexander Alemi, Jascha Sohl- Sohl-Dickstein, and Samuel S. Schoenholz. Neural tangents: Fast and easy infinite neural networks in python. In International Conference on Learning Representations, 2020. URL. httpp:://ggt thub. com/ pnoollenneuran waw.urrallattaattt.....
Tapio Pahikkala and Antti Airola. Riscore: Regularized least-squares learners. Journal of Machine Learning Research, 17(220):155, 2016. URL /ttp:://mmll org/ papers/v17/16-00 html.
12

---

Published as a conference paper at ICLR 2022
Pratik Patil, Yuting Wei, Alessandro Rinaldo, and Ryan Tibshirani. Uniform consistency of cross- validation estimators for high-dimensional ridge regression. In Arindam Banerjee and Kenji Fukumizu (eds.), Proceedings of The 24th International Conference on Artificial Intelligence and Statistics, volume 130 of Proceedings of Machine Learning Research, pp. 3178-3186. PMLR, 13-15 Apr 2021.
Vern I. Paulsen and Mrinal Raghupathi. An Introduction the Theory of Reproducing Kernel Hilbert Spaces, pp. i-iv. Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2016.
M. Pontil. Leave-one-out error and stability of learning algorithms with applications. International Journal of Systems Science, 2002.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In J. Platt, D. Koller, Y. Singer, and S. Roweis (eds.), Advances in Neural Information Processing Systems, volume 20. Curran Associates, Inc., 2008.
David Rolnick, Andreas Veit, Serge Belongie, and Nir Shavit. Deep learning robust to massive label noise, 2018.
Sarath Shekkizhar and Antonio Ortega. Deepnnk: Explaining deep models and their generalization using polytope interpolation, 2020.
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. International Conference Learning Representations (ICLR), 2015.
M. Stone. Cross-validatory choice and assessment of statistical predictions. Journal of the Royal Statistical Society, 36(2):111-147, 1974.
Andrea Tacchetti, Pavan Mallapragada, Matteo Santoro, and Lorenzo Rosasco. Gurls: toolbox for regularized least squares learning. 02 2012.
Gaël Varoquaux. Cross-validation failure: Small sample sizes lead to large error bars. Neurolmage, 180:68-775 77, 2018. ISSN 1053-8119. New advances in encoding and decoding of brain signals.
Aki Vehtari, Andrew Gelman, and Jonah Gabry. Practical bayesian model evaluation using leave- one-out vrooss-validation and waic. Statistics and Computing, 27(5):1413-1432, Aug 2016. ISSN 1573-1375.
Roman Vershynin. High--Dimessioal Probability: An Introduction with Applications in Data Sci- ence. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, 2018.
Ch. Walck. Hand- book on statistical distributions for experimentalists. 1996.
J. Weston. Leave-one-out support vector machines. In IJCAI, 1999.
Greg Yang. Tensor programs ii: Neural tangent kernel for any architecture, 2020.
Jason Yosinski, Jeff Clune, Yoshua Bengio, and Hod Lipson. How transferable are features in deep neural networks? Advances Neural Information Processing Systems, 2014.
Chiyuan Zhang, Samy Bengio, Moritz Hardt, Benjamin Recht, and Oriol Vinyals. Understanding deep learning requires rethinking generalization. International Conference Learning Repre- sentations (ICLR), 2017.
Rui Zhang and Shihua Zhang. Rethinking influence functions of neural networks in the over- parameterized regime, 2021.
Tong Zhang. Leave-one-out bounds for kernel methods. Neural Computation, 1397)11377 2003.
Yongli Zhang and Yuhong Yang. Cross-validation for selecting model selection procedure. Journal of Econometrics, 187(1):55-12, 2015. ISSN 0304-4076.
13

---

Published as a conference paper at ICLR 2022
A
OMITTED PROOFS
We list all the omitted proofs in the following section.
A.1 PROOF OF THEOREM 3.2
Theorem 3.2. Consider a kernel K H. xRd + R and the associated objective with regularization
parameter > O under mean squared loss. Define A = K (K + + Then it holds that
11,00 (Q%
1
AA)
ALOo (DtRar)
1 (1. }
1
k=1
where the residuals Aie E for i 1,..., n, 1..... K given by Ai Yiu 12
1-
Proof. Recall that få solves the optimization problem
I's = argminn 1B( argmin
(Ju(ze)) Ysx)² + A
and predicting on the training data takes the form fs(X) AY for some A R=x. Now consider the model 5 == fo. obtained from training on S.,. W.L.O.G. assume that i n. We want to understand the quantity fx. (In), ie. the k-th component of the prediction on 2,. To that end, consider the dataset 2 = S_n u { ann (("m))) }. Notice that for any f E F, holds
))
Σ
(x.) -Ya)² (fx FTK((.))) + "
C n-1
(.)()t)) - Vit) + A1l "1
= L3_ (f**)
< 2 (f)
C
< (13,00) + Σ -
= (f
where the first inequality follows because f minimizes LS_., by definition. Thus fx also mini- mizes L and hence also takes the form
(X) A.
Yi (
ii
where Y RaxC such that Yux-
Now we care about the n-th prediction
else
which is
n-1
(x
Σ
Ans Ysk
Σ
AngYsk + Ann.fx (xx))
1=1
j=1
n
Σ
Anz Yyk
Ann Yok + Ann Tnt (xm))
jml
-nn Vok + Ann Ant (xr)
14

---

Published as a conference paper at ICLR 2022
Solving for (z,) gives
f (In))
-nn Ynk
fx. (20n)
(3)
Ann
Then, subtracting Yn leads
Ynk (2n) = Ynk (
Ann Ynk
Ynk
Ynk Ann
S'S (B Ynk
Yuk
Ann
Ann
Ann
Squaring and summing the expression over n and k results in the formula. For the accuracy, we know that we correctly predict if the maximal coordinate of fx (xn) agrees with the maximal coordinate of yn i.c.
argmax (2))) argmaxx Ynk
From equation 3, we notice that
fb, (xn))
Ann Ynk
(b,)(nn) - Yuk + Ynk Ann Ynk
argmax, (2,) argmax,
argmax,
AnA
Ann
Ann
-AA Yuk
argmax,
(ynn An
We thus have to check the indicator 1 ((2). -.,o)' vn) and sum over n to obtain the result.
A.2 BINARY CLASSIFICATION
Here state the corresponding results in the case of binary classification. The formulation for the accuracy changes slightly now the sign of the classifier serves the prediction.
Proposition A.1. Consider a kernel K _dd x IRd I. and the associated objective with regular-
izution parameter > under mean squared loss. Define A K (K + x1,,) Then holds that
LL00 (DARM) = (A:)
ALoo (DARM)
Σ 1 (ma3<1)
1=1
1=1
9: - (a.)
where the residuals A E for I,... is given by A
I-A..
Proof. Notice that the result for L1o0 is analogous to the proof for Theorem 3.2 by setting K = 1. For binary classification we use the sign of the classifier as a decision rule, i.e. the classifier predicts correctly if (xx(())))))))))))))()))) > O. We can thus calculate that
yn (xx.) = (ac.)
Annya
Un J (x.)) - 2/x + 1/ 1 Ann
Ann
1 Ann
Uの Yn Un (x(
Ann
f3 (xx
Un Yn
Ann
yn A
Thus, the n-th sample correctly classified and only if
yn A = yn A
We now just count the correct predictions for the accuracy, i.e.
ALoO
(Q FRM
1 (..A/11)
15

---

Published as a conference paper at ICLR 2022
A.3 PROOF OF COROLLARY 3.3
Corollary 3.3. Consider the eigendecoompssiton K - V di' for V E (n) and w E RR.
Denole is rank by rank(K)) ). Then it holds that the residuals A I can be expressed
47()) = Σ Eker+1 1=1
11
Vs Vix + Ei
Vea Via
VIR
ih EkEr+1 + + W- Vi
Moreover for zero regularization, i.e. X + O, it holds that
Eizrt1 ViJ Vig
Σ Yiu
ifr <n
Σ 2j-++1 ViJ
(7 + Aa(r))
Σー= 1 VigVig ifr= n
wi
Yik
دي V?
Proof. Define A K(K+ + AI
RRxx, Recall that (x( = Ay and thus fb()))
Σj=1 Aig Yzk. Let us first simplify A:
A = K (K
+ Aln)
V diag (w) V (Vdiag diag (w) V + +11n)
V diag
3
VT
We can characterize the off- off-diagonal elements for i + j as follows:
Aij
Vik Wi +
Wi
Vjk+
Vi
Wi
Va
wk + A Va
A
X
k=1
k=
VIR
VinVi Vz
Wk + X
k=++1
k=1
where we made use of the fact that V.. 1 Vj.. The diagonal elements i = =j on the other hand can be written as
Aa
Wi
Wk 22 ie
V2
+
Wk +
Wkk + X
k=1
k=1
1=1
a
W/ +
k=++1
k=1
where we have made use of the fact that V. is unit vector. Plugging- in the quantities into L.o0 results in
Yik (xx
Yu
Σi=
AuYi
YA - Anyi - El Yu
ck
- Aii
1 Aii
1 1 Asi
Yin Ejerti Vi3 Ek=1
V2
Eifi YI
Ejzrti VigVis + +i= 3
13 1/++t
Ejer+1
V + Σド=
V2 wi
2
19
Els You
EEjr+1 Vig + E
> Viy
uyth
Ejer+ + E s=
1g W
Now crucially, in the full rank case we obtain
n, we have empty sums, i.e. Ei.+1 Em=nti 0 and
Yix Σ j==1 wi
VigVis
El Yik Σ j==1 W Vig
Ej=1 V2 Wyt1
1
Σ V3 wytt
Yik Σj=1 1 Vi
A 1
Σド LV3
16

---

Published as a conference paper at ICLR 2022
On the other hand, in the rank deficient
cancel the regularization term:
Ejzr+1 Vi
YIE
Plugging this into the formulas for L and ALoo concludes the proof.
A.4 PROOF OF PROPOSITION 4.1
Proposition 4.1. Consider a kernel with spectral decomposition K = V diag(w)VT for V e Raxa orthogonal and w E RR. Assume that rank (K) = n. Then it holds that the leave-one-out ervor Lio0(Y; Y) for a model trained on S {(x, D:) but evaluated on S {( yi )i is given by
L100 (8;
ΣΣ
Σ
Ais + Vin Put)
A A Y) =
1 (B.--..)' }
1=1 km
1=1
where Âu== = A))(Y) E R is defined as in Corollary 3.3.
Proof. Denote by S_, the dataset {(tg,8)))77 05)) Denote by f the model trained S_.. Recall from the proof of Theorem 3.2 that
(x)) f (xn) Ann
Ann
Instead of subtracting the same label Ynk. now subtract the evaluation label Ynk:
Ynk (x.) Ynk Ann Ynk (x)) + Ann
(1 Ann) (an)(nnk Ynk)) + Yak - f (In)
Ann
Ann
-Ynk Ynk) Ynk -ff (x))
Ann
(Ynkk - Ynk) + +
The second term Â now the summand of the standard leave-one-out error where we evaluate on Y. We can hence re-use Theorem 3.3 to decompose it. Squaring and summing over n concludes LOO loss result. For the accuracy, notice that a similar derivation as for Theorem 3.2 applies:
f (xx) Ann Ynk argmax;
fA (xx) Ynk + Ynk Ann Y
argmax, (T argmax,,
1 Ann
Ann
argmax, - A Ynk
Ün Am
We thus have to check the indicator against the true label yn i.c. 1 "ma)--an)"--0 and sum it over n. obtain the result.
A.5 PROOF OF THEOREM 4.3
Theorem 4.3. For large enough n E N, estimate Tifoomm") 2 2nAA
where A I(2, 1) is independent of Lioo (m") hence diverges with co.
Proof. First we notice that for m m by definition it holds that r = n 1, which simplifies the LOO expression
(m²) A=0,
Σ
Ye Vin
V2
i=
17

---

Published as a conference paper at ICLR 2022
For notational convenience, we will introduce IR such that e; Vin- We will now bound the both factors one-by-one. The first part is a simple application of Proposition B.1 and Proposition B.5:
2
Loo (mo)
Σ
n B
Now for large enough n, use Lemma B.6 to make the following approximation in distribu- tion:
nB = 2 71 (d)
2A
2
where A~ 1),, Thus for large enough n, it holds that
I (Loo(m") 2 2n.A
As the approximation becomes exact for larger and larger n, we conclude that
(oo)(mm) >000 0o a.s.
B ADDITIONAL LEMMAS
In this section we present the additional technical Lemmas needed for the proofs of the main claims in A.
Lemma B.1. Consider a unit vector Sn-1, Then it holds that
Σ
n
Proof. Let's parametrize each f as
Zi
1//
1==
2g
for 1,..., n and z E R", One can easily check that ||0||2 = and hence v E Sn-1, Plugging this in, we arrive at
a
n
n
We can re-arrange the sum into pairs
2
2
+
1 a²
2
2
2 2
for
> O and using the fact that x +
1 > 2 for x
2
We can find min-1) such summands,
2
and thus
2 n n(n - 1)
n²
2
Lemma B.2. Consider U (Sn-1) and any fixed orthogonal matrix U E EOO.). Then it holds that
Proof.
This is standard result and can for instance be found in Vershynin (2018).
18

---

Published as a conference paper at ICLR 2022
Lemma B.3. Consider (O0 nn). Then it holds that
u (sn-1)
w
Proof. This a standard result and can for instance be found in Vershynin (2018).
Lemma B.4. Consider two independent Gamma variables X ~ Gamma(a, v) and Y
Gamma(B, v). Then it holds that
X
~ Beta (a, B)
X
Proof. This is standard result and can for instance be found in Bowman et al. (1998).
Lemma B.5, Consider ~ u (sn-1). Then it holds that
n 1
yeus
Beta
2' 2
Proof. First realize that we can write
y.u: 1 (v y)
with ||T,.1/ 1 and the fact that 3 (d)
where i, = Vx
for fixed E 1-1,1)"
vn
The idea is now choose U (n) such that U e1 01.,....,0) Then by using Lemma B.2, it holds
Hu (
(Vi,))
(
e
Thus, surprisingly, it suffices understand the distribution of U1 By Lemma B.3, know that
(d)
21
#/
where z NO 1,.. We are interested in the square this expression,
(d)
(d)
U4
71
where we define w Gamma (5) 1) and w Gamma n-1 .22
Σラ 2.
clearly independent of of. Moreover, it holds that of
Thus. by Lemma B.4 we can conclude that
1
1 n 2' 2
V1
Beta
n
Lemma B.6. Consider the sequence of Beta distributions X,, Beta(k, n). Then it holds that
(d) Gamma 1)
TLX,,
Proof. This is standard result and can for instance be found in Walck (1996).
C FURTHER EXPERIMENTS
In this section present additional experimental results on the leave-one-out error.
19

---

Published as a conference paper at ICLR 2022
(a) Depth 1
(b) Depth 2, m2
(c) Depth 2, m2
Figure 4: Kernel rank rank( as a function of complexity. For (a) we use depth random feature model xW.), W E Rmxdd where complexity is measured through width In (b) and (c) we use a random feature model of depth 2, o (Vo (Wx)), W E IR and V E m For (b) we visualize the rank function of m1, where m2 120 fixed and in (c) a function of my, where my = 10 fixed. We use MNIST with n 100 samples.
C.I RANK DYNAMICS FOR DIFFERENT KERNELS
In this section, we illustrate how the rank rank K) of the kernel evolves as a function of the un- derlying complexity. As observed in various works, the spike in the double descent curve for neural networks usually occurs around the interpolation threshold, i.e. the point in complexity where the model able achieve zero training loss. Naturally, for the kernel formulation, interpolation achieved when the kernel matrix K has full rank. We illustrate in the following how the dynamics of the rank change for different architectures, displaying a similar behaviour as finite width neural networks. In Fig. (a) show depth 1 random feature model with feature maps a (Wæ) where W E I xx xd and o is the ReLU non-linearity. We use MNIST with n = 100. We measure the complexity through the width of the model. We observe that in this special case, the critical com- plexity exactly coincides with the number of samples, i.e. rank K) n as soon as m n. This counter-intuitive first not observed for standard neural networks. We show however in Fig. 4 (b) and (c) that the rank dy- namics indeed become more involved for larger depth. In Fig. 4 (b) and (c), we use 2-layer random feature model with feature map (Vo(Wæ)) for weights W E m xd and V E IR xms, In (b) we show the change rank as mi increases, while m2 120 is fixed. We observe that indeed the dynamics change and the critical complexity is not
exact match of the complexity with the sample size is usually
Similarly in (c) we fix and vary m2. Also there we observe that the critical threshold is not located at n but rather a bigger width is needed to reach interpolation.
10
Finally also study the linearizations of networks that also give rise to kernels. More concretely, we consider feature maps of the form
(x)) (o)
where So is a fully-connected network with parameters E IR, as introduced before. Our double- descent framework also captures this scenario. In Fig. 5, we display the rank dynamics in case of 2 layer network fo(x) w" (Uo(Vv:: where w E Rm= U E mm V e IR xd and a is the ReLU non-linearity. Again we observe that the rank dynamics change and do not coincide with the number of samples n..
C.2 LOO AS FUNCTION OF DEPTH
We study how the depth of the NTK kemnel (L) affects the performance of LOO loss and ac- curacy. We use the datasets MNIST and CIFARIO with 5000 and evaluate NTK models with depth ranging from 3 to 20. We present our findings Figure 6. Again we see a very close match between LOO and the corresponding test quantity for CIFARIO. Interestingly the performance is slightly worse for very shallow models. For MNIST we see gap between LOO loss and test loss, which is due the very zoomed-in nature of the plot (the gap is actually only 0.015) as the loss values are very small in general. Indeed we observe an excellent match between the test and LOO accuracy.
20

---

Published as a conference paper at ICLR 2022
Interplation
Crical éparars
2000
*params
Figure 5: Rank dynamics of K for the linearization kernel of fo(x: = w wV)(UU((V where
w E _ U xmm V I and is the ReLU non-linearity.
13
Nauray
LOC Nawrlyy
2430
650
(a) LEO0, MNIST
(b) ALoO. MNIST
(c) LL00. CIFARIO
(d) ALoO. CIFARIO
Figure 6: Test and LOO losses (a, c) and accuracies (b, d) as function of depth L. We use fully- connected NTK model MNIST and CIFARIO.
C.3 DOUBLE DESCENT WITH RANDOM LABELS
Here we demonstrate how the spike in double descent is a very universal phenomenon as demon- strated by Theorem 4.3. We consider random feature model of varying width m on binary MNIST with n = 2000, where the labels are fully randomized (p 1), destroying thus any relationship between the inputs and targets. Of course, there will no double descent behaviour in the test ac- curacy as the network has to perform random guessing at any width. We display this in Figure 7. We observe that indeed the model is randomly guessing throughout all the regimes of overparametriza- tion. Both the test and LOO loss however, exhibit strong spike around the interpolation threshold. This underlines the universal nature of the phenomenon, connecting with the fact that Theorem 4.3 does not need any assumptions the targets.
C.4 TRANSFER LEARNING LOSS
We report the corresponding test and leave-one-out losses, moved to the appendix due to space constraints. We display the scores in Table 2. Again observe very good match between the test and LOO losses. Moreover, we again find that pre-training on ImageNer is beneficial in terms of the achieved loss values.
21

---

Published as a conference paper at ICLR 2022
Test LOO Loss
Accuracy
Accuracy
100
0.52
0.50
Acpuracy
Loss
0.48
40
0.44
20
0.42
0.40
1000
2000
3000
4000
1000
2000
3000
4000
Width
Width
Loss
(h) Accuracy
Figure 7: Test and LOO losses (a) and accuracies (b) as function of sample width m. We use random feature model on binary MNIST with random labels.
MODEL
FrEST(@Own)
TrEEsT TrTEsT(RAASE
RESNET18
0,602 + 0.0053
0.619 1 0.009
0.77 1 0.003
0.758 0.0051
ALEXNET
0.638 = 0.0021
0.639 + 0.0036
0.837 + 0.002
0.835 + 0.004
VGG16
0.657 = 0.0062
0.66 1 0.0091
0.852 + 0.0026
0.834 + 0.0049
DENSENET161
0.599 0.0044
0.613 0.0097
0.718 + 0.0043
0.731 0.0081
Table 2: Test and LOO losses for models pre-trained on ImageNet and transferred to CIFARIO by re-training the top layer. We use 5 runs, each with a different training set of size n 10000. We compare the pre-trained networks with random networks to illustrate the benefits of transfer learning.
22


Reviews:
[{"review_id": "xot6BsxKZLw", "reviewer": "Reviewer_dZ2X", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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. \n\nIt 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.\n\nThe 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.\n\nMy 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.\n\nAlso 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.\n\nFinally, 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.\n\n\n[1] Strobl, Eric V., and Shyam Visweswaran. \"Deep multiple kernel learning.\" 2013 12th International Conference on Machine Learning and Applications. Vol. 1. IEEE, 2013.\n\n[2] Dhar, Sauptik, Vladimir Cherkassky, and Mohak Shah. \"Multiclass learning from contradictions.\" Advances in Neural Information Processing Systems 32 (2019): 8400-8410.\n\n[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.\n\n[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.\n", "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.", "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.\n\n---\nBased on the authors' explanations and editions of the paper I change my score.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "vmnXKNn37k6", "reviewer": "Reviewer_k266", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "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.\n\nThe various forms of leave-one-out computations for ridge regression are quite well known and therefore do not provide that much novelty, see\nhttp://128.30.100.62:8080/media/fb/ps/MIT-CSAIL-TR-2007-025.pdf\nfor a summary and especially the multi-class classification has been implemented in several software libraries such as\nhttps://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.676.9100&rep=rep1&type=pdf\nand\nhttp://jmlr.org/papers/v17/16-470.html\nThe details concerning the \"ridgeless\" case may be less well known.\n\nWhile 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.\n", "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.\n", "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.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "msldiaF3p4D", "reviewer": "Reviewer_6oHc", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Strength:\n\n- 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. \n\n- Demonstrated agreement is quite good and indicates LOO metrics can be useful in kernel regression. \n\n- The paper is clearly written with good organization of presentation. \n\nWeakness:\n\n- 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) … \n\n- 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. \n\n- 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]. \n\n- 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. \n\n- 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)\n\nCorrections:\n\n- 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).\n- 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)\n-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. \n- 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.\n\n\nNit:\n- Please, include references in the main submission. Instructions for ICLR 2022 submission were to include both references and the appendix in the main file. \n\n-----------------------------------------------\nPost 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_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. \n\nSpecific contributions claimed by the authors are: \n- Extend LOO error for multi-class setting and closed-form formula for LOO accuracy\n- Demonstrate empirically LOO loss and accuracy capture generalization ability of deep learning in variety of settings\n- Utility of LOO on practical networks predicting transfer performance\n- Utilize the mathematical form of LOO loss to derive insights into double descent and the role of regularization\n", "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. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

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)