[AN #77]: Double descent: a unification of statistical theory and modern ML practice

post by Rohin Shah (rohinmshah) · 2019-12-18T18:30:01.862Z · LW · GW · 4 comments

Contents

    Highlights
  Technical AI alignment
      Problems
  AI strategy and policy
  Other progress in AI
      Deep learning
  News
None
4 comments

Find all Alignment Newsletter resources here. In particular, you can sign up, or look through this spreadsheet of all summaries that have ever been in the newsletter. I'm always happy to hear feedback; you can send it to me by replying to this email.

Audio version here (may not be up yet).

Highlights

Deep Double Descent (Preetum Nakkiran et al) (summarized by Rohin): This blog post provides empirical evidence for the existence of the double descent phenomenon, proposed in an earlier paper summarized below. Define the effective model complexity (EMC) of a training procedure and a dataset to be the maximum size of training set such that the training procedure achieves a train error of at most ε (they use ε = 0.1). Let's suppose you start with a small, underparameterized model with low EMC. Then initially, as you increase the EMC, the model will achieve a better fit to the data, leading to lower test error. However, once the EMC is approximately equal to the size of the actual training set, then the model can "just barely" fit the training set, and the test error can increase or decrease. Finally, as you increase the EMC even further, so that the training procedure can easily fit the training set, the test error will once again decrease, causing a second descent in test error. This unifies the perspectives of statistics, where larger models are predicted to overfit, leading to increasing test error with higher EMC, and modern machine learning, where the common empirical wisdom is to make models as big as possible and test error will continue decreasing.

They show that this pattern arises in a variety of simple settings. As you increase the width of a ResNet up to 64, you can observe double descent in the final test error of the trained model. In addition, if you fix a large overparameterized model and change the number of epochs for which it is trained, you see another double descent curve, which means that simply training longer can actually correct overfitting. Finally, if you fix a training procedure and change the size of the dataset, you can see a double descent curve as the size of the dataset decreases. This actually implies that there are points in which more data is worse, because the training procedure is in the critical interpolation region where test error can increase. Note that most of these results only occur when there is label noise present, that is, some proportion of the training set (usually 10-20%) is given random incorrect labels. Some results still occur without label noise, but the resulting double descent peak is quite small. The authors hypothesize that label noise leads to the effect because double descent occurs when the model is misspecified, though it is not clear to me what it means for a model to be misspecified in this context.

Rohin's opinion: While I previously didn't think that double descent was a real phenomenon (see summaries later in this email for details), these experiments convinced me that I was wrong and in fact there is something real going on. Note that the settings studied in this work are still not fully representative of typical use of neural nets today; the label noise is the most obvious difference, but also e.g. ResNets are usually trained with higher widths than studied in this paper. So the phenomenon might not generalize to neural nets as used in practice, but nonetheless, there's some real phenomenon here, which flies in the face of all of my intuitions.

The authors don't really suggest an explanation; the closest they come is speculating that at the interpolation threshold there's only ~one model that can fit the data, which may be overfit, but then as you increase further the training procedure can "choose" from the various models that all fit the data, and that "choice" leads to better generalization. But this doesn't make sense to me, because whatever is being used to "choose" the better model applies throughout training, and so even at the interpolation threshold the model should have been selected throughout training to be the type of model that generalized well. (For example, if you think that regularization is providing a simplicity bias that leads to better generalization, the regularization should also help models at the interpolation threshold, since you always regularize throughout training.)

Perhaps one explanation could be that in order for the regularization to work, there needs to be a "direction" in the space of model parameters that doesn't lead to increased training error, so that the model can move along that direction towards a simpler model. Each training data point defines a particular direction in which training error will increase. So, when the number of training points is equal to the number of parameters, the training points just barely cover all of the directions, and then as you increase the number of parameters further, that starts creating new directions that are not constrained by the training points, allowing the regularization to work much better. (In fact, the original paper, summarized below, defined the interpolation threshold as the point where number of parameters equals the size of the training dataset.) However, while this could explain model-wise double descent and training-set-size double descent, it's not a great explanation for epoch-wise double descent.

Read more: Paper: Deep Double Descent: Where Bigger Models and More Data Hurt

Technical AI alignment

Problems

Comment on Coherence arguments do not imply goal directed behavior [LW · GW] (Ronny Fernandez) (summarized by Rohin): I have argued [AF · GW] (AN #35) that coherence arguments that argue for modeling rational behavior as expected utility maximization do not add anything to AI risk arguments. This post argues that there is a different way in which to interpret these arguments: we should only model a system to be an EU maximizer if it was the result of an optimization process, such that the EU maximizer model is the best model we have of the system. In this case, the best way to predict the agent is to imagine what we would do if we had its goals, which leads to the standard convergent instrumental subgoals.

Rohin's opinion: This version of the argument seems to be more a statement about our epistemic state than about actual AI risk. For example, I know many people without technical expertise who anthropomorphize their laptops as though they were pursuing some goal, but they don't (and shouldn't) worry that their laptops are going to take over the world. More details in this comment [LW(p) · GW(p)].

AI strategy and policy

How does the offense-defense balance scale? (Ben Garfinkel et al) (summarized by Flo): The offense-defense balance that characterises how easy it is to successfully attack others can affect what kinds of conflicts break out and how often that happens. This paper analyses how growing capabilities on both sides affect that balance. For example, consider an idealized model of cyber defense with a fixed set of vulnerabilities that are discovered independently by attackers and defenders. The attacker will initially be able to use almost all of the vulnerabilities they found. This is because, with only a small percentage of vulnerabilities discovered by both sides, the defender is unlikely to have found the same ones as the attacker. Marginal increases of the defender's capabilities are unlikely to uncover vulnerabilities used by the attacker in this regime, such that attacks become easier as both sides invest resources. Once most vulnerabilities have been found by both sides, this effect reverses as marginal investments by the attacker become unlikely to uncover vulnerabilities the defender has not fixed yet.

This pattern, where increasingly growing capabilities first favour offense but lead to defensive stability in the long run, dubbed OD-scaling seems to be common and can be expected to be found whenever there are multiple attack vectors, the attacker only needs to break through on some of them and the defender enjoys local defense superiority, meaning that with sufficient coverage by the defender for a given attack vector, it is almost impossible for the attacker to break through.

Because the use of digital and AI systems can be scaled up quickly, scale-dependent shifts of the offense-defense balance are going to increase in importance as these systems become ubiquitous.

Flo's opinion: I found it quite surprising that the paper mentions a lack of academic consensus about whether or not offensive advantage is destabilizing. Assuming that it is, OD-scaling might provide a silver lining concerning cybersecurity, provided things can be scaled up sufficiently. These kinds of dynamics also seem to put a natural ceiling on arms races: above a certain threshold, gains in capabilities provide advantage to both sides such that resources are better invested elsewhere.

Other progress in AI

Deep learning

Reconciling modern machine learning practice and the bias-variance trade-off (Mikhail Belkin et al) (summarized by Rohin): This paper first proposed double descent as a general phenomenon, and demonstrated it in three machine learning models: linear predictors over random Fourier features, fully connected neural networks with one hidden layer, and forests of decision trees. Note that they define the interpolation threshold as the point where the number of parameters equals the number of training points, rather than using something like effective model complexiy.

For linear predictors over random Fourier features, their procedure is as follows: they generate a set of random features, and then find the linear predictor that minimizes the squared loss incurred. If there are multiple predictors that achieve zero squared loss, then they choose the one with the minimum L2 norm. The double descent curve for a subset of MNIST is very pronounced and has a huge peak at the point where the number of features equals the number of training points.

For the fully connected neural networks on MNIST, they make a significant change to normal training: prior to the interpolation threshold, rather than training the networks from scratch, they train them from the final solution found for the previous (smaller) network, but after the interpolation threshold they train from scratch as normal. With this change, you see a very pronounced and clear double descent curve. However, if you always train from scratch, then it's less clear -- there's a small peak, which the authors describe as "clearly discernible", but to me it looks like it could be noise.

For decision trees, if the dataset has n training points, they learn decision trees of size up to n leaves, and then at that point (the interpolation threshold) they switch to having ensembles of decision trees (called forests) to get more expressive function classes. Once again, you can see a clear, pronounced double descent curve.

Rohin's opinion: I read this paper back when summarizing Are Deep Neural Networks Dramatically Overfitted? (AN #53) and found it uncompelling, and I'm really curious how the ML community correctly seized upon this idea as deserving of further investigation while I incorrectly dismissed it. None of the experimental results in this paper are particularly surprising to me, whereas double descent itself is quite surprising.

In the random Fourier features and decision trees experiments, there is a qualitative difference in the learning algorithm before and after the interpolation threshold, that suffices to explain the curve. With the random Fourier features, we only start regularizing the model after the interpolation threshold; it is not surprising that adding regularization helps reduce test loss. With the decision trees, after the interpolation threshold, we start using ensembles; it is again not at all surprising that ensembles help reduce test error. (See also this comment [AF(p) · GW(p)].) So yeah, if you start regularizing (via L2 norm or ensembles) after the interpolation threshold, that will help your test error, but in practice we regularize throughout the training process, so this should not occur with neural nets.

The neural net experiments also have a similar flavor -- the nets before the interpolation threshold are required to reuse weights from the previous run, while the ones after the interpolation threshold do not have any such requirement. When this is removed, the results are much more muted. The authors claim that this is necessary to have clear graphs (where training risk monotonically decreases), but it's almost certainly biasing the results -- at the interpolation threshold, with weight reuse, the test squared loss is ~0.55 and test accuracy is ~80%, while without weight reuse, test squared loss is ~0.35 and test accuracy is ~85%, a massive difference and probably not within the error bars.

Some speculation on what's happening here: neural net losses are nonconvex and training can get stuck in local optima. A pretty good way to get stuck in a local optimum is to initialize half your parameters to do something that does quite well while the other half are initialized randomly. So with weight reuse we might expect getting stuck in worse local optima. However, it looks like the training losses are comparable between the methods. Maybe what's happening is that with weight reuse, the half of parameters that are initialized randomly memorize the training points that the good half of the parameters can't predict, which doesn't generalize well but does get low training error. Meanwhile, without weight reuse, all of the parameters end up finding a good model that does generalize well, for whatever reason it is that neural nets do work well.

But again, note that the authors were right about double descent being a real phenomenon, while I was wrong, so take all this speculation with many grains of salt.

More Data Can Hurt for Linear Regression: Sample-wise Double Descent (Preetum Nakkiran) (summarized by Rohin): This paper demonstrates the presence of double descent (in the size of the dataset) for unregularized linear regression. In particular, we assume that each data point x is a vector in independent samples from Normal(0, σ^2), and the output is y = βx + ε. Given a dataset of (x, y) pairs, we would like to estimate the unknown β, under the mean squared error loss, with no regularization.

In this setting, when the dimensionality d of the space (and thus number of parameters in β) is equal to the number of training points n, the training data points are linearly independent almost always / with probability 1, and so there will be exactly one β that solves the n linearly independent equalities of the form βx = y. However, such a β must also be fitting the noise variables ε, which means that it could be drastically overfitted, with very high norm. For example, imagine β = [1, 1], so that y = x1 + x2 + ε, and in our dataset x = (-1, 3) is mapped to y = 3 (i.e. an ε of +1), and x = (0, 1) is mapped to y = 0 (i.e. an ε of -1). Gradient descent will estimate that β = [-3, 0], which is going to generalize very poorly.

As we decrease the number of training points n, so that d > n, there are infinitely many settings of the d parameters of β that satisfy the n linearly independent equalities, and gradient descent naturally chooses the one with minimum norm (even without regularization). This limits how bad the test error can be. Similarly, as we increase the number of training points, so that d < n, there are too many constraints for β to satisfy, and so it ends up primarily modeling the signal rather than the noise, and so generalizing well.

Rohin's opinion: Basically what's happening here is that at the interpolation threshold, the model is forced to memorize noise, and it has only one way of doing so, which need not generalize well. However, past the interpolation threshold, when the model is overparameterized, there are many models that successfully memorize noise, and gradient descent "correctly" chooses one with minimum norm. This fits into the broader story being told in other papers that what's happening is that the data has noise and/or misspecification, and at the interpolation threshold it fits the noise in a way that doesn't generalize, and after the interpolation threshold it fits the noise in a way that does generalize. Here that's happening because gradient descent chooses the minimum norm estimator that fits the noise; perhaps something similar is happening with neural nets.

This explanation seems like it could explain double descent on model size and double descent on dataset size, but I don't see how it would explain double descent on training time. This would imply that gradient descent on neural nets first has to memorize noise in one particular way, and then further training "fixes" the weights to memorize noise in a different way that generalizes better. While I can't rule it out, this seems rather implausible to me. (Note that regularization is not such an explanation, because regularization applies throughout training, and doesn't "come into effect" after the interpolation threshold.)

Understanding “Deep Double Descent” [AF · GW] (Evan Hubinger) (summarized by Rohin): This post explains deep double descent (in more detail than my summaries), and speculates on its relevance to AI safety. In particular, Evan believes that deep double descent shows that neural nets are providing strong inductive biases that are crucial to their performance -- even after getting to ~zero training loss, the inductive biases continue to do work for us, and find better models that lead to lower test loss. As a result, it seems quite important to understand the inductive biases that neural nets use, which seems particularly relevant for e.g. mesa optimization and pseudo alignment (AN #58).

Rohin's opinion: I certainly agree that neural nets have strong inductive biases that help with their generalization; a clear example of this is that neural nets can learn randomly labeled data (which can never generalize to the test set), but nonetheless when trained on correctly labeled data such nets do generalize to test data. Perhaps more surprising here is that the inductive biases help even after fully capturing the data (achieving zero training loss) -- you might have thought that the data would swamp the inductive biases. This might suggest that powerful AI systems will become simpler over time (assuming an inductive bias towards simplicity). However, this is happening in the regime where the neural nets are overparameterized, so it makes sense that inductive biases would still play a large role. I expect that in contrast, powerful AI systems will be severely underparameterized, simply because of how much data there is (for example, the largest GPT-2 model still underfits the data (AN #46)).

Uniform convergence may be unable to explain generalization in deep learning (Vaishnavh Nagarajan) (summarized by Rohin): This post argues that existing generalization bounds cannot explain the empirical success of neural networks at generalizing to the test set.

"What?", you say if you're like me, "didn't we already know this? Generalization bounds depend on your hypothesis space being sufficiently small, but neural nets can represent any reasonable function? And even if you avoid that by considering the size of the neural net, we know that empirically neural nets can learn randomly labeled data, which can never generalize; surely this means that you can't explain generalization without reference to some property of the dataset, which generalization bounds typically don't do?"

It turns out that the strategy has been to prove generalization bounds that depend on the norm of the weights of the trained model (for some norm that depends on the specific bound), which gets around both these objections, since the resulting bounds are independent of the number of parameters, and depend on the trained model (which itself depends on the dataset). However, when these bounds are evaluated on a simple sphere-separation task, they increase with the size of the training dataset, because the norms of the trained models increase.

Okay, but can we have a stronger argument than mere empirical results? Well, all of these bounds depend on a uniform convergence bound: a number that bounds the absolute difference between the train and test error for any model in your hypothesis space. (I assume the recent generalization bounds only consider the hypothesis space "neural nets with norms at most K", or some suitable overapproximation of that, and this is how they get a not-obviously-vacuous generalization bound that depends on weight norms. However, I haven't actually read those papers.)

However, no matter what hypothesis space these bounds choose, to get a valid generalization bound the hypothesis space must contain (nearly) all of the models that would occur by training the neural net on a dataset sampled from the underlying distribution. What if we had the actual smallest such hypothesis space, which only contained the models that resulted from an actual training run? The authors show that, at least on the sphere-separation task, the uniform convergence bound is still extremely weak. Let's suppose we have a training dataset S. Our goal is now to find a model in the hypothesis space which has a high absolute difference between actual test error, and error in classifying S. (Recall that uniform convergence requires you to bound the absolute difference for all models in your hypothesis class, not just the one trained on S.) The authors do so by creating an "adversarial" training dataset S' that also could have been sampled from the underlying distribution, and training a model on S'. This model empirically gets S almost completely wrong. Thus, this model has low test error, but high error in classifying S, which forces the uniform convergence bound to be very high.

Rohin's opinion: I enjoyed this blog post a lot (though it took some time to digest it, since I know very little about generalization bounds). It constrains the ways in which we can try to explain the empirical generalization of neural networks, which I for one would love to understand. Hopefully future work will explore new avenues for understanding generalization, and hit upon a more fruitful line of inquiry.

Read more: Paper

Understanding the generalization of ‘lottery tickets’ in neural networks (Ari Morcos et al) (summarized by Flo): The lottery ticket hypothesis (AN #52) states that a randomly initialized dense or convolutional neural network contains (sparse) subnetworks, called "winning tickets", which can be trained to achieve performance similar to the trained base network while requiring a lot less compute.

The blogpost summarizes facebook AI's recent investigations of the generalization of winning tickets and the generality of the hypothesis. Because winning tickets are hard to find, we would like to reuse the ones we have found for similar tasks. To test whether this works, the authors trained classifiers, pruned and reset them to obtain winning tickets on different image datasets and then trained these on other datasets. Winning tickets derived from similar datasets relevantly outperform random subnetworks after training and ones derived from larger or more complex datasets generalize better. For example, tickets from ImageNet are consistently among the best and tickets from CIFAR-100 generalize better than those from CIFAR-10.

Experiments in natural language processing and reinforcement learning suggest that the lottery ticket hypothesis is not just a peculiarity of image classification: for example, the performance of a large transformer model could be recovered from a winning ticket with just a third of the original weights, whereas random tickets with that amount of weights performed quite a bit worse. The analysis of simple shallow neural networks in a student-teacher setting is used as a toy model: when a larger student network is trained to mimic a smaller teacher with the same amount of layers, student specialization happens: some of the student's neurons learn to imitate single neurons of the teacher. This can be seen to happen more often and faster if the student neuron is already close to the teacher neuron at initialization. If the student network is large enough, every teacher neuron will be imitated by some student neuron and these student neurons collectively form a winning ticket.

Flo's opinion: I enjoyed reading this blogpost and like the idea of using winning tickets for transfer learning. I would have been quite surprised if they had found that the lottery ticket hypothesis was specific to image classification, as similar to pretraining, winning tickets seem to provide an inductive bias constraining the set of features that can be learnt during training to more useful ones. I do not think that further research into that direction will directly help with quickly training models for novel tasks unless the tickets can be identified very efficiently which seems like a harder optimization problem than just training a network by gradient descent.

Recent Progress in the Theory of Neural Networks [AF · GW] (interstice)

News

AI Safety Camp Toronto (summarized by Rohin): The next AI safety camp (AN #10) will be held in early May, in Toronto. Apply here by Jan 5.

4 comments

Comments sorted by top scores.