How double descent breaks the shackles of the interpolation threshold

Insights for deep learning from solving N equations with N unknowns

Photo by niu niu on Unsplash

How does a deep neural net with a billion parameters perform well and avoid overfitting? Empirically, we know the explanation is related to double descent, the phenomenon where the generalization error (sometimes) goes back down as many more parameters are added — typically after a spike in generalization error at the interpolation threshold. But why does this pattern sometimes happen? There are some math papers developing explanations, but here I help develop intuition.

See, double descent also happens in linear regression, which is more easily understood and explored with simulations. In particular, a system of linear equations with the same number of equations as unknowns is equivalent to a simple linear regressions where the number of rows = number of columns, assuming there is one weight per column. This is a special case because N equations in N unknowns has exactly one solution (assuming full rank of the matrix). The analyst has no wiggle room to modify the solution, even if they “know” the equations came from noisy measurements. In contrast, when there are fewer parameters than equations, there are no solutions, leaving the analyst free to choose a metric to select a “least bad” fit, traditionally least squares (the residual sum of squared errors, or RSS), analytically with a matrix inverse. And when there are more parameters than equations, there are infinitely many solutions, leaving the analyst free to choose a metric to select a “best” solution, usually chosen using a generalized matrix inverse. If that is beginning to sound too mathy, don’t worry. I never heard about a generalized inverse in my statistics or linear algebra classes, but walking through some examples will make clearer how it chooses a solution and how it helps with noisy data.

That’s the heart of breaking the shackles, but there is a prelude and a postlude:

1. Prelude: Examples of the interpolation threshold causing an error spike. I show how to manipulate double descent with a few lines of sklearn code, fitting linear regression on data sampled with different numbers of rows and columns, allowing me to control exactly where the interpolation threshold causes a spike in generalization error.
2. Heart: How solving N equations in N unknowns is analogous to the interpolation threshold, and since there is exactly one solution, it has to fit any noise in the data in one specific way. These are the shackles. And having either fewer unknown parameters or more unknown parameters gives freedom to choose “solutions” that reduce overfitting. Double descent is enabled, but not guaranteed, because there are many solutions for N equations in p unknowns where p >> N.
3. Postlude: How regularization plays a similar role in unshackling our solutions, giving freedom even for fitting N equations in N unknowns. Regularization can eliminate the error spike entirely and does well for a wide range of data sets.

In a way, regularization is the “cheap” way to unshackle the interpolation threshold, although tuning regularization requires a savvy analyst. Regularization can avoid overfitting with a finite data set and finite resources for training. Double descent, if you can achieve it, does even better, as our amazing billion-parameter neural nets illustrate. However, double descent requires massive amounts of training data and expensive compute for training.

I illustrate these ideas here in words and plots and tables, but you can experiment with it yourself using the code in my github repo:

• https://github.com/jeanimal/double_descent_dar/

Why is double descent so interesting?

Double descent is the observation that although a model’s generalization error initially increases with increasing model complexity —i.e. when adding more parameters to the model — the generalization error may descend again when making the model even more complex, with even more parameters.

In this blog and the github repo, I focus on a data set for predicting the fuel efficiency — measured in “miles per gallon” — for 32 models of car using 9 numeric variables, the mtcars data set used in statistics classes. In the case of a simple linear regression, every column has one weight, so we can control the number of parameters simply by controlling the number of columns. Then I use “resampling”, drawing sub-samples of data from the full data set. I fit regressions on a resampled set of 15 car models but varied the number of columns sampled. In the example below (figure 1) from my simulations, the minimum generalization error was achieved with 3 sampled columns. The U-shape is typical: as we add parameters, error due to bias gets lower while error due to sampling variance increases, known as the the bias-variance trade-off.

Figure 1. The generalization error (“test” in blue) has a typical U-shaped curve. Error initial decreases with more sampled columns (parameter to be fit) but then error increases. The points are averages from fitting linear regression to a resampled data set — see my github.

I will then re-run the simulations using a data set where I add noisy columns of data to create 30 parameters in the data set. Now the generalization error has a typical doulbe descent shape. Error is low around 3 columns, peaks at 6 columns, then has a second descent in generalization error, shown below in figure 2.

