This paper, a recipient of an Outstanding Paper Award at NeurIPS 2019, fundamentally challenges the way theorists try to explain why deep learning works. It suggests that our most trusted tool for understanding machine learning—uniform convergence—might be mathematically incapable of explaining the success of overparameterized neural networks.
Introduction
In classical machine learning, we worry about "overfitting": if a model has too many parameters relative to the amount of data, it should just memorize the noise and fail on new data. Deep learning defies this logic. Modern networks have millions of parameters but only thousands of data points, yet they generalize remarkably well.
To explain this, researchers use generalization bounds. Most of these are based on uniform convergence, which essentially asks: "Is the training error close to the test error for every possible model in our hypothesis class?"
The problem is that existing bounds for deep learning are often "vacuous"—they might predict an error rate of 100% or more, even when the actual error is 1%. This paper asks a deeper question: Is this just because our current bounds are "loose," or is there a fundamental flaw in using uniform convergence itself for deep learning? The authors prove that uniform convergence can fail to explain why deep networks generalize well, demonstrating that even the tightest versions of these bounds can be vacuous and can paradoxically increase as you add more training data.
Methodology
The authors use a combination of empirical experiments and rigorous mathematical proofs to dismantle the reliance on uniform convergence:
- Empirical Tracking: They trained neural networks on the MNIST dataset and tracked how weight norms (like the distance from initialization) changed as they increased the number of training samples ($m$).
- Theoretical Construction: They defined the "tightest possible" algorithm-dependent uniform convergence bound. This is a version of the theory that aggressively prunes the hypothesis class to only include models that the learning algorithm (like Gradient Descent) would actually find.
- Counter-examples: They constructed specific scenarios—a high-dimensional linear classifier and a two-layer ReLU network—where they could prove that the actual generalization error is small, but any uniform convergence-based bound must be nearly 1 (completely useless).
To support their theoretical claims, the authors utilized synthetic high-dimensional data for the linear classifier proof and a "Two-Hypersphere Task" to show that ReLU networks learn "skewed" boundaries that generalize well but look overly complex to uniform convergence.
Key Findings
The "More Data, Worse Bound" Paradox
Ideally, a generalization bound should decrease as you add more data (scaling with $1/\sqrt{m}$). However, the authors found that in deep learning, weight norms actually increase with the dataset size. Because existing bounds depend heavily on these norms, the bounds get worse (larger) as you give the model more data, even though the model's actual test error is going down.
Empirically, on MNIST, they showed that popular bounds from previous high-profile papers grow at a rate of roughly $\Omega(m^{0.68})$. This means the more data you have, the "less sure" the theory becomes about the model's success.
Microscopic Complexity and Two-Sided Failure
The authors conjecture that Gradient Descent finds a solution that is "simple" at a macroscopic level (leading to good generalization) but contains "microscopic fluctuations" or "wiggles" around the training points.
Uniform convergence is "tricked" by these microscopic complexities. It sees these wiggles and concludes that the model class is incredibly complex, even though those wiggles don't affect performance on new, random test data. Furthermore, uniform convergence requires the error to be small on all datasets in a certain set. The authors show that for any "good" dataset, there exists a "bad" dataset that looks just like it but where the model fails. Uniform convergence cannot distinguish between the two, leading to vacuous results. For the high-dimensional linear case, they proved that while the actual error $\epsilon_{gen}$ is very small, the uniform convergence bound $\epsilon_{unif-alg}$ is $\ge 1 - \epsilon$.
Limitations and Future Directions
- Regularization: The authors note that their results apply to networks trained without explicit regularization (like weight decay). It is possible that uniform convergence still works if strong regularization is used to "smooth out" the microscopic complexities.
- Alternative Frameworks: The paper doesn't solve the generalization puzzle; it rules out one major path. They suggest that future work should look into algorithmic stability—a framework that looks at how much a model changes if you change one data point—rather than trying to bound the complexity of the entire function class.
- The "Deep Learning Conjecture": They leave as a future challenge the task of formally separating the "macroscopic simplicity" from the "microscopic complexity" in learned neural networks to better understand their true generalization capabilities.
Summary updated