A U-turn on Double Descent: Rethinking Parameter Counting in Statistical Learning
Authors: Alicia Curth
Alan Jeffares
Mihaela van der Schaar
Venue: NeurIPS 2023 oral (2023)
Keywords: Double Descent
Statistical Machine Learning
Interpolation Regime
Effective Parameters
TL;DR: By demonstrating that the double descent shape observed in recent studies of non-deep ML methods is a direct consequence of the x-axes used to present it, we provide a resolution to the tension between statistical intuition and double descent.

Abstract: Conventional statistical wisdom established a well-understood relationship between model complexity and prediction error, typically presented as a _U-shaped curve_ reflecting a transition between under- and overfitting regimes. However, motivated by the success of overparametrized neural networks, recent influential work has suggested this theory to be generally incomplete, introducing an additional regime that exhibits a second descent in test error as the parameter count $p$ grows past sample size $n$  -- a  phenomenon dubbed  _double descent_. While most attention has naturally been given to the deep-learning setting, double descent was shown to emerge more generally across non-neural models: known cases include _linear regression, trees, and boosting_. In this work, we take a closer look at the evidence surrounding these more classical statistical machine learning methods and challenge the claim that observed cases of  double descent truly extend the limits of a traditional U-shaped complexity-generalization curve therein. We show that once careful consideration is given to _what is being plotted_ on the x-axes of their double descent plots, it becomes apparent that there are implicitly multiple, distinct complexity axes along which the parameter count grows. We demonstrate that the second descent appears exactly (and _only_) when and where the transition between these underlying axes occurs, and that its location is thus _not_ inherently tied to the interpolation threshold $p=n$. We then gain further insight by adopting a classical nonparametric statistics perspective. We interpret the investigated methods as _smoothers_ and propose a generalized measure for the _effective_ number of parameters they use _on unseen examples_, using which we find that their apparent double descent curves do indeed fold back into more traditional convex shapes -- providing a resolution to the ostensible tension between double descent and traditional statistical intuition.

A U-turn on Double Descent: Rethinking Parameter
Counting in Statistical Learning
Alicia Curth" University of Cambridge amc2530cam. ac. uk
Alan Jeffares" University of Cambridge aj6598cam... ac uk
Mihaela van der Schaar University of Cambridge mv4720cam ac uk
Abstract
Conventional statistical wisdom established well-understood relationship between model complexity and prediction error, typically presented as U-shaped curve reflecting transition between under- and overfitting regimes. However, motivated by the success of overparametrized neural networks, recent influential work has sug- gested this theory to be generally incomplete, introducing an additional regime that exhibits second descent in test error as the parameter count grows past sample size n phenomenon dubbed double descent. While most attention has naturally been given to the deep-learning setting, double descent was shown to emerge more generally across non-neural models: known cases include linear regression, trees, and boosting. In this work, we take closer look at the evidence surrounding these more classical statistical machine learning methods and challenge the claim that observed cases of double descent truly extend the limits of traditional U-shaped complexity-enneralizaatoo generalization curve therein. We show that once careful considcration is given to what is being plotted on the X-axes of their double descent plots, it becomes apparent that there are implicitly multiple, distinct complexity axes along which the parameter count grows. We demonstrate that the second descent appears exactly (and only) when and where the transition between these underlying axes occurs, and that its location thus not inherently tied the interpolation threshold p=n. We then gain further insight by adopting a classical nonparametric statistics perspective. We interpret the investigated methods smoothers and propose generalized measure for the effective number of parameters they use on unseen examples, using which we find that their apparent double descent curves do in- deed fold back into more traditional convex shapes providing resolution to the ostensible tension between double descent and traditional statistical intuition.
Introduction
Historically, throughout the statistical learning literature, the relationship between model complexity and prediction error has been well-understood as a careful balancing act between underfitting, associated with models of high bias, and overfitting, associated with high model variability. This implied tradeoff, with optimal performance achieved between extremes, gives rise to a U-shaped curve, illustrated in the left panel of Fig. [ It has been a fundamental tenet learning from data, omnipresent in introductions to statistical learning (HT90] Vap95 [TFF9), and is also practically reflected in numerous classical model selection criteria that explicitly trade off training error with model complexity [Ma173] Aka74 Sch78). Importantly. much of the intuition relating to this U- shaped curve was originally developed in the context of the earlier statisties literature (see e.g. the historical note in [Nea19), which focussed on conceptually simple learning methods such as linear regression, splines or nearest neighbor methods WW5 HT90 GBD92 and their expected
in-sample prediction error, which fixes inputs and resamples noisy outcomes Ma173 HT9) KT19.
Equua contribution
37th Conference on Neural Information Processing Systems (NcurIPS 2023).

---

