The optimal information complexity of VC learning

Steve Hanneke; Juexiao Wang

stat.MLOct 6, 2026

The optimal information complexity of VC learning

Authors: Steve Hanneke, Juexiao Wang

Abstract

Steinke and Zakynthinou(2020) introduces the Conditional Mutual Information (CMI) framework of analyzing the information complexity of learning algorithms based on algorithm-dependent information-theoretic quantities. We study one of these quantities, the evaluated Conditional Mutual Information (eCMI). It has been an interesting question whether the optimal PAC guarantee for VC classes can be recovered from the algorithm-dependent analyses via CMI. And we show that it is possible to recover this guarantee by constructing a learning algorithm whose eCMI is of order O(d) in the realizable case, where d is the VC-dimension of the concept class. Specially, our algorithm is a randomized Majority-of-5 base learners with optimal in-expectation generalization guarantee.

Explore similar work

An Accuracy-Information Tradeoff for Loss-Difference Conditional Mutual Information
Oct 6, 2026Hazar YuekselStatistical Learning Theory Information-Theoretic Generalization Bounds
Information-theoretic Limits of Learning and Estimation
May 6, 2026Abbas El Gamal, Maxim RaginskyInformation-Theoretic Generalization Bounds Minimax Estimation
Stanford University* · UIUC**
An Optimal Agnostic PAC Algorithm
Aug 6, 2026Markus Engelund Mathiasen, Jian Qian, Nikita ZhivotovskiyPAC Learning Statistical Learning Theory
Department of Computer Science, Aarhus University · Division of Artificial Intelligence and Data Science, School of Computing and Data Science, The University of Hong Kong · Department of Statistics, University of California, Berkeley

Oct 6, 2026, cs.LGJ/K move · Enter open · S save

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

Hazar Yueksel

Statistical Learning Theory Information-Theoretic Generalization Bounds Information-Theoretic Lower Bounds Mutual Information

Open paper AskPDF arXiv

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.

Abstract

Explore similar work

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

Information-theoretic Limits of Learning and Estimation

An Optimal Agnostic PAC Algorithm