Abstract
We develop a new theoretical framework to analyze the generalization error of deep learning, and derive a new fast learning rate for two representative algorithms: empirical risk minimization and Bayesian deep learning. By treating neural networks as finite approximations of infinite-dimensional integral models and utilizing the "degree of freedom" of Reproducing Kernel Hilbert Spaces (RKHS), we show that deep learning can achieve convergence rates significantly faster than the standard $O(1/\sqrt{n})$, potentially reaching $O(1/n)$ depending on the eigenvalue decay of internal layers.
Introduction
Despite the empirical success of deep learning, theoretical understanding of its generalization error—the performance gap between training and unseen data—has remained relatively "loose." Conventional theories often rely on Rademacher complexity, which typically yields a slow convergence rate of $O(1/\sqrt{n})$. These pessimistic bounds often fail to account for input distributions and specific architectural nuances, leading to a disconnect between theory and the high performance observed in practice. This work bridges this gap by providing a sharper bound that incorporates the internal structure of the network and data distribution through a kernel-based lens.
A Kernel Perspective on Deep Learning
The proposed framework views deep neural networks as a stack of infinite-dimensional models. By modeling each layer as a continuous operator in an integral form, the authors define a Reproducing Kernel Hilbert Space (RKHS) for every layer. The complexity of a layer is then characterized by the eigenvalues of its corresponding kernel.
A central metric in this analysis is the "degree of freedom" ($N_\ell(\lambda)$), which quantifies the "effective" number of parameters a layer utilizes. When the eigenvalues of a layer's kernel decay rapidly, the degree of freedom remains low, implying that most information is captured within a few dimensions. This perspective allows for a refined analysis of the bias-variance trade-off, where generalization error is balanced between approximation error (bias from finite neurons) and estimation error (variance from data noise).
Empirical Validation and Key Insights
The researchers validated their framework using MNIST and CIFAR-10 benchmarks. Experiments on a VGG-type network trained on CIFAR-10 confirmed that eigenvalues in real-world deep networks indeed decay rapidly, justifying the assumption that the "effective dimension" is much smaller than the total parameter count.
Key findings include:
- Fast Convergence Rates: Under favorable conditions, such as strong convexity in regression, the error can decrease at a rate of $O(1/n)$. For kernels with polynomial eigenvalue decay of rate $s$, the bound is approximately $n^{-1/(1+2s)}$.
- Optimal Layer Width: The theory suggests that hidden layer width should be informed by the kernel's degree of freedom. A "peaky" eigenvalue distribution allows for narrower layers without sacrificing accuracy.
- Bias-Variance Trade-off: Numerical results on MNIST showed a U-shaped performance curve relative to layer width, confirming that excessively wide layers can lead to increased variance and slightly lower test accuracy.
Conclusion and Future Directions
This framework provides a unified language for both finite-dimensional practical networks and infinite-dimensional theoretical models. While the current proofs focus primarily on regression with squared loss and Lipschitz continuous activations like ReLU, they offer a rigorous foundation for understanding generalization. Future work may extend these "fast" rates to more complex non-convex landscapes and provide practical guidelines for optimizing network architecture based on real-time estimates of the degree of freedom during training.
Summary updated