Introduction
Modern learners are routinely trained until they fit their training data perfectly, even when some of the training labels are wrong. Deep networks fit randomly relabelled data [75 ] . Random forests and boosted ensembles reach zero training error and keep improving [62 , 72 ] . Minimum-norm least squares interpolates noisy targets and can still be consistent [7 , 33 ] . This behaviour is called benign overfitting . It is not universal: other interpolators, such as the 1-nearest-neighbour rule, settle at a fixed excess risk (tempered overfitting ), and some fail completely (catastrophic overfitting ) [48 ] . All three kinds of learner have the same training error, zero, so whatever separates them is invisible on the training set.
In this paper we ask two questions about interpolating learners.
(Q1) What separates a benign interpolator from a harmful one? In particular, is there an information-theoretic quantity that does so, given that interpolators all memorize their training labels?
(Q2) Can we use that quantity to choose among interpolating learners? Training error cannot rank them, and validation labels may be scarce or noisy themselves.
Why information theory, and why it has struggled here. Information theory gives a natural language for “how much a model has learned from its data”. Information-theoretic generalization bounds control the generalization gap by the mutual information I ( W ; S ) I(W; S) I ( W ; S ) between the trained weights W W W and the training sample S S S [60 , 73 , 65 ] . The information bottleneck (IB) describes good representations as those that compress the input while keeping what is relevant for the label [69 , 68 ] . Both views have difficulties with interpolators. Any learner that fits noisy labels must store them, so I ( W ; S ) I(W; S) I ( W ; S ) is large for every interpolator, benign or not [31 , 46 ] . And for deterministic models the IB quantities are degenerate [3 , 43 , 61 ] .
An earlier attempt. Two earlier non-archival papers by the author described margin-maximizing boosting as lossless maximal compression (LMC): a model whose output keeps all the information about the label that the input has, while being as compressed as possible [55 , 54 ] ; we refer to them as the LMC papers. That work had flaws. Its central object does not exist when labels are noisy, its empirical estimates are degenerate for any interpolator, and some of its experimental claims do not survive replication. We therefore do not treat it as an established framework. This paper builds the framework from scratch and corrects the earlier work as it goes. Appendix § 18 gives a full erratum.
Our approach in one paragraph. We separate what a learner stores from what it expresses . Storage is the information the trained model keeps about the training labels, I ( W ; Y n ∣ X n ) I(W; Y^n \mid X^n) I ( W ; Y n ∣ X n ) . Expression is the information about the training sample that reaches the model’s prediction at a fresh input x x x . We measure it by the expressed information
V ( x ) = H ( h W ( x ) ) , V(x) = H(h_W(x)), V ( x ) = H ( h W ( x )) ,
the entropy1 of the prediction h W ( x ) h_W(x) h W ( x ) at x x x when the training sample (and any training randomness) is drawn afresh. In plain terms, V ( x ) V(x) V ( x ) is zero if every training sample leads to the same prediction at
x x x , and it is large if the prediction at x x x depends on which particular sample, and so which particular noisy labels, the learner happened to see. § 4.1 explains both words informally, with an analogy; in this sense, both are terms introduced in this paper (Table 2 lists which of our terms are new and which are standard). Storage and expression behave very differently for interpolators. Every interpolator stores exactly n H ( Y ∣ X ) n\,H(Y \mid X) n H ( Y ∣ X ) bits of label noise (Theorem 5 ), so storage cannot tell them apart. Expression can: excess risk is controlled from above and below by expressed information plus a “modal bias” term (Theorem 9 ).
Table 2. Terminology. “New”: term (and, where stated, quantity) introduced in this paper. “Adapted”: an existing notion specialized or renamed here. “Standard”: used as in the cited literature.
A running example. We will use one simple task throughout the paper (Example 1 in § 2 ). The input consists of one informative discrete feature and 16 irrelevant binary features; the label is a noisy function of the informative feature. Every learner in Table 1 interpolates its noisy training labels, including a memorize-and-smooth learner that we construct for this purpose,2 and every one has the same score under the old LMC criterion.3 Yet their excess risks differ by two orders of magnitude, and their expressed information ranks them correctly. We return to this example at each step of the development.
Table 1. The running example (Example 1) with n = 4096 n = 4096 n = 4096 training points and label noise ε = 0.2 \varepsilon= 0.2 ε = 0.2 . All five learners interpolate. The legacy LMC score of Nikolaou et al. [55 ] is the same for all of them, while their excess risks differ by two orders of magnitude. Expressed information V V V (§ 4.3 ) ranks them correctly. Best value per column in bold (the two degenerate columns are identical for all learners). †: learner constructed in this paper (Proposition 16 ).
Contributions. Our contributions are the following.
A framework for the ideal model (§ 3 ). For a general loss we define ℓ \ell ℓ -sufficient representations, the minimal sufficient complexity C ℓ ∗ = H ( a ∗ ( X ) ) C_\ell^* = H(a^*(X)) C ℓ ∗ = H ( a ∗ ( X )) (the entropy of the Bayes act), maximal complexity, and excess complexity. We relate them to decision-theoretic sufficiency, to the indirect rate–distortion function, and to the information bottleneck. We show that the original LMC exists only in degenerate cases, and that its generalized form, the minimal ℓ \ell ℓ -sufficient representation, always exists.
Storage versus expression (§ 4 ). We show that every interpolator stores exactly n H ( Y ∣ n\,H(Y \mid n H ( Y ∣
X) bits of label noise (sharpening a bound of Harutyunyan et al., [31 ] ), and that information-theoretic generalization bounds, including those based on conditional mutual information (Steinke and Zakynthinou, [65 ] ), therefore cannot separate benign from tempered interpolators. We introduce expressed information and prove a two-sided information decomposition of excess risk, which is exact for binary labels. We show that a learner’s output entropy at fresh inputs splits into complexity and expression, and that a consistent learner’s outputs converge to the minimal sufficient representation.
Benign overfitting as vanishing expression (§ 5 ). We give an information-theoretic version of the benign/tempered/catastrophic taxonomy. We work it out for an explicit benign interpolator, for nearest-neighbour rules (recovering the classical result of Cover and Hart, [17 ] ), for averaging, and for minimum-norm least squares, where the expressed information equals the variance term of Bartlett et al. [7 ] . Double descent appears as a peak of expressed information.
Expressed information as a model-selection criterion (§ 6 ). We show that among candidates with no modal bias, excess risk is monotone in expressed information, and we argue that the overparameterized regime is where this condition is most nearly met. We explain how to estimate V V V from a single dataset, and why disjoint splits must be used. Because it needs no held-out labels, only unlabelled inputs, it suits settings where validation labels are scarce, delayed or noisy (semi-supervised and streaming data, label noise, covariate shift; § 9 ). We characterize where V V V alone fails and give two remedies: a label-free consensus criterion, and a switch to noise-corrected validation when the label noise is asymmetric.
Connections to bias–variance and disagreement (§ 4.6 ). We show that the 0-1 variances of Kohavi–Wolpert, Domingos and James and the disagreement of two independently trained models are equivalent to V V V up to explicit bounds, and that disagreement bounds excess risk from above and below: the generalization disagreement equality of Jiang et al. [39 ] holds exactly for the 1-NN rule and fails by the Bayes risk for benign learners.
Experiments (§ 7 ) on synthetic tasks with exact excess risk and on 15 real datasets. Among overparameterized candidates on a single noisy dataset, V V V computed from two disjoint halves has 60% less regret than holdout validation and 44% less than 2-fold cross-validation at about the same cost, and matches 5-fold cross-validation (15 datasets, five seeds each). At matched cost it also beats selection by conditional mutual information, which, unlike V V V , needs held-out labels.
Roadmap. § 2 fixes notation and introduces the running example. § 3 describes the ideal model. § 4 separates storage from expression, and § 5 uses this separation to explain benign overfitting. § 6 turns expressed information into a selection rule, and § 7 tests the theory and the rule. § 8 discusses connections to existing work, and § 9 discusses limitations. Proofs, further theory, the erratum for the LMC papers, experimental details, additional results and the extension to regression are in the appendices, which form the supplementary material. Code to reproduce every result is available at https://github.com/nnickolaou/GLMC , and Appendix § 24 describes it.
Setting, notation and a running example
Let us first fix the notation that we will use throughout, and introduce the simple example that we will return to in every section.
Data and Bayes classifier. A pair ( X , Y ) (X,Y) ( X , Y ) is drawn from a distribution P P P on X × Y \mathcal{X} \times\mathcal{Y} X × Y . In most of the paper Y = [ K ] = { 1 , … , K } \mathcal{Y} = [K] = \{1,\ldots,K\} Y = [ K ] = { 1 , … , K } is a set of K K K classes; § 4.5 treats real-valued Y Y Y . For the information-theoretic statements we take X \mathcal{X} X to be finite or countable with H ( X ) < ∞ H(X) < \infty H ( X ) < ∞ (continuous inputs are handled by the learner-level quantities of § 4 , which do not need this). We write
η ( x ) = ( P ( Y = 1 ∣ X = x ) , … , P ( Y = K ∣ X = x ) ) \eta(x) = \left(\mathbb{P}(Y=1 \mid X=x),\ldots,\mathbb{P}(Y=K \mid X=x)\right) η ( x ) = ( P ( Y = 1 ∣ X = x ) , … , P ( Y = K ∣ X = x ) )
for the vector of class probabilities at x x x . The Bayes classifier predicts the most likely class, b ∗ ( x ) = arg max k η k ( x ) b^*(x) = \arg\max_k \eta_k(x) b ∗ ( x ) = arg max k η k ( x ) , and the Bayes risk R ∗ = P ( b ∗ ( X ) ≠ Y ) R^* = \mathbb{P}(b^*(X) \ne Y) R ∗ = P ( b ∗ ( X ) = Y ) is the smallest achievable error. Its excess risk , R ( h ) − R ∗ R(h)-R^* R ( h ) − R ∗ with R ( h ) = P ( h ( X ) ≠ Y ) R(h) = \mathbb{P}(h(X) \ne Y) R ( h ) = P ( h ( X ) = Y ) , measures how far a classifier h h h is from that ideal. When the labels are noisy, R ∗ > 0 R^* > 0 R ∗ > 0 : even the best classifier makes mistakes, because the label is not a function of the input.
Learners. A training sample S = ( ( X 1 , Y 1 ) , … , ( X n , Y n ) ) S = ((X_1,Y_1),\ldots,(X_n,Y_n)) S = (( X 1 , Y 1 ) , … , ( X n , Y n )) consists of n n n independent draws from P P P . A learner A A A maps the sample, and possibly some internal randomness ξ \xi ξ (a random seed, independent of S S S ), to a trained model W = A ( S , ξ ) W = A(S,\xi) W = A ( S , ξ ) , which induces a classifier h W : X → [ K ] h_W : \mathcal{X} \to[K] h W : X → [ K ] . We say that the learner interpolates if h W ( X i ) = Y i h_W(X_i) = Y_i h W ( X i ) = Y i for every training point, almost surely. The important point to keep in mind is that W W W is random: a different sample, or a different seed, gives a different trained model. Much of this paper is about how much the predictions of h W h_W h W vary because of this randomness.
Information measures. H ( ⋅ ) H(\cdot) H ( ⋅ ) denotes Shannon entropy, H ( ⋅ ∣ ⋅ ) H(\cdot\mid\cdot) H ( ⋅ ∣ ⋅ ) conditional entropy and I ( ⋅ ; ⋅ ) I(\cdot;\cdot) I ( ⋅ ; ⋅ ) mutual information ([18 ] ). Unless stated otherwise we measure them in bits. For a probability vector q q q we write H ( q ) = − ∑ k q k log 2 q k H(q) = -\sum_k q_k \log_2 q_k H ( q ) = − ∑ k q k log 2 q k , and h ( t ) = H ( ( t , 1 − t ) ) h(t) = H((t,1-t)) h ( t ) = H (( t , 1 − t )) is the binary entropy. Two quantities of the data distribution will appear repeatedly: H ( Y ∣ X ) H(Y \mid X) H ( Y ∣ X ) , the label noise (the uncertainty about Y Y Y that remains when X X X is known), and I ( X ; Y ) I(X;Y) I ( X ; Y ) , the information the input carries about the label.
The running example. We will illustrate every definition and result on the following task. It is chosen so that all quantities can be computed exactly, and so that it contains the two ingredients that matter: label noise, and input features that carry no information about the label.
Example 1 (Running example). The input is X = ( Z , U ) X = (Z,U) X = ( Z , U ) , where Z Z Z is uniform on { 0 , 1 , … , 7 } \{0,1,\ldots,7\} { 0 , 1 , … , 7 } and U U U is uniform on { 0 , 1 } 16 \{0,1\}^{16} { 0 , 1 } 16 , independent of Z Z Z . The label is Y ∈ { 0 , 1 } Y \in\{0,1\} Y ∈ { 0 , 1 } , and it depends on Z Z Z only: the clean label is 1 { Z ≥ 4 } 1\{Z \ge4\} 1 { Z ≥ 4 } , and it is flipped with probability ε \varepsilon ε when Z Z Z is even and with probability ε / 2 \varepsilon/2 ε /2 when Z Z Z is odd. So Z Z Z is the informative part of the input, and the 16 bits of U U U are pure distractors.
For ε = 0.2 \varepsilon= 0.2 ε = 0.2 , which we use throughout unless stated otherwise, the quantities above are as follows.
The Bayes classifier is b ∗ ( X ) = 1 { Z ≥ 4 } b^*(X) = 1\{Z \ge4\} b ∗ ( X ) = 1 { Z ≥ 4 } , and the Bayes risk is R ∗ = 1 2 ( 0.2 ) + 1 2 ( 0.1 ) = 0.15 R^* = \frac{1}{2}(0.2) + \frac{1}{2}(0.1) = 0.15 R ∗ = 2 1 ( 0.2 ) + 2 1 ( 0.1 ) = 0.15 .
The label noise is H ( Y ∣ X ) = 1 2 h ( 0.2 ) + 1 2 h ( 0.1 ) = 0.595 H(Y \mid X) = \frac{1}{2}h(0.2) + \frac{1}{2}h(0.1) = 0.595 H ( Y ∣ X ) = 2 1 h ( 0.2 ) + 2 1 h ( 0.1 ) = 0.595 bits per example.
H ( X ) = 3 + 16 = 19 H(X) = 3 + 16 = 19 H ( X ) = 3 + 16 = 19 bits, H ( b ∗ ( X ) ) = 1 H(b^*(X)) = 1 H ( b ∗ ( X )) = 1 bit, and η ( X ) \eta(X) η ( X ) takes four equally likely values, so H ( η ( X ) ) = 2 H(\eta(X)) = 2 H ( η ( X )) = 2 bits.
In words: a good model of this task needs to know only one bit about each input (which half Z Z Z falls in), out of the 19 bits the input contains. We will see in § 3 that these three numbers, 1, 2 and 19 bits, are respectively the minimal sufficient complexity under 0-1 loss, the minimal sufficient complexity under log-loss, and the maximal complexity. In § 4 we will see that the label noise of 0.595 bits per example is exactly what every interpolator must store.
Losses. Sections 4–6 focus on classification error (0-1 loss). The definitions of § 3 hold for a general loss ℓ : A × Y → [ 0 , ∞ ] \ell: \mathcal{A} \times\mathcal{Y} \to[0,\infty] ℓ : A × Y → [ 0 , ∞ ] , where A \mathcal{A} A is a set of actions. For a probability vector q q q , let L ( a , q ) = ∑ k q k ℓ ( a , k ) L(a,q) = \sum_k q_k \ell(a,k) L ( a , q ) = ∑ k q k ℓ ( a , k ) be the expected loss of action a a a when the label has distribution q q q . The Bayes act at x x x , written a ∗ ( x ) a^*(x) a ∗ ( x ) , is the action that minimizes L ( a , η ( x ) ) L(a,\eta(x)) L ( a , η ( x )) . Two cases will be used repeatedly.
Under log-loss , the action is a probability vector q q q , ℓ ( q , k ) = − log q k \ell(q,k) = -\log q_k ℓ ( q , k ) = − log q k , and the Bayes act is the vector of true class probabilities, a ∗ = η a^* = \eta a ∗ = η .
We assume, as is standard, that minimizers exist and that the Bayes act is unique for almost every x x x (for 0-1 loss: there are no ties). Appendix § 12 states these regularity conditions precisely.
Terminology. Because this paper connects several literatures, and introduces some terms of its own, Table 2 lists the main terms, says which are standard, which adapt an existing notion, and which are introduced here, and points to where each is defined.
The ideal model: sufficiency, minimal and excess complexity
Before studying what learners do, it is useful to describe what an ideal model would look like in information-theoretic terms. In this section we ask: what is the least information about the input that a model’s output must carry to be optimal, and how much more than that does a given model carry? This gives us three reference points, the minimal sufficient, maximal and excess complexity, which we will use in § 4 and § 5 to describe what benign interpolators converge to. Everything in this section is a property of the data distribution and of a fixed model; learning from samples enters only in § 4 .
Representations and sufficiency
A representation of the input is a random variable T T T computed from X X X , possibly with extra randomness that does not depend on Y Y Y . Formally, Y − X − T Y - X - T Y − X − T is a Markov chain. The output F = f ( X ) F = f(X) F = f ( X ) of a fixed model is a representation, but so is an intermediate layer, a clustering of the inputs, or the input itself. To judge how useful a representation is for a loss ℓ \ell ℓ , we allow ourselves to post-process it in the best possible way. The recalibrated risk of T T T is
R ℓ ( T ) = inf g E ℓ ( g ( T ) , Y ) , R_{\ell}(T) = \inf_{g} \mathbb{E} \ell(g(T),Y), R ℓ ( T ) = g inf E ℓ ( g ( T ) , Y ) ,
where the infimum is over all functions g g g from the values of T T T to actions. In plain terms, R ℓ ( T ) R_{\ell}(T) R ℓ ( T ) is the risk of the best decision rule that only gets to see T T T . Recalibration makes the theory invariant to relabelling the values of T T T , as mutual information is. For example, a classifier that always outputs the wrong one of two classes is, after recalibration, a perfect classifier. Under log-loss the recalibrated risk is simply the conditional entropy, R log ( T ) = H ( Y ∣ T ) R_{\log}(T) = H(Y \mid T) R l o g ( T ) = H ( Y ∣ T ) .
Definition 1 (ℓ \ell ℓ -sufficiency and ℓ \ell ℓ -deficiency). A representation T T T is ℓ \ell ℓ -sufficient if R ℓ ( T ) = R ℓ ∗ R_{\ell}(T) = R_{\ell}^{*} R ℓ ( T ) = R ℓ ∗ , where R ℓ ∗ = E ℓ ( a ∗ ( X ) , Y ) R_{\ell}^{*} = \mathbb{E}\,\ell(a^{*}(X), Y) R ℓ ∗ = E ℓ ( a ∗ ( X ) , Y ) is the Bayes risk for ℓ \ell ℓ . Its ℓ \ell ℓ -deficiency is Δ ℓ ( T ) = R ℓ ( T ) − R ℓ ∗ ≥ 0 \Delta_{\ell}(T) = R_{\ell}(T) - R_{\ell}^{*} \ge0 Δ ℓ ( T ) = R ℓ ( T ) − R ℓ ∗ ≥ 0 .
In words, T T T is ℓ \ell ℓ -sufficient if nothing is lost, as far as the loss ℓ \ell ℓ is concerned, by looking at T T T instead of at the whole input X X X . The deficiency measures how much is lost. Sufficiency in this sense is the decision-theoretic sufficiency of Blackwell [13 ] and Le Cam [45 ] , specialized to a single decision problem; deficiency is the single-loss analogue of Le Cam’s deficiency. Under log-loss, ℓ \ell ℓ -sufficiency is ordinary statistical sufficiency of T T T for Y Y Y , and the deficiency is the information lost, Δ log ( T ) = I ( X ; Y ∣ T ) \Delta_{\log}(T) = I(X;Y \mid T) Δ l o g ( T ) = I ( X ; Y ∣ T ) . The LMC papers called ℓ \ell ℓ -sufficient representations “lossless” (Nikolaou et al. [55 ] ); we use the standard term here.
The next result says that sufficiency has a simple characterization: a representation is sufficient exactly when the Bayes act can be read off from it.
Proposition 1 (Sufficiency means the Bayes act is recoverable). T T T is ℓ \ell ℓ -sufficient if and only if a ∗ ( X ) = g ( T ) a^{*}(X) = g(T) a ∗ ( X ) = g ( T ) almost surely for some function g g g . Under log-loss, T T T is sufficient if and only if η ( X ) \eta(X) η ( X )
is a function of T T T , which holds if and only if I ( T ; Y ) = I ( X ; Y ) I(T;Y)=I(X;Y) I ( T ; Y ) = I ( X ; Y ) .
All proofs for this section are in Appendix § 13 . For the running example (Example 1) under 0-1 loss, T T T is sufficient if and only if it reveals whether Z ≥ 4 Z \ge4 Z ≥ 4 . Under log-loss it must reveal more: it must also reveal whether Z Z Z is even or odd, since the noise level, and hence η \eta η , differs between the two.
Minimal sufficient complexity and the G-LMC
Many representations are sufficient; the input X X X itself always is. We are interested in the least complex one. We measure the complexity of a representation by the information it retains about the input, I ( T ; X ) I(T;X) I ( T ; X ) . For a deterministic model output F = f ( X ) F=f(X) F = f ( X ) , this is just the entropy of the output, I ( F ; X ) = H ( F ) I(F;X)=H(F) I ( F ; X ) = H ( F ) .
Theorem 2 (Minimal sufficient complexity). Every ℓ \ell ℓ -sufficient representation T T T satisfies
I ( T ; X ) ≥ C ℓ ∗ ≔ H ( a ∗ ( X ) ) , I(T;X) \ge C_\ell^* \coloneqq H\left(a^*(X)\right), I ( T ; X ) ≥ C ℓ ∗ : = H ( a ∗ ( X ) ) , with equality if and only if T T T depends on X X X only through a ∗ ( X ) a^*(X) a ∗ ( X ) (the Markov chain T − a ∗ ( X ) − X T-a^*(X)-X T − a ∗ ( X ) − X ). A sufficient deterministic output F = f ( X ) F=f(X) F = f ( X ) attains equality if and only if it is a relabelling of the Bayes act, F = φ ( a ∗ ( X ) ) F=\varphi(a^*(X)) F = φ ( a ∗ ( X )) for a bijection φ \varphi φ .
Let us restate the theorem in plain terms. To be optimal for a loss, a model must at least be able to tell apart inputs that call for different optimal actions. The entropy of the optimal action is therefore a floor on the complexity of any optimal model, and the Bayes act itself sits exactly on that floor. Anything that distinguishes inputs within a set that shares the same optimal action is, for this loss, unnecessary.
Definition 2 (Complexities and the G-LMC). 1. The minimal sufficient complexity for ℓ \ell ℓ is C ℓ ∗ = H ( a ∗ ( X ) ) C_\ell^*=H(a^*(X)) C ℓ ∗ = H ( a ∗ ( X )) . A representation that is ℓ \ell ℓ -sufficient and attains I ( T ; X ) = C ℓ ∗ I(T;X)=C_\ell^* I ( T ; X ) = C ℓ ∗ is a minimal ℓ \ell ℓ -sufficient representation ; we also call it a generalized lossless maximal compression (G-LMC) of X X X for ℓ \ell ℓ .
The maximal complexity is C max = H ( X ) C_{\max}=H(X) C m a x = H ( X ) , the complexity of a model that distinguishes every input. When the outputs range over a model family F \mathcal{F} F , we use sup f ∈ F H ( f ( X ) ) \sup_{f\in\mathcal{F}}H(f(X)) sup f ∈ F H ( f ( X )) instead.
The excess complexity of a model output F F F is
E ℓ ( F ) = I ( F ; X ) − R ℓ ( R ℓ ( F ) ) ≥ 0 , \mathcal{E}_\ell(F)=I(F;X)-\mathcal{R}_\ell(\mathcal{R}_\ell(F))\ge0, E ℓ ( F ) = I ( F ; X ) − R ℓ ( R ℓ ( F )) ≥ 0 , where R ℓ \mathcal{R}_\ell R ℓ is the indirect rate–distortion function defined in (1) below.
The excess complexity measures how much more complex F F F is than it needs to be for the risk it achieves . For a sufficient model the definition simplifies.
Proposition 3 (Excess complexity of sufficient models). If F F F is ℓ \ell ℓ -sufficient, then E ℓ ( F ) = I ( F ; X ) − C ℓ ∗ = H ( F ∣ a ∗ ( X ) ) \mathcal{E}_\ell(F)=I(F;X)-C_\ell^*=H(F\mid a^*(X)) E ℓ ( F ) = I ( F ; X ) − C ℓ ∗ = H ( F ∣ a ∗ ( X )) . Under log-loss, moreover, E log ( F ) = H ( F ∣ Y ) − H ( η ( X ) ∣ Y ) \mathcal{E}_{\log}(F)=H(F\mid Y)-H(\eta(X)\mid Y) E l o g ( F ) = H ( F ∣ Y ) − H ( η ( X ) ∣ Y ) .
So, for a sufficient model, the excess complexity is the information that its output carries beyond the Bayes act: the uncertainty that remains about the output when the optimal action is known. The log-loss identity is useful in practice, because it involves the label Y Y Y rather than the unknown η ( X ) \eta(X) η ( X ) ; it gives a held-out estimator of excess complexity (Appendix § 13 .§ 1 ).
Example 2 (Running example, continued). Recall from § 2 that in Example 1, H ( X ) = 19 H(X)=19 H ( X ) = 19 bits, H ( b ∗ ( X ) ) = 1 H(b^*(X))=1 H ( b ∗ ( X )) = 1 bit and H ( η ( X ) ) = 2 H(\eta(X))=2 H ( η ( X )) = 2 bits. So under 0-1 loss the minimal sufficient complexity is C 01 ∗ = 1 C^*_{01}=1 C 01 ∗ = 1 bit and the G-LMC is b ∗ ( X ) = 1 { Z ≥ 4 } b^*(X)=1\{Z\geq4\} b ∗ ( X ) = 1 { Z ≥ 4 } ; under log-loss, C log ∗ = 2 C^*_{\log}=2 C l o g ∗ = 2 bits and the G-LMC is η ( X ) \eta(X) η ( X ) , which records the half and the parity of Z Z Z . A model whose output is the whole input, F = X F=X F = X , is sufficient for both losses, and its excess complexity is 19 − 1 = 18 19-1=18 19 − 1 = 18 bits under 0-1 loss: everything it records about U U U and about Z Z Z beyond its half is unnecessary. A model that outputs Z Z Z has excess complexity 3 − 1 = 2 3-1=2 3 − 1 = 2 bits under 0-1 loss and 3 − 2 = 1 3-2=1 3 − 2 = 1 bit under log-loss.
Connection to rate–distortion and the information bottleneck
The minimal sufficient complexity is one point on a trade-off curve. If we allow some deficiency, we can compress further. The indirect rate–distortion function [22 , 71 ] gives the least complexity compatible with a given risk:
R ℓ ( D ) = inf { I ( T ; X ) : Y − X − T , R ℓ ( T ) ≤ D } . (1) R_{\ell}(D)=\inf\{I(T;X):Y-X-T,\ R_{\ell}(T)\leq D\}. \tag*{(1)} R ℓ ( D ) = inf { I ( T ; X ) : Y − X − T , R ℓ ( T ) ≤ D } . (1)
It is “indirect” because the representation is computed from X X X but judged on Y Y Y , which is only observed through X X X . Theorem 2 says that at zero deficiency, R ℓ ( C ℓ ∗ ) = C ℓ ∗ R_{\ell}(C^*_{\ell})=C^*_{\ell} R ℓ ( C ℓ ∗ ) = C ℓ ∗ , attained by T = a ∗ ( X ) T=a^*(X) T = a ∗ ( X ) . The excess complexity of Definition 2 is the distance of a model above this curve, which in source-coding terms is its redundancy .
Under log-loss, R log ( T ) = H ( Y ∣ T ) = H ( Y ) − I ( T ; Y ) R_{\log}(T)=H(Y\mid T)=H(Y)-I(T;Y) R l o g ( T ) = H ( Y ∣ T ) = H ( Y ) − I ( T ; Y ) , so the constraint R log ( T ) ≤ D R_{\log}(T)\leq D R l o g ( T ) ≤ D is a constraint I ( T ; Y ) ≥ H ( Y ) − D I(T;Y)\geq H(Y)-D I ( T ; Y ) ≥ H ( Y ) − D , and (1) becomes the information bottleneck curve [69 ] . The minimal sufficient complexity C log ∗ = H ( η ( X ) ) C^*_{\log}=H(\eta(X)) C l o g ∗ = H ( η ( X )) is therefore the full-relevance end point of the IB curve, and the G-LMC under log-loss is the minimal sufficient statistic η ( X ) \eta(X) η ( X ) . (With past and future of a process in place of X X X and Y Y Y , C log ∗ C^*_{\log} C l o g ∗ is also the statistical complexity of computational mechanics; [19 ] . ) For other losses, (1) is a loss-specific bottleneck. The 0-1 version is the relevant one for classification: in Example 1 it ends at 1 bit, not 2, because a classifier does not need to know the noise level.
The original LMC and why we work at the population level
We can now say precisely what was wrong with the original definition, and why its generalization above avoids the problem. The LMC papers called a deterministic output F = f ( X ) F=f(X) F = f ( X ) a lossless maximal compression if I ( F ; X ) = I ( F ; Y ) = I ( X ; Y ) I(F;X)=I(F;Y)=I(X;Y) I ( F ; X ) = I ( F ; Y ) = I ( X ; Y ) [55 Def. 4 and Prop. 1] . In words: the output keeps all the information that X X X has about Y Y Y , and retains nothing else about X X X . When the labels are noiseless this is the same as being a G-LMC under log-loss. When they are noisy it is not, and the requirement can almost never be met.
Proposition 4 (The original LMC rarely exists). A deterministic F F F with I ( F ; X ) = I ( F ; Y ) = I ( X ; Y ) I(F;X)=I(F;Y)=I(X;Y) I ( F ; X ) = I ( F ; Y ) = I ( X ; Y ) exists if and only if the Gács–Körner common information of X X X and Y Y Y , [27 ] , equals I ( X ; Y ) I(X;Y) I ( X ; Y ) . For binary labels, this holds if and only if H ( Y ∣ X ) = 0 H(Y\mid X)=0 H ( Y ∣ X ) = 0 or I ( X ; Y ) = 0 I(X;Y)=0 I ( X ; Y ) = 0 .
So for binary classification with informative features, the original LMC exists only if there is no label noise at all. In Example 1 with ε > 0 \varepsilon>0 ε > 0 , no LMC exists, while the G-LMC always exists (it is b ∗ ( X ) b^*(X) b ∗ ( X ) under 0-1 loss). The reason is that requiring I ( F ; X ) = I ( F ; Y ) I(F;X)=I(F;Y) I ( F ; X ) = I ( F ; Y ) forces H ( F ∣ Y ) = 0 H(F\mid Y)=0 H ( F ∣ Y ) = 0 , so F F F would have to be a function of the noisy label as well as of the input.
There is a second, empirical, problem. On a training sample with distinct inputs, the empirical label noise is zero: each input appears once, with one label. Any classifier that interpolates the sample then satisfies the empirical version of the LMC equations exactly (Appendix § 13 .§ 2 ). This is why, in Table 1 , all five interpolators have the same legacy score of 0.99, despite their very different test behaviour. The lesson is that information quantities computed on the training sample cannot distinguish interpolators. For this reason every quantity in the rest of this paper is defined either at the population level, as in this section, or through the learner’s behaviour over independent training samples, as in the next. Appendix § 18 lists the claims of the earlier papers that this affects and those that survive.
What a learner stores and what it expresses
In the last section we described the ideal model: an output that carries the minimal sufficient complexity C ℓ ∗ = H ( a ∗ ( X ) ) C_{\ell}^{*} = H(a^{*}(X)) C ℓ ∗ = H ( a ∗ ( X )) and no excess. We will now bring learning into the picture. A learner sees a finite noisy sample, and an interpolating learner reproduces every noisy label in it. We ask two questions. How much information about the training labels must such a learner keep (§ 4.2 )? And how much of it reaches its predictions on new inputs (§ 4.3 )? We will see that the first quantity is the same for every interpolator, while the second controls excess risk.
Recall from § 2 that W = A ( S , ξ ) W = A(S,\xi) W = A ( S , ξ ) is the trained model, which is random through both the sample S S S and the seed ξ \xi ξ , and that h W h_{W} h W is the classifier it induces. Let ϵ ^ = 1 n ∑ i 1 { h W ( X i ) ≠ Y i } \hat{\epsilon} = \frac{1}{n}\sum_{i}1\{h_{W}(X_{i}) \ne Y_{i}\} ϵ ^ = n 1 ∑ i 1 { h W ( X i ) = Y i } be its training error and ϵ ˉ = E ϵ ^ \bar{\epsilon} = \mathbb{E}\hat{\epsilon} ϵ ˉ = E ϵ ^ the expected training error. Let ϕ K ( e ) = h ( e ) + e log 2 ( K − 1 ) \phi_{K}(e) = h(e) + e\log_{2}(K - 1) ϕ K ( e ) = h ( e ) + e log 2 ( K − 1 ) , the function that appears in Fano’s inequality.
Storing and expressing, in plain terms
Before the formal definitions, let us explain the two words informally. Both describe what an interpolating learner does with the noisy labels it was trained on. Storing a label means that the trained model keeps it. Expressing it means that the label still affects the model’s predictions at new inputs . Both terms, in this sense, are introduced in this paper (Table 2 ).
Storage: what the model keeps from its training labels. Suppose we could look inside the trained model and reconstruct, from it and the training inputs, which training points were labelled 1 and which 0, including the mislabelled ones. Then the model has stored those labels. An interpolator reproduces every training label, wrong ones included, so all of them can be read back off. Theorem 5 makes this exact: every interpolator stores n H ( Y ∣ X ) n H(Y \mid X) n H ( Y ∣ X ) bits, all of the label noise in its sample. In the running example (Example 1) with n = 4096 n = 4096 n = 4096 , this is about 2,437 bits, the same for every learner in Table 1 . So storage cannot tell a good interpolator from a bad one, and neither can generalization bounds built on the information in the weights.
Expression: what reaches predictions at new inputs. Now fix one new input x x x and imagine retraining the learner many times, each time on a fresh sample, recording its prediction at x x x . If the prediction is always the same, the particular sample, noisy labels included, made no difference at x x x : nothing was expressed there. If the prediction changes with the sample, the prediction at x x x carries information about which noisy labels the learner happened to see. Expressed information V ( x ) V(x) V ( x ) (Definition 3) measures exactly this.
Why the distinction matters. A learner can store everything and express almost nothing. The memorize-and-smooth learner of Proposition 16 returns the memorized label on a training input, but on a new input it predicts the majority label among training points with the same informative feature, which individual noisy labels barely move. Since new inputs almost never coincide with training inputs, the memorized labels are almost never used: in Table 1 it expresses 0.007 bits and has excess risk 0.001. The 1-NN rule stores exactly as much, but predicts with the label of the nearest training point, so each prediction is effectively a fresh noisy label; it expresses all the noise it stores (V → H ( Y ∣ X ) = 0.595 V \to H(Y \mid X) = 0.595 V → H ( Y ∣ X ) = 0.595 bits; Proposition 17 ) and its excess risk stays near 0.12. Excess risk is controlled by expression, not by storage (Theorem 9 ). Benign overfitting means that the noise is stored but not expressed.
An analogy. Consider students who memorize an answer key that contains some typos. Storage is how much of the key, typos included, is in a student’s memory; every student who can recite the key perfectly stores the same amount. Expression is whether those typos appear when the student answers new questions. One student has memorized the key but answers new questions from an understanding of the topic, so the typos never surface (benign). Another answers each new question by recalling the closest memorized entry and copying it, typo and all (tempered). Grading the students on the memorized questions cannot separate them, since both answer all of them “correctly”. The difference appears only on new questions, and that is what V V V measures, without needing the correct answers to those questions.
Storage: interpolators memorize all of the label noise
Theorem 5 (Storage of label noise; cf. Harutyunyan et al., [31 ] Thm. 2.1). For every learner,
I ( W ; Y n ∣ X n ) ≥ n [ H ( Y ∣ X ) − ϕ K ( ε ˉ ) ] . I(W;Y^n \mid X^n) \ge n[H(Y \mid X)-\phi_K(\bar{\varepsilon})]. I ( W ; Y n ∣ X n ) ≥ n [ H ( Y ∣ X ) − ϕ K ( ε ˉ )] . If the learner interpolates, then I ( W ; Y n ∣ X n ) = n H ( Y ∣ X ) I(W;Y^n \mid X^n) = n H(Y \mid X) I ( W ; Y n ∣ X n ) = n H ( Y ∣ X ) exactly, and so I ( W ; S ) ≥ n H ( Y ∣ X ) I(W;S) \ge n H(Y \mid X) I ( W ; S ) ≥ n H ( Y ∣ X ) .
The quantity I ( W ; Y n ∣ X n ) I(W;Y^n \mid X^n) I ( W ; Y n ∣ X n ) is the information that the trained model holds about the training labels beyond what the training inputs already say about them. It is the natural measure of how much the model has memorized . The theorem says that a model that fits its labels well must have memorized almost all of their noise, and that an interpolator has memorized exactly all of it: H ( Y ∣ X ) H(Y \mid X) H ( Y ∣ X ) bits per example. In the running example (Example 1) with n = 4096 n = 4096 n = 4096 , every interpolator in Table 1 stores exactly 4096 × 0.595 ≈ 2437 4096 \times0.595 \approx2437 4096 × 0.595 ≈ 2437 bits of label noise, regardless of how well it predicts. The inequality is a rearrangement of Theorem 2.1 of Harutyunyan et al. [31 ] , who use it to bound the expected number of training errors. What we add is the exact equality for interpolators and the consequence below; Appendix § 14 also splits the stored information into a task part and a noise part.
An immediate consequence concerns information-theoretic generalization bounds. These bound the expected generalization gap by I ( W ; S ) I(W;S) I ( W ; S ) ; for example, for a σ \sigma σ -sub-Gaussian loss, ∣ E g a p ∣ ≤ 2 σ 2 I ( W ; S ) / n |\mathbb{E}\,\mathrm{gap}| \le\sqrt{2\sigma^2 I(W;S)/n} ∣ E gap ∣ ≤ 2 σ 2 I ( W ; S ) / n (Xu and Raginsky, [73 ] ).
Corollary 6 (Mutual-information bounds cannot separate interpolators). For every interpolator and every n n n , the bound of Xu and Raginsky [73 ] is at least 2 σ 2 H ( Y ∣ X ) \sqrt{2\sigma^2 H(Y \mid X)} 2 σ 2 H ( Y ∣ X ) (with H H H in nats). It therefore does not vanish, and it cannot distinguish a benign interpolator from a tempered one.
In plain terms: both a benign and a tempered interpolator have a generalization gap that tends to the Bayes risk (their training error is zero and their test error tends to R ∗ R^* R ∗ or above), and the bound is equally loose for both. What separates them is their excess risk , which the bound does not see. This is not a defect of one particular bound; it is a consequence of storage being pinned at n H ( Y ∣ X ) nH(Y \mid X) n H ( Y ∣ X ) (see also [46 , 30 ] . To separate interpolators, we need a quantity that looks at the predictions, not at the weights.
Conditional mutual information. Steinke and Zakynthinou [65 ] proposed a refinement that avoids some of the problems of I ( W ; S ) I(W;S) I ( W ; S ) . Draw a supersample Z ~ ∈ ( X × Y ) n × 2 \widetilde{Z} \in(\mathcal{X} \times\mathcal{Y})^{n \times2} Z ∈ ( X × Y ) n × 2 of 2 n 2n 2 n i.i.d. examples arranged in n n n pairs, and a uniformly random selector U ∈ { 0 , 1 } n U \in\{0,1\}^{n} U ∈ { 0 , 1 } n that picks one example from each pair to form the training sample S = Z ~ U S = \widetilde{Z}_{U} S = Z U . The conditional mutual information of the learner is C M I = I ( W ; U ∣ Z ~ ) \mathrm{CMI} = I(W;U \mid\widetilde{Z}) CMI = I ( W ; U ∣ Z ) : how much the trained model reveals about which example of each pair it was trained on. Unlike I ( W ; S ) I(W;S) I ( W ; S ) , it is always finite, C M I ≤ n ln 2 \mathrm{CMI} \le n \ln2 CMI ≤ n ln 2 , and for losses in [ 0 , 1 ] [0,1] [ 0 , 1 ] it gives ∣ E g a p ∣ ≤ 2 C M I / n |\mathbb{E}\,\mathrm{gap}| \le\sqrt{2\,\mathrm{CMI}/n} ∣ E gap ∣ ≤ 2 CMI / n [65 Thm. 2] . Its behaviour on interpolators is nevertheless the same in kind.
Corollary 7 (CMI cannot separate interpolators either). For every interpolator, C M I ≥ n 2 ( E R ( h W ) ) 2 ≥ n 2 ( R ∗ ) 2 \mathrm{CMI} \ge\frac{n}{2}\bigl(\mathrm{ER}(h_W)\bigr)^2 \ge\frac{n}{2}(R^*)^2 CMI ≥ 2 n ( ER ( h W ) ) 2 ≥ 2 n ( R ∗ ) 2 (in nats). So the CMI of a benign interpolator grows linearly in n n n , like that of a tempered one, and the CMI bound on the gap is at least R ∗ R^* R ∗ for both.
In plain terms, the CMI framework conditions away the randomness of the data and keeps only the randomness of the selection, which makes it finite and often much tighter. But it still bounds the generalization gap , and for an interpolator the gap is its whole test error, which is at least the Bayes risk. In the running example with ε = 0.2 \varepsilon= 0.2 ε = 0.2 , every interpolator has C M I ≥ 0.011 n \mathrm{CMI} \ge0.011\,n CMI ≥ 0.011 n nats. We will see in § 4.3 that the CMI construction is still useful: applied to predictions at fresh inputs rather than to the weights, it gives one of the components of expressed information (Proposition 8 ).
Expression: the information that reaches predictions
Let us now introduce the central quantity of the paper. Fix an input x x x , and imagine retraining the learner many times on fresh samples (and with fresh seeds). Each time we record the prediction h W ( x ) h_W(x) h W ( x ) . Let q ( ⋅ ∣ x ) q(\cdot\mid x) q ( ⋅ ∣ x ) be the distribution of these predictions over [ K ] [K] [ K ] :
q ( k ∣ x ) = P S , ξ ( h W ( x ) = k ) . q(k \mid x) = \mathbb{P}_{S,\xi}\bigl(h_W(x) = k\bigr). q ( k ∣ x ) = P S , ξ ( h W ( x ) = k ) .
Definition 3 (Expressed information). The expressed information of a learner at x x x is the entropy of its prediction distribution,
V ( x ) = H ( q ( ⋅ ∣ x ) ) = I ( h W ( x ) ; S , ξ ) . V(x) = H\bigl(q(\cdot\mid x)\bigr) = I\bigl(h_W(x); S,\xi\bigr). V ( x ) = H ( q ( ⋅ ∣ x ) ) = I ( h W ( x ) ; S , ξ ) . Its average over a fresh test input X ′ ∼ P X X' \sim P_X X ′ ∼ P X , independent of the sample, is E V ( X ′ ) = I ( h W ( X ′ ) ; S , ξ ∣ X ′ ) \mathbb{E}\,V(X') = I\bigl(h_W(X'); S,\xi\mid X'\bigr) E V ( X ′ ) = I ( h W ( X ′ ) ; S , ξ ∣ X ′ ) . The modal prediction m ( x ) = arg max k q ( k ∣ x ) m(x) = \arg\max_k q(k \mid x) m ( x ) = arg max k q ( k ∣ x ) is the most frequent prediction at x x x .
The two expressions for V ( x ) V(x) V ( x ) are equal because h W ( x ) h_W(x) h W ( x ) is a function of ( S , ξ ) (S,\xi) ( S , ξ ) . Let us explain both readings in plain terms.
As an entropy , V ( x ) V(x) V ( x ) measures how unpredictable the prediction at x x x is before we know which sample the learner will be trained on. It is 0 0 0 if every sample leads to the same prediction, and it is at most log 2 K \log_2 K log 2 K bits.
As a mutual information , V ( x ) V(x) V ( x ) measures how much the prediction at x x x reveals about the particular training sample (and seed). If the learner has memorized a noisy label near x x x , its prediction at x x x will reveal that label, and V ( x ) V(x) V ( x ) will be large. If it has smoothed the label away, the prediction will not depend on it, and V ( x ) V(x) V ( x ) will be small.
So V V V measures the part of what was stored that is expressed at test time.
Expressed information can also be read in the supersample construction of Steinke and Zakynthinou [65 ] described in § 4.2 .
Proposition 8 (Expressed information in the supersample construction). Let S = Z ~ U S = \widetilde{Z}_{U} S = Z U as in § 4.2 , with ξ \xi ξ independent of ( Z ~ , U ) (\widetilde{Z}, U) ( Z , U ) . For every x x x ,
V ( x ) = I ( h W ( x ) ; Z ~ ) ⏟ which pool + I ( h W ( x ) ; U ∣ Z ~ ) ⏟ which half of the pool + I ( h W ( x ) ; ξ ∣ Z ~ , U ) ⏟ which seed . V(x) = \underbrace{I(h_W(x); \widetilde{Z})}_{\textit{which pool}} + \underbrace{I(h_W(x); U \mid\widetilde{Z})}_{\textit{which half of the pool}} + \underbrace{I(h_W(x); \xi\mid\widetilde{Z}, U)}_{\textit{which seed}}. V ( x ) = which pool I ( h W ( x ) ; Z ) + which half of the pool I ( h W ( x ) ; U ∣ Z ) + which seed I ( h W ( x ) ; ξ ∣ Z , U ) .
So the CMI-style quantity at a fresh input, I ( h W ( x ) ; U ∣ Z ~ ) I(h_W(x); U \mid\widetilde{Z}) I ( h W ( x ) ; U ∣ Z ) , is the part of the expressed information that reflects which half of a fixed pool of data the learner saw, and it is at most V ( x ) V(x) V ( x ) . It is the prediction-level, fresh-input counterpart of CMI = I ( W ; U ∣ Z ~ ) = I(W; U \mid\widetilde{Z}) = I ( W ; U ∣ Z ) : where CMI asks how much the weights reveal about the selection, this term asks how much a prediction at a new input reveals about it. Our estimator from two disjoint halves (§ 6.3 ) is exactly this construction for one draw of U U U : one copy is trained on Z ~ U \widetilde{Z}_{U} Z U and the other on Z ~ 1 − U \widetilde{Z}_{1-U} Z 1 − U , and their disagreement on fresh inputs is observed. The proof is in Appendix § 15 .
The modal prediction m ( x ) m(x) m ( x ) is what the learner predicts “on average”; it is the prediction of an infinitely large bagged ensemble of independently trained copies of the learner. Expressed information is the hard-prediction, Shannon-entropy counterpart of the 0-1 “variance” of Kohavi and Wolpert [42 ] and Domingos [23 ] ; we discuss the relation in § 8 .
The next theorem is the main result of this section. It says that excess risk is governed by two things: how much a learner expresses (V V V ), and whether its modal prediction is right. Let Δ ( x ) = η b ∗ ( x ) ( x ) − min k η k ( x ) \Delta(x) = \eta_{b^*(x)}(x) - \min_k \eta_k(x) Δ ( x ) = η b ∗ ( x ) ( x ) − min k η k ( x ) and γ ( x ) = η b ∗ ( x ) ( x ) − max k ≠ b ∗ ( x ) η k ( x ) \gamma(x) = \eta_{b^*(x)}(x) - \max_{k \ne b^*(x)} \eta_k(x) γ ( x ) = η b ∗ ( x ) ( x ) − max k = b ∗ ( x ) η k ( x ) be the largest and smallest gaps between the probability of the Bayes class and that of another class. For binary labels both are ∣ 2 η 1 ( x ) − 1 ∣ \lvert2\eta_1(x) - 1\rvert ∣ 2 η 1 ( x ) − 1 ∣ , the margin of the problem at x x x .4
Theorem 9 (Information decomposition of excess risk). For every learner,
E R ( h W ) − R ∗ ≤ 1 2 E [ Δ ( X ) V ( X ) ] + E [ Δ ( X ) 1 { m ( X ) ≠ b ∗ ( X ) } ] , \mathbb{E}\,R(h_W) - R^* \le\frac{1}{2}\mathbb{E}\left[\Delta(X)V(X)\right] + \mathbb{E}\left[\Delta(X)\mathbf{1}\{m(X) \ne b^*(X)\}\right], E R ( h W ) − R ∗ ≤ 2 1 E [ Δ ( X ) V ( X ) ] + E [ Δ ( X ) 1 { m ( X ) = b ∗ ( X )} ] , E R ( h W ) − R ∗ ≥ E [ γ ( X ) ϕ K − 1 ( V ( X ) ) 1 { m ( X ) = b ∗ ( X ) } ] + 1 2 E [ γ ( X ) 1 { m ( X ) ≠ b ∗ ( X ) } ] . \mathbb{E}\,R(h_W) - R^* \ge\mathbb{E}\left[\gamma(X)\phi_K^{-1}(V(X))\mathbf{1}\{m(X) = b^*(X)\}\right] + \frac{1}{2}\mathbb{E}\left[\gamma(X)\mathbf{1}\{m(X) \ne b^*(X)\}\right]. E R ( h W ) − R ∗ ≥ E [ γ ( X ) ϕ K − 1 ( V ( X )) 1 { m ( X ) = b ∗ ( X )} ] + 2 1 E [ γ ( X ) 1 { m ( X ) = b ∗ ( X )} ] . where ϕ K − 1 \phi_K^{-1} ϕ K − 1 is the inverse of ϕ K \phi_K ϕ K on [ 0 , 1 − 1 / K ] [0, 1 - 1/K] [ 0 , 1 − 1/ K ] . For binary labels the decomposition is exact: with π ( x ) = h − 1 ( V ( x ) ) ∈ [ 0 , 1 2 ] \pi(x) = h^{-1}(V(x)) \in[0, \frac{1}{2}] π ( x ) = h − 1 ( V ( x )) ∈ [ 0 , 2 1 ] ,
E R ( h W ) − R ∗ = E [ ∣ 2 η 1 ( X ) − 1 ∣ ( π ( X ) 1 { m ( X ) = b ∗ ( X ) } + ( 1 − π ( X ) ) 1 { m ( X ) ≠ b ∗ ( X ) } ) ] . (2) \mathbb{E}\,R(h_W) - R^* = \mathbb{E}\left[\lvert2\eta_1(X) - 1\rvert\left(\pi(X)\mathbf{1}\{m(X) = b^*(X)\} + (1-\pi(X))\mathbf{1}\{m(X) \ne b^*(X)\}\right)\right]. \tag*{(2)} E R ( h W ) − R ∗ = E [ ∣ 2 η 1 ( X ) − 1 ∣ ( π ( X ) 1 { m ( X ) = b ∗ ( X )} + ( 1 − π ( X )) 1 { m ( X ) = b ∗ ( X )} ) ] . (2)
The proof (Appendix § 15 ) combines the exact identity E R ( h W ) − R ∗ = E [ ∑ k q ( k ∣ X ) ( η b ∗ ( X ) − η k ( X ) ) ] \mathbb{E}R(h_W)-R^* = \mathbb{E}[\sum_k q(k \mid X)(\eta_{b^*(X)}-\eta_k(X))] E R ( h W ) − R ∗ = E [ ∑ k q ( k ∣ X ) ( η b ∗ ( X ) − η k ( X ))] with a two-sided bound on the probability mass of the mode in terms of entropy (Lemma S4; cf. Feder and Merhav [24 ] ). In plain terms, the theorem says that a learner can lose accuracy in two ways.
Through expression. At inputs where its modal prediction is correct, a learner errs only when it departs from its mode, which it does with a probability controlled by V ( x ) V(x) V ( x ) from above and below. In the binary case, π ( x ) = h − 1 ( V ( x ) ) \pi(x)=h^{-1}(V(x)) π ( x ) = h − 1 ( V ( x )) is exactly the probability of departing from the mode.
Each loss is weighted by the margin of the problem at x x x : errors cost little where the classes are nearly balanced.
Corollary 10 (Consistency means vanishing expression and vanishing modal bias). Let ( A n ) (A_n) ( A n ) be a sequence of learners and assume γ ( X ) > 0 \gamma(X)>0 γ ( X ) > 0 almost surely. Then ER ( h W n ) → R ∗ \operatorname{ER}(h_{W_n})\to R^* ER ( h W n ) → R ∗ if and only if E V n ( X ′ ) → 0 \mathbb{E}V_n(X')\to0 E V n ( X ′ ) → 0 and P ( m n ( X ) ≠ b ∗ ( X ) ) → 0 \mathbb{P}(m_n(X)\ne b^*(X))\to0 P ( m n ( X ) = b ∗ ( X )) → 0 .
Output entropy splits into complexity and expression
We now connect expression back to the complexities of § 3 . There, a model was a fixed function. A learner’s output at a fresh input, F = h W ( X ′ ) F=h_W(X') F = h W ( X ′ ) , is a random function of X ′ X' X ′ : it depends on X ′ X' X ′ , and also on the sample and the seed. Since ( S , ξ ) (S,\xi) ( S , ξ ) is independent of the test pair, F F F is a stochastic representation of X ′ X' X ′ in the sense of § 3.1 .
Proposition 11 (Complexity plus expression). For F = h W ( X ′ ) F=h_W(X') F = h W ( X ′ ) ,
H ( F ) = I ( F ; X ′ ) + E V ( X ′ ) . H(F)=I(F;X')+\mathbb{E}V(X'). H ( F ) = I ( F ; X ′ ) + E V ( X ′ ) .
Proof. H ( F ) = I ( F ; X ′ ) + H ( F ∣ X ′ ) H(F)=I(F;X')+H(F\mid X') H ( F ) = I ( F ; X ′ ) + H ( F ∣ X ′ ) , and H ( F ∣ X ′ = x ) = H ( q ( ⋅ ∣ x ) ) = V ( x ) H(F\mid X'=x)=H(q(\cdot\mid x))=V(x) H ( F ∣ X ′ = x ) = H ( q ( ⋅ ∣ x )) = V ( x ) .
So the total entropy of a learner’s predictions on new inputs has two parts. The first, I ( F ; X ′ ) I(F;X') I ( F ; X ′ ) , is complexity : variation of the prediction that is explained by the input, as in § 3 . The second, E V \mathbb{E}V E V , is expression : variation that is explained only by the training sample. The ideal output, the G-LMC b ∗ ( X ′ ) b^*(X') b ∗ ( X ′ ) , has complexity C 01 ∗ = H ( b ∗ ( X ′ ) ) C^*_{01}=H(b^*(X')) C 01 ∗ = H ( b ∗ ( X ′ )) and no expression. The next result says that a consistent learner approaches exactly this.
Corollary 12 (Consistent learners converge to the G-LMC). Under the assumption of Corollary 10, if ER ( h W n ) → R ∗ \operatorname{ER}(h_{W_n})\to R^* ER ( h W n ) → R ∗ then P ( h W n ( X ′ ) ≠ b ∗ ( X ′ ) ) → 0 \mathbb{P}(h_{W_n}(X')\ne b^*(X'))\to0 P ( h W n ( X ′ ) = b ∗ ( X ′ )) → 0 , and
H ( h W n ( X ′ ) ) → C 01 ∗ , I ( h W n ( X ′ ) ; X ′ ) → C 01 ∗ , E V n ( X ′ ) → 0. H(h_{W_n}(X'))\to C^*_{01},\qquad I(h_{W_n}(X');X')\to C^*_{01},\qquad\mathbb{E}V_n(X')\to0. H ( h W n ( X ′ )) → C 01 ∗ , I ( h W n ( X ′ ) ; X ′ ) → C 01 ∗ , E V n ( X ′ ) → 0.
In particular, the excess complexity of the learner’s output over the minimal sufficient complexity vanishes, even if the learner interpolates and stores n H ( Y ∣ X ) nH(Y\mid X) n H ( Y ∣ X ) bits of label noise.
This corollary gives the picture of benign overfitting that we develop in the next section. Storage is pinned at its maximum: an interpolator memorizes all the label noise in its sample (Theorem 5 ). But the learner’s predictions on new inputs can still converge to the minimal sufficient representation. Benign overfitting means that what is stored is not expressed.
Example 3 (Running example, continued). In Example 1, H ( Y ) = 1 H(Y)=1 H ( Y ) = 1 bit. § 5.3 shows that, as n → ∞ n\to\infty n → ∞ , the prediction of the 1-nearest-neighbour rule at a fresh input behaves like a fresh noisy label: E V → H ( Y ∣ X ) = 0.595 \mathbb{E}V\to H(Y\mid X)=0.595 E V → H ( Y ∣ X ) = 0.595 bits and I ( F ; X ′ ) → I ( X ; Y ) = 0.405 I(F;X')\to I(X;Y)=0.405 I ( F ; X ′ ) → I ( X ; Y ) = 0.405 bits, which add up to H ( F ) = 1 H(F)=1 H ( F ) = 1 bit. A benign interpolator, such as the memorize-and-smooth rule of Proposition 16 , instead has E V → 0 \mathbb{E}V\to0 E V → 0 and I ( F ; X ′ ) → 1 I(F;X')\to1 I ( F ; X ′ ) → 1 bit, the minimal sufficient complexity. Both store the same 0.595 bits per training example. In Table 1 , at n = 4096 n=4096 n = 4096 , the 1-NN rule expresses 0.642 bits and the memorize-and-smooth rule 0.007 bits.
Beyond classification error
The decomposition of Theorem 9 is for 0-1 loss, but the idea carries over to other losses. We briefly state the squared-loss version, which links expressed information to the classical variance. Let Y ∈ R Y \in\mathbb{R} Y ∈ R , let f W ( x ) f_W(x) f W ( x ) be the learner’s real-valued prediction, and let v ( x ) v(x) v ( x ) and f ˉ ( x ) \bar{f}(x) f ˉ ( x ) be its variance and mean over ( S , ξ ) (S,\xi) ( S , ξ ) . A continuous prediction carries infinite information, so we add a small amount of independent Gaussian noise before measuring it: let V σ ( x ) = I ( f W ( x ) + σ Z ; S , ξ ) V_\sigma(x) = I(f_W(x) + \sigma Z; S,\xi) V σ ( x ) = I ( f W ( x ) + σ Z ; S , ξ ) with Z ∼ N ( 0 , 1 ) Z \sim N(0,1) Z ∼ N ( 0 , 1 ) , in nats.
Theorem 13 (Variance is low-resolution expressed information). For every x x x , V σ ( x ) ≤ 1 2 log ( 1 + v ( x ) / σ 2 ) V_\sigma(x) \le\frac{1}{2}\log(1 + v(x)/\sigma^2) V σ ( x ) ≤ 2 1 log ( 1 + v ( x ) / σ 2 ) and lim σ → ∞ 2 σ 2 V σ ( x ) = v ( x ) \lim_{\sigma\to\infty} 2\sigma^2 V_\sigma(x) = v(x) lim σ → ∞ 2 σ 2 V σ ( x ) = v ( x ) . Consequently
E R ( f W ) − R ∗ = E ( f ˉ ( X ) − E [ Y ∣ X ] ) 2 + lim σ → ∞ 2 σ 2 E V σ ( X ) . \mathbb{E}R(f_W) - R^* = \mathbb{E}\left(\bar{f}(X) - \mathbb{E}[Y \mid X]\right)^2 + \lim_{\sigma\to\infty} 2\sigma^2 \mathbb{E}V_\sigma(X). E R ( f W ) − R ∗ = E ( f ˉ ( X ) − E [ Y ∣ X ] ) 2 + σ → ∞ lim 2 σ 2 E V σ ( X ) .
So under squared loss, the familiar variance term is expressed information, measured at low resolution; the proof uses the I-MMSE relation of Guo et al. [29 ] . For log-loss with probabilistic outputs, the analogous result is the bias–variance decomposition of Heskes [35 ] , whose variance term is again an expressed-information quantity (Appendix § 15 .§ 1 ). Appendix § 23 works out the regression case further: every exact interpolator of real-valued labels stores infinitely much information about them (and n [ h ( Y ∣ X ) + log ( 1 / Δ ) ] n[h(Y \mid X) + \log(1/\Delta)] n [ h ( Y ∣ X ) + log ( 1/Δ )] bits at resolution Δ \Delta Δ ), and the label-free rule “least variance between two half-sample fits” selects well when the candidates have similar bias, but not otherwise, because interpolation does not keep bias small in regression.
Relation to bias–variance decompositions and to disagreement
Expressed information is not the first quantity to measure how much a learner’s predictions vary across training samples. Bias–variance decompositions for 0-1 loss ([42 , 23 , 38 ] ) and, more recently, the disagreement between independently trained models ([39 , 52 , 6 ] ) do the same. In this subsection we make the relations exact. We will see that these quantities are all functions of the same prediction distribution q ( ⋅ ∣ x ) q(\cdot\mid x) q ( ⋅ ∣ x ) as V V V , that they are equivalent to V V V up to explicit monotone bounds, and that Theorem 9 tells us what each of them measures.
Let us first recall the classical quantities, all computed at a fixed input x x x from the prediction distribution q = q ( ⋅ ∣ x ) q = q(\cdot\mid x) q = q ( ⋅ ∣ x ) and the modal prediction m = m ( x ) m = m(x) m = m ( x ) (Domingos’ “main prediction”).
Domingos’ variance is the probability of departing from the main prediction, π D ( x ) = 1 − q ( m ∣ x ) \pi_D(x) = 1 - q(m \mid x) π D ( x ) = 1 − q ( m ∣ x ) . His bias is B ( x ) = 1 { m ( x ) ≠ b ∗ ( x ) } B(x) = \mathbf{1}\{m(x) \ne b^*(x)\} B ( x ) = 1 { m ( x ) = b ∗ ( x )} , which we called modal bias.
Kohavi and Wolpert’s variance is the Gini impurity of the predictions, σ K W 2 ( x ) = 1 2 ( 1 − ∑ k q ( k ∣ x ) 2 ) \sigma^2_{\mathrm{KW}}(x) = \frac{1}{2}\left(1 - \sum_k q(k \mid x)^2\right) σ KW 2 ( x ) = 2 1 ( 1 − ∑ k q ( k ∣ x ) 2 ) .
The disagreement of two independently trained copies is Dis ( x ) = P ( h W 1 ( x ) ≠ h W 2 ( x ) ) = 1 − ∑ k q ( k ∣ x ) 2 = 2 σ K W 2 ( x ) \operatorname{Dis}(x) = \mathbb{P}(h_{W_1}(x) \ne h_{W_2}(x)) = 1 - \sum_k q(k \mid x)^2 = 2\sigma^2_{\mathrm{KW}}(x) Dis ( x ) = P ( h W 1 ( x ) = h W 2 ( x )) = 1 − ∑ k q ( k ∣ x ) 2 = 2 σ KW 2 ( x ) .
James’ variance effect is the increase in expected loss caused by departing from the main prediction, VE ( x ) = E [ 1 { h W ( x ) ≠ Y } ] − P ( m ( x ) ≠ Y ) \operatorname{VE}(x) = \mathbb{E}[\mathbf{1}\{h_W(x) \ne Y\}] - \mathbb{P}(m(x) \ne Y) VE ( x ) = E [ 1 { h W ( x ) = Y }] − P ( m ( x ) = Y ) , and his systematic effect is SE ( x ) = P ( m ( x ) ≠ Y ) − P ( b ∗ ( x ) ≠ Y ) \operatorname{SE}(x) = \mathbb{P}(m(x) \ne Y) - \mathbb{P}(b^*(x) \ne Y) SE ( x ) = P ( m ( x ) = Y ) − P ( b ∗ ( x ) = Y ) .
Note that the disagreement of two copies is exactly twice the Kohavi–Wolpert variance; this simple identity links the disagreement literature to the bias–variance literature.
Proposition 14 (A dictionary of variances). At every x x x ,
ϕ K − 1 ( V ( x ) ) ≤ π D ( x ) ≤ Dis ( x ) = 2 σ K W 2 ( x ) ≤ 2 π D ( x ) ≤ V ( x ) . \phi_K^{-1}(V(x)) \le\pi_D(x) \le\operatorname{Dis}(x) = 2\sigma_{KW}^{2}(x) \le2\pi_D(x) \le V(x). ϕ K − 1 ( V ( x )) ≤ π D ( x ) ≤ Dis ( x ) = 2 σ K W 2 ( x ) ≤ 2 π D ( x ) ≤ V ( x ) . For K = 2 K = 2 K = 2 the four quantities are increasing functions of one another: π D = h − 1 ( V ) \pi_D = h^{-1}(V) π D = h − 1 ( V ) and Dis = 2 π D ( 1 − π D ) \operatorname{Dis} = 2\pi_D(1-\pi_D) Dis = 2 π D ( 1 − π D ) . Moreover, ER ( h W ) − R ∗ = E [ SE ( X ) ] + E [ VE ( X ) ] \operatorname{ER}(h_W) - R^* = \mathbb{E}[\operatorname{SE}(X)] + \mathbb{E}[\operatorname{VE}(X)] ER ( h W ) − R ∗ = E [ SE ( X )] + E [ VE ( X )] , and for K = 2 K = 2 K = 2
SE ( x ) + VE ( x ) = ∣ 2 η 1 ( x ) − 1 ∣ ( B ( x ) + ( 1 − 2 B ( x ) ) π D ( x ) ) , \operatorname{SE}(x) + \operatorname{VE}(x) = |2\eta_1(x)-1|\left(B(x) + (1-2B(x))\pi_D(x)\right), SE ( x ) + VE ( x ) = ∣2 η 1 ( x ) − 1∣ ( B ( x ) + ( 1 − 2 B ( x )) π D ( x ) ) , which is the exact decomposition (2) .
In plain terms: all these “variances” measure the same thing, the spread of the prediction distribution, on different scales. What distinguishes V V V is that it is also a mutual information, I ( h W ( x ) ; S , ξ ) I(h_W(x); S,\xi) I ( h W ( x ) ; S , ξ ) . This is what links variance to storage (Theorem 5 ) and to the complexity of the output (Proposition 11), and what gives the matching upper and lower bounds of Theorem 9 for any number of classes. The last identity is Domingos’ observation that “unbiased” variance (B = 0 B = 0 B = 0 ) increases error, while “biased” variance (B = 1 B = 1 B = 1 ) decreases it, now weighted by the margin. Proposition 19 is its consequence for averaging.
What does disagreement measure? Jiang et al. [39 ] observed that the expected disagreement of two copies of a network, trained with different seeds, is close to its test error, and proved that this generalization disagreement equality (GDE) holds when the ensemble is class-wise calibrated. Theorem 9 explains when this happens and when it cannot.
Proposition 15 (Disagreement bounds excess risk from both sides, not risk). Let Dis = E Dis ( X ) \operatorname{Dis} = \mathbb{E}\operatorname{Dis}(X) Dis = E Dis ( X ) for copies trained on independent samples (and seeds).
(a) If q ( ⋅ ∣ x ) = η ( x ) q(\cdot\mid x) = \eta(x) q ( ⋅ ∣ x ) = η ( x ) for every x x x , i.e. the learner’s predictions are distributed like a fresh label, then ER ( h W ) = Dis \operatorname{ER}(h_W) = \operatorname{Dis} ER ( h W ) = Dis exactly.
(b) For K = 2 K = 2 K = 2 , if the modal predictions are correct (m = b ∗ m = b^* m = b ∗ a.s.), then
ER ( h W ) − R ∗ ≤ E π D ( X ) ≤ Dis ≤ 2 E π D ( X ) ≤ E V ( X ) , \operatorname{ER}(h_W)-R^* \le\mathbb{E}\pi_D(X) \le\operatorname{Dis} \le2\mathbb{E}\pi_D(X) \le\mathbb{E}V(X), ER ( h W ) − R ∗ ≤ E π D ( X ) ≤ Dis ≤ 2 E π D ( X ) ≤ E V ( X ) , and if moreover ∣ 2 η 1 − 1 ∣ ≥ γ 0 > 0 |2\eta_1-1| \ge\gamma_0 > 0 ∣2 η 1 − 1∣ ≥ γ 0 > 0 a.s., then ER ( h W ) − R ∗ ≥ γ 0 2 Dis \operatorname{ER}(h_W)-R^* \ge\frac{\gamma_0}{2}\operatorname{Dis} ER ( h W ) − R ∗ ≥ 2 γ 0 Dis .
(c) For the 1-NN rule, Dis → 2 E [ η 1 ( X ) ( 1 − η 1 ( X ) ) ] = lim ER ( h W ) \operatorname{Dis} \to2\mathbb{E}[\eta_1(X)(1-\eta_1(X))] = \lim\operatorname{ER}(h_W) Dis → 2 E [ η 1 ( X ) ( 1 − η 1 ( X ))] = lim ER ( h W ) : the GDE holds exactly in the limit. For any consistent sequence of learners, Dis → 0 \operatorname{Dis} \to0 Dis → 0 while ER ( h W ) → R ∗ \operatorname{ER}(h_W) \to R^* ER ( h W ) → R ∗ , so the GDE fails by exactly the Bayes risk.
Let us restate the proposition in plain terms. Disagreement, like V V V , measures excess risk (part b). It equals the total risk only when the learner’s predictions behave like samples of the label distribution (part a), which is the “distributional generalization” of interpolating classifiers described by Nakkiran and Bansal [52 ] . Tempered interpolators such as 1-NN behave this way (part c; Example 3), so for them the GDE holds. A benign interpolator under label noise does not: its predictions concentrate on b ∗ b^* b ∗ , its disagreement vanishes, and its test error stays at R ∗ > 0 R^* > 0 R ∗ > 0 . In the running example at $n = 4096 ({xref}Section 7.1, {xref}Table 3`), the disagreement of 1-NN is 0.30 against a test error of 0.27, while the random forest has disagreement 0.014 against a test error of 0.154.
Two further remarks connect to recent work. First, the randomness matters. V = I ( h W ( x ) ; S , ξ ) = I ( h W ( x ) ; S ) + I ( h W ( x ) ; ξ ∣ S ) V = I(h_W(x); S,\xi) = I(h_W(x); S) + I(h_W(x);\xi\mid S) V = I ( h W ( x ) ; S , ξ ) = I ( h W ( x ) ; S ) + I ( h W ( x ) ; ξ ∣ S ) splits into a sample part and a seed part, much as the fine-grained variance decomposition of Adlam and Pennington [2 ] splits variance into data, initialization and label-noise parts. The GDE of Jiang et al. [39 ] uses copies trained on the same data with different seeds, so it sees only the seed part. For a deterministic learner such as 1-NN that part is zero, even though the 1-NN rule expresses H ( Y ∣ X ) H(Y \mid X) H ( Y ∣ X ) bits through the sample. Second, agreement between classifiers is also used to estimate accuracy without labels (Platanios et al., [59 ] ) and to predict performance under distribution shift (Baek et al., [6 ] ). These methods typically rely on independence or calibration assumptions. The consensus criterion of § 6.4 uses agreement differently: it estimates each candidate’s modal bias by its disagreement with the consensus, with the explicit guarantee ∣ D j − β j ∣ ≤ δ |D_j-\beta_j| \le\delta ∣ D j − β j ∣ ≤ δ and no independence assumption (Appendix § 17 ).
Benign overfitting as vanishing expression
In the last section we saw that every interpolator stores all the label noise in its sample (Theorem 5 ), and that excess risk is controlled by expressed information and modal bias (Theorem 9 ). We will now use these two results to explain when interpolation is harmless. We first state the resulting taxonomy, and then work it out for the main mechanisms studied in the benign-overfitting literature: memorizing while smoothing, local averaging, ensembling, and minimum-norm interpolation. Proofs are in Appendix § 16 .
An information-theoretic taxonomy
Mallinar et al. [48 ] classify interpolating learners as benign, tempered or catastrophic according to their limiting excess risk. Combining Theorem 5 with Corollary 10 gives an information-theoretic reading of the same taxonomy. As n → ∞ n \to\infty n → ∞ , an interpolator always stores n H ( Y ∣ X ) n H(Y \mid X) n H ( Y ∣ X ) bits. It overfits
benignly if EV n → 0 \operatorname{EV}_n \to0 EV n → 0 and its modal bias vanishes: it stores all of the noise and expresses none of it;
temperedly if EV n → c \operatorname{EV}_n \to c EV n → c for some c ∈ ( 0 , log 2 K ] c \in(0,\log_2 K] c ∈ ( 0 , log 2 K ] while its modal bias vanishes: it expresses a fixed fraction of what it stores, and its excess risk tends to a constant set by c c c through Theorem 9 ;
catastrophically if its modal bias does not vanish: even its average prediction is wrong on a set of positive probability.
The important point is that the dividing line between benign and tempered overfitting is a property of predictions at fresh inputs, V V V , and not of the trained model’s memory, which is the same for both.
Memorizing without expressing
Our first example shows that the two extremes, maximal storage and minimal expression, can be attained at the same time. It is deliberately simple, and it is built for the running example.
Proposition 16 (A benign interpolator). Consider the setting of Example 1, with d d d irrelevant bits instead of 16 and η \eta η depending on Z Z Z only, with η 1 ( z ) ≠ 1 2 \eta_1(z) \ne\frac{1}{2} η 1 ( z ) = 2 1 . The memorize-and-smooth learner predicts the training label at x x x if x x x appears in the training sample, and otherwise predicts the majority training label among examples with the same Z Z Z . Let n → ∞ n \to\infty n → ∞ and d = d n d = d_n d = d n with n 2 2 − d n → 0 n^2 2^{-d_n} \to0 n 2 2 − d n → 0 . Then the learner interpolates with probability tending to one, it stores n ( H ( Y ∣ X ) − o ( 1 ) ) n(H(Y \mid X)-o(1)) n ( H ( Y ∣ X ) − o ( 1 )) bits of label noise, and EV n → 0 \operatorname{EV}_n \to0 EV n → 0 and ER → R ∗ \operatorname{ER} \to R^* ER → R ∗ .
In words, the learner memorizes every training label exactly, but because fresh inputs almost never coincide with training inputs, the memorized labels are almost never used for prediction. All predictions on new inputs come from a smoothed majority vote, which does not depend on individual noisy labels. In Table 1 this learner expresses 0.007 bits and has excess risk 0.001. The random forest behaves in a similar way: each tree memorizes, but the average over trees smooths the memorized labels away from the training points (V = 0.045 V = 0.045 V = 0.045 ).
Nearest neighbours: from tempered to benign
The k k k -nearest-neighbour (k k k -NN) rule is the classical example of a learner whose overfitting can be tuned. With k = 1 k = 1 k = 1 it interpolates and is tempered; with k k k growing it is consistent. Expressed information describes the whole transition.
Proposition 17 (Nearest neighbours). Let K = 2 K = 2 K = 2 , X ⊆ R d \mathcal{X} \subseteq\mathbb{R}^{d} X ⊆ R d , let η 1 \eta_{1} η 1 be continuous, and let k k k be fixed and odd. Let β k ( t ) = P ( Bin ( k , t ) > k / 2 ) \beta_{k}(t) = \mathbb{P}(\operatorname{Bin}(k,t) > k/2) β k ( t ) = P ( Bin ( k , t ) > k /2 ) . As n → ∞ n \to\infty n → ∞ , for almost every x x x ,
V n ( x ) → h ( min { β k ( η 1 ( x ) ) , 1 − β k ( η 1 ( x ) ) } ) ≤ h ( min { 1 2 , e − 2 k ( η 1 ( x ) − 1 / 2 ) 2 } ) , V_{n}(x) \to h\left(\min\{\beta_{k}(\eta_{1}(x)),1-\beta_{k}(\eta_{1}(x))\}\right) \leq h\left(\min\left\{\frac{1}{2},e^{-2k(\eta_{1}(x)-1/2)^{2}}\right\}\right), V n ( x ) → h ( min { β k ( η 1 ( x )) , 1 − β k ( η 1 ( x ))} ) ≤ h ( min { 2 1 , e − 2 k ( η 1 ( x ) − 1/2 ) 2 } ) , and the modal prediction converges to b ∗ b^{*} b ∗ . In particular, for the 1-NN rule, E V n → H ( Y ∣ X ) \mathbb{E}V_{n} \to H(Y \mid X) E V n → H ( Y ∣ X ) , and Theorem 9 gives E R − R ∗ → 2 E [ η 1 ( 1 − η 1 ) ] − R ∗ \mathbb{E}R - R^{*} \to2\mathbb{E}[\eta_{1}(1-\eta_{1})] - R^{*} E R − R ∗ → 2 E [ η 1 ( 1 − η 1 )] − R ∗ , the classical limit of Cover and Hart [17 ] .
Let us restate the result for k = 1 k = 1 k = 1 in plain terms. Asymptotically, the 1-NN rule expresses exactly the label noise: its prediction at a new input is the label of a nearby training point, which is a fresh noisy draw from η ( x ) \eta(x) η ( x ) . So the 1-NN rule passes on all the noise it stores, at the rate of H ( Y ∣ X ) H(Y \mid X) H ( Y ∣ X ) bits per prediction. In the running example this is 0.595 bits, and at n = 4096 n = 4096 n = 4096 we measure 0.642 bits (Table 1 ; our checks in Appendix § 21 .§ 2 match the limits of Proposition 17 to within 0.003 bits). The Cover–Hart excess risk of 1-NN thus follows from an information-theoretic statement. For larger fixed k k k , the expressed information decays exponentially in k k k wherever the margin is bounded away from zero; the rule remains tempered, with a smaller constant.
When k n → ∞ k_{n} \to\infty k n → ∞ and k n / n → 0 k_{n}/n \to0 k n / n → 0 , the rule is consistent, so E V n → 0 \mathbb{E}V_{n} \to0 E V n → 0 by Corollary 10. Under the standard smoothness and margin conditions (Audibert and Tsybakov, [5 ] ) we can also give a rate.
Proposition 18 (Rate of vanishing expression). Let X X X have a density on [ 0 , 1 ] d [0,1]^{d} [ 0 , 1 ] d bounded above and below, let η 1 \eta_{1} η 1 be Lipschitz, and assume the margin condition P ( 0 < ∣ η 1 ( X ) − 1 2 ∣ ≤ t ) ≤ C 0 t α \mathbb{P}(0 < |\eta_{1}(X) - \frac{1}{2}| \leq t) \leq C_{0}t^{\alpha} P ( 0 < ∣ η 1 ( X ) − 2 1 ∣ ≤ t ) ≤ C 0 t α . With k n ≍ n 2 / ( d + 2 ) k_{n} \asymp n^{2/(d+2)} k n ≍ n 2/ ( d + 2 ) , the k n k_{n} k n -NN rule has E V n = O ( n − α / ( d + 2 ) ) \mathbb{E}V_{n} = O(n^{-\alpha/(d+2)}) E V n = O ( n − α / ( d + 2 ) ) .
The rate is half the exponent of the familiar excess-risk rate n − ( 1 + α ) / ( d + 2 ) n^{-(1+\alpha)/(d+2)} n − ( 1 + α ) / ( d + 2 ) ; the difference is the margin weighting in Theorem 9 . In simulation with d = α = 1 d = \alpha= 1 d = α = 1 we measure slopes of − 0.32 -0.32 − 0.32 for E V n \mathbb{E}V_{n} E V n and − 0.68 -0.68 − 0.68 for excess risk, against the predicted − 1 3 -\frac{1}{3} − 3 1 and − 2 3 -\frac{2}{3} − 3 2 (Appendix § 21 .§ 2 ).
Averaging removes expression but keeps modal bias
Ensembling is the most common way to make interpolators benign. Theorem 9 says exactly what it does.
Proposition 19 (Averaging). Let g B g_{B} g B be the majority vote of B B B independently trained copies of a binary learner (B B B odd). Then g B g_{B} g B has the same modal prediction as one copy, and its expressed information satisfies V g B ( x ) ≤ h ( min { 1 2 , e − 2 B ( 1 / 2 − π ( x ) ) 2 } ) V_{g_{B}}(x) \leq h\left(\min\left\{\frac{1}{2},e^{-2B(1/2-\pi(x))^{2}}\right\}\right) V g B ( x ) ≤ h ( min { 2 1 , e − 2 B ( 1/2 − π ( x ) ) 2 } ) , where π ( x ) = h − 1 ( V ( x ) ) \pi(x) = h^{-1}(V(x)) π ( x ) = h − 1 ( V ( x )) is the single learner’s probability of departing from its mode.
So averaging removes expressed information exponentially fast in B B B , but it leaves the modal bias untouched. It reduces risk where the mode is right and locks in the error where the mode is wrong. This is an information-theoretic form of the observation that bagging helps unstable learners and does not help biased ones [15 ] . Appendix E gives the exact limiting change in risk, and a related result for stable learners: replace-one stability β n \beta_n β n at x x x implies V n ( x ) ≤ h ( min { 1 2 , n β n ( x ) } ) V_n(x) \le h(\min\{\frac{1}{2}, n\beta_n(x)\}) V n ( x ) ≤ h ( min { 2 1 , n β n ( x )}) , so uniformly stable learners [14 ] express little.
Minimum-norm interpolation and double descent
The best-understood benign interpolator is minimum-norm least squares in high dimensions [7 , 33 ] . Using the squared-loss version of expressed information (Theorem 13 ), we can compute V V V exactly for it.
Proposition 20 (Minimum-norm least squares). Let y = X β + ε y = X\beta+ \varepsilon y = X β + ε with a fixed design X ∈ R n × p X \in\mathbb{R}^{n \times p} X ∈ R n × p , p ≥ n p \ge n p ≥ n , noise ε ∼ N ( 0 , σ ε 2 I ) \varepsilon\sim N(0, \sigma_{\varepsilon}^{2}I) ε ∼ N ( 0 , σ ε 2 I ) , and estimator β ^ = X + y \hat{\beta} = X^{+}y β ^ = X + y . Let x ′ x' x ′ be a test input with covariance Σ \Sigma Σ . With the label noise as the only source of randomness,
V σ ( x ′ ) = 1 2 log ( 1 + σ ε 2 σ 2 ∥ ( X + ) T x ′ ∥ 2 ) , lim σ → ∞ 2 σ 2 E V σ ( x ′ ) = σ ε 2 tr ( C ) , V_{\sigma}(x') = \frac{1}{2}\log\left(1 + \frac{\sigma_{\varepsilon}^{2}}{\sigma^{2}}\left\lVert(X^{+})^{\mathsf{T}}x' \right\rVert^{2}\right), \qquad\lim_{\sigma\to\infty} 2\sigma^{2}\mathbb{E}V_{\sigma}(x') = \sigma_{\varepsilon}^{2}\operatorname{tr}(C), V σ ( x ′ ) = 2 1 log ( 1 + σ 2 σ ε 2 ( X + ) T x ′ 2 ) , σ → ∞ lim 2 σ 2 E V σ ( x ′ ) = σ ε 2 tr ( C ) , where C = ( X X T ) − 1 X Σ X T ( X X T ) − 1 C = (XX^{\mathsf{T}})^{-1}X\Sigma X^{\mathsf{T}}(XX^{\mathsf{T}})^{-1} C = ( X X T ) − 1 X Σ X T ( X X T ) − 1 .
The limit σ ε 2 tr ( C ) \sigma_{\varepsilon}^{2}\operatorname{tr}(C) σ ε 2 tr ( C ) is exactly the variance term in the analysis of Bartlett et al. [7 ] . So, in their setting, minimum-norm interpolation is benign precisely when its label-noise expressed information vanishes, which by their theorem happens exactly when the covariance Σ \Sigma Σ satisfies their effective-rank conditions. Their conditions can be read as conditions under which noise that is stored in many unimportant directions is not expressed in the important ones.
The same view explains double descent [9 ] . As the number of random features p p p grows past the number of examples n n n , the test error of the minimum-norm fit first peaks at p ≈ n p \approx n p ≈ n and then falls again. At the peak the fit is forced through every noisy label with the fewest possible degrees of freedom, so its predictions are extremely sensitive to the noise: expressed information is near its maximum. As p p p grows further, the noise is spread over many directions and expressed less. In § 7.2 we show that test error and V V V peak together, on synthetic and real data, and that a small ridge penalty removes both peaks. This is consistent with variance-based accounts of double descent [2 , 74 , 49 ] ; the information view adds that storage is constant along the whole interpolating branch, so the entire curve is driven by expression.
Expressed information as a model-selection criterion
In the last two sections we used expressed information to explain benign overfitting. We will now use it to choose among learners. We first explain why choosing among interpolators is hard for standard tools (§ 6.1 ). We then show that V V V ranks candidates correctly when they have no modal bias, and argue that the overparameterized regime is where this is most nearly the case (§ 6.2 ). § 6.3 explains how to estimate V V V from a single dataset, and why this must be done with disjoint splits. Finally, § 6.4 describes when V V V alone is not enough, and what to do then.
Why selecting among interpolators is hard
Suppose we have several candidate learners, for example the five interpolators of Table 1 , and one noisy training set. Let us recall what the previous sections tell us about the usual tools.
Validation works, but it needs labels that are not used for training, and in a noisy problem these labels are noisy too. With n v a l n_{\mathrm{val}} n val validation points, the standard error of a validation error is about R / n v a l \sqrt{R/n_{\mathrm{val}}} R / n val , which, for small validation sets, is often larger than the differences between good candidates.
Expressed information avoids all four problems. It looks at predictions at fresh inputs, not at the training set; it does not need validation labels, only unlabelled inputs; and, by Theorem 9 , it is directly tied to excess risk. Being free of ground truth at the selection step, it can also be used where held-out labels are not available at all, for instance in semi-supervised or streaming settings; § 9 discusses these uses and the unsupervised analogue.
Expressed information ranks candidates without modal bias
Recall from Theorem 9 that excess risk has two sources: expression, measured by V V V , and modal bias, the mass of inputs where the learner’s most frequent prediction is wrong. If the candidates have no modal bias, only the first source is left, and V V V should rank them. The next proposition makes this precise.
Proposition 21 (Ranking candidates without modal bias). Consider candidate learners j = 1 , … , J j = 1,\ldots,J j = 1 , … , J whose modal predictions are all correct, m j ( X ) = b ∗ ( X ) m_j(X) = b^*(X) m j ( X ) = b ∗ ( X ) almost surely.
(a) For binary labels, with π j ( x ) = h − 1 ( V j ( x ) ) \pi_j(x) = h^{-1}(V_j(x)) π j ( x ) = h − 1 ( V j ( x )) the probability that candidate j j j departs from its mode at x x x ,
E R ( h W j ) − R ∗ = E [ ∣ 2 η 1 ( X ) − 1 ∣ π j ( X ) ] . \mathbb{E}\,R(h_{W_j}) - R^* = \mathbb{E}\left[|2\eta_1(X)-1|\pi_j(X)\right]. E R ( h W j ) − R ∗ = E [ ∣2 η 1 ( X ) − 1∣ π j ( X ) ] . Hence, if V i ( x ) ≤ V j ( x ) V_i(x) \le V_j(x) V i ( x ) ≤ V j ( x ) for almost every x x x , then candidate i i i has excess risk no larger than candidate j j j . If the margin ∣ 2 η 1 − 1 ∣ |2\eta_1-1| ∣2 η 1 − 1∣ is constant, as it is for symmetric label noise on a noiseless task, then ranking by the mean off-mode probability π ˉ j = E π j ( X ) \bar{\pi}_j = \mathbb{E}\,\pi_j(X) π ˉ j = E π j ( X ) is exactly ranking by excess risk.
(b) For K K K classes, E [ γ ( X ) ϕ K − 1 ( V j ( X ) ) ] ≤ E R ( h W j ) − R ∗ ≤ 1 2 E [ Δ ( X ) V j ( X ) ] \mathbb{E}[\gamma(X)\phi_K^{-1}(V_j(X))] \le\mathbb{E}\,R(h_{W_j})-R^* \le\frac{1}{2}\mathbb{E}[\Delta(X)V_j(X)] E [ γ ( X ) ϕ K − 1 ( V j ( X ))] ≤ E R ( h W j ) − R ∗ ≤ 2 1 E [ Δ ( X ) V j ( X )] , so the excess risk of every candidate is sandwiched between two increasing functions of its pointwise expressed information.
Proof. Both parts follow from Theorem 9 with 1 { m j ≠ b ∗ } = 0 \mathbb{1}\{m_j \ne b^*\}=0 1 { m j = b ∗ } = 0 . Monotonicity in (a) holds because h − 1 h^{-1} h − 1 is increasing.
In plain terms, among learners whose “average prediction” is right, the one whose predictions depend least on the particular sample is the best. Note that the proposition needs no labels at all: V j V_j V j and π j \pi_j π j are properties of the candidates’ predictions only.
Why the overparameterized regime. The condition of Proposition 21 , no modal bias, is not something we can check directly. But there are good reasons to expect it to hold approximately among flexible, overparameterized learners, and to fail mainly for rigid ones.
The modal prediction of a learner is the prediction of an infinite bagged ensemble of independent copies of it (§ 4.3 ). For flexible learners this ensemble is typically close to consistent: for k k k -NN, the mode converges to b ∗ b^* b ∗ for every fixed k k k (Proposition 17 ), and similar statements hold for trees and forests. What separates flexible interpolators is then how much they express, not where their average prediction lies.
In the running example (Example 1) at n = 4096 n = 4096 n = 4096 , the modal bias of every interpolator is at most 0.0004, while their excess risks range from 0.001 to 0.13. Over all 72 noisy interpolating configurations of our synthetic experiment (§ 7.1 ), modal bias accounts on average for about 4% of excess risk.
Learners with substantial modal bias are those that cannot represent the Bayes classifier at all, such as a linear model on a curved boundary. These are typically the underparameterized candidates, which do not interpolate. It is tempting to screen them out by their training fit before applying min-V V V , but under label noise this also removes the well-regularized candidates, which do not fit noisy labels either and are often the best (§ 7.7 ). They are better handled by the extension of § 6.4 , which estimates modal bias directly.
So, among overparameterized candidates, Proposition 21 suggests a simple rule: choose the candidate with the smallest expressed information . We call this rule min-V . We test it in § 7.5 .
Estimating expressed information
Expressed information is defined over independent training samples. Let us now discuss how to estimate it in two situations: when several independent samples are available, and when, as is usual, there is only one.
Plug-in estimate. Let h 1 , … , h R h_1,\ldots,h_R h 1 , … , h R be R R R trained copies of a candidate, and let x 1 , … , x M x_1,\ldots,x_M x 1 , … , x M be unlabelled inputs (for example the inputs of a test set, or any unlabelled data from the same distribution). For each x m x_m x m , let q ^ ( ⋅ ∣ x m ) \hat{q}(\cdot\mid x_m) q ^ ( ⋅ ∣ x m ) be the empirical distribution of the R R R predictions. We estimate V V V by
V ^ = 1 M ∑ m = 1 M [ H ( q ^ ( ⋅ ∣ x m ) ) + k ^ m − 1 2 R ln 2 ] . \widehat{V} = \frac{1}{M} \sum_{m=1}^{M} \left[ H(\hat{q}(\cdot\mid x_m)) + \frac{\hat{k}_m - 1}{2R\ln2} \right]. V = M 1 m = 1 ∑ M [ H ( q ^ ( ⋅ ∣ x m )) + 2 R ln 2 k ^ m − 1 ] .
where k ^ m \hat{k}_m k ^ m is the number of distinct predictions at x m x_m x m ; the second term is the Miller–Madow bias correction [50 ] . Similarly, π ^ = 1 M ∑ m ( 1 − max k q ^ ( k ∣ x m ) ) \hat{\pi} = \frac{1}{M}\sum_m(1-\max_k\hat{q}(k\mid x_m)) π ^ = M 1 ∑ m ( 1 − max k q ^ ( k ∣ x m )) estimates the mean off-mode probability. The plug-in entropy is biased low for small R R R , but the bias affects all candidates in a similar way. In our experiments (Appendix § 21 .§ 1 ) the corrected estimate from R = 5 R = 5 R = 5 runs recovers 62–91% of the reference value and ranks four learners correctly for every R ≥ 5 R \ge5 R ≥ 5 .
Several independent samples. If the R R R copies are trained on independent samples, with independent label noise, V ^ \hat{V} V ^ is a consistent estimate of E V \mathbb{E}V E V as R , M → ∞ R,M\to\infty R , M → ∞ . This situation arises when several labelled batches, or several independent noisy labellings, are available.
One dataset: use disjoint splits. Usually there is a single labelled dataset. The natural idea is to reuse the fold models of R R R -fold cross-validation. There is a catch, and it matters. Fold models of R R R -fold cross-validation with R > 2 R>2 R > 2 share most of their training points and, crucially, the same noisy labels . A mislabelled training point is seen by R − 1 R-1 R − 1 of the R R R fold models, and they will tend to agree near it. So the expression of label noise, which is precisely what V V V is meant to measure, is largely hidden.
Remark 1 (Overlapping folds hide expression). Consider the 1-NN rule and a test input x x x whose nearest neighbour in the full training set is the point ( X i , Y i ) (X_i,Y_i) ( X i , Y i ) . That point is in the training set of R − 1 R-1 R − 1 of the R R R fold models of R R R -fold cross-validation, and each of them predicts Y i Y_i Y i at x x x . So the estimated probability of departing from the mode at x x x is at most 1 / R 1/R 1/ R , whatever the noise level. In contrast, Proposition 17 says that the true off-mode probability of 1-NN tends to min ( η 1 ( x ) , 1 − η 1 ( x ) ) \min(\eta_1(x),1-\eta_1(x)) min ( η 1 ( x ) , 1 − η 1 ( x )) .
The remedy is to train the copies on disjoint parts of the data. With two disjoint halves, the two copies see independent labels, and the only cost is that each sees half the data. Their predictions also give a 2-fold cross-validation estimate for free. We write V 2 V_2 V 2 for V V V estimated from the two fold models of 2-fold cross-validation, and V 5 V_5 V 5 for V V V estimated from the five fold models of 5-fold cross-validation. Remark 1 predicts that V 5 V_5 V 5 is less reliable than V 2 V_2 V 2 , despite using more models; § 7.5 confirms this.
Cost. Computing V 2 V_2 V 2 costs two fits on half of the data, plus predictions on unlabelled inputs. In our measurements (§ 7.5 ) this is 1.25 times the cost of one holdout fit, of which the unlabelled predictions are about 1%.
When expressed information alone is not enough
Proposition 21 assumes that the candidates have no modal bias. We now discuss what happens when this fails, and give two remedies. The theory behind this subsection is in Appendix § 17 .
Failure 1: underfitting candidates. If the pool contains rigid learners, such as strongly regularized linear models, these have low V V V (their predictions hardly depend on the sample) and may have large modal bias. Min-V V V will then prefer them wrongly. Some estimate of modal bias is needed.
Remedy 1: a label-free consensus criterion. The modal bias of candidate j j j is β j = P ( m j ( X ) ≠ b ∗ ( X ) ) \beta_j=\mathbb{P}(m_j(X)\ne b^*(X)) β j = P ( m j ( X ) = b ∗ ( X )) . We cannot compute it, since b ∗ b^* b ∗ is unknown, but we can compare each candidate’s modal prediction with the consensus c ( x ) c(x) c ( x ) , the plurality vote of all candidates’ modal predictions. Let D j = P ( m j ( X ) ≠ c ( X ) ) D_j=\mathbb{P}(m_j(X)\ne c(X)) D j = P ( m j ( X ) = c ( X )) be candidate j j j ’s disagreement with the consensus. We score candidate j j j by
L F j = D j + π ˉ j ( 1 − K K − 1 D j ) , (3) \mathrm{LF}_j = D_j+\bar{\pi}_j\left(1-\frac{K}{K-1}D_j\right), \tag*{(3)} LF j = D j + π ˉ j ( 1 − K − 1 K D j ) , (3)
and choose the candidate with the lowest score. The form of (3) mirrors the exact decomposition (2) : if the consensus were the Bayes classifier, D j D_j D j would be the modal-bias mass, and a candidate would err where its mode is wrong, plus where it departs from a correct mode. The criterion uses no labels at all, only predictions on unlabelled inputs. Appendix § 17 shows that disagreement estimates modal bias up to the consensus error δ = P ( c ( X ) ≠ b ∗ ( X ) ) \delta= \mathbb{P}(c(X) \ne b^*(X)) δ = P ( c ( X ) = b ∗ ( X )) , in the sense that ∣ D j − β j ∣ ≤ δ |D_j - \beta_j| \le\delta ∣ D j − β j ∣ ≤ δ , and that δ ≤ 2 β ˉ \delta\le2\bar{\beta} δ ≤ 2 β ˉ , twice the average modal bias of the candidates. So the consensus can be trusted unless a large part of the pool shares the same bias. When many candidates are near-copies of one model family, giving one vote per cluster of near-identical candidates restores this (Appendix § 17 ).
Failure 2: asymmetric label noise. If the training labels are flipped more often in one direction than the other, every candidate learns the same shifted decision boundary. Their modal predictions all agree, and all are wrong on the same region. This shared bias is invisible to V V V , to the consensus, and also to validation on equally noisy labels. For binary labels flipped 0 → 1 0 \to1 0 → 1 with probability ρ 0 \rho_0 ρ 0 and 1 → 0 1 \to0 1 → 0 with probability ρ 1 \rho_1 ρ 1 , the shift moves the threshold on η 1 \eta_1 η 1 from 1 2 \frac{1}{2} 2 1 to ( 1 2 − ρ 0 ) / ( 1 − ρ 0 − ρ 1 ) (\frac{1}{2} - \rho_0)/(1 - \rho_0 - \rho_1) ( 2 1 − ρ 0 ) / ( 1 − ρ 0 − ρ 1 ) ; it vanishes exactly when ρ 0 = ρ 1 \rho_0 = \rho_1 ρ 0 = ρ 1 (Proposition S11).
Remedy 2: detect asymmetry and switch to noise-corrected validation. Label noise can be corrected if its transition matrix T j k = P ( Y ~ = k ∣ Y = j ) T_{jk} = \mathbb{P}(\widetilde{Y} = k \mid Y = j) T j k = P ( Y = k ∣ Y = j ) is known, by the backward correction of Natarajan et al. [53 ] and Patrini et al. [57 ] : the loss of predicting y ^ \hat{y} y ^ for a noisy label y ~ \widetilde{y} y is replaced by 1 − ( T − 1 ) y ~ y ^ 1 - (T^{-1})_{\widetilde{y}\hat{y}} 1 − ( T − 1 ) y y ^ , which is unbiased for the clean 0-1 loss. We estimate T T T without extra labels, by cross-tabulating the consensus of the candidates’ out-of-fold predictions against the noisy training labels. Under symmetric noise, correction cannot change the ranking of candidates at all, because the corrected loss is an increasing affine function of the noisy one (Remark S3); it can only help when the noise is asymmetric. This suggests a simple switch rule: measure the asymmetry of T ^ \hat{T} T ^ (its largest deviation from a symmetric noise matrix with the same mean flip rate); if it exceeds 0.1, select by noise-corrected cross-validation; otherwise, use the label-free criterion.
Summary of the recommendations. Putting this section together, we suggest the following.
Among overparameterized, flexible candidates, select by min-V V V , estimated on unlabelled inputs from copies trained on disjoint parts of the data (V 2 V_2 V 2 from a single dataset).
When the pool also contains rigid or regularized candidates, use the label-free criterion (3), which adds a consensus estimate of modal bias.
When the label noise may be asymmetric, check the asymmetry of T ^ \hat{T} T ^ , and switch to noise-corrected cross-validation if it is large.
§ 7.5 tests the first rule and § 7.7 the other two.
Experiments
We now test the theory of § 4 –§ 5 and the selection rules of § 6 . Let us first say what each experiment is for.
Details of all experiments (datasets, learner configurations, noise models, protocols and compute) are in Appendix § 20 , and further results in Appendix § 21 . Appendix § 24 maps every figure and table to the script that produces it. In all tables, bold marks the best value in each column of each comparison, and {sup}†` marks methods proposed in this paper.
Exact validation on synthetic data
Setup. We use the running example (Example 1), for which η \eta η and b ∗ b^{*} b ∗ are known, so excess risk and V V V can be computed exactly over all 2 19 2^{19} 2 19 inputs (in practice, on a fixed Monte Carlo set of 20,000 test inputs). We train 8 learners: memorize-and-smooth (Proposition 16 ), 1-NN, k k k -NN with k ≈ n k \approx\sqrt{n} k ≈ n , a full-depth tree, a random forest, gradient boosting with exponential loss, a 512-unit MLP trained to interpolate, and weakly regularized logistic regression. We use n ∈ { 256 , 1024 , 4096 } n \in\{256, 1024, 4096\} n ∈ { 256 , 1024 , 4096 } and label noise ε ∈ { 0 , 0.1 , 0.2 , 0.3 , 0.4 } \varepsilon\in\{0, 0.1, 0.2, 0.3, 0.4\} ε ∈ { 0 , 0.1 , 0.2 , 0.3 , 0.4 } , which gives 120 configurations, each with R = 30 R = 30 R = 30 independent training samples.
Results. Figure 1 (left) shows that V V V and excess risk are tightly linked. The Spearman correlation between them is 0.96 over all 120 configurations, and 0.92 over the 72 noisy interpolating ones. For comparison, training error has a correlation of 0.14 with excess risk. Every configuration lies within the bounds of Theorem 9 . To show this with a single band for all noise levels, the figure normalises by the mean margin and weights V V V by the margin, as in the theorem; the band from h − 1 ( V ˉ ) h^{-1}(\bar{V}) h − 1 ( V ˉ ) to V ˉ / 2 \bar{V}/2 V ˉ /2 is then the tightest range that can be stated in terms of the mean of V V V alone (the lower edge follows from the exact binary identity by convexity of h − 1 h^{-1} h − 1 , and the upper edge is attained when V ( x ) V(x) V ( x ) takes only the values 0 and 1). The points lie close to the lower edge (for configurations with V ˉ > 0.05 \bar{V} > 0.05 V ˉ > 0.05 and no modal bias, a median of 11% of the way from the lower to the upper edge), which means that the off-mode probability is spread fairly evenly over inputs, so that h − 1 ( V ˉ ) h^{-1}(\bar{V}) h − 1 ( V ˉ ) is itself a good estimate of normalised excess risk. The modal bias of every interpolator is small at moderate noise (at most 0.0004 at n = 4096 n = 4096 n = 4096 and ε = 0.2 \varepsilon= 0.2 ε = 0.2 ), as § 6.2 anticipated, so almost all of the excess risk of interpolators comes from expression. It grows at high noise (up to 0.019 at ε = 0.4 \varepsilon= 0.4 ε = 0.4 ), partly because the mode is then estimated from only 30 copies.
Figure 1. Synthetic validation on the running example. Left: the two-sided bound of Theorem 9 for 120 configurations (blue: interpolating). Both axes are normalised by the mean margin m ˉ = E ∣ 2 η 1 ( X ) − 1 ∣ \bar{m} = \mathbb{E}|2\eta_1(X)-1| m ˉ = E ∣2 η 1 ( X ) − 1∣ , which differs between noise levels: the vertical axis is exact excess risk divided by m ˉ \bar{m} m ˉ , the horizontal axis is the margin-weighted expressed information V ˉ = E [ ∣ 2 η 1 ( X ) − 1 ∣ V ( X ) ] / m ˉ \bar{V} = \mathbb{E}[|2\eta_1(X)-1|V(X)]/\bar{m} V ˉ = E [ ∣2 η 1 ( X ) − 1∣ V ( X )] / m ˉ . For binary labels the theorem then gives h − 1 ( V ˉ ) ≤ ( E R − R ∗ ) / m ˉ ≤ V ˉ / 2 + β / m ˉ h^{-1}(\bar{V}) \leq(\mathrm{ER}-R^*)/\bar{m} \leq\bar{V}/2+\beta/\bar{m} h − 1 ( V ˉ ) ≤ ( ER − R ∗ ) / m ˉ ≤ V ˉ /2 + β / m ˉ , with β \beta β the margin-weighted modal bias; the shaded band is this range for β = 0 \beta=0 β = 0 . The lower edge holds for every learner, the upper edge when β = 0 \beta=0 β = 0 ; hollow points have β / m ˉ > 1 % \beta/\bar{m}>1\% β / m ˉ > 1% . Right: V V V against training-set size at ε = 0.2 \varepsilon=0.2 ε = 0.2 . Memorize-and-smooth and the random forest are benign (V → 0 V\to0 V → 0 ); 1-NN and the full tree are tempered, with V V V approaching the label noise H ( Y ∣ X ) = 0.595 H(Y\mid X)=0.595 H ( Y ∣ X ) = 0.595 bits (dashed); the MLP’s V V V grows with n n n .
Figure 1 (right) illustrates the taxonomy of § 5.1 . Memorize-and-smooth and the random forest are benign: their V V V decreases towards 0 as n n n grows. The 1-NN rule and the full tree are tempered: their V V V stays close to H ( Y ∣ X ) = 0.595 H(Y \mid X) = 0.595 H ( Y ∣ X ) = 0.595 bits, as Proposition 17 predicts for 1-NN. The interpolating MLP is tempered too, but becomes worse with more data: from n = 256 n = 256 n = 256 to $n = 4096 its excess risk grows from 0.051 to 0.075 and its V V V from 0.35 to 0.47 bits. All of these learners store the same n H ( Y ∣ X ) nH(Y\mid X) n H ( Y ∣ X ) bits (Theorem 5 ).
Excess complexity of the trained outputs. The ideal-model quantities of § 3 can also be measured. The 0-1 excess complexity of a learner’s output, H ( F ∣ b ∗ ( X ) ) H(F\mid b^*(X)) H ( F ∣ b ∗ ( X )) , has a Spearman correlation of 0.95 with excess risk. The held-out log-loss estimator of Proposition 3 has correlation 0.85, but it underestimates the true value by 0.35 bits on average (Appendix § 13 .§ 1 explains why: it is a lower bound for non-sufficient outputs).
Disagreement measures excess risk, not risk. Table 3 checks Proposition 15 on the running example at n = 4096 n=4096 n = 4096 , with 10 copies per learner. For every learner, disagreement lies between excess risk and V V V , as part (b) predicts. For the tempered learners (1-NN, the full tree, boosting), disagreement over independent samples is close to the test error, so the generalization disagreement equality of Jiang et al. [39 ] approximately holds. For the benign or consistent ones (memorize-and-smooth, the random forest, and the non-interpolating k k k -NN with k ≈ n k\approx\sqrt{n} k ≈ n ), disagreement is close to zero while the test error stays at R ∗ = 0.15 R^*=0.15 R ∗ = 0.15 , as part (c) predicts. Disagreement between copies trained on the same sample with different seeds, the setting of the GDE, is zero for the deterministic learners, including 1-NN, whose test error is 0.27.
Table 3 : Disagreement, excess risk and expressed information on the running example (n = 4096 n = 4096 n = 4096 , ε = 0.2 \varepsilon= 0.2 ε = 0.2 , R ∗ = 0.150 R^{*} = 0.150 R ∗ = 0.150 ; 10 copies per learner; exact risks). “Dis. (samples)”: disagreement of copies trained on independent samples; “Dis. (seeds)”: copies trained on one sample with different seeds, as in the GDE. †: learner constructed in this paper. Descriptive table; nothing is bolded.
Table 3.
Double descent and width selection
Setup. We fit random ReLU features by minimum-norm least squares on ± 1 \pm1 ± 1 labels and predict by sign, sweeping the number of features p p p from 16 to 4096 at n = 512 n = 512 n = 512 , with 40 independent training sets per width. We repeat this on two real datasets (digits, 10 classes, n = 629 n = 629 n = 629 , with one-hot targets; and wdbc, n = 199 n = 199 n = 199 ), with 20% injected label noise.
Double descent is a peak of expression. Figure 2 shows the familiar double-descent curve. At ε = 0.2 \varepsilon= 0.2 ε = 0.2 , excess risk is 0.034 at p = 64 p = 64 p = 64 , peaks at 0.33 at p = 528 ≈ n p = 528 \approx n p = 528 ≈ n , and falls to 0.099 at p = 4096 p = 4096 p = 4096 . Expressed information follows the same curve: from 0.26 bits, to a peak of 0.98 bits (close to its maximum of 1 bit), and down to 0.57 bits. A small ridge penalty (λ = 10 − 2 \lambda= 10^{-2} λ = 1 0 − 2 ) removes both peaks. Across all 64 configurations, the Spearman correlation of V V V with excess risk is 0.99, and the bound of Theorem 9 holds in every case. The real datasets show the same picture (Appendix § 21 .§ 3 ): on digits the test error peaks at 0.88 together with V = 3.07 V = 3.07 V = 3.07 bits, against a ceiling of log 2 10 = 3.32 \log_{2} 10 = 3.32 log 2 10 = 3.32 bits.
Figure 2. Random-features least squares at n = 512 n = 512 n = 512 with label noise 0.2. Left : exact excess risk; right : expressed information; both against p / n p/n p / n (log scale). Minimum-norm interpolation (blue) shows a double-descent peak at p ≈ n p \approx n p ≈ n in both quantities; a small ridge penalty (grey) removes both.
Choosing the width among interpolating ones. Restricting to interpolating widths (p ≥ n p \ge n p ≥ n , minimum-norm), we ask whether min-V V V chooses the best width. Over the six cases (synthetic with ε ∈ { 0 , 0.2 } \varepsilon\in\{0, 0.2\} ε ∈ { 0 , 0.2 } , and the two real datasets with and without injected noise), the Spearman correlation between V V V and test error ranges from 0.98 to 1.00. Min-V V V chooses the best width in five of the six cases, and in the sixth (noiseless wdbc) its regret is 0.0029. A random interpolating width would have regret between 0.0018 and 0.23.
The information plane of boosting, revisited
The LMC papers argued, from information-plane trajectories, that boosting compresses its output as it maximizes margins, and that this compression explains why it keeps improving after reaching zero training error ([55 , 54 ] ). Let us now revisit that picture with the tools of this paper.
On the running example with ε = 0.2 \varepsilon= 0.2 ε = 0.2 (Figure 3 ), the old information-plane coordinate rises and then falls, from 0.58 to 0.12, exactly the “compression” that the earlier papers reported. But over the same rounds, the excess risk increases from its minimum of 0.011 at round 15 to 0.050 at round 200, a factor of 4.5. Expressed information rises with it, from 0.09 to 0.35 bits. So, under label noise, the apparent compression goes together with worse generalization, and it is expression, not compression, that tracks test performance. The same happens on four real datasets with 20% injected noise (Appendix § 21 .§ 4 ): test error rises from its minimum to its final value, for example from 0.101 to 0.144 on wdbc and from 0.093 to 0.165 on biopsy, while the old coordinate shows “compression”. Without injected noise, on the nearly noiseless wdbc and biopsy, compression and falling test error coincide, as reported earlier. The earlier observations are thus reproduced where the labels are nearly noiseless, and reversed where they are not. Appendix § 18 discusses this in detail.
Figure 3. Gradient boosting on the running example (ε = 0.2 \varepsilon= 0.2 ε = 0.2 , shrinkage 0.1). Top: the information-plane coordinate used in the LMC papers, which rises and then falls (“compression”). Middle: expressed information. Bottom: exact excess risk. The dotted lines mark the best round (15) and the round where training error reaches 0.5%.
Expressed information ranks learners on real data
Setup. We use five datasets (wdbc, biopsy, OJ, a class-balanced Caravan, and digits). A fixed 30% of each is held out as a clean test set, and we inject symmetric label noise at rate ρ ∈ { 0 , 0.1 , 0.2 , 0.3 } \rho\in\{0, 0.1, 0.2, 0.3\} ρ ∈ { 0 , 0.1 , 0.2 , 0.3 } into the training labels only. We train 19 learner configurations (k k k -NN, trees, random forests, gradient boosting, logistic regression, RBF SVMs and MLPs, each at several capacity levels; Appendix § 20 ), each R = 12 R = 12 R = 12 times on random halves of the training pool with fresh noise draws. The Bayes risk is unknown, so we report clean test error, which ranks learners exactly as excess risk does within a dataset.
Results. Across the 20 dataset–noise combinations, the median Spearman correlation between V V V and clean test error is 0.94, and 0.96 when restricted to interpolators (Figure 4 ). The legacy LMC score is between 0.91 and 1.00 for every interpolator under injected noise, while their test errors range from 0.04 to 0.50: it does not rank them. Choosing the interpolator with the smallest V V V selects the one with the lowest test error in 16 of 17 cases (the remaining case costs 0.0015); a random interpolator would cost 0.059 on average. Finally, as Proposition 19 predicts, the majority vote of the R R R copies beats a single copy in every combination, and the gain grows with the noise rate (for example from 0.027 to 0.150 on digits as ρ \rho ρ goes from 0 to 0.3).
Figure 4. Real data with 20% injected label noise: clean test error against expressed information for 19 learner configurations per dataset (blue: interpolating). The circled point is the interpolator with the smallest V V V , chosen without validation labels.
Selecting among overparameterized learners
This is the main experiment on model selection. We ask whether min-V V V (§ 6.2 ) is a viable alternative to holdout validation and cross-validation for choosing among overparameterized learners. We use two protocols, which differ in what is available to the practitioner.
Protocol A: independent training samples. This is the setting in which V V V is defined. On the five datasets of § 7.4 , each candidate is trained 12 times on independent random halves of a training pool, each with its own label-noise draw. Holdout uses a separate validation set with labels corrupted by the same noise process (113–359 points), or a random subset of 40 of its points. We consider symmetric noise (0.2 and 0.3; 60 cases) and class-dependent noise (30 cases). Regret is the mean clean test error of a single trained model of the chosen configuration, minus that of the best configuration. Here we restrict the choice to configurations that interpolate.
Protocol B: one noisy dataset, matched compute. This is the realistic setting. On 15 datasets (the five above and ten PMLB benchmarks, each of at most 2,000 points), 30% is held out as a clean test set and the rest receives one draw of label noise: symmetric (0.2), class-dependent, or instance-dependent (labels near the decision boundary are flipped more often; mean flip rate 0.16). Each dataset–noise combination is repeated with five seeds, which change the train/test split, the subsample (for datasets above 2,000 points), the noise draw and the folds. There are 225 cases. The candidates are the six configurations designed to interpolate: 1-NN, a full-depth tree, a random forest with leaf size 1, gradient boosting with 300 depth-6 trees, an RBF SVM with C = 10 4 C = 10^{4} C = 1 0 4 , and a weakly regularized 512-unit MLP. Each is fitted once on 80% of the training set (for holdout), in 2-fold and 5-fold cross-validation, and on the full training set. Regret is the clean test error of the full refit of the chosen candidate, minus that of the best. We measure CPU time for every fit and every prediction. Means are over all 225 cases; 95% intervals for paired differences use a cluster bootstrap that resamples the 45 dataset–noise combinations, so the five seeds of one dataset are not treated as independent.
Results with independent samples (Table 4 , Panel A). When independent training samples are available, min-V V V is the best or tied-best criterion in every setting. Under symmetric noise it has a third of the regret of holdout with the full validation set (0.0010 against 0.0031), and a ninth of it with 40 validation points (0.0010 against 0.0094). The 95% bootstrap intervals for the difference from holdout are −0.002 [−0.005, 0.001] and −0.008 [−0.012, −0.005] under symmetric noise (full validation set and 40 points), and −0.001 [−0.004, 0.000] and −0.010 [−0.015, −0.006] under class-dependent noise. So the advantage is clear with small validation sets, and within noise with large ones. Min-V V V does not depend on the validation set at all, so it is unaffected by the size of the validation set, while holdout degrades as the validation set shrinks.
Table 4. Selecting among overparameterized learners: regret in clean test error (lower is better; mean over cases). Best per column in bold, within each panel. †: proposed in this paper. Panel A (independent training samples, interpolating configurations of 19): 12 independent fits per candidate for every criterion. Panel B (one noisy dataset; six overparameterized candidates; 15 datasets × 5 seeds per noise model): cost is the median CPU time relative to one holdout fit, including predictions on unlabelled inputs; “exact” counts the cases (of 225) in which the best candidate was chosen. *The consensus criterion and the noise-corrected CV use the consensus of a reference pool of all 19 configurations; their costs include fitting that pool. A random choice has regret 0.085 in Panel B.
Results on one dataset (Table 4 , Panel B; Figure 5 ). We highlight four findings; brackets give cluster-bootstrap 95% intervals for paired differences.
Figure 5. Protocol B in detail: selection regret for each noise model (mean over 15 datasets × \times × 5 seeds; error bars: standard error over datasets, after averaging the seeds of each dataset). Grey: criteria that use held-out labels; blue: criteria based on expressed information, which use no held-out labels. The consensus criteria and noise-corrected CV use a reference pool of all 19 configurations, whose cost is included. Bracketed: median compute relative to one holdout fit.
Min-V 2 V_2 V 2 beats holdout and 2-fold CV at the same cost, and matches 5-fold CV at a quarter of the cost. At 1.25 × 1.25\times 1.25 × the cost of one holdout fit, min-V 2 V_2 V 2 has 60% less regret than holdout (0.0055 against 0.0136; difference − 0.0081 -0.0081 − 0.0081 [− 0.0122 -0.0122 − 0.0122 , − 0.0039 -0.0039 − 0.0039 ]) and 44% less than 2-fold CV, which uses the same two fits (− 0.0043 -0.0043 − 0.0043 [− 0.0067 -0.0067 − 0.0067 , − 0.0022 -0.0022 − 0.0022 ]). It is indistinguishable from 5-fold CV (− 0.0001 -0.0001 − 0.0001 [− 0.0019 -0.0019 − 0.0019 , 0.0021]), which costs 4.99 × 4.99\times 4.99 × . The advantage over 2-fold CV holds under each noise model separately. Min-V 2 V_2 V 2 uses no held-out labels for the selection step: the two half-size models’ disagreement on unlabelled inputs carries more information about the ranking than their errors on the 50% of noisy labels they did not see.
Overlapping folds hurt V V V , as Remark 1 predicts. Min-V 5 V_5 V 5 uses more than twice as many models as min-V 2 V_2 V 2 and is worse (0.0101 against 0.0055; − 0.0046 -0.0046 − 0.0046 [− 0.0133 -0.0133 − 0.0133 , 0.0006]). It is no better than 5-fold CV, which uses the same models (+ 0.0044 +0.0044 + 0.0044 [− 0.0011 -0.0011 − 0.0011 , + 0.0133 +0.0133 + 0.0133 ]). With overlapping folds, the shared noisy labels hide exactly the expression that V V V is meant to measure.
Class-dependent noise is the hard case for V V V , as § 6.4 predicts: asymmetric noise creates a bias shared by all candidates, which V V V cannot see. Here min-V 2 V_2 V 2 (0.0121) is behind 5-fold CV (0.0100), although still ahead of holdout and 2-fold CV.
Adding a consensus estimate of modal bias gives the best criterion overall. The consensus criterion ((3) ), computed from two disjoint halves with a reference pool of 19 configurations, has the lowest mean regret (0.0033) and chooses the best candidate in 187 of 225 cases. It is significantly better than holdout (− 0.0103 -0.0103 − 0.0103 [− 0.0145 -0.0145 − 0.0145 , − 0.0065 -0.0065 − 0.0065 ]), 2-fold CV (− 0.0065 -0.0065 − 0.0065 [− 0.0099 -0.0099 − 0.0099 , − 0.0035 -0.0035 − 0.0035 ]), min-V 2 V_2 V 2 (− 0.0022 -0.0022 − 0.0022 [− 0.0051 -0.0051 − 0.0051 , − 0.0001 -0.0001 − 0.0001 ]), 5-fold CV (− 0.0023 -0.0023 − 0.0023 [− 0.0047 -0.0047 − 0.0047 , − 0.0006 -0.0006 − 0.0006 ]) and noise-corrected 5-fold CV (− 0.0024 -0.0024 − 0.0024 [− 0.0053 -0.0053 − 0.0053 , − 0.0004 -0.0004 − 0.0004 ]), at under half the cost of 5-fold CV even when the reference pool is included (2.39 × 2.39\times 2.39 × against 4.99 × 4.99\times 4.99 × ). Its gain is largest under class-dependent noise (0.0057
against 0.0100 for 5-fold CV), where the consensus supplies the modal-bias information that V V V lacks.
Seed 0 alone gives the same ordering with wider intervals, and seeds 1–4 replicate it (mean regret over seed 0 and over seeds 1–4: min-V 2 V_2 V 2 0.0069 and 0.0051, holdout 0.0125 and 0.0139, 5-fold CV 0.0035 and 0.0062). In summary: among overparameterized candidates, expressed information is a viable and cheap selection criterion. With independent samples it is the best criterion we tested. On a single dataset, estimated from two disjoint halves, it beats holdout and cross-validation of the same cost and matches 5-fold cross-validation; combined with a consensus estimate of modal bias, it beats 5-fold cross-validation at half the cost. The thresholds of § 6.4 were set on earlier experiments and frozen before Protocol B.
Comparison with selection by conditional mutual information
§ 4 argued that CMI (Steinke and Zakynthinou [65 ] ) measures the wrong thing for interpolators: it bounds the generalization gap, not excess risk. We now compare the two quantities directly as selection criteria , on the same data, the same models and the same compute.
Setup. We use the 225 cases of Protocol B (§ 7.5 ). The two halves of the 2-fold split form a supersample of pairs ( a i , b i ) (a_i,b_i) ( a i , b i ) , one point from each half; the two half-sample models are trained on the members selected by U U U and on the complement. Evaluated CMI (e-CMI; Steinke and Zakynthinou [65 ] ) is estimated per pair as the plug-in mutual information between the pair’s loss pattern and the selection bit, and averaged over pairs; functional CMI (Harutyunyan et al. [32 ] ) uses the prediction pattern instead and gives the same results here. Besides ranking by e-CMI itself, we rank by two generalization bounds built on it: training error plus 2 \sqrt{2} 2 e-CMI (Steinke and Zakynthinou [65 ] ), and training error plus the samplewise bound of Hellström and Durisi [34 ] . With one pair of fits, every criterion in the comparison uses exactly the two models of 2-fold CV and of min-V 2 V_2 V 2 . We also use two further random splits of the same supersample (three pairs of fits), which lets the CMI estimate average over several draws of U U U , and compare with repeated 2-fold CV and with V 2 V_2 V 2 averaged over the three pairs. The refits reproduce the Protocol B models exactly; details are in Appendix § 21 .§ 6 .
There is one difference in what the criteria need. CMI conditions on the supersample, labels included, so its estimate uses the label of the held-out member of each pair, as cross-validation does. Min-V 2 V_2 V 2 uses only predictions on unlabelled inputs.
Results (Table 5 ). Min-V V V is the better criterion, and it needs no held-out labels.
Table 5. Selection by CMI against selection by expressed information at matched cost (Protocol B, 225 cases; mean regret in clean test error, lower is better). Columns 3–6: the six overparameterized candidates of Table 4 , Panel B; “exact”: cases (of 225) in which the best candidate was chosen; cost: median CPU time relative to one holdout fit; last column: all 19 configurations. “Labels”: whether the criterion uses held-out labels. Best per column in bold. Functional CMI gives the same regrets as e-CMI among the overparameterized candidates. †: proposed in this paper.
At the cost of two fits, min-V 2 V_2 V 2 beats every CMI criterion. Its regret is 0.0055, against 0.0080 for e-CMI (−0.0025 [−0.0052, −0.0001]), 0.0092 for the 2 \sqrt{2} 2 e-CMI bound (−0.0037 [−0.0066, −0.0013]) and 0.0096 for the samplewise bound (−0.0041 [−0.0077, −0.0012]). It chooses the best candidate in 181 of 225 cases, against 163–164 for the CMI criteria. It is ahead under each noise model.
CMI behaves like cross-validation, because it is a function of held-out losses. For an interpolator the loss on the training member of a pair is zero, so the e-CMI estimate from one pair of fits is ln 2 times the probability that at least one of the pair’s two held-out predictions is wrong. Its regret is indeed close to that of 2-fold CV on the same fits (0.0080 against 0.0098; −0.0018
[−0.0051, +0.0014]). So CMI brings no information beyond the held-out labels it consumes, whereas V 2 V_2 V 2 replaces them by unlabelled inputs and does better.
With more fits, the advantage of V V V grows. With three pairs of fits, V 2 V_2 V 2 averaged over the pairs has regret 0.0031, the lowest in the table, against 0.0069 for the best CMI criterion (−0.0038 [−0.0071, −0.0013]) and 0.0166 for e-CMI itself, whose plug-in estimate is more biased with more draws. It also beats 5-fold CV (0.0056; −0.0026 [−0.0058, −0.0004]) at two thirds of its cost.
In a pool with rigid learners, neither criterion is enough on its own. With all 19 configurations, e-CMI has regret 0.089 and min-V 2 V_2 V 2 0.075. Both prefer rigid learners: CMI because their generalization gap is small whatever their error, V V V because their predictions hardly depend on the sample whatever their modal bias. Adding the training error, as the CMI bounds do, helps (0.045–0.053) but stays far behind cross-validation, because the bounds are loose (for interpolators, 2 \sqrt{2} 2 e-CMI ≈ 0.8 \approx0.8 ≈ 0.8 ). § 7.7 discusses how to handle such pools.
In summary, among overparameterized candidates and at matched cost, expressed information is both label-free and more accurate than CMI as a selection criterion. This is the empirical counterpart of Corollary 7 and Proposition 8 : CMI measures what the model reveals about which examples it was trained on, while V V V measures what reaches its predictions at fresh inputs, and only the latter is tied to excess risk.
Beyond overparameterized candidates
Finally, we test what happens when the candidate pool also contains underparameterized learners, for which modal bias is not negligible (§ 6.4 ). We use all 19 configurations under both protocols.
Min-V V V alone fails, as expected. With all candidates, V V V alone prefers rigid learners whose predictions hardly depend on the sample, even when their modal predictions are wrong. On one dataset (Protocol B; Figure 6 ), min-V 5 V_5 V 5 has regret 0.068 and min-V 2 V_2 V 2 0.075, against 0.020 for 5-fold CV. This is the failure that Proposition 21 warns of, and the reason we recommend min-V V V only among overparameterized candidates.
Figure 6. Protocol B with all 19 configurations (15 datasets × \times × 5 seeds per noise model; error bars: standard error over datasets). Grey: labelled criteria; dark blue: noise-corrected cross-validation; orange: criteria based on expressed information, computed from the cross-validation fold models. Bracketed: median compute relative to one holdout fit.
The extensions help, but on one dataset cross-validation remains best. With independent samples (Protocol A; Appendix § 21 .§ 5 ), the consensus criterion (3) has the lowest mean regret of all criteria, 0.0085 against 0.0219 for holdout, and it matches holdout with clean validation labels under symmetric noise (0.0037 against 0.0040). Under class-dependent noise, the switch rule of § 6.4 detects the asymmetry and improves on both of its components (regret 0.0106; overall 0.0060). On one dataset (Protocol B, 225 cases), however, noise-corrected 5-fold CV has the lowest mean regret (0.0149), significantly below 5-fold CV (0.0196; −0.0048 [−0.0073, −0.0025]), with almost all of the gain under class-dependent noise. The consensus criterion from two halves (0.0220) and the switch rule built on it (0.0217) cost 1.21× holdout, are significantly better than holdout (0.0326; −0.0106 [−0.0187, −0.0028]), and are on a par with 2-fold CV (0.0213), but they do not reach 5-fold or noise-corrected CV. The consensus criterion from five overlapping folds is worse (0.0287), for the reason given in Remark 1.
Screening by training fit first does not help. A natural alternative is a two-stage rule: keep the candidates that fit the training data, for example the interpolators, and choose among them by min-V 2 V_2 V 2 . This lowers the regret of min-V 2 V_2 V 2 in the 19-candidate pool from 0.075 to 0.046, but it stays behind holdout and cross-validation. Under label noise the best candidate is usually a regularized learner that does not interpolate, and the screen removes it in 85% of the cases; min-V V V then chooses well among interpolators, but the best interpolator is not the best candidate. Appendix § 21 .§ 6 gives the details, other screens (including the legacy LMC score), and the same finding with independent samples.
With a diverse pool and one dataset, our recommendation is therefore noise-corrected cross-validation, with expressed information computed from its fold models as a nearly free diagnostic (about 1% of the cost). A stress test with a controlled share of redundant, equally biased candidates, and with growing asymmetric noise, confirms the two failure modes predicted by the theory (Appendix § 21 .§ 7 ).
Connections to existing work
Throughout the paper we have pointed out connections as they arose. Let us now collect them, and say for each line of work what the present framework shares with it and what it adds.
Information bottleneck. The IB method describes a good representation as one that keeps as little information about the input as possible while keeping a prescribed amount of information about the label [69 ] . It has been proposed as a theory of deep learning [68 , 64 ] and as a training objective [1 , 66 ] . Our framework relates to it in five ways.
(i) Where the ideal model sits. Under log-loss, the indirect rate–distortion function (1) is the IB curve, the minimal sufficient complexity C log ∗ = H ( η ( X ) ) C_{\log}^{*} = H(\eta(X)) C l o g ∗ = H ( η ( X )) is its full-relevance end point (β → ∞ \beta\to\infty β → ∞ in the IB Lagrangian I ( T ; X ) − β I ( T ; Y ) I(T;X) - \beta I(T;Y) I ( T ; X ) − β I ( T ; Y ) ), and the G-LMC is the minimal sufficient statistic (Section 3.3. For other losses, (1) is a loss-specific bottleneck whose end point is H ( a ∗ ( X ) ) H(a^{*}(X)) H ( a ∗ ( X )) . Under 0-1 loss it ends at H ( b ∗ ( X ) ) H(b^{*}(X)) H ( b ∗ ( X )) , which is smaller than H ( η ( X ) ) H(\eta(X)) H ( η ( X )) under label noise. So a classifier does not need to compress to the log-loss IB end point; this distinction disappears for noiseless labels, the only case the original LMC covered. Restricted to deterministic representations, our complexity I ( F ; X ) = H ( F ) I(F;X) = H(F) I ( F ; X ) = H ( F ) is the objective of the deterministic IB [66 ] .
(ii) Excess complexity as distance to the curve. Excess complexity (Definition 2) is the vertical distance of a model above the (loss-specific) IB curve at the risk it achieves, i.e. its redundancy. Proposition 11 shows that, for a learner’s output at fresh inputs, total output entropy splits into this complexity and expressed information, so an information-plane coordinate computed for a learner mixes the two.
(iii) Estimation and compression phases. For deterministic maps of continuous inputs, I ( T ; X ) I(T;X) I ( T ; X ) is degenerate or infinite, so information-plane analyses depend on binning or noise [3 , 43 , 28 ] , and compression phases depend on the estimator and the activation function [61 ] . Our ideal-model quantities are defined for discrete variables, where they are finite, and V V V is an entropy over training samples at a fixed input, which needs no binning. Our boosting experiment (Section 7.3) agrees with Saxe et al. [61 ] that compression in the information plane need not track generalization: under label noise, an apparent compression coincides with a 4.5-fold increase in excess risk.
(iv) Information in the weights. Achille and Soatto [1 ] argued that limiting the information that the weights store about the training set, I ( W ; S ) I(W;S) I ( W ; S ) , favours invariant representations and good generalization. Theorem 5 shows that this cannot be a necessary condition for generalization: every interpolator, benign ones included, stores at least n H ( Y ∣ X ) nH(Y \mid X) n H ( Y ∣ X ) bits. In our terms, what matters is not how much is stored in the weights but how much reaches predictions.
(v) IB-based generalization bounds. Shamir et al. [63 ] bound the finite-sample error of IB solutions, and Kawaguchi et al. [40 ] bound the generalization gap of a network through I ( X ; Z ∣ Y ) I(X;Z \mid Y) I ( X ; Z ∣ Y ) for an intermediate representation Z Z Z , among other terms. Lemma S3 shows that under label noise this quantity cannot vanish even for the ideal representation: a log-loss sufficient output must retain at least H ( η ( X ) ∣ Y ) > 0 H(\eta(X) \mid Y) > 0 H ( η ( X ) ∣ Y ) > 0 bits about the input beyond the label, so such bounds have an irreducible term set by the noise.
Decision-theoretic sufficiency. ℓ \ell ℓ -sufficiency and ℓ \ell ℓ -deficiency (§ 3.1 ) are the sufficiency and deficiency of Blackwell [13 ] and Le Cam [45 ] , specialized to a single decision problem. The characterization in Proposition 1, that sufficiency means the Bayes act is recoverable, and the identification of the minimal sufficient complexity with H ( a ∗ ( X ) ) H(a^*(X)) H ( a ∗ ( X )) are elementary in that setting; what they give us is a loss-specific notion of “minimal model” that does not require the label to be a function of the input, unlike the original LMC (Proposition 4).
Information-theoretic generalization bounds, CMI and memorization. Bounds based on I ( W ; S ) I(W;S) I ( W ; S ) ([60 , 73 ] ) control the expected generalization gap, but I ( W ; S ) I(W;S) I ( W ; S ) can be infinite, for instance for deterministic learners with continuous parameters. Steinke and Zakynthinou [65 ] introduced the conditional mutual information CMI = I ( W ; U ∣ Z ~ ) = I(W;U \mid\widetilde{Z}) = I ( W ; U ∣ Z ) of a supersample, which is always at most n ln 2 n \ln2 n ln 2 , recovers VC-type and compression-based bounds, and gives ∣ E g a p ∣ ≤ 2 C M I / n |\mathbb{E}\,\mathrm{gap}| \le\sqrt{2\,\mathrm{CMI}/n} ∣ E gap ∣ ≤ 2 CMI / n . Variants evaluate the information in the losses or the predictions at the supersample points instead of the weights (functional CMI; Harutyunyan et al. [32 ] ). Several works show that such bounds must be large for some learners ([8 , 46 , 30 ] ), and that memorization of labels is sometimes necessary for good accuracy ([26 , 16 ] ). Harutyunyan et al. [31 ] relate the information stored about the labels to the number of training errors; Theorem 5 sharpens their result into an equality for interpolators. We connect to this line of work in three ways.
(i) Gap versus excess risk. All of these quantities bound the gap. For an interpolator the gap is its whole test error, at least R ∗ R^* R ∗ , for benign and tempered learners alike. So I ( W ; S ) ≥ n H ( Y ∣ X ) I(W;S) \ge nH(Y \mid X) I ( W ; S ) ≥ n H ( Y ∣ X ) (Corollary 6) and C M I ≥ n 2 ( R ∗ ) 2 \mathrm{CMI} \ge\frac{n}{2}(R^*)^2 CMI ≥ 2 n ( R ∗ ) 2 (Corollary 7); both grow linearly in n n n for every interpolator, and neither can separate a benign interpolator from a tempered one. The separating quantity must concern excess risk, which requires looking at predictions at fresh inputs.
(ii) CMI at fresh inputs. Proposition 8 places V V V in the supersample construction. V ( x ) V(x) V ( x ) splits into the information the prediction at a fresh input carries about the pool Z ~ \widetilde{Z} Z , about the selection U U U given the pool, and about the seed. The middle term is the fresh-input, prediction-level analogue of CMI. Functional CMI evaluates predictions at the 2 n 2n 2 n supersample points, half of which are training points, in order to bound the gap; V V V evaluates them at new points and characterizes excess risk (Theorem 9 ).
(iii) Estimation. The supersample construction is also how we estimate V V V from one dataset: the two copies trained on disjoint halves are the models trained on Z ~ U \widetilde{Z}_U Z U and Z ~ 1 − U \widetilde{Z}_{1-U} Z 1 − U (§ 6.3 ). The failure of overlapping folds (Remark 1) is the observation that, without this disjointness, the copies share noisy labels and the selection is no longer what distinguishes them.
(iv) Selection. Evaluated and functional CMI can be estimated from the same pairs of half-sample fits as V 2 V_2 V 2 , so the two can be compared as selection criteria at equal cost (§ 7.6 ). CMI conditions on the labels of the held-out member of each pair, so it is not label-free, and for interpolators its estimate from one pair of fits ranks candidates like 2-fold cross-validation. Min-V 2 V_2 V 2 needs no held-out labels and, among overparameterized candidates, has lower regret than every CMI criterion computed from the same fits; in a pool with rigid learners both fail, since rigid learners have a small gap and a small V V V whatever their error.
Benign overfitting and double descent. Benign overfitting has been established for minimum-norm least squares ([7 , 33 , 51 ] ), for local interpolating rules [10 ] , and classified into benign, tempered and catastrophic regimes [48 ] . Double descent was described by Belkin et al. [9 ] and analysed through bias–variance decompositions [2 , 74 , 49 ] . § 5 recovers several of these results through one quantity: the 1-NN limit of Cover and Hart [17 ] (Proposition 17 ), the variance term of Bartlett et al. [7 ] (Proposition 20 ), the taxonomy of Mallinar et al. [48 ] (§ 5.1 ), and double descent as a peak of expression. The “interpolation as a combination of a smooth component and spiky memorization” picture of Wyner et al. [72 ] and Belkin et al. [10 ] is exactly what memorize-and-smooth makes explicit (Proposition 16 ).
Bias–variance decompositions for classification. § 4.6 makes the relation exact, and Table S1 summarizes it in a full-page dictionary that maps each existing notion to its counterpart in this paper. The identity behind Theorem 9 is the excess-risk form of the 0-1 decompositions of Kohavi and Wolpert [42 ] , Domingos [23 ] and James [38 ] : Domingos’ main prediction is our modal prediction, his bias is our modal bias, his variance is the off-mode probability π D \pi_D π D , and James’ systematic and variance effects add up to our identity (2) (Proposition 14 ). Kohavi and Wolpert’s variance is half the disagreement of two copies, and all of these variances are equivalent to V V V up to the explicit bounds of Proposition 14 . What V V V adds is its reading as a mutual information with the training sample, which connects variance to storage (Theorem 5 ) and to output complexity (Proposition 11). It also gives matching upper and lower bounds for any number of classes, and its chain rule separates sample and seed contributions, as in the fine-grained decomposition of Adlam and Pennington [2 ] . For squared loss, the classical variance is a limit of V V V (Theorem 13 ); for log-loss, the variance of Heskes [35 ] is the analogous quantity (Appendix § 15 .§ 1 ).
Table S1. Correspondence between existing information, variance and disagreement notions and the quantities of this paper, at a fixed input x x x with prediction distribution q q q and modal prediction m m m . All relations are exact; the last column gives where they are proved. This table accompanies Section 4.3.
Epistemic uncertainty. In Bayesian deep learning, the mutual information between a prediction and the model parameters under the posterior measures epistemic uncertainty [20 ] . V V V is its frequentist counterpart for hard predictions: the randomness comes from the training sample rather than from a posterior. Ensembles of independently trained models, which estimate V V V , are also a common practical estimate of epistemic uncertainty.
Disagreement and agreement-based model assessment. The disagreement of two independently trained networks tracks their test error [39 ] ; agreement between models predicts accuracy under distribution shift [6 ] ; and agreement rates among several classifiers can estimate their accuracies without labels [59 ] . Proposition 15 and Table 3 explain what disagreement measures. It bounds excess risk from above and below when modal bias is absent. It equals total risk only when the predictions are distributed like a fresh label: this is the case for tempered interpolators such as 1-NN, which show the distributional generalization of Nakkiran and Bansal [52 ] , and not for benign interpolators under label noise, for which the GDE fails by exactly the Bayes risk. Seed-only disagreement, as used for the GDE, misses the sample part of V V V altogether. Proposition 21 turns disagreement-type quantities into a ranking guarantee, and the consensus criterion (§ 6.4 ) uses agreement for a different purpose, to estimate modal bias, with a guarantee that needs no independence assumption.
Learning with noisy labels and model selection. Backward loss correction with a known or estimated transition matrix gives unbiased risk estimates under class-conditional noise [53 , 57 ] , and we use it in the switch rule of § 6.4 . Our observation that correction cannot change the ranking under symmetric noise (Remark S3) explains why it helps only when noise is asymmetric. Cross-validation is the standard tool for model selection [4 ] ; our experiments show that, among overparameterized candidates, expressed information estimated from 2-fold fold models adds a label-free criterion at almost no extra cost.
Margins and the LMC papers. Nikolaou et al. [55 ] and Nikolaou [54 ] related margin maximization in boosting to lossless maximal compression; margin-based explanations of boosting go back to Schapire et al. [62 ] , and the noise sensitivity of boosting is well known [47 ] . § 3.4 and Appendix § 18 explain what in that work does and does not survive. In particular, the result that log-loss sufficiency of a binary score is equivalent to its recoverability of η \eta η (our Proposition 1) survives, now stated for the population and for stochastic representations; the claims that do not survive are the existence of a lossless maximal compressor under label noise, the inheritance of margin guarantees, and the reading of information-plane “compression” as a sign that early stopping is unnecessary.
Discussion and conclusion
Let us summarize what we have done, discuss uses of expressed information beyond the settings tested here, and then acknowledge the limitations of the framework and of the experiments, together with the steps we see for addressing them.
Summary. We started from the ideal model (§ 3 ): for any loss, the least complex optimal representation is the Bayes act, its entropy is the minimal sufficient complexity, and anything above it is excess complexity. We then separated what a learner stores from what it expresses (§ 4 ). Storage is pinned at n H ( Y ∣ X ) n H(Y \mid X) n H ( Y ∣ X ) for every interpolator, which is why storage-based bounds and training-set information measures cannot tell interpolators apart. Expression, measured by V V V , controls excess risk together with modal bias, and a consistent learner’s outputs converge to the minimal sufficient representation even while it stores all the noise. Benign overfitting is therefore vanishing expression (§ 5 ), a view that recovers classical and recent results for nearest neighbours, averaging and minimum-norm interpolation, and places double descent as a peak of expression. Finally (§ 6 and § 7 ), V V V ranks overparameterized candidates, and it gives a viable label-free selection rule: with independent samples it beats holdout validation, and on a single dataset, estimated from disjoint halves, it beats holdout and 2-fold cross-validation at the same cost and matches 5-fold cross-validation. § 4.6 relates all of this to bias–variance decompositions and to disagreement.
Selection without ground truth. Min-V V V uses the training labels to fit the candidates, but no held-out labels: it needs only unlabelled inputs from the distribution on which the model will be used. This is an advantage wherever labels for validation are scarce, costly, delayed or untrustworthy while inputs are plentiful.
Under label noise , validation labels are as noisy as the training labels (§ 6.1 ). Panel A of Table 4 shows the consequence: when the validation set shrinks from its full size to 40 points, the regret of holdout roughly triples, while min-V V V , which uses no validation labels, is unaffected.
The idea also has an unsupervised counterpart. Stability-based selection of the number of clusters fits a clustering method on two halves of the data and compares the two assignments on common points [12 , 44 , 67 , 70 ] ; min-V 2 V_2 V 2 is the same procedure applied to supervised learners. The known failure of clustering stability, that a stable but wrong solution such as too few clusters can be preferred [11 ] , is the unsupervised counterpart of modal bias, and Theorem 9 makes this failure precise for classification. What the unsupervised case lacks is an analogue of the regime in which modal bias is small, and hence an analogue of Proposition 21 ; we leave this open.
Limitations and directions for future work. The framework and the experiments have limitations. We list them below, each with the steps we see for addressing it.
From a property of the learner to a property of a trained model. V V V is defined over independent training samples, so it describes the learner, not one trained model; a single model’s excess risk over its learner’s modal prediction is controlled by V V V only in probability (Appendix § 15 .§ 2 ). A natural route to a per-model quantity is the chain rule over the parts of the sample,
V ( x ) = I ( h W ( x ) ; X n ) + I ( h W ( x ) ; Y n ∣ X n ) + I ( h W ( x ) ; ξ ∣ S ) . V(x) = I(h_W(x); X^n) + I(h_W(x); Y^n \mid X^n) + I(h_W(x); \xi\mid S). V ( x ) = I ( h W ( x ) ; X n ) + I ( h W ( x ) ; Y n ∣ X n ) + I ( h W ( x ) ; ξ ∣ S ) .
The middle term, which we would call the label-expressed information , fixes the training inputs and asks how much the prediction at x x x depends on the particular labels the model was given; it is the closest formal counterpart of “how much this model uses the training labels when it predicts at a new point”. For linear smoothers (nearest-neighbour rules, kernel ridge(less) regression, minimum-norm least squares, and forests viewed as adaptive nearest neighbours), the prediction is ∑ i w i ( x ) y i \sum_i w_i(x)y_i ∑ i w i ( x ) y i with weights that are fixed once the model is trained, and the term can be computed from the fitted model itself: Proposition 20 is exactly this computation for minimum-norm least squares, where it is a function of ∥ ( X + ) T x ∥ 2 \lVert(X^+)^\mathsf{T}x\rVert^2 ∥( X + ) T x ∥ 2 . For general models such as deep networks, the weights w i ( x ) w_i(x) w i ( x ) can be approximated by influence functions [41 ] , by linearization around the trained weights, or by datamodels [36 ] , or the term can be estimated by briefly fine-tuning the trained model on resampled labels; the per-example influence estimates of Feldman and Zhang [26 ] are a related per-model quantity. What remains to be done is to prove a conditional version of Theorem 9 given the training inputs, and to test such estimators against the learner-level V V V .
Estimating modal bias. V V V does not see modal bias, and Proposition 21 assumes it away. We argued that this is reasonable among flexible overparameterized learners and measured it to be small in our synthetic experiments, but it cannot be checked directly on real data, and it fails for underfitting candidates and under asymmetric label noise. The consensus criterion and the switch rule of § 6.4 address part of this. A next step is to estimate modal bias without a consensus, for instance from how V V V changes with the sample size, or with a small labelled set used only to screen out biased candidates.
learner-level quantities (V V V and storage) do not need this assumption, and Theorem 13 handles continuous outputs by smoothing. For regression, the storage result carries over in a stronger form, but selection by variance works only when the candidates have similar bias (Appendix § 23 ), because interpolation does not keep bias small in regression. Extending the ideal-model quantities to continuous inputs through quantization or rate–distortion, and finding a reliable bias estimate for regression, are open problems.
Rates. We give a rate of vanishing expression for k n k_n k n -NN only (Proposition 18 ). Deriving rates for kernel machines, forests and networks is a natural next step. For kernel ridge(less) regression and for networks in the lazy regime, the expressed information of minimum-norm interpolators can be computed exactly, as in Proposition 20 , which makes these the most promising cases.
Scale of the experiments. All experiments run on CPUs, on datasets of at most a few thousand points and with small networks, so whether min-V V V selects well among large deep networks is not yet tested. The disagreement results of Jiang et al. [39 ] suggest that it may, since disagreement is a function of V V V for binary labels. The next experiment is to choose among networks of different widths and training lengths on a benchmark with real label noise, such as CIFAR-10N, at a scale where the networks approach low modal bias.
Estimation from one dataset. On one dataset, V V V must be estimated from copies trained on disjoint parts of the data, which halves the training set of each copy and measures expression at half the sample size; with two copies the estimate is coarse. Averaging over several disjoint pairs already helps (§ 7.6 ). Correcting for the change of sample size, and using several independent noisy labellings where they exist, are further steps.
Statistical dependence and tuning. In Protocol B we account for the correlation between seeds of the same dataset with a cluster bootstrap, but the 15 datasets are a convenience sample of small tabular benchmarks, and in Protocol A cases from the same dataset are correlated, so those intervals are optimistic. The thresholds of the switch rule and of the clustering step were chosen on early experiments and then frozen. Validating them, and the whole comparison, on a larger and preregistered collection of datasets would strengthen the conclusions.
Conclusion. An interpolating learner memorizes all the noise in its training labels; whether it overfits benignly depends on whether that noise reaches its predictions. Expressed information measures exactly this, and it can be estimated without validation labels. It explains benign, tempered and catastrophic overfitting in one framework, and among overparameterized learners it is a practical criterion for choosing between them.
Acknowledgments
We used Claude (Anthropic; Claude Opus 5.5) to implement and run the experiments, derive certain results and edit and revise the manuscript text, tables and figures. The authors conceived and designed the study, specified the experiments, checked the code, proofs and results, and drafted the final text. They take full responsibility for the content of the submission.
Appendices (supplementary material)
These appendices form the supplementary material. Results stated only here are numbered S1, S2, … \ldots … , as are the tables, figures and equations of the appendices. They are organized as follows.
Section A states the regularity assumptions.
Sections B–E give all proofs, in the order of the main text, together with results that we only mention there (held-out estimation of excess complexity, log-loss, single trained models, stability).
Section F gives the theory of the consensus criterion and of noise correction (§ 6.4 ).
Section G is an erratum for the two earlier papers on lossless maximal compression.
Sections H and I give experimental details and additional results.
Section J extends the storage result and the selection rule to regression, with one experiment.
Section K describes the code package.
Regularity assumptions
Recall the setting of § 2 : ( X , Y ) ∼ P (X,Y)\sim P ( X , Y ) ∼ P , a loss ℓ : A × Y → [ 0 , ∞ ] \ell:\mathcal{A}\times\mathcal{Y}\to[0,\infty] ℓ : A × Y → [ 0 , ∞ ] on an action set A \mathcal{A} A , L ( a , q ) = ∑ k q k ℓ ( a , k ) L(a,q)=\sum_k q_k\ell(a,k) L ( a , q ) = ∑ k q k ℓ ( a , k ) , and L ∗ ( q ) = inf a L ( a , q ) L^*(q)=\inf_a L(a,q) L ∗ ( q ) = inf a L ( a , q ) . In § 3 we use the following two assumptions.
Assumption 1 (Regularity). A \mathcal{A} A is a compact metric space, and a ↦ ℓ ( a , k ) a\mapsto\ell(a,k) a ↦ ℓ ( a , k ) is lower semicontinuous for every k k k . Hence every L ( ⋅ , q ) L(\cdot,q) L ( ⋅ , q ) attains its infimum.
Assumption 2 (Unique Bayes act). For P X P_X P X -almost every x x x , L ( ⋅ , η ( x ) ) L(\cdot,\eta(x)) L ( ⋅ , η ( x )) has a unique minimizer, denoted a ∗ ( x ) a^*(x) a ∗ ( x ) .
Under log-loss, A = Δ K \mathcal{A}=\Delta_K A = Δ K and L ( q , η ) = H ( η ) + KL ( η ∥ q ) L(q,\eta)=H(\eta)+\operatorname{KL}(\eta\mathbin{\|}q) L ( q , η ) = H ( η ) + KL ( η ∥ q ) , so both assumptions hold (with the convention − log 0 = ∞ -\log0=\infty − log 0 = ∞ ), with a ∗ = η a^*=\eta a ∗ = η and R log ( T ) = H ( Y ∣ T ) R_{\log}(T)=H(Y\mid T) R l o g ( T ) = H ( Y ∣ T ) . Under 0-1 loss, A = [ K ] \mathcal{A}=[K] A = [ K ] , a ∗ = b ∗ a^*=b^* a ∗ = b ∗ , and Assumption 2 means that there are no ties, i.e. γ ( x ) > 0 \gamma(x)>0 γ ( x ) > 0 almost surely. A representation T T T has countable range and satisfies the Markov chain Y − X − T Y-X-T Y − X − T .
Proofs for main Section 3
Lemma S1 (Recalibrated risk). Let η T ( t ) = P ( Y = ⋅ ∣ T = t ) \eta_T(t)=P(Y=\cdot\mid T=t) η T ( t ) = P ( Y = ⋅ ∣ T = t ) . Then R ℓ ( T ) = ∑ t P ( T = t ) L ∗ ( η T ( t ) ) R_\ell(T)=\sum_tP(T=t)L^*(\eta_T(t)) R ℓ ( T ) = ∑ t P ( T = t ) L ∗ ( η T ( t )) , the infimum is attained by any g ∗ ( t ) ∈ arg min a L ( a , η T ( t ) ) g^*(t)\in\arg\min_aL(a,\eta_T(t)) g ∗ ( t ) ∈ arg min a L ( a , η T ( t )) , and R ℓ ( T ) ≥ R ℓ ∗ R_\ell(T)\ge R^*_\ell R ℓ ( T ) ≥ R ℓ ∗ .
Proof. By Y − X − T Y-X-T Y − X − T , E [ ℓ ( g ( T ) , Y ) ∣ X , T ] = L ( g ( T ) , η ( X ) ) \mathbb{E}[\ell(g(T),Y)\mid X,T]=L(g(T),\eta(X)) E [ ℓ ( g ( T ) , Y ) ∣ X , T ] = L ( g ( T ) , η ( X )) , and E [ ℓ ( g ( T ) , Y ) ∣ T = t ] = L ( g ( t ) , η T ( t ) ) \mathbb{E}[\ell(g(T),Y)\mid T=t]=L(g(t),\eta_T(t)) E [ ℓ ( g ( T ) , Y ) ∣ T = t ] = L ( g ( t ) , η T ( t )) . Minimizing pointwise in t t t gives the formula; minimizers exist by Assumption 1. For the inequality, E ℓ ( g ∗ ( T ) , Y ) = E L ( g ∗ ( T ) , η ( X ) ) ≥ E L ∗ ( η ( X ) ) = R ℓ ∗ \mathbb{E}\ell(g^*(T),Y)=\mathbb{E}L(g^*(T),\eta(X))\ge\mathbb{E}L^*(\eta(X))=R^*_\ell E ℓ ( g ∗ ( T ) , Y ) = E L ( g ∗ ( T ) , η ( X )) ≥ E L ∗ ( η ( X )) = R ℓ ∗ . □
Proof of Proposition 1. ( ⇐ ) (\Leftarrow) ( ⇐ ) If a ∗ ( X ) = g ( T ) a^*(X)=g(T) a ∗ ( X ) = g ( T ) , then E ℓ ( g ( T ) , Y ) = E L ( a ∗ ( X ) , η ( X ) ) = R ℓ ∗ \mathbb{E}\ell(g(T),Y)=\mathbb{E}L(a^*(X),\eta(X))=R^*_\ell E ℓ ( g ( T ) , Y ) = E L ( a ∗ ( X ) , η ( X )) = R ℓ ∗ . ( ⇒ ) (\Rightarrow) ( ⇒ ) Take g ∗ g^* g ∗ from Lemma S1. Then 0 = R ℓ ( T ) − R ℓ ∗ = E [ L ( g ∗ ( T ) , η ( X ) ) − L ∗ ( η ( X ) ) ] 0=R_\ell(T)-R^*_\ell=\mathbb{E}[L(g^*(T),\eta(X))-L^*(\eta(X))] 0 = R ℓ ( T ) − R ℓ ∗ = E [ L ( g ∗ ( T ) , η ( X )) − L ∗ ( η ( X ))] , with a non-negative integrand, so g ∗ ( T ) g^*(T) g ∗ ( T ) minimizes L ( ⋅ , η ( X ) ) L(\cdot,\eta(X)) L ( ⋅ , η ( X )) almost surely. By Assumption 2, g ∗ ( T ) = a ∗ ( X ) g^*(T)=a^*(X) g ∗ ( T ) = a ∗ ( X ) almost surely. Under log-loss, R log ( T ) = H ( Y ∣ T ) ≥ H ( Y ∣ X ) = R log ∗ R_{\log}(T)=H(Y\mid T)\ge H(Y\mid X)=R^*_{\log} R l o g ( T ) = H ( Y ∣ T ) ≥ H ( Y ∣ X ) = R l o g ∗ , with equality iff I ( T ; Y ) = I ( X ; Y ) I(T;Y)=I(X;Y) I ( T ; Y ) = I ( X ; Y ) ; apply the first part with a ∗ = η a^*=\eta a ∗ = η . For K = 2 K=2 K = 2 this is Lemma 3 of Nikolau et al. (2020), here stated for the population and for stochastic T T T . □
Proof of Theorem 2. Since a ∗ ( X ) a^{*}(X) a ∗ ( X ) is a function of X X X , we have T − X − a ∗ ( X ) T-X-a^{*}(X) T − X − a ∗ ( X ) , and the data-processing inequality gives I ( T ; X ) ≥ I ( T ; a ∗ ( X ) ) = H ( a ∗ ( X ) ) − H ( a ∗ ( X ) ∣ T ) = H ( a ∗ ( X ) ) I(T;X) \ge I(T;a^{*}(X)) = H(a^{*}(X))-H(a^{*}(X)\mid T) = H(a^{*}(X)) I ( T ; X ) ≥ I ( T ; a ∗ ( X )) = H ( a ∗ ( X )) − H ( a ∗ ( X ) ∣ T ) = H ( a ∗ ( X )) , where the last step uses Proposition 1 (a ∗ ( X ) a^{*}(X) a ∗ ( X ) is a function of T T T ). Equality in data processing holds iff I ( T ; X ∣ a ∗ ( X ) ) = 0 I(T;X\mid a^{*}(X))=0 I ( T ; X ∣ a ∗ ( X )) = 0 , i.e. iff T − a ∗ ( X ) − X T-a^{*}(X)-X T − a ∗ ( X ) − X . For deterministic F F F : H ( F ) = H ( F , a ∗ ( X ) ) = H ( a ∗ ( X ) ) + H ( F ∣ a ∗ ( X ) ) H(F)=H(F,a^{*}(X))=H(a^{*}(X))+H(F\mid a^{*}(X)) H ( F ) = H ( F , a ∗ ( X )) = H ( a ∗ ( X )) + H ( F ∣ a ∗ ( X )) , which equals H ( a ∗ ( X ) ) H(a^{*}(X)) H ( a ∗ ( X )) iff F F F is a function of a ∗ ( X ) a^{*}(X) a ∗ ( X ) ; since a ∗ ( X ) a^{*}(X) a ∗ ( X ) is also a function of F F F , the two are in bijection on their supports. Finally, T = a ∗ ( X ) T=a^{*}(X) T = a ∗ ( X ) is sufficient with I ( T ; X ) = C ℓ ∗ I(T;X)=C_{\ell}^{*} I ( T ; X ) = C ℓ ∗ , so R ℓ ( R ℓ ∗ ) = C ℓ ∗ R_{\ell}(R_{\ell}^{*})=C_{\ell}^{*} R ℓ ( R ℓ ∗ ) = C ℓ ∗ .
Proof of Proposition 3. If F F F is sufficient then R ℓ ( F ) = R ℓ ∗ R_{\ell}(F)=R_{\ell}^{*} R ℓ ( F ) = R ℓ ∗ and R ℓ ( R ℓ ∗ ) = C ℓ ∗ R_{\ell}(R_{\ell}^{*})=C_{\ell}^{*} R ℓ ( R ℓ ∗ ) = C ℓ ∗ , so E ℓ ( F ) = H ( F ) − H ( a ∗ ( X ) ) = H ( F ∣ a ∗ ( X ) ) E_{\ell}(F)=H(F)-H(a^{*}(X))=H(F\mid a^{*}(X)) E ℓ ( F ) = H ( F ) − H ( a ∗ ( X )) = H ( F ∣ a ∗ ( X )) by the proof of Theorem 2. Under log-loss a ∗ = η a^{*}=\eta a ∗ = η and η ( X ) = g ( F ) \eta(X)=g(F) η ( X ) = g ( F ) , so H ( F ∣ Y ) = H ( F , η ( X ) ∣ Y ) = H ( η ( X ) ∣ Y ) + H ( F ∣ η ( X ) , Y ) H(F\mid Y)=H(F,\eta(X)\mid Y)=H(\eta(X)\mid Y)+H(F\mid\eta(X),Y) H ( F ∣ Y ) = H ( F , η ( X ) ∣ Y ) = H ( η ( X ) ∣ Y ) + H ( F ∣ η ( X ) , Y ) . Since P ( Y ∣ X ) = η ( X ) = P ( Y ∣ η ( X ) ) \mathbb{P}(Y\mid X)=\eta(X)=\mathbb{P}(Y\mid\eta(X)) P ( Y ∣ X ) = η ( X ) = P ( Y ∣ η ( X )) , we have Y ⊥ X ∣ η ( X ) Y\perp X\mid\eta(X) Y ⊥ X ∣ η ( X ) , hence Y ⊥ F ∣ η ( X ) Y\perp F\mid\eta(X) Y ⊥ F ∣ η ( X ) , so H ( F ∣ η ( X ) , Y ) = H ( F ∣ η ( X ) ) = E log ( F ) H(F\mid\eta(X),Y)=H(F\mid\eta(X))=E_{\log}(F) H ( F ∣ η ( X ) , Y ) = H ( F ∣ η ( X )) = E l o g ( F ) .
Held-out estimation of excess complexity
The log-loss identity of Proposition 3 suggests estimating excess complexity by H ( F ∣ Y ) H(F\mid Y) H ( F ∣ Y ) on held-out data (minus the task constant H ( η ( X ) ∣ Y ) H(\eta(X)\mid Y) H ( η ( X ) ∣ Y ) ). For non-sufficient outputs this is only a lower bound.
Proposition S2 (The held-out estimator is a lower bound). For any representation T T T with Y − X − T Y-X-T Y − X − T , under log-loss,
H ( T ∣ Y ) − H ( η ( X ) ∣ Y ) = H ( T ∣ η ( X ) ) − H ( η ( X ) ∣ T , Y ) ≤ H ( T ∣ η ( X ) ) , H(T\mid Y)-H(\eta(X)\mid Y)=H(T\mid\eta(X))-H(\eta(X)\mid T,Y)\le H(T\mid\eta(X)), H ( T ∣ Y ) − H ( η ( X ) ∣ Y ) = H ( T ∣ η ( X )) − H ( η ( X ) ∣ T , Y ) ≤ H ( T ∣ η ( X )) , with equality iff η ( X ) \eta(X) η ( X ) is a function of ( T , Y ) (T,Y) ( T , Y ) ; in particular for every sufficient T T T .
Proof. H ( T ∣ Y ) = H ( T , η ( X ) ∣ Y ) − H ( η ( X ) ∣ T , Y ) = H ( η ( X ) ∣ Y ) + H ( T ∣ η ( X ) , Y ) − H ( η ( X ) ∣ T , Y ) H(T\mid Y)=H(T,\eta(X)\mid Y)-H(\eta(X)\mid T,Y)=H(\eta(X)\mid Y)+H(T\mid\eta(X),Y)-H(\eta(X)\mid T,Y) H ( T ∣ Y ) = H ( T , η ( X ) ∣ Y ) − H ( η ( X ) ∣ T , Y ) = H ( η ( X ) ∣ Y ) + H ( T ∣ η ( X ) , Y ) − H ( η ( X ) ∣ T , Y ) , and H ( T ∣ η ( X ) , Y ) = H ( T ∣ η ( X ) ) H(T\mid\eta(X),Y)=H(T\mid\eta(X)) H ( T ∣ η ( X ) , Y ) = H ( T ∣ η ( X )) because Y ⊥ T ∣ η ( X ) Y\perp T\mid\eta(X) Y ⊥ T ∣ η ( X ) .
This is why, in § 7.1 , the held-out estimator ranks learners reasonably (Spearman 0.85) but underestimates by 0.35 bits on average: most trained outputs there are not log-loss sufficient. The task constant is strictly positive under label noise:
Lemma S3 (Irreducible noise complexity). For deterministic F F F , I ( F ; X ) = I ( F ; Y ) + I ( F ; X ∣ Y ) I(F;X)=I(F;Y)+I(F;X\mid Y) I ( F ; X ) = I ( F ; Y ) + I ( F ; X ∣ Y ) . If F F F is log-loss sufficient then I ( F ; X ∣ Y ) = H ( F ∣ Y ) ≥ H ( η ( X ) ∣ Y ) I(F;X\mid Y)=H(F\mid Y)\ge H(\eta(X)\mid Y) I ( F ; X ∣ Y ) = H ( F ∣ Y ) ≥ H ( η ( X ) ∣ Y ) . If K = 2 K=2 K = 2 , I ( X ; Y ) > 0 I(X;Y)>0 I ( X ; Y ) > 0 and H ( Y ∣ X ) > 0 H(Y\mid X)>0 H ( Y ∣ X ) > 0 , then H ( η ( X ) ∣ Y ) > 0 H(\eta(X)\mid Y)>0 H ( η ( X ) ∣ Y ) > 0 .
Proof. I ( F ; X ) = I ( F ; X , Y ) I(F;X)=I(F;X,Y) I ( F ; X ) = I ( F ; X , Y ) because I ( F ; Y ∣ X ) = 0 I(F;Y\mid X)=0 I ( F ; Y ∣ X ) = 0 ; then apply the chain rule. The inequality follows from Proposition 3. For the last claim, let η 1 = P ( Y = 1 ∣ X ) \eta_{1}=\mathbb{P}(Y=1\mid X) η 1 = P ( Y = 1 ∣ X ) . Since I ( X ; Y ) > 0 I(X;Y)>0 I ( X ; Y ) > 0 , η 1 ( X ) \eta_{1}(X) η 1 ( X ) takes at least two values p ≠ q p\ne q p = q , and since H ( Y ∣ X ) > 0 H(Y\mid X)>0 H ( Y ∣ X ) > 0 we may take p ∈ ( 0 , 1 ) p\in(0,1) p ∈ ( 0 , 1 ) . If q ∈ ( 0 , 1 ) q\in(0,1) q ∈ ( 0 , 1 ) , both labels occur under both values. If q = 0 q=0 q = 0 , label 0 occurs under both; if q = 1 q=1 q = 1 , label 1 does. Either way, some y y y has P ( η 1 ( X ) = p ∣ Y = y ) ∈ ( 0 , 1 ) \mathbb{P}(\eta_{1}(X)=p\mid Y=y)\in(0,1) P ( η 1 ( X ) = p ∣ Y = y ) ∈ ( 0 , 1 ) , so H ( η ( X ) ∣ Y ) > 0 H(\eta(X)\mid Y)>0 H ( η ( X ) ∣ Y ) > 0 .
So a log-loss sufficient model must retain at least H ( η ( X ) ∣ Y ) > 0 H(\eta(X)\mid Y)>0 H ( η ( X ) ∣ Y ) > 0 bits about its input beyond what the label explains. This is another way to see why the original LMC condition I ( F ; X ) = I ( F ; Y ) I(F;X)=I(F;Y) I ( F ; X ) = I ( F ; Y ) cannot hold under noise.
The original LMC
Proof of Proposition 4. Let C G K ( X ; Y ) = max { H ( G ) : G = g 1 ( X ) = g 2 ( Y ) a . s . } C_{GK}(X;Y)=\max\{H(G):G=g_1(X)=g_2(Y)\ \mathrm{a.s.}\} C G K ( X ; Y ) = max { H ( G ) : G = g 1 ( X ) = g 2 ( Y ) a.s. } . Always C G K ≤ I ( X ; Y ) C_{GK}\le I(X;Y) C G K ≤ I ( X ; Y ) : if G = g 1 ( X ) = g 2 ( Y ) G=g_1(X)=g_2(Y) G = g 1 ( X ) = g 2 ( Y ) then I ( X ; Y ) ≥ I ( G ; Y ) ≥ I ( G ; G ) = H ( G ) I(X;Y)\ge I(G;Y)\ge I(G;G)=H(G) I ( X ; Y ) ≥ I ( G ; Y ) ≥ I ( G ; G ) = H ( G ) . ( ⇒ ) (\Rightarrow) ( ⇒ ) I ( F ; Y ) = H ( F ) − H ( F ∣ Y ) I(F;Y)=H(F)-H(F\mid Y) I ( F ; Y ) = H ( F ) − H ( F ∣ Y ) and I ( F ; X ) = H ( F ) I(F;X)=H(F) I ( F ; X ) = H ( F ) , so I ( F ; X ) = I ( F ; Y ) I(F;X)=I(F;Y) I ( F ; X ) = I ( F ; Y ) forces H ( F ∣ Y ) = 0 H(F\mid Y)=0 H ( F ∣ Y ) = 0 , i.e. F = g 2 ( Y ) F=g_2(Y) F = g 2 ( Y ) a.s. Thus F F F is common to X X X and Y Y Y , and I ( X ; Y ) = H ( F ) ≤ C G K I(X;Y)=H(F)\le C_{GK} I ( X ; Y ) = H ( F ) ≤ C G K . ( ⇐ ) (\Leftarrow) ( ⇐ ) Take G G G attaining C G K C_{GK} C G K and F = g 1 ( X ) F=g_1(X) F = g 1 ( X ) ; then I ( F ; X ) = H ( G ) = I ( F ; Y ) = C G K = I ( X ; Y ) I(F;X)=H(G)=I(F;Y)=C_{GK}=I(X;Y) I ( F ; X ) = H ( G ) = I ( F ; Y ) = C G K = I ( X ; Y ) . For K = 2 K=2 K = 2 , g 2 ( Y ) g_2(Y) g 2 ( Y ) is either constant (H ( G ) = 0 H(G)=0 H ( G ) = 0 ) or a bijection of Y Y Y (H ( G ) = H ( Y ) H(G)=H(Y) H ( G ) = H ( Y ) ). So C G K = I ( X ; Y ) C_{GK}=I(X;Y) C G K = I ( X ; Y ) forces I ( X ; Y ) = 0 I(X;Y)=0 I ( X ; Y ) = 0 or I ( X ; Y ) = H ( Y ) I(X;Y)=H(Y) I ( X ; Y ) = H ( Y ) , i.e. H ( Y ∣ X ) = 0 H(Y\mid X)=0 H ( Y ∣ X ) = 0 .
Remark S1 (Empirical degeneracy). If all n n n training inputs are distinct, the empirical distribution has H S ( Y ∣ X ) = 0 H_S(Y\mid X)=0 H S ( Y ∣ X ) = 0 and I S ( X ; Y ) = H S ( Y ) I_S(X;Y)=H_S(Y) I S ( X ; Y ) = H S ( Y ) . Any interpolating hard classifier h h h then has h ( X i ) = Y i h(X_i)=Y_i h ( X i ) = Y i for all i i i , so I S ( h ( X ) ; Y ) = H S ( Y ) = I S ( X ; Y ) I_S(h(X);Y)=H_S(Y)=I_S(X;Y) I S ( h ( X ) ; Y ) = H S ( Y ) = I S ( X ; Y ) and I S ( h ( X ) ; X ) = H S ( h ( X ) ) = H S ( Y ) I_S(h(X);X)=H_S(h(X))=H_S(Y) I S ( h ( X ) ; X ) = H S ( h ( X )) = H S ( Y ) : it is an empirical LMC, whatever its test behaviour (1-NN included). The legacy score I S ( F ; Y ) / H S ( Y ) I_S(F;Y)/H_S(Y) I S ( F ; Y ) / H S ( Y ) of Nikolaou et al. [55 ] equals 1 for every exact interpolator. In Table 1 it is 0.99 rather than 1 because of duplicate training inputs. With n = 4096 n=4096 n = 4096 draws from 2 19 2^{19} 2 19 inputs, about ( 4096 2 ) 2 − 19 ≈ 16 \binom{4096}{2}2^{-19}\approx16 ( 2 4096 ) 2 − 19 ≈ 16 pairs of training inputs coincide. Where the two labels of a pair conflict, no classifier can fit both, which leaves about 4.6 unavoidable training errors (training error 0.0011). The score is computed from hard predictions without binning. With training error e e e , it is close to 1 − h ( e ) = 1 − h ( 0.0011 ) = 0.987 1-h(e)=1-h(0.0011)=0.987 1 − h ( e ) = 1 − h ( 0.0011 ) = 0.987 , which matches the measured 0.988–0.989.
Proofs for main Section 4
Proof of Theorem 5. I ( W ; Y n ∣ X n ) = H ( Y n ∣ X n ) − H ( Y n ∣ X n , W ) I(W;Y^n\mid X^n)=H(Y^n\mid X^n)-H(Y^n\mid X^n,W) I ( W ; Y n ∣ X n ) = H ( Y n ∣ X n ) − H ( Y n ∣ X n , W ) . Given X n X^n X n the labels are independent with laws η ( X i ) \eta(X_i) η ( X i ) , so H ( Y n ∣ X n ) = n H ( Y ∣ X ) H(Y^n\mid X^n)=nH(Y\mid X) H ( Y n ∣ X n ) = n H ( Y ∣ X ) . By subadditivity and since conditioning reduces entropy,
H ( Y n ∣ X n , W ) ≤ ∑ i H ( Y i ∣ X i , W ) ≤ ∑ i H ( Y i ∣ h W ( X i ) ) ≤ ∑ i ϕ K ( p i ) , H(Y^n\mid X^n,W)\le\sum_i H(Y_i\mid X_i,W)\le\sum_i H(Y_i\mid h_W(X_i))\le\sum_i\phi_K(p_i), H ( Y n ∣ X n , W ) ≤ i ∑ H ( Y i ∣ X i , W ) ≤ i ∑ H ( Y i ∣ h W ( X i )) ≤ i ∑ ϕ K ( p i ) ,
with p i = P ( h W ( X i ) ≠ Y i ) p_i=\mathbb{P}(h_W(X_i)\ne Y_i) p i = P ( h W ( X i ) = Y i ) , by Fano’s inequality. ϕ K \phi_K ϕ K is concave, so 1 n ∑ i ϕ K ( p i ) ≤ ϕ K ( ϵ ˉ ) \frac{1}{n}\sum_i\phi_K(p_i)\le\phi_K(\bar{\epsilon}) n 1 ∑ i ϕ K ( p i ) ≤ ϕ K ( ϵ ˉ ) . If ϵ ^ = 0 \hat{\epsilon}=0 ϵ ^ = 0 a.s., then Y n = h W ( X n ) Y^n=h_W(X^n) Y n = h W ( X n ) is a function of ( X n , W ) (X^n,W) ( X n , W ) and H ( Y n ∣ X n , W ) = 0 H(Y^n\mid X^n,W)=0 H ( Y n ∣ X n , W ) = 0 . Finally, I ( W ; S ) = I ( W ; X n ) + I ( W ; Y n ∣ X n ) ≥ I ( W ; Y n ∣ X n ) I(W;S)=I(W;X^n)+I(W;Y^n\mid X^n)\ge I(W;Y^n\mid X^n) I ( W ; S ) = I ( W ; X n ) + I ( W ; Y n ∣ X n ) ≥ I ( W ; Y n ∣ X n ) .
Remark S2 (Stored task versus stored noise). Place a prior on the task: a random θ \theta θ indexes P θ P_\theta P θ , with S ∣ θ ∼ P θ S\mid\theta\sim P_\theta S ∣ θ ∼ P θ , so that θ − S − W \theta-S-W θ − S − W . The chain rule gives I ( W ; Y n ∣ X n ) = I ( W ; θ ∣ X n ) + I ( W ; Y n ∣ X n , θ ) I(W;Y^n\mid X^n)=I(W;\theta\mid X^n)+I(W;Y^n\mid X^n,\theta) I ( W ; Y n ∣ X n ) = I ( W ; θ ∣ X n ) + I ( W ; Y n ∣ X n , θ ) , because I ( W ; θ ∣ S ) = 0 I(W;\theta\mid S)=0 I ( W ; θ ∣ S ) = 0 . The first term is stored information about the task, and the second is stored noise. For an interpolator the second term equals n H ( Y ∣ X , θ ) nH(Y\mid X,\theta) n H ( Y ∣ X , θ ) exactly, by Theorem 5 applied conditionally on θ \theta θ .
Proof of Corollary 6. By Theorem 5, I ( W ; S ) ≥ n H ( Y ∣ X ) I(W;S)\ge nH(Y\mid X) I ( W ; S ) ≥ n H ( Y ∣ X ) for every interpolator, so 2 σ 2 I ( W ; S ) / n ≥ 2 σ 2 H ( Y ∣ X ) \sqrt{2\sigma^2I(W;S)/n}\ge\sqrt{2\sigma^2H(Y\mid X)} 2 σ 2 I ( W ; S ) / n ≥ 2 σ 2 H ( Y ∣ X ) for all n n n .
Proof of Corollary 7. For losses in [ 0 , 1 ] [0,1] [ 0 , 1 ] , Theorem 2 of Steinke and Zakynthinou [65 ] gives ∣ E [ R ( h W ) − R ^ S ( h W ) ] ∣ ≤ 2 C M I / n \lvert\mathbb{E}[R(h_W)-\widehat{R}_S(h_W)]\rvert\le\sqrt{2\,\mathrm{CMI}/n} ∣ E [ R ( h W ) − R S ( h W )]∣ ≤ 2 CMI / n (CMI in nats). An interpolator has R ^ S ( h W ) = 0 \widehat{R}_S(h_W)=0 R S ( h W ) = 0 almost surely, so E R ( h W ) ≤ 2 C M I / n \mathbb{E}R(h_W)\le\sqrt{2\,\mathrm{CMI}/n} E R ( h W ) ≤ 2 CMI / n , i.e. C M I ≥ n 2 ( E R ( h W ) ) 2 \mathrm{CMI}\ge\frac{n}{2}(\mathbb{E}R(h_W))^2 CMI ≥ 2 n ( E R ( h W ) ) 2 , and E R ( h W ) ≥ R ∗ \mathbb{E}R(h_W)\ge R^* E R ( h W ) ≥ R ∗ . In the running example, R ∗ = 0.15 R^*=0.15 R ∗ = 0.15 gives C M I ≥ 0.0113 n \mathrm{CMI}\ge0.0113\,n CMI ≥ 0.0113 n nats.
Proofs for main Section 4.3 and related results
Lemma S4 (Entropy and mass off the mode; cf. Feder and Merhav, [24 ] ). For any probability vector q q q on K K K points with largest atom q max q_{\max} q m a x ,
ϕ K − 1 ( H ( q ) ) ≤ 1 − q max ≤ 1 2 H ( q ) , \phi_K^{-1}(H(q)) \le1-q_{\max} \le\frac{1}{2}H(q), ϕ K − 1 ( H ( q )) ≤ 1 − q m a x ≤ 2 1 H ( q ) ,
where ϕ K − 1 \phi_K^{-1} ϕ K − 1 is the inverse of ϕ K ( e ) = h ( e ) + e log 2 ( K − 1 ) \phi_K(e)=h(e)+e\log_2(K-1) ϕ K ( e ) = h ( e ) + e log 2 ( K − 1 ) on [ 0 , 1 − 1 / K ] [0,1-1/K] [ 0 , 1 − 1/ K ] and H H H is in bits.
Proof. Lower bound: apply Fano’s inequality to the estimator that always outputs the mode, whose error probability is 1 − q max ≤ 1 − 1 / K 1-q_{\max}\le1-1/K 1 − q m a x ≤ 1 − 1/ K . Upper bound: let p = q max p=q_{\max} p = q m a x . If p ≥ 1 2 p\ge\frac{1}{2} p ≥ 2 1 , the grouping property gives H ( q ) = h ( p ) + ( 1 − p ) H ( q ~ ) ≥ h ( p ) H(q)=h(p)+(1-p)H(\widetilde q)\ge h(p) H ( q ) = h ( p ) + ( 1 − p ) H ( q ) ≥ h ( p ) , and h ( p ) ≥ 2 ( 1 − p ) h(p)\ge2(1-p) h ( p ) ≥ 2 ( 1 − p ) on [ 1 2 , 1 ] [\frac{1}{2},1] [ 2 1 , 1 ] by concavity of h h h (the chord from ( 1 2 , 1 ) (\frac{1}{2},1) ( 2 1 , 1 ) to ( 1 , 0 ) (1,0) ( 1 , 0 ) ). If p < 1 2 p<\frac{1}{2} p < 2 1 , H ( q ) ≥ − log 2 p H(q)\ge-\log_2p H ( q ) ≥ − log 2 p (min-entropy), and g ( p ) = − log 2 p − 2 ( 1 − p ) g(p)=-\log_2p-2(1-p) g ( p ) = − log 2 p − 2 ( 1 − p ) satisfies g ( 1 2 ) = 0 g(\frac{1}{2})=0 g ( 2 1 ) = 0 and g ′ ( p ) = 2 − 1 p ln 2 < 0 g'(p)=2-\frac{1}{p\ln2}<0 g ′ ( p ) = 2 − p l n 2 1 < 0 on ( 0 , 1 2 ] (0,\frac{1}{2}] ( 0 , 2 1 ] , so g ≥ 0 g\ge0 g ≥ 0 there. □
Proof of Proposition 8. h W ( x ) h_W(x) h W ( x ) is a function of ( S , ξ ) (S,\xi) ( S , ξ ) , and ( S , ξ ) (S,\xi) ( S , ξ ) is a function of ( Z ~ , U , ξ ~ ) (\widetilde Z,U,\widetilde\xi) ( Z , U , ξ ) , so H ( h W ( x ) ∣ S , ξ ) = H ( h W ( x ) ∣ Z ~ , U , ξ ~ ) = 0 H(h_W(x)\mid S,\xi)=H(h_W(x)\mid\widetilde Z,U,\widetilde\xi)=0 H ( h W ( x ) ∣ S , ξ ) = H ( h W ( x ) ∣ Z , U , ξ ) = 0 and V ( x ) = H ( h W ( x ) ) = I ( h W ( x ) ; Z ~ , U , ξ ~ ) V(x)=H(h_W(x))=I(h_W(x);\widetilde Z,U,\widetilde\xi) V ( x ) = H ( h W ( x )) = I ( h W ( x ) ; Z , U , ξ ) . The chain rule gives I ( h W ( x ) ; Z ~ , U , ξ ~ ) = I ( h W ( x ) ; Z ~ ) + I ( h W ( x ) ; U ∣ Z ~ ) + I ( h W ( x ) ; ξ ∣ Z , U ~ ) I(h_W(x);\widetilde Z,U,\widetilde\xi)=I(h_W(x);\widetilde Z)+I(h_W(x);U\mid\widetilde Z)+I(h_W(x);\xi\mid Z,\widetilde U) I ( h W ( x ) ; Z , U , ξ ) = I ( h W ( x ) ; Z ) + I ( h W ( x ) ; U ∣ Z ) + I ( h W ( x ) ; ξ ∣ Z , U ) . If the two halves Z ~ U \widetilde Z_U Z U and Z ~ 1 − U \widetilde Z_{1-U} Z 1 − U are used to train two copies, then, since the 2 n 2n 2 n examples are i.i.d., the two training samples are independent samples of size n n n ; this is why the two-halves estimator of § 6.3 estimates E V EV E V for training size n / 2 n/2 n /2 when applied to a dataset of size n n n . □
Proof of Theorem 9 . For any classifier c c c , R ( c ) − R ∗ = E [ η b ∗ ( X ) − η c ( X ) ( X ) ] R(c)-R^*=\mathbb{E}[\eta_{b^*}(X)-\eta_{c(X)}(X)] R ( c ) − R ∗ = E [ η b ∗ ( X ) − η c ( X ) ( X )] . Averaging over ( S , ξ ) (S,\xi) ( S , ξ ) , which is independent of the test point, gives the identity
E R ( h W ) − R ∗ = E [ ∑ k q ( k ∣ X ) ( η b ∗ ( X ) − η k ( X ) ) ] . (4) \mathbb{E}\,R(h_W)-R^*=\mathbb{E}\left[\sum_k q(k\mid X)(\eta_{b^*}(X)-\eta_k(X))\right]. \tag*{(4)} E R ( h W ) − R ∗ = E [ k ∑ q ( k ∣ X ) ( η b ∗ ( X ) − η k ( X )) ] . (4)
At fixed x x x , the inner sum lies in [ γ ( x ) ( 1 − q b ∗ ) , Δ ( x ) ( 1 − q b ∗ ) ] [\gamma(x)(1-q_{b^*}),\Delta(x)(1-q_{b^*})] [ γ ( x ) ( 1 − q b ∗ ) , Δ ( x ) ( 1 − q b ∗ )] . If m = b ∗ m=b^* m = b ∗ , then 1 − q b ∗ = 1 − q max 1-q_{b^*}=1-q_{\max} 1 − q b ∗ = 1 − q m a x , and Lemma S4 gives both bounds. If m ≠ b ∗ m\ne b^* m = b ∗ , then q b ∗ ≤ q m q_{b^*}\le q_m q b ∗ ≤ q m and q b ∗ + q m ≤ 1 q_{b^*}+q_m\le1 q b ∗ + q m ≤ 1 give 1 2 ≤ 1 − q b ∗ ≤ 1 \frac{1}{2}\le1-q_{b^*}\le1 2 1 ≤ 1 − q b ∗ ≤ 1 . For K = 2 K=2 K = 2 , Δ = γ = ∣ 2 η 1 − 1 ∣ \Delta=\gamma=|2\eta_1-1| Δ = γ = ∣2 η 1 − 1∣ ; the two-point law has 1 − q max = π = h − 1 ( V ) 1-q_{\max}=\pi=h^{-1}(V) 1 − q m a x = π = h − 1 ( V ) , and 1 − q b ∗ 1-q_{b^*} 1 − q b ∗ equals π \pi π or 1 − π 1-\pi 1 − π according to whether m = b ∗ m=b^* m = b ∗ . □
Proof of Corollary 10. ( ⇐ ) (\Leftarrow) ( ⇐ ) Use the upper bound of Theorem 9 with Δ ≤ 1 \Delta\le1 Δ ≤ 1 . ( ⇒ ) (\Rightarrow) ( ⇒ ) Let Z n = ϕ K − 1 ( V n ) 1 { m n = b ∗ } + 1 2 1 { m n ≠ b ∗ } ∈ [ 0 , 1 ] Z_n=\phi_K^{-1}(V_n)1\{m_n=b^*\}+\frac{1}{2}1\{m_n\ne b^*\}\in[0,1] Z n = ϕ K − 1 ( V n ) 1 { m n = b ∗ } + 2 1 1 { m n = b ∗ } ∈ [ 0 , 1 ] . The lower bound gives E [ γ Z n ] → 0 \mathbb{E}[\gamma Z_n]\to0 E [ γ Z n ] → 0 . For δ , τ > 0 \delta,\tau>0 δ , τ > 0 ,
P ( Z n > δ ) ≤ P ( γ < τ ) + E [ γ Z n ] τ δ ; \mathbb{P}(Z_n>\delta)\le\mathbb{P}(\gamma<\tau)+\frac{\mathbb{E}[\gamma Z_n]}{\tau\delta}; P ( Z n > δ ) ≤ P ( γ < τ ) + τ δ E [ γ Z n ] ;
letting n → ∞ n\to\infty n → ∞ and then τ → 0 \tau\to0 τ → 0 shows Z n → 0 Z_n\to0 Z n → 0 in probability. Hence P ( m n ≠ b ∗ ) → 0 \mathbb{P}(m_n\ne b^*)\to0 P ( m n = b ∗ ) → 0 , and ϕ K − 1 ( V n ) → 0 \phi_K^{-1}(V_n)\to0 ϕ K − 1 ( V n ) → 0 in probability; since ϕ K \phi_K ϕ K is continuous with ϕ K ( 0 ) = 0 \phi_K(0)=0 ϕ K ( 0 ) = 0 , so does V n V_n V n . As V n ≤ log 2 K V_n\le\log_2K V n ≤ log 2 K , bounded convergence gives E V n → 0 \mathbb{E}V_n\to0 E V n → 0 . □
Proof of Corollary 12. Let F n = h W n ( X ′ ) F_n=h_{W_n}(X') F n = h W n ( X ′ ) and p n = P ( F n ≠ b ∗ ( X ′ ) ) p_n=\mathbb{P}(F_n\ne b^*(X')) p n = P ( F n = b ∗ ( X ′ )) . Since R ( c ) − R ∗ = E [ η b ∗ − η c ] ≥ E [ γ 1 { c ≠ b ∗ } ] R(c)-R^*=\mathbb{E}[\eta_{b^*}-\eta_c]\ge\mathbb{E}[\gamma1\{c\ne b^*\}] R ( c ) − R ∗ = E [ η b ∗ − η c ] ≥ E [ γ 1 { c = b ∗ }] , we have E [ γ 1 { F n ≠ b ∗ } ] ≤ E R ( h W n ) − R ∗ → 0 \mathbb{E}[\gamma1\{F_n\ne b^*\}]\le\mathbb{E}R(h_{W_n})-R^*\to0 E [ γ 1 { F n = b ∗ }] ≤ E R ( h W n ) − R ∗ → 0 , and the same Markov argument as above gives p n → 0 p_n\to0 p n → 0 . By Fano’s inequality, H ( F n ∣ b ∗ ( X ′ ) ) ≤ ϕ K ( p n ) H(F_n\mid b^*(X'))\le\phi_K(p_n) H ( F n ∣ b ∗ ( X ′ )) ≤ ϕ K ( p n ) and H ( b ∗ ( X ′ ) ∣ F n ) ≤ ϕ K ( p n ) H(b^*(X')\mid F_n)\le\phi_K(p_n) H ( b ∗ ( X ′ ) ∣ F n ) ≤ ϕ K ( p n ) , hence ∣ H ( F n ) − H ( b ∗ ( X ′ ) ) ∣ ≤ ϕ K ( p n ) → 0 |H(F_n)-H(b^*(X'))|\le\phi_K(p_n)\to0 ∣ H ( F n ) − H ( b ∗ ( X ′ )) ∣ ≤ ϕ K ( p n ) → 0 . Corollary 10 gives E V n → 0 \mathbb{E}V_n\to0 E V n → 0 , and Proposition 11 gives I ( F n ; X ′ ) = H ( F n ) − E V n → H ( b ∗ ( X ′ ) ) = C 01 ∗ I(F_n;X')=H(F_n)-\mathbb{E}V_n\to H(b^*(X'))=C^*_{01} I ( F n ; X ′ ) = H ( F n ) − E V n → H ( b ∗ ( X ′ )) = C 01 ∗ . □
Proof of Theorem 13 . Since f W ( x ) f_W(x) f W ( x ) is a function of ( S , ξ ) (S,\xi) ( S , ξ ) and the added noise is independent, V σ ( x ) = I ( f W ( x ) + σ Z ; f W ( x ) ) = h ( f W ( x ) + σ Z ) − h ( σ Z ) V_\sigma(x)=I(f_W(x)+\sigma Z;f_W(x))=h(f_W(x)+\sigma Z)-h(\sigma Z) V σ ( x ) = I ( f W ( x ) + σ Z ; f W ( x )) = h ( f W ( x ) + σ Z ) − h ( σ Z ) (differential entropies). (i) The Gaussian maximizes differential entropy at fixed variance, so h ( f W ( x ) + σ Z ) ≤ 1 2 log ( 2 π e ( v ( x ) + σ 2 ) ) h(f_W(x)+\sigma Z)\le\frac{1}{2}\log(2\pi e(v(x)+\sigma^2)) h ( f W ( x ) + σ Z ) ≤ 2 1 log ( 2 π e ( v ( x ) + σ 2 )) . (ii) Write f W ( x ) + σ Z = σ ( s n r f W ( x ) + Z ) f_W(x)+\sigma Z=\sigma(\sqrt{\mathop{\rm snr}}f_W(x)+Z) f W ( x ) + σ Z = σ ( snr f W ( x ) + Z ) with s n r = σ − 2 \mathop{\rm snr}=\sigma^{-2} snr = σ − 2 . The I-MMSE relation (Guo et al., [29 ] ) gives d d snr I = 1 2 mmse ( snr ) \frac{d}{d\operatorname{snr}} I = \frac{1}{2}\operatorname{mmse}(\operatorname{snr}) d snr d I = 2 1 mmse ( snr ) , with mmse \operatorname{mmse} mmse continuous at 0 0 0 and mmse ( 0 ) = v ( x ) \operatorname{mmse}(0) = v(x) mmse ( 0 ) = v ( x ) , so I = snr 2 v ( x ) + o ( snr ) I = \frac{\operatorname{snr}}{2}v(x) + o(\operatorname{snr}) I = 2 snr v ( x ) + o ( snr ) .
(iii) E ( f W ( X ) − Y ) 2 − E ( a ∗ ( X ) − Y ) 2 = E ( f W ( X ) − a ∗ ( X ) ) 2 = E ( f ˉ − a ∗ ) 2 + E v ( X ) \mathbb{E}(f_W(X) - Y)^2 - \mathbb{E}(a^*(X) - Y)^2 = \mathbb{E}(f_W(X) - a^*(X))^2 = \mathbb{E}(\bar{f} - a^*)^2 + \mathbb{E}v(X) E ( f W ( X ) − Y ) 2 − E ( a ∗ ( X ) − Y ) 2 = E ( f W ( X ) − a ∗ ( X ) ) 2 = E ( f ˉ − a ∗ ) 2 + E v ( X ) . By (i), 0 ≤ 2 σ 2 V σ ≤ σ 2 log ( 1 + v / σ 2 ) ≤ v 0 \le2\sigma^2 V_\sigma\le\sigma^2 \log(1 + v/\sigma^2) \le v 0 ≤ 2 σ 2 V σ ≤ σ 2 log ( 1 + v / σ 2 ) ≤ v , so dominated convergence and (ii) give lim σ 2 σ 2 E V σ = E v \lim_{\sigma} 2\sigma^2 \mathbb{E}V_\sigma= \mathbb{E}v lim σ 2 σ 2 E V σ = E v . □
Probabilistic outputs and log-loss
Proposition S5 (Log-loss; [35 ] ). Let the learner output class probabilities q W ( x ) ∈ Δ K q_W(x) \in\Delta_K q W ( x ) ∈ Δ K with E ∣ log q W , k ( x ) ∣ < ∞ \mathbb{E}|\log q_{W,k}(x)| < \infty E ∣ log q W , k ( x ) ∣ < ∞ . Let q ˉ k ( x ) = exp ( E log q W , k ( x ) ) / Z ( x ) \bar{q}_k(x) = \exp(\mathbb{E}\log q_{W,k}(x))/Z(x) q ˉ k ( x ) = exp ( E log q W , k ( x )) / Z ( x ) be the normalized geometric mean, where Z ( x ) = ∑ k exp ( E log q W , k ( x ) ) ≤ 1 Z(x) = \sum_k \exp(\mathbb{E}\log q_{W,k}(x)) \le1 Z ( x ) = ∑ k exp ( E log q W , k ( x )) ≤ 1 . Then, exactly,
E KL ( η ( x ) ∥ q W ( x ) ) = KL ( η ( x ) ∥ q ˉ ( x ) ) + E KL ( q ˉ ( x ) ∥ q W ( x ) ) , \mathbb{E}\operatorname{KL}(\eta(x)\mathbin\Vert q_W(x)) = \operatorname{KL}(\eta(x)\mathbin\Vert\bar{q}(x)) + \mathbb{E}\operatorname{KL}(\bar{q}(x)\mathbin\Vert q_W(x)), E KL ( η ( x ) ∥ q W ( x )) = KL ( η ( x ) ∥ q ˉ ( x )) + E KL ( q ˉ ( x ) ∥ q W ( x )) , and the left-hand side is the expected excess log-loss at x x x .
Proof. E KL ( η ∥ q W ) = ∑ k η k log η k − ∑ k η k E log q W , k = ∑ k η k log η k − ∑ k η k ( log q ˉ k + log Z ) = KL ( η ∥ q ˉ ) − log Z \mathbb{E}\operatorname{KL}(\eta\mathbin\Vert q_W) = \sum_k \eta_k \log\eta_k - \sum_k \eta_k\mathbb{E}\log q_{W,k} = \sum_k \eta_k \log\eta_k - \sum_k \eta_k(\log\bar{q}_k + \log Z) = \operatorname{KL}(\eta\mathbin\Vert\bar{q}) - \log Z E KL ( η ∥ q W ) = ∑ k η k log η k − ∑ k η k E log q W , k = ∑ k η k log η k − ∑ k η k ( log q ˉ k + log Z ) = KL ( η ∥ q ˉ ) − log Z ; and E KL ( q ˉ ∥ q W ) = ∑ k q ˉ k ( log q ˉ k − E log q W , k ) = − log Z \mathbb{E}\operatorname{KL}(\bar{q}\mathbin\Vert q_W) = \sum_k \bar{q}_k(\log\bar{q}_k - \mathbb{E}\log q_{W,k}) = -\log Z E KL ( q ˉ ∥ q W ) = ∑ k q ˉ k ( log q ˉ k − E log q W , k ) = − log Z . □
V log V_{\log} V l o g is the log-loss counterpart of V V V : it vanishes iff the learner’s probabilities do not depend on the sample, and it is infinite for one-hot outputs that vary, which is how log-loss penalizes confident instability. With logistic regression on a misspecified task, the identity holds to 10 − 15 10^{-15} 1 0 − 15 in simulation (t_theory2.py).
A single trained model
Proposition S6 (A single trained model). For K = 2 K = 2 K = 2 and any δ ∈ ( 0 , 1 ) \delta\in(0, 1) δ ∈ ( 0 , 1 ) , with probability at least 1 − δ 1 - \delta 1 − δ over ( S , ξ ) (S, \xi) ( S , ξ ) ,
R ( h W ) − R ∗ ≤ E [ ∣ 2 η 1 − 1 ∣ 1 { m ≠ b ∗ } ] + 1 2 δ E [ ∣ 2 η 1 − 1 ∣ V ( X ) ] . R(h_W) - R^* \le\mathbb{E}[|2\eta_1 - 1|1\{m \ne b^*\}] + \frac{1}{2\delta}\mathbb{E}[|2\eta_1 - 1|V(X)]. R ( h W ) − R ∗ ≤ E [ ∣2 η 1 − 1∣1 { m = b ∗ }] + 2 δ 1 E [ ∣2 η 1 − 1∣ V ( X )] .
Proof. R ( h W ) − R ∗ = E X [ ∣ 2 η 1 − 1 ∣ 1 { h W ≠ b ∗ } ] ≤ E X [ ∣ 2 η 1 − 1 ∣ 1 { m ≠ b ∗ } ] + Z R(h_W) - R^* = \mathbb{E}_X[|2\eta_1 - 1|1\{h_W \ne b^*\}] \le\mathbb{E}_X[|2\eta_1 - 1|1\{m \ne b^*\}] + Z R ( h W ) − R ∗ = E X [ ∣2 η 1 − 1∣1 { h W = b ∗ }] ≤ E X [ ∣2 η 1 − 1∣1 { m = b ∗ }] + Z , where Z = E X [ ∣ 2 η 1 − 1 ∣ 1 { h W ≠ m } ] ≥ 0 Z = \mathbb{E}_X[|2\eta_1 - 1|1\{h_W \ne m\}] \ge0 Z = E X [ ∣2 η 1 − 1∣1 { h W = m }] ≥ 0 and E Z = E [ ∣ 2 η 1 − 1 ∣ π ] ≤ 1 2 E [ ∣ 2 η 1 − 1 ∣ V ] \mathbb{E}Z = \mathbb{E}[|2\eta_1 - 1|\pi] \le\frac{1}{2}\mathbb{E}[|2\eta_1 - 1|V] E Z = E [ ∣2 η 1 − 1∣ π ] ≤ 2 1 E [ ∣2 η 1 − 1∣ V ] by Lemma S4. Apply Markov’s inequality to Z Z Z . □
So all of a single model’s excess over its learner’s modal predictor is controlled by expressed information, in probability. Sharper concentration needs stability (Proposition S8).
Bias–variance decompositions and disagreement
Table S1 collects the correspondence between existing variance, disagreement and information notions and the quantities of the main text (§ 4.6 and § 8 ).
Proof of Proposition 14 . Fix x x x and write q k = q ( k ∣ x ) q_k = q(k \mid x) q k = q ( k ∣ x ) , q m = max k q k q_m = \max_k q_k q m = max k q k . The first and last inequalities are Lemma S4, since π D = 1 − q m \pi_D = 1 - q_m π D = 1 − q m . Next, ∑ k q k 2 ≤ q m ∑ k q k = q m \sum_k q_k^2 \le q_m\sum_k q_k = q_m ∑ k q k 2 ≤ q m ∑ k q k = q m , so Dis = 1 − ∑ k q k 2 ≥ 1 − q m = π D \operatorname{Dis} = 1 - \sum_k q_k^2 \ge1 - q_m = \pi_D Dis = 1 − ∑ k q k 2 ≥ 1 − q m = π D . Also ∑ k q k 2 ≥ q m 2 \sum_k q_k^2 \ge q_m^2 ∑ k q k 2 ≥ q m 2 , so Dis ≤ 1 − q m 2 = ( 1 − q m ) ( 1 + q m ) ≤ 2 ( 1 − q m ) = 2 π D \operatorname{Dis} \le1 - q_m^2 = (1 - q_m)(1 + q_m) \le2(1 - q_m) = 2\pi_D Dis ≤ 1 − q m 2 = ( 1 − q m ) ( 1 + q m ) ≤ 2 ( 1 − q m ) = 2 π D . Two independent copies disagree with probability 1 − ∑ k P ( h W 1 ( x ) = k ) P ( h W 2 ( x ) = k ) = 1 − ∑ k q k 2 1 - \sum_k \mathbb{P}(h_{W_1}(x) = k)\mathbb{P}(h_{W_2}(x) = k) = 1 - \sum_k q_k^2 1 − ∑ k P ( h W 1 ( x ) = k ) P ( h W 2 ( x ) = k ) = 1 − ∑ k q k 2 . For K = 2 K = 2 K = 2 , the two-point law has π D = min ( q 1 , q 2 ) = h − 1 ( V ) \pi_D = \min(q_1, q_2) = h^{-1}(V) π D = min ( q 1 , q 2 ) = h − 1 ( V ) and Dis = 2 q 1 q 2 = 2 π D ( 1 − π D ) \operatorname{Dis} = 2q_1q_2 = 2\pi_D(1 - \pi_D) Dis = 2 q 1 q 2 = 2 π D ( 1 − π D ) ; both maps are
increasing on [ 0 , 1 2 ] [0,\frac{1}{2}] [ 0 , 2 1 ] . For the decomposition, P ( c ( x ) ≠ Y ) = 1 − η c ( x ) ( x ) \mathbb{P}(c(x) \ne Y) = 1-\eta_{c(x)}(x) P ( c ( x ) = Y ) = 1 − η c ( x ) ( x ) for any fixed classifier c c c , so SE ( x ) = η b ∗ ( x ) − η m ( x ) \operatorname{SE}(x)=\eta_{b^*}(x)-\eta_m(x) SE ( x ) = η b ∗ ( x ) − η m ( x ) and VE ( x ) = ∑ k q k ( η m ( x ) − η k ( x ) ) \operatorname{VE}(x)=\sum_k q_k(\eta_m(x)-\eta_k(x)) VE ( x ) = ∑ k q k ( η m ( x ) − η k ( x )) . Their sum is ∑ k q k ( η b ∗ ( x ) − η k ( x ) ) \sum_k q_k(\eta_{b^*}(x)-\eta_k(x)) ∑ k q k ( η b ∗ ( x ) − η k ( x )) , whose expectation is ER ( h W ) − R ∗ \operatorname{ER}(h_W)-R^* ER ( h W ) − R ∗ by (S1). For K = 2 K=2 K = 2 : if B = 0 B=0 B = 0 , SE = 0 \operatorname{SE}=0 SE = 0 and VE = ∣ 2 η 1 − 1 ∣ π D \operatorname{VE}=|2\eta_1-1|\pi_D VE = ∣2 η 1 − 1∣ π D ; if B = 1 B=1 B = 1 , SE = ∣ 2 η 1 − 1 ∣ \operatorname{SE}=|2\eta_1-1| SE = ∣2 η 1 − 1∣ and VE = q b ∗ ( η m − η b ∗ ) = − ∣ 2 η 1 − 1 ∣ π D \operatorname{VE}=q_{b^*}(\eta_m-\eta_{b^*})=-|2\eta_1-1|\pi_D VE = q b ∗ ( η m − η b ∗ ) = − ∣2 η 1 − 1∣ π D , since q b ∗ = 1 − q m = π D q_{b^*}=1-q_m=\pi_D q b ∗ = 1 − q m = π D .
Proof of Proposition 15. (a) At x x x , E 1 { h W ( x ) ≠ Y } = ∑ k q k ( 1 − η k ) \mathbb{E}\,1\{h_W(x)\ne Y\}=\sum_k q_k(1-\eta_k) E 1 { h W ( x ) = Y } = ∑ k q k ( 1 − η k ) , which equals 1 − ∑ k η k 2 = Dis ( x ) 1-\sum_k\eta_k^2=\operatorname{Dis}(x) 1 − ∑ k η k 2 = Dis ( x ) when q = η q=\eta q = η . (b) By (2) with m = b ∗ m=b^* m = b ∗ , ER − R ∗ = E [ ∣ 2 η 1 − 1 ∣ π D ] ≤ E π D \operatorname{ER}-R^*=\mathbb{E}[|2\eta_1-1|\pi_D]\le\mathbb{E}\pi_D ER − R ∗ = E [ ∣2 η 1 − 1∣ π D ] ≤ E π D . The remaining inequalities are Proposition 14 averaged over X X X . If ∣ 2 η 1 − 1 ∣ ≥ γ 0 |2\eta_1-1|\ge\gamma_0 ∣2 η 1 − 1∣ ≥ γ 0 , then ER − R ∗ ≥ γ 0 E π D ≥ γ 0 2 Dis \operatorname{ER}-R^*\ge\gamma_0\mathbb{E}\pi_D\ge\frac{\gamma_0}{2}\operatorname{Dis} ER − R ∗ ≥ γ 0 E π D ≥ 2 γ 0 Dis . (c) By Proposition 17 with k = 1 k=1 k = 1 , π D ( x ) → μ ( x ) = min ( η 1 ( x ) , 1 − η 1 ( x ) ) \pi_D(x)\to\mu(x)=\min(\eta_1(x),1-\eta_1(x)) π D ( x ) → μ ( x ) = min ( η 1 ( x ) , 1 − η 1 ( x )) for almost every x x x , so Dis ( x ) = 2 π D ( 1 − π D ) → 2 μ ( 1 − μ ) = 2 η 1 ( 1 − η 1 ) \operatorname{Dis}(x)=2\pi_D(1-\pi_D)\to2\mu(1-\mu)=2\eta_1(1-\eta_1) Dis ( x ) = 2 π D ( 1 − π D ) → 2 μ ( 1 − μ ) = 2 η 1 ( 1 − η 1 ) ; bounded convergence gives the limit of Dis \operatorname{Dis} Dis , which is the Cover–Hart limit of ER \operatorname{ER} ER . For a consistent sequence, Corollary 10 gives EV n → 0 \operatorname{EV}_n\to0 EV n → 0 , hence Dis ≤ EV n → 0 \operatorname{Dis}\le\operatorname{EV}_n\to0 Dis ≤ EV n → 0 , while ER → R ∗ \operatorname{ER}\to R^* ER → R ∗ .
Proofs for main Section 5
Throughout this section K = 2 K=2 K = 2 , p n ( x ) = P ( h W ( x ) = 1 ) p_n(x)=\mathbb{P}(h_W(x)=1) p n ( x ) = P ( h W ( x ) = 1 ) over ( S , ξ ) (S,\xi) ( S , ξ ) , and π n ( x ) = min ( p n ( x ) , 1 − p n ( x ) ) \pi_n(x)=\min(p_n(x),1-p_n(x)) π n ( x ) = min ( p n ( x ) , 1 − p n ( x )) , so that V n ( x ) = h ( π n ( x ) ) V_n(x)=h(\pi_n(x)) V n ( x ) = h ( π n ( x )) .
Proof of Proposition 16. (a) For two independent inputs, P ( X i = X j ) = ∑ z P ( Z = z ) 2 2 − d ≤ 2 − d \mathbb{P}(X_i=X_j)=\sum_z\mathbb{P}(Z=z)^2 2^{-d}\le2^{-d} P ( X i = X j ) = ∑ z P ( Z = z ) 2 2 − d ≤ 2 − d , so a union bound over pairs gives a collision probability of at most ( n 2 ) 2 − d ≤ n 2 2 − d − 1 → 0 \binom{n}{2}2^{-d}\le n^2 2^{-d-1}\to0 ( 2 n ) 2 − d ≤ n 2 2 − d − 1 → 0 . Without collisions the learner interpolates. (b) The training error satisfies ε ^ ≤ 1 { collision } \hat{\varepsilon}\le1\{\text{collision}\} ε ^ ≤ 1 { collision } , so ε ˉ ≤ n 2 2 − d − 1 → 0 \bar{\varepsilon}\le n^2 2^{-d-1}\to0 ε ˉ ≤ n 2 2 − d − 1 → 0 , and Theorem 5 gives I ( W ; Y n ∣ X n ) ≥ n [ H ( Y ∣ X ) − ϕ 2 ( ε ˉ ) ] = n ( H ( Y ∣ X ) − o ( 1 ) ) I(W;Y^n\mid X^n)\ge n[H(Y\mid X)-\phi_2(\bar{\varepsilon})]=n(H(Y\mid X)-o(1)) I ( W ; Y n ∣ X n ) ≥ n [ H ( Y ∣ X ) − ϕ 2 ( ε ˉ )] = n ( H ( Y ∣ X ) − o ( 1 )) . (c) For a fresh x ′ = ( z , u ) x'=(z,u) x ′ = ( z , u ) , P ( x ′ ∈ { X 1 , … , X n } ) ≤ n 2 − d → 0 \mathbb{P}(x'\in\{X_1,\ldots,X_n\})\le n2^{-d}\to0 P ( x ′ ∈ { X 1 , … , X n }) ≤ n 2 − d → 0 . Off the sample, the prediction is the majority of N z ∼ Bin ( n , P ( Z = z ) ) N_z\sim\operatorname{Bin}(n,\mathbb{P}(Z=z)) N z ∼ Bin ( n , P ( Z = z )) labels with mean η 1 ( z ) ≠ 1 2 \eta_1(z)\ne\frac{1}{2} η 1 ( z ) = 2 1 , which is wrong with probability at most E exp ( − 2 N z ( η 1 ( z ) − 1 2 ) 2 ) → 0 \mathbb{E}\exp(-2N_z(\eta_1(z)-\frac{1}{2})^2)\to0 E exp ( − 2 N z ( η 1 ( z ) − 2 1 ) 2 ) → 0 by Hoeffding’s inequality. So sup x ′ P ( h W ( x ′ ) ≠ b ∗ ( x ′ ) ) → 0 \sup_{x'}\mathbb{P}(h_W(x')\ne b^*(x'))\to0 sup x ′ P ( h W ( x ′ ) = b ∗ ( x ′ )) → 0 (finitely many z z z ). Hence m n = b ∗ m_n=b^* m n = b ∗ eventually, π n → 0 \pi_n\to0 π n → 0 uniformly, V n → 0 V_n\to0 V n → 0 , and ER → R ∗ \operatorname{ER}\to R^* ER → R ∗ by Theorem 9.
Proof of Proposition 17. Break distance and vote ties uniformly at random. For x x x in the support of P X P_X P X , the distance from x x x to its k k k -th nearest neighbour tends to 0 0 0 a.s. as n → ∞ n\to\infty n → ∞ with k k k fixed (Devroye et al., [21 ] , Lemma 5.1). Given X n X^n X n , the k k k neighbour labels are independent Bernoulli( η 1 ( X ( i ) ( x ) ) ) (\eta_1(X_{(i)}(x))) ( η 1 ( X ( i ) ( x ))) , and by continuity of η 1 \eta_1 η 1 at x x x their conditional law converges a.s. to that of k k k i.i.d. Bernoulli( η 1 ( x ) ) (\eta_1(x)) ( η 1 ( x )) labels. Bounded convergence gives p n ( x ) → β k ( η 1 ( x ) ) p_n(x)\to\beta_k(\eta_1(x)) p n ( x ) → β k ( η 1 ( x )) , and continuity of t ↦ h ( min ( t , 1 − t ) ) t\mapsto h(\min(t,1-t)) t ↦ h ( min ( t , 1 − t )) gives the limit of V n ( x ) V_n(x) V n ( x ) ; bounded convergence again gives the limit of E V n \mathbb{E}V_n E V n . The bound is Hoeffding’s inequality, min ( β k , 1 − β k ) ≤ exp ( − 2 k ( η 1 − 1 2 ) 2 ) \min(\beta_k,1-\beta_k)\le\exp(-2k(\eta_1-\frac{1}{2})^2) min ( β k , 1 − β k ) ≤ exp ( − 2 k ( η 1 − 2 1 ) 2 ) , together with monotonicity of h h h on [ 0 , 1 2 ] [0,\frac{1}{2}] [ 0 , 2 1 ] . For odd k k k , β k ( t ) > 1 2 \beta_k(t)>\frac{1}{2} β k ( t ) > 2 1 iff t > 1 2 t>\frac{1}{2} t > 2 1 , so the modal prediction converges to b ∗ b^* b ∗ wherever η 1 ≠ 1 2 \eta_1\ne\frac{1}{2} η 1 = 2 1 . The excess-risk limit follows from the exact identity (2) by bounded convergence: ER − R ∗ → E [ ∣ 2 η 1 − 1 ∣ min { β k ( η 1 ) , 1 − β k ( η 1 ) } ] \operatorname{ER}-R^*\to\mathbb{E}[|2\eta_1-1|\min\{\beta_k(\eta_1),1-\beta_k(\eta_1)\}] ER − R ∗ → E [ ∣2 η 1 − 1∣ min { β k ( η 1 ) , 1 − β k ( η 1 )}] . For k = 1 k=1 k = 1 , β 1 ( t ) = t \beta_1(t)=t β 1 ( t ) = t and h ( min ( η 1 , 1 − η 1 ) ) = h ( η 1 ) h(\min(\eta_1,1-\eta_1))=h(\eta_1) h ( min ( η 1 , 1 − η 1 )) = h ( η 1 ) , whose expectation is H ( Y ∣ X ) H(Y\mid X) H ( Y ∣ X ) . With μ = min ( η 1 , 1 − η 1 ) \mu=\min(\eta_1,1-\eta_1) μ = min ( η 1 , 1 − η 1 ) , ∣ 2 η 1 − 1 ∣ μ = μ − 2 μ 2 = 2 η 1 ( 1 − η 1 ) − μ |2\eta_1-1|\mu=\mu-2\mu^2=2\eta_1(1-\eta_1)-\mu ∣2 η 1 − 1∣ μ = μ − 2 μ 2 = 2 η 1 ( 1 − η 1 ) − μ , and E μ = R ∗ \mathbb{E}\mu=R^* E μ = R ∗ .
Proof of Proposition 18. Since h ( π ) ≤ 2 π h(\pi)\le2\sqrt{\pi} h ( π ) ≤ 2 π on [ 0 , 1 2 ] [0,\frac{1}{2}] [ 0 , 2 1 ] , it suffices to bound E π n ( X ) \mathbb{E}\sqrt{\pi_n(X)} E π n ( X ) , and π n ( x ) ≤ P ( vote ≠ b ∗ ( x ) ) \pi_n(x)\le\mathbb{P}(\text{vote}\ne b^*(x)) π n ( x ) ≤ P ( vote = b ∗ ( x )) . Fix x x x , let γ = ∣ η 1 ( x ) − 1 2 ∣ \gamma=|\eta_1(x)-\frac{1}{2}| γ = ∣ η 1 ( x ) − 2 1 ∣ , and let r k ( x ) r_k(x) r k ( x ) be the k k k -th nearest-neighbour distance. On { L r k ≤ γ / 2 } \{Lr_k\le\gamma/2\} { L r k ≤ γ /2 } , the neighbours’ labels are independent with means on the correct side of 1 2 \frac{1}{2} 2 1 by at least γ / 2 \gamma/2 γ /2 , so Hoeffding gives P ( vote wrong ∣ X n ) ≤ e − k γ 2 / 2 \mathbb{P}(\text{vote wrong}\mid X^n)\le e^{-k\gamma^2/2} P ( vote wrong ∣ X n ) ≤ e − k γ 2 /2 . Hence π n ( x ) ≤ e − k γ 2 / 2 + P ( r k ( x ) > γ / ( 2 L ) ) \pi_n(x)\le e^{-k\gamma^2/2}+\mathbb{P}(r_k(x)>\gamma/(2L)) π n ( x ) ≤ e − k γ 2 /2 + P ( r k ( x ) > γ / ( 2 L )) , and π n ( x ) ≤ e − k γ 2 / 4 + P ( r k ( x ) > γ / ( 2 L ) ) 1 / 2 \sqrt{\pi_n(x)}\le e^{-k\gamma^2/4}+\mathbb{P}(r_k(x)>\gamma/(2L))^{1/2} π n ( x ) ≤ e − k γ 2 /4 + P ( r k ( x ) > γ / ( 2 L ) ) 1/2 . The margin condition gives E e − k γ 2 / 4 ≤ ∑ j ≥ 0 P ( γ ≤ ( j + 1 ) / k ) e − j 2 / 4 ≤ c 1 k − α / 2 \mathbb{E}e^{-k\gamma^2/4}\le\sum_{j\ge0}\mathbb{P}(\gamma\le(j+1)/\sqrt{k})e^{-j^2/4}\le c_1k^{-\alpha/2} E e − k γ 2 /4 ≤ ∑ j ≥ 0 P ( γ ≤ ( j + 1 ) / k ) e − j 2 /4 ≤ c 1 k − α /2 . Under the density assumption, a Chernoff bound gives P ( r k ( x ) > r ) ≤ e − c n r d \mathbb{P}(r_k(x)>r)\le e^{-cnr^d} P ( r k ( x ) > r ) ≤ e − c n r d whenever n r d ≥ c ′ k nr^d\ge c'k n r d ≥ c ′ k ([21 ] ). Split on γ ≤ t n \gamma\le t_n γ ≤ t n with t n = 2 L ( c ′ k / n ) 1 / d t_n=2L(c'k/n)^{1/d} t n = 2 L ( c ′ k / n ) 1/ d : the event { γ ≤ t n } \{\gamma\le t_n\} { γ ≤ t n } has probability at most C 0 t n α = c 2 ( k / n ) α / d C_0t_n^\alpha=c_2(k/n)^{\alpha/d} C 0 t n α = c 2 ( k / n ) α / d , and on its complement P ( r k > γ / ( 2 L ) ) ≤ e − c c ′ k \mathbb{P}(r_k>\gamma/(2L))\le e^{-c c'k} P ( r k > γ / ( 2 L )) ≤ e − c c ′ k . Altogether E V n ≤ c 1 k − α / 2 + c 2 ( k / n ) α / d + c 3 e − c 4 k \mathbb{E}V_n\le c_1k^{-\alpha/2}+c_2(k/n)^{\alpha/d}+c_3e^{-c_4k} E V n ≤ c 1 k − α /2 + c 2 ( k / n ) α / d + c 3 e − c 4 k , and k ≍ n 2 / ( d + 2 ) k\asymp n^{2/(d+2)} k ≍ n 2/ ( d + 2 ) balances the first two terms at n − α / ( d + 2 ) n^{-\alpha/(d+2)} n − α / ( d + 2 ) .
Proposition S7 (Averaging, full statement). Let g B g_B g B be the majority vote of B B B independent copies of a binary learner (B B B odd; independent samples and seeds), and write π = π n \pi=\pi_n π = π n , m = m n m=m_n m = m n . Then for every x x x : (a) the modal prediction of g B g_B g B is m ( x ) m(x) m ( x ) ; (b) π g B ( x ) = P ( Bin ( B , π ( x ) ) > B / 2 ) ≤ exp ( − 2 B ( 1 / 2 − π ( x ) ) 2 ) \pi_{g_B}(x)=\mathbb{P}(\operatorname{Bin}(B,\pi(x))>B/2)\le\exp(-2B(1/2-\pi(x))^2) π g B ( x ) = P ( Bin ( B , π ( x )) > B /2 ) ≤ exp ( − 2 B ( 1/2 − π ( x ) ) 2 ) ; (c) as B → ∞ B\to\infty B → ∞ ,
E R ( g B ) − E R ( h W ) → E [ ∣ 2 η 1 − 1 ∣ π ( 1 { m ≠ b ∗ } − 1 { m = b ∗ } ) 1 { π < 1 2 } ] . \mathbb{E}R(g_B)-\mathbb{E}R(h_W)\to\mathbb{E}\left[|2\eta_1-1|\pi\left(1\{m\ne b^*\}-1\{m=b^*\}\right)1\{\pi<\tfrac12\}\right]. E R ( g B ) − E R ( h W ) → E [ ∣2 η 1 − 1∣ π ( 1 { m = b ∗ } − 1 { m = b ∗ } ) 1 { π < 2 1 } ] .
Proof. (a)–(b) Given x x x , the B B B votes are i.i.d. Bernoulli( p ( x ) ) (p(x)) ( p ( x )) . For odd B B B , P ( Bin ( B , p ) > B / 2 ) > 1 2 \mathbb{P}(\operatorname{Bin}(B,p)>B/2)>\frac12 P ( Bin ( B , p ) > B /2 ) > 2 1 iff p > 1 2 p>\frac12 p > 2 1 , and the probability that the vote disagrees with m ( x ) m(x) m ( x ) is P ( Bin ( B , π ) > B / 2 ) \mathbb{P}(\operatorname{Bin}(B,\pi)>B/2) P ( Bin ( B , π ) > B /2 ) , which Hoeffding’s inequality bounds. (c) By (2) , E R ( g B ) − R ∗ = E [ ∣ 2 η 1 − 1 ∣ ( π g B 1 { m = b ∗ } + ( 1 − π g B ) 1 { m ≠ b ∗ } ) ] \mathbb{E}R(g_B)-R^*=\mathbb{E}[|2\eta_1-1|(\pi_{g_B}1\{m=b^*\}+(1-\pi_{g_B})1\{m\ne b^*\})] E R ( g B ) − R ∗ = E [ ∣2 η 1 − 1∣ ( π g B 1 { m = b ∗ } + ( 1 − π g B ) 1 { m = b ∗ })] . As B → ∞ B\to\infty B → ∞ , π g B → 0 \pi_{g_B}\to0 π g B → 0 where π < 1 2 \pi<\frac12 π < 2 1 and stays 1 2 \frac12 2 1 where π = 1 2 \pi=\frac12 π = 2 1 . Subtract the same identity for h W h_W h W and use bounded convergence.
Part (c) says that averaging reduces risk exactly when the expression it removes where the mode is right outweighs the expression it removes where the mode is wrong (where averaging locks the error in). Practical bagging uses bootstrap resamples of one sample, which are dependent, so its gain is smaller than (b) suggests; random forests partly restore independence by feature subsampling ([15 ] ).
Proposition S8 (Stable learners express little). Let the learner be deterministic, let S ( i ) S^{(i)} S ( i ) be S S S with its i i i -th example replaced by an independent copy, and let β n ( x ) = max i P ( h S ( x ) ≠ h S ( i ) ( x ) ) \beta_n(x)=\max_i\mathbb{P}(h_S(x)\ne h_{S^{(i)}}(x)) β n ( x ) = max i P ( h S ( x ) = h S ( i ) ( x )) . Then π n ( x ) ≤ n β n ( x ) \pi_n(x)\le n\beta_n(x) π n ( x ) ≤ n β n ( x ) and V n ( x ) ≤ h ( min { 1 2 , n β n ( x ) } ) V_n(x)\le h(\min\{\frac12,n\beta_n(x)\}) V n ( x ) ≤ h ( min { 2 1 , n β n ( x )}) .
Proof. Apply the Efron–Stein inequality to f ( S ) = 1 { h S ( x ) = 1 } f(S)=1\{h_S(x)=1\} f ( S ) = 1 { h S ( x ) = 1 } : p ( 1 − p ) = Var f ( S ) ≤ 1 2 ∑ i E ( f ( S ) − f ( S ( i ) ) ) 2 ≤ n 2 β n ( x ) p(1-p)=\operatorname{Var}f(S)\le\frac12\sum_i\mathbb{E}(f(S)-f(S^{(i)}))^2\le\frac n2\beta_n(x) p ( 1 − p ) = Var f ( S ) ≤ 2 1 ∑ i E ( f ( S ) − f ( S ( i ) ) ) 2 ≤ 2 n β n ( x ) . Since π ≤ 1 2 \pi\le\frac12 π ≤ 2 1 , π ( 1 − π ) ≥ π / 2 \pi(1-\pi)\ge\pi/2 π ( 1 − π ) ≥ π /2 , so π ≤ n β n ( x ) \pi\le n\beta_n(x) π ≤ n β n ( x ) . Then use monotonicity of h h h on [ 0 , 1 2 ] [0,\frac12] [ 0 , 2 1 ] .
Uniform stability at rate o ( 1 / n ) o(1/n) o ( 1/ n ) ([14 ] ) thus forces V n → 0 V_n\to0 V n → 0 . Interpolators of noisy labels cannot be that stable, since replacing a training point near x x x flips the prediction there, so this result is mainly informative for regularized learners.
Proof of Proposition 20. The prediction x ′ ⊤ X + ( X β + ε ) x'^\top X^+(X\beta+\varepsilon) x ′⊤ X + ( X β + ε ) is Gaussian with variance σ ε 2 ∥ ( X + ) ⊤ x ′ ∥ 2 \sigma_\varepsilon^2\|(X^+)^\top x'\|^2 σ ε 2 ∥ ( X + ) ⊤ x ′ ∥ 2 given the design and x ′ x' x ′ . Adding independent N ( 0 , σ 2 ) N(0,\sigma^2) N ( 0 , σ 2 ) noise gives a Gaussian channel with Gaussian input, whose mutual information is the stated formula. For p ≥ n p\ge n p ≥ n (full row rank), X + = X ⊤ ( X X ⊤ ) − 1 X^+=X^\top(XX^\top)^{-1} X + = X ⊤ ( X X ⊤ ) − 1 , and E x ′ ∥ ( X X ⊤ ) − 1 X x ′ ∥ 2 = tr ( ( X X ⊤ ) − 1 X Σ X ⊤ ( X X ⊤ ) − 1 ) = tr ( C ) \mathbb{E}_{x'}\|(XX^\top)^{-1}Xx'\|^2=\operatorname{tr}((XX^\top)^{-1}X\Sigma X^\top(XX^\top)^{-1})=\operatorname{tr}(C) E x ′ ∥ ( X X ⊤ ) − 1 X x ′ ∥ 2 = tr (( X X ⊤ ) − 1 X Σ X ⊤ ( X X ⊤ ) − 1 ) = tr ( C ) (for centred x ′ x' x ′ ; otherwise Σ \Sigma Σ is the second-moment matrix). The limit follows from log ( 1 + a ) / a → 1 \log(1+a)/a\to1 log ( 1 + a ) / a → 1 and dominated convergence, as in Theorem 13 .
A Monte Carlo check with n = 50 n=50 n = 50 , p = 200 p=200 p = 200 matches the predictive variance σ ε 2 ∥ ( X + ) ⊤ x ′ ∥ 2 \sigma_\varepsilon^2\|(X^+)^\top x'\|^2 σ ε 2 ∥ ( X + ) ⊤ x ′ ∥ 2 to within 2% (t_theory2.py).
Theory of the consensus criterion and of noise correction
In Section 6.4 we introduced the label-free consensus criterion (3) and a switch to noise-corrected validation. This section gives the theory behind both: what disagreement with a consensus measures, when the consensus is close to the Bayes classifier, and the two ways it can fail.
Let m 1 , … , m J m_1,\ldots,m_J m 1 , … , m J be the candidates’ modal predictors and c c c their plurality vote (fixed tie-break). Write β j = P ( m j ( X ) ≠ b ∗ ( X ) ) \beta_j=\mathbb{P}(m_j(X)\ne b^*(X)) β j = P ( m j ( X ) = b ∗ ( X )) for candidate j j j ’s modal-bias mass, β ˉ \bar{\beta} β ˉ for its average over candidates, D j = P ( m j ( X ) ≠ c ( X ) ) D_j=\mathbb{P}(m_j(X)\ne c(X)) D j = P ( m j ( X ) = c ( X )) for its disagreement with the consensus, and δ = P ( c ( X ) ≠ b ∗ ( X ) ) \delta=\mathbb{P}(c(X)\ne b^*(X)) δ = P ( c ( X ) = b ∗ ( X )) for the consensus error. Let W ( x ) = 1 J ∑ j 1 { m j ( x ) ≠ b ∗ ( x ) } W(x)=\frac{1}{J}\sum_j1\{m_j(x)\ne b^*(x)\} W ( x ) = J 1 ∑ j 1 { m j ( x ) = b ∗ ( x )} be the fraction of candidates that are wrong at x x x .
Proposition S9 (Consensus error is shared-bias mass). δ ≤ P ( W ( X ) ≥ 1 2 ) ≤ 2 β ˉ \delta\le\mathbb{P}(W(X)\ge\frac{1}{2})\le2\bar{\beta} δ ≤ P ( W ( X ) ≥ 2 1 ) ≤ 2 β ˉ . The same holds when the voters are clusters of candidates, each voting with its own plurality, with W W W and β ˉ \bar{\beta} β ˉ computed over clusters.
Proof. If more than half of the candidates predict b ∗ ( x ) b^*(x) b ∗ ( x ) , then b ∗ ( x ) b^*(x) b ∗ ( x ) is the plurality, so { c ≠ b ∗ } ⊆ { W ≥ 1 2 } \{c\ne b^*\}\subseteq\{W\ge\frac{1}{2}\} { c = b ∗ } ⊆ { W ≥ 2 1 } . Markov’s inequality gives P ( W ≥ 1 2 ) ≤ 2 E W = 2 β ˉ \mathbb{P}(W\ge\frac{1}{2})\le2\mathbb{E}W=2\bar{\beta} P ( W ≥ 2 1 ) ≤ 2 E W = 2 β ˉ . The cluster version is the same argument with clusters as voters.
In words, the consensus is wrong only where at least half of the voters share an error. Many candidates with different biases do no harm; a majority with the same bias does.
Proposition S10 (What disagreement measures). Let S = { c ≠ b ∗ } S=\{c\ne b^*\} S = { c = b ∗ } . (a) For K = 2 K=2 K = 2 , D j = β j + δ − 2 s j D_j=\beta_j+\delta-2s_j D j = β j + δ − 2 s j , where s j = P ( S ∩ { m j ≠ b ∗ } ) ≤ min ( β j , δ ) s_j=\mathbb{P}(S\cap\{m_j\ne b^*\})\le\min(\beta_j,\delta) s j = P ( S ∩ { m j = b ∗ }) ≤ min ( β j , δ ) is the part of candidate j j j ’s bias that it shares with the consensus. (b) For any K K K , ∣ D j − β j ∣ ≤ δ \lvert D_j-\beta_j\rvert\le\delta ∣ D j − β j ∣ ≤ δ . Consequently ∣ ( D i − D j ) − ( β i − β j ) ∣ ≤ 2 δ \lvert(D_i-D_j)-(\beta_i-\beta_j)\rvert\le2\delta ∣( D i − D j ) − ( β i − β j )∣ ≤ 2 δ for all i , j i,j i , j , and the candidate with the smallest disagreement has modal-bias mass within 2 δ 2\delta 2 δ of the smallest.
Proof. (a) For binary labels, m j ( x ) ≠ c ( x ) m_j(x)\ne c(x) m j ( x ) = c ( x ) iff exactly one of m j ( x ) ≠ b ∗ ( x ) m_j(x)\ne b^*(x) m j ( x ) = b ∗ ( x ) and c ( x ) ≠ b ∗ ( x ) c(x)\ne b^*(x) c ( x ) = b ∗ ( x ) holds, so D j = β j + δ − 2 s j D_j=\beta_j+\delta-2s_j D j = β j + δ − 2 s j . (b) P ( u ≠ w ) \mathbb{P}(u\ne w) P ( u = w ) is a pseudometric on classifiers, and the triangle inequality gives ∣ P ( m j ≠ c ) − P ( m j ≠ b ∗ ) ∣ ≤ P ( c ≠ b ∗ ) \lvert\mathbb{P}(m_j\ne c)-\mathbb{P}(m_j\ne b^*)\rvert\le\mathbb{P}(c\ne b^*) ∣ P ( m j = c ) − P ( m j = b ∗ )∣ ≤ P ( c = b ∗ ) . The consequence follows by subtracting the bounds for i i i and j j j .
Part (a) states the failure mode exactly: disagreement counts a candidate’s private errors in full, but subtracts the errors it shares with the consensus, so conforming to a biased majority is rewarded. Two mechanisms produce such a majority.
Redundant candidates. When many candidates come from one family with a common misspecification (for example several regularization levels of a linear model on a curved boundary), they form a majority with a common bias. Giving one vote per cluster of near-identical candidates removes the redundancy: by Proposition S9, only clusters then count. Our adaptive clustering uses average-linkage clusters at disagreement 0.05, one vote per cluster, and only when some cluster holds at least a third of the candidates.
Asymmetric label noise. The second mechanism affects every candidate at once.
Proposition S11 (Noise-induced shared bias). Let K = 2 K=2 K = 2 and let the training labels pass through class-conditional noise with ρ 0 = P ( Y ~ = 1 ∣ Y = 0 ) \rho_0=\mathbb{P}(\widetilde{Y}=1\mid Y=0) ρ 0 = P ( Y = 1 ∣ Y = 0 ) and ρ 1 = P ( Y ~ = 0 ∣ Y = 1 ) \rho_1=\mathbb{P}(\widetilde{Y}=0\mid Y=1) ρ 1 = P ( Y = 0 ∣ Y = 1 ) , where ρ 0 + ρ 1 < 1 \rho_0+\rho_1<1 ρ 0 + ρ 1 < 1 . Then η ~ 1 = ρ 0 + ( 1 − ρ 0 − ρ 1 ) η 1 \widetilde{\eta}_1=\rho_0+(1-\rho_0-\rho_1)\eta_1 η 1 = ρ 0 + ( 1 − ρ 0 − ρ 1 ) η 1 , and the Bayes classifier of the noisy problem is b ∗ ( x ) = 1 { η 1 ( x ) > θ } b^*(x)=1\{\eta_1(x)>\theta\} b ∗ ( x ) = 1 { η 1 ( x ) > θ } with θ = 1 2 − ρ 0 1 − ρ 0 − ρ 1 \theta=\frac{\frac{1}{2}-\rho_0}{1-\rho_0-\rho_1} θ = 1 − ρ 0 − ρ 1 2 1 − ρ 0 . If every candidate is consistent for the noisy problem, then
δ → δ T : = P ( b ~ ∗ ( X ) ≠ b ∗ ( X ) ) \delta\to\delta_T := \mathbb{P}(\tilde{b}^{*}(X) \ne b^{*}(X)) δ → δ T := P ( b ~ ∗ ( X ) = b ∗ ( X )) , the mass of η 1 \eta_1 η 1 between θ \theta θ and 1 2 \frac{1}{2} 2 1 . In particular δ T = 0 \delta_T = 0 δ T = 0 when ρ 0 = ρ 1 \rho_0 = \rho_1 ρ 0 = ρ 1 : symmetric noise creates no shared bias.
Proof. P ( Y ~ = 1 ∣ X ) = ρ 0 ( 1 − η 1 ) + ( 1 − ρ 1 ) η 1 \mathbb{P}(\tilde{Y} = 1 \mid X) = \rho_0(1-\eta_1) + (1-\rho_1)\eta_1 P ( Y ~ = 1 ∣ X ) = ρ 0 ( 1 − η 1 ) + ( 1 − ρ 1 ) η 1 , which exceeds 1 2 \frac{1}{2} 2 1 iff η 1 > θ \eta_1 > \theta η 1 > θ . Consistency for the noisy problem drives each candidate’s prediction, and hence its mode, to b ~ ∗ ( x ) \tilde{b}^{*}(x) b ~ ∗ ( x ) wherever η 1 ( x ) ≠ θ \eta_1(x) \ne\theta η 1 ( x ) = θ , so the plurality is b ~ ∗ \tilde{b}^{*} b ~ ∗ and δ → P ( b ~ ∗ ≠ b ∗ ) \delta\to\mathbb{P}(\tilde{b}^{*} \ne b^{*}) δ → P ( b ~ ∗ = b ∗ ) . If ρ 0 = ρ 1 < 1 2 \rho_0 = \rho_1 < \frac{1}{2} ρ 0 = ρ 1 < 2 1 , then θ = 1 2 \theta= \frac{1}{2} θ = 2 1 .
The shift cannot be seen in the candidates’ predictions, because every candidate shares it. Holdout on noisy labels does not see it either, since it estimates the noisy risk, which b ~ ∗ \tilde{b}^{*} b ~ ∗ minimizes. Removing it needs knowledge of the transition matrix T T T , through backward correction ([53 , 57 ] ): for T j k = P ( Y ~ = k ∣ Y = j ) T_{jk} = \mathbb{P}(\tilde{Y} = k \mid Y = j) T j k = P ( Y ~ = k ∣ Y = j ) invertible, E [ 1 − ( T − 1 ) Y ~ y ^ ∣ Y = y ] = 1 − ∑ k T y k ( T − 1 ) k y ^ = 1 { y ^ ≠ y } \mathbb{E}[1 - (T^{-1})_{\tilde{Y}\hat{y}} \mid Y = y] = 1 - \sum_k T_{yk}(T^{-1})_{k\hat{y}} = 1\{\hat{y} \ne y\} E [ 1 − ( T − 1 ) Y ~ y ^ ∣ Y = y ] = 1 − ∑ k T y k ( T − 1 ) k y ^ = 1 { y ^ = y } , an unbiased estimate of the clean 0-1 loss. The next remark shows when correction can change a selection at all.
Estimating T T T and the switch rule. We estimate T T T without extra labels: T ^ j k \hat{T}_{jk} T ^ j k is the fraction of training points whose consensus out-of-fold prediction is j j j and whose noisy label is k k k . For numerical stability we shrink, T ^ ← 0.95 T ^ + 0.05 I \hat{T} \leftarrow0.95\hat{T} + 0.05I T ^ ← 0.95 T ^ + 0.05 I , and fall back to no correction when the condition number exceeds 50. The asymmetry of T ^ \hat{T} T ^ is its largest entrywise deviation from the symmetric noise matrix with the same mean flip rate ρ ^ = 1 − tr ( T ^ ) / K \hat{\rho} = 1 - \operatorname{tr}(\hat{T})/K ρ ^ = 1 − tr ( T ^ ) / K . The switch rule uses noise-corrected validation when the asymmetry exceeds 0.1, and the label-free criterion otherwise. On the 90 Protocol-A cases, the asymmetry is 0.023 on average (at most 0.087) under symmetric noise and 0.144 on average (at least 0.067) under class-dependent noise, so the threshold separates the two noise types; thresholds between 0.05 and 0.15 give the same regret to within 0.001.
Erratum for the earlier work on lossless maximal compression
This section corrects two earlier non-archival papers: the preprint Nikolaou et al. [55 ] , “Margin Maximization as Lossless Maximal Compression” (arXiv:2001.10318), and the short paper Nikolaou [54 ] , “Lossless Compression & Generalization in Overparameterized Models: The Case of Boosting” (ICLR 2021). We call them “the preprint” and “the short paper.” All numbered items below refer to the preprint’s arXiv version, unless stated otherwise. For each problem we state what was claimed, what is wrong, and how the main text corrects it. We end with what survives.
What was claimed. The preprint defines, on a training set S S S , noiselessness (H S ( Y ∣ X ) = 0 H_S(Y \mid X) = 0 H S ( Y ∣ X ) = 0 ; Def. 1), losslessness (I S ( F ; Y ) = I S ( X ; Y ) I_S(F;Y) = I_S(X;Y) I S ( F ; Y ) = I S ( X ; Y ) ; Def. 2), maximal compression (I S ( F ; X ) = I S ( F ; Y ) I_S(F;X) = I_S(F;Y) I S ( F ; X ) = I S ( F ; Y ) ; Def. 3), and a lossless maximal compressor (LMC) as a model that is both (Def. 4). Prop. 1 states that f f f is an LMC iff I S ( F ; X ) = I S ( F ; Y ) = I S ( X ; Y ) I_S(F;X) = I_S(F;Y) = I_S(X;Y) I S ( F ; X ) = I S ( F ; Y ) = I S ( X ; Y ) , and Theorem 1 states that, for a noiseless finitely supported S S S , f f f is an LMC iff some invertible transform g ∘ f g \circ f g ∘ f is a margin maximizer (Theorem 2 and Prop. 2 in its supplement extend these to a general finitely supported distribution). Table 1 and Figure 1 enumerate the relations between the information quantities in eight scenarios: noiseless or noisy data, lossy or lossless, under- or maximally compressed. Section 4 reports that boosting “traces a trajectory on the information plane that leads to the LMC point” and never leaves it. Section 4.2 is titled “Early stopping does not improve generalization in gradient boosting”. The short paper restates the definitions and Propositions (I)–(III), argues that “adequate overparameterization guarantees losslessness” and that inductive biases then drive training towards maximal compression, and shows the same trajectories on the musk and credit datasets. Both papers estimate all quantities on the training data, after discretizing features and outputs into b = 100 b = 100 b = 100 equal-width bins and encoding the joint input as X = ∑ i X i b i − 1 X = \sum_i X_i b^{i-1} X = ∑ i X i b i − 1 , with 100 random 50/50 train/test splits.
Error 1: the noisy-case LMC does not exist. For a deterministic output, I ( F ; X ) = I ( F ; Y ) I(F; X) = I(F; Y) I ( F ; X ) = I ( F ; Y ) forces H ( F ∣ Y ) = 0 H(F \mid Y) = 0 H ( F ∣ Y ) = 0 , so F F F would have to be a function of the label. By Proposition 4, a deterministic LMC exists iff the Gács–Körner common information equals I ( X ; Y ) I(X; Y) I ( X ; Y ) ; for binary labels, this means H ( Y ∣ X ) = 0 H(Y \mid X) = 0 H ( Y ∣ X ) = 0 or I ( X ; Y ) = 0 I(X; Y) = 0 I ( X ; Y ) = 0 . Prop. 1 (and its supplementary version, Prop. 2) is correct as a characterization, but for noisy data with informative features the set it characterizes is empty. In particular:
the “noisy, lossless, maximally compressed” row of Table 1 , I ( F ; Y ) = I ( X ; Y ) = I ( F ; X ) < H ( Y ) I(F; Y) = I(X; Y) = I(F; X) < H(Y) I ( F ; Y ) = I ( X ; Y ) = I ( F ; X ) < H ( Y ) , and the corresponding bottom-right panel of Figure 1 (noisy column, lossless maximally compressed row) describe an impossible configuration;
so does the statement in Table 2 that, on noisy data, “some training error minimizers are LMCs”;
and so does the suggestion in § 3.3 that models capturing the label distribution are “ideally” LMCs.
The preprint’s own observation that “in the noisy case, a margin maximizer cannot even be a lossless model” is correct. Correction: § 3.2 replaces LMC by the minimal ℓ \ell ℓ -sufficient representation (G-LMC), which always exists. It is the Bayes act a ∗ ( X ) : η ( X ) a^*(X): \eta(X) a ∗ ( X ) : η ( X ) under log-loss and b ∗ ( X ) b^*(X) b ∗ ( X ) under 0-1 loss. Lemma S3 quantifies the gap: a log-loss sufficient output must retain at least H ( η ( X ) ∣ Y ) > 0 H(\eta(X) \mid Y) > 0 H ( η ( X ) ∣ Y ) > 0 bits beyond I ( F ; Y ) I(F; Y) I ( F ; Y ) .
Error 2: empirical information cannot tell interpolators apart. With distinct training inputs, the empirical distribution is noiseless, so every interpolating hard classifier is an empirical LMC (Remark S1). This includes the 1-NN rule, whose asymptotic risk can approach twice the Bayes risk. The binning used in both papers makes this worse: with b = 100 b = 100 b = 100 bins per feature and several features, almost every training input occupies its own cell. The preprint notes that discretization did not make any dataset noisy, which is precisely this degeneracy, and it reports that “all results shown are on noiseless datasets”, including a synthetic dataset with 1% label flips. Table 1 confirms the consequence. The legacy score I S ( F ; Y ) / H S ( Y ) I_S(F; Y)/H_S(Y) I S ( F ; Y ) / H S ( Y ) is 0.99 for five interpolators whose excess risks range over two orders of magnitude. In § 7.4 it is 0.91–1.00 for every interpolator on real data with injected noise, against test errors of 0.04–0.50. Correction: every quantity in the main text is defined at the population level, or through the learner’s behaviour over independent training samples.
Error 3: estimation artifacts. Binned estimates of mutual information for deterministic maps depend strongly on the bin width, and they can show spurious “compression” [61 , 43 , 28 ] . On the training set, the normalized coordinate I S ( F ; X ) / H S ( X ) I_S(F;X)/H_S(X) I S ( F ; X ) / H S ( X ) of a hard or binned output is H S ( F ) / log 2 n H_S(F)/\log_2 n H S ( F ) / log 2 n . It falls whenever the binned training scores concentrate into fewer cells, for example as boosting pushes scores towards the extremes. That is a property of the score distribution on the training set, not evidence of better generalization (Error 5). Correction: the main text’s ideal-model quantities use discrete inputs and outputs, where they are well defined. V V V is an entropy of hard predictions over training samples at a fixed input, so it needs no binning.
Error 4: margin guarantees are not inherited by LMC models in general. The preprint argues that “the existence of margin-based bounds on the generalization error implies that margin maximization is beneficial”, and therefore so is lossless maximal compression. This inference holds only within Theorem 1: noiseless data, and only for the transformed score g ∘ f g \circ f g ∘ f with some invertible g g g . On the training set, Theorem 1 applies to every interpolating score, because the empirical distribution is noiseless (Error 2). Margin bounds depend on the margin distribution of the actual score, which an arbitrary invertible g g g can change at will. So an LMC on the training set carries no margin guarantee; the 1-NN rule is an example. Under noise, LMC models do not exist (Error 1). Correction: the main text makes no margin claims. The link between learners and risk goes through Theorem 9 .
Error 5: compression and early stopping under label noise. Both papers read the late-stage decrease of I S ( F ; X ) I_S(F;X) I S ( F ; X ) as compression that improves generalization, and concluded that early stopping is unnecessary in boosting. Their experiments used data that were noiseless, at least empirically (Error 2). We replicated the experiment on the running example with 20% label noise (§ 7.3 ; n = 1024 n = 1024 n = 1024 , depth-6 trees, exponential loss, 200 rounds).
With the original setting (learning rate 1, no shrinkage), the old coordinate falls from 0.52 at round 5 to 0.10 by round 25 and stays there. Over the same rounds, excess risk stays at 0.058–0.065, and V V V at 0.39–0.43 bits.
With shrinkage 0.1 (Figure 3 ), the coordinate falls from 0.58 to 0.12, while excess risk rises from 0.011 at round 15 to 0.050 at round 200, and V V V from 0.09 to 0.35 bits.
So “compression” does not improve generalization under noise, and early stopping with shrinkage gives a five times lower excess risk than the original unstopped setting. On four real datasets with 20% injected noise (depth-3 trees, shrinkage 0.1) the same reversal occurs (Figure 3 ). Without injected noise, the old reading is reproduced on the nearly noiseless wdbc and biopsy, and reversed on OJ and Caravan, whose labels are intrinsically noisy. Correction: the claim holds only on (nearly) noiseless data. Under label noise, early stopping helps, and expressed information tracks test error along the trajectory (Spearman 0.82–1.00 on real data).
What survives.
(i) The noiseless-case identification of LMC with the Bayes decision, up to relabelling, is the special case H ( Y ∣ X ) = 0 H(Y \mid X) = 0 H ( Y ∣ X ) = 0 of Theorem 2. The noiseless part of Theorem 1 is unaffected as a statement about distributions.
(ii) Lemma 3 of the preprint, that I ( F ; Y ) = I ( X ; Y ) I(F;Y) = I(X;Y) I ( F ; Y ) = I ( X ; Y ) if x ↦ P ( Y = 1 ∣ X = x ) x \mapsto\mathbb{P}(Y = 1 \mid X = x) x ↦ P ( Y = 1 ∣ X = x ) is constant on the level sets of f f f , is the binary log-loss case of Proposition 1. It is now stated for general losses, K K K classes and stochastic representations.
(iii) The observation that margin maximizers cannot be lossless under noise is correct. In the terms of the main text, a margin maximizer can be 0-1 sufficient but not log-loss sufficient, because C 01 ∗ = H ( b ∗ ( X ) ) < H ( η ( X ) ) = C log ∗ C^{*}_{01}=H(b^{*}(X))<H(\eta(X))=C^{*}_{\log} C 01 ∗ = H ( b ∗ ( X )) < H ( η ( X )) = C l o g ∗ in general.
(iv) The motivation, that a model’s output complexity should be compared with a minimal sufficient level, survives as the excess complexity of § 3.2 . It is complemented by expressed information, which explains generalization where the output-level picture cannot.
(v) On noiseless data, the boosting trajectories reported earlier are reproduced.
Experimental details
All experiments use Python with numpy, scipy and scikit-learn ([58 ] ), and run on CPUs. Section K lists the script for each experiment.
Synthetic tasks
Running example (§ 7.1 ). As in Example 1. Excess risks are computed exactly from η \eta η on a fixed Monte Carlo set of test inputs (20,000 inputs). The learners are: memorize-and-smooth; 1-NN and k k k -NN with k k k the odd integer nearest n \sqrt{n} n (Hamming distance); a full-depth tree; a random forest (100 trees); gradient boosting with exponential loss, learning rate 1, depth 6 and 100 rounds (the setting of the earlier papers); logistic regression with C = 10 4 C=10^{4} C = 1 0 4 ; and a 512-unit MLP trained without regularization until it interpolates. R = 30 R=30 R = 30 independent training samples per configuration. Soft outputs, where needed for log-loss quantities, are quantized to multiples of 1/20. Table 1 is a separate pilot run of the same task; its numbers differ from those of § 7.1 in the third decimal.
Double descent (§ 7.2 ). Random ReLU features ϕ ( x ) = max ( G x + b , 0 ) / p \phi(x)=\max(Gx+b,0)/\sqrt{p} ϕ ( x ) = max ( G x + b , 0 ) / p with Gaussian G G G , b b b , on the one-hot encoding of the running example; minimum-norm least squares on ± 1 \pm1 ± 1 labels (or one-hot targets for digits); prediction by sign (argmax). Widths p ∈ { 16 , … , 4096 } p\in\{16,\ldots,4096\} p ∈ { 16 , … , 4096 } , n = 512 n=512 n = 512 , 40 independent training sets per width; ridge λ = 10 − 2 \lambda=10^{-2} λ = 1 0 − 2 for the regularized branch. The feature draw is part of the learner’s internal randomness ξ \xi ξ .
Boosting (§ 7.3 ). Gradient boosting with exponential loss. Running example: n = 1024 n=1024 n = 1024 , R = 30 R=30 R = 30 , depth-6 trees, 200 rounds, learning rate 1 (the setting of the earlier papers) and 0.1. Real data: 300 rounds, (learning rate 1, depth 6) and (learning rate 0.1, depth 3); the figures show the latter. The old coordinate is the normalized empirical I S ( F ; X ) / H S ( X ) = H S ( F ) / log 2 n I_{S}(F;X)/H_{S}(X)=H_{S}(F)/\log_{2}n I S ( F ; X ) / H S ( X ) = H S ( F ) / log 2 n of the earlier papers, computed on the training data with the real-valued score binned into 100 bins, as in those papers.
Stress tests (§ 22.1 ). X ∼ U [ 0 , 1 ] 6 X\sim U[0,1]^{6} X ∼ U [ 0 , 1 ] 6 , η 1 ( x ) = 1 2 + 0.4 tanh ( 8 ( x 2 − 1 2 − 0.3 sin 3 π x 1 ) ) \eta_{1}(x)=\frac{1}{2}+0.4\tanh\left(8(x_{2}-\frac{1}{2}-0.3\sin3\pi x_{1})\right) η 1 ( x ) = 2 1 + 0.4 tanh ( 8 ( x 2 − 2 1 − 0.3 sin 3 π x 1 ) ) . Eighteen candidates: nine in a shared-bias family (logistic regression with five values of C C C , two linear SVMs, LDA, a ridge classifier), and nine diverse learners (k k k -NN with k = 1 , 15 k=1,15 k = 1 , 15 , random forest, extra trees, gradient boosting, RBF SVM, MLP, two trees). Each candidate is trained 10 times on independent samples of size 400. Validation: 300 points, or random subsets of 40. 12 replicates per condition; 20 random pools of 12 candidates per replicate.
Real data
Datasets. wdbc and digits from scikit-learn; OJ and Caravan (class-balanced by subsampling the majority class) from the ISLP package [37 ] ; biopsy (original Wisconsin breast cancer). For Protocol B we add ten benchmarks from PMLB [56 ] not used before: twonorm, ring, magic, phoneme, spambase, churn, waveform-40, satimage, optdigits, kr-vs-kp, each subsampled to at most 2,000 points. Features are standardized, and categorical features are one-hot encoded.
The 19 learner configurations. k k k -NN with k ∈ { 1 , 3 , 9 , 27 } k \in\{1, 3, 9, 27\} k ∈ { 1 , 3 , 9 , 27 } ; decision trees of depth 2, 4, 8 and unlimited; random forests (200 trees) with minimum leaf size 1 and 5; gradient boosting with (100 rounds, depth 3, learning rate 0.1) and (300 rounds, depth 6, learning rate 1); logistic regression with C ∈ { 0.01 , 1 , 10 4 } C \in\{0.01, 1, 10^{4}\} C ∈ { 0.01 , 1 , 1 0 4 } ; RBF SVMs with C ∈ { 1 , 10 4 } C \in\{1, 10^{4}\} C ∈ { 1 , 1 0 4 } ; 512-unit MLPs with α ∈ { 10 − 5 , 1 } \alpha\in\{10^{-5}, 1\} α ∈ { 1 0 − 5 , 1 } . The six overparameterized configurations of § 7.5 are 1-NN, the unlimited tree, the forest with leaf size 1, the (300, 6, 1) boosting, the SVM with C = 10 4 C = 10^{4} C = 1 0 4 and the MLP with α = 10 − 5 \alpha= 10^{-5} α = 1 0 − 5 . They were fixed before running the selection analysis, as the configurations designed to interpolate.
Noise models. Symmetric: each label is replaced with probability ρ \rho ρ by a uniformly random different class. Class-dependent: for binary tasks, 0 → 1 0 \to1 0 → 1 with probability 0.4 and 1 → 0 1 \to0 1 → 0 with probability 0.05; for multiclass tasks, k → k + 1 ( m o d K ) k \to k + 1 \pmod{K} k → k + 1 ( mod K ) with probability 0.35. Instance-dependent (Protocol B only): a label is flipped with probability min ( 0.5 , 0.7 u ( x ) ) \min(0.5, 0.7 u(x)) min ( 0.5 , 0.7 u ( x )) to the most confusable other class, where u ( x ) = 1 − ( p ( 1 ) ( x ) − p ( 2 ) ( x ) ) u(x) = 1 - (p_{(1)}(x) - p_{(2)}(x)) u ( x ) = 1 − ( p ( 1 ) ( x ) − p ( 2 ) ( x )) is one minus the class-probability margin of a reference random forest fit to clean data; the mean flip rate is 0.16.
Protocol A (independent samples). Clean test set 30%; validation set 20% (113–359 points), with labels corrupted by the same noise process; training pool 50%. Each configuration is trained R = 12 R = 12 R = 12 times on random halves of the pool, each with a fresh noise draw and seed; all configurations share the same halves and draws. Six random splits per dataset and noise setting (symmetric 0.2 and 0.3; class-dependent): 60 symmetric and 30 class-dependent cases. Small validation budgets: 40 random validation points, 100 draws per case. V V V is estimated on the (unlabelled) test inputs.
Protocol B (one dataset). Five seeds per dataset and noise model (225 cases); the seed sets the subsample (datasets above 2,000 points), the train/test split, the noise draw, the holdout split and the folds (r6_cost.py for seed 0, r6_seeds.py for seeds 1–4). Clean test set 30%; the remaining 70% receive one noise draw. Each configuration is fit (i) on a random 80% of the training set (holdout on the other 20%), (ii) in 2-fold and 5-fold cross-validation, and (iii) on the full training set. Fold models also predict on the unlabelled test inputs, from which V 2 V_2 V 2 , V 5 V_5 V 5 and the consensus criteria are computed. The noise-corrected CV estimates T ^ \hat{T} T ^ from the plurality of the out-of-fold predictions of all 19 configurations. CPU time is recorded for every fit and every prediction; costs are reported relative to the holdout fit of the same candidate set. Regret uses the full refit of the chosen configuration. Paired differences between criteria are summarized by a cluster bootstrap (4,000 resamples) over the 45 dataset–noise combinations (r6_multiseed.py).
Compute. All experiments run on a 2-core CPU cloud machine; no GPU is used. Table S2 estimates the cost of one full reproduction. Where running times were recorded with the results (the running example, its 120-configuration grid, synthetic double descent, and Protocol B, whose per-case wall-clock times were logged and whose every fit and prediction was timed), we use them directly. For the other experiments, we timed a reduced run on the same machine (fewer repetitions) and scaled it linearly to the number of repetitions used in the paper. The total is about 9.8 hours of wall-clock time, or at most about 20 CPU-hours, since two cores were used; Protocol B with five seeds and its extension in § 21 .§ 6 account for about 60% of it. It excludes exploratory runs and analysis scripts; the analysis and all figures take about one minute from the stored predictions.
Table S2. Estimated compute for one full reproduction on a 2-core CPU machine. “Recorded”: timings stored with the results. “Scaled”: a reduced run, timed and scaled linearly.
Additional results
Estimating V from few training runs
We trained each of four learners on R r e f = 200 R_{\mathrm{ref}} = 200 R ref = 200 independent training sets of the running example (ε = 0.2 \varepsilon= 0.2 ε = 0.2 , n = 1024 n = 1024 n = 1024 , 5,000 test inputs), and compared estimates from random subsets of R R R runs against the plug-in value from all 200 (Figure S1 ). At R = 5 R = 5 R = 5 , the plug-in estimate recovers 77% of the reference for 1-NN, 76% for the full tree and 52% for the random forest; with the Miller–Madow correction these become 91%, 90% and 62%. From R = 20 R = 20 R = 20 , the corrected estimate is within 2% of the reference for 1-NN and the tree, and within 14% for the forest. The ranking of the four learners is the same at every R ≥ 5 R \ge5 R ≥ 5 .
Figure S1. Estimated expressed information as a fraction of the R r e f = 200 R_{\mathrm{ref}} = 200 R ref = 200 reference, against the number of independent training runs R R R . Solid: Miller–Madow corrected; dashed: plug-in. Error bars: one standard deviation over 20 random subsets.
Checks of the mechanism results
Fixed-k k k nearest neighbours (Proposition 17 ): on a one-dimensional task with η 1 ( x ) = 1 2 + 0.4 sin 2 π x \eta_1(x) = \frac{1}{2} + 0.4 \sin2\pi x η 1 ( x ) = 2 1 + 0.4 sin 2 π x and n = 20,000 n = 20{,}000 n = 20 , 000 (300 training sets), the measured E V n \mathbb{E}V_n E V n for k = 1 , 3 , 9 k = 1, 3, 9 k = 1 , 3 , 9 matches the limit E h ( min { β k ( η 1 ) , 1 − β k ( η 1 ) } ) \mathbb{E}\,h(\min\{\beta_k(\eta_1),1-\beta_k(\eta_1)\}) E h ( min { β k ( η 1 ) , 1 − β k ( η 1 )}) to within 0.003 bits (t_knn_check.py).
Rates (Proposition 18 ): with d = α = 1 d = \alpha= 1 d = α = 1 , k n = n 2 / 3 k_n = n^{2/3} k n = n 2/3 and n n n from 250 to 16,000, the fitted slopes of log E V n \log\mathbb{E}V_n log E V n and of log excess risk against log n \log n log n are −0.32 and −0.68, against the predicted − 1 3 -\frac{1}{3} − 3 1 and − 2 3 -\frac{2}{3} − 3 2 (t_theory2.py).
Averaging (Proposition S7): for 1-NN, a depth-2 tree and a misspecified logistic regression on the same one-dimensional task, the predicted excess risk of majority votes of B ∈ { 1 , 5 , 25 } B \in\{1, 5, 25\} B ∈ { 1 , 5 , 25 } independent copies matches simulation to within 0.0005 (t_ens_check.py).
Double descent on real data
Random-features least squares on digits (n = 629 n = 629 n = 629 ) and wdbc (n = 199 n = 199 n = 199 ) with 20% injected noise (Figure S2 ) reproduces § 7.2 . Test error and V V V peak together at p = n p = n p = n : on digits, error 0.88 and V = 3.07 V = 3.07 V = 3.07 bits against a ceiling of log 2 10 = 3.32 \log_{2} 10 = 3.32 log 2 10 = 3.32 bits; on wdbc, 0.47 and 0.98 bits. A small ridge removes both peaks. The Spearman correlation of V V V with test error over widths is 0.97–0.99 for minimum-norm fits. Table S3 gives the width-selection results of § 7.2 .
Table S3. Choosing the width among interpolating (minimum-norm, p ≥ n p \ge n p ≥ n ) random-features models: Spearman correlation between V V V and test error over the eight widths, regret of min-V V V †, and expected regret of a random width. Best (lowest) regret per row in bold.
Figure S2. Random-features double descent on real data with 20% label noise: clean test error (top) and expressed information (bottom) against p / n p/n p / n .
Boosting on real data
With 20% injected noise (Figure S3 ), clean test error rises from its minimum at round 10–20 to its final value on every dataset: 0.101 → \to → 0.144 (wdbc), 0.093 → \to → 0.165 (biopsy), 0.203 → \to → 0.275 (OJ) and 0.413 → \to → 0.430 (Caravan), while the old coordinate rises and then falls. V V V rises with test error; their Spearman correlation along the trajectory is 0.82–1.00.
Figure S3. Gradient boosting (exponential loss, shrinkage 0.1) on four real datasets. Rows: the old information-plane coordinate, expressed information, clean test error (dot: best round under noise). Grey: original labels; blue: 20% injected label noise.
Model selection with all 19 candidates
Table S4 gives the Protocol-A comparison with all 19 configurations as candidates. Besides holdout, min-V V V and the consensus criterion, it includes: corrected holdout (backward correction with T ^ \hat{T} T ^ estimated from the training labels); combined (the modal predictor’s noisy validation error e ^ m \hat{e}_m e ^ m plus π ˉ ( 1 − e ^ m K / ( K − 1 ) ) \bar{\pi}(1-\hat{e}_m K/(K-1)) π ˉ ( 1 − e ^ m K / ( K − 1 )) ); and gated (the one-standard-error rule on corrected holdout, then the least V V V ). As a reference that is unavailable in practice, we also report holdout with clean validation labels.
Table S4: Protocol A with all 19 configurations: selection regret in clean test error (mean over cases; lower is better). Best per column in bold (excluding the clean-label reference). †: proposed in this paper. A random choice has regret 0.10.
Table S4.
Five findings, with 95% bootstrap intervals over cases for differences from holdout:
Min-V V V alone matches holdout with ample symmetric-noise validation data (−0.002 [−0.006, 0.002]) and beats it with 40 points (−0.012 [−0.016, −0.008]). Under class-dependent noise it is worse (+0.037 [0.017, 0.059]), its predicted blind spot (Proposition S11).
Noise correction helps only under asymmetric noise , as Remark S3 predicts: under class-dependent noise, −0.006 [−0.011, −0.001] (full validation) and −0.017 [−0.023, −0.012] (40 points); with the oracle T T T , −0.010 and −0.024.
The consensus criterion has the lowest regret overall (0.0085 against 0.0219), and under symmetric noise it matches holdout with clean labels .
The consensus need not be large or include the best models : consensus from 5 or 10 random candidates gives 0.0059 and 0.0050 (symmetric) and 0.0153, 0.0123 (class-dependent); dropping the three best candidates gives 0.0057 (0.0136).
The switch rule (Section F) has regret 0.0060 over the 90 full-validation cases, against 0.0069 for the consensus criterion, 0.0097 for corrected holdout and 0.0113 for holdout; it keeps 0.0037 under symmetric noise and improves on both components under class-dependent noise (0.0106).
Protocol B with all 19 candidates (Figure 6 ). Table S5 gives mean regrets over the 225 cases. Paired differences (cluster bootstrap over the 45 dataset–noise combinations): noise-corrected minus plain 5-fold CV −0.0048 [−0.0073, −0.0025], almost all of it under class-dependent noise (−0.0113 [−0.0168, −0.0061]); consensus (2 halves) minus 2-fold CV +0.0007 [−0.0060, 0.0072]; consensus (2 halves) minus holdout −0.0106 [−0.0187, −0.0028]; consensus (5 folds) minus 5-fold CV +0.0091 [+0.0008, +0.0197]; min-V 5 V_{5} V 5 minus 5-fold CV +0.0486 [+0.0293, +0.0711]. The switch rule’s asymmetry test triggers in 7% of symmetric-noise cases, 49% of class-dependent cases and 12% of instance-dependent cases. Computing V V V or the consensus criterion from the CV fold models adds about 1% of the CV cost.
Table S5: Protocol B with all 19 configurations: mean regret over 15 datasets × 5 seeds per noise model (lower is better). Best per column in bold. Cost: median CPU time relative to one holdout fit. †: proposed in this paper.
Table S5.
Two-stage selection, and details of the CMI comparison
This subsection reports a further comparison on Protocol B (§ 7.5 ), two-stage selection , which first screens the candidates by how well they fit the training data and then applies min-V 2 V_2 V 2 among those kept, and it gives the estimation details of the comparison with CMI in § 7.6 . Both use the same 225 cases (15 datasets × 3 noise models × 5 seeds) and the same regret as Table 4 . The new fits were made with r8_screen_cmi.py; they reproduce the 2-fold models of Protocol B exactly (same data, noise, folds and seeds), so all criteria are compared on identical models.
Setup. The training set of each case is split into pairs ( a i , b i ) (a_i,b_i) ( a i , b i ) , with a i a_i a i from one fold and b i b_i b i from the other fold of the Protocol B 2-fold split. This is a supersample in the sense of Steinke and Zakynthinou [65 ] . A draw of the selection vector U ∈ { 0 , 1 } n / 2 U \in\{0,1\}^{n/2} U ∈ { 0 , 1 } n /2 gives two models, one trained on the members selected by U U U and one on the complement; the Protocol B 2-fold split is one such draw, and we add two draws with independent uniform U U U . Each model predicts on all training points and on the unlabelled test inputs.
their own halves; the legacy LMC score I S ( F ; Y ) / H S ( Y ) I_S(F;Y)/H_S(Y) I S ( F ; Y ) / H S ( Y ) on the same halves; and a label-free estimate ρ ^ \hat{\rho} ρ ^ of the noise rate, the disagreement of the plurality of all 19 configurations’ out-of-fold predictions with the noisy labels (mean absolute error 0.061).
e-CMI (evaluated CMI; Steinke and Zakynthinou, [65 ] ) is estimated per pair as the plug-in mutual information between the pair’s loss pattern ( ℓ ( a i ) , ℓ ( b i ) ) ∈ { 0 , 1 } 2 (\ell(a_i),\ell(b_i)) \in\{0,1\}^{2} ( ℓ ( a i ) , ℓ ( b i )) ∈ { 0 , 1 } 2 and the selection bit, over the models of all draws, and averaged over pairs (in nats). f-CMI (Harutyunyan et al., [32 ] ) uses the prediction pattern instead; since the labels of the pair are fixed, it equals e-CMI for binary labels, and it gives the same regrets as e-CMI among the overparameterized candidates. The two bounds used for ranking are training error plus 2 e - C M I \sqrt{2\,\mathrm{e\text{-}CMI}} 2 e - CMI (Steinke and Zakynthinou, [65 ] ) and training error plus the samplewise bound 1 n / 2 ∑ i 2 I i \frac{1}{n/2}\sum_i\sqrt{2I_i} n /2 1 ∑ i 2 I i (Hellström and Durisi, [34 ] ), with I i I_i I i the estimate for pair i i i . With one draw (two fits, identical to those of 2-fold CV and of V2 _2 2 ), the per-pair estimate is ln 2 \ln2 ln 2 if the two models’ loss patterns differ and 0 otherwise; with three draws it is a plug-in estimate from six observations per pair, which is biased upwards, more so for candidates whose held-out losses vary between draws. This bias is why e-CMI from three pairs does worse than from one (Table 5 ).
The CMI bounds are loose: for interpolators, 2 e - C M I \sqrt{2\,\mathrm{e\text{-}CMI}} 2 e - CMI is about 0.8 (10th–90th percentile 0.63–1.01, on seed 0), larger than the differences in error between candidates. With all 19 configurations, f-CMI from three pairs has regret 0.082 and the 2 f - C M I \sqrt{2\,\mathrm{f\text{-}CMI}} 2 f - CMI bound 0.055, close to the e-CMI values in Table 5 .
Findings on two-stage selection.
Screening by training fit does not rescue min-V V V in a mixed pool. Keeping only the interpolators before applying min-V 2 V_2 V 2 lowers its regret from 0.0748 to 0.0457 (−0.029 [−0.058, −0.003]), but
it remains well behind holdout (0.0326), 2-fold CV (0.0213) and 5-fold CV (0.0196; difference +0.026 [+0.015, +0.039]). Screening by the legacy LMC score, which for hard predictions is a function of the training fit, behaves in the same way (0.0461).
The reason is that, under label noise, the best candidate usually does not fit the training data well. With all 19 configurations, the best one (most often an RBF SVM with C = 1 C = 1 C = 1 , 63 of 225 cases, or a random forest with leaf size 5, 39 cases; the interpolating forest with leaf size 1 is best in 29 cases) is removed by the interpolation screen in 85% of the cases. A training-fit screen removes the regularized candidates together with the underfitting ones, so the second stage chooses the best interpolator , which is not the best candidate. A looser screen (training error below the median) keeps the best candidate in only 34% of the cases and has regret 0.0340.
The same happens with independent samples. In Protocol A (Table 4 , Panel A), restricting to interpolators and then taking the least V V V has regret 0.065 measured against the best of all 19 configurations, against 0.022 for min-V V V over all 19 and 0.011 for holdout with the full validation set (r8_protA.py). The small regret reported in Panel A of Table 4 (0.0010 under symmetric noise) is measured against the best interpolator : min-V V V chooses well among interpolators, and the training-fit screen is what loses.
A screen anchored at the estimated noise rate is harmless but adds little. Keeping candidates with training error at most ρ ^ + 0.02 \hat{\rho} + 0.02 ρ ^ + 0.02 removes only clear underfitters (17.6 of 19 kept on average) and never removes the best candidate. Followed by the consensus criterion it has regret 0.0209, on a par with 2-fold and 5-fold CV (+0.0013 [−0.0039, +0.0062] against 5-fold CV) and slightly below the consensus criterion alone (0.0220; −0.0011 [−0.0031, 0]). Followed by min-V 2 V_2 V 2 it does not help enough (0.0451), because the remaining rigid candidates still have low V V V and large modal bias.
Among overparameterized candidates the screens are unnecessary: they can only remove candidates, and the interpolation screen removes the best one in 12% of cases (regret 0.0074 against 0.0055 for min-V 2 V_2 V 2 ).
In short, the first stage of a two-stage rule must remove candidates with modal bias , not candidates with training error. Training error is a poor proxy for modal bias under label noise, because good candidates do not fit noisy labels. The consensus criterion estimates modal bias directly, and this is why it, rather than a training-fit screen followed by min-V V V , is our recommendation for mixed pools.
Stress tests of the consensus criterion
Redundant candidates (Figure S4 , left). With at most a quarter of the pool from the shared-bias family, the plain consensus criterion is competitive (regret 0.0029, against 0.0025 for holdout with 300 labels and 0.0063 with 40). Once half the pool shares the bias, its regret jumps to 0.049 and the consensus error rises from δ = 0.080 \delta= 0.080 δ = 0.080 to 0.148. Adaptive clustering lowers the regret to 0.0093, below holdout with 40 labels (0.0104). With two thirds or more of the pool redundant, it helps but is not enough (0.022–0.032). In all 1,248 pools, the candidate with the smallest disagreement had modal-bias mass within 2 δ 2\delta 2 δ of the best, as Proposition S10 guarantees.
Figure S4. Stress tests of the consensus criterion (synthetic task with known Bayes classifier; means and standard errors over 12 replicates). Left: a growing share of candidates with a common misspecification. Right: growing asymmetric label noise; δ T \delta_T δ T is the shared-bias mass of Proposition S11.
Asymmetric noise (Figure S4 , right). Flipping labels 0 → 1 with probability f f f grows the shared-bias mass from δ T = 0 \delta_T = 0 δ T = 0 to 0.15. The consensus criterion degrades from 0.0029 to 0.070; holdout on noisy labels is robust up to f = 0.3 f = 0.3 f = 0.3 but fails at f = 0.4 f = 0.4 f = 0.4 (0.051); backward-corrected holdout with the true T T T stays below 0.008.
Extension to regression
The main paper treats classification, with a brief squared-loss statement in § 4.5 . This section works out what carries over to regression: a storage statement (Proposition S12), a label-free selection rule with a guarantee (Proposition S13), a regression consensus criterion (Proposition S14), and one experiment. In short, storage carries over in a stronger form, and selection carries over only when the candidates have similar bias.
Setting. Let Y ∈ R Y \in\mathbb{R} Y ∈ R , with squared loss and f ∗ ( x ) = E [ Y ∣ X = x ] f^{*}(x) = \mathbb{E}[Y \mid X = x] f ∗ ( x ) = E [ Y ∣ X = x ] , so the excess risk of a predictor f f f is E ( f ( X ) − f ∗ ( X ) ) 2 \mathbb{E}(f(X) - f^{*}(X))^{2} E ( f ( X ) − f ∗ ( X ) ) 2 . A learner outputs f W f_W f W , random through the sample and the seed. Write f ˉ ( x ) = E f W ( x ) \bar{f}(x) = \mathbb{E}f_W(x) f ˉ ( x ) = E f W ( x ) for its mean prediction, v ( x ) = Var f W ( x ) v(x) = \operatorname{Var} f_W(x) v ( x ) = Var f W ( x ) for its variance and B ( x ) = ( f ˉ ( x ) − f ∗ ( x ) ) 2 B(x) = (\bar{f}(x)-f^{*}(x))^{2} B ( x ) = ( f ˉ ( x ) − f ∗ ( x ) ) 2 for its squared bias. The mean prediction plays the role of the modal prediction, and B B B the role of modal bias. Theorem 13 gives v ( x ) = lim σ → ∞ 2 σ 2 V σ ( x ) v(x) = \lim_{\sigma\to\infty} 2\sigma^{2}V_{\sigma}(x) v ( x ) = lim σ → ∞ 2 σ 2 V σ ( x ) and the exact decomposition
ER ( f W ) − R ∗ = E B ( X ) + E v ( X ) . (5) \operatorname{ER}(f_W) - R^{*} = \mathbb{E}B(X) + \mathbb{E}v(X). \tag*{(5)} ER ( f W ) − R ∗ = E B ( X ) + E v ( X ) . (5)
So in regression the variance plays the role of V V V : it is expressed information measured at low resolution.
Storage
Proposition S12 (Storage of label noise, regression). Assume Y ∣ X Y \mid X Y ∣ X has a density with finite conditional differential entropy h ( Y ∣ X ) h(Y \mid X) h ( Y ∣ X ) , and let D = 1 n ∑ i = 1 n E ( f W ( X i ) − Y i ) 2 D = \frac{1}{n}\sum_{i=1}^{n}\mathbb{E}(f_W(X_i) - Y_i)^{2} D = n 1 ∑ i = 1 n E ( f W ( X i ) − Y i ) 2 be the learner’s expected training MSE.
(a) For every learner, I ( W ; Y n ∣ X n ) ≥ n [ h ( Y ∣ X ) − 1 2 log ( 2 π e D ) ] + I(W;Y^{n} \mid X^{n}) \ge n\left[h(Y \mid X) - \frac{1}{2}\log(2\pi eD)\right]_{+} I ( W ; Y n ∣ X n ) ≥ n [ h ( Y ∣ X ) − 2 1 log ( 2 π eD ) ] + . With Gaussian noise of variance σ 2 \sigma^{2} σ 2 , the bound is n 2 log ( σ 2 / D ) \frac{n}{2}\log(\sigma^{2}/D) 2 n log ( σ 2 / D ) when D ≤ σ 2 D \le\sigma^{2} D ≤ σ 2 . In particular, every exact interpolator (D = 0 D = 0 D = 0 ) stores infinitely much information about its training labels.
(b) Fix Δ > 0 \Delta> 0 Δ > 0 and let Y Δ = Δ ⌊ Y / Δ + 1 2 ⌋ Y^{\Delta} = \Delta\left\lfloor Y/\Delta+ \frac{1}{2} \right\rfloor Y Δ = Δ ⌊ Y /Δ + 2 1 ⌋ be the labels rounded to the grid Δ Z \Delta\mathbb{Z} Δ Z . If the learner interpolates at resolution Δ \Delta Δ , i.e. f W ( X i ) f_W(X_i) f W ( X i ) rounds to Y i Δ Y_i^{\Delta} Y i Δ for every i i i (for example, if it interpolates the Y i Y_i Y i exactly), then
I ( W ; Y n ∣ X n ) ≥ I ( W ; ( Y Δ ) n ∣ X n ) = n H ( Y Δ ∣ X ) = n [ h ( Y ∣ X ) + log 1 Δ + o ( 1 ) ] ( Δ → 0 ) . I(W;Y^n \mid X^n) \ge I(W;(Y^{\Delta})^n \mid X^n) = nH(Y^{\Delta}\mid X)
= n\left[h(Y\mid X)+\log\frac{1}{\Delta}+o(1)\right] \qquad(\Delta\to0). I ( W ; Y n ∣ X n ) ≥ I ( W ; ( Y Δ ) n ∣ X n ) = n H ( Y Δ ∣ X ) = n [ h ( Y ∣ X ) + log Δ 1 + o ( 1 ) ] ( Δ → 0 ) .
Proof. (a) The fitted values Y ^ i = f W ( X i ) \widehat{Y}_i=f_W(X_i) Y i = f W ( X i ) are functions of ( W , X n ) (W,X^n) ( W , X n ) , so I ( W ; Y n ∣ X n ) ≥ I ( Y ^ n ; Y n ∣ X n ) I(W;Y^n\mid X^n)\ge I(\widehat{Y}^n;Y^n\mid X^n) I ( W ; Y n ∣ X n ) ≥ I ( Y n ; Y n ∣ X n ) . Given X n X^n X n the labels are independent, so I ( Y ^ n ; Y n ∣ X n ) ≥ ∑ i I ( Y ^ n ; Y i ∣ X n ) ≥ ∑ i I ( Y ^ i ; Y i ∣ X n ) I(\widehat{Y}^n;Y^n\mid X^n)\ge\sum_i I(\widehat{Y}^n;Y_i\mid X^n)\ge\sum_i I(\widehat{Y}_i;Y_i\mid X^n) I ( Y n ; Y n ∣ X n ) ≥ ∑ i I ( Y n ; Y i ∣ X n ) ≥ ∑ i I ( Y i ; Y i ∣ X n ) . For each i i i ,
I ( Y ^ i ; Y i ∣ X n ) = h ( Y i ∣ X n ) − h ( Y i ∣ Y ^ i , X n ) ≥ h ( Y ∣ X ) − h ( Y i − Y ^ i ) ≥ h ( Y ∣ X ) − 1 2 log ( 2 π e D i ) , I(\widehat{Y}_i;Y_i\mid X^n)=h(Y_i\mid X^n)-h(Y_i\mid\widehat{Y}_i,X^n)\ge h(Y\mid X)-h(Y_i-\widehat{Y}_i)\ge h(Y\mid X)-\frac{1}{2}\log(2\pi eD_i), I ( Y i ; Y i ∣ X n ) = h ( Y i ∣ X n ) − h ( Y i ∣ Y i , X n ) ≥ h ( Y ∣ X ) − h ( Y i − Y i ) ≥ h ( Y ∣ X ) − 2 1 log ( 2 π e D i ) ,
with D i = E ( Y i − Y ^ i ) 2 D_i=\mathbb{E}(Y_i-\widehat{Y}_i)^2 D i = E ( Y i − Y i ) 2 , because conditioning reduces entropy and the Gaussian maximizes entropy for a given second moment. Summing over i i i and using the concavity of log \log log gives the bound; mutual information is non-negative, hence the positive part. With Gaussian noise h ( Y ∣ X ) = 1 2 log ( 2 π e σ 2 ) h(Y\mid X)=\frac{1}{2}\log(2\pi e\sigma^2) h ( Y ∣ X ) = 2 1 log ( 2 π e σ 2 ) .
(b) Y Δ Y^\Delta Y Δ is a function of Y Y Y , which gives the inequality. Interpolation at resolution Δ \Delta Δ makes ( Y Δ ) n (Y^\Delta)^n ( Y Δ ) n a function of ( W , X n ) (W,X^n) ( W , X n ) , so I ( W ; ( Y Δ ) n ∣ X n ) = H ( ( Y Δ ) n ∣ X n ) = n H ( Y Δ ∣ X ) I(W;(Y^\Delta)^n\mid X^n)=H((Y^\Delta)^n\mid X^n)=nH(Y^\Delta\mid X) I ( W ; ( Y Δ ) n ∣ X n ) = H (( Y Δ ) n ∣ X n ) = n H ( Y Δ ∣ X ) ; this is Theorem 5 applied to the discrete labels Y Δ Y^\Delta Y Δ . The last equality is the standard relation between the entropy of a fine quantization and differential entropy, valid for instance when Y ∣ X Y\mid X Y ∣ X has a bounded density with finite second moment.
In plain terms, storage is again decided by the training fit and not by generalization: every learner with the same training MSE faces the same lower bound. In regression the stored amount is not even finite for an interpolator; it grows by log ( 1 / Δ ) \log(1/\Delta) log ( 1/Δ ) bits per example for each refinement of the resolution. This makes the conclusion of Corollary 6, that storage-based quantities cannot separate interpolators, even starker. In the experiment of Table S8 at noise level 0.5, the weakly regularized MLP must store at least 0.28 bits per example and the random forest with leaf size 1 at least 1.05, while extra-trees, kernel ridgeless regression and distance-weighted k k k -NN interpolate exactly and store infinitely much.
Table S8. Exact decomposition on Friedman #1 for the interpolating regressors.
Selection
The rule. For each candidate j j j , train two copies on disjoint halves of the data, f j , 1 f_{j,1} f j , 1 and f j , 2 f_{j,2} f j , 2 , and compute on unlabelled inputs x 1 , … , x M x_1,\ldots,x_M x 1 , … , x M
Var ^ 2 , j = 1 M ∑ m = 1 M 1 2 ( f j , 1 ( x m ) − f j , 2 ( x m ) ) 2 . \widehat{\operatorname{Var}}_{2,j}=\frac{1}{M}\sum_{m=1}^{M}\frac{1}{2}\left(f_{j,1}(x_m)-f_{j,2}(x_m)\right)^2. Var 2 , j = M 1 m = 1 ∑ M 2 1 ( f j , 1 ( x m ) − f j , 2 ( x m ) ) 2 .
Min-variance chooses the candidate with the smallest value. The two copies are independent, so E Var ^ 2 , j \mathbb{E}\widehat{\operatorname{Var}}_{2,j} E Var 2 , j is exactly the mean variance of the learner at half the sample size. The rule uses no held-out labels, and by Theorem 13 it is min-V V V at low resolution. With R R R disjoint pairs, the R R R estimates are averaged.
Proposition S13 (Min-variance selection). Let candidates j = 1 , … , J j=1,\ldots,J j = 1 , … , J have squared biases B j = E b j ( X ) B_j=\mathbb{E}b_j(X) B j = E b j ( X ) , variances v j = E v j ( X ) v_j=\mathbb{E}v_j(X) v j = E v j ( X ) and excess risks Exc j = B j + v j \operatorname{Exc}_j=B_j+v_j Exc j = B j + v j .
(a) If all B j B_j B j are equal (in particular, if all are zero), ranking by v j v_j v j is exactly ranking by excess risk.
(b) In general, if j ^ \hat{j} j ^ minimizes estimates v ^ j \hat{v}_j v ^ j with ∣ v ^ j − v j ∣ ≤ ε |\hat{v}_j-v_j| \le\varepsilon ∣ v ^ j − v j ∣ ≤ ε for all j j j , then Exc j ^ ≤ min j Exc j + max j B j − min j B j + 2 ε \operatorname{Exc}_{\hat{j}} \le\min_j \operatorname{Exc}_j + \max_j B_j - \min_j B_j + 2\varepsilon Exc j ^ ≤ min j Exc j + max j B j − min j B j + 2 ε .
(c) If the prediction distribution at x x x is Gaussian, V σ ( x ) = 1 2 log ( 1 + v ( x ) / σ 2 ) V_\sigma(x) = \frac{1}{2}\log(1+v(x)/\sigma^2) V σ ( x ) = 2 1 log ( 1 + v ( x ) / σ 2 ) is increasing in v ( x ) v(x) v ( x ) at every resolution σ \sigma σ .
Proof. (a) is (S2). (b) Let j ∗ j^* j ∗ minimize Exc j \operatorname{Exc}_j Exc j . Then v ^ j ^ ≤ v ^ j ^ + ε ≤ v ^ j ∗ + ε ≤ v j ∗ + 2 ε \hat{v}_{\hat{j}} \le\hat{v}_{\hat{j}}+\varepsilon\le\hat{v}_{j^*}+\varepsilon\le v_{j^*}+2\varepsilon v ^ j ^ ≤ v ^ j ^ + ε ≤ v ^ j ∗ + ε ≤ v j ∗ + 2 ε , so Exc j ^ ≤ B j ^ + v j ∗ + 2 ε = Exc j ∗ + ( B j ^ − B j ∗ ) + 2 ε \operatorname{Exc}_{\hat{j}} \le B_{\hat{j}}+v_{j^*}+2\varepsilon= \operatorname{Exc}_{j^*}+(B_{\hat{j}}-B_{j^*})+2\varepsilon Exc j ^ ≤ B j ^ + v j ∗ + 2 ε = Exc j ∗ + ( B j ^ − B j ∗ ) + 2 ε . (c) is the capacity formula of the Gaussian channel. □
Proposition S14 (Regression consensus criterion). Let m ^ j = 1 2 ( f j , 1 + f j , 2 ) \hat{m}_j = \frac{1}{2}(f_{j,1}+f_{j,2}) m ^ j = 2 1 ( f j , 1 + f j , 2 ) , v ^ j ( x ) = 1 2 ( f j , 1 ( x ) − f j , 2 ( x ) ) 2 \hat{v}_j(x) = \frac{1}{2}(f_{j,1}(x)-f_{j,2}(x))^2 v ^ j ( x ) = 2 1 ( f j , 1 ( x ) − f j , 2 ( x ) ) 2 , and let c ( x ) c(x) c ( x ) be a reference function (we use the pointwise median of all candidates’ m ^ j \hat{m}_j m ^ j ). Score candidate j j j by LF j = 1 M ∑ m [ ( m ^ j ( x m ) − c ( x m ) ) 2 + 1 2 v ^ j ( x m ) ] \operatorname{LF}_j = \frac{1}{M}\sum_m [(\hat{m}_j(x_m)-c(x_m))^2+\frac{1}{2}\hat{v}_j(x_m)] LF j = M 1 ∑ m [( m ^ j ( x m ) − c ( x m ) ) 2 + 2 1 v ^ j ( x m )] . If c = f ∗ c=f^* c = f ∗ , then E LF j \mathbb{E}\operatorname{LF}_j E LF j is the excess risk of candidate j j j at half the sample size. For any c c c , with ∥ g ∥ 2 = E g ( X ) 2 \lVert g\rVert^2=\mathbb{E}g(X)^2 ∥ g ∥ 2 = E g ( X ) 2 , ∣ ∥ m ^ j − c ∥ − ∥ m ^ j − f ∗ ∥ ∣ ≤ ∥ c − f ∗ ∥ |\lVert\hat{m}_j-c\rVert-\lVert\hat{m}_j-f^*\rVert| \le\lVert c-f^*\rVert ∣ ∥ m ^ j − c ∥ − ∥ m ^ j − f ∗ ∥ ∣ ≤ ∥ c − f ∗ ∥ , so the bias part of the score is off by at most the consensus error, with no independence assumption.
Proof. E ( m ^ j − f ∗ ) 2 = B j + v j / 2 \mathbb{E}(\hat{m}_j-f^*)^2=B_j+v_j/2 E ( m ^ j − f ∗ ) 2 = B j + v j /2 pointwise (the mean of two independent copies) and E v ^ j = v j \mathbb{E}\hat{v}_j=v_j E v ^ j = v j , so E [ ( m ^ j − f ∗ ) 2 + v ^ j / 2 ] = B j + v j \mathbb{E}[(\hat{m}_j-f^*)^2+\hat{v}_j/2]=B_j+v_j E [( m ^ j − f ∗ ) 2 + v ^ j /2 ] = B j + v j at sample size n / 2 n/2 n /2 . The second claim is the triangle inequality in L 2 ( P X ) L^2(P_X) L 2 ( P X ) . □
Experiment
Design. This is a Protocol B analogue for regression: one noisy dataset and matched, measured compute (r9_regression.py).
Data. Eleven datasets: Friedman #1 (synthetic, with known f ∗ f^* f ∗ , so its regret is exact excess risk), diabetes, and nine PMLB regression benchmarks (echoMonths, 2dplanes, puma8NH, cpu_act, wind, pollen, houses, fried, mv). Targets are standardized and at most 1,000 training points are used. A 30% test set keeps the original targets. The training targets receive Gaussian noise with standard deviation 0.5 or 1, in units of the target’s standard deviation. With five seeds this gives 110 cases.
Candidates. 22 regressors. Twelve are designed to interpolate: 1-NN, distance-weighted 5-NN and 25-NN, a full tree, extra-trees, a random forest without bootstrap, a random forest with leaf size 1, gradient boosting (300 depth-6 trees, learning rate 1), kernel ridgeless regression with RBF and with Laplace kernel, min-norm random ReLU features (p = 4 n p=4n p = 4 n ), and a weakly regularized 512-unit MLP. The other ten are regularized: k k k -NN, shallower trees, a random forest with leaf size 5, shrunk boosting, kernel ridge, linear ridge, and an MLP with weight decay.
The analysis (r9_analyse.py) was fixed before the results were computed. The exact decomposition on Friedman #1 (Table S8 , Figure S5 ) uses 10 independent training samples of size 500 per learner (r9_exact.py).
Figure S5. Excess risk against variance for the interpolating regressors of Table S8 (RBF ridgeless regression omitted at noise level 1, where its excess risk is 4.9). Dashed: excess = variance; the vertical distance to it is the squared bias (colour).
Table S7: Selection among regressors (110 cases; mean regret in clean test MSE, in units of the target variance; lower is better). “Labels”: uses held-out labels. “Exact” and “cost” are for the 7-interpolator pool (cases of 110 in which the best candidate was chosen; median CPU time relative to one holdout fit). Best per column in bold. The median-candidate row gives the regret of a typical candidate; the mean is dominated by catastrophic interpolators (RBF ridgeless regression and min-norm random features have test MSE above 10 in 40 and 22 cases). †: proposed in this paper.
Table S8: Exact decomposition on Friedman #1 for the interpolating regressors (10 independent training samples of size 500; standardized units), sorted by excess risk at noise level 0.5. “Storage ≥”: the lower bound of Proposition S12(a), in bits per example, at noise level 0.5. V a r ^ 2 \widehat{\mathrm{Var}}_2 Var 2 : the two-halves estimate from a single dataset.
Findings. Brackets give 95% cluster-bootstrap intervals (resampling the 22 dataset–noise combinations) for paired differences.
Among the seven standard interpolators, min-variance is competitive, and best at high noise. Its regret is 0.0038, against 0.0088 for holdout (−0.0050 [−0.0115, +0.0005]), 0.0018 for 2-fold CV (+0.0020 [0, +0.0050]) and 0.0026 for 5-fold CV (+0.0012 [−0.0022, +0.0047]), at the cost of 2-fold CV. At noise level 1 it ties for best with 2-fold CV (0.0017) and beats 5-fold CV (0.0038) and holdout (0.0111); at noise level 0.5 it is behind cross-validation. This pool is easy, though: the random forest with leaf size 1 or the MLP is best in every case, and all criteria except the consensus criterion choose the best candidate in at least 96 of the 110 cases.
When the pool contains smoothed interpolators, min-variance fails. With all twelve interpolators its regret is 0.095, against 0.008–0.020 for the labelled criteria. It picks distance-weighted 25-NN in 107 of the 110 cases, the interpolator with the least variance and the most bias (Remark S4). On Friedman #1 the squared bias of the interpolators ranges from 0.04 to 0.31, which is large compared with the differences in variance among the good ones.
The consensus criterion repairs most of this failure, but does not reach cross-validation. It lowers the regret to 0.026 with twelve interpolators and to 0.035 with all 22 (min-variance: 0.108), but 2-fold CV (0.012 and 0.016) remains better. Robust variants of the consensus (the median over interpolators only, a trimmed mean, the median over the more stable half; weight 1 2 \frac{1}{2} 2 1 or 1 on the variance term) give 0.020–0.030 with twelve interpolators. A plain mean fails (0.09), because catastrophic interpolators pull it away.
Averaging over three pairs does not help (0.0044 and 0.094), unlike in classification (§ 7.6 ): the bottleneck is bias, not the noise of the variance estimate.
The exact decomposition behaves as expected (Table S8 , Figure S5 ). 1-NN, the full tree, boosting with learning rate 1, min-norm random features and RBF ridgeless regression are tempered or catastrophic through their variance. Among the good interpolators, bias and variance are
comparable. The two-halves estimate tracks the full-size variance with a modest upward drift, since it measures the variance at half the sample size.
In summary, the storage half of the framework carries over to regression unchanged, and in a stronger form. The selection half carries over only partly: min-variance works when the interpolators being compared have similar bias, especially at high noise. Unlike in classification, interpolation does not keep bias small in regression, so in general a bias estimate is needed, and even with the consensus criterion 2-fold cross-validation of the same cost is better. Part of the reason is that additive zero-mean label noise only shifts held-out MSE by the constant σ 2 \sigma^2 σ 2 , so it leaves the ranking by cross-validation unbiased, and validation on noisy labels is less handicapped than it is in classification.
Code package
The code package, available at https://github.com/nnikolaou/GLMC , contains every script used for the paper, the result files, and the figure scripts. Table S9 maps each result to its script. The README.md in the package gives installation and run instructions; in brief:
Table S9. Table S9: Map from results to scripts (all in code/).
Table S6. Two-stage selection on Protocol B (225 cases; mean regret in clean test error, lower is better). Columns 2–5: all 19 configurations, by noise model; column 6: the six overparameterized configurations of Table 4 , Panel B. Best per column in bold among the criteria shown; with all 19 candidates, noise-corrected 5-fold CV remains best overall (0.0149; Table S5 ). Cost: median CPU time relative to one holdout fit, for the 19-candidate pool. *The consensus criterion uses the consensus of all 19 configurations (with the six-candidate pool its cost is 2.39). †: proposed in this paper.
Table S7. Selection among regressors.
pip install -r requirements.txt
python data/fetch_pmlb.py # ten PMLB datasets for Protocol B
bash run_all.sh figures # figures from the stored results (minutes)
bash run_all.sh all # all experiments from scratch (~10 h on 2 cores)
All scripts are seeded. The stored JSON results reproduce every number in the paper; the large intermediate prediction files (*.npz) are regenerated by the experiment scripts.