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

arXiv:2610.09206v1 Announce Type: new 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 rge2, on product distributions over a scaled sign cube in dimension at least linear in n, every proper learner with expected excess risk at most arepsilon on these distributions at the optimal sample size nasymparepsilon^{-2+2/r} has worst-case ld-CMI of order n bits, and Theta(n/(1+(au/arepsilon)^2)) bits under Gaussian noise of standard deviation au on the loss differences. The same holds without a regularizer, at nasymparepsilon^{-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.

Source: arXiv cs.LG | 2026-10-08