On the Universality of the Double Descent Peak in Ridgeless Regression
  We prove a non-asymptotic distribution-independent lower bound for the
expected mean squared generalization error caused by label noise in ridgeless
linear regression. Our lower bound generalizes a similar known result to the
overparameterized (interpolating) regime. In contrast to most previous works,
our analysis applies to a broad class of input distributions with almost surely
full-rank feature matrices, which allows us to cover various types of
deterministic or random feature maps. Our lower bound is asymptotically sharp
and implies that in the presence of label noise, ridgeless linear regression
does not perform well around the interpolation threshold for any of these
feature maps. We analyze the imposed assumptions in detail and provide a theory
for analytic (random) feature maps. Using this theory, we can show that our
assumptions are satisfied for input distributions with a (Lebesgue) density and
feature maps given by random deep neural networks with analytic activation
functions like sigmoid, tanh, softplus or GELU. As further examples, we show
that feature maps from random Fourier features and polynomial kernels also
satisfy our assumptions. We complement our theory with further experimental and
analytic results.
