🤖 machine learning

Information-Theoretic Foundations for Machine Learning

This paper proposes a mathematically rigorous, information-theoretic framework rooted in Bayesian statistics that unifies the analysis of diverse machine learning paradigms—from i.i.d. data to sequential, hierarchical, and misspecified settings—to provide both theoretical depth for researchers and practical intuition for practitioners.

Original authors: Hong Jun Jeon, Benjamin Van Roy

Published 2026-08-04

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Hong Jun Jeon, Benjamin Van Roy

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a detective trying to solve a mystery, but instead of clues, you have a stream of data. For the last decade, machine learning has been like a detective who solves cases by sheer intuition and massive amounts of trial-and-error. They look at a mountain of evidence, guess the culprit, and if they get it right, they move on. It works incredibly well—AI can now beat grandmasters at chess and write coherent stories—but nobody really has a solid rulebook explaining why it works or how to predict exactly how much more data is needed to solve the next, harder case. It's a bit like the famous "Allegory of the Cave," where people only see shadows on a wall and think that's the whole world, never realizing the real objects casting those shadows exist outside.

To understand this paper, you need to know two simple things. First, Bayesian statistics is just a fancy way of saying "updating your beliefs." Imagine you think a coin is fair, but after flipping it ten times and seeing ten heads, you update your belief to think it might be weighted. Second, Information Theory, invented by Claude Shannon, is the science of measuring how much "surprise" or "new information" is in a message. If you tell someone "the sun rose today," that's zero information because it's not surprising. If you tell them "the sun didn't rise," that's a huge amount of information. This paper asks: Can we use the math of "surprise" to build a rulebook for how AI learns, even when the world is messy and complicated?

The authors, Hong Jun Jeon and Benjamin Van Roy, propose a new theoretical framework that acts like a flashlight to see what's outside the cave. They argue that the "error" an AI makes—how wrong its predictions are—is directly linked to how much information it needs to learn about the hidden rules of the world. They don't just guess; they use rigorous math to prove that the amount of data an AI needs to learn is determined by the "complexity" of the data's hidden structure, measured in units of information.

Here is the core of their discovery: They found that for an ideal learner (one that uses perfect Bayesian reasoning), the average mistake it makes is exactly equal to the total amount of information it has gathered about the hidden truth, divided by the number of data points it has seen. It's like saying that every time you learn a new fact, you reduce your confusion by a specific, measurable amount.

The paper challenges the idea that we need rigid, worst-case scenarios to understand learning. Instead, it suggests that by looking at the average case through the lens of information, we can get much clearer answers. They tested this idea on several different "worlds" or data types. They looked at simple, random data (like rolling dice), sequential data (like reading a sentence where the next word depends on the previous ones), and even complex, hierarchical data (like learning to write different styles of essays).

In every case, their framework provided a precise way to calculate the limits of learning. For example, when they looked at deep neural networks (the kind used in large language models), they showed that even if the network is infinitely wide and complex, the amount of data needed to learn it depends on how "concentrated" the learning is. They also tackled the problem of "misspecification," which happens when the AI's model is slightly wrong about how the world works (like trying to fit a square peg in a round hole). They proved that even with a wrong model, the AI can still learn, but there is a permanent "floor" to how good it can get, determined by how wrong the model is.

One of the most exciting findings relates to the "neural scaling laws" that tech companies use today. These laws describe how performance improves as you increase computing power. The authors' math reveals a specific optimal balance: to get the best results with a fixed amount of computing power (FLOPs), you should balance your model size and your data size so that the number of parameters grows with the square root of your total computing budget. Since total computing power is the product of model size and dataset size, this means you shouldn't just make your model infinitely huge or your dataset infinitely large in isolation. Instead, the optimal strategy is to grow both in tandem, but with the model size scaling as the square root of your resources. For instance, if you quadruple your computing budget, the optimal model size only doubles, while the dataset size also doubles, keeping the product equal to your new budget.

The paper doesn't claim to have solved every problem in AI, nor does it say that current AI is perfect. Instead, it provides a new, mathematically sound map. It shows that the relationship between data, model complexity, and learning error is not a mystery, but a calculable trade-off. By treating learning as an information game, the authors give us a way to predict how much data we need and how big our models should be, turning the "shadows on the wall" into a clear picture of what is possible. Whether you are training a robot to walk or a computer to write poetry, this framework suggests that the key to success isn't just throwing more data at the problem, but understanding the specific information structure of the problem itself.

Technical Summary: Information-Theoretic Foundations for Machine Learning

Problem Statement

The rapid progress of machine learning over the past decade has largely outpaced the development of rigorous theoretical frameworks capable of explaining empirical observations. While practitioners have successfully guided experimentation through large-scale empirical investigations, existing theoretical tools—such as Frequentist PAC learning bounds (VC dimension, Rademacher complexity)—often fail to explain modern phenomena, particularly in deep learning. These traditional bounds tend to be vacuous for overparameterized models or rely on rigid assumptions (e.g., specific mixing times for sequential data) that do not hold in complex, real-world settings.

Furthermore, as models scale, the "misspecification" problem becomes prominent: the data-generating process is often more complex than the learner's model (e.g., an infinite-width network generating data for a finite-width learner). Current analyses struggle to characterize the trade-offs between model complexity, dataset size, and performance in these misspecified regimes, especially under computational constraints.

Methodology

The authors propose a unified theoretical framework rooted in Bayesian statistics and Shannon's information theory. The core philosophy follows Shannon's maxim of "information first, then computation," aiming to characterize the fundamental limits of learning before addressing computational constraints.

Core Framework