Figure 2. The generalization error (“test” in blue) has a double descent. After the error spiked at 6 sampled columns (parameters to fit), error descended again as more sampled columns were added. The points are averages from fitting linear regression to a resampled data set trained on 7 rows. Plot generated in my github.

Various researchers have been developing the mathematical theory of how and in what conditions linear regression can exhibit double descent, including a paper by Dar et al. (2023). Not every billion-parameter neural net or 30-parameter linear regression will perform well. But the math complicated. Visual examples, like the ones I showed above, are better for intuition. And by varying data and model parameters, we can better understand when double descent does and doesn’t happen in a linear regression, which sheds some light on the phenomenon in neural nets.

Which error?

The plots above showed only test error. Below, figure 1b, is the same as figure 1 but adds error on the training data set, labelled “train.” The train error is artificially low as the number of parameter increase. At the interpolation threshold, train error is akin to memorizing exam questions, e.g the Mazda RX4 has a fuel efficiency of 21 mpg. The test error is a better measure of the model’s “understanding” of the patterns in the data, e.g. that heavier cars have lower fuel efficiency.

Figure 1b. Average training error (“train” in orange) and generalization error (“test” in blue). Train error always decreases for more number of sampled columns but generalization error is more complicated. Code to generate is at my github.

The parameterization ratio and the interpolation threshold

A photographic memory is a useful analogy for understanding a model’s “interpolation threshold,” a key turning point in model generalization behavior. Interpolation is when the model has exactly enough free parameters to fit the data perfectly. That is, if you trained a model on N car models (or examples or data points) and the model had p parameters, then your model can exactly fit every data point– that is, interpolate– when p = N (assuming a full rank matrix).

This leads to the idea of a parameterization ratio, p/N, which lets us classify different regimes:

• When p < N (num_columns < num_rows in a simple regression), the parameterization ratio is < 1, and the model is “underparameterized.”
• When p=N, the parameterization ratio is 1, and the model is at the interpolation threshold.
• When p > N (num_columns > num_rows), the parameterization ratio is > 1, and the model is “overparameterized.” There are many possible combinations of the p parameter values the that would fit the N data points perfectly.

Figure 3 below visually explores these three regimes. The x axis is a proxy of the parameterization ratio. The U curve labeled “bias-variance tradeoff” is in the underparameterized region. The double descent curve (when it occurs) is in the overparameterized region. The transition point is the interpolation threshold.

Figure 3. The regions of test error behavior. For linear regression, the x axis is number of parameters. This diagram is figure 1 from Dar et al. (2021).

Prelude: How to manipulate the parameterization ratio

Although data sets typically come with a fixed number of rows and columns, we can manipulate these with resampling, allowing us to explore changes in error with changes in the parameterization ratio.

How the python library makes the parameterization ratio obvious

Python’s sklearn library is wonderful but is not designed for manipulating the parameterization ratio directly, so I wrote a wrapper to help.

sklearn lets you specify a proportion of data to train on, e.g. to train on 50% of the data, we would call: train_test_split(X, y, train_size=0.5) . The training size actually samples the rows by percent, and there is no way to sample columns. So you would have to calculate the parameterization ratio.

My library is a wrapper that let you specify the number of rows and columns for training directly, so we know the parameterization ratio. For example, to do a run at the interpolation threshold, we would call: test_train_split_by_rows_and_cols(X, y, num_rows=8, num_columns=8). In the diagrams above, I held fixed the number of rows and then tried differing numbers of columns. Under the right conditions, we see a U when num_columns < num_rows, then a peak at the interpolation threshold when num_colums = num_rows, and reach the interpolation regime when num_columns > num_rows. I will soon talk more about why these patterns happen. But I first want to discuss some data issues.

Munging the data set

The obvious way to get to the overparameterized regime is to increase p, the number of parameters fit. However, the mtcars data set had only 9 columns, meaning the only way to reach overparameterized regime was to train on less than 9 rows, which is pretty limiting.

So another technique I used was to artifically increase the number of columns. Inspired by a paper by Dar et al. (2021) that indicated double descent for linear regression was most likely to happen when there was a low-dimensional signal in noisy data, I added 20 columns of random noise. This created a data set of 9 + 20 = 29 columns, allowing me to increase the number of rows much more to get a bigger overparameterized regime. It also gave a much clearer “double descent” shape. The rest of the diagrams use this data set of mtcars + random noise.

