An Information-Theoretic Framework for Deep Learning

Hong Jun Jeon, Benjamin Van RoyNeurIPS 2022 · OpenReview

The Theory-Practice Gap in Deep Learning

In the world of deep learning, there is a glaring "theory-practice gap." Standard statistical learning theories, such as those relying on VC dimension, suggest that as models get deeper and wider, they should require an astronomical—even exponential—amount of data to avoid overfitting.

However, empirical evidence shows the exact opposite: gargantuan models like GPT-3 generalize remarkably well with tractable amounts of data. Existing theoretical bounds often become vacuous when applied to these modern architectures because they rely heavily on parameter counting or worst-case analysis.

Deep neural network architectures analyzed in the study.

To address this, the authors of this paper introduce a novel information-theoretic framework. By applying rate-distortion theory, they prove that the amount of data needed to learn (sample complexity) scales linearly or quadratically with network depth, rather than exponentially. This provides a crucial theoretical bridge to explain the empirical success of massive, deep models.

Methodology: Learning as Communication

The authors pivot away from traditional parameter counting and instead treat learning as a communication problem using Information Theory. Their framework is built on three core pillars:

  1. Information-Theoretic Regret: The authors define the error of a model using Kullback-Leibler (KL) divergence. This allows them to equate "prediction error" with "information gain." Essentially, every time a model makes a mistake, it is "surprised" and gains a specific amount of information (measured in nats) about the environment. Learning is literally the process of reducing uncertainty.
  2. Rate-Distortion Theory: This is the core engine of the paper. The authors treat the "environment" (the true function the network is trying to learn) as a data source and the model as a "lossy compression" of that source. The rate-distortion function describes the minimum information (rate) needed to achieve a certain level of accuracy (distortion).
  3. Layer-wise Decomposition: To tackle the "curse of depth," the authors analyze how error propagates through layers. Instead of looking at the network as a single black box where errors might explode, they break it down into incremental errors at each stage, showing that the total error is simply the sum of these manageable parts.
Layer-wise error decomposition.

Key Insights and Results

By utilizing an average-case (Bayesian) framework rather than a pessimistic worst-case scenario, the authors derive bounds that more closely mirror how models behave in practice. Traditional bounds often show error blowing up by a factor of the "spectral radius" at every layer, leading to exponential growth. By using rate-distortion, the authors show that if layers don't amplify the scale of the output, the complexity is tamed.

The paper provides concrete sample complexity bounds ($T_\epsilon$) for two prototypical environments:

  • Deep ReLU Networks: The authors establish a bound of $\tilde{O}(\frac{KN^2 + dN}{\epsilon})$. Crucially, this is linear in the number of parameters and depth ($K$). This significantly improves upon previous results that suggested complexity grew with the product of parameters and depth.
  • Deep Nonparametric Networks: For networks with arbitrary (even infinite) width but bounded weights, they show the sample complexity grows only quadratically with depth ($K^2$). This is a massive improvement over existing theories that predicted exponential or high-order polynomial dependence on depth, proving that the framework provides bounds that remain meaningful independent of network width.

Limitations and Future Work

While this framework offers a powerful new lens for understanding deep learning, it is a purely theoretical work with a few notable limitations:

  • The "Optimal Agent" Assumption: The framework assumes an optimal agent performing perfect Bayesian inference. In reality, modern models are trained using Stochastic Gradient Descent (SGD). Whether SGD can actually achieve these theoretical limits remains an open question.
  • Simple Input Distributions: The current analysis assumes relatively simple input structures. The authors note that more complex, structured input distributions (like natural images) could be analyzed in the future using the "data processing inequality."
  • Practical Algorithms: The paper proves that it is mathematically possible to learn with this little data, but it does not provide a specific algorithm to reach these bounds. Bridging this theoretical possibility to practical training techniques is the next frontier.

Summary updated

Abstract

Each year, deep learning demonstrate new and improved empirical results with deeper and wider neural networks. Meanwhile, with existing theoretical frameworks, it is difficult to analyze networks deeper than two layers without resorting to counting parameters or encountering sample complexity bounds that are exponential in depth. Perhaps it may be fruitful to try to analyze modern machine learning under a different lens. In this paper, we propose a novel information-theoretic framework with its own notions of regret and sample complexity for analyzing the data requirements of machine learning. We use this framework to study the sample complexity of learning from data generated by deep ReLU neural networks and deep networks that are infinitely wide but have a bounded sum of weights. We establish that the sample complexity of learning under these data generating processes is at most linear and quadratic, respectively, in network depth.
BibTeX
@inproceedings{jeon2022information,
  author = {Hong Jun Jeon and Benjamin Van Roy},
  title = {{An Information-Theoretic Framework for Deep Learning}},
  booktitle = {Advances in Neural Information Processing Systems},
  year = {2022},
  url = {https://openreview.net/forum?id=p_BVHgrvHD4},
}
Figure