Loss-difference conditional mutual information (ld-CMI) uses the smallest of the standard observations in the supersample hierarchy of generalization bounds: it measures what a learner's loss differences reveal about which candidate of each pair it was trained on. Accuracy is known to force information into the model; data processing does not carry such lower bounds to losses. We show, by bounding three moments of the loss differences, that accuracy also forces ld-CMI. For linear predictors with a smooth convex loss of nonzero slope at zero, such as the logistic loss, plus a regularizer whose curvature and growth are both of power r≥2, on product distributions over a scaled sign cube in dimension at least linear in n, every proper learner with expected excess risk at most ε on these distributions at the optimal sample size n≍ε−2+2/r has worst-case ld-CMI of order n bits, and Θ(n/(1+(τ/ε)2)) bits under Gaussian noise of standard deviation τ on the loss differences. The same holds without a regularizer, at n≍ε−2. Consequently, range-scaled ld-CMI bounds cannot vanish on these distributions, although every proper learner's generalization gap is O(n−1/2). We also show that model-level information does not determine noisy loss-difference information, and that the growth, slope and dimension conditions are needed, the last up to a logarithm.
Figures & tables
Work
Observable and learners
Instance; dimension
Attias et al. (2024)
I(θ;U∣Z)=Ω(ε−2) or Ω(ε−1) , also per sample (the first for proper learners), for every learner accurate with high probability
affine and strongly convex losses on the sign cube; d≥Ω(n2logn) a
Voitovych et al. (2025)
tracer recall Ω(n) from (θ,z,μ) , for every learner with expected excess risk O(n−1/2)
affine loss with parameters in a cube, sparse signs; d≳nlog(1/ξ)
Haghifam et al. (2023) ; Wang & Mao (2023b)
non-vanishing evaluated-CMI bounds; signs of loss differences; gradient descent
one-hot convex Lipschitz instance; d=2n2
This paper
Θ(n/(1+(τ/ε)2)) for three information measures of X+τG and every proper learner accurate on the family
smooth convex links, power- r regularizers, product laws on the scaled sign cube; n≍ε−2+2/r , d≳n
Table 1: What Accuracy Is Known to Force. Each row is a lower bound for every learner of the stated kind; only the last row allows observation noise, and it has a matching upper bound at every noise level.
Figure 1: Structure of the Proof. Shaded boxes are hypotheses; Section 6 shows that the slope and growth conditions are needed, and the dimension condition up to a logarithm.
Figure 2: Measurements at d=64n . Values are averages over the prior; bars are 95% intervals. (a) Lower-bound estimates of the bits per pair ι against τ/(M/n) for ridge ERM (filled) and logistic ridge ERM (open); shaded: between the two halves of Theorem 6 at each learner’s own M , V and Vres . (b) Ridge ERM at τ=0 : the gap, its bounds 4L/n and EΠVp/n , and the lower bound 2L2ln2ι on the range-scaled ld-CMI bounds; L=1 .
Appendix figures & tables8 assets
Supplementary material from the paper’s appendix.
Appendix
Link
ϕ(t)
b
L
H
logistic
ln(1+e−t)
1/2
(1+e−1)−1
1/4
exponential
e−t
1
e
e
squared
(1−t)2/2
1
2
1
affine
−t
1
1
0
Appendix
Table E.1: Links and Their Constants. Admissible constants of Assumption 2 : b=−ϕ′(0) , L≥max[−1,1]∣ϕ′∣ and H≥max[−1,1]ϕ′′ .
Learner, dimension
n
d
Trials
Pairs
Seed
Runtime (s)
ridge ERM, d=32n
100
3200
2000
200000
10100
104.7†
300
9600
600
180000
10300
85.8†
1000
32000
200
200000
11000
123.3†
3000
96000
40
120000
13000
139.6†
ridge ERM, d=64n
50
3200
4000
200000
17050
198.1†
100
6400
2000
200000
17100
188.7†
Appendix
Table I.1: The Runs. Runtimes marked † include a membership test that this paper does not use; it draws 2000 fresh points per trial after the release is recorded. The runtime marked ‡ is the sum of four chunks of 50 trials, run in parallel in 741.2 to 742.5 s each.
Learner, dimension
n
ι(0) [95% interval]
Lower /ι
Upper /ι
In
Slope
cfit
afit
ridge ERM, d=32n
100
0.7049 [0.7017, 0.7080]
0.672
1.822
16
−1.991
0.713
1.000
300
0.6924 [0.6890, 0.6959]
0.673
1.797
16
−1.978
0.697
1.023
1000
0.6865 [0.6831, 0.6899]
0.675
1.801
16
−1.875
0.696
1.000
3000
0.6849 [0.6806, 0.6891]
0.675
1.802
16
−1.985
0.690
1.000
ridge ERM, d=64n
50
0.9133 [0.9113, 0.9154]
0.632
1.476
16
−1.936
0.929
0.871
100
0.9063 [0.9042, 0.9084]
0.631
1.454
16
−1.986
0.924
0.871
Appendix
Table I.2: Results per Run. ι(0) : bits per pair at τ=0 , with its 95% interval. Lower /ι and upper /ι : smallest ratio of the lower half and largest ratio of the upper half of Theorem 6 , at the learner’s own budgets, to ι , over the noise levels with ι≥0.01 . In: noise levels, of 16, at which ι lies in the bracket up to its 95% intervals. Slope, cfit , afit : tail slope and fitted constants (Appendix I.3 ). The runs at d=32n do not meet the dimension condition d≥64n of Theorem 3 for these learners; Theorem 6 holds in every dimension (Appendix I.2 ).
Figure I.1: Total Information against n . Totals nι in bits (prior averages of lower-bound estimates, with 95% intervals) against n at d=64n for ridge ERM (filled) and logistic ridge ERM (open), at τ=0 , τ=M/n and τ=nM/(2n) with each learner’s own M . Shaded: between the lower and upper halves of Theorem 6 at the learners’ own budgets. Values at τ>0 are interpolated linearly in log–log coordinates between neighbouring noise levels of the grid.
n
n2/3M/n
ι(0) [95% interval]
Lower /ι
Upper /ι
In
Slope
cfit
afit
50
0.406
0.9133 [0.9113, 0.9154]
0.632
1.410
24
−1.967
0.928
0.871
100
0.444
0.9063 [0.9042, 0.9084]
0.632
1.383
22
−2.081
0.920
0.851
300
0.470
0.8965 [0.8935, 0.8996]
0.633
1.388
22
−1.952
0.905
0.851
1000
0.478
0.8910 [0.8885, 0.8935]
0.633
1.488
24
−2.048
0.892
0.891
3000
0.480
0.8881 [0.8851, 0.8910]
0.635
1.400
24
−1.945
0.899
0.891
Appendix
Table I.3: The Quartic Learner on the Supersamples of the Ridge ERM Runs at d=64n . n2/3M/n : the per-pair signal in units of n−2/3 . The other columns are those of Table I.2 , at the learner’s own budgets and over its 24 noise levels (In: of 24); the slope uses five to seven levels. The column ι(0) nearly coincides with that of ridge ERM in Table I.2 : at τ=0 the release is the ridge release times ∥Zˉ∥−2/3 , which is close to a function of the law.
Figure I.2: The Quartic Learner on the Ridge Supersamples. The learner θ(4)=∥Zˉ∥−2/3Zˉ at d=64n , averaged over the prior; bars are 95% intervals. (a) Lower-bound estimates of the bits per pair ι of X(4)+τG against τ/(M/n) , with the learner’s own M ; shaded: between the two halves of Theorem 6 at its own M , V and Vres ; open: ridge ERM, as in Figure 2 (a). (b) Totals nι at τ=n−2/3 for the releases X(4) and X(2) of the two learners on the same supersamples, with the bounds 3n1/3 on X(2) at every law and n/8 on X(4) at the zero-mean law of Proposition H.5 (v).
Result
Statement
Consequence for X+τG
Livni (2023) , Thm. 1
For 0<ε<1/54 , every learner with expected excess risk at most ε and sample complexity n(ε) has, for some law on the scaled sign cube in dimension d and a convex Lipschitz loss, quadratic in the construction, I(θ;Sn)≥∑iI(θ;Zi)=Ω~(d/(ε5n(ε)6)) . Lower bounds on the conditional information are left open.
None: I(θ;Sn)≥I(θ;U∣Z) , so not even the conditional model information is bounded below.
Attias et al. (2024) , Thms. 4.1–4.2, 4.5–4.6, Cors. 5.6–5.7
Learners whose excess risk, at every law on the scaled sign cube, is at most ε with probability at least 1−δ′ , for the affine loss −⟨θ,z⟩ on the unit ball with δ′≤ε (Thm. 4.1), or for the strongly convex loss ∥θ∥2/2−⟨θ,z⟩ on Rd with δ′=O(n−2) (Thm. 4.2); every sample size at least the sample complexity of the learner; d≥Ω(n2logn) . Then I(θ;U∣Z)=Ω(ε−2) and Ω(ε−1) , respectively, and the same orders hold for its individual-sample form (Cors. 5.6–5.7, the first for proper learners). ξ -sound adversaries, which read θ , the point and the data law and flag any of the fresh points with probability at most ξ , certify recall of the same orders with probability Ω(1) up to logarithmic factors (Thms. 4.5–4.6) if d≥Ω(n2log(n/ξ)) and, for the affine loss, δ′<ε and n equals the learner’s sample complexity, assumed of order log(1/δ′)/ε2 .
Upper bound only: Icand(X+τG)≤I(θ;U∣Z) by ( 4 ).
Voitovych et al. (2025) , Thm. 2.7
Affine loss, with parameters in the largest cube inscribed in a unit ℓs ball, s≥2 , and sparse sign data. In the Euclidean case, for ξ<1/e and 1/(6n)≤ε≤min{c(d/(n2log(1/ξ)))1/2,1/6} , with a constant c , every learner with expected excess risk at most ε has a tracer that reads θ , the point and the population mean, with false-positive rate at most ξ and expected recall Ω(ε−2) . At ε≍n−1/2 this requires d≳nlog(1/ξ) and gives recall Ω(n) .
The decisions are functions of θ , the point and the mean, not of the release, and involve no τ .
Voitovych et al. (2025) , Thm. 3.5
Recall bounds derived from a lower bound on the trace value, the mean tracer score of the training points, and a bound on the sum of squared scores (Lemma 3.4), through a counting inequality of Paley–Zygmund type (Lemma A.11).
The two moments that Theorem 6 turns into information (Remark J.1 ).
Haghifam et al. (2023) , Thm. 17
Gradient descent with n2 steps of size n−3/2 on the loss −⟨θ,z⟩ over the unit ball, with data among the standard basis vectors of R2n2 : its evaluated-CMI bounds do not vanish, while its generalization error is O(n−1/2) . They also show that analysing a surrogate whose final iterate is corrupted by Gaussian noise cannot establish minimax rates for gradient descent.
One algorithm on one instance, at τ=0 , with no upper bound.
Wang & Mao (2023b) , Ex. 1 and App. F
On the algorithm and instance of the previous row (their Example 1), with constant probability the sign of Xi reveals Ui (Appendix F).
As in the previous row.
Appendix
Table J.1: Exact Statements of the Results Closest to Theorem 3
Result
Declarations
Assumption 2
NativeLinkClass , NativeRegularizerClass
Section 2
signProductLaw (the law Dp ), superMeasure (the supersample), nativeAccurateLearners (the learners of Theorem 3 )
Definition 1
nativeLossRelease ; releaseInfoI , releaseInfoJ , releaseInfoS , built on mutualInfo and condMutualInfo
native_loss_information_law_local (Assumption 2 as stated), native_loss_information_law ( ϕ and g measurable), native_loss_information_law_infimum (infimum over a class), native_loss_information_prior_averaged_local (the lower bound on average over the prior); nativeWorstInformation (the worst case); mainDimensionConstant_eq_of_le_four ( Cdim=32 when b≤4 )
Appendix D.7
Theorem 3 at ε1 : native_loss_information_law_paper_threshold . The bound ( 42 ) and the positivity of M on (0,ε1] : explicit_threshold_bound , paperThresholdBracket_anti , native_signed_budget_threshold . The bracket ( 43 ): explicit_bracket . The limits ( 44 ) and the bounds over the regime: explicit_schedule_limits , explicit_regime_limits . Monotonicity in d : native_budgets_mono_dim . Quartic logistic learning, the limits and the threshold 6.0⋅10−4 : quartic_schedule_limits , quartic_bracket_root
Appendix
Table K.1: Results of the Paper and the Lean Declarations That Prove Them
Information-theoretic generalization bounds based on the supersample construction are a central tool for algorithm-dependent generalization analysis in the batch i.i.d.~setting. However, existing supersample conditional mutual information (CMI) bounds do not directly apply to sequential decision-making problems such as online learning, streaming active learning, and bandits, where data are revealed adaptively and the learner evolves along a causal trajectory. To address this limitation, we develop a sequential supersample framework that separates the learner filtration from a proof-side enlargement used for ghost-coordinate comparisons. Under a row-wise exchangeability assumption, the sequential generalization gap is controlled by sequential CMI, a sum of roundwise selector--loss information terms. We also establish a Bernstein-type refinement that yields faster rates under suitable variance conditions. The selector-SCMI proof strategy applies to online learning, streaming active learning with importance weighting, and stochastic multi-armed bandits.
Futoshi Futami, Masahiro Fujisawa
The University of Osaka / RIKEN AIP / The University of Tokyo · The University of Osaka / RIKEN AIP
Information theory plays a central role in establishing fundamental limits on what any learning or estimation algorithm can -- and cannot -- achieve, regardless of computational power. In this chapter, we provide an introduction to these connections. End-of-chapter exercises makes the material suitable for both classroom use and self-study. We begin by introducing concentration inequalities along with the notions of covering and packing in metric spaces, and the associated concept of metric entropy. These tools are essential for our analysis. We then introduce the learning-theoretic framework and derive upper bounds on generalization error in terms of metric entropy, Rademacher complexity, and the VC dimension, as well as mutual information and relative entropy. Finally we discuss the minimax estimation framework and establish lower bounds on minimax risk using Fano's inequality, yielding bounds in terms of relative entropy and covering and packing numbers. This manuscript contains preprint of a chapter under consideration for inclusion in the forthcoming third edition of Cover and Thomas's Elements of Information Theory, posted with permission from Wiley. It would follow the chapter posted at arXiv:2605.02989 . The table of contents of the new edition can be found at: https://docs.google.com/document/d/1L-m4oQEJw1PJhoxBeMwrrBD8S_HmvzMEkPbYvS24980/edit?usp=sharing . For feedback, please contact abbas@ee.stanford.edu.
A learner does not only fit data; it also determines how strongly the training sample may shape its output and how much distortion it can hedge. We study this relation as a bounded-rational decision problem whose primitive object is the induced channel from samples to outputs. The learner's response law determines which changes in this channel are cheap or costly, and therefore induces both a lower tradeoff curve between training loss and sample dependence and a matched upper certificate curve. When the response law is represented by an f-divergence regularizer, these curves live in the regularizer's native information geometry, with KL as the special case corresponding to Shannon mutual information. We show how the hedge and the two curves can be recovered from black-box behavior by observing responses to scaled losses and local loss perturbations. In learning, population loss is empirical loss plus the distortion induced by the particular training sample. The recovered hedge gives a practical certificate when it covers that distortion. Thus generalization is treated as a testable hedging property of the learner's own response law.