Putting it all together

Put that all together, and we can show a beautiful demonstration of how the interpolation threshold — the “peak” that leads to double descent — can be shifted.

Figure 4 shows five variants of double descent, each training on one more row and thus moving the interpolation threshold and peak to the right by one sampled column. Specifically:

• The top diagram trained on 3 rows and had error peak at 3 columns.
• The 2nd diagram trained on 4 rows and peaked at 4 columns.
• The 3rd diagram trained on 5 rows and peaked at 5 columns

And so on. We can control the interpolation threshold at will.

Figure 4. Diagram moving the peak generalization error, the threshold beyond which we observe double descent, simply by changing how many rows are sampled for the training data set. Plot generated in my github.

Why? The shackles!

Okay, so now you are convinced that the interpolation threshold is important and controls the start of double descent. But why? Why does the first point where train error can be zero (because num_rows = num_columns) cause a spike in test error ?

Well, when we solve systems of linear equations with algebra, there are three cases:

• number of parameters < number of equations. No solutions.
• number of parameters = number of equations. One solution
• number of parameters > number of equations. Many solutions.

But if the equations were derived from empirical measurements, there may have been some noise. For example, maybe there was “no solution” only because someone measured something wrong. How could we find “best fit” parameters anyway? So the above three cases translate into three cases for statistical models trained on data that is num_rows x num_columns:

• num_columns < num_rows: When models are underparameterized, they cannot be fitted perfectly, so you have to use a technique to get the “closest” fit. If that technique does a good job of distinguishing signal from noise, it will generalize well.
• num_columns = num_rows: When a linear system of equations has the same number of equations as unknowns, there is a unique solution. If there is noise, in the data, that means the “solution” is actually fitting signal AND noise. That won’t generalize well but there’s nothing you can do about it.
• num_columns > num_rows: When models are overparameterized, there are many solutions. While that might seem bad, it also gives us an opportunity to use a technique to choose a solution that generalizes well.

Put another way, only the case of num_columns = num_rows handcuffs the savvy analyst — there is no freedom to try techniques to select paramters might generalize better. (But regularization will offer a way out as I explain later.)

To make these statements more concrete, let’s look at examples for solving a linear system of equations for interpolation, underparameterization, and overparameterization.

Interpolation

Let’s start with interpolation, when the number of equations equals the number of unknowns. The simplest case is one equation with one unknown. Here is an example:

10 = 2x

There is exactly one solution, x=5. In the more general case of N equations and N unknowns, we use the inverse matrix to find the solution (assuming full rank).

Underparameterization

In underparameterization, there are fewer parameters than equations, so let’s add one more equation. Suppose we want to solve this:

10 = 2x
10 = 5x

Now, obviously no x could satisfy both equations. But suppose each equation came from data collected for two types of cars, where 10 was the fuel efficiency, and 2 and 5 were the number of pistons in the engine. Then x indicates the “true,” non-noisy impact of number of pistons on fuel efficiency. With that framing, the question becomes: what value of x would mostly likely capture the “signal” that will generalize well and ignore all the noise?

The typical way to choose parameter values in the underparameterized case is with ordinary least squares (OLS). For each possible value of x, we calculate how far it is using the squared residual, (ŷ-y)², and then sum across all the data points (equations). This sum is called the “residual sum of squares,” or “RSS”). Below is a table where each row is a posited value of x, its predictions ŷ=2x and ŷ=5x, and the resulting RSS. Rember all of these x’s are “non-solutions” because they cannot solve the system of equations, but RSS tells us how close they get.

Figure 5. For each value of X, this tells us how close it gets to solving the equations 2x=10 and 5x=10. The RSS is the residual sum of squares across both equations.

Ordinary least squares (OLS) chooses the value of x that minimizes the RSS, which would be x=2.5, with an RSS of 31.25.

This grid search did not find the exact minimum, but it’s close. The exact minimum can be solved analytically by finding the x that minimizes:

RSS = (2x-10)^2 + (5x-10)^2

The minimum RSS is x=140/58, which is approximately 2.41, so we got pretty close with x=2.5. The RSS is essentially the training error, if we are using a sum of squares error. Conveniently, it turns out that the OLS-selected parameter values can generalize well, but performance depends on the bias-variance trade-off, which well-studied.

