Year: 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 (Nagarajan & Kolter, 2019). 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.

heading: 1 INTRODUCTION
text: Neural networks have achieved astonishing performance across many learning tasks such as in computer 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 understanding 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 theoretically motivated by a connection to the concept of uniform stability (Pontil, 2002). It has also recently been advocated by Nagarajan & Kolter (2019) as a potential substitute for uniform convergence 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 a sudden tractable thanks to the availability of a closed-form expression due to Stone (1974, Eq. 3.13). While the role of the LOO error as an estimator of the generalization performance is debated in the statistics community
(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 error in the large sample limit, under mild assumptions on the data distribution. Inspired by these recent advances, in this work, we investigate the use of LOO as a 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 transfer 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 3 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 Github1.

heading: 2 RELATED WORK
text: Originally introduced by Lachenbruch (1967); Mosteller & Tukey (1968), the leave-one-out error is a standard tool in the field of statistics that has been used to study and improve a variety of models, 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-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 to fit polytope interpolators to a given neural network and estimate its resulting LOO error. Alaa & van der Schaar (2020) rely on a Jackknife estimator, applied in a LOO fashion to obtain better confidence intervals for Bayesian neural networks. Finally, we want to highlight the concurrent work of Zhang & Zhang (2021) who analyze the related concept of influence functions in the context of deep models.
Recent works have established a connection between kernel regression and deep learning. Surprisingly, 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 non-asymptotic 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. Moreover, 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 to 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 not been explored yet.
1https://github.com/gregorbachmann/LeaveOneOut

heading: 3 SETTING AND BACKGROUND
text: In the following, we establish the notations required to describe the problem of interest and the setting we consider. We study the standard learning setting, where we are given a dataset of inputtarget pairs S = {(x1,y1), . . . , (xn,yn)}where each (xi,yi)
i.i.d.∼ D for i = 1, . . . , n is distributed according to some probability measure D. We refer to xi ∈ X ⊂ Rd as the input and to y ∈ Y ⊂ RC as the target. We will often use matrix notations to obtain more compact formulations, thus summarizing all inputs and targets as matrices X ∈ Rn×d and Y ∈ Rn×C . We will mainly be concerned with the task of multiclass classification, where targets yi are encoded as one-hot vectors. We consider a function space F and an associated loss function Lf : X × Y −→ R that measures how well a given function f ∈ F performs at predicting the targets. More concretely, we define the regularized empirical error as
L̂λS : F −→ R, f 7→ 1
n n∑ i=1 Lf (xi,yi) + λΩ(f),
where λ > 0 is a regularization parameter and Ω : F −→ R is a functional. For any vector v ∈ RC , let v∗ = argmaxk≤C vk. Using this notation, we let af (x,y) := 1{f∗(x)=y∗}. We then define the empirical accuracy ÂS as the average number of instances for which f ∈ F provides the correct prediction, i.e.
ÂS : F −→ [0, 1], f 7→ 1
n n∑ i=1 af (xi,yi)
Finally, we introduce a learning algorithm QF : (X × Y)n −→ F , that given a function class F and a training set S ∈ (X × Y)n, chooses a function f ∈ F . We will exclusively be concerned with learning through empirical risk minimization, i.e.
QλF (S) := f̂λS := argminf∈F L̂λS(f),
and use the shortcut f̂S := f̂λ=0S . In practice however, the most important measures are given by the generalization loss and accuracy of the model, defined as
L : F −→ R, f 7→ E(x,y)∼D [Lf (x,y)] , A : F −→ [0, 1], f 7→ P(x,y)∼D (f∗(x) = y∗) .
A central goal in machine learning is to control the difference between the empirical error L̂S(f) and the generalization error L(f). In this work, we mainly focus on the mean squared loss,
Lf (x,y) = 1
2 C∑ k=1 (fk(x)− yk)2,
and also treat classification as a 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, we consider the function spaces induced by kernels and neural networks, presented in the following.

heading: 3.1 KERNEL LEARNING
text: A kernel K : X × X −→ R is a symmetric, positive semi-definite function, i.e. K(x,x′) = K(x′,x) ∀ x,x′ ∈ X and for any set {x1, . . . ,xn} ⊂ X , the matrix K ∈ Rn×n with entries Kij = K(xi,xj) 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 〈·, ·〉H, containing elements
H = cl ({ f : fk(·) = n∑ i=1 αikK(·,xi) for α ∈ Rn×C ,xi ∈ X })
where cl is the closure operator. Although H is an infinite dimensional space, it turns out that the minimizer f̂λS can be obtained in closed form for mean squared loss, given by
f̂λS (x) = K T x (K + λ1n)
−1 Y λ−→0−−−→ f̂S(x) := KTxK†Y
where the regularization functional is induced by the inner product of the space, Ω(f) = ||f ||2H, K ∈ Rn×n has entriesKij = K(xi,xj) andKx ∈ Rn has entries (Kx)i = K(x,xi). A† denotes the pseudo-inverse of A ∈ Rn×n. We will analyze both the regularized (f̂λS ) and unregularized model (f̂S ) and their associated LOO errors in the following. For a more in-depth discussion of kernels, we refer the reader to Hofmann et al. (2008); Paulsen & Raghupathi (2016).

heading: 3.2 NEURAL NETWORKS AND ASSOCIATED KERNELS
text: Another function class that has seen a rise in popularity is given by the family of fully-connected neural networks of depth L ∈ N,
FNN = { fθ : fθ(x) = W (L)σ ( W (L−1) . . . σ ( W (1)x ) . . . ) , forW (l) ∈ Rdl×dl−1 } ,
for dl ∈ N, d0 = d, dL = C and σ : R −→ R is an element-wise non-linearity. We denote by θ ∈ Rm the concatenation of all parameters ( W (1), . . . ,W (L) ) , where m = ∑L−1 i=0 didi+1 is the number of parameters of the model. The parameters are initialized randomly according to W
(l) ij ∼ N (0, σ2w) for σw > 0 and then adjusted to optimize the empirical error L̂S , usually through an iterative procedure using a variant of gradient descent. Typically, the entire vector θ is optimized via gradient descent, leading to a highly non-convex problem which does not admit a closed-form solution f̂ , in contrast to kernel learning. Next, we will review settings under which the output of a deep neural network can be approximated using a kernel formulation.
Random Features. Instead of training all the parameters θ, we restrict the function space by only optimizing over the top layer W (L) and freezing the other variables W (1), . . . ,W (L−1) to their value at initialization. This restriction makes the model linear in its parameters and induces a finitedimensional feature map
φRF : Rd −→ RdL−1 , x 7→ σ ( W (L−1) . . . σ ( W (1)x ) . . . ) .
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 σw = 1√dl for each layer, Lee et al. (2018) showed that at initialization, the network exhibits a Gaussian process behaviour in the infinite-width limit. More precisely, it holds that fk i.i.d.∼ GP ( 0,Σ(L) ) , for k = 1, . . . , C, where Σ(L) : Rd×Rd −→ R is a kernel, coined NNGP, obeying the recursive relation
Σ(l)(x,x′) = Ez∼N(0,Σ(l−1)|x,x′) [ σ(z1)σ(z2) ] with base Σ(1)(x,x′) = 1√
d xTx′ and Σ(l−1)|x,x′ ∈ R2×2 is Σ(l−1) evaluated on the set {x,x′}.
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 a constant kernel Θ. The so-called neural tangent kernel Θ : Rd × Rd −→ R is also available through a recursive relation involving the NNGP:
Θ(l+1)(x,x′) = Θ(l)(x,x′)Σ̇(l+1)(x,x′) + Σ(l+1)(x,x′), with base Θ(1)(x,x′) = Σ(1)(x,x′) and Σ̇(l)(x,x′) = Ez∼N (0,Σ(l−1)|x,x′ [ σ̇(z1)σ̇(z2) ] . Training infinitely-wide networks with gradient descent thus reduces to kernel learning with the NTK Θ(L). Arora et al. (2019a); Lee et al. (2019) extended this result to a non-asymptotic setting, showing that very wide networks trained with small learning rates become indistinguishable from kernel learning.

heading: 3.3 LEAVE-ONE-OUT ERROR
text: The goal of learning is to choose a model f ∈ F with minimal generalization error L(f). Since the data distribution D is usually not known, practitioners obtain an estimate for L(f) by using an
additional test set Stest = {(xt1,yt1) , . . . , (xtb,ytb)} not used as input to the learning algorithm QF , and calculate
Ltest = 1
b b∑ i=1 Lf (x t i,y t i), Atest = 1 b b∑ i=1 af (x t i,y t i) (1)
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 L(f) without having to rely on additional data (Lachenbruch, 1967; Mosteller & Tukey, 1968). We give a formal definition below.
Definition 3.1. Consider a learning algorithmQF and a training set S = {(xi,yi)}ni=1. Let S−i = S \ {(xi,yi)} be the training set without the i-th data point (xi,yi) and define f̂−i := QF (S−i), the corresponding model obtained by training on S−i. The leave-one-out loss/accuracy ofQF on S is then defined as the average loss/accuracy of f̂−i incurred on the left out point (xi,yi), given by
LLOO (QF ;S) = 1
n n∑ i=1 Lf̂−i(xi,yi), ALOO(QF ;S) = 1 n n∑ i=1 af̂−i (xi,yi)
Notice that calculating LLOO can indeed be done solely based on the training set. On the other hand, using the training set to estimate L(f) comes at a cost. Computing f̂−i for i = 1, . . . , n requires fitting the given model class n 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 LLOO for ResNet-152 on ImageNet requires fitting a model with 6 × 107 parameters 107 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, we will now show that the recently established connection between deep networks and kernel learning gives us an efficient way to compute LLOO. 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 a closedform solution, making the leave-one-out error more attractive in the setting we study.
In the following, we will use the shortcut f̂λS := f̂ λ. Surprisingly, it turns out that the space of kernels using QλF with mean-squared loss admits a closed-form expression for the leave-one-out error, only relying on a single model obtained on the full training set (X,Y ):
Theorem 3.2. Consider a kernelK : Rd×Rd −→ R and the associated objective with regularization parameter λ > 0 under mean squared loss. DefineA = K (K + λ1n) −1. Then it holds that
LLOO ( QλF ) = 1
n n∑ i=1 C∑ k=1 ( ∆λik )2 , ALOO ( QλF ) = 1 n n∑ i=1 1{ (yi−∆λi•) ∗ =y∗i } (2) where the residual ∆λik ∈ R for i = 1, . . . , n, k = 1, . . . , C is given by ∆λik = Yik−f̂λk (xi) 1−Aii .
For the remainder of this text, we will use the shortcut LλLOO := LLOO ( QλF ) . While the expression for LλLOO for C = 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 AλLOO is to the best of our knowledge a novel result. We provide a proof of Theorem 3.2 in the Appendix A.1. Notice that Theorem 3.2 not only allows for an efficient computation of LλLOO and A λ LOO but also provides us with a simple formula to assess the generalization behaviour of the model. It turns out that LλLOO captures a great variety of generalization phenomena, typically encountered in deep learning. Leveraging the neural tangent kernel together with Theorem 3.2 allows us to investigate their origin.
As a first step, we consider the zero regularization limit λ −→ 0, i.e. L0LOO since this is the standard setting considered in deep learning. A quick look at the formula reveals however that care has to be taken; as soon as the kernel is invertible, we have a 00 situation.
Corollary 3.3. Consider the eigendecompositionK = V diag(ω)V T forV ∈ O(n) andω ∈ Rn. Denote its rank by r = rank(K). Then it holds that the residuals ∆λik ∈ R can be expressed as
∆λik(r) = n∑ l=1 Ylk
∑n j=r+1 VijVlj + ∑r j=1 λ λ+ωj
VijVlj∑n j=r+1 V 2 ij + ∑r j=1 λ λ+ωj V 2ij
Moreover in the zero regularization limit, i.e. λ −→ 0, it holds that
∆λik(r) −→ ∆ik(r) =  n∑ l=1 Ylk ∑n j=r+1 VijVlj∑n j=r+1 V 2 ij
if r < n
n∑ l=1 Ylk
∑n j=1
1 ωj VijVlj∑n
j=1 1 ωj V 2ij
if r = n
Remark. At first glance for λ = 0, a distinct phase transition appears to take place when moving from r = n − 1 to r = n. Notice however that a small eigenvalue ωn will allow for a smooth interpolation, i.e. ∆ik(n)
ωn−→0−−−−→ ∆ik(n− 1) for i = 1, . . . , n, k = 1, . . . , C. A similar result for the special case of 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.

heading: 4 LEAVE-ONE-OUT AS A GENERALIZATION PROXY
text: 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, in the case of infinitely-wide networks. We evaluate the models on the benchmark vision datasets MNIST (LeCun & Cortes, 2010) and CIFAR10 (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-art networks by predicting their transferability to new tasks. All experiments are performed in Jax (Bradbury et al., 2018) using the neural-tangents library (Novak et al., 2020).

heading: 4.1 FUNCTION OF SAMPLE SIZE
text: While known to exhibit only a small amount of 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 as a function of the sample size n. In the following we thus interpret LOO as a function of n. In order to quantify how well LOO captures the generalization error for different sample regimes, we evaluate a 5-layer fully-connected NTK model for varying sample sizes on MNIST and CIFAR10. We display the resulting test and LOO losses in Figure 1. We plot the average result of 5 runs along with confidence intervals. We observe that both LLOO and ALOO closely follow their corresponding test quantity, even for very small sample sizes of around n = 500. As we increase the sample size, the variance of the estimator decreases and the quality of both LOO loss and accuracy improves even further, offering a very precise estimate at n = 20000.

heading: 4.2 RANDOM LABELS
text: Next we study the behaviour of the generalization error when a portion of the labels is randomized. In Zhang et al. (2017), the authors investigated how the performance of deep neural networks is affected when the functional relationship between inputs x and targets y is destroyed by replacing y by a random label. More specifically, given a dataset X ∈ Rn×d and one-hot targets y = ek for k ∈ {1, . . . , C}, we fix a noise level p ∈ [0, 1] and replace a subset of size pn of the targets with
random ones, i.e. y = ek̃ for k̃ ∼ U({1, . . . , C}). We then train the model using the noisy targets ỹ 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 et al., 2019b; 2018; Bartlett et al., 2017). We now show how the leave-one-out error exhibits the same behaviour as the test error 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 a function of the labels, i.e. LLOO = LLOO(y). The phenomenon of noisy labels is of particular interest when the model has enough capacity to achieve zero empirical error. For kernels, this is equivalent to rank(K) = n and we will thus assume in this section that the kernel matrix has full rank. However, a 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 f̂−iS̃ against ỹi since ỹi might be one of the randomized labels. Instead, we want to compare f̂−iS̃ with the true label yi, 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 = V diag(ω)V T for V ∈ Rn×n orthogonal and ω ∈ Rn. Assume that rank(K) = n. Then it holds that the leave-one-out error LLOO(Ỹ ;Y ) for a model trained on S̃ = {(xi, ỹi)}ni=1 but evaluated on S = {(xi,yi)}ni=1 is given by
LLOO(Ỹ ;Y ) = 1
n n∑ i=1 K∑ k=1 ( ∆̃ik + Yik − Ỹik )2 , ALOO(Ỹ ;Y ) = 1 n n∑ i=1 1{ (ỹi−∆̃i•) ∗ =y∗i } where ∆̃ik = ∆ik(Ỹ ) ∈ R is defined as in Corollary 3.3.
We defer the proof to the Appendix A.4. Attentive readers will notice that we indeed recover Theorem 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 CIFAR10 with n = 20000 for a NTK model of depth 5, where we 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 as well test and LOO accuracy, highlighting how precisely LOO reflects the true error.

heading: 4.3 DOUBLE DESCENT
text: 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, increasing 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
restrictive assumptions such as Gaussian input distributions (Harzli et al., 2021; Adlam & Pennington, 2020; d’Ascoli et al., 2020) or teacher models (Bartlett et al., 2020; Harzli et 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 a spike at the interpolation threshold.
In order to reason about the effect of complexity, we have to consider models with a finite dimensional feature map φm : Rd −→ Rm. Increasing the dimensionality of the feature space Rm naturally overparametrizes the model and induces a dynamic in the rank r(m) := rank(K) = rank (φm(X)). We restrict our attention to models that admit an interpolation point, i.e. ∃m∗ ∈ N such that r(m∗) = n. While the developed theory holds for any kernel, we focus the empirical evaluations largely to the random feature model due to its aforementioned connection to neural networks. In the following, we will interpret the leave-one-out-error as a function of m and n, i.e. LLOO = L n LOO(m). Notice that L n LOO(m) measures the generalization error of a model trained on n − 1 points, instead of n. The underlying interpolation point thus shifts, i.e. we denote m∗ ∈ N such that r(m∗) = n− 1. In the following we will show that LnLOO(m∗(n)) n−→∞−−−−→∞.
Intuition. We give a high level explanation for our theoretical insights in this paragraph. For m < m∗ the dominating term in LnLOO(m) is
g(r, λ) = n∑ i=1 1∑n l=r+1 V 2 il + ∑r l=1 λ λ+ωl V 2il
We observe a blow-up for small λ due to the unit vector nature of both Vi• and V•j . For instance, considering the interpolation point where r = n − 1 and λ = 0, we get g(n − 1, 0) = ∑n i=1
1 V 2in , the sum over the elements of V•n, which likely has a small entry due to its unit norm nature. On the other hand, reducing r or increasing λ has a dampening effect as we combine multiple positive terms together, increasing the likelihood to move away from the singularity. A similar dampening behaviour in LnLOO(m) can also be observed for m > m
∗ when ωn >> 0. In order to formalize this argument, we need the following assumption: Assumption 4.2. ForK = V diag (ω)V T we impose that the orthogonal matrix V follows
V ∼ U (On) where U (On) is the Haar measure on the orthogonal group On.
Under Assumption 4.2, we can prove that at the interpolation point, the leave-one-out error exhibits a spike, which worsens as we increase the amount of data:
Theorem 4.3. For large enough n ∈ N and λ −→ 0, it holds that
LnLOO(m ∗) ' 2nA
where A ∼ Γ( 12 , 1) is independent of n. L n LOO(m ∗) hence diverges a.s. with n −→∞.
It 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 a sample size of n = 5000. We observe that the LOO error indeed closely follows the
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∗ ≈ n.

heading: 4.4 TRANSFER LEARNING
text: Finally, we study more realistic networks often employed for large-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 CIFAR10 dataset. Notice that this corresponds to training a kernel with a data-dependent feature map φdata induced by the nonoutput 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 of the test accuracy. We display the results in Table 1. We consider a small data regime where n = 10000, as often encountered in practice for transfer learning tasks. In order to highlight the role of pre-training, we also evaluate random feature maps φrand where we use standard initialization for all the parameters in 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 leave-one-out accuracies across all architectures.

heading: 5 CONCLUSION
text: We investigated the concept of leave-one-out error as a measure for generalization in the context of 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 a minimal set of theoretical tools. Finally, we demonstrated that LOO accurately predicts the performance of deep models in the setting of transfer learning.
Notably, the simple form of LOO might open the door to new types of theoretical analyses to better understand generalization, allowing for a disentanglement of the roles of various factors at play such as overparametrization, noise and architectural design.

heading: A OMITTED PROOFS
text: We list all the omitted proofs in the following section.

heading: A.1 PROOF OF THEOREM 3.2
text: Theorem 3.2. Consider a kernelK : Rd×Rd −→ R and the associated objective with regularization parameter λ > 0 under mean squared loss. DefineA = K (K + λ1n) −1. Then it holds that
LLOO ( QERMλ ) = 1
n n∑ i=1 K∑ k=1 ( ∆λik )2 , ALOO ( QERMλ ) = 1 n n∑ i=1 1{ (yi−∆i•)∗=y∗i } where the residuals ∆λik ∈ R for i = 1, . . . , n, k = 1, . . . ,K is given by ∆λik = Yik−f̂λk (xi) 1−Aii .
Proof. Recall that f̂λS solves the optimization problem
f̂λS = argminf∈F L λ S(f) := argminf∈F { n∑ i=1 K∑ k=1 (fk(xi)− Yik)2 + λ||f ||2H }
and predicting on the training data takes the form f̂S(X) = AY for some A ∈ Rn×n. Now consider the model f−iλ := f̂ λ S−i obtained from training on S−i. W.L.O.G. assume that i = n. We want to understand the quantity f̂−nλ,k (xn), i.e. the k-th component of the prediction on xi. To that
end, consider the dataset Z := S−n ∪ {( xn, f̂ −n λ (xn) )} . Notice that for any f ∈ F , it holds
LλZ(f̂ −n λ ) = C∑ k=1 { n−1∑ i=1 ( f̂−nλ,k (xi)− Yik )2 + ( f̂−nλ,k (xn)− f̂ −n λ,k (xn) )2 } + λ||f̂−nλ || 2 H
= C∑ k=1 n−1∑ i=1 ( f̂−nλ,k (xi)− Yik )2 + λ||f̂−nλ || 2 H
= LλS−n ( f̂−nλ ) ≤ LλS−n(f)
≤ LλS−n(f) + C∑ k=1 ( fk(xn)− f̂−nλ,k (xn) )2 = LλZ(f)
where the first inequality follows because f̂−n minimizes LλS−n by definition. Thus f̂ −n λ also minimizes LλZ and hence also takes the form
f̂−nλ (X) = AỸ
where Ỹ ∈ Rn×C such that Ỹik = { Yik if i 6= n f̂−nλ,k (xn) else . Now we care about the n-th prediction which is
f̂−nλ,k (xn) = n∑ j=1 Anj Ỹjk = n−1∑ j=1 AnjYjk +Annf̂ −n λ,k (xn)
= n∑ j=1 AnjYjk −AnnYnk +Annf̂−nλ,k (xn)
= f̂λS,k(xn)−AnnYnk +Annf̂−nλ,k (xn)
Solving for f̂−nλ,k (xn) gives
f̂−nλ,k (xn) = f̂λS,k(xn)−AnnYnk
1−Ann (3)
Then, subtracting Ynk leads to
Ynk − f̂−nλ,k (xn) = Ynk − f̂λS,k(xn)−AnnYnk 1−Ann = Ynk − YnkAnn − f̂λS,k(xn) +AnnYnk 1−Ann = Ynk − f̂λS,k(xn)
1−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 f̂−nλ (xn) agrees with the maximal coordinate of yn, i.e.
argmaxk f̂ −n λ,k (xn) = argmaxk Ynk
From equation 3, we notice that
argmaxk f̂ −n λ,k (xn) = argmaxk f̂λS,k(xn)−AnnYnk 1−Ann = argmaxk f̂λS,k(xn)− Ynk + Ynk −AnnYnk
1−Ann = argmaxk −∆λnk + Ynk = (yn −∆n•)∗
We thus have to check the indicator 1{(yn−∆n•)∗=y∗n} and sum it over n to obtain the result.

heading: A.2 BINARY CLASSIFICATION
text: Here we state the corresponding results in the case of binary classification. The formulation for the accuracy changes slightly as now the sign of the classifier serves as the prediction. Proposition A.1. Consider a kernel K : Rd × Rd −→ R and the associated objective with regularization parameter λ > 0 under mean squared loss. Define A = K (K + λ1n)
−1. Then it holds that
LLOO ( QERMλ ) = 1
n n∑ i=1 ( ∆λi )2 , ALOO ( QERMλ ) = 1 n n∑ i=1 1{yi∆λi <1}
where the residuals ∆λi ∈ R for i = 1, . . . , n is given by ∆λi = yi−f̂λ(xi) 1−Aii .
Proof. Notice that the result for LLOO 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 yf̂λ(x) > 0. We can thus calculate that
ynf̂ −n λ (xn) =
ynf̂ λ S (xn)−Anny2n
1−Ann = ynf̂
λ S (xn)− y2n + y2n − y2nAnn
1−Ann
= y2n − yn yn − f̂λS (xn)
1−Ann
= 1− yn yn − f̂λS (xn) 1−Ann = 1− yn∆λn
Thus, the n-th sample is correctly classified if and only if
1− yn∆λn > 0 ⇐⇒ yn∆λn < 1 We now just count the correct predictions for the accuracy, i.e.
ALOO ( QERMλ ) = 1
n n∑ i=1 1{yi∆λi <1}

heading: A.3 PROOF OF COROLLARY 3.3
text: Corollary 3.3. Consider the eigendecompositionK = V diag(ω)V T for V ∈ O(n) and ω ∈ Rn. Denote its rank by r = rank(K). Then it holds that the residuals ∆λik ∈ R can be expressed as
∆λik(r) = n∑ l=1 Ylk
∑n k=r+1 VikVlk + ∑r k=1 λ λ+ωk
VikVlk∑n k=r+1 V 2 ik + ∑r k=1 λ λ+ωk V 2ik
Moreover for zero regularization, i.e. λ −→ 0, it holds that
∆λik(r) −→ ∆ik(r) =  n∑ l=1 Ylk ∑n j=r+1 VijVlj∑n j=r+1 V 2 ij
if r < n
n∑ l=1 Ylk
∑n j=1
1 ωj VijVlj∑n
j=1 1 ωj V 2ij
if r = n
Proof. Define A = K (K + λ1n) −1 ∈ Rn×n. Recall that f̂λS (X) = Ay and thus f̂λk (xi) =∑n
j=1AijYjk. Let us first simplifyA:
A = K (K + λ1n) −1 = V diag (ω)V T ( V diag (ω)V T + λ1n )−1 = V diag ( ω
ω + λ
) V T
We can characterize the off-diagonal elements for i 6= j as follows:
Aij = n∑ k=1 Vik ωi ωi + λ Vjk = r∑ k=1 VikVjk ωi ωi + λ = r∑ k=1 VikVjk − r∑ k=1 λ ωk + λ VikVjk
= − n∑
k=r+1
VikVjk − r∑
k=1
λ
ωk + λ VikVjk
where we made use of the fact that Vi• ⊥ Vj•. The diagonal elements i = j on the other hand can be written as
Aii = n∑ k=1 V 2ik ωi ωi + λ = r∑ k=1 V 2ik ωk ωk + λ = r∑ k=1 V 2ik − r∑ k=1 V 2ik λ ωk + λ
= 1− n∑
k=r+1
V 2ik − r∑
k=1
V 2ik λ
ωk + λ
where we have made use of the fact that Vi• is a unit vector. Plugging-in the quantities into LLOO results in
∆λik = Yik − f̂λk (xi) 1−Aii = Yik −
∑n l=1AilYlk
1−Aii = Yik −Aiiyi −
∑n l 6=iAilYlk
1−Aii
= Yik
(∑n j=r+1 V 2 ij + ∑r k=1 V 2 ij λ ωj+λ ) + ∑n l 6=i Ylk (∑n j=r+1 VijVlj + ∑r j=1 λ ωj+λ VijVlj ) ∑n j=r+1 V 2 ij + ∑r j=1 V 2 ij λ ωl+λ
=
∑n l=1 Ylk (∑n j=r+1 VijVlj + ∑r j=1 λ ωj+λ VijVlj ) ∑n j=r+1 V 2 ij + ∑r j=1 V 2 ij λ ωk+λ
Now crucially, in the full rank case r = n, we have empty sums, i.e. ∑n l=r+1 = ∑n l=n+1 = 0 and we obtain
∆λik =
∑n l=1 Ylk ∑n j=1 λ ωj+λ
VijVlj∑n j=1 V 2 ij λ ωj+λ =
∑n l=1 Ylk ∑n j=1 1 ωj+λ
VijVlj∑n j=1 V 2 ij 1 ωj+λ
λ−→0−−−→ n∑ l=1 Ylk
∑n j=1
1 ωj VijVlj∑n
j=1 1 ωj V 2ij
On the other hand, in the rank deficient case r < n we can cancel the regularization term:
∆λik λ−→0−−−→ n∑ l=1 Ylk ∑n j=r+1 VijVlj∑n j=r+1 V 2 ij
Plugging this into the formulas for LλLOO and A λ LOO concludes the proof.

heading: A.4 PROOF OF PROPOSITION 4.1
text: Proposition 4.1. Consider a kernel with spectral decomposition K = V diag(ω)V T for V ∈ Rn×n orthogonal and ω ∈ Rn. Assume that rank(K) = n. Then it holds that the leave-one-out error LLOO(Ỹ ;Y ) for a model trained on S̃ = {(xi, ỹi)}ni=1 but evaluated on S = {(xi,yi)}ni=1 is given by
LLOO(Ỹ ;Y ) = 1
n n∑ i=1 C∑ k=1 ( ∆̃ik + Yik − Ỹik )2 , ALOO(Ỹ ;Y ) = 1 n n∑ i=1 1{ (ỹi−∆̃i•) ∗ =y∗i } where ∆̃ik = ∆ik(Ỹ ) ∈ R is defined as in Corollary 3.3.
Proof. Denote by S̃−i the dataset {(xj , ỹj)}nj 6=i. Denote by f̃ −i λ the model trained on S̃−i. Recall from the proof of Theorem 3.2 that
f̃−nλ,k (xn) = f̃λk (xn)−AnnỸnk
1−Ann Instead of subtracting the same label Ỹnk, we now subtract the evaluation label Ynk:
Ynk − f̃−nλ,k (xn) = Ynk −AnnYnk − f̃λk (xn) +AnnỸnk
1−Ann = (1−Ann)(Ynk − Ỹnk) + Ỹnk − f̃λk (xn) 1−Ann
= (Ynk − Ỹnk) + Ỹnk − f̃λk (xn) 1−Ann = (Ynk − Ỹnk) + ∆̃λik
The second term ∆̃λik is 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 the LOO loss result. For the accuracy, we notice that a similar derivation as for Theorem 3.2 applies:
argmaxk f̃ −n λ,k (xn) = argmaxk f̃λk (xn)−AnnỸnk 1−Ann = argmaxk f̂λk (xn)− Ỹnk + Ỹnk −AnnỸnk
1−Ann = argmaxk −∆̃λnk + Ỹnk
= ( ỹn − ∆̃n• )∗ We thus have to check the indicator against the true label yn, i.e. 1{(ỹn−∆̃n•)∗=y∗n} and sum it over n to obtain the result.

heading: A.5 PROOF OF THEOREM 4.3
text: Theorem 4.3. For large enough n ∈ N, we can estimate as LnLOO(m ∗) ' 2nA
where A ∼ Γ( 12 , 1) is independent of n. L n LOO(m ∗) hence diverges a.s. with n −→∞.
Proof. First we notice that for m = m∗, by definition it holds that r = n − 1, which simplifies the LOO expression to
LnLOO(m ∗) λ−→0−−−→ 1 n ( n∑ i=1 1 V 2in )( n∑ i=1 yiVin )2
For notational convenience, we will introduce v ∈ Rn such that vi := 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:
LnLOO(m ∗) =
1
n ( n∑ i=1 vi )2 n∑ i=1 1 v2i ≥ n2 1 n ( n∑ i=1 vi )2 (d) = n2B
Now for large enough n, we can use Lemma B.6 to make the following approximation in distribution:
nB ≈ 2n− 1 2 B (d)−−→ 2A
where A ∼ Γ( 12 , 1). Thus for large enough n, it holds that
LnLOO(m ∗) ' 2nA
As the approximation becomes exact for larger and larger n, we conclude that
LnLOO(m ∗)
n−→∞−−−−→∞ a.s.

heading: B ADDITIONAL LEMMAS
text: 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 v ∈ Sn−1. Then it holds that n∑ i=1 1 v2i ≥ n2
Proof. Let’s parametrize each vi as vi = zi√∑n i=1 z 2 i for i = 1, . . . , n and z ∈ Rn. One can easily check that ||v||2 = 1 and hence v ∈ Sn−1. Plugging this in, we arrive at
n∑ i=1 1 v2i = n∑ i=1
∑n j=1 z 2 j
z2i = n∑ i=1 n∑ j=1 z2j z2i = n+ n∑ i=1 n∑ j 6=i z2j z2i
We can re-arrange the sum into pairs
z2j z2i + z2i z2j = a2 + 1 a2 ≥ 2
for a2 = z2j z2i > 0 and using the fact that x+ 1x ≥ 2 for x ≥ 0. We can find n(n−1) 2 such summands, and thus n∑ i=1 1 v2i ≥ n+ 2n(n− 1) 2 = n2 Lemma B.2. Consider v ∼ U ( Sn−1 ) and any fixed orthogonal matrix U ∈ O(n). Then it holds that Uv (d) = v
Proof. This is a standard result and can for instance be found in Vershynin (2018).
Lemma B.3. Consider w ∼ N (0,1n). Then it holds that
v = w
||w||2 ∼ U
( Sn−1 ) Proof. This is a standard result and can for instance be found in Vershynin (2018).
Lemma B.4. Consider two independent Gamma variables X ∼ Gamma(α, ν) and Y ∼ Gamma(β, ν). Then it holds that
X
X + Y ∼ Beta (α, β)
Proof. This is a standard result and can for instance be found in Bowman et al. (1998). Lemma B.5. Consider v ∼ U ( Sn−1 ) . Then it holds that
1
n ( n∑ i=1 yivi )2 ∼ Beta ( 1 2 , n− 1 2 )
Proof. First realize that we can write
1√ n n∑ i=1 yivi = 1̃ T n (v y) (d) = 1̃Tnv
where 1̃n = (
1√ n , . . . , 1√ n ) with ||1̃n||2 = 1 and the fact that v y (d) = v for fixed y ∈ {−1, 1}n.
The idea is now to chooseU ∈ O(n) such thatUT 1̃n = e1 = (1, 0, . . . , 0). Then by using Lemma B.2, it holds
1̃Tnv (d) = 1̃TnUv (d) = ( U 1̃n )T v (d) = eT1 v (d) = v1
Thus, surprisingly, it suffices to understand the distribution of v1. By Lemma B.3, we know that
v1 (d) = z1√ z21 + · · ·+ z2n
where z ∼ N (0,1n). We are interested in the square of this expression,
1
n ( n∑ i=1 vi )2 (d) = v21 (d) = z21 z21 + · · ·+ z2n (d) = z21 z21 + w
where we define w = ∑n i=2 z 2 i , clearly independent of z 2 1 . Moreover, it holds that z 2 1 ∼
Gamma (
1 2 , 1 2
) and w ∼ Gamma ( n−1
2 , 1 2
) . Thus, by Lemma B.4 we can conclude that
1
n ( n∑ i=1 vi )2 ∼ Beta ( 1 2 , n− 1 2 )
Lemma B.6. Consider the sequence of Beta distributions Xn ∼ Beta(k, n). Then it holds that
nXn (d)−−→ Gamma(k, 1)
Proof. This is a standard result and can for instance be found in Walck (1996).

heading: C FURTHER EXPERIMENTS
text: In this section we present additional experimental results on the leave-one-out error.

heading: C.1 RANK DYNAMICS FOR DIFFERENT KERNELS
text: In this section, we illustrate how the rank rank(K) of the kernel evolves as a function of the underlying 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 is able to achieve zero training loss. Naturally, for the kernel formulation, interpolation is 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. 4 (a) we show a depth 1 random feature model with feature maps σ(Wx) where W ∈ Rm×d and σ is the ReLU non-linearity. We use MNIST with n = 100. We measure the complexity through the width m of the model. We observe that in this special case, the critical complexity exactly coincides with the number of samples, i.e. rank(K) = n as soon as m = n. This seems counter-intuitive at first as an exact match of the complexity with the sample size is usually not observed for standard neural networks. We show however in Fig. 4 (b) and (c) that the rank dynamics indeed become more involved for larger depth. In Fig. 4 (b) and (c), we use a 2-layer random feature model with feature map σ(V σ(Wx)) for weights W ∈ Rm1×d and V ∈ Rm2×m1 . In (b) we show the change in rank as m1 increases, while m2 = 120 is fixed. We observe that indeed the dynamics change and the critical complexity is not at m1 = n. Similarly in (c) we fix m1 = 10 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.
Finally we also study the linearizations of networks that also give rise to kernels. More concretely, we consider feature maps of the form
φ(x) = ∇θfθ(x)
where fθ is a fully-connected network with parameters θ ∈ Rp, as introduced before. Our doubledescent framework also captures this scenario. In Fig. 5, we display the rank dynamics in case of a 2 layer network fθ(x) = wTσ(Uσ(V x)) where w ∈ Rm2 , U ∈ Rm2×m1 , V ∈ Rm1×d and σ is the ReLU non-linearity. Again we observe that the rank dynamics change and do not coincide with the number of samples n.

heading: C.2 LOO AS FUNCTION OF DEPTH L
text: We study how the depth L of the NTK kernel Θ(L) affects the performance of LOO loss and accuracy. We use the datasets MNIST and CIFAR10 with n = 5000 and evaluate NTK models with depth ranging from 3 to 20. We present our findings in Figure 6. Again we see a very close match between LOO and the corresponding test quantity for CIFAR10. Interestingly the performance is slightly worse for very shallow models. For MNIST we see a gap between LOO loss and test loss, which is due to 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.

heading: C.3 DOUBLE DESCENT WITH RANDOM LABELS
text: Here we demonstrate how the spike in double descent is a very universal phenomenon as demonstrated by Theorem 4.3. We consider a 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 be no double descent behaviour in the test accuracy 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 overparametrization. Both the test and LOO loss however, exhibit a 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 on the targets.

heading: C.4 TRANSFER LEARNING LOSS
text: 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 we observe a very good match between the test and LOO losses. Moreover, we again find that pre-training on ImageNet is beneficial in terms of the achieved loss values.

Review summaries:
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 

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.

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.