Reconciling modern machine learning and the bias-variance trade-off
machine learning bias variance tradeoff generalization overfitting interpolation parameters model class complexity deep learning neural networks overparameterization erm random fourier features
It turns out that the classic view of generalization and overfitting is incomplete! If you add parameters beyond the number of points in your dataset, generalization performance might increase again due to the increased smoothness of overparameterized functions.

Abstract:
The question of generalization in machine learning---how algorithms are able to learn predictors from a training sample to make accurate predictions out-of-sample---is revisited in light of the recent breakthroughs in modern machine learning technology. 
The classical approach to understanding generalization is based on bias-variance trade-offs, where model complexity is carefully calibrated so that the fit on the training sample reflects performance out-of-sample. 
However, it is now common practice to fit highly complex models like deep neural networks to data with (nearly) zero training error, and yet these interpolating predictors are observed to have good out-of-sample accuracy even for noisy data. 
How can the classical understanding of generalization be reconciled with these observations from modern machine learning practice? 
In this paper, we bridge the two regimes by exhibiting a new "double descent" risk curve that extends the traditional U-shaped bias-variance curve beyond the point of interpolation. 
Specifically, the curve shows that as soon as the model complexity is high enough to achieve interpolation on the training sample---a point that we call the "interpolation threshold"---the risk of suitably chosen interpolating predictors from these models can, in fact, be decreasing as the model complexity increases, often below the risk achieved using non-interpolating models. 
The double descent risk curve is demonstrated for a broad range of models, including neural networks and random forests, and a mechanism for producing this behavior is posited.

Authors: Mikhail Belkin, Daniel Hsu, Siyuan Ma, Soumik Mandal

