Benign Overfitting and Double Descent

The "benign overfitting" research programme crystallized between 2017 and 2020 around three stubborn empirical facts that uniform-convergence theory could not accommodate. First, deep networks fit random labels to zero training error while still generalizing on the true labels (Zhang et al. 2017). The same networks remain fragile to imperceptible adversarial perturbations even where they generalize (Szegedy et al. 2014), so whatever inductive bias selects a generalizing interpolator is also selecting a non-robust one, and a capacity-only account has no vocabulary in which to say that. Section Robustness, Adversarial Examples, and Benign Overfitting takes that tension up in detail, and the answer there turns out to be a property of the min-norm interpolator rather than an accident of training. Second, their test error does not increase monotonically with capacity past the interpolation threshold; it decreases again, tracing the double-descent curve (Belkin et al. 2019; Nakkiran et al. 2020). Third, the same phenomenology is visible in linear regression, kernel regression, and random-feature regression, which admit exact asymptotic analysis (Bartlett et al. 2020; Mei and Montanari 2022; Hastie et al. 2022). These three facts together ruled out any explanation based purely on function-class capacity and forced the field to look at the interaction between the data covariance spectrum, the optimizer's implicit bias, and the architectural parameterization.

The lineage of the interpolation idea predates deep learning. (Schapire et al. 1998) already explained why boosting keeps improving test error after training error hits zero (the margin story, see Part I). The kernel community observed the same behaviour when interpolating RBF kernels with zero regularization, documented systematically by (Belkin et al. 2018): kernels with sufficiently flat spectra can interpolate noisy data and still generalize, contradicting the bias-variance orthodoxy that interpolation must overfit. What deep learning added was scale: models routinely exceed sample size by orders of magnitude, pushing into a regime where the classical analyses simply do not apply. (Belkin et al. 2019) was the synthesis paper that named the phenomenon ("double descent") and drew the canonical figure; a U-curve joined to a second descent, with a spike at the interpolation threshold.

The theoretical settlement came from two directions. (Bartlett et al. 2020) gave finite-sample risk bounds for the min-norm linear interpolator and identified the effective-rank conditions that govern when interpolation is benign; (Tsigler and Bartlett 2023) extended this to ridge regression with both positive and negative regularization. Independently, (Liang and Rakhlin 2020) proved a matching statement for kernel ridgeless regression in the high-dimensional setting, relating the implicit regularization to the curvature of the kernel. On the optimization side, (Soudry et al. 2018) showed that gradient descent on separable data with logistic-type losses converges to the max-margin (L2 SVM) predictor; the implicit bias result that provided the missing algorithmic explanation. (Gunasekar et al. 2018) extended this to convolutional networks (different implicit bias: Fourier-sparse, not L2), and (Ji and Telgarsky 2019) closed the nonseparable case.

The final piece was the random-features bridge. (Rahimi and Recht 2008) introduced random features as a tractable kernel approximation; (Mei and Montanari 2022) used the random-features model as an analytically solvable proxy for a two-layer neural network and derived the precise asymptotic curves that match Belkin and Nakkiran's empirical double-descent plots. (Hastie et al. 2022) independently analyzed high-dimensional ridgeless least squares and also reproduced double descent. (Advani et al. 2020) had earlier given the dynamical picture from statistical physics, explaining double descent as an interaction between signal and noise modes during training.

A parallel empirical thread sharpens what role overparameterization actually plays. The Lottery Ticket Hypothesis (Frankle and Carbin 2019) (ICLR 2019 Best Paper) showed that dense networks contain sparse subnetworks ("winning tickets") that, when extracted and reset to their original random initialization and retrained in isolation, match the dense network's accuracy at roughly 10-20% of the original weight count. The construction is iterative magnitude pruning (IMP): train the full network to convergence, prune the lowest-magnitude $p$% of weights, reset surviving weights to their exact values from before any training (not to zero, not to a new random draw; back to $\theta_0$), then retrain the sparse network. Repeating this over multiple rounds finds progressively sparser winning tickets.

On small networks the result is striking. A Lenet winning ticket at 21.1% sparsity reaches minimum validation loss 38% faster than the full network and finishes 0.3 percentage points higher. On CIFAR-10 convolutional networks, the winning ticket at ~11% sparsity improves accuracy by 3.5 points over the dense baseline when matched for iteration count.

The core claim is not about expressivity but about initialization quality: the dense network's parameter budget functions as a search space for discovering an initialization that makes sparse training efficient. The winning ticket is not sparser-but-equivalent; it trains faster than the full network, which a capacity argument cannot explain.

The scale limitation of the original paper is concrete: IMP fails on VGG-19 and ResNet-18 at standard learning rates (0.1), because large-network training is sensitive to learning-rate warmup in ways small-network training is not. Subsequent work (Frankle et al. 2020) addressed this by rewinding surviving weights not all the way to $\theta_0$ but to a checkpoint taken after a few hundred steps (the "stability point"), recovering the winning-ticket property at ImageNet scale. This refinement is not in the 2019 paper. The skeptical reading that connects Lottery Ticket to double descent: double descent says capacity past interpolation helps generalization; Lottery Ticket says the mechanism is finding a sparse trainable initialization, not deploying all the parameters at inference. This unified reading is not yet a theorem, but it is the cleanest framing for why both phenomena coexist without contradicting each other.

References