Abstract:
Double descent refers to the phase transition that is exhibited by
the generalization error of unregularized learning models when varying the ratio
between the number of parameters and the number of training
samples. The recent success of highly over-parameterized machine learning
models such as deep neural networks has motivated a theoretical analysis of
the double descent phenomenon in classical models such as linear
regression which can also generalize well in the over-parameterized
regime. We provide the first exact non-asymptotic
expressions for double descent of the minimum norm linear
estimator. Our approach involves constructing a special
determinantal point process which we call surrogate random
design, to replace the standard i.i.d. design of the training
sample. This surrogate design admits exact expressions for the mean
squared error of the estimator while preserving the key properties
of the standard design. We also establish an exact implicit
regularization result for over-parameterized training samples. In
particular, we show that, for the surrogate design, the implicit bias
of the unregularized minimum norm estimator precisely corresponds to
solving a ridge-regularized least squares problem on the population
distribution. In our analysis we introduce a new mathematical tool of
independent interest: the class of random matrices for which
determinant commutes with expectation.
