Optimal Information Complexity for VC Learning: Recovering PAC Guarantees via eCMI

An Open Theoretical Question

In statistical learning theory, the PAC (Probably Approximately Correct) framework provides upper bounds on the sample complexity of learnable concept classes. For concept classes with VC dimension d, classical theory has established that in the realizable setting, the optimal generalization guarantee scales linearly with the VC dimension. However, when we shift perspective — examining learning algorithm complexity through an information-theoretic lens — a long-standing open question emerges: can this optimal PAC guarantee be recovered using information-theoretic quantities tied to the algorithm itself?

A newly released arXiv paper (arXiv:2610.10600) answers this question affirmatively. Building on the Conditional Mutual Information (CMI) framework introduced by Steinke and Zakynthinou (2020), the paper demonstrates that one can construct a learning algorithm whose evaluated Conditional Mutual Information (eCMI) achieves O(d) order in the realizable setting, thereby successfully recovering the optimal PAC guarantee for VC classes.

The PAC learning framework was proposed by Leslie Valiant in 1984. Its core idea is that a concept class is "learnable" if and only if there exists an algorithm that can output an approximately correct hypothesis with high probability using a polynomial number of samples and computation. The VC dimension (Vapnik-Chervonenkis dimension) is the central combinatorial quantity characterizing the complexity of a hypothesis space — intuitively, it measures the size of the largest point set that the hypothesis class can "shatter." The classical theorem by Blumer et al. shows that in the realizable setting, sample complexity scales linearly with VC dimension d, meaning O(d/ε) samples suffice to guarantee ε generalization error. This result is a cornerstone of learning theory, but its proof relies entirely on the combinatorial structure of the hypothesis space and is independent of the specific algorithm used.

The CMI Framework: Measuring Learning Complexity from an Algorithmic Perspective

Traditional generalization bound analyses typically rely on complexity measures of the hypothesis space — such as VC dimension or Rademacher complexity — which are algorithm-independent. The CMI framework introduced by Steinke and Zakynthinou in 2020 opens a different path: it focuses on how much information the algorithm actually "extracts" from the data during training.

Intuitively, if a learning algorithm's output is highly sensitive to some randomized configuration of the training samples, it has "memorized" more information about the training data, which often signals greater overfitting risk. CMI captures this dependence via conditional mutual information, and the eCMI (evaluated CMI) studied in this paper is a more refined variant — it measures the information leakage of the algorithm's output at evaluation points.

These algorithm-dependent information-theoretic quantities are attractive because they can potentially yield tighter bounds than algorithm-independent complexity measures, and they connect naturally to the study of generalization phenomena in modern machine learning.

The CMI framework is set up as follows: given 2n samples, randomly split them into two groups of n — one as the training set and one as the "shadow" set, with membership controlled by a random superset variable. The eCMI measures the mutual information between the prediction of the learned hypothesis at a randomly selected test point and the information about whether that test point belongs to the training set or the shadow set. The elegance of this "two-sample" design lies in directly linking generalization error to how much the algorithm's output depends on the sample configuration — if the algorithm over-memorizes the training set, its predictions at test points will differ based on sample membership, resulting in higher eCMI. Steinke and Zakynthinou proved a key inequality: generalization error can be upper bounded by a function of eCMI, providing an actionable mathematical tool for analyzing generalization through information-theoretic quantities.

The Core Result: eCMI at O(d) Order

The paper's main contribution is answering an open question: can the optimal PAC guarantee for VC classes be recovered through CMI-style analysis? The answer is yes.

The authors explicitly construct a learning algorithm and prove that its eCMI is O(d) in the realizable setting, where d is the VC dimension of the concept class. Given the known conversion between information complexity and generalization error, an O(d) eCMI directly corresponds to an optimal generalization guarantee that scales linearly with the VC dimension. This means the information-theoretic perspective can not only explain generalization, but can do so with the same precision as classical combinatorial complexity theory.

The Randomized Majority-of-5 Base Learner

The constructed algorithm has a distinctive character: it is a randomized "Majority-of-5" structure — a majority vote of five base learners — with optimal generalization guarantees in expectation.

Majority voting is well-known in learning theory, and in recent work on recovering optimal sample complexity in the realizable setting, majority votes among a small number of base learners have repeatedly emerged as key constructions. This paper combines that approach with information-theoretic measures, showing that such an ensemble structure achieves not only optimal sample complexity but also the order of the theoretical lower bound on the eCMI information complexity metric.

Majority vote, as a fundamental form of ensemble learning, plays a key role in constructive proofs of optimal sample complexity for VC learning. The theoretical rationale is that a single base learner (such as an empirical risk minimizer) may overfit on small samples, but a majority vote of multiple independently randomized base learners can reduce variance through a "democratic effect." In particular, majority votes of an odd number of learners (especially 3 or 5) exhibit favorable error amplification in the realizable setting — the error of individual learners can be exponentially suppressed. The choice of 5 rather than 3 base learners is closely tied to the information-theoretic calculations needed to achieve a tight O(d) upper bound on eCMI — fewer votes can incur constant-factor losses in certain boundary cases, while 5 precisely satisfies the technical conditions required for optimality.

Why This Work Deserves Attention

The significance of this research lies primarily in theoretical unification. For a long time, learning theory has developed along two relatively independent analytical tracks: a classical path based on combinatorial and geometric quantities such as VC dimension and covering numbers, and a modern path based on information-theoretic tools like mutual information and PAC-Bayes bounds. The latter has gained favor in deep learning generalization research, but an awkward fact has persisted: whether it can achieve optimality on the most fundamental VC classes had never been settled.

This paper fills that gap, demonstrating that the information-theoretic framework is no less expressive than classical theory — at least for the benchmark problem of realizable VC learning, the two approaches can reach the same destination by different routes. This provides both confidence and methodological guidance for applying CMI tools to analyze more complex learning scenarios, such as the agnostic (non-realizable) setting or deep neural networks.

It should be noted that the results in this paper are limited to the realizable setting, where some hypothesis in the concept class perfectly fits the data. The optimal information complexity in the agnostic (non-realizable) setting remains an open research direction.

Summary

With a clean and elegant construction — a randomized Majority-of-5 base learner — this paper proves that the optimal PAC guarantee for VC classes can be recovered via eCMI, an algorithm-dependent information-theoretic quantity, at O(d) complexity. It bridges the gap between combinatorial complexity theory and information-theoretic analysis, serving as an important piece in the puzzle of information-theoretic learning theory. For researchers interested in the foundations of generalization theory, this is a result well worth a careful read.