Deep Learning is Not So Mysterious or Different

TL;DR

A position paper (Andrew Gordon Wilson, NYU, ICML 2025) arguing that benign overfitting, double descent, and the success of overparametrization are not distinct to neural networks and not mysterious — they are reproducible with simple linear / polynomial models and rigorously characterized by PAC-Bayes and countable-hypothesis generalization bounds that predate deep learning by decades. The unifying recipe is soft inductive biases: rather than restricting the hypothesis space to avoid overfitting, embrace a flexible hypothesis space combined with a preference for simpler solutions consistent with the data. The paper concedes that deep learning is genuinely different in other ways (representation learning, mode connectivity, broad universality) — but the generalization story does not require rethinking textbooks.

Key claims

Benign overfitting (perfectly fitting noise while still generalizing on structured data) can be reproduced with simple linear and polynomial models — not distinct to neural networks; the understanding deep learning requires rethinking generalization framing has been over-stated [§4, Fig. 1].
The unifying mechanism is soft inductive biases: combine a flexible hypothesis space with a preference for simpler solutions, rather than constraining the hypothesis space outright; soft biases give better generalization than hard restriction biases across data scales [§2, Fig. 3, Fig. 5].
PAC-Bayes and countable-hypothesis bounds do characterize benign overfitting, double descent, and overparametrization — including for neural networks with billions of parameters — when evaluated with a Solomonoff / Kolmogorov-complexity-based prior [§3.1, Eqs. 1–4].
Generalization bound takes the schema: $\text{generalization gap} \lesssim \sqrt{(\text{empirical risk} + \text{compressibility}) / n}$ ; both training loss and model compressibility (file size after compression) are sufficient to compute non-vacuous bounds on real models [§3.1, Fig. 2].
Rademacher complexity and VC dimension fail to characterize these phenomena precisely because they penalize the size of the hypothesis space rather than the prior likelihood of specific hypotheses — they prescribe restriction biases, not soft biases [§3.3, App. B, Table 1].
Double descent in the test-error-vs-model-size curve is reproduced exactly with linear regression and explained by tail eigenvalue behavior; it is not a deep-learning-specific phenomenon [§6].
The same bounds extend to LLMs (with adaptations for unbounded loss, stochastic training, token dependence) — yielding non-vacuous guarantees on models with billions of parameters and even recovering Chinchilla-style scaling laws [§3.1, citing Lotfi et al.].
Deep learning is distinctively different in three ways the paper identifies: representation learning (the learned hidden representations are themselves useful), mode connectivity (optima lie in connected manifolds), and broad universality (a single architecture works across many domains) [§8].

Method

This is a position paper without a new algorithm. The argument structure is: (1) restate three “mysterious” phenomena — benign overfitting, overparametrization, double descent — and the conventional wisdom that they require new generalization theory; (2) reproduce each phenomenon with a basic linear or polynomial model under an order-dependent parameter prior / regularizer, where high-order coefficients are penalized more than low-order ones; (3) formalize the underlying intuition with PAC-Bayes (Theorem 3.1 — Countable Hypothesis Bound) and Solomonoff-prior bounds, showing that “low empirical risk + high compressibility ⇒ low generalization gap” holds for arbitrarily large models; (4) contrast with frameworks (VC, Rademacher, fat-shattering) that fail because they bound the size of $\mathcal{H}$ rather than the prior weight of specific hypotheses in it; (5) name the things deep learning genuinely does differently — representation learning, mode connectivity, universality, in-context learning. The running mechanical example is a high-order polynomial with order-dependent regularization $\sum_n \alpha_n^2 / \sigma_n^2$ , $\sigma_n$ decreasing in $n$ — the same hypothesis class that reproduces benign overfitting on noisy CIFAR-10 with a Gaussian process and the same one that reproduces double descent.

Results

The paper does not report new training results. Rather, it shows reproductions of the canonical phenomena with non-neural models: Fig. 1 shows benign overfitting and double descent in simple linear / polynomial models with order-dependent priors; Fig. 1(d–e) exactly reproduces Zhang et al. 2016’s mixed-signal-and-noise CIFAR-10 experiment with a Gaussian process (rather than a CNN) and shows the marginal likelihood decreases as label-noise fraction rises, aligned with degraded generalization. Cites Lotfi et al.’s non-vacuous PAC-Bayes generalization bounds on convolutional models trained on CIFAR-10 — upper-bounding classification error at 16.6% with ≥95% probability for a million-parameter model. The author-named limitations are explicit: scaling laws and grokking are not covered (because they don’t conflict with classical theory); the position is not that deep learning is fully understood, only that the generalization story does not require rethinking.

Why it’s interesting

This paper is the cleanest filed counterpoint on the wiki to the “we need new theory for large models” position that implicitly underlies the Hyperparameter scaling laws and Training stability at scale clusters. Where those clusters are about prescriptions (fitting LR surfaces, spectral constraints, weight-decay scaling) derived from large-scale empirical sweeps, Wilson’s position is the retrospective claim that the underlying generalization framework was already there — PAC-Bayes + soft priors — and the prescriptions are recovering it. The contrast with How To Scale and How to Set the Learning Rate for Large-Scale Pre-training? is structural: those papers are pragmatic recipes, Wilson is naming the theoretical substrate. The position also intersects with Deep sequence models tend to memorize geometrically; it is unclear why (geometric memorization without a mechanism) and Generalization at the Edge of Stability (edge-of-stability dynamics) on the question of “what does generalization look like in this regime”; Wilson’s answer is “PAC-Bayes with a compressibility prior, even when overparametrized.” Useful as a citation when arguing that an empirical-recipe paper recovers something theory-of-deep-learning already predicted, and worth tracking against the architecture-axis scaling laws emerging on the wiki.