Fast generalization error bound of deep learning from a kernel perspective

Taiji SuzukiAISTATS 2018 · OpenReview

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).

Table 1: Theoretical generalization error bounds for different settings, showing the impact of layer width and eigenvalue decay.

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.

The degree of freedom $N_\ell(\lambda)$ across different layers of a CNN, illustrating how effective complexity varies with the regularization parameter $\lambda$.

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

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 B...
BibTeX
@inproceedings{suzuki2018fast,
  author = {Taiji Suzuki},
  title = {{Fast generalization error bound of deep learning from a kernel perspective}},
  booktitle = {International Conference on Artificial Intelligence and Statistics},
  year = {2018},
  url = {https://openreview.net/forum?id=6kfN_6er80v},
}
Figure