In any case, the point is that the underparameterized case does not have an exact solution, which gives the analyst some freedom in the method to pick a “close” solution, and that method might generalize better or worse.

Overparameterization

Now consider the overparameterized case. The simplest overparameterization is one equation with two unknowns. So let’s add one more parameter to the original equation:

10 = 2x + 4y

We obviously can’t solve that! There are many — infinitely many — possible solutions. The good news is that having all these solutions gives the savvy analyst the freedom in choosing a method for picking one solution.

I list a few possible options for x and y in figure 5. Every row would result in x2+4y having a value of 10. The RSS for every row is 0, so RSS cannot be used as a guide for picking one set of parameter values.

Figure 6. Some possible solutions for 10 = 2x + 4y. Since they all solve the equation, all have a residual sum of squares (RSS) of 0.

One common method is to choose the (x, y) solution that is closest to (0, 0). That means choosing the pair with the shortest distance, x² + y², also called the L2 norm. The L2 values for every row are shown in figure 7.

Figure 7. Some possible solutions for 10 = 2x + 4y and the parameters’ distance from (0, 0), known as the L2 norm.

Figure 7 shows that the L2-minimizing solution is (x=2, y=4), and in this case the grid search has performed perfectly, getting the same answer as found analytically. The analytical solution to minimize the L2 norm can be found using the Moore-Penrose inverse, a form of generalized matrix inverse, to solve the system of equations.

Empirically, minimizing the L2 norm often has good generalization performance. The Moore-Penrose inverse is implemented in sklearn’s linear regression model solver, so all the plots you saw above that had a linear regression with low error in the overparameterized regime can be credited to using the minimum L2 norm to choose which solution would be used.

Reflection

It is perhaps ironic that the situation that high school algebra would indicate was best — N equations with N unknowns — turns out to be the worst when we sprinkle in some noise. That is at least in part because it can be solved perfectly, and thus we have no wiggle room to avoid fitting noise. Luckily, regularization will provide some wiggle room.

Postlude: Escape through regularization

Regularization is a collection of techniques to “regularize” parameters with the goal of preventing overfitting. These techniques shrink the parameter space closer to a region or pattern that we have a priori reasons to believe will generalize better. For example, the L2 norm prefers parameters closer Euclidean distance to the origin of (0, 0).

Typically, regularization defines a new metric to be minimized that includes both the error term (RSS) and a term that regularizes the parameter space. For example, ridge regression minimizes a weighted sum of RSS and the L2 norm, where 𝛼 is the hyperparameter to control how much regularization to apply:

ridge = RSS +𝛼* L2

For 𝛼 = 0, there is no regularization and the metric becomes ordinary least squares regression (OLS) because only RSS is minimized. In the examples below, I use 𝛼=1.0 to give equal weight to the error term (RSS) and the regularizer (L2). I will first show some examples of how we use this new metric to select solutions beyond the RSS=0 restriction, giving us more freedom. This is particularly important in interpolation case. And then I will demonstrate empirically how regularization improves generalization error

Overparameterized ridge

Let’s start with the overparameterized case. Below are the sample values of the overparameterized fit with the ridge term added as an additional column. I also added a NEW set of (x, y) values that no longer exactly solve the equation.

Figure 8. Selecting (x, y) that minimize the ridge term in an overparameterized linear equation system (1 equation with 2 unknowns).

We find a new minimum at (x=0.95, y=1.9) because it has the minimum ridge term, even though its prediction has a small error, having an RSS 0f 0.3025 rather than zero.

Thus, the ridge term gives us the freedom to explore the parameter space away from RSS=0. Importantly, it only increases RSS in the direction of parameter space we believe is likely to generalize better, which in the case of the L2 norm means closer to the origin.

No-longer-interpolating ridge

But even more important is the effect of regularization on the interpolation case, when there are N equations in N unknowns and no freedom.

Recall our example of one equation and one unknown:

10 = 2x

There was exactly one solution, x=5. But with ridge regression, we no longer require exact solutions. Let us calculate the ridge term for some neighboring values of x.

Figure 9. Selecting (x, y) that minimize the ridge term in an interpolated linear equation system (1 equation in 1 unknown).