Probabilistic Setup: The learning process is modeled as a Bayesian agent observing a stream of data pairs $(X_t, Y_{t+1})$ generated by an underlying latent variable $\theta$ . The agent maintains a posterior distribution over $\theta$ and produces a predictive distribution $P_t$ .
Loss Metric: The performance metric is the expected log-loss (cross-entropy). The authors establish that minimizing expected log-loss is equivalent to minimizing the expected Kullback-Leibler (KL) divergence between the "clairvoyant" predictive distribution (which knows $\theta$ ) and the learner's predictive distribution.
Error as Information: A central theoretical result (Theorem 15) equates the average error of an optimal Bayesian learner over a horizon $T$ to the mutual information between the observed history $H_T$ and the latent parameter $\theta$ , normalized by $T$ :
$L_T = \frac{I(\theta; H_T)}{T}$
Rate-Distortion Characterization: To bound this mutual information for complex problems where exact calculation is intractable, the framework utilizes rate-distortion theory. The error is bounded above and below by the $T$ -horizon rate-distortion function $H_{\epsilon, T}(\theta)$ , which quantifies the minimum information rate required to approximate $\theta$ within a distortion threshold $\epsilon$ .
$\sup_{\epsilon \ge 0} \min \left\{ \frac{H_{\epsilon, T}(\theta)}{T}, \epsilon \right\} \le L_T \le \inf_{\epsilon \ge 0} \left( \frac{H_{\epsilon, T}(\theta)}{T} + \epsilon \right)$

Extensions

The framework is extended to handle:

Sequential Data: Removing the assumption of independent and identically distributed (iid) data, applying to autoregressive processes and Transformers without relying on mixing time assumptions.
Meta-Learning: Analyzing hierarchical data structures where tasks are drawn from a meta-distribution, decomposing error into "meta-error" (learning the task distribution) and "intra-task error."
Misspecification: Characterizing the error of learners using a prior distribution $Q$ that differs from the true data-generating prior $P$ . The total error is decomposed into a statistical error (learning the constrained approximation) and an irreducible misspecification error.

Key Contributions and Results

1. Unification of Learning Paradigms

The framework provides a single analytical toolset applicable to diverse settings:

Iid Data: Derives tight error bounds for linear regression, logistic regression, and finite/infinite-width Multi-Layer Perceptrons (MLPs).
- Result: For linear regression, the error scales as $\tilde{O}(d/T)$ .
- Result: For finite-width MLPs with $P$ parameters, the error scales linearly with $P$ ( $O(P/T)$ ), improving upon frequentist bounds that often scale with $P \times \text{depth}$ .
- Result: For infinite-width MLPs (Dirichlet process), the error scales as $\tilde{O}(K/T)$ , where $K$ is a scale parameter controlling sparsity, demonstrating that infinite models can be learned efficiently if the prior induces structure.
Sequential Data:
- Binary AR(K): Error bounds scale with the product of embedding dimension and context length ($dK/T$).
- Transformers: Derives error bounds for Transformer processes, showing scaling linear in the product of parameter count and depth, though with a quadratic depth dependence due to the Lipschitz properties of attention mechanisms.
Meta-Learning:
- Analyzes a "Mixture of Transformers" setting. The error decomposes into a term decaying with the total number of tokens ($MT$) and a term decaying with the number of tasks ( $M$ ). This formalizes the intuition that pre-training on diverse tasks allows for rapid adaptation to new tasks.

2. Analysis of Misspecification and Scaling Laws

The paper rigorously characterizes the trade-off between model capacity and dataset size under a fixed computational budget (FLOPs).

Misspecification Error: When a learner uses a misspecified prior (e.g., ignoring a feature or using a wrong noise variance), the error contains an irreducible component. However, the authors show that misspecifying the noise variance to compensate for missing features can actually reduce the total error compared to a correctly specified model with missing features.
Neural Scaling Laws: Applying the misspecification framework to a finite-width network learning from an infinite-width teacher, the authors derive an optimal allocation of resources.
- Result: Under a fixed FLOP constraint $C = p \times T$ , the optimal number of parameters $p^*$ scales as $\tilde{\Theta}(\sqrt{C})$ . This implies that the optimal dataset size and parameter count exhibit a linear relationship, consistent with empirical findings by Hoffmann et al. [2022] and Kaplan et al. [2020].

3. Comparison to Minimax and Frequentist Approaches

The authors contrast their Bayesian information-theoretic approach with Frequentist minimax analysis.

They show that while minimax error corresponds to channel capacity, bounding it often requires constructing complex confidence sets that lead to vacuous bounds for deep learning.
In contrast, the Bayesian approach allows for the specification of simple priors (e.g., Gaussian) that yield elegant, non-vacuous sample complexity results, reflecting the "average-case" performance observed in practice rather than worst-case scenarios.

Significance and Claims

The paper claims to provide a general, mathematically rigorous framework that unifies the analysis of machine learning phenomena across varying levels of data complexity (iid, sequential, hierarchical) and model fidelity (correctly specified, misspecified).

For Theorists: It offers a rigorous foundation that leaves open many avenues for future exploration, particularly in bounding mutual information via rate-distortion functions for complex architectures.
For Practitioners: It provides intuitive results that explain why larger models and datasets improve performance, even in misspecified regimes. The framework suggests that the "shadows" of empirical reality observed in the "cave" of current ML practice can be understood through the lens of information acquisition.
Fundamental Insight: The work posits that the performance limits of machine learning are fundamentally determined by the informational content of the data relative to the model's capacity, independent of computational constraints. The authors argue that their tools provide accurate insights where existing theories (like PAC bounds) fail, particularly in explaining the success of overparameterized models and the scaling laws observed in Large Language Models (LLMs).

The paper concludes that while it does not address computational constraints directly, empirical evidence suggests that practical stochastic gradient algorithms are capable of attaining the information-performance trade-offs established by this theory.