Abstract
Even though Deep Neural Networks (DNNs) are widely celebrated for their practical performance, they possess many intriguing properties related to depth that are difficult to explain both theoretically and intuitively. Understanding how weights in deep networks coordinate together across layers to form useful learners has proven challenging, in part because the repeated composition of nonlinearities has proved intractable. This paper presents a reparameterization of DNNs as a linear function of a feature map that is locally independent of the weights. This feature map transforms depth-dependencies into simple tensor products and maps each input to a discrete subset of the feature space. Then, using a max-margin assumption, the paper develops a sample compression representation of the neural network in terms of the discrete activation state of neurons induced by $s$ "support vectors". The paper shows that the number of support vectors $s$ relates with learning guarantees for neural networks through sample compression bounds, yielding a sample complexity of $O(ns/\epsilon)$ for networks with $n$ neurons. Finally, the number of support vectors $s$ is found to monotonically increase with width and label noise but decrease with depth.
Introduction
One of the central mysteries in modern artificial intelligence is why Deep Neural Networks (DNNs) generalize so effectively. Traditional statistical learning theory suggests that models with millions of parameters should overfit training data. However, in practice, increasing network depth often leads to better performance on unseen data. This paper addresses this "depth paradox" by bridging the gap between DNNs and Support Vector Machines (SVMs) through the lens of sample compression theory.
Methods: Path Space and Support Vectors
The authors introduce a novel framework to analyze DNNs by reparameterizing them into a "Path Space." In this space, a ReLU network acts as a linear function of a feature map representing all possible paths from input to output.
Key components of this framework include:
- Local Invariance: Due to the piecewise linear nature of ReLU activations, the network's feature map remains locally independent of the weights. Small perturbations in weights do not change the set of active neurons.
- Max-Margin Assumption: The researchers posit that trained DNNs behave like max-margin classifiers in path space. Empirical evidence shows that unregularized gradient descent naturally converges toward these solutions, with standard DNN decision boundaries showing over 99% agreement with max-margin counterparts.
- Network Support Vectors (NSVs): Under the max-margin assumption, a model can be fully reconstructed using only a small subset of the training data. These samples are termed Network Support Vectors (NSVs).
Key Results: The Impact of Depth
The most significant finding is that while adding layers increases the total number of neurons ($n$), it simultaneously decreases the fraction of training samples that act as support vectors ($s/m$). This reduction in $s$ is "superlinear," meaning it outweighs the increase in $n$, ultimately leading to tighter generalization bounds for deeper models.
As shown in the empirical analysis, the fraction of NSVs consistently drops as depth increases. This trend directly influences the theoretical generalization bound derived by the authors, $O(ns/\epsilon)$. When plotted against depth, this bound trends downward, mirroring the improved test accuracy observed in real-world deep learning applications.
Additional insights include:
- Width vs. Depth: While depth reduces the number of support vectors, increasing network width causes $s$ to grow logarithmically.
- Memorization Complexity: When trained on randomized labels, the number of support vectors jumps from approximately 10% to 60% of the dataset. This suggests that memorizing noise is mathematically more complex in path space than learning structured patterns.
- Weight Coordination: The authors observed a "sign-parity" coordination where weights across layers align so that path products are predominantly positive, facilitating efficient learning.
Conclusion and Future Work
By reparameterizing DNNs as linear classifiers in a high-dimensional path space, this work provides a concrete mathematical explanation for why depth aids generalization. The discovery that depth minimizes the required number of support vectors offers a new metric for model complexity that aligns with empirical performance.
Future research may explore the specific mechanisms by which depth facilitates this reduction in support vectors and whether new training objectives can be designed to explicitly minimize $s$ to guarantee superior generalization.
Summary updated