Phenomenology of Double Descent in Finite-Width Neural Networks
Authors: Sidak Pal Singh
Aurelien Lucchi
Thomas Hofmann
Bernhard Schölkopf
Venue: ICLR 2022 Poster (2022)
Keywords: double descent
generalization
neural networks
hessian
flatness

Abstract: `Double descent' delineates the generalization behaviour of models depending on the regime they belong to: under- or over-parameterized. The current theoretical understanding behind the occurrence of this phenomenon is primarily based on linear and kernel regression models --- with informal parallels to neural networks via the Neural Tangent Kernel. Therefore such analyses do not adequately capture the mechanisms behind double descent in finite-width neural networks, as well as, disregard crucial components --- such as the choice of the loss function. We address these shortcomings by leveraging influence functions in order to derive suitable expressions of the population loss and its lower bound, while imposing minimal assumptions on the form of the parametric model. Our derived bounds bear an intimate connection with the spectrum of the Hessian at the optimum, and importantly, exhibit a double descent behaviour at the interpolation threshold. Building on our analysis, we further investigate how the loss function affects double descent --- and thus uncover interesting properties of neural networks and their Hessian spectra near the interpolation threshold.

Published as a conference paper at ICLR 2022
PHENOMENOLOGY OF DOUBLE DESCENT IN FINITE-WI WIDTH NEURAL NETWORKS
Sidak Pal Singh" as, Aurelien Lucchi", Thomas Hofmann" and Bernhard Schölkopf
"ETH Zürich, Switzerland
Department of Mathematics and Computer Science, University of Basel MPI for Intelligent Systems, Tübingen, Germany
ABSTRACT
'Double descent' delineates the generalization behaviour of models depending on the regime they belong to: under- or over-parameterized. The current theoretical understanding behind the occurrence of this phenomenon is primarily based on linear and kernel regression models with informal parallels to neural networks via the Neural Tangent Kernel. Therefore such analyses do not adequately capture the mechanisms behind double descent in finite-width neural networks, as well as, disregard crucial components - such as the choice of the loss function. We address these shortcomings by leveraging influence functions in order to derive suitable expressions of the population loss and its lower bound, while imposing minimal assumptions on the form the parametric model. Our derived bounds bear intimate connection with the spectrum of the Hessian at the optimum, and importantly, exhibit a double descent behaviour at the interpolation threshold. Building our analysis, ble descent - and thus uncover interesting properties of neural networks and their Hessian spectra near the interpolation threshold.
further investigate how the loss function affects dou-
INTRODUCTION
Double-descent (DD) (Belkin et al., 2019) refers to the phenomenon of population (or test) loss ex- hibiting second descent when the model is wer-parameterize beyond certain threshold (dubbed as the interpolation threshold). While such a behaviour has been originally observed in multiple contexts before (Loog et al., 2020), this terminology has been made commonplace by the influential work of (Belkin et al., 2019), who posited DD as way to reconcile the traditional statistical wis- dom with modern-day usage in machine learning. In particular, when models such as deep neural networks are employed the over-parameterized regime, this second descent in test loss is seen as an extension of the usual U-shaped bias-variance curve thus providing basis reason about the amazing generalization abilities of neural networks despite their extreme surplus of parameters.
As result, there have been vast number of studies that investigate DD further and others that seek to explain the underlying mechanisms. The former category of works (Nakkiran et al., 2019) has served to make this phenomenon conspicuous even in the context of frequently employed deep networks and shown the existence of such DD like behaviour based on other axes such as the amount of data or number of epochs (Nakkiran, 2019; Nakkiran et al., 2019); while the latter category of studies (Hastie et al., 2019; Mei & Montanari, 2019; Advani et al., 2020; Bartlett et al., 2020) has provided the theoretical grounds for the occurrence of such a phenomenon, but almost always, in linear or kernel regression. Although the connection of (infinite-width) neural networks to Neural Tangent Kernel (Jacot et al., 2018) provides interesting parallels, its applicability to finite-width neural networks i.e., models of actual practical significance is unclear.
Hence, our aim is to go beyond such informal correspondences, and instead, thoroughly understand and characterize the phenomenology of double descent in finite-wdthh neural networks. In other words, we develop a theoretical analysis that can explain the source of double descent in the class of models that originally brought this phenomenon the limelight, well study the impact of crucial training-related aspects, such as the choice of the loss function. To this end, we derive
"Correspondence s sidak. n nf ethz. ch. The most recent version of our paper be found aiv and the code for the experiments is available on GitHub.

---

Published as a conference paper at ICLR 2022
an expression for the population risk by considering the change in the loss at a particular sample when excluded from the training set and when included. We do so by utilizing the notion of influence functions from robust statisties, which provides change in parameters. Subsequently, we establish a lower bound to the population risk and leverage results from Random Matrix Theory to show that it diverges the interpolation threshold thereby demonstrating the presence of double descent.
with a closed-form estimate of the
The use of influence functions (Hampel et al., 1986; Efron & Stein, 1981) makes our analysis appli- cable to a broad class of parametric estimators such as maxiium--ikelihood---
- which includes the class of neural networks but also applies to other settings such as linear and kernel regression as a special case (see Section A.4). As a result, this approach allows us to probe the effect of the loss functions used to train neural networks - which, as we will see, clearly influences the nature of DI) and reveals novel insights into the properties of neural networks near the interpolation threshold.
Contributions. (a) Section 3: We derive a generalization expression based on 'add-one-in' (akin to 'leave-oneoout') procedure that requires minimal assumptions and, in principle, allows us to analyze the population risk of any neural network or linear/kernel regression model. (b) Sec- tion 4: We show how this yields a suitable asymptotic lower-bound, which diverges at the inter- polation threshold and helps explain double descent for neural networks via the Hessian spectra at the optimum. We additionally support the theoretical arguments by an empirical investigation of the involved quantities, which also suggests its applicability in the non-asymptotic setting. (c) Section 5: We thoroughly study the effect of the loss function by exploring in detail the double descent behaviour for cross-entropy loss, such as the location of the interpolation threshold, Hessian spectra near interpolation, as well as discuss novel insights implied by these observations. (d) Sec- tion 6: Lastly, as a by-product of our influence functions based approach, we derive a generalized closed-form expression for ceave-oneour loss that applies to finite- neural networks.
SETUP AND BACKGROUND
Let us consider the general setting of statistical estimation. Assume that the input samples z E Z drawn i.i.d. from some (unknown) distribution D. A parametric model can be defined family of probability distributions Dg on the sample space Z, where f E O. The main task is to find an estimate O of the parameters such that "Da ~ D", but given finite set of samples S = {211... ................................ ) drawn i.i.d from D. The parameter estimator, 0, is considered to be provided by some statistic T( 2n.. Alternatively, if we denote the empirical distribution of the dataset by D., then the parameter estimator can be written as a functional, 0p. := =D.),) = T(D,).
2.1 INFLUENCE FUNCTIONS: A QUICK PRIMER
Quite often we are interested in analyzing how a slight contamination in the distribution affects, say, the estimated parameters 0, or some other statistic T. Specifically, when this contamination can be expressed in the form of Dirac distribution 8z. the (standardized) change in the statistic T can be obtained via the concept of influence functions.
Definition 1. (Hampel et al. (1986)) The influence function IF of a statistic T based on some distri-
bution D, is given by, IF(z;T, = lim.-- T (11 e) + e62) T(D) evaluated on a point
Z where such a limit exists.
Essentially, the influence function (IF) involves a directional derivative of D along the direction of 8z. More generally, one can view influence functions from the perspective of Taylor series expansion (or what is referred to in this context as the first-order von Mises expansion) of T at D, evaluated on some distribution D close to D: T(D) = T(D)+ + ff DD) d)D((DD) + O(())
So, as evident from this, it is also possible to utilize higher-order influence functions as considered in Debruyne et al. (2008). However, the first-order term is usually the dominating term and to ensure tractability when we later consider neural networks we will restrict our attention to first- order influence functions hereafter. Influence functions have a long history as an important tool, particularly in robust statistics (Hampel al., 1986), but lately also in deep learning (Koh & Liang, 2017). Not only do they have useful properties (see Appendix B.1 for a detailed background), but they form natural tool to analyze changes in distribution (c.g., leave-one-out estimation).
2

---

Published as a conference paper at ICLR 2022
2.2 INFLUENCE FUNCTION FOR MAXIMUM LIKELIHOOD TYPE ESTIMATORS
In general, we do not explicitly have the analytic form of the estimator 0 - but implicitly as the solution to an optimization problem (e.g., parameters of neural networks obtained via training). So, let us consider influence functions for the class of 'maximum likelihood type' estimators (or M-
estimators), i.c. satisfying the implicit equation, IE (2; 0. Let assume that the z>D
function (2; 0) Vol(z. 0), where the (loss) function L 2 θ R is twice-differentiable in the parameters 0. When the loss l is the negative log- ligllikel,hod,, we recover the usual maximum likelihood estimator, 0 = arg mingge EznD [e(z,)) 0)] The following proposition describes the influence function for such an estimator 0 (all the omitted proofs can be found in Appendix A).
Proposition 2. The (first-order) influence function IF of the M-estimator 0p based on the distribution D. evaluated at point 2, takes the following form: [F D) Hc) Vol(z,00) (0(z,,0), where, the Hessian matrix Hc(Op) == Va C(0 contains the second derivative of the loss C(0) = z~ ()) with respect to the parameters 0.
Remark. The Hessian in neural networks is typically rank deficient (Sagun al., 2017; Singh et al., 2021), so for the sake our analysis we will consider an additive regularization term AI, A >> 0, alongside the (z term in the above-mentioned IF formula and call this modification x- Later, we will take the limit -
EXPRESSION OF THE POPULATION RISK
As we lack access to the true distribution, we usually take the route of empirical risk minimization and consider 0s == arg mingee (0) with (0 := 1/2 E==1(( ((z,, 0) and recall, S = {z,} is the training set of size However, in regards to performance, our actual concern is the population risk (()) = ED (). which is measured empirically via the loss (0) on some unseen (test) set S To analyze double descent (Belkin al., 2019)-i.e. i.e., with increasing model capacity, the population risk exhibits peak before descending again (besides the usual first descent) - we first derive suitable expression of the population risk that will also apply neural networks.
'Add-one-in' procedure. Let us consider how the parameter estimate 0g changes when an addi- tional sample z' ~ D is included in the training set S. We can cast this as contamination of the corresponding empirical distribution D,, to yield an altered distribution D = (1 - c)D,, + c 8z', with the contamination amount = a+I Thanks to the influence function of the parameter estimate (Proposition 2 for D = D.). we do not have to retrain and explicitly measure the change in final parameters, but have an analytic expression given follows, IF (z (s, D,) =
H (0s) + XI] Vol(z', 0s)) where the superscript S H denotes the computation of the Hessian on the set S. Now using the chain rule of influence functions, can express the influence
on l. = ((2' 0) as. IF (R= P,) Vol(z',
Os) + AI Tol(2',0s) When
|S] 72 large enough to ignore O(n terms, the (infinitesimal) definition of influence function is equivalent using the finitediifferece form. This allows us to directly express the change in loss which we leverage to derive an expression of the test loss, in Theorem 3 below.
Theorem 3. Consider the parameter estimator Og based on the set of input samples of = n.
Then the population risk ((0s) EE=~D (((z,0)) ) takes the following form,
[(0s)= = [s(0s) + n n+1 Tr ( + AI C2(0s) + O
1
((())
n2
where (ss) = EXIND l ((2)00s(z))) is the expectation of 'one sample training loss' and
CP (0s) EgInD Vol(2',0s) Tol(z',0g) is the (uncentered) covariance of loss gradients.
3

---

Published as a conference paper at ICLR 2022
Remark. Note, the first term in the right-hand side of eq. 1 is not exactly the training loss, but deviates by a negligible quantity related to the expected difference between the loss of a training sample and the average loss on the remaining training set (as discussed in Section A.1.2). When trained sufficiently long so that the loss on individual samples is close to zero (i.e., the interpolation setting), this quantity becomes inconsequential for the purpose of analyzing double descent.
Related work. The more interesting quantity in eq. is the second term on the right, which is reminiscent of the Takeuchi Information Criterion (Takeuchi, 1976; Stone, 1977) and similar term appears in several works on neural networks (Murata et al.. 1994; Thomas et al., 2019) as well as in the analyses of geast-squares regression (Flammarion Bach, 2015; Défossez & Bach, 2015; Pillaud- et al., 2018). However, an important difference is that in our expression the Hessian based on the entire true data distribution
H evaluated on the training set appears, whereas in prior works. This seemingly minor difference is in fact crucial, since studying double descent necessarily involves analyzing the relation between the training set size and the model capacity (such as the number of parameters). Also, directly taking the results from previous works and merely approximating the involved quantities based on the training set, such as the Hessian and the covariance Cº, does not work either. Since in such scenario, when the limit of the regularization strength À - 0, results from prior works reduce to something ineffective for further analysis. E.g., for mean-squared loss, to the rank of Hessian at the optimum (see Section A.2.2 for more details).
4 LOWER BOUND ON THE POPULATION RISK
As a brief outline, our strategy to theoretically illustrate the double descent behaviour will be to show that the lower bound of the population risk diverges around certain threshold. Before pro- ceeding further, we would like to emphasize that so far we have not employed any assumptions on the structural form of the model or the neural network, as well as neither the data distribution.
So let us now introduce some relevant notations to describe the precise setting for our upcoming result. We assume that the samples are tuples (æz, y). where the input E Rd has dimension and the targets y E RRK are of dimension K. Let us consider the neural network function is fa(x) == fxx 0) Rd x Rº + RK where we have taken 0 E Rº. The parameter estimator, 0g. in this context refers to the parameters obtained by training to convergence using the training set S, and which we will henceforth denote by 0" := 0s (to emphasize the fact that we are at the local optimum). Also, the loss function f(z, 0), with slight abuse of notation, refers to L f(f(ar) y) in this setting. Let us additionally define shorthand L ==
Next, let us discuss in more detail the two matrices that appear in Theorem 3, before we introduce the assumptions we require.
First, the Hessian matrix of the loss, can in general be decomposed as of two other matri- ces (Schraudolph, 2002): outer-product Hessian H (0) and functional Hessian H i.e.
( H (0) H)
Vefo(z;)
Vi L Vofo(x.)
V Llle Vola
(z,)
(2) where, Vefe E gxXk is the Jacobian of the function and V3 E R is the Hessian of the loss with respect to the function. Next, the other matrix that appears in eq. I is the (uncen- tered) covariance of loss gradients, () B( ( v) Vol(fo( (z). v) with Vol(fo
fe (x) V vl((f((z),) y) where V,l RK is the gradient of the loss with spect to the function. Similar to the covariance of loss gradients, let us define the covariance func- tion Jacobians, which will denote by C when computed over the samples in set S and which can be expressed as C (0)
[S| Zs Zo)
with Zg- = [Vofo( ... Vofo(z E RS
4.1 LOWER BOUND
We employ the following assumption to obtain an appropriate lower bound of the population risk: Assumption A1. There exists sample (æe, y) D with non-zero probability a such that of
||V { 1)² 0.
Finally, we are in a position to state our main theorem (all the proofs are in Appendix A).
4

---

Published as a conference paper at ICLR 2022
Theorem 4. Under the assumption Al and taking the limit of external regularization X 0 and K = L, we obtain the following lower bound on the population risk (eq. 1) at the minimum 0"
O omain Or Ammin (CB(0))
1
[( (0 n n+1
(3)
Ay (H)))))
where consider the convention X 2 2 A, for the eigenvalues with r rank (0")), (02)( and min denotes the minimum (a.x) = V ( (x)) y) over D, i.e. (x. y) D ((..)) (x)
The key takeaway of this theorem is that the lower bound on the population risk is inversely pro- portional to the minimum non-zero eigenvalue X, of the Hessian the optimum H (0"), which as we will see shortly - largely characterizes the double descent like the behaviour of the popu- lation risk. Besides, we would like to emphasize that the primary purpose of the lower bounds to isolate the source of double descent, and thus the practical applicability of the lower bounds which is in itself an open research area - is of secondary concern. As a result, in our analysis we
lower bound the quantity #=1 A. (H) by Xr (HH(())) although it might be of interest to keep the
1
original quantity in a different context.
Remark. The assumption Al just requires the existence of such point from the true distribution D with non-zero probability. Notice, otherwise, we would have zero population risk, which is obviously of no interest. The benefit of this assumption is that we can analyze (f*) instead of CP (0*) by taking the minimum non-zero min outside of the corresponding expression.
4.2 DOUBLE DESCENT BEHAVIOUR
Having established this lower bound, we will utilize it to demonstrate the existence of the double descent behaviour. Let us consider the case of mean-squared error (MSE) loss, L(fo (z). y) yyy f0 and where the Hessian of the loss with respect to the function is just the identity, i.., VJf I. We will employ the following additional assumptions:
Assumption A2. The functional Hessian at the optimum 0 is zero, i.e, -5
Assumption A3. The minimum non-zero eigenvalue Amin of covariance of function Jacobians at optimum 6² is bounded by the corresponding one initialization 8 over some common set S, i.e., A Amin C)(00))) (00)) S Amin (C$ (0*) )) S B Amin (C)(8))) (8")), with constants A, B <0.
Assumption A4. The columns of (0%) are sub- Gaussian independent random vectors initial- ization 8".
Note on the assumptions. Assumption A2 is known from prior works (Sagun et al., 2017: Singh et al., 2021) to hold empirically in particular, c.f. Figures 5, S2 of Singh et al. (2021) where shown that the rank of the functional Hessian converges to 0 when trained sufficiently (besides, c.f. Appendix C.8). Also, in the setting of double descent, the individual losses (and their gradients) are themselves close to zero near the interpolation threshold, thereby making the functional Hessian vanish at the optimum (recall eq. 2). Next, the assumption A3 essentially guarantees that, at the optimum, the minimum non-zero eigenvalue of the covariance of function gradients does not change much relative to that at initialization. Importantly, this is purely for the purposes of the lower bound constraint during training (vis-à-vis the NTK regime). The
not something that we impose existence of the constants mentioned in this assumption A3 can be theoretically justified by the fact that the map A + (A) is Lipschitz-continuuus on the space of Hermitian matrices, which follows from Weyl's s inequality (Tao, 2012, p. 56). Besides, in Figure 2a, we empirically justify this assumption, and in the adjoining Figure 2b we also validate our lower bound to the population risk throughout the double descent curve (additional details of which can be found in Appendix 1O).
The last assumption may seem more demanding but is mild in comparison to that in prior work (Pen- nington& & Bahri, 2017), where all entries the covariance of function gradients at the optimum are considered to be independent and identically distributed. In contrast, sub- babb-aaussiantty only at initialization. Similar sub- gaussianity assumptions are also common in the regression-based analyses of double descent (Muthukumar et al., 2019; Bartlett al., 2020). The
assumption just requires
5

---

Published as a conference paper at ICLR 2022
benefit of such an assumption is that it allows to precisely characterize the behaviour of the min- imum eigenvalue that appears in Theorem 4 using results from Random Matrix Theory ( (Vershynin, 2010), and thereby that of double descent, as described in the upcoming Theorem 5. Lastly, before proceeding ahead, let us mention that the Appendix A.4 discusses concrete settings where all the above assumptions hold simultaneously for finite-width neural networks.
Theorem 5. For the MSE loss, under the setting of Theorem 4 and the assumptions A2, A3, A4, the population risk takes the following form and diverges almost surely to oo at p = ve n,
min at Amin (C)(0))
((0') 2 [0" +
in the asymptotic regime of p, + do but
B B ( ll (Vū- cv/p²
their ratio is a fixed constant, and where e > 0 is a constant that depends only on the uub-Gaussian norm of columns of (.")
Takeaways. (a) Firstly, the point where the second descent occurs, i.. the interpolation thresh- old, is typically p x n in the setting of K 1. So our result from Theorem 5 (which is in this setting) not only implies a divergence at the interpolation threshold, but further illustrates that the complexity term will get smaller as its denominator increases for p >> n. thereby also capturing the overall trend of population risk. (b) Second, while the above result holds in the asymptotic setting, we empirically show that such behaviour also takes place for p and n as small as a few hundreds or thousands, as discussed in Section 4.3 ahead.
Interpretation of the interpolation threshold location. An interesting empirical observation, very briefly alluded to in prior works (Belkin et al., 2019; Greydanus, 2020), is that for the MSE loss with K targets, the interpolation threshold is instead located at p R Kn. This can be reconciled by looking the rank of the Hessian at the optimum, as inherently the divergence at the interpolation threshold is because the Hessian's minimum non-zero eigenvalue Ay vanishes. More intuitively, double descent occurs at the transition when the Hessian rank starts being dictated by the # of samples (i.e.. when over-paramente ) rather than being governed by the of parameters (i.e., when ander-paramettrizzedee e.g., for MSE when p = Kn and note Kn is precisely the rank of the Hessian in the over-parameterized regime (Kn > p). As matter of fact, in practice, there might be redundancies due to either duplicates or linearly dependent features/samples, as well as parameters. For instance, in Figure 15 we show a simple example of linear regression where the interpolation threshold can be moved arbitrarily by changing the extent of redundancy in the design matrix. But, as demonstrated therein, thinking in terms of the Hessian rank can help avoid such inconsistencies.
Other facets of double descent. (i) Our analysis additionally explains the empirical observation of label noise accentuating the peak (Nakkiran et al., 2019), since the complexity term contains a (ii) The exact term that multiplicative factor of o which increases proportionately with label noise.
appears in our proof, before we take the limit of regularization À - 0. is (A,, { )) +A) This reveals why, when using a regularization of suitable magnitude, double descent is not prominent or disappears, as also noted in (Nakkiran et al., 2019; 2020).- since this term can no longer explode.
4.3 EMPIRICAL VERIFICATION
2.5
200
345
3
3.5
2.0
41
12
365
1010
(a) L 2, n2 500, K 10
(b) L
3, 12 200, K
10
Figure 1: MSE Loss: Behaviour of the population (test) loss and minimum non-zero eigenvalues for the setting of L 2 and L = 3 layer networks on downscaled MNIST (Greydanus, 2020). The results are averaged over 5 seeds and the shaded interval denotes the mean + std. deviation region.

---

Published as a conference paper at ICLR 2022
To empirically demonstrate the validity of our theoretical results, carry out the entire proce- dure of obtaining double descent for neural networks. Namely, this involves training a large set of neural networks with layer widths sampled in regular intervals - for sufficiently many num- ber of epochs. However, in our case, there is another factor which makes this whole process even more arduous- the lower bound depends As a result, we cannot resort to efficient Hessian approximations based on, say. Hessian-vector products (Pearlmutter, 1994), but rather we need compute entire Hessian spectrum which has O(p²) computational and memory costs. Hence, we cannot but restrict our empirical investigation to smaller network sizes. Nevertheless, on the positive side we can thoroughly assure the accuracy of our empirical investigations - since we compute the exact Hessian and its spectrum, and that too in FL.AT664 precision.
the minimum non-zero eigenvalue of the Hessian.
In terms of the dataset, we primarily utilize MNISTID (Greydanus, 2020), which is downscaled version of MNIST yet designed be significantly harder than the usual version. However, we also CIFARIO and the usual (easier) MNIST, which alongside other empirical details,
present results can be found in Appendix C. Figure I shows the results of running the double descent experiments for the settings of two and three layer conneced networks with ReLU activation trained for 5K epochs via SGD. Alongside the population loss (empirically measured on a test set) - which peaks the interpolation threshold of p Kn
plot the trend of the minimum non-zero eigenvalue. As predicted by our theory, this eigenvalue indeed tends to zero (note the log scale), in both the settings, around the precise neighborhood where the population loss takes its maximum value.
(a) Minimum non-zero eigenvalue stays close.
(b) Lower bound captures the trend of population loss.
Fi Figure 2: Empirical validity of assumption A3 & the lower bound of Theorem 4 in Double Descent.
THE CASE OF CROSS-ENTROPY
Greydanus (2020) notes that in the of cross-entropy, the population loss peaks at (unlike at xe Kn for the MSE loss). To better understand this aspect, let us start by checking the form of the Hessian the optimum for the cross-entropy loss, which by our assumption A2, will be given by the outer-product term. as in eq. 2. Now, the main difference is that the Hessian of the loss with respect to the function (named 'output-Hessian') )) instead of being identity like in MSE, is given by Vi (z), y) diag(p) - -pp" where p = softmax Se (x)) denotes the predicted class- probabilities obtained from applying the softmax operation. In general, this output-Hessian Hessian matrix of size K x K, is rank-deficient with rank K - 1. Thus, the Fank(H,, (0) min (p, (K - 1))n) for any 0, and the initial surmise would be that the interpolation threshold is at p Ro (K 1) n.
But, this is not in line with the stated observation from Greydanus (2020). Hence, let take another closer look at the Hessian, and in particular, V2P.. Notice that near interpolation, when the loss on individual training samples tends to zero, the predicated class class- probability p will tend to 1 for the correct class (as per the training label) and 0 elsewhere. This suggests that Hessian matrix collapses to O since F (ar), y) = diag(p) pp" - O. And indeed, this is true based on our empirical results, displayed in Figure 3 given the network is trained sufficiently long. We clearly observe that the population loss diverges at p Rs n, however the test error, although not conspicuous, still shows a slight peak (similar to the curves in (Nakkiran et al., 2019) without label-noise). Next, from the right sub- figure (plotted in log-scale), it also becomes evident that the entire Hessian spectrum from the maximum to the minimum eigenvalue - collapses to zero near the interpolation threshold.
Fact 6. Thus, we have that for the cross- entropy loss, near the interpolation threshold of p = n, the entire Hessian matrix vanishes at the optimum, ie., H 0.
7

---

Published as a conference paper at ICLR 2022
240
3008
+oforrmmrrrs
Figure 3: (Left) Double descent curve for CE loss and (right) log-scale plots of the test and train loss, alongside Hessian eigenvalues, for a one-hidden layer neural network trained for 40K epochs.
Importantly, the above fact (and our empirical results) report such behaviour only around p n, and not well into the pvermmaraeteiize regime >> n. Therefore, a straightforward consequence of the above fact and empirical observations is that X, (0")))) 0 near this interpolation thresh- old, implying that the population loss in case of cross-entropy loss diverges at p Rz n..
Figure 3 right, seems suggest, rather surprisingly, that even the training loss has the same trend as these Hessian eigenvalue statistics. Note, this is not the case that networks were not trained long enough rather, We run them for 40, 000 epochs. In fact, we even trained models, right to the interpolation threshold, up to 80, 000 epochs. Yet, the training loss only drops by factor of 2 and is still le 5, compared to exact 0 at machine precision in half the epochs for networks lying in the region where the test loss diverges. This leads us to posit the following hypothesis: around p se n, SGD finds critical points with zero Hessian for neural networks trained with CE loss and over over-parameterizunn parmmttrrzzaioon beyond the interpolation threshold helps completely avoid or significantly decelerate convergence to such critical points. Further investigation into this hypothesis is beyond the current scope, but forms exciting direction for future work.
Vanishing Hessian hypothesis.
6 LEAVE-ONE-OUT ESTIMATE VIA INFLUENCE FUNCTIONS
Leave-one-out (LOO) is also known to provide reasonable estimate of the population loss (Pontil, 2002). The principle behind it is to leave behind one sample, optimize the model from scratch on the remaining 1 samples, then evaluate the loss the left-out sample, and finally average over the choice of the left-out sample. In our setting for double descent, we prefer the add-one-in procedure since it directly gives the population loss itself. However, LOO can still be useful from practical perspective as it relies only on the training set - assuming we can analytically estimate it via some closed-form expression which avoids the need to train n models in the otherwise naive manner.
Similar to the add-one-in procedure from before, lcave-one-out can be cast as a slight contamination of the distribution. We can express the new distribution D)"", with the i-th sample removed as follows, D (1 <)Dn + e edz; with = -1 .-I- where Dn refers to the original empirical distribution over the training set. Now, we can carry out similar steps like for add-one-in, and derive the change the parameter estimate as well as the change in loss over the left-out sample. But, here we additionally analyze the effect of incorporating the second-order influence function, apart from the usual first-order influences. This provides with estimates LOO(1) and (0)(2), the expressions of which can be found in Appendix 1. As a quick test-bed, we investigate the fidelity of these two approaches relative to the exact formula LOO in the case of least-squares.
Theorem 7. Consider the particular case of the ordinary-least squares (OLS) with the training inputs gathered into the data matrix X E gaad and the targets collected in the vector y E R.. Under the assumption that the number of samples n is large enough, we have that L0O
0 Tr;
An
LOO
and (OO +
y, 0 xz)
where, Ai
1-AR
A
2 [ X) x; denotes the i-th diagonal entry of the matrix A = X X
(i.e., the
so-called 'hat-matrix') and 0 denotes the usual solution of (X] x) "XT y obtained via OLS.
8

---

Published as a conference paper at ICLR 2022
This result is reassuring as it shows that LOO expressions from influence function analysis are accu- rate, and we recover the least-squares formula
formull as a special case through 1.0 Further,
Corollary 8. For any finite-width neural network, the first and second-order inftu- ence function give similar formulas for LOO like that in Theorem 7, but with A "s(00)T
Zs(0")) where Zs(0") (Vo (oo.o. (xw)] and 0* are the parameters at convergence for MSE loss.
Finally, the above result raises concern about the sub-optimality of first-order influence functions when used in the leave-one-out framework. While this is not necessarily significant concern for a theoretical analysis, say that of double descent, this can be relevant from a practical viewpoint (Basu et al., 2020). However, an empirical investigation on this front remains beyond the current scope.
7 DISCUSSION
Summary. We derived an expression of the population risk via influence functions and obtained lower bound to it with fairly minimal assumptions that applies to any finite-width neu- ral network trained with commonly used loss functions. The lower bound is inversely related to the smallest non-zero eigenvalue of the Hessian of the loss the optimum. When specialized the MSE loss, this provably exhibits a double descent behaviour in the asymptotic regime and we empir- ically demonstrated that this holds even in much smaller non-asymptotic settings. We also analyzed the intriguing phenomenology of double descent across other losses - through our deessaan-base framework which explained existing empirical observations as well uncovered novel aspects of neural networks near interpolation. Finally, as by-product, we presented theoretical results for leave-one-out estimation using influence functions the case of neural networks.
Related theoretical work on Double Descent. We carve out niche in the growing set of studies -fnite- finite-width neural networks. For the linear/kernel regression setting (or lately, the nearly equivalent two-layer network with frozen hidden-layer), there a plethora of existing work (Advani et al., 2020; Bartlett et al., 2020; Mei & Montanari. 2019; Muthukumar et al., 2019; Geiger et al., 2020; Ba et al., 2020), that analyzes double descent. Thus, our aim is not to make these existing analyses tighter, but rather to take a step towards developing analyses that directly hold for finite-width neural networks. Therefore, unlike the above works, we do not impose any restrictive assumptions on the structure of neural network, like two-layer networks, the optimization methods used train them, like gradient flow. Yet, our work also bears a natural connection between the matrix whose spectrum comes to be of concern in the prior works the input-covariance or kernel matrix in linear or kernel regression outer-product Hessian in our work for MSE loss (which has the same spectrum as the 'empirical' NTK). But our strategy also makes our work applicable to cross-entropy, e.g., where we bring to light the interesting observations near the interpolation threshold.
on double descent by focusing primarily on -
while that of the
closely related recent work, Kuzborskij et al. (2021), links the population risk for least-squares to the minimum non-zero eigenvalue of the input covariance matrix - but although via upper- bound, which is insufficient for illustrating double descent. Nevertheless, analogy to their regres- sion result, they study the minimum eigenvalue of the covariance matrix consisting of penultimate- layer features and conjecture this as a possible extension to neural networks. However, the input- covariance matrix in least-squares is also the Hessian, and as we have thoroughly established the Hessian (at the optimum) is indeed the relevant object- - thus contradicting their conjecture.
Limitations and directions for future work. There are many important aspects surrounding double descent that remain unanswered, in the context of neural networks: (a) Analogous to (Hastie al., 2019) for linear regression, what the conditions for the global optimum lie in the over- parameterized regime instead of under- under-paramett patarr--aaaamteeddd... (b) Given the vanishing Hessian hypothesis, there a qualification to the regime where the flat-minima generalizes better hypothesis (Hochreiter & Schmidhuber, 1997; Keskar et al., 2016) holds - since the Hessian is the flattest possible here. (d) On the technical side: better characterization of the mentioned cross-entropy phenomenon as well as non-asymptotic results. Overall, we hope that our work will encourage foray into further studies of double descent, that are specifically built for finite-widh neural networks.

---

Published as a conference paper at ICLR 2022
REPRODUCIBILITY STATEMENT
All the omitted proofs to the theoretical results can be found the Appendix A.
In regards to empirical results, we provide all the relevant details and additional results in the Appendix C.
The corresponding code for the experiments is located at https//gthua..om//dddddbbbbbb descent.
ACKNOWLEDGEMENTS
We would like to thank Simon Buchholz for proofreading an early draft the paper. Besides, we thank the members of DA lab for useful comments. Sidak Pal Singh would also like acknowledge the financial support from Max Planck ETH Center for Learning Systems and the travel support from ELISE (GA no 951847).
REFERENCES
Madhu S Advani, Andrew M Saxe, and Haim Sompolinsky, High-dimensional dynamics of gener- alization enror in neural networks. Neural Networks, 132:428 446, 2020.
Jimmy Ba, Murat Erdogdu, Taiji Suzuki, Denny Wu, and Tianzong Zhang. Generalization of two- layer neural networks: An asymptotic viewpoint. In International Conference on Learning Rep- resentations, 2020. URL https: /ttp////ppeeeeeeeeeeee/eeeeeeeee net How.mmidd-..gssgeee...
Peter L Bartlett, Philip M Long, Gábor Lugosi, and Alexander Tsigler. Benign overfitting in linear regression. Proceedings of the National Academy of Sciences, 117(48):300033330770 2020.
Samyadeep Basu, Philip Pope, and Soheil Feizi. Influence functions in deep learning are fragile, 2020.
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-
learning practice and the classical biri-vari trade-off. Proceedings of the National Academy of Sciences, 116(32) 15854, 2019. ISSN 0027-8424. doi: 10.1073/pnas. 29.1073/pnas.1903070166 wttg///onee//11/////1111
190307011
URL httph::t////. wwww
Michiel Debruyne, Mia Hubert, and Johan A.K. Suykens. Model selection in kernel based regression using the influence function, Journal of Machine Learning Research, 9778:2337-2200,, 2008
URL http::tt:///tt oorgg...rrroo.ooooooo..ooo http://tttgppprrr//////////m hppppppp///s/ debruynee@@e html.
Alexandre Défossez and Francis Bach. Averaged least-mean-squares:
Bias-variance trade-offs and optimal sampling distributions. In Artificial Intelligence and Statistics, pp. 205-213. PMLR, 2015.
Simon Du, Jason Lee, Haochuan Li, Liwei Wang, and Xiyu Zhai. Gradient descent finds global minima of deep neural networks. In International Conference on Machine Learning, pp. 1675- 1685. PMLR, 2019.
Bradley Efron and Charles Stein. The jackknife estimate of variance. The Annals of Statistics, pp- 586-596, 1981.
Yuguang Fang, Kenneth A Loparo, and Xiangbo Feng. Inequalities for the trace of matrix product. IEEE Transactions on Automatic Control, (9(12)2248-22490 1994.
Nicolas Flammarion and Francis Bach. From averaging to acceleration, there is only a step-size, 2015.
Mario Geiger, Arthur Jacot, Stefano Spigler, Franck Gabriel, Levent Sagun, Stéphane A'scolli, Giulio Biroli, Clément Hongler, and Matthieu Wyart. Scaling description of generalization with number parameters deep learning. Journal of Statistical Mechanics: Theory and Experiment, 2020(2):033001, 2020.
10

---

Published as a conference paper at ICLR 2022
Sam Greydanus. Scaling down deep learning, 2020.
Frank R Hampel, Elvezio Ronchetti, Peter J Rousseeuw, and Werner A Stahel. Robust statistics: the approach based influence finctiins, volume 196. John Wiley & Sons, 1986.
Markus Harva and Ata Kabán. Variational learning for rectified factor analysis. Signal Processing, 87(3):509-52)) 2007.
Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan Tibshirani. Surprises in high- dimensional ridgeless least squares interpolation. arXiv preprint arXiv:1903.08560 2019.
Sepp Hochreiter and Jürgen Schmidhuber. Flat minima. Neural computation, 9(1):1-42, 1997.
Roger A. Horn and Charles R. Johnson. Topics in Matrix Analysis. Cambridge University Press, 1991. doi: 10.1077CB0098001144077
Peter Huber. Robust statistics, volume 523. John Wiley & Sons, 2004.
Arthur Jacot, Franck Gabriel, and Clément Hongler. Neural tangent kernel: Convergence and gen- eralization in neural networks, 2018.
Nitish Shirish Keskar, Dheevatsa Mudigere, Jorge Nocedal, Mikhail Smelyanskiy, and Ping Tak Pe- Tang. On large-batch training for deep learning: Generalization gap and sharp minima. arXiv preprint arXiv: 1.XX::6609904866, 2016.
Pang Wei Koh and Percy Liang. Understanding black-box predictions via influence functions, 2017.
Rannen-Triki, Iija Kuzborskij, Csaba Szepesvári, Omar Rivasplata, Amal Rannen- Triki, and Razvan Pas- canu. On the role of optimization in double descent: A least squares study. arXiv preprint 1rXiv:2107.12665, 2021.
Marco Loog, Tom Viering, Alexander Mey, Jesse H. Krijthe, and David J. Tax. A brief prehistory of double descent. Proceedings of the National Academy of Sciences, 107(20):10625-1066) May 2020. ISSN 1091-6490. doi: 1..073//paa.2001875111 URL http: //tp:///xxxooooooo doi org/10. 1073/pnas 2 200000010111111
Song Mei and Andrea Montanari. The generalization enror of random features regression: Precise asymptotics and the double descent curve. Communications on Pure and Applied Mathematics, 2019.
N. Murata, S. Yoshizawa, and S. Amari. Network information triteion-decermmniig the number of hidden units for artificial neural network model. IEEE Transactions Neural Networks, 5(6): 865-872, 1994. doi: 10.1109/72.329683.
Vidya Muthukumar, Kailas Vodrahalli, and Anant Sahai. Harmless interpolation of noisy data in regression. 2019 IEEE International Symposium on Information Theory (ISIT), Jul 2019. doi: 10. 1109/isit2011.888444 8889919, URL http: / dx. doi. wwg/10.............o......... 11w..111111... III..SIITIII.. 2019. 8.199.888499 8849614
Preetum Nakkiran. More data can hurt for linear regression: Sample-wise double descent. arXiv preprint
2019.
Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt, 2019.
Preetum Nakkiran, Prayaag Venkat, Sham Kakade, and Tengyu Ma. Optimal regularization can mitigate double descent, 2020.
Quynh Nguyen, Marco Mondelli, and Guido F Montufar. Tight bounds the smallest eigenvalue of the neural tangent kernel for deep relu networks. In International Conference on Machine Learning. pp. 8119-8129. PMLR. 2021.
Barak A Pearlmutter. Fast exact multiplication by the hessian. Neural computation, 6(1):147-160, 1994.
11

---

Published as a conference paper at ICLR 2022
Jeffrey Pennington and Yasaman Bahri. Geometry of neural network loss surfaces via random matrix theory. In International Conference on Machine Learning, pp. 2798 21982798-200 PMLR, 2017.
Loucas Pillaud-Vivien Alessandro Rudi, and Francis Bach. Exponential convergence of testing error for stochastic gradient methods. In Conference on Learning Theory, pp. 250-296. PMLR, 2018.
Massimiliano Pontil. Leave-one-out error and stability of learning algorithms with applications. International Journal of Systems Science, 2002.
Levent Sagun, Leon Bottou, and Yann LeCun. Eigenvalues the hessian in deep learning: Singu- larity and beyond, 2017.
Nicol N. Schraudolph. Fast curvature matrix-vector products for second-order gradient descent. Neural Computation, 14:1723-1738, 2002.
S. P. Singh, G. Bachmann, and T. Hofmann. Analytic insights into structure and rank of neural net- work hessian maps. In Advances Neurul Information Processing Systems (NeurIPS 2021), December 2021.
Mervyn Stone. An asymptotic equivalence of choice of model by cross valisvaali and akaike's criterion. Journal of the Royal Statistical Society: Series B (Methodological), 99(1):44-47, 1977.
Kei Takeuchi. The distribution of information statistics and the criterion of goodness of fit of models. Mathematical Science, 153:12-18, 1976.
Terence Tao. Topics random matrix theory, volume 132. American Mathematical Soc., 2012.
Valentin Thomas, Fabian Pedregosa, Bart van Merriënboer, Pierre-Antoine Mangazol, Yoshua Bengio, and Nicolas Le Roux. Information matrices and generalization. arXiv preprint arXiv:1906.07774. 2019.
Roman Vershynin. Introduction to the non-asymptotic analysis of random matrices. arXiv preprint arXiv:1011.3027, 2010.
12

---

Published as a conference paper at ICLR 2022
A OMITTED PROOFS
Proposition 2. The influence function IF of the M-estimator OD based the distribution D, evalu- ated at point z, takes the following form:
--(Ho(OD) --
Vol(z,0p),
(4)
Vi C(O)) is the matrix of second-derivatives of the loss [(0) = E [2(2,0) 0)] with respect to the parameters 0.
where, the Hessian matrix Hz(0p)
z~D
Proof. Let OD arg mingae
E
[((=,)) Instead of this formulation, we can also define the
x~D
estimator one that satisfies the following implicit equation (assuming the derivative can be moved inside expectation).
[ol(2,0) m~
E
=
(5)
which is nothing but the first-order stationary point condition. Now, consider a contaminated distri- bution D (1 +)D + dg. The corresponding implicit equation, to be satisfied by the estimator corresponding D, can be written as follows:
E Vol(z,0) =0
(6)
(1-c) E Vol(z,0) Vo = znD
Take the derivative of the above expression with respect to (plus interchanging derivative and expectation), get:
d
de (1 -
Vol(2,0)
[Vol((20)
ZND
de
d0
E Vol(z,0) TDD
+1 (1- c) ZDD
Vi (z
vol(z.0) - -V -
(7)
de
de
Since, 0r satisfies the above eq. 7, let us substitute place of and analyze the case for c - 0.
We are left with the following (after removing terms multiplied with c):
db
E [ol(2,0))) z>D
+ zND
(g
-Vl((2,00)
(8)
Now, the first term goes to zero - O, because eq. 6 holds for 0 5, shown below
E vol(2,0g)) = E. z>D
Vol(2,05)) + E (ol(2,00))) IND
zND
Vol 0
IND
Further, as 6 one can replace o by 0D in the expressions of the gradient and Hessian of L. Then, assuming that the Hessian Hc(Op) = vă NDD this yields:
[[(z,0)] DND Vzl(2.00) invertible,
IF(2;0,, D) [)(())) Vol(2,0n)
13

---

Published as a conference paper at ICLR 2022
A.1 EXPRESSION OF THE POPULATION RISK
Theorem 3. Consider the parameter estimator 0g based on the set of input samples S of n.
Then the population risk L(Os) = EEED (((,0s)) takes the following form,
((,s)= = (0s) + n+1 71 (HE(s) + AT cB + +0
(10)
n2
where Es(Os) = BIIND [e ( (sutes)))) denotes the expectation of 'one-sample training loss'
and (gs)) = BR'ND Vol(=' Vol(z', is the (uncentered) covariance of loss gradi-
ents.
Proof.
Let us recall the expression of influence function for the loss on the new sample x',
IF (ss D,)) - H 0ss) + + Vol(='.0s)
(11)
When |S| n is large enough to ignore O(n 2) terms, the (infinitesimal) definition of influence function is equivalent to using the finite mnite-differenc form. Then the change in loss can be expressed as,
A( ((z',0)((>)) - -(E',0s) n+ Vol(z',0s) T (H)))) + ^I] Vol(z',0s)
(12)
where we have multiplied both sides by De e I expression of the test loss follows. Starting from eq. 12, average out over the choice of an additional sample z' ~ D:
We leverage this relation derive an
E x' x'
e(> ((22) [SS
E.
((2
=
x'ND
E Z'rD
Vol(z'.0s) 0s)
02) + A1 Vol(z',0s) 0s)
(n 1)
Using properties of the trace and moving expectation inside, we get
[((2 (()=
E e(2' 0 [s)(=)))
1 Tr (HA + +AI C²0s)) (13)
E
+ n+1
>'
D'ND
where, ()( ERIND [ vol(z',0)
Now the term on the left-hand side nothing but the population risk L(0s) = BE-D [(2,, 0z) )
and we coin the first term the right-hand side the expectation of 'one-sample training loss".
A.1.1 REMARKS THE FIRST-ORDER INFLUENCE FUNCTION USAGE
Let us better understand when using the first-order influence function suffices by analyzing the respective expression for the change in loss. First, let us apply the influence function of the parameter estimator from eq. 9,
(='' = 0s) -H +
XI
Vol(=',0s) Vol(2'
(14)
for the add-one-in case of sample z' to the training set S discussed above. Next, we can substitute n-1 and thereby obtain the change in parameters ~0 as:
A0
1
H
(0s)
A1 Vol(z'00))
(15)
m+1
n
14

---

Published as a conference paper at ICLR 2022
Then, via first-order influences, get the change in loss over the sample z' as:
(2)) Vol(z'.0s) Ad
Tr | OH) +
Vol(=', T
ni n
(16)
In contrast for the second-order influence, we obtain the change loss over the sample z' as:
(2)) Vol(z',00 Ab -e T 1
vjl(z', Ae
(17)
n n+1 [ AI
Vol(z' v
Tr H ( + II
Vil(z' 0s) (s) + Vol(z' Voll2::bsVVo((2'03)
2(n + 1)2
Later on, we take the expectation over the distribution, i.e., z' ~ D. but it is not relevant for ana- lyzing the scale of the above mentioned change loss obtained via first or second order influences. Note, the Hessian is itself (1)) in terms of number of samples n. it is average of the per- sample Hessians. Also, the numerator in both the above equations is a trace of a p x p matrix and, overall, the numerator scales (p)). Whereas, if we look the denominator, the extra term in ( scales Onn while the common term in (? and ( is of O(n Hence, when large enough such that n² >> p. then the On -) terms can be ignored, we can simply consider the first-order influences.
A.1.2 INTERPRETATION OF THE 'ONE-SAMPLE TRAINING LOSS'
First, note that the first term on the RHS of eq. 13 is not exactly the training loss but rather some related quantity. To see this better, let us rewrite as follows:
[(2' (ss(x)s)] #'ND
E
[S] e(z' ((z(O))U()))) E(S, ((S,
E x'-D
0(5,0
x/ND
|S|
ATR(3(SUU(=1)
L(z,, 0) is the sum of the loss over the samples in S. Further, the expression ATR(2', S (2')) refers the deviation between the loss of a training sample (here, x') relative to the average loss on rest of the training samples. The 'TR' in this symbol refers to this deviation being computed on the given training set.
where, E(S,0) = >1
E D
1(2', ((x')))U())))]
|ATR(2 (x)1I+ Z'ND
E
1 [S|
((S, e(S, Su(Z)))
I' |ATR(* .SU (z'Il
|S| ((S (2') (z'),0 -(2',) =(Et,
H'DD
Notice, the last term in the expression above is the same as the term on the left hand side - albeit with an additional scaling factor of [ST and negative sign in front Rearranging this results in the following equation:
|S| +1 S
(122,0sute)))
-E [ATR(2', x'DD
SSU (UU'UUUU2' (2'))]
x'DD
|S|
+1
|SU e(S (2') 0 Sstter))
1
S
x'D
The only extra thing we have done to multiply and divide by JSU (x') = |S| + the last term in the right hand side. Notice the rightmost term is expectation (over z') of the average training
15

---

Published as a conference paper at ICLR 2022
loss of the training set S U {2'} and to which assign the shorthand TR(S U {2'})- Also, it is evident from here that the 'one-sample training loss' a quantity very much related to the training loss. Lastly, considering the large [S] n limit, we have - nt1 1. and which thereby yields:
[0ss)= = E z'
e(xz (s(
E Z'-D
E [ U {z1)) R'-D
A.2 LOWER BOUND THE POPULATION RISK
Lemma 9. Consider two matrices A E m and B E Rmxm where A is symmetric and B is symmetric and positive semi-definite. Then the following holds,
Amin A)T(B) S Tr(AB) s >mor (A)Tr(B
Proof. See Fang et al. (1994).
Theorem 4. Under the assumption Al and taking the limit of external regularization À - 0 and K 1, we obtain the following lower bound on the population risk eq. 1), at the minimum l
o min Ammin (CB
((0)) 2 (s(
1
(18)
n n+1
A (0))
where we consider the convention A1 2 ... 2 for the eigenvalues with == rank and mi denotes the minimum (,.))) V ff(fo-(x)) y)11 over D, i.e. (x, y) D ) 0.
Proof. Let us recall the expression for the population risk that we proved in Theorem for 0 0"
0 00011
C(0") = [s(0r) + n n+1 Tr (H) II CP())
(19)
n2
In particular, we would like to analyze the complexity term T = Tr (H) + AI
cg (0
on the right-hand side and lower bound it. The full expression of this term is given by,
E (=
Vol(Jo-
(0)) + XI] (o((
(20)
Now using the chain rule, we have that Vol(foo (x). = Vefe (x) v vel(fo (2)) (x). Then, for K 1, the above equation is equivalent
T
vofo-(a))
(H) + AI] VoJo
| VV (1))
(21)
(m.D)
(=.w)
B B(
Next, we take the lower bound by considering the minimum over all non-zero o( |[V [ (z).
T o E ( (a.1)~
D
min a Tr (H + AI
c (0*)
(22)
where mmin min Be.y)-DDoor ? 00 (m. and whose non-zero probability a is guaranteed by the as-
sumption Al. Finally, in the last line, we use the cyclic property of the trace once again and move the expectation inside the trace, obtaining the covariance of function gradients cp (0*).
16

---

Published as a conference paper at ICLR 2022
Proceeding further, again make use of Lemma 9 in the eq. 22, since these matrices are also symmetric positive semi-definite. This yields,
T 2 om mia
C (0)
(0)(0))+ +1I]
(23)
Amin (C)
Σ
(24)
da (H)) +1
(25)
where, the notation >-(-) denotes the i-th eigenvalue of the corresponding matrix and we will use the convention that for some matrix in Rmxm.
Am
Let us suppose denotes the rank of the Hessian at the optimum, i.e., := rank Since the Hessian positive semi-definite by the second-order necessary conditions of local minima, all the eigenvalues are non-negative and we can further lower bound the previous expression to 7 as follows:
T 2 minn Amin
(cP(8))
Σ 1=1
(O") +
2 min a Amin (cP(8))
Ar (H) +
where the second line, we have used the fact that a sum of non-negative numbers can be lower bounded by the maximum summand. The maximum here will correspond to using the inverse of the minimum non zero eigenvalue Ap-
Now, substituting the following lower bound together with expression of population risk and taking the limit -> 0, finishes the proof.
min Amin (CP(0))
1 A H (0'))
((0") (0')
(26)
n
Note. For the purposes of this lower bound, we ignored the ( part in Theorem This because they take the form, e.g. for second-order influences shown in Section A. and A.I.I.
17

---

Published as a conference paper at ICLR 2022
A.2.1 ANALOGOUS UPPER BOUND
We can in fact derive an upper bound to the population risk by following analogous steps to that in the lower bound. First, let us recall the expression of the complexity term T,
E
Vol(So- ( (0* + XI VVL((o
(27)
The existence of a non-zero residual via the min assumption Al also implies that there exists an analogous T defined as follows:
max
max
(m.
(w.y)
Thus, we get the following upper bound by also considering the chain rule of Vol(Jo-(x),,) Vofe. (x) (f((fo(())) y) and repeating similar steps as before,
T s o Tr (( AI] cF()))
(28)
Then we can use Lemma 9 as both the matrices inside trace are symmetric positive semi semi-defnite, which gives us our initial upper bound:
T of
(H) + XI] ")) Amax (c)(0))
(29)
While additional steps be further carried out, depending the required context, but the objective of this discussion is to show that many of the steps in our lower bound can be likewise generalized get corresponding upper bound.
A.2.2 EMPTRICAL APPROXIMATIONS OF TIC LIKE EXPRESSIONS
Consider the case when both the Hessian and covariance in the complexity term that shows up in our lower-bound expression,
Tr (1) + AI] ))))
are based/aprroximated on the training set.
Let us further assume the case of MSE loss and that are at the optimum, where by A2, ( (0*). Under these set of assumptions, the term above reduces to,
Tr ((C)(00) -
Since we can always express a positive semi-definite matrix as some ZZ Let us substitute this in the above expression and consider the limit of regularization X 0.
lim Tr (ZZZT x
AI) 'z Tr Tz
(30)
where in the last line we have used the result from Tikhonov regularization, and Zt denotes the pseudo-inverse of But this expression nothing but the rank(Z) and thus shows the ineffective- ness of such analysis where both the Hessian and the covariance of function gradients are based on training set.
18

---

Published as a conference paper at ICLR 2022
A.3 DOUBLE DESCENT BEHAVIOUR
Theorem S. For the MSE loss, under the setting of Theorem 4 and the assumptions A2, A3, A4, the population risk takes the following form and diverges almost surely oo p Jeh.
min A Ammin (C)(0")
B ( ll2 (VT - c/P) in the asymptotic regime of p. n + oc but their ratio a fixed constant, and where e a constant that depends only the sab-Gaussian norm of columns of Zs(
C( [s)
Proof. Let start from the lower bound shown in Theorem 4.
Pmin a Amin (CP(0))
1
C((') Es(0') +
(31)
n #1 dy (H)
For the MSE loss, we have the Hessian H (0) = (0)), from assumption A2. We then use the assumption A3 to bound the minimum non-zero eigenvalue (here, A,)) of C (0*) to the correspond- ing minimum non-zero eigenvalue at initialization. This results in the following lower bound,
o Aminn (C}(0))
1 n +1
C(0') 2 Es()')
+
(32)
B Ar CC
Again utilize the assumption A3 upper bound the minimum non-zero eigenvalue of Cj (0*) to the corresponding minimum non-zero eigenvalue at initialization, thus obtaining:
min a Aminn (ck (0)(
[((') 2 (0") +
(33)
n+1
B Ar (C
Now notice that, via assumption A4, (O = [ST ZsZg is covariance matrix with the columns of Zs containing independent, sub-gaussian random vectors in I..
Thus, can leverage the results of Vershynin (2010) the extremal eigenvalues of covariance matrices. Specifically, given a random matrix, Z E R whose columns are isotropic, indepen- dent, sub-gaussian random vectors RT Vershynin (2010) states that the extremal eigenvalues of 1 ZZ' in the asymptotic regime where m, + co but their ratio + E (0, 1]. we have:
2
Amin
1 --zz T
)
(1-
m and
Amax
1
ZZ
T
+
1
c
m
a.s.,
(34)
where a constant that depends on the subgaussian norm.
Since the above result holds in the isotropic case, let us first ensure this aspect. Consider the ma- trix 2s cF(00)) (0") - which is possible since CF (00) is clearly positive semi-definite and its spectrum being bounded away from zero is a typical assumption, c.f. Du et al. (2019); Nguyen et al. (2021). As result, the columns of this new matrix Zş are isotropic, besides being independent, subgaussian random vectors. Thus, apply the above RMT result to the matrix 1 ZsZ5. and
then obtain the following relation on X, (C)(0)):
Xr (C)(0)) < C (0)) (1-a/")
P
2
(35)
This because, Smin (AB) < ||A||2 Smin (B). where s denotes the singular value, and follows from using the definition of spectral norm together with min-max characterization of singular values
19

---

Published as a conference paper at ICLR 2022
(see Theorem 3.3.16 in Horn & Johnson (1991) for more). Also, we know that (M M) (MM)) = =s for some matrix M E Rm*x and for S S min(m, n). Therefore, using
this for A = Cj (0") & and B = c (0") Zs gives the above bound.
Finally, combining all these together yields,
o at A Amin (CF(0"))
1
C(0") [s(0))
(36)
B BI (10))(00)le (1 - c/
Then, by a simple rearrangement and noting that we are in the asymptotic regime where n + oc, recover our desired lower bound, thus finishing the proof.
In the wer-parameterized case, where y > 1, the similar procedure follows by using the random matrix theory result [S] 2 Zg and the fact that in our lower bound we anyways have minimum non-zero eigenvalue Ar-
Remark 1.
Remark The ratio of the terms ||C] (0") l|2 and Amin (c} (C9) looks like condition number,
but notice the the minimum eigenvalue is for the covariance over 7) and not D. Thus, if we are to write in the form of condition number, the above result will take the form:
2 a Amin (CP(0%) /demin (C7(0")
((0)) 2 (0 + m+
(37)
B Cx( (1-OVH)
A.4 ONE-HIDDEN LAYER NEURAL NETWORK WITH TRAINED OUTPUT WEIGHTS
In this section, discuss the concrete case of one-hidden layer neural network, but where only the output layer weights v are trained (akin to a random feature model). Also, for simplicity we assume that the input Rd is sampled from sub-Gaussian distribution (i.e. distribution with tail decay).
Linear case. Let us begin with the case linear neural network, and then we can write the network function follows,
fe(z) = WWa Wa
W @ mad
Notice, since 0f de: [W the second-derivatives trivially for parameter configurations.
8 Bu:
0, Vi. Thus, Assumption A2 holds
Next, note that the columns of Zg, consisting of the vectors Vefo(z) 0f(w) are sub- Gauusassiinn
random vectors when conditioned the initialization weights W, thus satisfying assumption A4.
Lastly, since the trainable parameters are only v and the matrix W remains fixed, then the covariance of network Jacobians remains fixed as well during training, i.e., C5 = [s| Zs(0") ( (e")) =
[S] Zs 00 (0*) (0*). Hence, assumption A3 holds trivially with equality and both con- stants equal to 1.
Non-linear case. Now, consider the general case where we have an elementwise non- non-linearity ø. So, the network function can be expressed as:
(x)) T ((W). W Wedd
The functional Hessian is still zero, the gradient of function with respect the parameters does not depend on the parameters. Similarly, the covariance of network Jacobian will remain the same during training, as the matrix W is fixed. Thus both assumptions A2, A3 hold. The subgaussian
20

---

Published as a conference paper at ICLR 2022
assumption holds well for wide set of activation functions, including for instance the ReLU non- linearity, ((z)= = max(0, 2). Indeed, each component the columns of Z is still independent and random. The difference relative to the linear case is that squash to zero the part of the distribution which is in the second quadrant, which gives a sub-Gaussian distribution as its tail is dominated by Gaussian. We note that if assume the input to be Gaussian, then we get the well-known rectified Gaussian distribution (Harva & Kabán, 2007), which is itself sub-Gaussian.
In summary, these two examples illustrate concrete scenarios of width neural networks where all the assumptions are clearly satisfied simultaneously.
A.5 LEAVE-ONE-OUT DERIVATION
Influence calculation
Let us recall the equation which the estimator 0 should satisfy:
d0 de - --Vo((zo.0 0) Vol(zu, 0) d0
E Vol(2,00 +1 x~D
(1 (1--) c) E Vjl(2,0) RND
(38)
de
Here, G (1 - c) - For leave-one-out, we have that G D and F Dn. Without loss of generality, assume that the removed sampled index = and so 2; nn. and consider the shorthand D Di=" Overall, then we are considering the contamination: D (1 D) + ted... with n-I
-1 Let substitute of this back into the equation above:
Ae
A0
E [ + DND
E [el(z,0
Vol(zn, -VVe(zzn - 0,)
Ae
Ae
(39)
A0
[ol(z,0))] E Vgl(2,0 znD,
p)
AE vol(zn 0p)
(40)
x~D
A0
A0
E [vll2,)0)]++ E (Ve((z,0))) DnD,
= Vol(zn,0p) - -eVel(zn θb)
znD,
AE
Ae
+ E. ())((,00)) A0
2-D,
Ac
AP
A0
E [ E (V)e(2,0)). ZnDn
= Vol(zn, 08) + E =nD
[gl(2, 0 0b)
*>D,
AC
Ac
The last equation holds because notice that the second term = ~ 0 (where D (1- and not z ~ Dn- Since, both D, and H are empirical distributions, we can compute the expectation finite sum,
Vol(z, 21. 0p)+
Oz)(
A0 Ae
-oo((zz,,
(41)
We split the term involving the gradient of the loss into two parts: based on the 1 samples (of which f also the parameter estimator) and the other based on the left-out sample with index
n1
1
(el(z;,0)) (e((zn00p)+
1
Vollz, 0,)
AB
Vol(zn, 0D)
Ac
1=1
(42)
21

---

Published as a conference paper at ICLR 2022
The first term is since i is the parameter estimator of the first 1 samples, and will satisfy the first-order stationarity conditions. Now, rearranging terms results in:
Ae n
)z)(z.))))
Vol(zn:0 Op)
A
7
The term the left nothing but the Hessian computed over D or in other words, the first samples. Let us denote it by H p), where the |n in the superscript emphasizes that the Hessian computed over samples excluding the n-th sample. Further, Ae = c c --- Also, n-1
AO = D 0p. Thus we obtain that the change in parameter estimator (i.e., influence on the parameter estimator) is,
AO H (0,)) Vol(zn.0
(43)
m
Linearizing the loss at the left-out sample. order to look at the change loss evaluated on the 12-hh sample (left-out sample), we can consider linearizing the loss at 0 0...
Aln - Vol(zn.00) 0p) H ( (oo((z.)
But, Ad, 0i) L(zn: And, have:
E(z,, 0p) = E(=n, 0p) + 1 Vol(zn 0p) H H O,) Vol((v))))))))) 0p)
Now, we would like to average over the choice of the left-out sample n. However, we have to be careful and remember that D = D depends on the particular left-out sample i. Thus, the full expression we get the following:
2 0 Db ) Hy (oDx ) O've (z,, ( .)
LOOs = Cs( +
n E Vol
Let us recall the change in parameters with the leave-one-out contaminaion....... From eq. 43, this was
AO H nM (05) ' Vol((zn) 0p)
n
where, D: D)"", (1 D, cd.,, with n-1 and assuming n large enough.
Under this asymptotic n scenario, it is reasonable to estimate the Hessian H and Vo at the distribution Dn instead of ò := D We thereby get the following (where we also make the dependence of AO explicit on the particular left-out sample index).
(1 = p'"
0s
1 HH (0s)
Vol(zn.
) Vol(zn,0D.)
1
Vide 2 0s)
12
i=1
Vie (2 0s) Vollzn.
(44)
121
22

---

Published as a conference paper at ICLR 2022
Now, we have nice expression - in the sense that everything the right-hand side is in terms of the parameters 0s obtained by training with the usual (empirical) distribution D,.- Since, we are interested in the leave-one-out loss, let us analyze how the above change in the estimated parameters (i.e., those obtained at convergence) brings about a change in the loss incurred on the n-th sample itself ( To this end, we consider a quadratic approximation of the n-th sample loss at 0g, as shown below (this can alternatively be thought of:
1zn 0 L(zn, 0s) Vol(zn, T + A 0z) +0110(1))))
(45)
Next, we consider this procedure for every choice of the left-out-sample, and then average out to get the expression of overall leave-one-out loss. We will also assume || l|3 and thus ignore the third-order term.
LO0
Zis D
i=1
Σ
E(z,, 0g) + Vol(z,,0s) (0 A0)))) Voe(z (ge(2,,ss)00 as)
71
L(0s)
Vol(z,, 0g) (0
T
V F( As)
(46)
2n
C
To go further, we need plug in the change in parameters computed in eq. 44 above. However, first establish the validity of this general expression via the following result.
A.6 LEAVE-ONE-OUT FORMULA PROOFS
Theorem 7. Consider the particular case of the ordinary least-squares, where L(z, ()
(((x,)) u). 0) = (y 8 az)². We assume that we are given training set 5 = (()) of points sampled i.i.d from the uniform empirical distribution Dn- Let the imputs be gathered into the data matrix X E 1xd where d is the input dimension and the targets are collected in the vector Under the assumption that the number of samples n is large enough such that n that the leave-one-out expression from eq. 46 (with parameter change given in eq. 44) is equal to the widely-known closed-form formula of leave-one-oul for least-squares LOO Mathematically, we have that.
IR..
we have
2
I.00 LOOLS
1
Vi
a; 1 A
0
n
where, = xx x; denotes the i-th diagonal entry of the matrix A
X(X X)
"XxT T
(i.e., the so-called 'hat-matrix') and 0 denotes the usual solution of 0 = (X X
y obtained
via ordinary least-squares.
Proof. We will first separately analyze the terms in the summation corresponding the first-order and second-order parts in the eq. 46, which have been accorded the shorthand B, and C, respectively.
Also, to make expressions simpler, we will define the residual as r; : x; Y: and denote the matrix X X by Σ.
Let us write down the individual loss gradients and Hessian in this case. We have
Vl, Vol((D;, v1), 0) 2r; W0
23

---

Published as a conference paper at ICLR 2022
and. V2L, Vjl(((x, vz). = 2x,
The term B, in summation corresponding to the first-order part can be computed follows.
-1
-1
: V4 T A
Ve,
Σ jtt
v2e
Vl, = 2r; 2i
2 2
2 J
2r, x;;
JFL
2n my
(x X T/
Di
2n x.
( T, !)
Ij
Σ- + Σ x: 0 Σ
2n9 x
0i
1 x Σ-
(A
2r
Aii +
Ai
A
2r
A;
Essentially, we have used the Interman-Morrisee Woodbbrry formula in the fourth line above and rest is mere manipulation. Similarly, we compute the term C, from the second-order part:
-1
-1
C. = A0(3 2 A0 -Ve,
Σ
E
Evee
V4
jti
jzi
2rr² az
T
[ m::00
( 20,00 )) 23
2r? a
T
E aaaa)
-1
Aji
2r?
1- A-A
In the last line, we just reuse the computation that we already did in the previous part for x. E x.x.) æ. Finally, let us combine everything we have got with eq, 46
n
LOO - (()) +
Σ
B
+
C
2n
1=1
1 12
A
A
2
11
+
2T
n
71 1=1
A
1
Av
A
Aji
2
Σ T
1
Ai
1
Asi
A
1+
A H
2
Ti
A
Thus, remembering our shorthand r; = @T.; - Di, we conclude our proof.
24

---

Published as a conference paper at ICLR 2022
Corollary 8. For any finite-width neural network, the first and second-order influence function give similar formulas for LOO like that in Theorem 7, but with A "s(0")T (Zs(0")ss)) (zs00)))((0)))) are the parameters at convergence for MSE loss.
"s(0") (ss(0)) where Zs(0") VVofo (x1),.... Vefo (In)) and 0*
Proof. Simply replace æ, Veje (x;) in the proof of Theorem and repeat the procedure, since all the steps hold under the assumption of MSE loss and considering the Hessian H (0") H (0') provided for by the assumption A2.
A.6.1 OVER- PARAMETERIZED CASE
In our above discussion, we considered that Σ X X was invertible (and likewise in the corollary considered Zs (0") Zs (0") was invertible). However, in the over-parameterized case this many not necessarily be the case. Nevertheless, there is one simple fix to this issue, as often carried out in the literature. We consider Σ A+ in place of Σ for À O, and in regards to influence functions, this would basically amount to having an l regularization in the loss function. exactly repeat the same steps in the proof of the Theorem 7, except with Σ instead. Eventually, we recover the same formulas but now the expression of the resulting matrix A is slightly different as mentioned below:
result, we can
A X
X
But, we can further use the well-known push-through identity and obtain [XXT= AT) XXT, where we consider the shorthand K == XX to indicate the kernel or (K + -A)= K which is the familiar expression as seen in regularized kernel regression. For the case of Corollary 8, the same extension can be carried out, except that now the matrix will be the empirical Neural Tangent Kernel (NTK) (Jacot et al., 2018) matrix at the optimum 0"
the gram matrix. Rewriting this gives,
25

---

Published as a conference paper at ICLR 2022
B INFLUENCE FUNCTIONS: A PRIMER
In this primer on influence functions, we closely follow the textbook of Hampel al. (1986). The key objective of influence function is investigate the infinitesimal behaviour of functionals, such as n. In particular, this defined when the change in underlying distribution can be expressed in the form of Dirac distribution. Formally, this defined as follows:
Definition 10. The influence function IF of the estimator T, at some distribution F, evaluated at point z (where such limit exists) is given by,
T(1 e) + +602) - T(F)
IF [F T, lim c-0
E
Essentially, the influence function (IF) involves a directional derivative of I F along the direction of 62. Further, in order to interpret the above definition, substitute F by Dn-1 and put implies that (TF) measures n times the change of statistic T due to an additional observation 2. In other words, it describes the (standardized) effect of an infinitesimal contamination on the estimate T. E.g., the case of parameter estimator, the change estimated parameters due to presence of an additional datapoint. By now, the astute reader can already see its natural application for leave-one- out error, but we ask for some patience so as to discuss some other important aspects of influence functions.
This
More generally, one can view influence functions from the perspective of Taylor series expansion (to be precise, the first-order Mises expansion) of T at F, evaluated some distribution G "close" to F,
T(G) T(F) + / /IF(::T,F)d(C F2) remainder terms.
(47)
So, evident from this, is also possible to consider higher-order influence functions and use them in a combined manner, as considered in Debruyne et (2008). However, since the first-order term is often the dominating term as well as ensure tractability when later consider neural networks we will restrict our attention to only first-order influence functions hereafter.
B.1 PROPERTIES OF INFLUENCE FUNCTIONS
(i) Zero expectation. The expectation of influence function over the same distribution is zero, i.e. f [F(2;; F))F(z) = 0. This should actually be quite intuitive as we are basically averaging all possible deviations of the estimator. But, the formal reasoning is that influence function essentially akin to Gâteaux derivative at the distribution F,
T ((1
F)F + + T(F) - IF(=)dG(z).
lim c00
Now, replace G by F in the above equation and the stated property follows.
(ii) Variance of IF provides asymptotic variance of corresponding estimator. When the obser- vations 2, sampled i.i.d. according to F, then the empirical distribution DD converges for sufficiently large, by Glivenko-Cantelli theorem. So, replacing G by D,, in eq. 47 and using the first property, we get:
T.,),.) T(F) [I(2:TT remainder terms.
Integrating over the empirical distribution Dn, we obtain:
VT(Tn(DD.) T(F))
Σ I((zTTPP) + remainder terms.
The term on the right-hand side involving is asymptotically normal by (multi-variate) Central Limit Theorem. Further, the remainder terms can often be neglected for co, and thereby the
26

---

Published as a conference paper at ICLR 2022
estimator T, is also asymptotically normal. Thus, vn((,, - T(F)) 4 No, V(T, with the asymptotic variance (more accurately, covariance matrix) F) as follows:
F) -IF(E:T.))EIEE:IIT... dF(z).
For the one-dimensional case, i.e., T(F) E R, we simply get ((T, = ()
(iii) Chain rule for influence functions. Suppose our estimator (F) depends on some other estimators, i.e., 0(F) T (F). (F) then can expression the influence function for
(F)
0T 00,
IF(2;0,F) = Σ IF(z;0,,F) F).
(48)
Remark. refer the mathematically-orienee reader to Huber (2004) for details on the regularity conditions needed to ensure the existence of TF and the like.
27

---

Published as a conference paper at ICLR 2022
C EMPIRICAL RESULTS AND DETAILS
C.I EMPIRICAL DETAILS
We train all the networks via SGD with learning rate 0.5 and learning rate decay by factor of 0.75 after each quarter of the target number of epochs.
For the experiments based on MNISTID (Greydanus, 2020), the input dimension size is d 40 while number of classes is K 10.
Double-descent model sizes (a) For the 3-layer double descent plot, we consider hidden widths mi, M2 E {10, 20, 30, 40, 50} and choose all those pairs as experiments where |m m2 S 20.
(b) For the 2-layer plot in MSE, we take the hidden layer widths from [1, 151] at an interval of 10.
(c) For the 2-layer plot corresponding to CE, we take hidden layer sizes from [2,32] at intervals of 2 and then for reducing the computation load when the network sizes increase, we take coarser intervals with a gap 5 and for even bigger sizes, at gap of later 10. But this is purely to reduce computational load that comes with Hessian computation.
In all the double descent curves, ensure that near the interpolation threshold all models are interpolation, in the sense that the training accuracy is 100%.
C.2 VERIFICATION OF ASSUMPTION A3
mum www.ooowweeee..... A200 (0op scate)
Optimum
1003
2300
2002
$000
(a) 2-hidee layer case, MNISTID.
-2
-30
-32
mum
Initiallzation
3000
1-hidden layer, CIFAR 10.
Figure 4: Additional results on verifying the assumption A3
28

---

Published as a conference paper at ICLR 2022
C.3 CROSS ENTROPY DOUBLE DESCENT
Appliitir
[os Test your
Papdssele 1est
Jesn end
1980
(a) Final Test Error
(b) Best Test Error
Figure 5: Both test emror at the final epoch as well as the 'best' test error in terms of the one selected based on a small validation set.
C.4 MSE DOUBLE DESCENT
For the sake of visualization in the 3-layer case, we smooth the quantities involved by considering a moving average of them over three successive model sizes.
1.5
1xp scukk
1.29
-12
LTX
of peraniree
(a) L=3, Smoothed version
(b) L=3, Unsmoothed version
+000 Opp ucdee
2002
2007
2002
5.00
(c) I.=2, Smoothed version
(d) I.=2, Unsmoothed version
Figure 6: We see that the same trend holds in both the cases - In fact, the unsmoothed version perhaps even more starkly shows the minimum non zero eigenvalue vanishes at the maximum pop- ulation loss.
Also, in the unsmoothed version of the above plots, we also show the corresponding train loss. It must be emphasized that near interpolation the training accuracy is 100%, even though there might be some non-zero training loss.
29

---

Published as a conference paper at ICLR 2022
C.5
RESULTS ON ADDITIONAL DATASETS
AX0
Prsssterioo
1595
2001
-5.55
1853
1390
2000
1050
3000
155
(a) L=2, CIFARIO
(b) L=2, MNIST
Figure 7: Population risk behaviour alongside the minimum eigenvalue of the Hessian at the optimum for CIFARIO 10 and MNIST with MSE loss.
Empirical details. The optimization details the same mentioned before in the setting of MNISTID, except that we train longer for 20K epochs. We downsample the input dimension for CIFAR10 10 and MNIST to about the same size so
ensure consistency, and in particular, = 48 for CIFARII 10 (by downsampling 32 x 32 x 3 images to 4 x x 3 and then flatten- ing) while d 49 for MNIST (by downsampling 28 28 images to 7 and then flattening). We find that on harder datasets like these, it takes even longer to drive the networks to interpola- tion and thus consider n 40 samples. We consider the sizes of the hidden layer from the set 31, 5, 7, 9, 11,21, 21, 31, 41, 51, 61. 71, 81, 91, 101, 111}. In other words, we sample at a finer gran- ularity near the interpolation threshold (Rx 400), while increase the gaps later on. Also, we find that networks with hidden layer width m = fails to train and gives NANs, so we exclude its result. Overall, we find that the population risk and the minimum non-7ero eigenvalue of the Hessian the optimum show very similar trend like in the case of MNISTID. As result, this implies that our empirical findings also generalize to other datasets as well.
C.6 2-IIIDEEN LAYER RESULTS FOR LARGE DIFFERENCE IN SUCCESSIVE LAYER SIZES
2.55
2.80
llop soalel
2.80
Pepu
2.35
3.43
2000
3106
6020
6C00
7000
(a) L=3, MNISTID
Figure 8: Population risk behaviour alongside the minimum non-zero eigenvalue of the Hessian at the optimum for 2-hidden layer network on MNISTID, but where the successive hidden layer sizes my, my have much bigger differences - i.e., [m1 m2l < 120 with MSE loss.
30

---

Published as a conference paper at ICLR 2022
Previously, in our double descent experiments for 2-hidden layers, considered that hidden widths m1. m2 E {10, 20, 30, 40, 50) and chose all those pairs where |m m2l I 20. Now, a question might arise what happens in the case when the successive hidden layer sizes are very 'imbalanced' (or non-uniform)), i.e., they have a big difference between their sizes. The Figure shows the setting of double descent with hidden layers with sizes my and m2, which chosen as per m. {20, 40} and m2 E {20, 40, 60, 80, 100, 120, 140). Rest of the empirical details regarding training and dataset identical to the MNISTID setting considered earlier. We find the population risk and minimum non-zero eigenvalue behaviour which is very similar to Figure 1 and in accordance with our theoretical predictions. This also confirms that our theoretical analysis generalizes to diverse architecture patterns, not just the 'balanced' setting in which double descent was has been considered before, which leads to the following remark.
Closing remark. Before finish this discussion, let us emphasize that almost all prior works on double descent Nakkiran et al. 2); Nakkiran (2019) consider the case of 'balanced' hidden layer sizes. In other words, these works consider fixed architectural pattem, say {m] - {2m} - {m} and then increase the common width multiplier m. In this respect, we are one of the first works that not just demonstrates the occurrence of double descent in the imbalanced hidden-layer settings but also explains the behaviour via the trend of the minimum non-zero eigenvalue of the Hessian at the optimum.
C.7 NATURE OF CONSTANTS FOR THE EIGENVALUE ASSUMPTION
In the assumption A3, we assume the existence of constants 0 < Ag < Bgg co such that the following holds:
A Amin ())()))) S Amin (C) (0')) S B Amin (C$(0"))
So in this section, how these constants actually behave in practice and if they are (1) across varying
network sizes? Or, equivalently, how the ratio Anni C (0'
Cj ()")) behaves and if it is O(1)
Ratio Amm Amn!Ci(0P))
25
Ceee 111
30
1302
5100
4002
5020
2020
paramaeter
Amin C (0)) Auni (O))
Figure 9: The ratio
We consider the setting of one-hidden layer neural networks trained with MSE loss for 5K epochs as discussed in the main text (for other training details, see Appendix C.1). To remind, we consider networks of hidden layer sizes sampled uniformly from [1, 151] at an interval of 10. The Figure plots this desired ratio. We find that indeed this ratio is ((1). More precisely, the Table details the summary statistics this ratio.
Overall, the trend in Figure and the precise summary statistics in the above Table even implies the existence of universal constants for A3 and Bg (c.g., setting would be to 0.3 and 12 respectively). This ratio naturally depends on the problem, so is likely that will change slightly (c.g., on CIFAR 10, the mean changes to 7.812) but are able to confirm the existence of universal constants
31

---

Published as a conference paper at ICLR 2022
Minimum
Median
Mean
Maximum
0.336
2.019
3.754
11.955
Anin C (0
Table 1: Summary statistics of the ratio
Amin C
across all our experiments, Lastly, there is also a theoretical basis to it, as remarked in the main text, since the map A (A) is Lipschitz-continuun on the space of Hermitian matrices, which follows from Weyl's inequality (Tao, 2012, 56).
Final remarks. Importantly, would thus like to reiterate that we never impose constraints the minimum eigenvalue of the covariance of the function Jacbians. But, rather inspired by the above empirical observation, consider the existence of such constants.
32

---

Published as a conference paper at ICLR 2022
C.8 CONSTITUENT OF HESSIAN AT THE OPTIMUM
For our analysis, we made the assumption A2 based on the prior works of (Sagun et al., 2017: Singh al.. 2021). We also find in our own experiments that the very same observation made in these papers holds - namely, that the Hessian Hę at the optimum is only composed of the outer-product Hessian H., while the functional Hessian H O.
To show this, we plot in Figure 10 the nuclear norm, spectral norms, as well as the minimum non- zero eigenvalue the the overall loss Hessian He and the outer-produce Hessian H, for one-hidden layer networks trained for 20K epochs and with rest of the training details identical to all other experiments.
2.4
(a) Nuclear norm
(b) Spectral norm
(c) Minimum non-zero eigenvalue
Figure 10: Comparison the spectra H and H. at the optimum 0* (across the set networks trained for double descent). We find that across all the above-plotted measures the curves for H and H. coincide. Thus showing that the functional Hessian H, goes to zero at the optimum and thereby establishing the merit of the assumption A2.
C.9 LOWEST FEW EIGENVALUES ARE THE DOMINATING FACTOR BEHIND DIVERGENCE NEAR INTERPOLATION THRESHOLD
We consider the settings of CIFARIO, MNIST, and MNISTID, all of which correspond to the dou- ble descent shown in Figures 7a, 7b, and 1 respectively. To demonstrate how many of the lowest eigenvalues capture the double descent trend, for each model in all of the above settings, the of the trace (of the Hessian inverse) captured by the lowest eigenvalues of the Hessian, since the lower bounds exhibit this dependence. In order model sizes, we consider the lowest eigenvalues in 0.5%, 1%, 2%, 5%, 10% of the total number of cigenvalues of that model. The results can be found in the following plots:
plot
consistent comparisons across varying
We that across all these cases just 0.5% of the lowest eigenvalues enough to capture the double descent behaviour capturing a minimum of 60% of the trace near interpolation across all these settings.
Observations.
33

---

Published as a conference paper at ICLR 2022
Smalkut Smoatest
26
100
mosse cipourd by by
(a) L=2, CIFARIO
Smaa 5%
Smatlea Bost 3%
Smalee 10%
Sma Ralk 2%
most by lut lot-llooooooonaaa
100
L=2, MNIST
fet
Smaleed Smraeest 10%
the lstt
1003
2002
5160
6020
paramelars
(c) L=2, MNISTID
The % of the Hessian inverse trace captured by varying proportions of smallest eigen- values of the Hessian across multiple datasets for MSE loss.
Figure 11:
Further > 98% of the trace is captured as soon as we have 1% the lowest eigenvalues for CI- FAR10, 0.5% for MNIST, and 5% for MNISTID. This clearly shows that the double descent be- haviour indeed captured by a very small handful of the lowest eigenvalues. (As matter of fact, the interpolation threshold, even just using the minimum non-zero eigenvalue alone captures 85.56% of the trace for CIFAR 10 and 97 80% for MNIST.)
34

---

Published as a conference paper at ICLR 2022
C.10 LOWER BOUND COMPUTATION
At an initial glance, it might seem that the computed lower bounds could be very small in magnitude be of use the bound is scaled by min-
However, while practically computing one can consider tighter lower bound, by using a particular tolerance T.
Let us illustrate by considering evaluating this bound on a test set S' (just like we actually do). This because the lower bound have the expression,
LHS
Σ (2.))SS
TT (A(r))
(V)e(fo-(z)))))
S
Now, since Tr (A (a.w) is non-negative, if we are given a tolerance т, we filter out those samples with V y (x). y) <
LHS
Tr (A(z))) + 1[IV (()) +}] (a.y)ES'
S
where, 1 is the indicator function. This helps us compute lower bounds which can be evaluated in practice.
Trace baved Lower bound
-an Aee based Lower bound
Looder lockrnd Uoo ScaLl)
-10
-12
500
parameters
Figure 12: Comparison of lower bounds with trace vs minimum eigenvalue
35

---

Published as a conference paper at ICLR 2022
C.11
EMPIRICAL OBSERVATIONS FROM LINEAR REGRESSION
C.11.1
HESSIAN STATISTICS ON TRAINING SET
Leear sngressiin with acancdal N--1R, Rout,
User rigins with narplle beias, inpittraiic
28
18
(a) Condition number
(b) (log scale) Condition number
Unea Nv-100 Inpet/ark:d22
Unear Wrangiis 50-100, input/antt
10
(c) Max absolute eigenvalue
(d) (log scale) Max absolute eigenvalue
175
(e) Min absolute eigenvalue
(f) (log scale) Min absolute cigenvalue
Uneer reg vution with Pranglis Six 200 inout parvi B1L
Unser rig wos with musnglic 20- Ingull PAA.II
154
144
28
(g) Nuclear norm (or Trace)
(h) (log scale) Nuclear norm (or Trace)
Figure 13: Hessian statistics computed over the training set. We observe that condition number diverges at the double descent peak, owing to minimum absolute eigenvalue becoming close to zero this threshold.
36

---

Published as a conference paper at ICLR 2022
C.11.2 HESSIAN STATISTICS ON TEST SET
Uher repeedaan doumplo 1o100,
Paomslo 1w-30 insitrancc
213
74
2.5
(a) Condition number
(b) (log scale) Condition number
150
225
250
175
Max absolute eigenvalue
(log scale) Max absolute eigenvalue
Linea reprasiion with msundler 8-100) houuusee di
Unear regraubn with #ramgna 10-103 Inputrant:871
3P
(e) Min absolute eigenvalue
(f) (log scale) Min absolute eigenvalue
Figure 14: Hessian statistics computed over the (size 500).
37

---

Published as a conference paper at ICLR 2022
C.11.3
DRAWING DD PLOTS ARBITRARY THRESHOLDS
regression daarpleck- Frput, mo.z.mnkk:1
Uiar Reamales M-101,
6-109
527
(a) 1 100, d" 100, B =
(b) 71 100, d" 200, B 1
regrendion eaarppec-- Frput, matk:
Livrr acamales M-102,
4
(c) n1 100, d" 300,
(d) n 100, 400, B 3
Figure 15: Changing the position of the interpolation threshold by adjusting the rank of the under-
lying input-covariance matrix.
The input design matrix is constructed in such way that given some d' many input features, the number of base features is d. But we additionally have 3 d many redundant features (composed of linear combinations of the base features). Also, the number of features is increased in the above test loss curve, these redundant features follow in succession to the base features. Therefore, any point in these graphs along the x-axis for some number of features d', the effective number of features are
Hence, the peak occurs when the effective number of features equals the (3 +
d'
(effective) number of samples, i.e., at 3+1 = n, which is nothing but d' = nn3 + 1). Thereby, looking from the perspective of rank (the Hessian here is simply the covariance matrix), the position of the interpolation threshold can reconciled.
38


Reviews:
[{"review_id": "tRM1tL3B0D", "reviewer": "Reviewer_E8Hk", "summary": "", "questions": "", "limitations": "", "rating": 3, "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 topic and the goal are both very important. However, the theorems are crucially limited and incremental. Theorem 3 simply rewrites the population risk by putting the difficult term into the expectation or population covariance of the gradient. The right-hand of (1) cannot be evaluated because of the population covariance. In the most cases, if we can evaluate it, then we can evaluate the population risk too. Moreover, the second term includes the trance of the matrix of size of the number of parameters. Thus, this can grow linearly as we increase the number of parameters in the worst case, which is not good for over-parametrized regime that this paper focuses on; otherwise, the first term is no longer negligible.  \n\nThe proof of Theorem 3 is very unclear regarding the O(n^2) term. It reads “when |S| = n is large enough to ignore O(n^2) terms, the (infinitesimal) definition of influence function is equivalent to using the finite-difference form”. However, the O(n^2) term can also grow in practice as we increase n. Thus, the authors must include the exact expression of the O(n^2) term and a more precise argument on why we can ignore this term. \n\nIn Theorem 4, Assumption 5 is problematic in many ways. First of all, the main goal of paper, as stated, is to avoid the neural tangent kernel regime, which is known to be not practical, and to analyze the practical finite-width regime of neural networks. However, Assumption 5 almost results in the neural tangent kernel regime, because the covariance contains neural tangent kernel by the chain rule, and the Assumption 5 restricts the practical change of the neural tangent kernel during the training, which is exactly the main issue of the neural tangent kernel regime. In the neural tangent kernel regime, the neural tangent kernel is not allowed to change a lot, which means that neural networks in the neural tangent kernel regime is equivalent to linear models with a random feature (or the initial kernel). The proof of this paper is not addressing this main limitation.\n\nMinor comments: why equation (10) in Theorem 10 does not contain O(n^2) term? There is a typo on page 3 with undesired space before `let us consider who the parameter estimator’. \n\nUpdate after author response: the authors' responses do not address my concerns. Assumption 5 (and the minimum eigenvalue in the revised version) is problematic. The modes studied in this paper are essentially still in the lazy/kernel regime. Based on these, I keep my original score.", "summary_of_the_paper": "This paper derives an expression of the population risk with influence function, and then use that to derive a lower bound on the population risk, which provides an explanation for double descent phenomena in the finite-width regime at the optimum point. The paper provides experiments to support the theoretical arguments. Moreover, the authors investigate how the choice of loss functions affect the double descent phenomena.", "summary_of_the_review": "The topic and the goal are both very important. However, the theorems are crucially limited and incremental as explained above. Moreover, the main claim to analyze the finite-width neural networks outside of the neural tangent kernel regime is not well supported because of the Assumption 5. \n\n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "1: The contributions are neither significant nor novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "lG6DNUSwdna", "reviewer": "Reviewer_SyuK", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Novelty: While the impact of the Hessian on the learning dynamics is expected, analysing it using the influence functions is novel to the best of my knowledge, and provides valuable  insights,  as  it  allows  to  express  the  population  loss  differently,  and therefore explicit a lower bound showing the double descent behavior.\n\nClarity:The  paper  is  generally  well  structured  and  clearly  written.  The  argument  is outlined  from  the  beginning  and  detailed  afterwards,  which  makes  it  easy  to follow.\n\nSignificance of the theory: The  overall  argument  is  well  constructed,  and  to  the  best  of  my  knowledge,the  provided  proofs  seem  correct.   In  particular,  the  analysis  in  terms  of  the Hessian  spectrum  and  rank  and  the  approach  taken  by  the  authors  to  do  so provide explanations to many of the latest observations in the double descent phenomena (e.g. the effect of regularization [Nakkiran et al., 2020]).  A major strength of the paper is the focus on finite-width models,  and the analysis of the cross entropy loss, which are of particular interest to practitioners.There are however a few weaknesses, in my opinion, of this analysis:\n* The  authors  claim  that  the  only  interesting  term  to  analyze  when  the model grows is the Hessian’s smallest non-zero eigenvalue.  There are however  in  the  bounds  other  quantities  that  can  hide  a  dependence  on the size of the model, and on which the authors do not provide sufficient comments - in particular the constants $A_{θ_0}$ and $B_{θ_0}$.  While the role of these constants is conceptually clear (i.e. the spectrum of the covariance of the gradients at the optimum is close to the one at initialization), it is not obvious that these constants are independent of the size of the model.Can the authors provide a more precise comment on these constants?\n* The provided analysis considers the size of the model,  independently of its architecture.  However, growing a model by increasing its depth or its width results in different training dynamics.  Can the authors comment on  this  point?   Can  their  analysis  be  adapted  to  take  into  account  the network’s architecture?  What happens if, for example, the difference in width between the hidden layers is larger than 20?\n* Recent works suggest the presence of a triple rather than a double descent in  neural  networks  [d’Ascoli  et  al.,  2020].   The  study  of  the  eigenvalues of the Hessian can only provide an explanation for a single descent (by the nature of the random matrix theory it is built on).  Can the authors comment on this line of works and its link to their analysis?\n\nSignificance of the experiments: The  experiments  provided  in  the  paper  are  in  line  with  the  theory  and  provide an interesting support for it.  There are however a few weaknesses in the experimental section:\n* In figure 1, the authors use a different size of subset for the 2 and 3 layer networks.  While the results show a drop of the eigenvalue and a peak of the test loss in the expected threshold in both cases, it would probably be better to use similar training subsets for a matter of comparability.\n* Both the initialization of the network and the randomly chosen training subset can influence the results.  I think that it would be better to show averaged results across different seeds (10 seeds would be great, but given how complicated and time consuming to sweep over the model size, 5 can already be enough to give an indication on the consistency and variance of the results).\n* The authors mention results on MNIST and CIFAR 10 in the main text,but they are not available in the appendix. It would be interesting to show the consistency of the results across different datasets.\n\nMinor comment: The authors cite a recent work in the discussion section that suggests that thespectrum of the features of the penultimate layer of the network can explain the double descent phenomena [Kuzborskij et al., 2021], and claim that the currentwork  contradicts  this  conjecture.   There  is  however  no  inherent  contradiction between the two approaches, they study two different quantities.  These workscan in the contrary be complementary, e.g. by indicating two different thresholds(which goes in the direction of a triple descent).", "summary_of_the_paper": "The paper provides a new analysis of the phenomena of double-descent in maximum likelihood type of estimators, with a focus on neural networks. This analysis is built on: \n* expressing the population loss based on a \"add-one-in\" procedure (a symmetric procedure to the more classical \"leave-one-out\", which allows in a second stage to use influence functions to provide a lower bound of this loss,\n* proving that the lower bound on the population loss diverges at a certain threshold, by analysing the spectrum of the Hessian at the optimum.\n\nThe paper also studies the influence of different loss functions on this behavior. In particular, the authors provide an analysis for the case of cross-entropy. Finally, as a by product of their analysis, they apply the influence function analysis to the ``leave-one-out'' loss, and show that, from a practical point of view, second order influence functions can be interesting to analyse along side the currently considered first order ones to provide a better understanding of deep learning. ", "summary_of_the_review": "The paper provides a novel analysis tool for the double descent phenomena, that is particularly useful in the case of finite width neural networks.  While the work can be of high interest to the community, it has some weaknesses, in some of the theoretical results and in the empirical validation that can limit its impact.This is why a recommend acceptance, but I think the paper can be improved.\n\nPost rebuttal: The authors addressed most of my concerns, as well as most if the other reviewers' comments and questions. The resulting paper is substantially improved, and I therefore recommend accepting it. ", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "VMFqiMzndHp", "reviewer": "Reviewer_mefD", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "Review for \"PHENOMENOLOGY OF DOUBLE DESCENT IN FINITE-WIDTH NEURAL NETWORKS\"\n===\n\nTypos\n---\n- 2nd paragraph:networksand ==> networks and\n- \"And while the connection of (infinite-width) neural networks to Neural Tangent Kernel (Jacot et al., 2018) provides interesting parallels, but ultimately its applicability to finite-width neural networks — i.e., models of practical significance — is unclear.\" <== Please rephrase.\n- Please choose between use of \"double descent\" and \"double-descent\".\n- \"Add-one-in procedure .\" ==> \"Add-one-in procedure.\" (remove stray space)\n\nOther minor issues\n---\n- \"Thanks to the influence function of the parameter estimate (Eq. 4 for D = D_n)\" <== Eq. 4\nis in the appendix. It should already appear as an equation in Propositoon 2 of the main\nmanuscript, then reference it.\n- A1: $\\ell(f_{\\theta_\\star}(x), y)$ is not a function, it is a number...\n- A4: Doesn't look good. The justification given by the authors is not satisfactory either. Indeed, the authors claim that A4 can be met at the price of a $\\lambda_\\min(\\Sigma)$ factor in the bounds. The issue is that lambda_min(Sigma) that as long as there isn't a sensible lower-bound on $\\lambda_\\min(\\Sigma)$, say in the case of neural networks, then all bets are off. At the very least, the authors should formally / rigorously justify this step.\n- In the appendix, results shouldn't be restarted under labels / names different from those used in the main paper. Makes the proof difficult / impossible to follow. For example, Corollary 5 in the paper is called Corollary 13 in the appendix, without any reference to one another; Theorem 3 has become Theorem 10 in the appendix (again without any reference to one another...).\n\nMajor issues\n----\n- Assumption. One of my main concerns with the paper are the assumptions. \n  - For example, what is a croncrete nontrivial scenario where all those assumptions hold simultaneously ? This is in contrast to previous works, wherein the assumptions made on the model and data are quite transparent to the reader. For example, what do the results of the current paper say about a single layer neural network with random hidden weights, and output weights learnt with MSE loss (this was analyzed in Adlam and Pennington 2020 \"The Neural Tangent Kernel in High Dimensions: Triple Descent and a Multi-Scale Theory of Generalization\")?  \n\n- It's not clear what is ultimately being assumed in Corollary 5. \n\nAfter authors' response\n---\nI'm changing my score from 6 to 8. I was convinced by the answers given to my concerns.\n", "summary_of_the_paper": "The paper studies the double-descent phenomenon in a very general scenario: general loss functions which include but are not limited to MSE and cross-entropy, and general finite-width neural networks (i.e not limited to linearized -- NTK / RF-- regimes). The main tool here is a clever use of *influences* function (from classical robust statistics), which allows the authors to study (in principle) double-descent curves for the risk of estimators defined only implicitly via MLE optimization problems, say. The end result is that the authors manage to lower-bound the population risk by a term which depends on the trace of the inverse of the hessian of the loss function at the optimum. When then this hessian becomes singular, the aforementioned trace-of-inverse explodes to infinity, and a double-descent curve occurs. The location of this double-descent curve is accurately predicted by this paper.", "summary_of_the_review": "This paper presents a completely new approach to understand the phenomenon of double-descent, for very general models / loss functions (including finite-width neural networks). I have a few concerns about the assumptions being used in the paper though (as explained further above).", "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": "4: The contributions are significant, and do not exist in prior works.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "NnDSrSs93Oh", "reviewer": "Reviewer_hctT", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "The paper is very well written, very clear and it is well aware of the current state of research and the literature. The contribution is worth publication.  ", "summary_of_the_paper": "The paper discusses the phenomenon of double descent in the framework of finite width neural networks trained with various loss functions. The analysis of the authors relies on the use of influence functions. They provide intuition on the dependence of double descent on the number of samples in the overparametrized regime and on the number of parameters (in the under parametrized regime) by highlighting the dependence of the population loss on the inverse of the smallest eigenvalue of the Hessian. By adding some additional assumption on the initialization and relying on random matrix theory, they are then able to express this smallest eigenvalue as proportional to the square of the difference between the number of training points and the number of parameters which matches the blow up observed numerically at the so-called interpolation threshold. \n", "summary_of_the_review": "Introduction \n\n- I would remove the sentence “as well as can cater to the idiosyncrasies that arise with the usage of neural networks”. It is so unclear that you have to explain it right after with the id est. Stick to  what you do, this is good enough: I would replace the entire paragraph with something like “We develop a theoretical analysis of double descent in the finite width framework and study how this phenomenon is impacted by changes in the loss function” or something similar\n- “by utilizing the tool of influence functions” —> ”by relying on influence functions which are commonly used in robust statistics” or if you really want “by using the notion of influence functions from ..” \n-  In the last paragraph, “starkly” might be a bit strong. I would replace with “clearly” or “which has a clear influence”\n\nSection 2.1.\n\n- When you use not only at the beginning of a paragraph, you should invert : “Not only they have useful properties” —> “Not only do they have useful properties” \n\nSection 2.2. \n\n- Why would you need regularity conditions to exchange the order of the expectation and the derivatives. This is not clear to me. Expand or remove. \n\nSection 3\n\n- The sentence “the change in loss and which we leverage” should be changed to “the change in loss which we leverage”\n- The sentence “this quantity is inconsequential ” is not very clear. Why not replace the remark with a clear explanation of the form : “Although the first term on the RHS of (1)  is not the exact training loss, it only deviates from that loss by a negligible quantity related to the difference of the training losses for two distinct training sets. When training for sufficiently long, both losses vanish and the difference thus becomes negligible. ” or something similar\n\n\nSection 4\n\n- A reference on the decomposition of the Hessian into The outer product Hessian and the functional Hessain would be good\n- I would replace the constant $A_{\\theta_0}$ and $B_{\\theta_0}$ with simpler symbols such as lower case letter or $c_0$ and $c_1$ or \n- Do we really use the term external regularization to denote the absence of any regularization?\n\nSection 4.2.\n\n- The key result (to me) which formalizes the double descent phenomenon is really corollary 5. I think it would be good to have that result appear somewhere earlier. For example in an informal form in the introduction. \n\nSection 4.3.\n\n- You provide a lower bound on the population loss, however, from the plot you give in section 4.3. it seems that one could also derive an upper bound (although probably not at the interpolation threshold). I.e. Would such an upper bound more difficult to derive given your proof technique?\n- page 7, “we can be thoroughly assure of the accuracy” should be replace by “thoroughly assured” or “we “can thoroughly assure”\n\nSection 5\n\n- The first plot in Figure 3 is unclear. What do you mean by Test error in this case, how does it vary with respect to the population loss as highlighted by the double descent curve shown in red ? \n- The explanation of the binary cross entropy loss is not very clear (double check)\n- What do you mean by “Note, this is not the case that networks were not trained long enough — rather, we run them for 40, 000 epochs” ? It would be more clear to replace the sentence with something like “Note that the networks were trained for long enough”\n\nSection 6\n\n- In the first paragraph, the sentence “which avoids the need to retrain training set size many models” is unclear. What do you mean ?\n- In the statement of Theorem 7, I think you forgot the sentence “Consider the particular case of the ordinary least-squares ” which appears in the appendix. it would be more clear to add in section 6 as well. \n- Generally speaking, it is not clear how section 6 relates to the rest of the paper. Is there a direct implication w.r.t double descent ? If I understand well we are not discussing the over parametrization regime as we consider inverting X^TX ? Although we still have a bound in the inverse of the Hessian. What prevents a bound similar to \n- Last paragraph : “raises an important aspect”. You don’t really raise an aspect. I would replace with “which highlights an important downside of first order influence functions” or even simpler “which confirms the suboptimality of first order influence functions when used in the leave one out framework”. \n\n\nA couple of additional comments and/or typos:\n\n- In the introduction “frequently employed deep networksand” —> “networks and”\n- In the introduction: “And while the connection … provides interesting parallels, but ultimately its applicability … is unclear.” —>  I would remove the but ultimately\n- third paragraph of the introduction, I would remove the “strive” which is not really appropriate here and replace it with the simpler \"we develop” (why complicate things when they can be simple?)\n- I would the term “function output” this makes the statements less clear. I would stick with “the function $f$”\n- Statement of Corollary 5: “For MSE loss” —> “For the MSE loss”\n\n", "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": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "LUGI38RWRf6", "reviewer": "Reviewer_hRBt", "summary": "", "questions": "", "limitations": "", "rating": 8, "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": "This work derives an interesting and to the best of my knowledge new, lower bound on DNN generalization and draws connections with a timely topic - the behaviour of finite width DNNs. The assumptions, proofs, and references to the relevant works are laid out in an accessible manner. A simple picture of the double descent behaviour arises from their work, creating a direct link with the spectrum of Wishart matrices.\n\nNotwithstanding I found the work lacking in the following aspects - \n\n** Assumptions: To derive their bound, the authors make 6 assumptions (A1-A6). Some of which seem quite reasonable however for some I didn't find sufficient support. \n\nConcerning the A2 assumption, arguing a certain term in the Hessian is zero, the authors provide two empirical references supporting this (one being very recent). However, looking at these Refs. I could not find where this is shown or implied. In addition, the authors argue that the loss term ($l_i$) would be close to zero near the interpolation threshold - but on what scale? Notably, the A2 assumption is crucial for one of the main novel features of their bound -- being robust to zero Hessian eigenvalues --- however, as far as I could tell the crux of it is the fact that $C$ always accompanies $[H+\\lambda I]^{1}$ and if $C=H$ zero eigenvalues do not contribute. Thus any small deviation of $C$ from being aligned with $H$ may affect this result. \n\nConcerning the A5 assumption, here the authors relate the low and high eigenvalue of the spectrum of the Hessian after training to that before training by some non-universal constants. For this to be of any quantitative use, these constants should be of order $1$ (otherwise the assumption is null). The authors justify this using experiments, however, due to the hardness of computing the low Hessian eigenvalues - these experiments are quite limited in scope. This again is a very crucial assumption - it allows them to glance over the difference between trained DNNs and DNNs at initialization. As such I think it needs more extensive support. \n\n** Tightness of lower bound - in their experiments the authors compare the lower bound with the actual population risk. The aim is to show they exhibit the same trend however if I understood correctly, a noticeable difference appears in their scale, with the bound being orders of magnitude lower than the actual risk slightly away from the interpolation threshold and a factor of $10$, or $e$ smaller at the interpolation threshold. This, along with the assumptions and low amount of experiments, raises concern in how intimately does their bound really affects and reflects performance. \n\n** Other real-world effects - The bound does not depend much on the high eigenvalues of the Hessian, which according to several works also affect generalization quite strongly. It also misses out on the fact that infinite width DNNs often under-perform their finite width counterparts thereby showing evidence of a second over-parameterization scale, not tied with the interpolation threshold (see for instance https://arxiv.org/pdf/2106.06529.pdf). It's true that this happens less for fully connected DNNs considered in the current work, but that's maybe a testimony against taking conclusions on finite width fully connected and applying it to real-world CNNs. In addition, while it may or may not be that the minimal Hessian eigenvalues of the true Hessian will provide a second change of trend - I find it hard to see how the analytical approach, modelling the latter as a random matrix, will provide such a second scale. \n\n** Experiments - Since this work relies on various assumptions, its potential impact is tied with verifying these assumptions. In this aspect I found the work lacking - experiments we're only done on fully-connected DNNs trained on MNIST1D reduced to 500 points. The main text promised some results on CIFAR10 but I couldn't find those in the supplementary material. In addition, I didn't find the little bump in Figure 3 (left) convincing as evidence for an interpolation peak.  \n", "summary_of_the_paper": "The current work deals with the generalization properties of finite-width DNNs from the Hessian perspective combined with the influence functional approach. Based on several assumptions, they derive a lower bound, bounding the loss by a quantity proportional to the inverse of the minimal non-zero Hessian eigenvalue. In addition, by assuming the Hessian is close to a random matrix, they estimate its lowest (non-zero) eigenvalue and show that their bound can reflect double descent behaviour at the anticipated interpolation threshold. They do so both in the context of MSE loss and cross-entropy loss. Their theoretical results are compared with small scale experiments on downsized (n=500) MNIST datasets. ", "summary_of_the_review": "An interesting exploration into the low eigenvalues of the Hessian and their links with generalization in finite DNNs. Some underlying assumptions need more support, the bound seems non-tight and not clearly reflective of the actual test loss, and the relevance to real-world settings, where other effects come into play, is unclear. \n\nFollowing discussions with the authors I currently raise my score to 8", "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": {}}]

Author rebuttal:

Meta-review: This paper studies the important statistical phenomenon of double descent, a very timely topic, using influence functions, and thereby derives lower bounds for the population loss. The reviewers generally appreciated the conceptual as well as the technical contributions in the work, but argued that the set of assumptions taken by authors can potentially diminish the significance of the analysis. This, as well as additional issues regarding the empirical and the analytical support for the modeling assumptions (and the implied scope of applicability, i.e. lazy\kernel vs. rich regime) have generated considerable discussion between the reviewers and the authors. Along the process, major and minor concerns were addressed to the satisfaction of the reviewers, resulting in a substantial improvement of the overall evaluation. Thus, this AC recommends acceptance.
Decision: Accept (Poster)