An Accuracy--Information Tradeoff for Loss-Difference Conditional Mutual Information

Hazar Yueksel

cs.LGOct 6, 2026

An Accuracy--Information Tradeoff for Loss-Difference Conditional Mutual Information

Authors: Hazar Yueksel

Abstract

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\ge2$ , on product distributions over a scaled sign cube in dimension at least linear in $n$ , every proper learner with expected excess risk at most $\varepsilon$ on these distributions at the optimal sample size $n\asymp\varepsilon^{-2+2/r}$ has worst-case ld-CMI of order $n$ bits, and $Θ(n/(1+(τ/\varepsilon)^2))$ bits under Gaussian noise of standard deviation $τ$ on the loss differences. The same holds without a regularizer, at $n\asymp\varepsilon^{-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(\widehat{\theta};U\mid\widetilde{Z})=\Omega(\varepsilon^{-2})$ or $\Omega(\varepsilon^{-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\geq\Omega(n^{2}\log n)$ a
Voitovych et al. (2025)	tracer recall $\Omega(n)$ from $(\widehat{\theta},z,\mu)$ , for every learner with expected excess risk $O(n^{-1/2})$	affine loss with parameters in a cube, sparse signs; $d\gtrsim n\log(1/\xi)$
Haghifam et al. (2023) ; Wang & Mao (2023b)	non-vanishing evaluated-CMI bounds; signs of loss differences; gradient descent	one-hot convex Lipschitz instance; $d=2n^{2}$
This paper	$\Theta(n/(1+(\tau/\varepsilon)^{2}))$ for three information measures of $X+\tau G$ and every proper learner accurate on the family	smooth convex links, power- $r$ regularizers, product laws on the scaled sign cube; $n\asymp\varepsilon^{-2+2/r}$ , $d\gtrsim 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.

Panel of Figure 1 — 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.

Panel of Figure 2 — 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 $\iota$ against $\tau/(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 $V_{\mathrm{res}}$ . (b) Ridge ERM at $\tau=0$ : the gap, its bounds $4L/\sqrt{n}$ and $\sqrt{\mathbb{E}_{\Pi}V_{p}/n}$ , and the lower bound $2L\sqrt{2\ln 2}\,\iota$ on the range-scaled ld-CMI bounds; $L=1$ .

Appendix figures & tables8 assets

Supplementary material from the paper’s appendix.

Appendix

Link	$\phi(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=-\phi^{\prime}(0)

L\geq\max_{[-1,1]}|\phi^{\prime}|

and

H\geq\max_{[-1,1]}\phi^{\prime\prime}

Learner, dimension	$n$	$d$	Trials	Pairs	Seed	Runtime (s)
ridge ERM, $d=32n$	100	3200	2000	200000	10100	$104.7^{\dagger}$
	300	9600	600	180000	10300	$85.8^{\dagger}$
	1000	32000	200	200000	11000	$123.3^{\dagger}$
	3000	96000	40	120000	13000	$139.6^{\dagger}$
ridge ERM, $d=64n$	50	3200	4000	200000	17050	$198.1^{\dagger}$
	100	6400	2000	200000	17100	$188.7^{\dagger}$

Appendix

Table I.1: The Runs. Runtimes marked

\dagger

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

\ddagger

is the sum of four chunks of 50 trials, run in parallel in 741.2 to 742.5 s each.

Learner, dimension	$n$	$\iota(0)$ [95% interval]	Lower $/\iota$	Upper $/\iota$	In	Slope	$c_{\mathrm{fit}}$	$a_{\mathrm{fit}}$
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.

\iota(0)

: bits per pair at

\tau=0

, with its 95% interval. Lower

/\iota

and upper

/\iota

: smallest ratio of the lower half and largest ratio of the upper half of Theorem 6 , at the learner’s own budgets, to

\iota

, over the noise levels with

\iota\geq 0.01

. In: noise levels, of 16, at which

\iota

lies in the bracket up to its 95% intervals. Slope,

c_{\mathrm{fit}}

a_{\mathrm{fit}}

: tail slope and fitted constants (Appendix I.3 ). The runs at

d=32n

do not meet the dimension condition

d\geq 64n

of Theorem 3 for these learners; Theorem 6 holds in every dimension (Appendix I.2 ).

Panel of Figure 7 — Figure I.1: Total Information against $n$ . Totals $n\iota$ 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 $\tau=0$ , $\tau=M/n$ and $\tau=\sqrt{n}\,M/(2n)$ with each learner’s own $M$ . Shaded: between the lower and upper halves of Theorem 6 at the learners’ own budgets. Values at $\tau>0$ are interpolated linearly in log–log coordinates between neighbouring noise levels of the grid.

$n$	$n^{2/3}M/n$	$\iota(0)$ [95% interval]	Lower $/\iota$	Upper $/\iota$	In	Slope	$c_{\mathrm{fit}}$	$a_{\mathrm{fit}}$
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

n^{2/3}M/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

\iota(0)

nearly coincides with that of ridge ERM in Table I.2 : at

\tau=0

the release is the ridge release times

\lVert\bar{Z}\rVert^{-2/3}

, which is close to a function of the law.

Panel of Figure 9 — Figure I.2: The Quartic Learner on the Ridge Supersamples. The learner $\widehat{\theta}^{(4)}=\lVert\bar{Z}\rVert^{-2/3}\bar{Z}$ at $d=64n$ , averaged over the prior; bars are 95% intervals. (a) Lower-bound estimates of the bits per pair $\iota$ of $X^{(4)}+\tau G$ against $\tau/(M/n)$ , with the learner’s own $M$ ; shaded: between the two halves of Theorem 6 at its own $M$ , $V$ and $V_{\mathrm{res}}$ ; open: ridge ERM, as in Figure 2 (a). (b) Totals $n\iota$ at $\tau=n^{-2/3}$ for the releases $X^{(4)}$ and $X^{(2)}$ of the two learners on the same supersamples, with the bounds $3n^{1/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+\tau G$
Livni (2023) , Thm. 1	For $0<\varepsilon<1/54$ , every learner with expected excess risk at most $\varepsilon$ and sample complexity $n(\varepsilon)$ has, for some law on the scaled sign cube in dimension $d$ and a convex Lipschitz loss, quadratic in the construction, $I(\widehat{\theta};S_{n})\geq\sum_{i}I(\widehat{\theta};Z_{i})=\tilde{\Omega}\big(d/(\varepsilon^{5}n(\varepsilon)^{6})\big)$ . Lower bounds on the conditional information are left open.	None: $I(\widehat{\theta};S_{n})\geq I(\widehat{\theta};U\mid\widetilde{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 $\varepsilon$ with probability at least $1-\delta^{\prime}$ , for the affine loss $-\langle\theta,z\rangle$ on the unit ball with $\delta^{\prime}\leq\varepsilon$ (Thm. 4.1), or for the strongly convex loss $\lVert\theta\rVert^{2}/2-\langle\theta,z\rangle$ on $\mathbb{R}^{d}$ with $\delta^{\prime}=O(n^{-2})$ (Thm. 4.2); every sample size at least the sample complexity of the learner; $d\geq\Omega(n^{2}\log n)$ . Then $I(\widehat{\theta};U\mid\widetilde{Z})=\Omega(\varepsilon^{-2})$ and $\Omega(\varepsilon^{-1})$ , respectively, and the same orders hold for its individual-sample form (Cors. 5.6–5.7, the first for proper learners). $\xi$ -sound adversaries, which read $\widehat{\theta}$ , the point and the data law and flag any of the fresh points with probability at most $\xi$ , certify recall of the same orders with probability $\Omega(1)$ up to logarithmic factors (Thms. 4.5–4.6) if $d\geq\Omega(n^{2}\log(n/\xi))$ and, for the affine loss, $\delta^{\prime}<\varepsilon$ and $n$ equals the learner’s sample complexity, assumed of order $\log(1/\delta^{\prime})/\varepsilon^{2}$ .	Upper bound only: $\mathcal{I}^{\mathrm{cand}}(X+\tau G)\leq I(\widehat{\theta};U\mid\widetilde{Z})$ by ( 4 ).
Voitovych et al. (2025) , Thm. 2.7	Affine loss, with parameters in the largest cube inscribed in a unit $\ell_{s}$ ball, $s\geq 2$ , and sparse sign data. In the Euclidean case, for $\xi<1/e$ and $1/(6\sqrt{n})\leq\varepsilon\leq\min\{c\,(d/(n^{2}\log(1/\xi)))^{1/2},1/6\}$ , with a constant $c$ , every learner with expected excess risk at most $\varepsilon$ has a tracer that reads $\widehat{\theta}$ , the point and the population mean, with false-positive rate at most $\xi$ and expected recall $\Omega(\varepsilon^{-2})$ . At $\varepsilon\asymp n^{-1/2}$ this requires $d\gtrsim n\log(1/\xi)$ and gives recall $\Omega(n)$ .	The decisions are functions of $\widehat{\theta}$ , the point and the mean, not of the release, and involve no $\tau$ .
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 $n^{2}$ steps of size $n^{-3/2}$ on the loss $-\langle\theta,z\rangle$ over the unit ball, with data among the standard basis vectors of $\mathbb{R}^{2n^{2}}$ : 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 $\tau=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 $X_{i}$ reveals $U_{i}$ (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 $D_{p}$ ), superMeasure (the supersample), nativeAccurateLearners (the learners of Theorem 3 )
Definition 1	nativeLossRelease ; releaseInfoI , releaseInfoJ , releaseInfoS , built on mutualInfo and condMutualInfo
Display ( 4 ), Lemma H.1	information_directions_supersample , information_directions_tracer_supersample
Theorem 3	native_loss_information_law_local (Assumption 2 as stated), native_loss_information_law ( $\phi$ 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 ( $C_{\mathrm{dim}}=32$ when $b\leq 4$ )
Appendix D.7	Theorem 3 at $\varepsilon_{1}$ : native_loss_information_law_paper_threshold . The bound ( 42 ) and the positivity of $M$ on $(0,\varepsilon_{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\cdot 10^{-4}$ : quartic_schedule_limits , quartic_bracket_root

Appendix

Table K.1: Results of the Paper and the Lean Declarations That Prove Them

Explore similar work

Information-Theoretic Generalization Bounds for Sequential Decision Making
May 12, 2026Futoshi Futami, Masahiro FujisawaGeneralization Bounds Mutual Information
The University of Osaka / RIKEN AIP / The University of Tokyo · The University of Osaka / RIKEN AIP
Information-theoretic Limits of Learning and Estimation
May 6, 2026Abbas El Gamal, Maxim RaginskyInformation-Theoretic Limits Concentration Bounds
Stanford University* · UIUC**
Bounded-Rationality, Hedging, and Generalization
May 14, 2026Pedro A. OrtegaGeneralization Bounds Rationality
Daios Technologies

May 12, 2026, stat.MLJ/K move · Enter open · S save

Information-Theoretic Generalization Bounds for Sequential Decision Making

Futoshi Futami, Masahiro Fujisawa

The University of Osaka / RIKEN AIP / The University of Tokyo · The University of Osaka / RIKEN AIP

Generalization Bounds Mutual Information Stochastic Multi-Armed Bandits Sequential Decision Making Theorem Proving

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

Information-Theoretic Generalization Bounds for Sequential Decision Making

Information-theoretic Limits of Learning and Estimation

Bounded-Rationality, Hedging, and Generalization