Previously we chose x=5.0 because the RSS was zero — it was our only option. With ridge regression, we choose x=4.0 because it minimizes the ridge term. Ridge regression provides some freedom to choose in the interpolation case, which had previously offered no freedom.

4.0 or 5.0 might seem like a slight difference — who needs a slightly different value of x? But in fact, we brought x closer to a region we believed would generalize better. And now I show that indeed ridge regression leads to better generalization in the data set I studied.

Ridge regression generalization error

With ridge regression and 𝛼=1.0, I re-ran the experiment in figure 2, which trained with 7 rows of the mt_cars data set. Figure 10 shows the generalization error with ridge regression.

Figure 10. Generalization error for ridge regression trained on 7 sampled rows of the mtcars data set but with varying numbers of sampled columns. Plot generated in my github.

With OLS, we saw a big spike in generalization error when at 7 sampled columns, the interpolation threshold becuase ittrained on 7 rows. With ridge regressions, the huge spike in error at the interpolation threshold is gone. Instead, the more columns of data were provided in training, the more generalization error went down until it plateau at about 3.5.

The effect of regularization is even more dramatically obvious if we compare generalization error on the same graph with the ordinary least squares error, as shown below in figure 11.

Figure 11. Comparison of generalization error for ridge regression (“ridge” in blue) and ordinary least squares (“OLS” in orange), both trained on 7 sampled rows of the mtcars data set but varying numbers of sampled columns. OLS has a spike in error at the interpolation threshold of 7 columns but ridge regression does not. Plot generated in my github.

Conclusions

So what are the lessons learned? First, double descent is a widespread phenomenon and does not only happen in neural nets. Under the right conditions, we can easily reproduce it with simple linear regression.

Second, we can manipulate double descent by controling exactly where the interpolation threshold appears. In simple linear regression, where one column maps to one parameter weight, this is done by creating training sets where num_rows = num_columns. In neural nets, there are additional parameters hidden in the layers, but the principle is the same: the data can be exactly memorized when the number of parameters is the same as the number of rows or examples in the training set.

Back to linear models and the inution they bring. A system of linear equations with the same number of equations as unknowns (num_rows = num_columns) is special: it is the only case where the solution is dictated. The analyst has no wiggle room to modify the solution, even if they “know” the equations came from noisy measurements. Luckily, regularization provides some freedom in choosing parameter values and “encourages” the parameters to go closer to regions we believe generalize better. The L2 norm, for example, encourages all parameters to fit closer to the origin.

Regularization is of course widely used in neural nets, too. L1 and L2 norms are also often included in the loss functions that gradient descent minimizes. There are also neural-net specific techniques for regularization, such as dropout, which randomly removes some neurons during back-propagation passes.

But regularization is the “cheap” way of dealing with the problem of overfitting. If you have massive amounts of data, and the right kind of data patterns (including those discovered by Dar et al 2021), you might not need regularization because you could harness the benefits of double descent. With double descent, additional parameters keep lowering generalization error. You can improve performance by going from a million-parameter neural net to a billion-parameter neural net. It’s expensive to collect the data and expensive to train, but if you can afford it, performance just keeps getting better — thanks to double descent.

See also

Daniela Witten has a nice spline-based visual explanation of interpolation and double descent: https://x.com/daniela_witten/status/1292293102103748609

I also have a blog post that elucidate the types of data sets that are more likely to exhibit double descent after the interpolation threshold — because not all data sets do. In short, data sets having a lot of mis-specified features, such as incidentally collected data from logs of online systems, are more likely to enable double descent than data sets with a handful of features curated by humans for the specific task at hand.

Acknowledgements

Thank you to Dan Goldstein for asking me probing questions about my previous double descent post, pushing me to explain more. Thank you to Pablo Montero Manso for improving my explanations even though he is not a fan of the “unshackling” analogy.

References

Yehuda Dar, V. Muthukumar, and R. Baraniuk, 2021, “A Farewell to the Bias-Variance Tradeoff? An Overview of the Theory of Overparameterized Machine Learning,” Cornell University, Sep. 06, 2021. Accessed: Oct. 28, 2021. [Online]. Available: https://arxiv.org/abs/2109.02355

My github repos:

• python with sklearn: https://github.com/jeanimal/double_descent_dar/
• double descent in R (older code more focused on my previous blog post): https://github.com/jeanimal/farewell_bias_variance