https://arxiv.org/abs/1812.11118
 Hi there! Today we're looking at reconciling modern machine learning and the bias-variance trade-off by Mikhail Belkin et al. This paper struck me as interesting at ICML when I heard a talk by Mikhail Belkin. The paper is very interesting in terms of what it proposes about modern machine learning. What's the problem? The problem is they contrast what they call classical machine learning and how to understand machine learning, namely in terms of bias-variance trade-offs, and modern machine learning where it's for example deep neural networks which have very different properties. Basically the best way to describe it is probably with an example. Let's say we have four data points. Here is a coordinate system in two dimensions. One, two, three, four. Four data points. Why not? These four data points we want to fit a function from X to Y. Y is our target. It's kind of a regression problem. Let's say we have just one parameter which we can use to describe our function. Probably the best thing we could do is to do something like this, which is a line. The only parameter here is the slope of that line. Our model would be this one line and it would pass basically through the data and would describe the data fairly well as you can see. If we have two parameters now we can introduce for example a bias term and not have the line at the origin. This line here, now we have the bias which is the distance to this point to describe it as well as the slope of this line as parameters. So two parameters and if you look at this line here it describes the data a bit better than before. It passes kind of through the center of the data. If we go to three or four parameters, it's well known that if I have the same number of parameters as I have data points, I can actually fit the data perfectly. How to do this? It would be like an order for polynomial which... Let's see if I can draw an order for polynomial. It needs to go... It needs to rip and then... Okay well... No that's... Okay that's more than order for. In any case I can fit actually the data perfectly. Now if you think about all of these functions, let's contrast these. Alright let's contrast them and let's look at what is the data distribution probably. Data distribution is probably, if I fill in the rest of the data that is not in our training set, maybe something like this. So which of these functions generalize as well to this general data, the unseen data? Probably the first function not doing very poorly. The first function actually doing okay. The second function doing even better as we saw. If we add a parameter to the first function it gets better, but if we then add more parameters it gets worse. This is kind of taught in current machine learning classes as the phenomenon of overfitting. Whereas here the function that has the most parameters actually doesn't fit well. What is troubling now is that if you think of things like neural networks, modern architectures, they actually have even more... They have oftentimes more parameters than their data points in the data set. So they can fit the training data perfectly and still have kind of spare room, spare capacity. These models actually generalize fairly well. This paper asks what's going on here and what they propose is the following picture. Here we have a classical view of machine learning. On the x-axis is the complexity of H. You can think of the complexity of the... This is H is the model class. H is the class of all the models you could fit. For example it would be every linear model with one parameter. This was our first model. The first model would be somewhere here one. The complexity is one. Then here we'd have the complexity of two where we added a parameter, three parameters and then four parameters. This is what we saw. At the beginning one parameter we had some training risk. Here simply another term for loss. We had some training loss. Then as we added a parameter the training loss decreased. It got better and also the test loss on the unseen data decreased. So it got better on the test set as well as we added parameter. Then as we added more parameters it was able to fit the training data better and better going to almost zero risk here. But on unseen data the performance actually got worse again. Again this is what we teach as overfitting. These authors propose this is incomplete. Namely the picture actually looks like this and all we've done so far is look at this left hand side here. Namely that there is a peak here and this is called the interpolation threshold. The interpolation threshold is roughly at the point where you have as many parameters as you have data points. After the interpolation threshold if you give even more parameters the training risk of course stays low because you can fit the training data perfectly from the interpolation threshold forward. But the test risk actually decreases again. This is really interesting. Let me just preempt this and say this is not due to regularization. It's not because people regularize their models or anything like this. In any case regularization would actually move you to less of a complexity of your model class. Because now if you regularize you're no longer able to fit certain models as easily or converge to them. They propose that this is happening and they give some reason why this might happening and they give some evidence that this is happening. Here is the evidence that this is happening and they do this here for example. This is a random Fourier features classifier. What are random Fourier features? They describe them here. If you have a data point X what you do is you push this through a function which or you push this through many of them. You sample capital N of these vectors v and of each of the vectors v you take the inner product and raise it. Take the exponential function of it and then aggregate them. These random Fourier features are the random Fourier features and these are the weights that you learn. This is basically a linear classifier but not of the original features but of intermediary features which are fixed for a given random seed. The good thing is here you can sample, you can decide how many intermediary features that you want. The other good thing is if you let n go to infinity this actually becomes an infinite dimensional kernel machine. It becomes a kernel SVM with the Gaussian kernel which is operating in an infinite dimensional space. If you don't go as far then it's just an approximation to that. It's a cool model where you can choose how many parameters you want. It's a perfect model to explore this phenomenon. What are they doing? They are doing the following. They take MNIST and they just apply this model. On the x-axis here are the number of parameters and the number of random Fourier features that they construct. Here you can see the mean squared error on the test set. As you can see at the beginning the error goes down as proposed. Then here is probably this sweet spot of classical machine learning. After that you start to overfit, it goes up again. There's a giant peak and then it goes down again. Here 10,000 I think they do it with a subset of MNIST if I remember correctly. Around 10,000 is exactly the number of data points they use or multiplied by the classes. I don't remember correctly but in any case at this number you have the same amount of parameters as data points. After that the test error decreases again. As you give more and more and more features every single classifier on this line is able to fit the training data perfectly but they successfully get less and less error on the test set. You can see it approaches this dotted line here which is if you perfectly solve the infinite dimensional problem. If you actually use a kernel SVM to solve this problem, you can see this gives you a lower bound. It really shows nicely that the random Fourier features classifier approximates this as you go higher and higher with capital N. It actually approximates the kernel SVM. This is really interesting that this actually happens in practice. What they also see here is when they look at the norm of the solution. The norm of the solution they calculate as basically the norm in the Hilbert space but they can't because it's hard to compute. A proxy for this is simply the norm of the weight vector that you learn. The norm of the solution as you add more parameters of course for first it goes up because you add more parameters, you fit each of them, they have some value and then it goes up. It peaks at this interpolation threshold. There you have a really high norm solution and after that the norm goes down again of the solution. Again it approximates the norm of the perfectly solved kernel machine. That's extremely interesting and is a part of an explanation they give why this is happening. Namely the following. If you have too many parameters what you might do with the correct inductive bias is find a low norm solution. What does a low norm solution mean? A low norm solution means a relatively simple function. As you add parameters your model is better and better able to find a simple function that describes the training data. Not in terms of simple of less parameters but simple in terms of how it moves between the training data. If you imagine the training data again from before and you imagine it perfectly fit this polynomial here that we drew with four parameters. If I have many many many more parameters I can do something like... I have many parameters but I can be kind of squeaky but they have... right? So this something like this here I grab this here I grab this something like this and this moves smoothly between the training data. It has many parameters because it has many many squiggles here but it's a low norm solution. The low norm will cause the solution to kind of be smooth whereas a high norm solution that perfectly interpolates the training data would look something like this. So the authors here say if your inductive bias is able to find a low norm solution that perfectly fits the training data then that will generalize well. It turns out that modern architectures tend to find low norm solutions if you train them for example with SGD. The combination of many parameters and low norm solutions will give you a smooth function and the smoothness of the function will be the thing that generalizes to unseen data because the smoothness kind of ensures that everything in between the data will be nicely kind of interpolated here. So that's the the perspective. They go on from these random Fourier features to neural networks and what they do here is they train a neural network on MNIST with a one hidden layer. So there's two weight layers now and again you can see as the as the number of parameters so this means basically the number of hidden nodes they increase the number of hidden nodes in the hidden layer and as they increase this the training and test error go down. The training error continues to go down test error goes up until the interpolation threshold again and then the test error drops again while the training error continues to be almost zero. They do the same thing with decision trees and random forests and show the exact same thing that there is this interpolation threshold after which the test error drops even though the training error is almost zero. To me this is really remarkable and they show this in the appendix of many many more experiments where they show this phenomenon happening on different datasets and on different architectures here random ReLU features and so on and it kind of gives a new perspective on generalization and why our models generalize so well. They finally conclude with why has this not been seen yet and they give some nice reasons basically that for example models where you can choose the models where you can choose the the complexity for example random Fourier features are originally proposed as an approximation to kernel machines if you have too many data points and don't want to compute as many features so they they're basically only ever used in this regime where the classical paradigm holds and the neural networks in the other hand often are simply made super large and they say this peak here that they show is very localized and you might if you increase your neural network maybe you try one at this size this size this size and this size and all you then see is kind of a downward trajectory you kind of miss this peak so it leads to the impression that simply oh bigger neural networks perform better. Yeah so I found this interesting I hope you did as well and definitely check out more of this group's work. That was it for now have a nice day
 Hi there! Today we're looking at reconciling modern machine learning and
 the bias-variance trade-off by Mikhail Belkin et al. This paper struck me as
 interesting at ICML when I heard a talk by Mikhail Belkin. The
 paper is very interesting in terms of what it proposes about modern machine
 learning. What's the problem? The problem is they contrast what they call
 classical machine learning and how to understand machine learning, namely in
 terms of bias-variance trade-offs, and modern machine learning where it's for
 example deep neural networks which have very different properties. Basically
 the best way to describe it is probably with an example. Let's say we have
 four data points. Here is a coordinate system in two dimensions.
 One, two, three, four. Four data points. Why not?
 These four data points we want to fit a function from X to Y. Y is our
 target. It's kind of a regression problem. Let's say we have just one
 parameter which we can use to describe our function. Probably the best
 thing we could do is to do something like this, which is a line. The
 only parameter here is the slope of that line. Our model would be
 this one line and it would pass basically through the data and would
 describe the data fairly well as you can see. If we have two parameters now we can
 introduce for example a bias term and not have the line at the origin. This
 line here, now we have the bias which is the distance to this point to describe
 it as well as the slope of this line as parameters. So two parameters and if you
 look at this line here it describes the data a bit better than
 before. It passes kind of through the center of the data. If we
 go to three or four parameters, it's well known that if I
 have the same number of parameters as I have data points, I can
 actually fit the data perfectly. How to do this? It would be like an order
 for polynomial which... Let's see if I can draw an order for polynomial. It
 needs to go... It needs to rip and then... Okay well... No that's... Okay that's more than
 order for. In any case I can fit actually the data perfectly. Now if you think
 about all of these functions, let's contrast these. Alright let's contrast
 them and let's look at what is the data distribution probably.
 Data distribution is probably, if I fill in the rest of the data that is not in
 our training set, maybe something like this. So which of these functions
 generalize as well to this general data, the unseen data? Probably the first
 function not doing very poorly. The first function actually doing okay. The second
 function doing even better as we saw. If we add a parameter to the
 first function it gets better, but if we then add more parameters it gets worse.
 This is kind of taught in current machine learning classes as the
 phenomenon of overfitting. Whereas here the function that has the most
 parameters actually doesn't fit well. What is troubling now is that if you
 think of things like neural networks, modern architectures, they actually have
 even more... They have oftentimes more parameters than their data points in the
 data set. So they can fit the training data perfectly and still have kind of
 spare room, spare capacity. These models actually generalize fairly well.
 This paper asks what's going on here and what they propose is the following
 picture. Here we have a classical view of machine learning. On the x-axis is
 the complexity of H. You can think of the complexity of the... This is H is
 the model class. H is the class of all the models you could fit. For
 example it would be every linear model with one parameter. This was our
 first model. The first model would be somewhere here one. The
 complexity is one. Then here we'd have the complexity of two where we added a
 parameter, three parameters and then four parameters. This is what we saw.
 At the beginning one parameter we had some training risk.
 Here simply another term for loss. We had some training loss. Then as
 we added a parameter the training loss decreased. It got better and also
 the test loss on the unseen data decreased. So it got better on the
 test set as well as we added parameter. Then as we added more parameters it was
 able to fit the training data better and better going to almost zero risk here.
 But on unseen data the performance actually got worse again.
 Again this is what we teach as overfitting. These authors propose this
 is incomplete. Namely the picture actually looks like this and all we've
 done so far is look at this left hand side here. Namely that there is a peak
 here and this is called the interpolation threshold. The interpolation
 threshold is roughly at the point where you have as many parameters as you have
 data points. After the interpolation threshold if you give even more
 parameters the training risk of course stays low because you can fit the
 training data perfectly from the interpolation threshold forward. But the
 test risk actually decreases again. This is really interesting.
 Let me just preempt this and say this is not due to regularization. It's
 not because people regularize their models or anything like this. In any
 case regularization would actually move you to less of a complexity of your
 model class. Because now if you regularize you're no longer able to fit
 certain models as easily or converge to them. They propose that this is
 happening and they give some reason why this might happening and they give some
 evidence that this is happening. Here is the evidence that this is happening
 and they do this here for example. This is a random Fourier features classifier.
 What are random Fourier features? They describe them here. If you have a
 data point X what you do is you push this through a function which or you
 push this through many of them. You sample capital N of these vectors v and
 of each of the vectors v you take the inner product and raise it.
 Take the exponential function of it and then aggregate them. These
 random Fourier features are the random Fourier features and these
 are the weights that you learn. This is basically a linear classifier but
 not of the original features but of intermediary features which are fixed
 for a given random seed. The good thing is here you can sample, you can decide
 how many intermediary features that you want. The other good thing is if you let
 n go to infinity this actually becomes an infinite dimensional kernel machine.
 It becomes a kernel SVM with the Gaussian kernel which is operating in
 an infinite dimensional space. If you don't go as far then it's just an
 approximation to that. It's a cool model where you can choose how
 many parameters you want. It's a perfect model to explore this phenomenon.
 What are they doing? They are doing the following. They take MNIST and they just
 apply this model. On the x-axis here are the number of parameters and
 the number of random Fourier features that they construct. Here you can see
 the mean squared error on the test set. As you can see at the beginning
 the error goes down as proposed. Then here is probably this sweet spot
 of classical machine learning. After that you start to overfit, it goes up again.
 There's a giant peak and then it goes down again.
 Here 10,000 I think they do it with a subset of MNIST if I remember correctly.
 Around 10,000 is exactly the number of data points they use or
 multiplied by the classes. I don't remember correctly but in any case at
 this number you have the same amount of parameters as data points.
 After that the test error decreases again. As you give more and more and
 more features every single classifier on this line is able to fit the
 training data perfectly but they successfully get less and less error on
 the test set. You can see it approaches this dotted line here which is if
 you perfectly solve the infinite dimensional problem. If you actually
 use a kernel SVM to solve this problem, you can see this
 gives you a lower bound. It really shows nicely that the
 random Fourier features classifier approximates this as you go higher and
 higher with capital N. It actually approximates the kernel SVM.
 This is really interesting that this actually happens in practice. What
 they also see here is when they look at the norm of the solution. The norm
 of the solution they calculate as basically the norm in the
 Hilbert space but they can't because it's hard to compute. A proxy for this
 is simply the norm of the weight vector that you learn. The norm of the
 solution as you add more parameters of course for first it goes up because you
 add more parameters, you fit each of them, they have some value and then
 it goes up. It peaks at this interpolation threshold. There you have a
 really high norm solution and after that the norm goes down again of the solution.
 Again it approximates the norm of the perfectly solved kernel
 machine. That's extremely interesting and is a part of an explanation they
 give why this is happening. Namely the following. If you have too many
 parameters what you might do with the correct inductive bias is find a low
 norm solution. What does a low norm solution mean? A low norm solution
 means a relatively simple function. As you add parameters your model is
 better and better able to find a simple function that describes the training
 data. Not in terms of simple of less parameters but simple in terms
 of how it moves between the training data. If you imagine the training
 data again from before and you imagine it perfectly fit this polynomial
 here that we drew with four parameters. If I have many many many more
 parameters I can do something like... I have many parameters but I can be
 kind of squeaky but they have... right? So this something like this here I grab
 this here I grab this something like this and this moves smoothly between the
 training data. It has many parameters because it has many many squiggles here
 but it's a low norm solution. The low norm will cause the solution to kind of
 be smooth whereas a high norm solution that perfectly interpolates the training
 data would look something like this. So the authors here say if your
 inductive bias is able to find a low norm solution that perfectly fits the
 training data then that will generalize well. It turns out that modern
 architectures tend to find low norm solutions if you train them for example
 with SGD. The combination of many parameters and low norm
 solutions will give you a smooth function and the smoothness of the
 function will be the thing that generalizes to unseen data because the
 smoothness kind of ensures that everything in between the data will be
 nicely kind of interpolated here. So that's the the perspective.
 They go on from these random Fourier features to neural networks and what
 they do here is they train a neural network on MNIST with a one hidden
 layer. So there's two weight layers now and again you can see as the as the
 number of parameters so this means basically the number of hidden nodes
 they increase the number of hidden nodes in the hidden layer and as they increase
 this the training and test error go down. The training error continues to go down
 test error goes up until the interpolation threshold again and then
 the test error drops again while the training error continues to be almost
 zero. They do the same thing with decision trees and random forests and
 show the exact same thing that there is this interpolation threshold after which
 the test error drops even though the training error is almost zero. To me
 this is really remarkable and they show this in the appendix of many many more
 experiments where they show this phenomenon happening on different
 datasets and on different architectures here random ReLU features and so on and
 it kind of gives a new perspective on generalization and why our models
 generalize so well. They finally conclude with why has this not been seen yet and
 they give some nice reasons basically that for example models where you can
 choose the models where you can choose the the complexity for example random
 Fourier features are originally proposed as an approximation to kernel machines
 if you have too many data points and don't want to compute as many features
 so they they're basically only ever used in this regime where the classical
 paradigm holds and the neural networks in the other hand often are simply made
 super large and they say this peak here that they show is very localized and you
 might if you increase your neural network maybe you try one at this size
 this size this size and this size and all you then see is kind of a downward
 trajectory you kind of miss this peak so it leads to the impression that simply
 oh bigger neural networks perform better. Yeah so I found this interesting I hope
 you did as well and definitely check out more of this group's work. That was it
 for now have a nice day