📊 statistics

Width-Robust Learnability in Mean-Field Bayesian Neural Networks

This paper establishes that for mean-field Bayesian neural networks, a target function is learnable from polynomial samples at infinite width if and only if it is learnable at polynomial width, provided its reduced entropy is polynomially bounded, thereby proving that the infinite-width limit preserves the complexity-theoretic inductive bias of finite networks without introducing spurious generalization power.

Original authors: Dmitry Vaintrob, Kaarel Hänni

Published 2026-07-08

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Dmitry Vaintrob, Kaarel Hänni

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

The Big Picture: Does Bigger Always Mean Better?

Imagine you are trying to teach a robot to recognize patterns. You have two choices:

The "Tiny" Robot: A small network with a limited number of neurons (like a simple brain).
The "Infinite" Robot: A theoretical giant network with infinite neurons.

In the world of machine learning, we often assume that if a small robot can learn a task, a giant robot can definitely do it too. But the reverse is the tricky part: If a giant, infinite robot learns a task, does that mean a small robot could have learned it too?

Sometimes, the answer is "no." There are mathematical scenarios where an infinite network learns something simply because it has infinite resources, but a small network would fail. This paper asks: Is there a "sweet spot" where the infinite network behaves exactly like a small, efficient one?

The authors say yes, but only under specific conditions (a regime called "Mean-Field"). They prove that in this specific setting, if an infinite network can learn a pattern from a reasonable amount of data, a small network can learn it too. The infinite network doesn't have any "magic superpowers" that a small one lacks.

The Core Concept: The "Reduced Entropy" Score

To understand why this happens, the authors introduce a new way to measure how "hard" a task is. They call this Reduced Entropy.

Think of the neural network's weights as a giant library of possible functions.

Simple tasks (like recognizing a circle) are like popular books in the library. There are millions of copies, so it's easy to find one. The "cost" to find one is low.
Complex tasks (like memorizing a random noise pattern) are like rare, one-of-a-kind manuscripts. You have to search the whole library to find them. The "cost" is high.

The Reduced Entropy is a score that measures this cost.

Low Score: The task is easy; the network naturally "wants" to learn it.
High Score: The task is hard; the network has to work very hard (or use infinite resources) to find a solution.