Double descent
Complexity dim
U-curve
Error
L-curve
"unfolding"
Complesioe dim 2
Figure 1: A 3D generalization plot with two complexity axes unfolding into double descent. generalization plot with two complexity axes, each exhibiting a convex curve (left). By increasing raw parameters along different axes sequentially, a double descent effect appears to emerge along their composite axis (right).
The modern machine learning (ML) literature, conversely, focuses on far more flexible methods with relatively huge parameter counts and considers their generalization to unseen inputs [BC[16 Mur22]. A similar U-shaped curve was long accepted to also govern the teaeleeitttgeeerrlization relationship of such methods [GBDD92, Vap95, [TT099] - until highly overparametrized models, e-g. neural networks, were recently found to achieve near-zero training eπror and excellent test set performance [TS14 BLLT20 Bel2 In this light, the seminal paper of Belkin et al. (2019) [BHMM19 sparked a new line of research by arguing for a need to extend on the apparent limitations of classic understanding to account for a double descent in prediction performance as the total number of model parameters (and thus presumably- model complexity) grows. This is illustrated in the right panel of Fig. Intuitively, it is argued that while the traditional U-curve is appropriate for the regime in which the number of total model parameters p is smaller than the number of instances n, it no longer holds in the modern, zero train-error, interpolation regime where p>> here, test error experiences a second descent. Further, it was demonstrated that this modern double descent view of model complexity applies not only in deep learning where it was first observed [BO96] NMB + 18 SGd+ 18 ASS20], but also ubiquitously appears across many non-deep learning methods such as trees, boosting and even linear regression [BHMMI9]
Contributions. In this work, we investigate whether the double descent behavior observed in recent empirical studies of such non-deep ML methods truly disagrees with the traditional notion of a U- shaped tradeoff between model complexity and prediction error. In two parts, we argue that once care- ful consideration is given to what is being plotted on the axes of these double descent plots, the origi- nally counter-intuitive peaking behavior can be comprehensively explained under existing paradigms:
Part 1: Revisiting existing experimental evidence. We show that in the experimental evidence for non-deep double descent using trees, boosting, and linear regressions there is implicitly more than one complexity axis along which the parameter count grows. Conceptually, as illustrated in Fig. [ we demonstrate that this empirical evidence for double descent can thus be comprehensively explained as a consequence of an implicit unfolding of a 3D plot with two orthogonal complexity axes (that both in- dividually display classical convex curve) into a single 2D-curve. We also highlight that the location of the second descent is thus not inherently tied to the interpolation threshold. While this is straight- forward to show for the tree- and boosting examples (Sec. 2). deconstructing the underlying axes in the linear regression example is non-trivial (and involves understanding the connections between min- norm solutions and wnsupervised dimensionality reduction). Our analysis in this case (Sec. 3) could thus be of independent interest as a simple new interpretation of double descent in linear regression.
Rethinking parameter counting through a classical statisties lens. We then note that all methods considered in Part can be interpreted as smoothers (Sec. 4. which are usually compared in terms of a measure of the effective (instead of raw) number of parameters they use when issuing predictions [H990]. As existing measures were derived with in in-sample prediction in mind, we propose a generalized effective parameter measure p that allows to consider arbitrary sets of inputs To. Using P to measure complexity, we then indeed discover that the apparent double descent curves fold back into more traditional U-shapes because p is not actually increasing in the interpolation regime. Further, we find that, in the interpolation regime, trained models tend to use different number of effective parameters when issuing predictions on unseen test inputs than on previously observed training inputs. We also note that, while such interpolating models can generalize well to unseen inputs, overparametrization cannot improve their performance in terms of the in-sample prediction error originally of interest statisties - providing new reason for the historical absence of double descent curves. Finally, we discuss practical implications for e.g. model comparison.
Part 2:
2

---

Double Descent Trees
Error by pinn pem fixee
Ervor by pass plous flxced
Squared test error
0.8
pohnt 200
0.6
10
plba 20
plo
0..4
0.1
200
x
plod
pin/ pena
Figure 2: Decomposing double descent for trees. Reproducing [BHMM19 tree experiment (left). Test error by pleaf for fixed pens (center). Test error by pena for fixed pleas (right).
Part 1: Revisiting the evidence for double descent in non-deep ML models
Experimental setup. We center our study around the non-neural experiments in [HMMM]] as it is the seminal paper on double descent and provides the broadest account of non-deep learning methods that exhibit double descent. Through multiple empirical studies, [BHMM]9] demonstrate that double descent arises in trees, boosting and linear regression. Below, we re-analyze these experiments and highlight that in each study, as we transition from the classical U-shaped regime into the subsequent second descent regime, something else implicitly changes in the model or training definition, funda- mentally changing the class of models under consideration exactly at the transition threshold between the observed regimes - which is precisely the cause of the second descent phenomenon. In Sec. [ we begin by investigating the tree and boosting experiments, where this is straightforward to show. In Sec. we then investigate the linear regression example, where decomposing the underlying mechanisms is non-trivial. Throughout, we closely follow [BHMM19' 's experimental setup: they use standard benchmark datasets and train all ML. methods by minimizing the squared los Similarly to their work, focus on results using MNIST (with Rerain = 10000) in the main text. We present addi- tional results, including other datasets, and further discussion of the experimental setup in Appendix E
2 Warm-up: Observations of double descent in trees and boosting
2.1
Understanding double descent in trees
In the left panel of Fig. we replicate the experiment in [HMM19 's Fig. 4, demonstrating double descent in trees. In their experiment, the number of model parameters is initially controlled through the maximum allowed number of terminal leaf nodes pleaf" However, pleaf for a single tree cannot be increased past (which is when every leaf contains only one instance), and often max( (Pleaf) max(Pieaf)) whenever larger leaves are already pure. Therefore, when pleaf reaches its maximum, in order to further increase the raw number of parameters, is necessary to change how further parameters are added to the model. [HMMI9 thus transition to showing how test error evolves as averages over an increasing number pens of different trees grown to full depth, where each tree will generally be distinct due to the randomness in features considered for each split. As one switches between plotting increasing pleaf and pens on the x-axis, one is thus conceptually no longer increasing the number of parameters within the same model class: in fact, when pene > one is longer actually considering a tree, but instead an ensemble of trees (i.e. a random forest [Bre01
without bootstrapping).
In Fig. 2 we illustrate this empirically: in the center plot show that, on the one hand, for fixed pens, error exhibits a classical convex U- (or L-)shape in tree-depth pleaf_ On the other hand, for fixed pleaf in the right plot, error also exhibits an L-shape in the number of trees pens, i.e. convex shape without any ascent which is in line with the known empirical observation that adding trees to a
Squared error
0.7
plo/
plrs/
plaf 100
0.5
plsf 50
random forest generally does not hurt [HTF09 Ch. 15.3.4). Thus,
0.1
Composite Axis
only by transitioning from increasing pleof (with pens = 1) to increasing pens (with plea/ =n) i.e. by connecting the solid curves across the middle and the right plot - do we obtain the double
Figure 3: Shifting the peak.
Transitioning from pleaf to pens at different values of pleas
In multi-class settings, [HMM]99 use a one-vs-ress strategy and report squared loss summed across classes. Their use of the squared loss is supported by recent work on squared loss for classification (HB21 M and practically implies the use of standard regression implementations of the considered ML methods.
3

---

Double Descent in Boosting
Error by plun pene fixed
Error by posa plasst fixed
Squared test error
0.5
per 1
pine
200
0.4
www plini 20
0.22
10
X00x0
10
pless pm
Figure 4: Decomposing double descent for gradient boosting. Reproducing [BHMM19 's boosting
experiment (left). Test error by ploost for fixed pens (center). Test error by pena for fixed ploost (right).
descent curve in the left plot of Fig. In Fig. 3 we show that could therefore arbitrarily move or even remove the first peak by changing when we switch from increasing parameters through fleaf to pens, . Finally, we note that the interpolation threshold p n plays special role only on the pleaf axis where it determines maximal depth, while parameters on the pens axis can be increased indefinitely further suggesting that parameter counts alone are not always meaningfu
2.2 Understanding double descent in gradient boosting
Another experiment is considered in Appendix S5 of [HMM11 seeking to provide evidence for the emergence of double descent in gradient boosting. Recall that in gradient boosting, new base- learners (trees) are trained sequentially, accounting for current residuals by performing multiple boosting rounds which improve upon predictions of previous trees. In their experiments, [BHMMI9) use trees with 10 leaves as base learners and a high learning rate of y 0.85 to encourage quick interpolation. The raw number of parameters is controlled by first increasing the number of boosting rounds phoost until the squared training error reaches approximately zero, after which phoost is fixed and ensembling of pens independent models is used to further increase the raw parameter count.
In Fig. we first replicate the original experiment and then again provide experiments varying each of phoost and pens separately. Our findings parallel those above for trees: for fixed number of ensemble members pens, test error has a U- or L-shape in the number of boosting rounds phoost and an L-shape in pens for fixed boosting rounds phoost As consequence, a double descent shape occurs only when and where we switch from one method of increasing complexity to another.
3 Deep dive: Understanding double descent in linear regression
We now ready to consider Fig. 2 of [BHMM19] which provides experiments demonstrating double descent in the case of linear regression. Recall that linear regression with y E R. and X E Raxd estimates the coefficients in model y X,3, thus the number of raw model parameters equals the number of input dimensions (i.e. the dimension d of the regression coefficient vector 33 by design. Therefore, in order to flexibly control the number of model parameters, [BHMM19 apply basis expansions using random Fourier features (RFF). Specifically, given input x E Id the number, raw model parameters pe is controlled by randomly generating features Φp (x) Re(exp (expp-ivx,>) for all p S Pd, where each Vp (O 52 Iz). For any given number of features p these are stacked to give a n pô dimensional random design matrix 4, which is then used to solve the regression
lid
problem y = $ by least squares. For pe < n, this has a unique solution (33 (Φ" "0'")b'''' kTy) while for p >> ni the problem becomes underdetermined (i.e. there are infinite solutions) which is why BHMMT9 rely specific choice: the min-norm solution (3 T (T
Unlike the experiments discussed in Sec. 2 there appears to be only one obvious mechanism for increasing raw parameters in this case study. Instead, as we show in Sec. [.I] the change in the used solution فف = n turns out to be the crucial factor here: we find that the min-norm solution leads to implicit insupervised dimensionality reduction, resulting in two distinct mechanisms for increasing the total parameter count in linear regression. Then, we again demonstrate empirically in Sec. 3.2 that each individual mechanism is indeed associated with standard generalization curve, such that the combined generalization curve exhibits double descent only because they are applied in succession.
AA related point is raised in [M211) who notice that double descent phenomenon random forests appears in [BHMM19] only because the total number of leaves is placed on the x- x-axis, while the true complexity of a forest is actually better characterized by the average number of leaves in its trees according to results in learning theory. However, this complexity measure clearly does not change once pleaf is fixed in the original experiment.

---

Double Descent in Regression
Error pre, p fixed
Erroz by p ,pn fixed
Squared test orrar
pro 10000
81.5
po 10020
..a. pro 5000
pa 50000
0.1
9,,0000
10,000 4 25,000
70,0000
20100
10003
G0000
5000
10000
10000 200000
30000
40000
50000
10,000
pPO
PPc par
Figure 5:
Decomposing double descent for RFF Regression. Double descent reproduced from [HMMI9 (left) can decomposed into the standard U-curve of ordinary linear regression with pPC features (center) and decreasing error achieved by a fixed capacity model with basis improving in po (right).
3.1
Understanding the connections between min-norm solutions and dimensionality reduction
In this section, we show that, while the min-norm solution finds coefficients 3 of raw dimension pe, only n of its dimensions are well-determined - i.c. the true parameter count is not actually increasing in pe once pe > n. Conceptually, this is because min-norm solutions project y onto the row-space of 4, which is n n-dimensional as rank( make the consequence of this more explicit, we can show that the min-norm solution (which has pe raw parameters) can always be represented by using a n-dimensional coefficient vector applied to n n-dimensional basis of Φb In fact, as we formalize in Proposition I this becomes most salient when noting that applying the min-norm solution to & is exactly equivalent to a learning algorithm that (i) first constructs a n- nn-dimensional basis BsvD from the n right singular vectors of the input matrix computed using the singular value decomposition (SVD) in an unsupervised pre-processing step and (ii) then applies standard (fully determined) least squares using the discovered n nn-dimensional basi f
min( P .n) (when & has full rank). To
Proposition 1. [Min-norm least squares as dimensionality reduction.] For a full rank matrix X E Raxd with < d and a vector of targets y E I2", the min-norm least squares solution GMN {ming || 3: X y and the least squares solution (SVDD {B: B3 y} using the matrix of basis vectors B E I=*"", constructed using the first n right singular vectors of X, are
equivalent; i.e. x BMN = b 3SVD for all x E IRd and corresponding basis representation b b(x). Proof. Please refer to Appendix B.2
Then what is really causing the second descent if not an increasing number of fitted dimensions? While the addition of feature dimensions does correspond to an increase in fitted model parameters while pe < n, the performance gains in the pe > n. regime are better explained as a linear model of fixed size n being fit to an increusingly rich basis constructed in an unsupervised step. To disentangle the two mechanisms further, applied to a centered design matrix" is a special case of principal component (PC) regression [Jo182], where select all empirical principal components to form complete basis of o. The more general approach would instead consist of selecting the top PPC principal components and fitting linear model to that basis. Varying PPC, the number of used principal components, is thus actually the first mechanism by which the raw parameter count can be altered; this controls the number of parameters being fit in the supervised step. The second, less obvious, mechanism is then the number of excess featurey per = ph PPC; this is the number of raw dimensions that only contribute to the creation of a richer basis, which is learned in an unsupervised manner
note that the procedure described above. when
Based on this, we can now provide new explanation for the emergence of double descent in this case study: due to the use of the min-norm solution, the two uncovered mechanisms are implicitly entangled
"This application of the fundamental connection between min-norm solutions and the singular value decom- position (see c.g. (GVL Ch. 5.7l) reinforces previous works which have noted related links between the min-norm solution and dimensionality reduction [RD98] KL16).
*Centering reduces the rank of the input matrix by and thus requires appending intercept the PC design matrix. Without centering, the procedure is using the so-called uncentered PCs (C instead. We the centered version with intercept our experiments, but obtained identical results when using uncentered PCs.
'The implicit inductive bias encoded in this step essentially consists of constructing and choosing the top- PPC features that capture the directions of maximun variation in the data. Within this inductive bias, the role of pes appears to that as more excess features are added the variation captured by each of the PPC
PCs is likely to increase. Using the directions of maximum variation is certainly not guaranteed to be optimal [Jo82], but it tends to be an effective inductive bias in practice as noted by Tukey [Tkk77] who suggested that high variance components are likely to be more important for prediction unless nature is "downright mean".
5

---

1908.2
pet fixed, PPC +
Squazed emTor
pro 10000
Squared Ervor
pro 7500
PPC 5000 fixed, per t
81.5
pre 5000
0.5
Pe 2500 fixed, Prc t
prd 2500
3.3
0.3
PPC 7500 lixod, per 1
pdt 5000 fixed, PPc f
0.1
0.1
25000
40000
00000
200000
500000
PPC 10000 fixed, pet f
PPC
per
p0
PPC
per
(a) Shifting the peak. Transitioning from PCC to per
(b) Multiple descent. Generalization curves with arbitrarily many peaks and locations (including peaks at p > n) can he created at different values of PPC by switching between increasing parameters through pPC and pez
multiple times.
Figure 6: Disentangling double descent from the interpolation threshold. The location of the peak(s) in RFF regression generalization error not inherently linked to the point where pa = n. Instead, changes in the mechanism for parameter increase determine the appearance of peaks.
through p PPC_ + prr, PPC = minnn, Po) and pa max(0, - Thus, we have indeed n). arrived back at setup that parallels the previous two experiments: when pe < n, pPC increases monotonically while per =0 is constant, while when pe > n we have constant prc = n but pez increases monotonically. Below, we now test empirically whether studying the two mechanisms separately indeed leads us back to standard convex curves as before. In particular, we also show that - while a transition between the mechanisms increasing PPC and per naturally happens at P in the original experiments - it is possible to transition elsewhere across the implied complexity axes, creating other thresholds, and to thus disentangle the double descent phenomenon from n.
3.2 Empirical resolutions to double descent in RFF regression
Mirroring the analyses in Sec. 2 we now investigate the effects of pPC and per in Fig. In the left plot, we once more replicate [BHMM]9' 's original experiment, and observe the same apparent trend that double descent emerges as we increase the number of raw parameters pe = pPC per (where the min-norm solution needs to be applied once p==n)) We then proceed to analyze the effects of varying PPC and par separately (while holding the other fixed). As before, we observe in the center plot that varying pPC (determining the actual number of parameters being fit in the regression) for different levels of excess features indeed gives rise to the traditional U-shaped generalization curve. Conversely, in the right plot, we observe that increasing per for fixed number of PPC results in an L-shaped generalization curve- indeed providing evidence that the effect of increasing the number of raw parameters past in the original experiment can be more accurately explained as a gradual improvement in the quality of a basis to which a fixed capacity model is being fit.
As before, note that if we connect the solid lines in the center and right plots we recover exactly the double descent curve shown in the left plot of Fig. 5 Alternatively, as we demonstrate in Fig. 6(a) fixing PPC at other values and then starting to increase the total number of parameters through per allows us to move or remove the first peak arbitrarily. In Fig. 6(b) we demonstrate that one could even create multiple peak:p switching between parameter- iancractr-incrrasiin mechanisms more than once. This highlights that, while the transition from parameter increase through PPC to pez naturally occurs at ph = n due the use of the min-norm solution, the second descent is not actually caused by the interpolation threshold p itself - but rather is due to the implicit change in model at exactly this point. Indeed, comparing the generalization curves in Fig. 6 with their train-error trajectories which we plot in Appendix [.2] it becomes clear that such a second descent can also occur in models that have not yet and will never achieve interpolation of the training data.
4 Part 2: Rethinking parameter counting through a classical statistics lens
Thus far, we have highlighted that "not all model parameters are created equal" - i.e. the intuitive notion that not all ways of increasing the number of raw parameters in an ML method have the same
'hiis experiment is inspired by [CMBK2I] who show multiple descent in regression by controlling the data-ged genta-generatingggg process (DGP), altering the order of revealing new (unornnormtttve features. Even more striking than through changing the DGP, we show that simply reordering the mechanisms by which the same raw parameters are added to the model allows us to arbitrarily increase and decrease test loss.

---

effect. However, we saw in the linear regression example, it is not always trivial to deconstruct the underlying mechanisms driving performance. Therefore, instead of having to reason about implicit complexity axes on a case-by-case basis for different models, hyperparameters, or inductive biases, we would rather be able to quantify the effect of these factors objectively. In what follows, we highlight that all previously considered methods can be interpreted as smoothers (in the classical statistics sense (TT90).. By making this connection in Sec. [4.]] we can exploit the properties of this class of models providing with measures of their effective number of parameters. After adapting this concept to our setting (Sec. 4.2) we are finally able to re-calibrate the complexity axis of the original double descent experiments, finding that they do indeed fold back into more traditional U-shapes (Sec. 4.3)
4.1 Connections to smoothers
Smoothers are class of supervised learning methods that summarize the relationship between outcomes "y C R* and inputs E C IRd by "smoothing" over values of Y observed in training. More formally, let A = 1 w.l.o.g.. and denote by Dusan = {(1,, ) the training realizations of (X, E)) and by y iimin = (yi....,, yn)" "n)) the x 1 vector of training outcomes with respective train- ing indices Turain = (1,..... n). Then, for any admissible input Do E X, smoother issues predictions
f(xu)) ((za)Yumin EieImn 8 (ar)
(1)
where ((x)) (8 (zo). .............................. 8" (20)) is 1 x vector containing smoother weights for input vo- A smoother is linear if s(-) does not depend on Ytrin- The most well-known examples of smoothers rely on weighted (moving-) averages, which includes k-nearest neighbor (kNN) methods and kernel smoothers as special cases. (Local) linear regression and basis-expanded linear regressions, including splines, are other popular examples of linear smoothers (see e.g. [HT90, Ch. 2-31).
In Appendix C we show that all methods studied in Part 1 can be interpreted as smoothers, and derive s()) for each method. To provide some intuition, note that linear regression is simple textbook exam- of a linear smoother (HT90). where s(-) is constructed from the so-called projection (or hat) matrix [Eub84). Further, trees- which issue predictions by averaging training outcomes within leaves sometimes interpreted as adaptive nearest neighbor methods (HTF09) Ch. 15.4.3) with learned (i.e. non-linear) weights, and corollary, boosted trees and sums of either admit similar interpretations.
4.2 A generalized measure of the effective number of parameters used by a smoother
The effective number of parameters Pe of a smoother was introduced provide a measure of model complexity which can account for a broad class of models as well as different levels of model regularization (see e.g. [HT90] Ch. 3.5]. [HTF09 Ch. 7.6)). This generalized the approach of simply counting raw parameters which is not always possible or appropriate - to measure model complexity. This concept is calibrated towards linear regression so that, as we might de- sire, effective and raw parameter numbers are equal in the case of ordinary linear regression with p < n. In this section, we adapt the variance based effective parameter definition discussed in [HT90] Ch. 3.5]. Because for fixed s(-) and outcomes generated with homoskedastic vari- ance o² we have Var(f(zo)) [[((z)) this definition uses that 4 EieT.. Var(f(x:))
EisI... [| o² p for linear regression: one can define Pe =Eizz [1((x=)]12 and thus have Pe = p for ordinary linear regression with n < p. As we discuss further in Appendix [ other variations of such effective parameter count definitions can also be found in the literature. However, this choice is particularly appropriate for our purposes as it has the unique characteristic that it can easily be adapted to arbitrary inpul points key distinction we will motivate next.
o²
Historically, the smoothing literature has primarily focused on prediction in the classical fixed design setup where expected in-sample prediction error on the training inputs H4, with only newly sampled targets z/. was considered the main quantity of interest [H990 RTT9] The modern ML literature, on the other hand, largely focuses its evaluations on out-of- prediction error in which we are interested in model performance, or generalization, on both unseen targets and unseen inputs (see e.g. [GBC16 Ch. 5.21; Mur22] Ch. 4.11). To make effective parameters fit for modern purposes, it is therefore necessary to adapt Pa. to measure the level of smoothing applied conditional on a given input, thus distinguishing between training and testing inputs. As ||((zr))|| can be computed for any input 2o, this is straightforward and can be done by replacing Tarin in the definition of pa. by any other set of inputs indexed by Io. Note that the scale of P. would then depend on [To due to the summation,
7

---

Trees
Boosting
Linear Regression
1 (logg
105
10-
10
200 x.
x
100
mas X
0. p00
30,000
25
10,000 5-50000
pine!
peu
plout
peu
nPP + par
Figure 7: The effective number of parameters does not increase past the transition threshold. Plotting train (orange) and y (green) for the tree (left), boosting (centre) and RFF--inear regression (right) experiments considered in Part I, using the original composite parameter axes of [BHMM19]
while it should actually depend on the number of training examples n (previously implicitly captured through ) across which the smoothing occurs thus also need to recalibrate our definition by n/ Zol. As presented in Definition [ parameters pg used by smoother when issuing predictions for any set of inputs To-
we can then measure the generalized effective number of
Definition 1 (Generalized Effective Number of Parameters). For set of inputs {2]))ezoo define the Generalized Effective Number of Parameters pl
used by a smoother with weights s(-) as
p = p(Io,
n Io Ejez, 11((x9)11
Note that for the training inputs we recover the original quantity exactly (Pe = -p! Further, for moving-average smoothers with Ei= (xx) = 1 and 0 S (2())) S 1 for all it holds that 1 1 Σ n. Finally, for kNN estimators we have pg n k.
so that for smoothers satisfying also admits interesting inter- E (mn) 1 and 0 S (xo) S for all i, the quantity 1g P% pretation as measuring the effective number of nearest neighbors.
4.3 Back to U: Measuring effective parameters folds apparent double descent curves
Using Definition] ! we now measure the effective number of parameters to re-examine the exam- ples of double descent described in Sections 2 2 We plot the results of the O-vs-all sub-problem in this section the 10 one-vs-all models in the full experiment are each individually endowed with effective parameter counts pd. Fig. 7 presents results plotting this quantity measured on the training inputs (pgain) and testing inputs (ph.)) against the original, composite parameter axes of [BMM 19), Fig. 8 considers the behavior of phaa for the two distinct mechanisms of parameter increase separately. and in Fig. 9 we plot test error against p finally replacing raw with effective parameter axes.
By examining the behavior of p in Fig. 7 and Fig. 8 several interesting insights emerge. First, we observe that these results complement the intuition developed in Part I: In all cases, measures of the effective number of parameters never increase after the threshold where the mechanism for increasing the raw parameter count changes. Second, the distinction of measuring effective number of parameters used on unseen inputs, i.c. using pfa instead of pr indeed better tracks the double descent phenomenon which itself emerges in generalization error (i.e. is also estimated on unseen inputs). This is best illustrated in Fig. in the linear regression example where p. train = n is constant once Pd 2 n - as is expected: simple matrix algebra reveals that $(x;) = e, (with e; the hth indicator vector) for any training example v; once p6 > n. Intuitively, no smoothing across training labels occurs on the training inputs after the interpolation threshold as each input simply predicts its own label (note that this would also be the case for regression trees if each training example fell into its
own leaf; this does not occur in these experiments as leaves are already pure before this point). As we
Trees
Boosting
Linear Regression
10
P/ (log scale)
16
102-
10
5000
50000
10-
part
10
peu
20
por
200
200
201
140
300
130
291
2000
4000
1000
10000
plra
plood
PPC
Figure 8: Understanding the behavior of the test-time effective number of parameters across the two parameter axes of each ML method. Plotting 2/a by pleas for fixed pens in trees (left). by ploust for fixed pess in boosting (centre) and by PPC for fixed fo in RFF-linear regression (right) highlights test that increases along the first parameter axes increase jest while increases along the second axes decrease ps Larger blue and red points
) points from [HMMM9 original parameter sequence.
8

---

Trees
Boosting
Linear Regression
0,07
Squared test error
2000
PM 5000
0.00
1000C
20
20000
0.00
100
0.01
10
10
10
10P
102
10P
10
20 (log scale)
(log scale)
(log scale)
Figure 9: Back to U. Plotring test error against the effective number of parameters as measured by p (larger blue and red points: @) for trees (left), boosting (centre) and RFF-lincar regression (right) eliminates the double descent shape. In fact, points from the first dimension of [BНMMI9 's composite axis (+) continue to produce the familiar U-shape, while points from the second dimension of the composite axis which originally created the apparent second - back into classical U-shapes. Dotted lines (r"m) show the effect of perturbing the first complexity parameter at different fixed values the second.
make more precise in Appendix C.2 this observation leads us an interesting impossibility result: the in-sample prediction error of interpolating models therefore cannot experience a second descent in the (raw) overparameterized regime. This provides new reason for the historical absence of double descent shapes (in one of the primary settings in which the U-shaped tradcoff was originally motivated (HT90)), complementing the discussion on the lack of previous observations in [BHMMI9). Third, while pgum is therefore not useful to understand double descent in generalization error, we note that for unseen inputs different levels of smoothing across the training labels can occur even in the interpolation regime- and this, as quantified by past does result in an informative complexity proxy.
This becomes obvious in Fig. 9 where we plot the test errors of [BHMM19] 's experimental setup against za85 (larger blue and red points: o. o). For each such point after the interpolation threshold (o), we also provide dotted contour lines (1..)) representing the effect of reducing the parameters along the first complexity axis (Pleaf, pboost and PPC). resulting in models that can no longer perfectly interpolate (c.g. for trees, we fix their number pens and reduce their depth through pleaf). Finally, we discover that once we control for the effective parameters of each model in this way, we consistently observe that each example indeed folds back into shapes that are best characterized as standard convex (U-shaped) curves providing a resolution to the apparent tension between traditional statistical intuition and double descent! We also note an interesting phenomenon: increasing pens and pez appears to not only shift the caaplexity--eneralll value of pleaf, phoost and pPC'), but also shifts them to the left (decreasing the effective complexity implied by each value of plea! pbonet and PPC, as also highlighted in Fig. (8) and flattens their ascent (making error less sensitive to interpolation). That is, models in (or close to) the interpolation regime discovered by [BHMM19] exhibit very interesting behavior where setting pew and pens larger actually decreases the test error through a reduction in the effective number of parameters used.
contours downwards (decreasing error for each
5 Consolidation with Related Work
In this section, we consolidate our findings with the most relevant recent work on understanding double descent; we provide an additional broader review of the literature in Appendix A A large portion of this literature has focused on modeling double descent in the raw number of parameters in linear regression, where these parameter counts are varied by employing random feature models BHMM19 BHX20) or by varying the ratio of n to input feature dimension d [ASS20 BLLT20 ML HMRT22). This literature, typically studying the behavior and conditioning of feature covariance matrices, has produced precise theoretical analyses of double descent for particular models as the raw number of parameters is increased (c.g. [BLLT20, HMRT22)). Our insights in Sections S and 4 are complementary to this line of work, providing a new perspective in terms of (a) decomposing raw parameters into two separate complexity axes which jointly produce the double descent shape only due to the choice of (min-norm) solution and (b) the underlying effective number of parameters used by model. Additionally, using theoretical insights from this line of work make more precise the role of per in improving the quality of a learned basis: as we show in Appendix [.3] increasing pez in our experiments indeed leads to the PC feature matrices being better conditioned.
Further, unrelated to the smoothing lens we use in Part 2 of this paper, different notions of ef- fective parameters complexity have appeared in other studies of double descent in specific
9

---

ML methods: BM21 use Rademacher complexity (RC) in their study of random forests but find that RC cannot explain their generalization because forests do not have lower RC than in- dividual trees (unlike the behavior of our 1 in this case). [MBW20] use [Mc99]]ss Bayesian interpretation of effective parameters based on the Hessian of the training loss when studying neural networks. While this proxy was originally motivated in a linear regression setting, it can- not explain double descent in linear regression because, as discussed further in Appendix [D] it does not decrease therein once > n. Finally, [DLM20) compute effective ridge penalties im- plied by min-norm linear regression, and [DSYW20] consider minimum description length princi- ples to measure complexity in ridge regression. Relative to this literature, only in terms of the ML methods we can consider (in particular, we are uniquely able to ex- plain the tree- and boosting experiments through our lens), but also in the insights provide e.g. we distinctively propose to distinguish between effective parameters used on train- versus test- examples, which we showed to be crucial to explaining the double descent phenomenon in Sec.
work differs not
6 Conclusion and Discussion
Conclusion: A Resolution to the ostensible tension between non-deep double descent and statis- tical intuition. We demonstrated that existing experimental evidence for double descent trees, boosting and linear regression does not contradict the traditional notion of a U-shaped complexity- generalization curve: to the contrary, we showed that in all three cases, there are actually two independent underlying complexity axes that each exhibit a standard convex shape, and that the observed double descent phenomenon distinct mechanisms of increasing the total number of model parameters. Furthermore, we highlighted that when we plot a measure of the effective, test-time, parameter count (instead of raw parameters) on their x-axes, the apparent double descent curves indeed fold back into more traditional U-shapes.
direct consequence of transitioning between these two
What about deep double descent? In this work, we intentionally limited ourselves to the study of non-deep double descent. Whether the approach pursued in this work could provide an alternative path to understanding double descent in the case of deep learning arguably its most prominent setting- - is thus a very natural next question. It may indeed be instructive to investigate whether there also exist multiple implicitly entangled complexity axes in neural networks, and whether this may help to explain double descent in that setting. In particular, one promising approach to bridging this gap could be to combine our insights of Sec. 3 with the known connections between random feature models and two-layer neural networks [SGT18), and stochastic gradient descent and min- norm solutions [WWB+17 17]. We consider this fruitful and non non-trivial direction for future research.
What are the practical implications of these findings? On the one hand, with regards to the specific ML methods under investigation, our empirical results in Sections anndi and Jimply interesting trade-off's between the need for hyperparameter tuning and raw model size. All methods appear to have one hyperparameter axis to which error can be highly sensitive pleaf phoost and PPC while along the other axis, "bigger is better" (or at least, not worse). In fact, it appears that the higher pens or per, the less sensitive the model becomes to changes along the first axis. This may constitute anecdotal evidence that the respective first axis can be best understood as train-time bias-reduction axis- - it controls how well the training data can be fit (increasing parameters along this axis reduces underfit- ting- only when set to its maximum can interpolation be achieved). The second axis, conversely, appears to predominantly achieve pariance-reduction at test-time: decreases ||((z)) II. reducing the impact of noise by smoothing over more training examples when issuing predictions for unseen inputs.
On the other hand, our results in Sec. 4 suggest interesting new avenues for model selection more generally, by highlighting potential routes of redemption for classical criteria trading off in-sample performance and parameter counts (e.g. [Aka74] [Ma733] - which have been largely abandoned in ML in favor of selection strategies evaluating held-out prediction error [Ras18]. While criteria based on raw parameter counts may be outdated in the modern ML regime, selection criteria based on effective parameter counts jest used on a test-set could provide an interesting new alternative, with the advantage of not requiring access to labels on held-out data, unlike error-based methods. In Appendix F.5) we provide anecdotal evidence that when choosing between models with different hyperparameter settings that all achieve zero training error, considering each model's p could be used to identify a good choice in terms of generalization performance: we illustrate this for the case of gradient boosting where we use pi to choose additional hyperparameters. Investigating such approaches to model selection more extensively could be another promising avenue for future work.
10

---

Acknowledgements
We would like thank Fergus Imrie, Tennison Liu, James Fox, and the anonymous reviewers for insightful comments and discussions on earlier drafts of this paper. AC and AJ gratefully acknowledge funding from AstraZeneca and the Cystic Fibrosis Trust respectively. This work was supported by Azure sponsorship credits granted by Microsoft's s Al for Good Research Lab.
References
[ACHL19]
Sanjeev Arora, Nadav Cohen, Wei Hu, and Yuping Luo. Implicit regularization in deep matrix factorization. Advances in Neural Information Processing Systems, 32, 2019.
[Aka74]
Hirotugu Akaike. A new look the statistical model identification. IEEE transactions on automatic control, 19(6):716 (0000:16--233: 723, 1974.
[AP20]
Ben Adlam and Jeffrey Pennington. Understanding double descent requires a fine- grained variana decomposition. Advances in neural information processing sys- tems, 33:1 13:11022-11022 10022, 2020.
[ASS20]
Madhu Advani, Andrew M Saxe, and Haim Sompolinsky. High-dimensional dynamics of generalization error in neural networks. Neural Networks, 132:428 446, 2020.
[Bel21]
Mikhail Belkin. Fit without fear: remarkable mathematical phenomena of deep learning through the prism of interpolation. Acta Numerica, 30:203-22 228, 2021.
[BFSO84]
Leo Breiman, Jerome Friedman, Charles J. Stone, and R.A. Olshen. Classification and Regression Trees. Chapman and Hall/CRC, 1984.
[BH89]
Pierre Baldi and Kurt Hornik. Neural networks and principal component analysis: Learning from examples without local minima. Neural networks, 2(1):53-58, 1989.
[BHMM19]
Mikhail Belkin, Daniel Hsu, Siyuan Ma, and Soumik Mandal. Reconciling modern machine-learning practice and the classical bias-variance trade-off. Proceedings of the National Academy of Sciences,
2019.
[BHX20] Mikhail Belkin, Daniel Hsu, and Ji Xu. Two models of double descent for weak features. SIAM Journal on Mathematics of Data Science, 2(4): 167-1188, 2020.
[BLLT20] 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):30063- 30070, 2020.
[BM21] Sebastian Buschjäger and Katharina Morik. There is no double-descent in random forests. arXiv preprint vrXiv:2111.04400 2021.
[BMM18]
Mikhail Belkin, Siyuan Ma, and Soumik Mandal. To understand deep learning we need to understand kernel learning. In International Conference on Machine Learning, pages 541-549. PMLR, 2018.
[BO%6]
Siegfried Bös and Manfred Opper. Dynamics of training. Advances in Neural Informa- tion Processing Systems, 9, 1996.
[Bre01]
Leo Breiman. Random forests. Machine learning, 45:5-32, 2001.
[CJ09]
Jorge Cadima and lan Jolliffe. On relationships between uncentred and column-centred principal component analysis. Pakistan Journal of Statistics, 25(4), 2009.
[CL21] Niladri S Chatterji and Philip M Long. Finite-sample analysis of interpolating linear classifiers in the overparameterized regime. The Journal of Machine Learning Research, 22(1) (2(1):572--5750, 2021.
[CMBK21] Lin Chen, Yifei Min, Mikhail Belkin, and Amin Karbasi. Multiple descent: Design your own generalization curve. Advances Neural Information Processing Systems, 84:8898-8912. 2021.
[DB22] Yehuda Dar and Richard G Baraniuk. Double double descent: on generalization errors in transfer learning between linear regression tasks. SIAM Journal Mathematics of Data Science, 4(4):1447-1472, 2022.
[DFO20] Marc Peter Deisenroth, Aldo Faisal, and Cheng Soon Ong. Mathematics for machine learning. Cambridge University Press, 2020.

---

[DLM20] Michal Derezinski, Feynman T Liang, and Michael W Mahoney. Exact expressions for double descent and implicit regularization via surrogate random design. Advances in neural information processing systems, 33:5152-515 5264444 2020.
[DMB21] Yehuda Dar, Vidya Muthukumar, and Richard G Baraniuk. A farewell to the bias- variance tradeoff? overview of the theory of overparameterizze machine learning. arXiv preprint arXiv:2 02355, 2021.
[DMLB20] Yehuda Dar, Paul Mayer, Lorenzo Luzi, and Richard Baraniuk. Subspace fitting meets regression: The effects of supervision and orthonormality constraints on double descent gencralization errors. In International Conference on Machine Learning, pages 2366-2311 PMLR, 2020.
[dRBK20] Stéphane d' Ascoli, Maria Refinetti, Giulio Biroli, and Florent Krzakala. Double trouble in double descent: Bias and variance (s) the lazy regime. In International Conference on Machine Learning, pages 2280-22909 PMLR, 2020.
[DSYW20] Raaz Dwivedi, Chandan Singh, Bin Yu, and Martin Wainwright. Revisiting complexity and the bias-variance tradeoff. arXiv preprint arXiv:2006. 10189, 2020.
[Dui95]
Robert PW Duin. Small sample size generalization. In Proceedings of the Scandinavian Conference on Image Analysis, volume 2, pages 957-964. Citeseer, 1995.
[Eub84]
RL Eubank. The hat matrix for smoothing splines. Statistics & probability letters, 2(1):9-14, 1984.
[FM23]
Ronald A Fisher and Winifred A Mackenzie. Studies in crop variation. ii. the manurial response of different potato varieties. The Journal of Agricultural Science, 13(3):311- 320, 1923.
[GBC16] Ian Goodfellow, Yoshua Bengio, and Aaron Courville. Deep learning. MIT press, 2016.
(GBD92] Stuart Geman, Elie Bienenstock, and René Doursat. Neural networks and the bias/variance dilemma. Neural computation, 4(1):1-58, 1992.
[GVL13] Gene H Golub and Charles F Van Loan. Matrix computations. JHU press, 2013.
[GWB+ 17] Suriya Gunasekar, Blake Woodworth, Srinadh Bhojanapalli, Behnam Neyshabur, and Nati Srebro. Implicit regularization in matrix factorization. Advances in Neural Information Processing Systems, 30, 2017.
(HB21] Like Hui and Mikhail Belkin. Evaluation of neural architectures trained with square loss vs cross-entropy in classification tasks. International Conference on Learning Representations (ICLR), 2021.
[HMRT22] Trevor Hastie, Andrea Montanari, Saharon Rosset, and Ryan J Tibshirani. Surprises in high-dimensional ridgeless least squares interpolation. The Annals of Statistics, 50(2):949-986, 2022.
[Hot57] Harold Hotelling. The relations of the newer multivariate statistical methods to factor analysis. British Journal of Statistical Psychology, 10(2):69-79, 1957.
[HT90] Trevor Hastie and Robert Tibshirani. Generalized additive models. Monographs statistics and applied probability. Chapman & Hall, 43:335, 1990.
[HTF09] Trevor Hastie, Robert Tibshirani, and Jerome H Friedman. The elements of statistical learning: data mining, inference, and prediction, volume 2. Springer, 2009.
[HXZQ22) Zheng He, Zeke Xie, Quanzhi Zhu, and Zengchang Qin. Sparse double descent:
Where network pruning aggravates overfitting. International Conference on Machine Learning, pages 8635-8659. PMLR, 2022.
[Jo182]
Ian T Jolliffe. A note on the use of principal components in regression. Journal of the Royal Statistical Society Series C: Applied Statistics, 31(3):300-300 1982.
[Ka196]
Dan Kalman. A singularly valuable decomposition: the svd of a matrix. The college mathematics 27(1):2-23, 1996.
[Ken57)
Maurice G Kendall, A course in multivariate analysis: London. Charles Griffin & Co. 1957.
[KH+09]
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. 2009.
12

---

[KL16]
Jesse H Krijthe and Marco Loog. The peaking phenomenon in semi semi-supervised learning. In Structural, Syntactic, and Statistical Pattern Recognition: Joint IAPR International Workshop, S+ SSPR 2016, Mérida, Mexico, November 29-December 2, 2016, Proceed- ings, pages 299-309. Springer, 2016.
[KSR 21] Uia Kuzborskij, Csaba Szepesvári, Omar Rivasplata, Amal Rainen-Triki, and Razvan Pascanu. On the role of optimization in double descent: A least squares study, Advances in Neural Information Processing Systems, 34:29567-225777 2021.
[LBBH98] Yann LeCun, Léon Bottou, Yoshua Bengio, and Patrick Haffner. Gradient-based learning applied document recognition. Proceedings of the IEEE, 86(11):2278-2322 1998.
[LD21] Licong Lin and Edgar Dobriban. What causes the test error? going beyond bias-variance via anova. The Journal of Machine Learning Research, 22(1):6925-700 --00,, 2021.
[LDB21] Lorenzo Luzi, Yehuda Dar, and Richard Baraniuk. Double descent and other interpola- tion phenomena in gans, arXiv preprint arXiv:2 040000 2021.
[LVM*200 Marco Loog, Tom Viering. Alexander Mey, Jesse H Krijthe, and David MJ Tax. A brief prehistory of double descent. Proceedings of the National Academy of Sciences, 117220):1022-10622 2020.
[Mac91]
David MacKay. Bayesian model comparison and backprop nets. Advances in neural information processing systems, 4, 1991.
[Ma173]
Colin L Mallows. Some comments on cp. Technometrics, 42(1))87-94, 1973.
[MBB18]
Siyuan Ma, Raef Bassily, and Mikhail Belkin. The power of interpolation: Understand- ing the effectiveness of sgd in modern over-parametriiee learning. In International Conference on Machine Learning, pages 3325-3334. PMLR, 2018.
[MBW20] Wesley Maddox, Gregory Benton, and Andrew Gordon Wilson. Rethinking pa- rameter counting in deep models: Effective dimensionality revisited. arXiv preprint arXiv:2003.02139, 2020.
[MNS*21] Vidya Muthukumar, Adhyyan Narang, Vignesh Subramanian, Mikhail Belkin, Daniel Hsu, and Anant Sahai. Classification regression in overparameteriized regimes: Does the loss function matter? The Journal of Machine Learning Research, 22(1):10104- 10172, 2021.
[Moo91]
John Moody. The effective number of parameters: An analysis of generalization and regularization in nonlinear learning systems. Advances in neural information processing systems, 4, 1991.
[Mur22]
Kevin Murphy. Probabilistic machine learning: an introduction. MIT press, 2022.
[Nea19]
Brady Neal. On the biri-nari tradeoff: Textbooks need an update. arXiv preprint arXiv:111..08286, 2019.
[NKB+21] Preetum Nakkiran, Gal Kaplun, Yamini Bansal, Tristan Yang, Boaz Barak, and Ilya Sutskever. Deep double descent: Where bigger models and more data hurt. Journal of Statistical Mechanics: Theory and Experiment. (02 2021.
[NMB+18] Brady Neal, Sarthak Mittal, Aristide Baratin, Vinayak Tantia, Matthew Scicluna, Simon Lacoste-Julien, and loannis Mitliagkas. A modern take on the bias-variance tradeoff in neural networks. arXiv preprint / 2018
[NTS14] Behnam Neyshabur, Ryota Tomioka, and Nathan Srebro. In search of the real in- ductive bias: On the role of implicit regularization in deep learning. arXiv preprint 41Xiv:1412.661 2014.
[NWC+1D 11] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. Reading digits in natural images with unsupervised feature learning. 2011.
[PeaO1]
Karl Pearson. Liñ. on lines and planes of closest to systems of points in space. The London, Edinburgh, and Dublin philosophical magazine and journal of science, 2(11):559-577 572, 1901.
[PKB19] Tomaso Poggio, Gil Kur, and Andrzej Banburski. Double descent the condition number. arXiv preprint arXiv:1912.061999 2019.
13

---

[PVG+11]
F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blon- del, P. Prettenhofer, R. Weiss. Dubourg, J. Vanderplas, A. Passos, D. Coumapeaau M. Brucher, M. Perrot, and E. Duchesnay. Scikit-learn: Machine learning in Python. Journal of Machine Learning Research, 12:2825-2830, 2011.
[Ras18]
Sebastian Raschka. Model evaluation, model selection, and algorithm selection in machine learning. arXiv preprint arXiv: 12808, 2018.
[RD98]
Sarunas Raudys and Robert PW Duin. Expected classification error of the fisher linear classifier with pseudo-inverse covariance matrix. Pattern recognition letters, 19(5- 6):385-392, 1998.
[RT19]
From fixed-x to random-x regression: Bias- variance decompositions, covariance penalties, and prediction error estimation. Journal of the American Statistical Association, 2019.
Saharon Rosset and Ryan J Tibshirani.
[Sch78]
Gideon Schwarz. Estimating the dimension model. The annals of statistics, pages 461-464, 1978.
[SD96]
Marina Skurichina and Robert PW Duin. Stabilizing classifiers for very small sample sizes. In Proceedings of 13th International Conference Pattern Recognition, volume pages 891-896. IEEE, 1996.
[SGd 18] Stefano Spigler, Mario Geiger, Stéphane d' Ascoli, Levent Sagun, Giulio Biroli, and Matthieu Wyart. A jamming transition from under-to wer-parametrizatioon affects loss landscape and generalization. arXiv preprint arXiv: 09665, 2018.
[SGT18] Yitong Sun, Anna Gilbert, and Ambuj Tewari. On the approximation properties of random relu features. arXiv preprint arXiv: 1oXXv:/810004374 2018.
[SKL92]
Jon M Sutter, John H Kalivas, and Patrick M Lang. Which principal components to utilize for principal component regression. Journal of chemometrics, 6(4):217-225, 1992.
[THV22]
Ningyuan Teresa, David W Hogg, and Soledad Villar, Dimensionality reduction, reg- ularization, and generalization in overparameterizee regressions. SIAM Journal Mathematics of Data Science, 4(1):126-152) 2022.
[Tuk77]
John Tukey. Exploratory data analysis, volume 2. Reading, MA, 1977.
[Vap95]
Vladimir Vapnik. The nature of statistical learning theory. Springer science & business media, 1995.
[VCR89]
F Vallet, J-G Cailton, and Ph Refregier. Linear and nonlinear extension of the pseudo- inverse solution for learning boolean functions. Europhysics Letters, 9(4):315, 1989.
[VL22]
Tom Viering and Marco Loog. The shape of learning curves: review. IEEE Transac- tions on Pattern Analysis and Machine Intelligence, 2022.
[WRR03]
Michael E Wall, Andreas Rechtsteiner, and Luis M Rocha. Singular value decomposition and principal component analysis. A practical approach to microarray data analysis, pages 91-109, 2003.
[WW75]
Grace Wahba and Svante Wold. A completely automatic french curve: fitting spline functions by cross validation. Communications in Statistics-Theory and Methods, 4(1):1 17, 1975.
14

---

Appendix
This Appendix is structured as follows: In Appendix A we present an additional, broader, literature review. In Appendix [B] we present additional background on the linear regression case study, including the proof of Proposition (Appendix [B2) and empirical study of the effect of excess features on the conditioning of PC feature matrices (Appendix B.3). In Appendix [ we present additional background prediction error in fixed design settings (Appendix c.2) and derivation of the smoothing matrices associated with linear regression, trees and boosting (Appendix C.3) In Appendix D
smoothers, including analysis of the impossibility of double descent in
we present additional background and other definitions of effective parameter measures. Finally, in Appendix E we further discuss the experimental setup and close by presenting additional results.
A Additional literature review
Double descent as a phenomenon, Although double descent only gained popular attention since
[BMMM19 influential paper on the topic, the phenomenon itself had previously been observed:
LVM+20 provide a historical note highlighting that [VCR89] may have been the first to demonstrate
double descent in min-norm linear regression; [BHMM19] themselves note that double descent-like
phase transitions in neural networks had previously been observed in [B0% ASS20 NMB + 18
1G). As discussed above, in addition to linear regressions and neural networks, [BHMM19]
also present double descent curves for trees and boosting. Since then, a rich literature on other
deep double descent phenomena has emerged, including double descent in the number of training
epochs| [NKB+ 21], sparsity [HXZQ22], data generation [DB22]] and transfer learning [D222 We also note that the occurrence of double descent has been studied for subspace regression methods themselves [DMLB20 THV22), but has not been linked to double descent in min-norm linear
regressions as we do here. For a recent review of double descent more broadly see [VL222]
Theoretical understanding of double descent. In addition to the studies of double descent in linear regression discussed in the main (ex((ASS0) BLLT2,, M2, BHX20 KSR 21 HMRT22), we note that further theoretical studies of double descent in neural networks exist (see c.g. [DMB2]] for
comprehensive review). These mainly focus exact expressions of bias and variance terms by taking into account all sources of randomness in model training and data sampling (NMB + 18 AP20
dRBK20 LD2I]. Finally, different to our peak-moving experiments in Sec. 3.2 and Appendix E.2 which show that the location of the second descent in all original non-deep experiments of [BHMMI9 is determined by a change in the underlying method training procedure, [CMBK21) show that one can "design your own generalization curve" in linear regression by controlling the data-generating process through the order by which newly (un)informative features are revealed, meaning that one could construct a learning curve with essentially arbitrary number of descents in this way. Similarly. we show in Fig. 6(b) in the main text and Fig. 13 in Appendix [E.2 that multiple peaks can be achieved by switching between mechanisms for adding parameters multiple times. Note that [CMBK21] consider only the effect of data- eetta-genrratig mechanisms and arrive at the conclusion that the generalization curves observed in practice must arise due to interactions between typical data-generating processes and inductive biases of algorithms and "highlight that the nature of these interactions is far from understood" [CMBK2I] p. 3] with our paper, we contributed to the understanding of these interactions by studying the role of changes in inductive biases in the case of trees, boosting and linear regression.
Interpolation regime. Entangled in the double descent literature is the interpolation regime or the benign overfitting effect (e.g. [BMM18 [BB18] 2L CL.2T). That is, the observation that models with near-zero training еттог can achieve excellent test set performance. This insight was largely motivated by large deep learning architectures where this is commonplace [MBB (IBBI8), While this line of research does provide an important update historic intuitions which linked perfect train set performance with poor generalization, it is entirely compatible with the ideas presented in this work. In particular, in Figure 20 we demonstrate that within the interpolation regime the number of effective parameters used on test examples and the predictive performance on those test examples can vary greatly. Therefore, benign overfitting may indeed result in excellent performance without contradicting the traditional notion of a U-shaped complexity curve. Additionally, note that while the double descent phenomenon is often presented as a consequence of benign overfitting in the interpolation regime, we show in Appendix E.2 that the location of the second descent is not
15

---

inherently linked to the interpolation regime at all in the non-deep experiments of [8НMМ1 but rather consequence of the point of change between multiple mechanisms of increasing parameter count.
Other related works. Finally, briefly discuss some other works that might provide further context on topics touched upon in this text. [BH89 study linear neural networks through the lens of principal component analysis. Recent theoretical work suggests that, when optimized using stochastic gradient descent, these networks tend to converge to low norm or rank solutions (e.g. [GWB 17 ACHLI9)). Aspects of double descent, which were referred as peaking in older literature, have been associated with the eigenvalues of the sample covariance matrix in limited setting involving linear classifiers as far back as [RD98]. Much of this work focused on increasing the number of samples for fixed model (e.g. [ui95] (D Prior to being rediscovered in the context of neural networks and larger models, more recent work investigated the peaking phenomenon in modern machine learning settings such as semi-supervised learning [KL16]]
B More on linear regression
In this section, we first present a brief refresher on SVD, PCA and PCR to provide some further background to the discussion in the main text and the following subsections. We then present a proof of Proposition I in Appendix B.2 and finally empirically analyze the effects of excess features on the conditioning of the PCR feature matrix in Appendix B.3
B.1 Background on SVD, PCA and PCR
In this section we provide brief refresher on some of the mathematical tools that are fundamental to the insights presented in the main text. We begin with the singular value decomposition (SVD) which acts as generalization of the standard eigendecomposition for non-square matrix X E RRad (see e.g. [Ka196] DFO20). The SVD consists of the factorization X UEVT where the columns of U E x and rows of V E dRd consist of the left and right singular vectors of X respectively and both form orthonormal bases of X. Then, Σ E i contains the so-called singular values σ 2 2 minu(n.d) along the diagonal with zeros everywhere else. Analogous to eigenvalues and eigenvectors. the SVD satisfies XV, o, U, for all I..... min(n,d) d). We note that for any c 0, the corresponding V, lies in the nullspace of X (while U, lies in the nullspace of X²). The SVD results in the geometric intuition of factorizing the transformation X into three parts consisting of basis change in Rd, followed by scaling by the singular values that adds or removes dimensions, and then a further basis change in R". We note that any columns U and V corresponding to either null singular values (i.e. o; 0) or the max(n, d) min(n, d) non-square dimensions of X are redundant in the SVD. Therefore we can equivalently express the SVD its so-called compact form with these vectors and their corresponding rows/columns in Σ removed.
The SVD is intimately linked to dimensionality reduction through principal component analysis (PCA) [PeOOl FM23 [RR03]. Recall that PCA is a technique that finds a basis of a centered matrix X by greedily selecting each successive basis dimension to maximize the variance within the data. Typically, this is presented as selecting each basis vector b; = arg max bll=1 || where X; denotes the original (centered) data matrix X with the first i 1 directions of variation removed (i.e. X, = - bgb(X) X). By expanding ||&bb|/ = b7 XT we can notice that the basis vectors obtained are also the eigenvectors of X which is proportional the sample covariance matrix. The dimensionality reduction then occurs by selecting subset of these new coordinates, ordered by highest variance, to represent a low-rank approximation of The relationship to the SVD is illuminated by noticing that, for centered X, we can use the singular value decomposition such that
x=== (UXVV) =
EVT -
This reveals that V, the orthonormal basis containing right singular vectors of X and obtained through the SVD, produces exactly the eigenvectors of X X required for PCA. Then the PCA operation PC PCAA( gaxd + paxk (where k d is the user-defined number of principal components
16

---

retained) may be obtained as (X) the subseript of each matrix denotes keeping only the vectors corresponding to those first principal components (ordered according to the magnitude of their singular values).
= =V== where we overload notation such that
A natural idea that emerges from the description of PCA is to apply it in the supervised setting. Specifically, we might wish to first perform the unsupervised dimensionality reduction step of PCA followed by least squares linear regression on the transformed data. This is exactly the approach taken in principal component regression (PCR) [Ken57 Ho157]. Mathematically this can be expressed as solving 3 = min (y - xV for coefficients B E I and targets y E R.. Then the least squares solution takes the form 3 (Vīx V The assumption of PCR is that the high variance components are most important for modeling the targets y. While this is not necessarily always the case [Jo122], PCR has historically been important method in the statistician's 's toolbox (e.g- (HTF09)) In the main text we make use of the connection between PCR and min-norm least squares on underdetermined problems (i.e. fat data matrix). In particular,
show that
applying min-norm least squares in this setting is equivalent to applying PCR with all principal components retained. We provide a proof for this proposition in Appendix B.2 Of course, related mathematical connections between min-norm solutions and the singular value decomposition have been made in previous work (see e.g. [GVL13 Ch. 5.7J). The regularization effect of PCR also has known connection to ridge regression where both methods penalize the coefficients of the principal components [HTF09 Ch. 3.5.1]. The former discards components corresponding the smallest singular values while the latter shrinks coefficients in proportion to the size of the singular values
B.2 Proof of Proposition
Proposition 1. [Min-norm least squares as dimensionality reduction.] For a full rank matrix X Raxd with n d and vector of targets y E R", the min-norm least squares solution gMN {ming || XB =y} and the least squares solution GSVD {B: BB y} using the matrix of basis vectors B E _R="", constructed using the first n right singular vectors of X, are equivalent; i.e. xT BMN b 3SVD for all x E IRd and corresponding basis representation b = b(x).
Proof. We will use the compact singular value decomposition = UEVT (i.e. with the redundant column vectors dropped from the full Σ and V). Specifically, the columns of U E g=** diagonal matrix with the singular
and V Raxd form orthonormal bases and Σ E Ruxn values along the diagonal. The transformation of X to B is then given by XV = UE- B. It is sufficient to show that for some test vector x E Rd the original data space and its projection to the reduced basis space b VTx E R", then the predictions ý of both models are equal such that xT BMN bT GSVD
1 MN = xT = -XXX(XX")
= "(("
-UEV"""
(BB))
= =b"BJ (OBT)-
SSVD
Indeed, an alternative approach is to standard variable selection techniques the constructed dimensions of the transtormed data (see e.g. [SKL92)..
'This connection explains why the explicit regularization with the ridge penalty in [HMRT22] and the implicit regularization of min-norm solutions have consistent shrinking effect test loss.
17

---

Singular values dn
Condition number K R(BB)
150
po 10000
1.5
12.5
po 12500
5.0
Is (Bx))
10.0
pe 15000
(og(
2.5
10000
p
pd 12500
7.5
p 30000
0.0
15000
p 60000
-2.5
20000
pe 50000
55.0
60000
2000
6000
10000
6000
8000
Figure 10: The effect of pd on the conditioning of the PCR feature matrix. Singular values os (left) and x(Be) (right) derived from the random Fourier feature matrix O as a function of k and for different raw number of features pd.
B.3 Understanding the impact of pes; Examining its impact singular values of the PCR feature matrix
In this section, we empirically investigate how increasing pew for a fixed number of PPC results in gradual improvement in the quality of basis of fixed dimension, revisiting the experimental setting of Sec. 3.2 in the main text.
In particular, we consider how excess features affect the conditioning of the feature matrix B₃ PX) = XVr UgEis. used in principal components regression, for different values of k = PPC, As noted in [PKB19], the condition number x( x(A) of matrix A measures how much errors in
(A) y impact solutions when solving system equations A 3 y. and is given by Ks (A) amiul the ratio maximal to minimal singular value A. Because in principal components regression B is constructed from the top & E {1..... n) principal components, it easy to see that m (BB) 01 and Omin Bg] = 0x the largest and k-th largest singular value of respectively (as defined in Appendix B.1 so that in principal components regression generally have [Ba) 01
To understand how the raw number of features p6 the experimental setup of Sec. 3.2 in the main text impacts basis quality, it is thus instructive to study the behavior of the singular values of the random Fourier feature matrix as pd grows. In Fig. 10 we therefore plot σ and k< x(B;)) for different values of p and observe that indeed, as pô (and thereby pez pd k:) increases, dg substantially increases in magnitude especially for large k == =PCC, This provides empirical evidence that the conditioning of feature matrices for principal components regression at large values of indeed substantially improves as we add excess raw features (i.e. x(B;) decreases substantially- particularly at large as can seen the right panel of Fig. 10
C More on smoothers: Bias-variance, on the impossibility of in-sample double descent and derivation of smoothing matrices
In this section, we give some further background on the well-known relationship between bias and variance in smoothers, then discuss the impossibility of double descent in prediction error in fixed design settings, and finally derive the smoothing matrices implied by the MI. methods used in the main text.
C.1 Background: Bias and variance in smoothers
In this section, we discuss the well-known bias-variance relationship in smoothers (which indeed determines the U-shape of their original complexity curves), following the discussion in (HT90 Sec. 3.3]. Under the standard assumption that targets are generated with true expectation (*(a)) and homoskedastic variance o², the bias and variance of a smoother 5(-) evaluated at test point zo (for
18

---

fixed input points {ai Hez. and fixed smoother s(-)). can be written as:
Bias(f f. z0) = f (xx0) DieI... ff Var (f, x0)) Var(5(=o))vmin)) = [|s(20))
(3)
(4)
Note that some of the historical intuition behind the U-shaped bias-variance tradeoff with model complexity on the x-axis appears to lead back to exactly the comparison between these two terms evaluated for training inputs in smoothers [[ trace explieit discussion of bias-variance tradeoff back to at least [HT90] (who indeed discuss it in the context of smoothers), preceding [GBD92]'s s influential machine learning paper on the topic. A bias-variance tradeoff is easily illustrated by considering e.g. a KNN smoother
1 a INN estimator has no bias when predicting outcomes for training input but variance o², while k(> 1)NN estimator generally incurs some bias but has variance o² / we thus expect a U-shaped curve in squared prediction error as we vary k Similarly, note that for linear regression on a p < n-dimensional subset of the input, the bias of the fit generally decreases in p. while the variance increases in p as 1 >i= Var($(z;))
pa? HTTF9
leaddin to
another well-known example of a U-shaped generalization curve (in p < n)).
When the expected mean-squared error (MSE) is the loss function of interest, bias variance tradeoff can also be motivated more explicitly by noting that the MSE can be decomposed
Ei(Y - f(xo)) = mo] = o² + Bias (f,0)) + Var(f,
(5)
C.2 On the impossibility of second prediction error descent in the interpolation regime in fixed design settings
[BHMM19] provide a discussion of possible cultural and practical reasons for the historical absence of double descent shapes in the statistics literature. They note that observing double descent in the number of parameters requires parametric families in which complexity can arbitrarily be controlled and that therefore the classical statistics literature- - which either focuses either on linear regression in fixed p n settings or considers highly flexible nonparametric classes but then applies heavy regularization could not have observed it because of this cultural focus on incompatible model classes (in which [BHMMI9] argue double descent cannot emerge due to a lack of interpolation). Through our investigation, we find another fundamental reason for the historical absence of double descent shapes in statistics: even when using sufficiently flexible parametric class (e.g. unregularized RFF linear regression), a second descent in the interpolation regime cannor emerge in fixed design settings, the primary setting considered in the early statisties literature where much of the intuition regarding the bias-variance tradeoff was initially established.
After recalling some definitions in Appendix C.2.1 demonstrate this impossibility of second descent in fixed design settings for general interpolating predictors in Appendix C.2.2 below, and make some additional observations specific smoothers in Appendix C.2.3
C.2.1 Preliminaries.
We begin by recalling the definition of the fixed design setting of statistical learning. Definition 2 (Fixed design setting). In the fixed design setting, the inputs .1,...,24 Fn are deterministic, while their associated targets are random (e.g. Yi = f2x)) + c where & is a random noise term).
The fixed design setting was a core consideration of much of the statistical literature RT19 and was suitable for several traditional applications in e.g. agriculture. While many modern applications require a random design setting which the inputs are also random, several modern applications are still suitably modeled within this framework (e.g. image denoising). Next, we will define in in-sample prediction error in line with [HTH09.
Definition 3 (In-sample prediction error). Given a set of fixed design points I1,..., En, training targets y Un and some model f, suppose we observe new set of random responses at each of
RRcall that, possibly counterintuitively, a KNN smoother is most complex when I 1. where at every training input the prediction is simply the original training label, and least complex when & = n. where it just outputs sample average
19

---

the training points denoted v.. Then the expected in-sample prediction error for some loss function given by
ERR - Σ n (())) (Fn, DnlH
Remark:
Note that in the fixed design setting, the expected in-sample prediction error is indeed the natural quantity of interest test time.
Finally, we define an interpolating predictor below.
Definition 4 (Interpolating predictor.). A predictor f()) interpolates the training data if for yitin I. Vi E Tnain
f(z;)) = Vi train
(6)
C.2.2 Main result: General impossibility second descent in test error for the interpolation regime in fixed design settings
We may now proceed to the main observation of this section. That is, in the fixed design setting second descent in test error observed in the interpolation regime cannot occur. Intuitively, this is because any improvement in fixed-design test-time performance by more complex model would require sacrificing the perfect performance on the train set. As a consequence, while as we observe in the main text different interpolating predictors can have wildly different (out-of-sampll generalization performance, we show below that all models in the interpolation regime have identical expected in- in-sample prediction error ERRi. That is, increasing the number of parameters p past n, e.g. in min-norm linear regression, does not and can not lead to a second descent in ERRin. We express this more formally below.
Proposition 2 (Impossibility of second error descent in the interpolation regime for fixed design settings.). Suppose we observe inputs 21,..., Th in a fixed design prediction problem, with associated random labels yituin ..... Un train in the training set. For all interpolating models test-time predictions will be identical and, therefore, a second descent in ERR in this regime is impossible.
Proof. By definition of fixed design problems, our test set consists of examples in which the features
duplicates from the training set and the targets new realizations from some target distribution.
Then the test dataset consists of the pairs (I y/ ) (In, y/aa). For any interpolating model f .....
we can calculate the test loss Clest E. ((f())), ((2:).))==)) 1). But by Definition 4 (and because know that f(x::)
interpolating models achieve zero training error),
y Irain Thus L
El= C(ybrinn ), and since this is not function of f. this quantity is independent of the number of parameters (or any other property) of f- Therefore, any change in Lest (or expectations thereof) in
the interpolation regime is impossible- including the second descent necessary for creating double descent shape.
While most, if not all, discussion of the double descent phenomenon in the ML literature is not within the fixed design setting, believe that the impossibility of double descent in this setting provides new useful partial explanation for its historical absence from the statistical discourse.
C.2.3 Additional observations specific smoothers
For the special case of interpolating linear smoothers, we make an additional interesting observation with regard to their smoothing weights and implied effective number of parameters. To do so, first recall that a linear smoother defined as follows:
Definition 5 (Linear smoother). A smoother with weights $(xo) : X Vtrain) ) is linear if 8(x)) does not depend on Ymain that is S(Zo; X y ' ) S(In: X y² for Vy . E IR"
We are now ready to show in Prop. that all interpolating linear smoothers must have the same smoother weights and effective parameters for training inputs.
Proposition 3 (Interpolating linear smoother.). Any interpolating linear smoother must have identical smoother weights $(x;) = e; for all E Tamin- This immediately implies also that all interpolating linear smoothers use the same effective number of parameters Pe in fixed design settings.
20

---

Proof. In linear smoothers, ((z;) can not depend on Yusin by definition. To have ((z;)y = y for all i Irrain and any possible training outcome realization V'rain
R we must have $(1;) e; for
i Tamin-
From this, ||e 12 1, it also follows that paain Pc training and testing inputs are identical so ps
||e|| || In fixed design settings,
Note that this specific property does not hold for more general (non-linear) interpolating smoothers: whenever Strain contains duplicates, non-linear interpolating smoother have ((x4)) * e for some i E Tuain- When all Yi observed at train-time are unique, then it is easy to see that even non-linear interpolating smoothers must have ((x4) e; for all E Tarain-
C.3
Derivation of smoothing weights of linear regression, trees and boosting
C.3.1 Smoothing weights for RFF linear regression
Derivation of the smoothing weights for the RFF linear regression example is trivial, as linear regres-
sion is textbook example of smoother [НTО)]. To see this, let Φ(x0)) = (oi (z()))....,00 (x)))) denote the pd 1 row-vector of RFF-projections of arbitrary admissible 2o R and let
T Pirain = [Ø(x1) )²= ((x,) denote the n x pd design matrix of the training set and note that the least squares prediction obtained through the min-norm solution be written
{ [((x))
2 T L wain) -1 -I train Verain Iruin
if < n
(LR(zz) = @(Z0)LLR = 3 (LR((r0) =
(7)
(x)x)
D train
Prain L I train
Ytrain
if 2 n
i.e.
(xo) [0( ( ( &
trinn train
T train
if P
(8)
(z)) 1 train train
$ T
P 2 n
train
Note also that by design, as alluded in Appendix
C.2.3
when pe > have
Q tran t train ( Prain D-r
train ) I, implying that that g
(I:)
=
e; for any I; observed at train
time.
C.3.2 Smoothing weights for trees and forests
Similarly, we can exploit that trees are sometimes considered adaptive nearest neighbor methods [НTF09) Ch. 15.4.3], i.e. nearest neighbor estimators with an adaptively constructed (outcome- oriented) kernel (or distance measure). To this, note that regression trees, that is trees trained to minimize the squared loss and/or classification trees that make predictions through averaging (not voting), all be understood as issuing predictions that simply average across training instances within terminal leaf. To make this more formal, consider that any tree with pleaf leaves can be represented by pleas contiguous axis-aligned hypercubes 1p. which store the mean outcome of all training examples that fall into this leaf: If we denote by ((xo) the leaf that Øy falls into and
Mi((o)) Dim 1(1(2)) I(x,)) the number of training examples in this leaf, then we have that
f(zo) To((zo)
1(1(20) ((x)))1
giving
grree gtree(xo) (((20))((x11)
1(((x)) = ((x1))
(10)
T(((za)
71((z))
Further, note that sums fr((2r)) EM fm (xo) of smoothers f**(x)) gTh
(x0o)) (aro) train
1, 1...., M are also smoothers with s (T((z)) = MM= sTh (zz). This immediately implies that the tree ensembles considered in Sec. 2211 are also smoothers, and, are boosted trees (and ensembles thereof) as considered in Sec. [.2
show in Appendix C.3.3 below, so
Remark: We note that, although the smooth stree(zp) can be written in linear form without explicit
reference to Yurain trees (and their sums) are not truly linear smoothers because the smoother geree (.)
does depend in its construction on y Yuain. reflecting their epithet as adaptive smoothers [HTF09 Ch.
21

---

15.4.3]. This mainly implies that when calculating bias and variance, we can no longer consider ((r)) as fixed and Eqs. (3) and (4) no longer hold exactly. However, this not an issue for our purposes as we are not interested in actually estimating bias and variance in this work, rather we are interested in smoothers because - as discussed in Sec. and Appendix D they allow us to compute the most useful measure of effective parameters. Conceptually, this allows us to assess the effective amount of smoothing used, which can also be interpreted relative to e.g. a standard KNN estimator. Because for KNN estimators we have p Σ and for trees and forests it holds that > 8' (x())
the quantity 00 2 admits an interesting interpretation as measuring the effective number of nearest neighbors examples have in tree forest (and this interpretation does not require fixed š).
C.3.3 Smoothing weights for boosting
Deriving the smoothing weights for gradient boosting is more involved. To do so, we first re-state the gradient boosting algorithm (as presented in [HTF099] Ch. 10.10) and then recursively construct weights from it.
The gradient boosted trees algorithm. We consider gradient boosting with learning rate r) and the squared loss as :::
1. Initialize fo(x) 0
2. For p E (1,...,pbooo,, pboost]
(a) Fori E {I...., compute
OL(y, [(x:))
Di.p
0f(zi)
(11)
f=fp-1
(b) Fit regression tree to {(x,, st.p) ) Vi=1 giving leaves Lip for j = ,p....
(c) Compute optimal predictions for each leaf j E (1....,,pl) JpJ:
7jp = arg min EER
Σ
L(vi, fp-1(()) + +7) = Mhp x,El,p
Σ - (p-
(12)
E,E4,p
(d) Denote by fp(x)= = Σ 1(x Lip the predictions the tree built in this fashion
(c) Set fp(x) = fp-1(1) (z)++f(()))
3. Output f(x) = f (I)
Recursive construction of smoothing weights. Equation 12 highlights that we can recursively construct smoothing weights similarly as for trees. In fact, note that in the first boosting round, (x) a standard tree with smoothing weights gtree.fi (-) computed as in Eq. (1). so that fi(x) nfi (=)
has smoothing weights gboost.1(.) rret h (-). Now we can recursively consider the smoothing weights associated with newly added residual trees fp(x)) by realizing that its predictions can be written as a function of standard tree weights ftree. and correction depending on shoost, (.) alone:
J 1,(x)= = 1sr E 1
1 fo epp))
Σ j=1
Σ
Σ (v: S fp-1(x=))
Mhs z:Elip
j=1
Jy Σ 1[r j=l
J Σ
V1
1fx E 1opا
gboost (20 (2e)
(13)
Bdpp ni n;Elio
núp z;Elip
Standard tree prediction: g gtree. (x)yerann
Residual correction: geore. (a))
(stroe. fo (x)
(14)
where, using the 1 x Jp indicator vector Cpr()) = .f, E E,,, we have
goort
R!
(15)
22

---

with R the 1p x n. leaf-residual correction matrix with j-th row given by
R
shoost. p- (x:))
(16)
Mlp s:El,
Thus, we have constructed the smoothing matrix for gradient boosting recursively as:
poostt (() gboost.p-11 (.) + n (s) - scomr.5())) (.)
(17)
D More on effective parameters
In what follows, we discuss the different effective parameter definitions considered in the smoothing literature, and follow closely the presentation in [HT90, Ch.3.4 & 3.5] and [HTF09) Ch. 7.5]. Recall that, as discussed Sec. 4 of the main text, these definitions are all naturally calibrated towards linear regression that, case of ordinary linear regression with < n2
might desire, effective and raw parameter numbers equal in the
To understand their motivation, we introduce some further notation. Assume that outcomes are generated as y/ = [*(x) + e with unknown expectation (x) and a zero-mean error term with variance x² Let f* = [f
denote the vector of true expectations. Further, let write the vector of in-sample predictions as f Sniii: For linear smoothers (and/or fixed S), bias and variance at any input point are given by Eqs. 33 and (4), so that we have +o2 Ei bias? (f(x)) = bb by for bias vector bg = (f" Sf and > var(f(x;)) = o² (SST))
S = [=(2z)) ..... $(x,,) 771 denote the smoother matrix for all input points, that
Covariance- effective parameter definition. In this setup, one way of defining the effective number of parameters that is very commonly used consider the covariance between predictions f(z;) and the observed training label yı [HTF09]
n i=
cor f(x.)) tr())
Cov Pe
(18)
As expected, tr($) = p in ordinary linear regression (p < n).
Error-based effective parameter definition. Another way considers the residual sum of squares (RSS) in the training sample RSS((f) Ei= f(x,))² (Yeroin Sytrainn (Ytrain Sytrain) and notes that has expected value:
B(RSS(F) = (n - tr(2$ (S"))'" + bs
(19)
and uses
n1 pe because in the linear regression case the degrees of freedom for error p [H990] and tr(2$ SST) =p
= pem==m
tr(2$ SST)
(20)
basedd effective parameter definition. Finally, the variance- based definition Pa discussed in the main text is motivated from Σm= var(f(x:) = = Σm [|8(x;)]| (SST" giving
Pe = pr. ($$
(21)
as Σ var(f(x.) = 2 in linear regression.
Note that, in ordinary linear regression with p < n and full rank design matrix, $ is idempotent so that tr(ST) tr($) = tr(2.- SST) = rS) p.
Why did we choose p We chose to adapt p. because it is the definition that can most obviously be adapted to out-of-sample settings: both the error-based definition and the covariance-based definition focus on the effect training outcome has in predicting itself (i.e. overfitting on the own label), while for out-ol-sample prediction, this not of interest. Instead, we therefore rely on the variance- baasnd definition because ||( can not only be computed for every input zo but also
23

---

admits meaningful interpretation as measuring the amount of smoothing over the different training
examples: for an averaging smoother with Σi=1 s (2o) 1. the simplest and smoothest prediction
a sample average with & (2o) = which minimizes ||s(za)]l Ei= n² = 1. Conversely,
the least smooth weights assign all weight to single training observation i.e. $(xo) = oj so that
[|(()))] = 1 is maximized.
Effective parameters for methods that cannot be written in linear form. The effective parameter definitions considered above all have in common that they require a way of writing predictions & as an explicit function of Ytrain which is possible for the three MI. methods considered in this paper, but not generally the case. Instead, for loss-based methods like neural networks, [HTF09 Ch. 7.7] note that one can make quadratic approximation to the error function R(w) and get
0
De
(22)
where Or are the eigenvalues of the Hessian 8 R(w)[( (/([[//l0 //wwww and a is the weight-decay penalty used. This proxy effective parameters, motivated in a Bayesian context [Mac9]]. is used in [MBW20] 's study of effective parameters used in overparameterized neural networks. We note that, in addition to not being applicable to our tree-based experiments (which do not possess a differentiable loss function), this effective parameter proxy also usually motivated in the context where in- pammall prediction error is of interest [Moo9]] and might therefore also need updating to reflect the modern focus on generalization to unseen inputs. This is definitely the case in the context of linear regression: to make Eq. (22) applicable to the puregularizedrriggless regression setup we consider, one needs to let a tend to 0. this case, the Hessian X'X and we will have that P Ei= [0, > 0} rank X'X) rank X) mán(n. which will be constant at value n once p > n, just like p!
Other related concepts. DLM20) theoretically study implicit regularization of min-norm solutions by computing effective ridge penalties X,, implied by min-norm solutions by solving n = tr(E,, (E,, X, ) with Σ,, = F|XX" X Further, building on the principle of minimum description length (MDL), DSYW20 define a complexity measure in the context of linear regression via an optimality criterion over the encodings induced by a good Ridge estimator class.
E
Additional results
In this section, we first provide further discussion of the experimental setup in Appendix E. and then present additional results: In Appendix [8.2 we show that the location of the second descent can be arbitrarily controlled for all methods under consideration, in Appendix E.3 we plot binary test error, Appendix EE.4 we plot training error, in Appendix E.5 we provide aneedotal evidence that
plaa could be used for model selection and in Appendix E.6 we finally present results using further datasets.
E.1 Experimental setup
Our experimental setup largely replicates that of [BНММ19] We describe the datasets, compu- tation, and each experiment in detail in this section. Code is provided at pattts://githut com/
Datasets- We perform our experiments in the main text on the MNIST image recognition dataset LBBH98] with inputs of dimension 784, In this section, we also repeat these experiments on the SVHN digit recognition task [NWC-1J as well the CIFAR-I0 10 object classification tasks 0H) both containing inputs of dimension 1024 as color images have been converted to grayscale.
All inputs are normalized to lie in the range [0, 1). All three tasks are 10 class classification problems. Furthermore, we randomly sample subset of 10,000 training examples and use the full test set in our evaluation. In SVHN randomly sample a balanced test set of 10,000 examples. We note that the less common choice of using squared error for this classification problem in [8MMM19] is supported by the same authors' work in (HB21 MNS+21 on the utility of the squared loss for classification.
Compute- All experiments are performed on an Azure FX4mds. This machine runs on an Intel Xeon Gold 6246R (Cascade Lake) processor with 84 GiB of memory. The majority of the computational
24

---

cost was due to matrix inversions of large data matrix in the case of linear regression experiments and fitting a large number of deep trees in the tree-based experiments. Each of the three experiments had total runtime in the order of hours.
Trees (Sec. 2.1
We use regression trees and random forests implemented in scikit-learn [PVG+ for our tree experiments, which in turn implement an optimized version of the CART algorithm [FSO84]. As in [BHMM19], we disable bootstrapping throughout and consider random feature subsets of size vd at each split. Like [BHMMT9] rely on 10 one-vs-all models due the multi-class nature of the datasets.
Gradient Boosting (Sec. 2.2) GGaddeent boosting is implemented as described in [HTF09] Ch. 10.10) and restated in Appendix C.3.3 using trees with pleas = 10 and a random feature subset of size vd considered at each split, and learning rate = .85 as used in [8HMM19]. We rely on the scikit-learn PVG 11] implementation loss function, and like [BHMM19 rely on 10 one-vs-all models to capture the multi-class nature of the datasets. We create ensembles of pene different boosted models by initialing them with different
to make use of the squared
seeds.
Linear regression (Sec. 3 As described in the main text we begin with random Fourier Features (RFF) basis expansion. Specifically, given input x E Rd the number of raw model parameters pe is controlled by randomly generating features o,((x)
for all S p where each Vp ~ (O. 52 IJ). For any given number of features P these are stacked to give a n x P dimensional random design matrix Φ which is then used to solve the regression problem y D by least squares. Following the methodology of [BНMМ19] we perform one-vs-all regression for each class resulting in 10 regression problems. For principal component regression we standardize the design matrix, apply PCA, add a bias term, and finally perform ordinary least squares regression.
Re(expV-Iv
E.2 "Peak-moving" experiments
In this section, we show that the first peak in generalization error can be arbitrarily (re)moved by changing when, i.e. at which value of pleaf phoost or PPC, we transition between the two mechanisms for increasing the raw number of parameters in each of the three methods. We do so for two reasons: First, as can be seen in Fig. TT] it allows us to highlight that the switch between the two parameter-increasnng mechanisms is indeed precisely the cause of the second descent in generalization error in all three methods considered. Second, this also implies that the second descent itself is not inherently caused by interpolation: to the contrary, comparing the generalization curves in Fig. II with their train-crror trajectories in Fig. [2] it becomes clear that such a second descent can also occur in models that have not yet and will not reach zero training error. Thus, the interpolation threshold does not itself cause the second descent- rather, it often coincides with a switch between parameter increasing mechanisms because parameters on the pleaf pboost and PPC axis can inherently not be further increased once interpolation is achieved.
Trees
Boosting
Regression
Squared test exroe
1996-2
puc 10000
2011
100
pPn 7700
phot
055
80.5
2000
3.5-
Compooiit Axis
Composite Axis
Composite Astis
Figure 11: Shifting the location of the double descent peak in generalization error by changing when switch between the two parameter-incre parameter-increasing mechanisms. Transitioning from pieaf to prns at different values of pieas in the tree experiments (left), transitioning from plrinet to prmx at diffcrent values of phonet in the boosting experiments (middle) and transitioning from PPC to par at different values of PPC in the regression experiments (right).
Finally, we note that one could also create generalization curve with arbitrarily many peaks and arbitrary peak locations (including peaks at raw parameter counts p > 11) by switching between parameter-increasing mechanisms more than once. In Fig. 13 we show this for the linear regression example, where we switch between increasing parameters through PPC and pez multiple times. This experiment is inspired by [CMBK2I], who show one can "design your own generalization curve"
25

---

Thms
Roosting
Regression
Squared tzsiu ezzor
10000
plot
05
100
PPC 7500
0.3
2000
Compooiit
Composite
Composite Astis
Figure 12: Evolution of the training error for different transitions between the two parameter- increasing mechanisms. Transitioning from pleaf pens different values of pieaf in the experi- ments (left), transitioning from pinost to pen* at different values of phoost in the boosting experiments (middle) and transitioning from PPC to pes at different values of pPC in the regression experiments (right).
in linear regression by controlling the data-generating process through the order by which newly (un)informative features are revealed. In our case, rather than inducing the change by changing the data, manipulate the location of the peak by simply changing the sequence in which parameter counts are increased.
Tes error
Trin ecour
pet 0 fixed, PM incressing 0,5000
Squazed Ernor
0.6
pre fixed PM increasing (0,2500]
p 2500 faced, ptC incressing in (5000, 7500]
pro 7300 fixee, p increasing in (2500, 5000]
0.0
p 3000 Enxed, piC incressing (7500, 10000]
0.0
faxed, PM increasing (5000, 60000)
1000
3.000
12.003
100
PCC
pr
19 PDC
Figure 13: "Design your own generalization curve". We show using the regression example that generalization curve with arbitrarily many peaks and arbitrary peak locations (including peaks at p >> n)) can be created simply by switching between increasing parameters through PPC and pes multiple times (left). Train error remains monotonically decreasing (right).
E.3 Plots of binary test error
revisit Figs. 2 4 and of the main text by plotting 0-1 (or binary) loss achieved on the test-set- measuring whether the class with the largest predicted probability indeed is the true class instead of summed squared loss across classes in the main text. We observe qualitatively identical behavior in all experiments also for this binary loss.
In Figs. 14 to 16
Double Descent in Trees
Foroor by plon pess fixed
Frvor by pens pien! fixed
0.
100
Bluny tost
0.4
200
max moox 50
100
200
300
600
200
80
50
100
plro
pro
x pess
Figure 14: Decomposing double descent in binary test error for trees. Reproducing the tree experiments of [HMM19] (left), Test error by plouf for fixed pena (center). Test error by pena for fixed ploo (right).
26

---

Double Descent in Boceting
Error by plont pams fixed
Error from plont fixed
Blusay ted seror
0.3
g
200
0.1
K 10.3
100
ploott
plwot x peu
Figure 15: Decomposing double descent in binary test error for boosting, Reproducing the boosting experiments of [BHMMT9] (left). Test error by phoost for fixed pen (center). Test error by pens for fixed phoost (right).
Double Descent in Regression
Erpor PPC par fooed
Error by jaz PFC fixed
Buuay test erre
0.8
0.8
pmt 10000
p
2500
ph0 7000
0.-
0.6-
0.5
1000
0.
0.4-
0,2-
0.0
0.0
1100000
10,000
20,000
10,000 + 500000
3000
10000
20000
pPc po
Figure 16: Decomposing double descent in binary test error for RFF regression. Reproducing the regression experiments of [BHMM19] (left). Test error by PCC for fixed pez (center). Test error by pez for fixed PPC (right).
E.4 Plots of training loss
In Figs.
we provide plots of summed squared training losses associated with the plots of summed squared test loss in presented Figs. and 5 in the main text.
to 19
Error en compositt
Error
ploa pams
Error pam, paind fixed
500
Square tran
0.5
10
0.-
2000 x
X
falo Sx gams
Figure 17: Training error in the tree double descent experiments. Training error against [BHMM19 composite axis (left). Train error by pleaf for fixed pens (center). Train error by pess for fixed pleaf (right).
Error on compoeitt axis
Frror by plont pams fixed
Error by pans pieest fixed
0.3
Squared toain
0.2
10
100
max moot 10
30
plose
100
150
200
prox
30
30
poooo pams
Figure 18: Training error in the boosting double descent experiments. Training error against BHMMI9''s s composite axis (left). Training emoor by ploost fixed pens (center). Training error by pens for fixed phoust (right).
27

---

Error on composite axis
Error pre, p fixed
pe .pC fixeed
10020
0.7
1
Squaeod train
0.0
19000
pr0
2000
5003
0.0
0.1
"16,00 0
30,000 + 25.000
10,000 + 50,000
0
30.0
1000
00000
2000
10000
10000
20000
300000
10:00
50000
PeC
per
pro pex
Figure 19: Training error in the RFF regression double descent experiments. Training error against [HMM]9 is composite axis (left). Training error by pPC for fixed pr (center). Training error by per for fixed P (right).
E.5 Investigating applications of p pest to model selection
In this section, we test whether measure like pf measuring the effective parameters used on the test inputs, could be used for model selection purposes, possibly providing some route for redemption for parameter count based selection criteria like [Aka74 Mal73 Sch78] that explicitly trade off training error and parameters used (and importantly, do not require access to held-out labels). We motivated by empirical observations presented in Sec. 4 In particular, we from Fig. that across all three methods, there are models in the interpolation regime that perform very well in terms of generalization and they happen to be those with the smallest y This observation indicates that one straightforward model selection strategy when choosing between different hyperparameter settings that all achieve zero training error could be to compare models by their p!
Here, we test whether it is possible to exploit this in more general settings when there are multiple other hyperparameter axes choose among. In particular, we consider tuning two other hyperpa- rameters in gradient boosting, tree depth pleaf E {10, 50, 100, 200, 500, max} and learning rate 7 (0.02, 0.05, .1, .2, ., 5, .85). We do so in single boosted models (i.e. pens 1), all trained until squared training eπгог reaches approximately zero, i.c. terminate after phoost [1, 500] rounds, where phoost is chosen as the first round (if any) where squared training error krain drops below c 10-4 (conversely, whenever train c for all phoost S 500, we do not consider the associated (pleaf, 17) configurations an interpolating model).
0.0200)
plo/ max
Squared test error
plu/ 500
0.0175
phaf 200
0.0150
pin/ = 100
pim/ = 30
pln/ 10
0.0100
Best with lerain (oracle)
0.0075
0.0050
10
10a
10a
paril
(log scale)
Figure 20: Interpolating models with lower plad are associated with lower test error. Test error vs Jest for interpolating gradient-boosting models with of different (pleaf .1)) -n)-combinntions.
In Fig. 20 we observe that the intuition indeed carries over to this more general scenario and that interpolating models with lower test are indeed associated with lower test error. particular, choosing the model with lowest yea which only requires access to test-time inputs x but no label information y would indeed lead to the best test-performance among the interpolating models (with 4erain < t). Further, using red cross, we also plot the performance of the best non-interpolating model (with 1arain > t) among the considered (pleaf 17) configurations; this is selected among the models with less boosting rounds pboost by oracle with access to test-time performance. We observe that this
28

---

non-interpolating oracle has essentially the same performance as the best interpolating model chosen by pl
E.6 Results using other datasets
Below, we replicate our main experimental results using other datasets considered in [BHMMI9], SVHN and CIFAR-IO, exhibiting the same trends as the experiments on MNIST presented in the main paper.
E.
SVHN
Double Desceut in Trees
Error plaj 5 peu Eased
Ervor by pau, piod Roodd
Sqpared led ertot
15
6.-
0.0
1
maz X.3 50
100
200
20
100
plol i
Figure 21: Decomposing double descent for trees on the SVHN dataset. Reproducing the tree experiment BIIMM1 (left). Test error by pleaf for fixed pers (center). Test error by pens for fixed pleaf (right).
Double Descent Boodting
Error by phece pere Exed pm
Erroe by pone Fiod
301
Squeed
10.41 100 x mas vusc
plan
Figure 22: Decomposing double descent for gradient boosting on the SVHN dataset. Reproducing the boosting experiments of [BHMMI9 (left). Test error by phoost for fixed pens (center). Test error by pens for fixed phoost (right).
Domble Descent in Regrossion
Error by PNC per Easd
Price by per pit Bood
po0 7331
2996.2-
10000
5030
Squared
$1.5
3.3-
6.1
10,000
55,000
10000-
56.00
0
5000
400
(000
5000
10000
10000 2000
3000
30003
5000
prt piz
Figure 23: Decomposing double descent for RFF Regression on the SVHN dataset. Reproducing the RFF regression experiments of [BHMM19 (left). Test error by PPC for fixed pez (center). Test error by pes for fixed PPC (right).
Thees
Roodiing
Linese Regission
#8 (oo scaks)
100
101
mat veax M plm] prss
your
0,00 D
20,000
plont pess
peo
Figure 24: The effective number of parameters does not increase past the transition threshold on the SVHN dataset. Plotting ps (orange) and 2 (green) for the tree (left), boosting (center) and RFF-linear regression (right) experiments, using the original composite parameter axes [HHMM9
29

---

Trees
Reowlnng
Linor Regresionn
2000
5000
0.00-
0.7
55603
Squeed
0.0
1%
(log scale)
1%
(log sosle)
16 (log scole)
Figure 25: Back to U (on the SVHN dataset). Plotting test error against the effective number of parameters measured by mm
E.6.2 CIFAR-10
Double Descent in. Trmes
Error pladt per Food
Eiroc by paur piin Fxod
Square erve
53)
100
12
241
1932
100
2001
110
Figure 26: Decomposing double descent for trees on the CIFAR-10 dataset. Reproducing tree experiment of BHHMM19 (left). Test error by pleaf for fixed pens (center). Test error by pens for fixed pieaf (right).
Double Descent Bocating
Ercor by phost pem Exod
Errce pine plost fized
Square led
0.5
10xx
viEz 19 1
100
150
201
phone Sc perss
Figure 27: Decomposing double descent for gradient boosting the CIFAR-10 dataset. Repro- ducing the boosting experiments of (BHMM19 (left). Test error by plonst for fixed pens (center). Test error by pris for fixed ploost (right).
Domble Doscant in Regresionn
Frror by pro per Eind
Finee by per prt food
1596.2
p 7530
1000
Squard bast
11603
pec 5030
1480)
pec 2030
35,000
50,00
10,00
13,00
Decomposing double descent for RFF Regression on the CIFAR-10 dataset. Reproduc- ing the RFF regression experiments of [BHMM] (left). Test error by PPC for fixed pez (center). Test error by per for fixed PPC (right).
Figure 28:
30

---

Thees 107
Boreting
Linoor Regresion
s (be sodes)
101
101
not rax
roor
10,000
plag peu
plout pas
prt
Figure 29: The effective number of parameters does not increase past the transition threshold the CIFAR-10 10 dataset. Plotting prin (orange) and p4 (green) for the (left), hoosting (center) and RFF-lincar regression (right) experiments, using the original composite parameter axes [HMM11..
Troes
Boosting
Linse Degression
2000 pres
0.15
0.3
Sipneed
0.07
y0t (log scale]
(Dog scdile
1
(log scaln)
Figure 30: Back to U (on the CIFAR-10 dataset), Plotting test emrr against the effective number of parameters as measured by ps
31


Reviews:
[{"review_id": "lvGnSKxRXL", "reviewer": "Reviewer_WN4r", "summary": "The paper analyzes the seeming appearance of double descent in non-deep models, and finds various ways in which it disappears when thinking more carefully about how the parameters are scaled. Trees and boosted models see double descent because parameters start increasing along a different and more effective dimension (ensemble size) once p=n. Linear regression sees double descent because the min-norm optimization solution used in prior work functions differently before and after p=n. And all of these methods no longer see double descent when the \"effective number of parameters\" is used as the x-axis instead of the raw number of parameters.", "questions": "I like the paper and applaud your work, but as a take-it-or-leave-it suggestion I would consider whether a reframing around your core contributions (insights about overparameterized linear regression) vs. being a rebuttal to another paper (forces simple and less interesting critiques about ensembles to take up space) would help. There's interesting stuff in the appendix (e.g. condition number analyses of bases) that could certainly fit in the main paper if you end up going that route.\n\nOne major question on my mind after reading this paper is what it \"means\" to find a richer basis among the input features and why that helps. Do you have any insights on this? Are there applications to preconditioning? How closely tied is it to the choice of RFF features, vs. alternate setups where e.g. there are p>n features by default?\n\nPer the 'weakness' above, can you add the relationship/analysis of raw parameter count and effective parameter count?", "limitations": "N/A", "rating": 7, "confidence": 4, "soundness": 4, "presentation": 3, "contribution": 3, "strengths": "I greatly enjoyed reading the paper. The findings on linear regression are very interesting and contribute towards the understanding of the important phenomenon of double descent. It is well-presented, with concise and easy-to-understand figures and clear writing. It is likely to encourage follow-on work in the field.", "weaknesses": "The portions on trees/boosting and linear regression sit a bit unevenly together. In my view, the trees/boosting section doesn't actually tell us much about double descent since we're talking about independently trained ensembles, which is a different issue altogether. Meanwhile, the linear regression bit is very interesting.\n\nThe connections between min-norm solutions, SVD, and PCA (and the Moore-Pensrose pseudoinverse) are reasonably well understood (see e.g. these class notes http://www.sci.utah.edu/~gerig/CS6640-F2012/Materials/pseudoinverse-cis61009sl10.pdf), so I'd question the novelty of the theory a bit. However, the application of the theory to understand the problem was excellent.\n\nThe section on effective number of parameters didn't spend enough time analyzing the relationship between raw parameter count and effective parameter count (and any implications thereof), which seems worth dwelling a bit from the purpose of understanding double descent (more so than showing the lack of double descent using that metric as the x-axis).\n\nI think the paper would be improved with more connections to related work and related ideas, e.g. regularization and particularly ridge regression (due to its connections with PCA), work on multi-layer linear networks and PCA (e.g. Baldi and Hornik 1988, \"Neural Networks and Principal Component Analysis: Learning from Examples Without Local Minima), connections between neural network optimization and min-norm solutions (which you do give a brief mention to, but seems quite relevant)", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the in-depth and constructive review! We were delighted by the assessment that our paper is \"interesting\", \"well-presented \" and \"likely to encourage follow-on work in the field\", and, limited by space constraints, hope to resolve doubts about any weaknesses in our response below!\n\n**Inclusion of boosting and trees.** We are delighted by the deep interest in our results on the linear regression case study! We agree that these may be of most individual interest to the community and will use the additional space in the updated manuscript to prioritise moving some of the additional linear regression results from the appendix to the main text. Nonetheless, allow us to attempt to convince you why we consider the case studies on trees and boosting an important part of our paper. The goal of our work was to study the appearance of double descent outside of deep learning generally, motivated by [BHMM19] who suggest they “provide evidence for the existence and _ubiquity of double descent for a wide spectrum of models_” (abstract). The experiments that we replicate were said to “give empirical evidence that the families of functions explored by boosting with decision trees and random forests also show similar generalization behavior to that of neural nets” (p.4) – this constitutes the only example of non-deep double descent except for linear regression that we are aware of, which is why we consider these results important to include. We certainly agree that the experimental setup is a lot less natural than the regression case study – in fact, this is precisely what inspired our paper in the first place: our investigation of the tree-based experiments (where the two-axes decomposition may be intuitively apparent to some readers) is what motivated our search for orthogonal parameter axes in the linear regression case (leading us to distinguish between PC- and excess features), and we thus also consider this part an important pre-requisite for our deeper analyses. \n\n**Connections between min-norm solutions, SVD, and PCA.** We did not intend to imply that we are the first to notice a connection between these concepts; rather, we indeed consider our application of these insights to the double descent context our main novelty. However, to the best of our knowledge, the specific result derived in Prop 1 has not previously been formalized in this way in the literature and provided an essential tool for our analysis in Sec. 3. We have added a line to our discussion of these topics further emphasising this point.  \n\n**Additional analyses of raw and effective parameter count.** We thank the reviewer for the suggestion to include further analyses of the raw parameter axes and the effective parameter count, as we agree that this provides interesting new insights into the behaviour of the ML methods. In particular, per the reviewer's request, we created figures plotting the effective parameters against the two separate parameter axes (see Figures attached to general rebuttal), which allows to make even more clear the role of the two parameter axes: along the first axes, effective parameters monotonically increase while along the second axes, effective parameters monotonically decrease. Thus, this further confirms that (as we had stated in l. 317) the second axis acts by ‘decreasing the effective complexity implied by each value’ along the first axis).  We agree that these results provide evidence that compliments Figs 6 & 7  – and will include some of the insights into the updated manuscript once the additional content page becomes available!\n\n**Understanding basis quality implied by $P^{ex}$.** Please refer to the general rebuttal, where we answer this for multiple reviewers! \n\n**Additional connections to related work.** We thank the reviewer for suggesting that our section on extended related work in appendix A could be expanded even further; we will include additional discussions of the connections between ridge regression and PCR as well as a discussion of work on regularization and the double descent phenomenon! We will also expand upon the connections between neural networks and our work. \n\n\n\n\n"}, {"review_id": "Gw1sJ60axi", "reviewer": "Reviewer_vbD3", "summary": "This paper studies the double descent phenomenon focusing on the complexity axis used to display the phenomenon. For trees and boosting, they show that double descent is a result of peculiar axes used by one previous work and that an alternative formulation of complexity removes the phenomenon. They then propose a generalized measure for the effective number of parameters for both trees, boosting, and lienar models which recovers a more classical U-shape.", "questions": "- A deeper comparison with related work would be helpful, particularly MBW20, DLM20, and DSYW20.\n- The authors should connect their analysis in Section 3 based on principal components  with the more popular analyses using ridge regression rather than limiting PCs (e.g. that in HMRT22). The empirical observations are extremely similar and the connection is fairly close, as ridge regression can (often) be seen as a smooth eversion of PCA regression.\n", "limitations": "- See above", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is clearly written\n- The reparameterization of complexity for trees and boosting is clear and needed + for linear models is well-motivated\n- The introduced generalized effective number of parameters based on smoothers is interesting and seems to work well", "weaknesses": "- The evidence for double descent in trees is very limited and weak (one main figure and one appendix figure in BHMM19); the authors may want to dedicate more time to the rest of the paper rather than refuting this phenomenon\n- The experimental settings shown are very limited, would be nice to see less synthetic settings, particularly in Fig 7 to see how well the proposed complexity measure holds\n", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review -- we are delighted by the positive assessment of our presentation, complexity reparametrization and effective parameter measure! We hope to resolve doubts about any weaknesses in our point-by-point response below.\n\n**Inclusion of boosting and trees.** We are delighted by the deep interest in our results on the linear regression case study and effective parameters, and certainly agree that they might be of most individual interest to the community. Nonetheless, allow us to attempt to convince you why we consider the case studies on trees and boosting an important part of our paper. The goal of our work was to study the appearance of double descent outside of deep learning generally, motivated by [BHMM19] who suggest they “provide evidence for the existence and _ubiquity of double descent for a wide spectrum of models_” (abstract). The experiments that we replicate were said to “give empirical evidence that the families of functions explored by boosting with decision trees and random forests also show similar generalization behavior to that of neural nets” (p.4) – this constitutes the only example of non-deep double descent except for linear regression that we are aware of, which is why we consider these results important to include. We certainly agree that the experimental setup is a lot less natural than the regression case study – in fact, this is precisely what inspired our paper in the first place: our investigation of the tree-based experiments (where the two-axes decomposition may be intuitively apparent to some readers) is what motivated our search for orthogonal parameter axes in the linear regression case (leading us to distinguish between PC and excess features), and we thus consider it an important pre-requisite for our deeper analyses. \n\n**Experimental settings.** The goal of our work was to reanalyse and provide explanations for the existing evidence for non-deep double descent -- of which BHMM19 (and the datasets within) provided the broadest account. Therefore, following closely the experimental setup in their paper was a key design choice for our work, as this focus allowed us to really zoom-in and provide in-depth analyses of the original experiments and findings.However, we are happy to provide results on an additional non-image, real-world dataset of different modality for this reviewer (also, note that replication of our complete analyses using some additional datasets were already included in our App E.6). To do so we selected MiniBooNE, a dataset from the particle physics community in the Fermilab in which 50 features represent a stream of muon neutrinos that are fired and recorded by a detector which measures the presence of electron neutrinos (signal) among the muon neutrinos (noise). The goal is to classify observations as signal or background noise. This task has been recently recognised as a recommended benchmark task in researching machine learning methods for unstructured data [1].\n\nWe process the data just as in the other experiments and repeat the analysis for the RFF-regression. The results are included in the attached PDF in the top level rebuttal where we observe the same double descent effect along the raw axes, which, when using our proposed measure of effective parameters, again reduces into a familiar U-shaped complexity curve consistent with our previous experiments.\n\n[1] Grinsztajn, Léo, Edouard Oyallon, and Gaël Varoquaux. \"Why do tree-based models still outperform deep learning on typical tabular data?.\" Advances in Neural Information Processing Systems 35 (2022): 507-520\n\n\n**Connections to the ridge regression results of HMRT22** The results in our work are entirely consistent with and complimentary to those of [HMRT22]. This is particularly highlighted in their Fig. 1 where they find the usual double descent shape in (ridgeless) min-norm regression but _no double descent_ in optimally tuned ridge regression (i.e. where the regularization strength is selected to optimize validation performance). Interestingly, at $\\gamma = 1$, where the number of features is equal to the number of examples, standard analysis based on just parameter counts would suggest performance should be poor. This is because, as shown in our work, this is typically where _effective parameters_ are highest. However, this is counteracted by optimally tuned ridge regression which would automatically select for higher regularization at this point and therefore reduces the implied effective parameters – thus removing the double descent behaviour entirely. This is an excellent illustration of the importance of measuring _effective parameters_ over raw parameters as advocated for in our work. We therefore thank the reviewer for suggesting that our section on extended related work in appendix A could be expanded even further; we will include additional discussions of the connections between ridge regression and PCR as well as a discussion of work on regularization in the context of the double descent phenomenon!\n\n**Further discussion of MBW20, DLM20, and DSYW20.**  We will include an additional discussion of the effective parameter measures used by DLM20, and DSYW20 into Appendix D, where we already discuss MBW20’s measure in more detail.\n"}, {"review_id": "btFYA8QtS5", "reviewer": "Reviewer_Uot3", "summary": "This paper studies the double descent phenomenon where it has been suggested that optimal generalization performance is achieved as model complexity gets extremely large and training data is perfectly overfit. However, this work suggests that true model complexity is not described simply by the number of parameters. This claim is backed by replications of experiments from a foundational double descent paper, where the main result is empirical evidence and a theoretical explanation on how linear regression in high dimension reduces to a lower dimension problem on principle component features. Lastly, the authors propose a way to measure the number of effective parameters for each replicated experiment.", "questions": "I'm curious how well your linear regression explanation extends to other statistical models like in BLLT20 and HMRT22.", "limitations": "The authors adequately address the limitations.", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "- The paper is well-written and the motivation for the work is well-defined\n- Proposition 1 is an interesting and novel observation and its proof is rigorous from what I can tell\n- The area of overparameterized machine learning is of very high relevance today", "weaknesses": "An obvious weakness of the paper is that it does not use modern neural network models. I recognize that work on linear models is necessary as a foundation and the authors do discuss this limitation in the discussion, however it is troubling that there is no proper justification/commentary on the connection between the work and modern architectures.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review -- we are delighted by the positive assessment of our presentation, relevance and our insights into the linear regression case study!\n\n**Connections to Neural Networks.** We completely agree that – as discussed in l. 356ff. – understanding double descent in neural networks is a natural and very interesting next step – which we consider highly nontrivial, and to hence fall beyond the scope of this paper. In addition to the possible connections already stated in our conclusion, we believe that one very interesting and promising starting point for extending our work to the neural network setting is to use our approaches for understanding double descent in linear models and apply them to neural networks trained  in the _lazy regime_ (see e.g. ‘On Lazy Training in Differentiable Programming’, Chizat et al, NeurIPS19), which essentially act like models that are linear in features defined through the gradients of the model at initialisation. Nonetheless, allow us to emphasize that we strongly believe that understanding double descent in simpler models (e.g. smoothers), as we do in this paper,  is of value to the community as is – both in its own right _and_ to provide a foundation for follow up work to understand this phenomenon in more complex models – exemplified also by the numerous papers published recently studying double descent in linear models exclusively.\n\n**How does our linear regression explanation extend to BLLT20 and HMRT22?** Where BLLT20 and HMRT22 also study min-norm linear regressions, our basic arguments naturally apply: Also in their studies, due to the use of the min-norm solution,  there is an implicit change in the parameter-increasing mechanism at p=n and thus once p>n, the number of truly determined directions remains constant at n and $p^{train}_s=n$ by construction. While $p^{train}_s$ is easy to determine as it is independent of the problem characteristics and simply equal to min(n,p),  $p^{test}_s$ depends on the data characteristics thus studying theoretically how this would evolve would likely involve different assumptions on the data-generating mechanism. Studying the interaction between our work and specific data generating process would definitely be an interesting avenue for future work!\n"}, {"review_id": "jn0vogGDTU", "reviewer": "Reviewer_4SoX", "summary": "This paper proposes a new perspective for understanding the double descent behavior in non deep learning models: Once the number of raw parameters goes pass the interpolation threshold, the effective parameter number actually stops increasing and if one keeps increasing the number of parameters, the underlying model class will be modified. The authors analyze three examples from existing literature: Decision tree, gradient boosting and linear regression. In particular, the authors perform a novel analysis on overparameterized linear regression shows that the increment of Fourier feature dimensions would first increase the number of PCA regression dimensions, which follows the classic U curve structure, and then increase the number of excess feature dimension, which results in a L shape of test error. However, studying the effective dimension size requires model-specific derivation, therefore the author proposes a unified framework for studying the effective parameter size in different models using techniques from smoothers. With, the proposed measurement as the x-axis, the double descent shape on y-axis disappears, which aligns with the experiment results for individual models.", "questions": "- The authors show that for decision tree, gradient boosting, and linear regression, there exists an axis in model complexity which follows \"bigger is better\". Does this axis exist for all types of models?\n\n- How does the proposed measurement fit into unsupervised learning models where there does not exist `y` in the task.", "limitations": "See Weaknesses", "rating": 7, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper is well written and well motivated.\n\n- The analysis and proposed measurement of effective number of parameter is technically sound.\n\n- The relationship with existing literature is thoroughly discussed.", "weaknesses": "- If I understand correctly, the proposed measurement needs to be computed using test samples, which is not as straightforward as other metrics that only requires training sample, e.g. the measurement proposed in [MBW20].", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the thoughtful review -- we are very delighted by the very positive assessment of our work! Below, we respond to the points raised in the review in turn.\n\n**The need to evaluate effective parameters on test samples.** We appreciate this reviewer raising this point as we believe this to be, in fact, a key strength of our work. Specifically, we would like to highlight that, as shown in Fig. 6, we _can_ compute our metric on the training examples too -- but observed this measurement of effective parameters without consideration of the test input distribution to be insufficient to explain generalization performance and were therefore motivated to address this limitation in our calculation of effective parameters. This becomes apparent when we compare to the measure in [MBW20] as suggested. Note that [MBW20]'s metric is motivated from a Bayesian setting where one uses a prior with parameter $\\alpha>0$ (corresponding to ridge regularization in a frequentist setting), while we consider unregularized regression. If we let $\\alpha$ approach 0, their effective parameter measure $\\sum\\_{i=1}^p \\lambda\\_i/(\\lambda\\_i+\\alpha)$, where $\\lambda\\_i$ are the eigenvalues of X'X (computed using training examples), approaches $\\sum\\_{i=1}^p 1[\\lambda\\_i>0] = rank(X'X) = min(n, p)$ which is exactly equal to what we measure with $p^{train}_s$ for linear regression -- and hence constant once p>n. Therefore, like the case of applying our metric to the training data (as shown in Fig 6), this metric would fail to capture the decrease in complexity during the second descent. This highlights precisely the _strength_ of our metric being that it _can_ also be applied to test data (note: this is without requiring access to labels).  Only through this application to test data, as discussed on L262-281, we may better extend beyond the fixed design setting into the modern machine learning regime where we are primarily interested in generalization to _unseen_ covariates.\n\n**Do these two types of axes exist for all types of models?** While we intentionally focused here on the three specific methods under investigation, we would certainly consider it an interesting and fruitful direction for future research to understand whether other ML methods also have a similar distinction into parameter axes along which generalisation performance evolves in particular patterns! Our results provide anecdotal evidence that the first parameter axes may be responsible for bias reduction – it controls how well the training data can be fit –, while the second parameter axes drive variance reduction for test-time predictions; studying how other methods fit into this intuition would certainly be an interesting next step!\n\n**How does the proposed measurement fit into unsupervised learning?** Although model complexity is typically primarily considered in the supervised setting, notions of model complexity are certainly valuable in the unsupervised setting too. Since the smoother matrix upon which we measure effective parameters is a transformation from ground truth labels to predictions one might similarly consider the unsupervised setting in which we have a transformation from input space into some (usually compressed) representation. A simple example might be the family of principal component analysis methods. Another interesting case for consideration might be semi-supervised learning in which we have access to some unlabelled data which clearly aligns with our measure. While further exploration of these settings is clearly outside the scope of this paper, considering how one might transfer the results from this and other similar works beyond the supervised setting would certainly make for an interesting research direction. \n\n\n"}, {"review_id": "BIFulzH0s0", "reviewer": "Reviewer_trNU", "summary": "This paper critically looks at the double descent phenomena, and it is shown that the number of parameters on the x-axis does not represent the complexity well for double descent curves, and in essence, causes the double descent. If a more appropriate complexity measure is adopted, in this paper, the effective number of parameters, the phenomena disappears, and we observe a typical U-shape or L-shape, as expected from learning theory. \n\nNote: I did not have time to study the appendix in detail. ", "questions": "Are there any connections with the proposed metric of Generalized Effective Number of parameters and generalization? E.g. are there any upperbounds on the generalization that can be given in terms of the proposed measure? That would be an added strength\n\n", "limitations": "none", "rating": 9, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "This paper addresses and resolves some paradoxes in the community surrounding the double descent phenenoma. As such, I believe it will have a high impact and is relevant for many researchers. Furthermore, the introduced complexity measure can be highly relevant for model selection tasks. \n\nThe analysis is straightforward and complete. Especially nice is that it revisits the original experiments of Belkin exactly and finds the root-causes of the behavior. \n\nThe figures are clear and intuitive, especially the color-coding with blue and red curves is very helpful to our understanding.\n\nThe analysis of linear regression seems to agree with some very early analysis by \nS. Raudys and R. Duin, “Expected classification error of the\nFisher linear classifier with pseudo-inverse covariance matrix,”\nPattern Recognit. Lett., vol. 19, no. 5-6, pp. 385–392, 1998\nwho noted that dimensionality reduction indeed plays the suggested role. A more recent work that covers this is:\nJ. H. Krijthe and M. Loog, “The peaking phenomenon in semisupervised learning,” in S+SSPR. Springer, 2016, pp. 299–309\nwhich can be slightly easier to read. However, the presentation in the current paper is much more clear and also covers the boosting and random forest experiments, while these papers only cover linear regression.\n\nMore connections and background on the double descent phenomena can be found in:\nViering, T., & Loog, M. (2022). The shape of learning curves: a review. IEEE Transactions on Pattern Analysis and Machine Intelligence.\nFor example, double descent can either be visible in learning curves or feature curves, a connection that is often overlooked. \n\nNote that, historically, the double descent behavior was studied inbetween 1990 and 2019 (as also apparent from above), but that this was in a subcommunity that was not popular. \n\nAs an aside, we have attempted a similar analysis as the one given in the paper via VC bounds and other similar measures for regression, but they generally are not fine grained enough for the analysis required. I am very happy the authors did manage to unmask the paradox via the proposed complexity measure. ", "weaknesses": "none", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We would like to thank the reviewer for the very interesting, in-depth and constructive review! We are delighted by the reviewer’s overwhelmingly positive review of our paper, in particular the assessment that “it will have a high impact and is relevant for many researchers”! We also put much effort into making the paper intuitive and easy to follow, and are especially excited to hear that this was appreciated. (Responding to the aside, we were also very interested in the reviewer’s own experience with applying other measures of complexity to this problem, and in this light especially thrilled by the review’s favourable assessment of our own approach!).\n\nFinally, we are grateful for the additional references included in the review –  we will include these in the updated version of  the extended literature review in Appendix A.  \n\nWith regards to the question on providing bounds for generalization using our effective parameter measure, we completely agree with the reviewer that this will be a very natural -- albeit challenging -- next step that will drive further, more crisp, understanding of the effect of effective parameters on generalization. It is not something we have investigated deeply so far, as we were focussed on finding an intuitive and empirical resolution to the double descent phenomenon, but we hope that it may be possible to borrow further insights from the vast literature on smoothing to make progress in this direction in the future!"}, {"review_id": "ZSENC7qTXy", "reviewer": "Reviewer_tnvy", "summary": "The paper aims to explain the well-known phenomenon of double-descent in the scope of several traditional ML methods (random forests, boosting and linear regression on random Fourier features). The main message of the paper (in the mentioned scope) is that what appears to be a double-descent on the first sight (using plots that count raw number of model parameters), might actually be a consequence of an intristincly two-dimensional parameter development composed of two traditionally behaved, complementary components. In all the studied cases, authors disentangle the parameter count into two parts - one accounting for a complexity of \"a single model within the considered class\", while the second accounting for something, that one could call \"extent of statistical power in terms of some proxy of mixture of experts, or ensembles\". The authors show that once the parameters are counted in this two-dimensional manner, the double-descent curve folds into two curves, of which one usually exhibits traditional U-shape and the other one exhibits an L-shape. For linear regression, authors consider a non-trivial disentanglement - into the number of basis vectors that are directly used for regression and the number of exceeding features. \n\nIn an independent part, authors consider models that fall into the category of smoothers (kNN, trees and forests, LR) and show that if one counts parameters in a more sensible way (in the paper via a specific, smoothers-tailored effective number of parameters measure), one can not even register a double-descent behavior anymore. The authors show that the test performance can be partially explained via the effective number of parameters (though it seems the number of ensembles/extra features should be taken into account too). ", "questions": "Q1: Why is the difference between test and train effective parameter count in Figure 6 for RFF-LR at the interpolation threshold so huge? \n\nQ2: Do you have an intuition on how to extend the results of part 1 to neural networks? What would be the candidates for the two dimensions? What about other models? Is there a way to make this more model-agnostic? \n\nQ3: Can you explain any of the questions raised in the \"weaknesses\" section? \n\nBesides, I have a few comments: \n\nC1: The statement in lines 159-160 seems to be incorrect. I don't see how min-norm solutions can project $y$ into a row space. \n\nSummary: \n\nDespite several significant concerns I have raised in the \"weaknesses\" section, the paper brings some truly novel and important ideas (most of the part 1). Therefore, I recommend accepting the paper. However, I would be more happy, if the authors addressed the issues raised in the \"weaknesses\" section, either in the rebuttal, or, more conveniently for them, by withdrawing the paper and submitting the improved version to another venue, producing a very strong submission. \n\nNote: After seeing the author's response and having most of my concerns resolved, I have decided to raise my score from the original 6 to new 7.", "limitations": "I didn't find any explicit discussion of limitations, despite being marked present by the authors in the paper checklist. Perhaps a few sentences here-and-there can be interpreted as a discussion of limitations. ", "rating": 7, "confidence": 4, "soundness": 3, "presentation": 4, "contribution": 4, "strengths": "S1: The idea of decomposing the parameter count into two independent dimensions which unfold (and therefore partially explain) the well-known double-descent is (I believe) novel, surprising, important (at least within the scope of the studied models), interesting, neat and probably impactful. The analysis done for the models considered is strong, empirical evidence convincing and theoretical analysis for RFF-LR makes sense. The experiments in this section are well-chosen and well-done and to the point. \n\nS2: As a part of the paper's exposition, another very important observation is made (around lines 192-195) - the double descent, being a consequence of different mechanisms (explained in the paper), is not strictly tight to the point where the model capacity enters the interpolation regime. We can obtain similar double-descent curves with breaking points far below the interpolation threshold.\n\nS3: The quality of writing and the overall clarity and structure of the paper are well-above the average. \n\n", "weaknesses": "The weaknesses are roughly sorted by severity, starting with the most severe. \n\nW1: The whole part 2 of the paper - explaining the double descent with alternative parameter counting - is not novel, as acknowledged by the authors. The idea of the double-descent appearing to happen only if raw parameters are displayed, but disappearing, or being more explainable, if effective number of parameters measure is used instead, is already done in several works cited by the paper. The authors defend the originality and novelty of this part and of the used effective parameter count as a tool for explaining double descent, within the scope of smoothers, by claiming that (i) unlike some of the previous work, it covers model classes that use trees and (ii) the proposed distinction between train and test time parameter count is essential to explaining the double-descent and (iii) the proposed parameter count does not require test-time labels, unlike the previous methods. However: (i) while this is true, the disadvantage is that this method is only usable for smoothers, and therefore it is very unclear how this can be used for, for instance, neural networks (unlike the measures used in the cited literature), which limits not only the scope of this part, but also, more importantly, the potential impact of this part. On the other hand, (ii) seems not to be well-reasoned. While it is true that for this particular measure and for smoothers and in-sample double-descent this seems to be the case, other complexity measures, such as the one considered in [1], but also those that [1] compares itself against, seem perfectly capable of explaining double-descent (for most of the models excluding trees) without this train-test distinction. Finally, (iii) seems not to even be true, as the method considered in [1] and the ones cited by [1] do not require the held-out / test data at all. \n\nW2: Related to W1, the authors do not explain at all why the effective parameter count drops so significantly if we increase the number of ensembles/exceeding features (i.e. the secondary parameter count dimension). Perhaps it is not in the scope of the paper, but I would find it a significant strengthening of the paper, if this was included. In fact, the authors don't even explain (except in the in-sample RFF-LR case with the first dimension of parameters already being equal $n$), why the effective parameter count in the test time doesn't increase. I would, moreover, want to see an alternative to Figure 7, but with $P^{PCA}$ being fixed and $P^{Ex}$ being the variable for different base levels of $P^P{PCA}$, because with this it is not even clear what the relation between the $P^{Ex}$ and the effective parameter count with fixed (and potentially small) $P^{PCA}$ is. \n\nW3: Though the authors provide a heuristic explanation on why increasing $P^{Ex}$ should improve the model's performance (by providing better basis features and better-conditioned feature matrices), this does not really explain the improvement in model's performance. The connection between the quality of basis features in terms of the properties of the basis feature matrix and the test performance is not clear. Information-theoretically, all the information necessary to predict $y$ should already be encoded in $X$, thus representing $X$ with increasing number of random features, just because some matrix becomes better conditioned, does not seem to causally explain the improvement in test performance. \n\nW4: Related to W3, the authors do not at all discuss the apparent non-symmetry between the first and the second dimension. How come the second dimension of parameter count enjoys L-curve, while the first dimension still displays U-curve? Can you provide an explanation that would extend beyond the particularities of Appendix B and wrap all the considered models in a simple (or at least general-enough) way? \n\nW5 (minor): I don't agree with line 290: \"First, we observe that these results perfectly match the intuition developed in Part 1\" - In part 1, there is no intuition built on why the measures of effective number of parameters should never increase beyond the first dimension of parameter count. \n\n[1] Maddox, Wesley J., Gregory Benton, and Andrew Gordon Wilson. \"Rethinking parameter counting in deep models: Effective dimensionality revisited.\" arXiv preprint arXiv:2003.02139 (2020).", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank the reviewer for the very interesting, in-depth and constructive review! We were delighted by the assessment that Part 1 of our paper was \"novel, surprising, important , interesting, neat and probably impactful\" and, limited by space constraints, hope to resolve more pressing doubts about Part 2 in our response below.\n\n**Novelty of part 2 (W1).** We certainly agree that – as discussed in the related work section – we are not the first to use alternative ways of measuring model complexity to study double descent (DD) in general. Nonetheless, the approach we take in our paper is very different from existing work, resulting in significant novelty also in this section: in particular a) we are able to quantify and understand the effective parameters used by _different classes of methods_ than existing work, while making new connections to the literature on smoothing, b) we are the first to study and discover differences in the used effective parameters at training and testing inputs, and c) are able to uncover the ‘stacked U-curve’ phenomenon in Figure 7 (which, to the best of our knowledge, has not previously appeared in any related work) only _because our decompositions from part 1 revealed the two-axis nature of the original experiments_.\n\n**Comparison to [MBW20] (W1).** First, allow us to emphasize that we strongly believe our work to be _complementary_ to  [MBW20]: while their approach cannot natively handle models trained without explicit loss function, our $p^0_s$ may indeed seem less _naturally_ applicable to study neural networks (*see also the top-level rebuttal for more on neural nets!) – thus, depending on the use-case of interest, either may be more appropriate to use.  Second, regarding (W1, ii) we would like to highlight that a need to look beyond train-time effective parameters to understand DD can also arise when using [MBW20]’s approach.  To see this, note that linear regression is the only method considered in both our and [MBW20]’s paper; however, while we consider _unregularized_ regression like BHMM19, [MBW20]’s metric is really only well-motivated when one uses a prior with hyperparameter $\\alpha > 0$ (i.e. corresponding to inclusion of a ridge penalty in a frequentist setting). If we let $\\alpha$ -> 0, their effective parameter measure $\\sum_{i=1}^p \\lambda_i/(\\lambda_i+\\alpha)$ approaches $\\sum_{i=1}^p 1[\\lambda_i>0] = rank(X’X) = min(n, p)$ which is exactly equal to our $p^{train}_s$ for linear regression and hence constant once $p>n$. For the unregularized linear regression case, their approach therefore cannot explain DD and a train-test distinction is also necessary here. Finally, regarding (W1, iii) we agree with the review – [MBW20]’s measure does not require access to test time labels and we did not intend to imply that it does. We would like to clarify that the statement in l. 377  refers to selection criteria based on held-out loss (e.g. cross-validation) as discussed in l. 374 (and not [MBW20]’s work discussed earlier in the paper).\n\n**Understanding why $p^{test}_s$ drops along axis 2 (W2).** For tree-based methods, this is easiest to see: Intuitively, $||s(x_0)||^2$ here measures the non-uniformity in weight given to each training target when issuing predictions. In a single tree grown to full depth, each test example will fall into a leaf with a single training example – which has the maximum number of effective parameters. However, when ensembling multiple such trees, for test inputs $x_0$ in underdetermined regions of the feature space, weight is likely to be spread more uniformly as different random splits place $x_0$ in leaves with different training examples across the different trees in an ensemble. While a single tree acts like a 1-NN regressor, an ensemble of multiple trees can thus act more like a k-NN regressor (with k>1) for unseen inputs. For the regression case, note that – for a basis B constructed through PCA, we have that $||s(x\\_0)||^2=||b(x\\_0)(B’B)^{-1}B’||^2=b(x\\_0)(B’B)^{-1}b’(x\\_0)=\\sum^{P^{PCA}}\\_{p=1} b^2\\_p(x\\_0)/\\lambda\\_p$ as B has orthogonal columns and for each column $B\\_p’B\\_p=\\lambda_p$ (where $\\lambda_p$ is the pth eigenvalue of  $\\Phi’\\Phi$) by construction. On the training data, we have that, as expected, $\\sum^n\\_{i=1}||s(x\\_i)||^2=\\sum^n\\_{i=1}\\sum^{P^{PCA}\\}_{p=1} b^2\\_p(x\\_i)/\\lambda\\_p = P^{PCA}$ as $\\lambda\\_p$ is also the empirical variance of the PCs ($\\lambda\\_p=n^{-1} \\sum^n\\_{i=1} b^2\\_p(x\\_i)$). However, on the unseen testing inputs, it is possible that previously unobserved large values along the low-variance directions with very small $\\lambda_p$ will lead to terms that blow up the $s(x_0)$ immensely (which is exactly what we observe in our experiments). Thus, $||s(x_0)||^2$ for new inputs likely shrinks as the variances $\\lambda_p$ of the included PCs grow – which – as we see empirically in Appendix B3 – happens as we increase $P^{ex}$ for fixed $P^{PCA}$. As suggested, we also included a plot of $p^{test}_s$ by $P^{ex}$ and $P^{PCA}$ separately (see the general rebuttal).  While our primary interest lies in understanding the DD phenomenon, we agree that interesting insights about the methods themselves can be gained through study of $p^{test}_s$ -- and will include some of the above into the updated manuscript, thank you for the suggestion!  \n\n**Why would adding more $P^{ex}$ improve model performance? (W3)** Please refer to the general rebuttal, where we answer this for multiple reviewers!\n\n**Non-symmetry between axes (W4).** Our results provide some anecdotal evidence that the first axis can be best understood as a bias-reduction axis – it controls how well the training data can be fit (increasing its parameters reduces underfitting – only when the first axis is set to its maximum can interpolation be achieved). The second axis appears to predominantly achieve variance-reduction _at test-time_: it reduces ||s(x_0)||, reducing the impact of label noise by smoothing over more training examples."}]

Author rebuttal:
We would like to once more thank all reviewers for their time and effort put into the review process -- we thoroughly enjoyed reading the interesting and constructive reviews we received. We were delighted by the overwhelmingly positive response to our paper, and are thrilled that all 6 reviewers agreed that our study of the double descent phenomenon will be of interest to the NeurIPS community! We also received numerous stimulating questions (extending far beyond what we could hope to answer within the scope of a single conference paper) and hope that future work will follow up on many of interesting directions highlighted in the reviews!

Below, we provide some responses to questions raised by multiple reviewers, and have also attached additional figures that -- as requested -- display the relationship between the two raw axes and effective parameter axes across the different methods (Figs 1 and 2) and experiments using an additional dataset of different modality (Fig 3).

**How could we extend this work to neural networks?** (Reviewers  Uot3, tnvy) In addition to the possible connections already stated in our conclusion  l. 356ff., we believe that one very interesting and promising starting point for extending our work to the neural network setting would be to use our approaches for understanding double descent in smoothing models  and apply them to neural networks trained  in the _lazy regime_ (see e.g. ‘On Lazy Training in Differentiable Programming’, Chizat et al, NeurIPS19), as these networks essentially act like models that are linear in features defined through the gradients of the model at initialisation -- to these linearised networks some of our arguments from the linear regression case study may extend very naturally. 

**What is the relationship between the two raw parameter axes and effective parameter count?**  (Reviewers WN4r, tnvy) In the attached Figs. 1&2, we find that along the respective first axes ($P^{leaf}, P^{boost}, P^{PCA}$) effective parameters monotonically increase while along the second axes ($P^{ens}, P^{ex}$), effective parameters monotonically decrease. Thus, this further confirms that (as we had stated in l. 317) the second axis acts by ‘decreasing the effective complexity implied by each value’ along the first axis). We agree that these results provide interesting evidence that compliments Figs 6 & 7 – and will include some of the insights into the updated manuscript once the additional content page becomes available!

**How exactly does adding more $P^{ex}$ improve model performance?** (Reviewers WN4r, tnvy) We agree that this is a very interesting (and nontrivial!) question, whose answer may extend beyond the scope of our original investigation. Below, we discuss our current understanding, but think that exploring this question further would constitute a fruitful direction for future work. 

Reviewer tnvy raised this question while noting that "all the information necessary to predict y should already be encoded in X" and that thus representing it with an increasing number of features (regardless of the conditioning of some matrix) would not seem to explain the improvement in performance. To intuitively address this point, we note that, for example, once p>n, adding additional features indeed does not add any new information for predicting the observed (training inputs) y. Yet, in such underspecified settings, different representations that make the same predictions on training inputs can lead to wildly different generalisation performance to new inputs– despite being indistinguishable on the training data. A basis construction step thus essentially serves to choose between models that all explain y equally well (and hence cannot be distinguished based on supervised loss), akin to an unsupervised pre-processing step. The _implicit inductive bias_ encoded in the step we uncover essentially consists of constructing and choosing the top-$P^{PCA}$ features that _capture the directions of maximum variation_ in the data. 

Within this inductive bias, the role of $P^{ex}$ appears to be that -- as more excess features are added -- the variation $\lambda_p$ captured by each of the top-$P^{PCA}$ principal components is likely to increase (which we indeed see empirically in Appendix B.3). This increase in the $\lambda_p$ in turn is likely to _decrease_ the variance of the regression predictions on unseen inputs because $Var(\hat{y}) = Var(s(x\_0)y)=\sigma^2\sum^{P^{PCA}}\_{p=1} b^2\_p(x\_0)/\lambda\_p$ (where $b(x_0)=(b_1(x_0), ..., b_{P^{PCA}}(x_0))$ is the representation of the input point using the PCs) can explode on the unseen testing inputs when previously unseen large values $b^2\_p(x\_0)$ occur along the low-variance directions with very small $\lambda\_p$ at test time (which is exactly what we observe in our experiments).

Still, using the directions of maximum variation is certainly not guaranteed to be optimal in all applications (Jolliffe, "A note on the use of principal components in regression.",  1982) but it tends to be an effective inductive bias in practice as noted in Tukey (“ Exploratory data analysis.”, 1977) who suggested that the high variance components are likely to be more important for prediction unless nature is "downright mean". However, note that we do not intend to make a claim that increasing $P^{ex}$ is always effective – rather, we are simply uncovering that this appears to be the underlying effect in the RFF experiments.



Meta-review: The paper provides valuable insights into the paradox of double descent curve. Observations on the double descent curve postulate there is a gap between theoretical uniform convergence rate and practical observations. While multiple studies on this observation, the current paper introduces an innovative perspective aimed at bridging the disparity between theory and practice through the introduction of a more precise understanding of complexity. The paper shows that the phenomenon of double descent arises from the amalgamation of two distinct effects within a single plot, potentially leading to confusion. This outcome underscores the need for future practical and theoretical investigations, with the potential to ultimately resolve the paradox inherent in the double descent curve.
Decision: Accept (oral)