Introduction
Deep Neural Networks (DNNs) present a significant challenge for classical learning theory. Despite their massive parameter counts, they generalize remarkably well, often defying traditional bounds that suggest they should overfit. This paper addresses the "depth-dependency" problem: why does increasing network depth often improve generalization? By reframing DNNs through the lens of sample compression and high-dimensional kernel methods, the authors provide a framework that explains this phenomenon without relying on parameter counts.
Theoretical Framework: Path Space and Network Support Vectors
The authors propose that Leaky-ReLU networks can be viewed as linear classifiers operating in a high-dimensional "Path Space." In this representation, features correspond to individual paths from the input to the output layer.
A central hypothesis is that gradient descent naturally drives these networks toward a max-margin solution in path space, similar to Support Vector Machines (SVMs). This leads to the definition of Network Support Vectors (NSVs)—a small subset of the training data that uniquely defines the decision boundary. Using PAC-Bayesian theory, the authors derive a generalization bound of $O(ns/m)$, where $n$ is the number of neurons, $s$ is the number of NSVs, and $m$ is the sample size.
Empirical Scaling and Key Results
The validity of this framework is supported by empirical observations on datasets like MNIST and CIFAR-10. The most critical insight is how the number of support vectors scales with network architecture.
As shown above, the fraction of support vectors ($s/m$) increases only logarithmically with network width. More importantly, the research reveals a "superlinear" effect regarding depth.
As network depth increases, the number of support vectors required to define the classifier decreases linearly. This reduction in $s$ effectively offsets the increase in $n$ (total neurons), leading to tighter, non-vacuous generalization bounds for deeper models. Furthermore, the decision boundaries of trained DNNs show over 99% agreement with their theoretical max-margin counterparts, suggesting that DNNs are "almost" SVMs in path space.
Conclusion and Future Directions
This work provides a compelling explanation for the success of deep architectures by linking generalization to sample compression. While the current theory relies on the empirical observation of max-margin behavior and focuses on fully-connected Leaky-ReLU networks, it opens the door for more refined bounds. Future research will aim to extend these proofs to convolutional and residual architectures and further explore the mechanisms by which gradient descent coordinates weight signs to achieve such high levels of compression.
Summary updated