The Paper's Main Claim:
If a task has a Low Score (it's naturally easy for the network), then:

An infinite network can learn it.
A small (polynomial-sized) network can learn it.
They will learn the exact same thing.

If the score is high, neither can learn it efficiently. The infinite network doesn't cheat; it just confirms what the small network could have done.

The Two Magic Tricks: "Cloning" and "Subsampling"

The paper proves this equivalence using two clever mathematical tricks, which act like a bridge between the infinite and the finite.

1. Cloning (The "Converse" Trick)

Scenario: You have a small, perfect teacher network that already knows the answer.
The Trick: You can take that small teacher and "clone" it inside a giant, infinite network.

Imagine you have one expert chef. You hire 1,000 clones of that chef.
Even though you have 1,000 chefs, they are all doing the exact same thing.
The paper shows that because the "cloned" solution is so similar to the original small network, the giant network doesn't have to pay a huge "cost" (entropy) to find it.
Result: If a small network can do it, the giant network can find that solution easily.

2. Subsampling (The "Forward" Trick)

Scenario: You have a giant, infinite network that has learned a solution. You want to shrink it down to a small network without losing the answer.
The Trick: The authors show you can "compress" the giant network by picking a few representatives and ignoring the rest, but with a twist. They split the neurons into two groups:

The "Active" Neurons: These are the neurons that actually learned something useful from the data (like the specific features of a cat). The paper says you can keep a small number of these and they will do the heavy lifting.
The "Lazy" Neurons: These are the neurons that didn't really change much; they are just doing random noise that happens to average out.
The Swap: Here is the magic. The paper proves that for the "Lazy" neurons, you can throw away the ones the giant network actually picked and replace them with fresh, random noise from the start. Surprisingly, the output of the network barely changes!
Result: You can take the infinite solution, keep the few "Active" neurons, swap the "Lazy" ones for random noise, and end up with a tiny, polynomial-sized network that gives the exact same answer as the infinite one.

The "Lazy" vs. "Active" Analogy

To visualize the "Mean-Field" scaling (the specific setting where this works), imagine a choir singing a song.

The "Lazy" Regime (Too small): The choir is so small and rigid that they can't change their tune based on the audience. They just sing a fixed song (like a standard radio station). They can't learn complex new songs.
The "Over-Rich" Regime (Too big): The choir is so massive that the audience's feedback gets lost in the noise. The choir sings everything at once, and it's hard to tell who is singing what.
The "Mean-Field" Regime (The Sweet Spot): The choir is large, but organized.
- A few Soloists (Active) step forward to sing the specific melody the audience asked for.
- The rest of the choir (Lazy) provides a background hum.
- The paper proves that if you record the Soloists and replace the background hum with a fresh recording of the same hum, the song sounds identical. You don't need the whole choir to hear the song; you just need the Soloists and a standard background track.

Why This Matters (According to the Paper)

The paper provides a "sanity check" for using infinite models.

Sometimes, mathematicians use "infinite width" models because they are easier to write equations for.
A common fear is: "Does this infinite model solve problems that real, finite computers can't?"
This paper says: No. In this specific setting, the infinite model is just a cleaner way of describing what a finite model is doing. It doesn't have any hidden computational superpowers. If the infinite model learns it, a small model can too.

Summary

The paper proves that for a specific type of neural network (Mean-Field Bayesian), learning ability is "width-robust."

If an infinite network learns a task, a small network can too.
The "cost" of learning (Reduced Entropy) determines if a task is learnable, not the size of the network.
You can shrink an infinite solution down to a small one by keeping the "active" parts and swapping the "lazy" parts for random noise, with no loss in performance.

Technical Summary: Width-Robust Learnability in Mean-Field Bayesian Neural Networks

Problem Statement

The paper addresses a fundamental gap in the theoretical understanding of overparameterized neural networks: the disconnect between the infinite-width limit and the behavior of large, finite-width networks. While infinite-width limits (such as the Neural Tangent Kernel or NNGP regimes) provide clean analytic descriptions, it is not guaranteed that these limits preserve the complexity-theoretic inductive bias of finite networks. Specifically, in "lazy" scaling regimes ( $\gamma < 1$ ), networks behave as fixed kernel methods, which are known to require super-polynomial samples to learn simple structured targets (e.g., parities) that small finite networks can compute.

The authors investigate the mean-field scaling (or critical feature-learning regime, $\gamma = 1$ ), where the distribution of hidden neurons is allowed to adapt to data. The central question is whether the infinite-width mean-field learner possesses the same learnability properties as its polynomial-width counterparts. The paper seeks to characterize the inductive bias of the mean-field limit and determine if the "infinite resource" of infinite width introduces spurious generalization power or merely simplifies the analytic description.

Methodology and Framework

1. The Reduced Entropy Complexity Measure

The authors define a complexity measure for a target function $y$ relative to the prior, termed the reduced entropy $s_\infty(y, \varepsilon)$ :
$s_\infty(y, \varepsilon) = \limsup_{N \to \infty} \left( -\frac{1}{N} \log \pi_0^N(L \le \varepsilon) \right)$
where $\pi_0^N(L \le \varepsilon)$ is the prior probability that a width- $N$ network achieves population mean-squared error at most $\varepsilon$ . This quantity represents the intensive prior cost (in nats per neuron) of representing the target. A target is considered "simple" if its reduced entropy is polynomially bounded in the input dimension $d$ .

2. The Mean-Field Limit and Spectral Split

The analysis relies on the standard mean-field description where, as $N \to \infty$ , the posterior is described by a tower of single-site laws (propagation of chaos). A key technical insight is the spectral split of the feature kernel $K_\ell$ at each layer:

Active Space ( $V$ ): A low-dimensional subspace corresponding to the top eigenvalues of the kernel, which carry data-dependent information.
Lazy Bulk ( $C$ ): The remaining bulk of the spectrum, which behaves like the prior (kernel regime).
At the critical scaling $\gamma=1$ , the lazy bulk remains significant (of the same order as the accuracy threshold $\varepsilon$ ), unlike in the over-rich regime ( $\gamma > 1$ ) where it becomes negligible.

3. Core Mechanisms: Compression and Conservation

The paper establishes an equivalence between learnability and reduced entropy through two inverse operations:

Pointwise Compression (Forward Direction): The authors prove that any infinite-width mean-field solution with low reduced entropy can be compressed into a polynomial-width network that agrees with the infinite-width solution pointwise (i.e., $|f_{\hat{\theta}}(x) - f_\infty(x)| \le \delta$ for all $x$ ).
- Technique: This involves a subsample-and-resample strategy. The construction subsamples a polynomial number of neurons to reconstruct the active components (using fixed eigenfunctions to avoid bias). For the lazy components, instead of trying to preserve the specific realized coordinates, the method resamples them from the prior distribution.
- Key Lemma: The Lazy-Swap Lemma (Lemma 5.1) proves that replacing the realized lazy coordinates with fresh prior noise introduces negligible error, provided the "lazy susceptibility" is bounded. This relies on Stein's method and the small operator norm of the lazy block.
Conservation by Cloning (Converse Direction): The authors prove that if a target is computable by a polynomial-width network (a "teacher"), then its reduced entropy is polynomially bounded.
- Technique: Cloning. A narrow teacher network is imitated within a wide network by "cloning" each teacher neuron into a group of $m$ neurons. The weights of the group are constrained to be close to the teacher's weights, while the orthogonal degrees of freedom remain at the prior.
- Result: Since the data occupies only a polynomial-dimensional subspace (the teacher's width), the relative entropy cost to reach the accurate region is polynomial in the teacher's width, ensuring low reduced entropy.

Key Results

Theorem 3.1: Width-Robust Learnability

For a family of targets on the Boolean cube and fixed depth, the following are equivalent (up to polynomial slack in accuracy, width, and sample size):

The target is learnable at infinite width from polynomially many samples.
The target is learnable at polynomial width from polynomially many samples.
The target is computed to $o(1)$ error by a polynomial-width network with polynomial-weight size.
The reduced entropy $s_\infty(y, \varepsilon)$ is polynomially bounded in $d$ .

This theorem establishes that the mean-field limit does not acquire artificial computational advantages; the class of learnable targets is identical to that of polynomial-width networks.

Theorem 3.2: Compression and Conservation

Compression: If $s_\infty(y, \varepsilon_-) \le s$ , there exists a width- $N_0 = \text{poly}(s, d, 1/\Delta)$ network that matches the infinite-width solution pointwise with high probability.
Conservation: If a width- $W$ network achieves error $\varepsilon_-$ , then $s_\infty(y, \varepsilon) \le \text{poly}(W, d)$ .

Generalization Bounds

The paper demonstrates that the infinite-width Gibbs posterior generalizes if and only if the reduced entropy is low. The proof utilizes uniform convergence over a fixed, data-independent class of functions constructed via the compression theorem, rather than relying on risk bounds alone.

Significance and Claims

The paper claims to provide a complexity-theoretic sanity check for the mean-field limit. It argues that the infinite-width object is not a "magic" learner that solves problems impossible for finite networks; rather, it is a cleaner analytic description of the same learning phenomena.

Inductive Bias Conservation: The primary contribution is showing that the inductive bias (the complexity ordering of targets) is width-robust. The mechanisms visible in the mean-field equations (active feature learning vs. lazy kernel behavior) are not artifacts of infinite resources but reflect the fundamental structure of the learning problem.
Pointwise vs. Mean-Square: The authors emphasize that their result is stronger than a mere coincidence of risk values. The infinite-width and polynomial-width learners agree pointwise, meaning the function learned at infinite width is explicitly reproducible by a finite network. This allows the infinite-width solution to be placed in a fixed, finite-dimensional class for uniform convergence arguments.
Critical Scaling ( $\gamma=1$ ): The paper highlights that $\gamma=1$ is the delicate case where both active and lazy components must be handled. In the over-rich regime ( $\gamma > 1$ ), the lazy bulk is negligible, making compression trivial. In the lazy regime ( $\gamma < 1$ ), the learner reduces to kernel learning. The $\gamma=1$ regime is unique because the lazy component is of the same order as the accuracy threshold, requiring the specific "lazy-swap" mechanism to preserve the law of the solution without preserving the specific coordinates.

The authors explicitly state that they do not claim that arbitrary finite training algorithms find the Gibbs posterior, nor that the constants are practical. The result is a characterization of the Bayesian mean-field inductive bias. They also note that while the result resembles a "P/poly" statement (learnable iff computable by a small circuit), the reductions incur depth-dependent factors, so the complexity statement is coarse and tracks polynomial size rather than precise circuit depth.