The optimal information complexity of VC learning

arXiv:2610.10600 · stat.ML, cs.IT, cs.LG, math.IT, math.ST, stat.TH · Submitted 2026-10-06 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: AI Radio. Generated commentary on the latest Artificial Intelligence papers.

Tom: I'm Tom, and with me are Jane, Lu, senior AI researcher at Tsinghua, Meng, lead engineer at a mysterious AI startup and Lalam, the in-house Large Language Model.

Jane: Today's paper: "The optimal information complexity of VC learning".

Tom: The optimal information complexity of VC learning presents a randomized Majority-of-5 algorithm that achieves an optimal worst-case eCMI of order O(d) and an expected training error rate of order O(d/n),…

Jane: First, who's behind it and why it matters.

Title and authors: Tom: The paper "The optimal information complexity of VC learning" and the authors Steinke and Zakynthinou are diving into how we can use these algorithm-dependent information quantities to understand the learning bounds for concept classes. They focus specifically on eCMI, which is this evaluated Conditional Mutual Information.

Jane: It’s about whether you can actually recover that optimal PAC guarantee for VC classes just by constructing an algorithm whose eCMI is of order O(d) in the realizable case, where d is the VC-dimension of the concept class.

Lu: What they are doing here is constructing a specific learning algorithm to prove this connection, and their core finding centers around using a randomized Majority-of-five base learner with an optimal in-expectation generalization guarantee <ref:2610.10600#pg1,a randomized Majority-of-5 base>.

Meng: So, it's not just theoretical; they are proposing a concrete algorithm—that Majority-of-five structure—to achieve this optimal information complexity bound <ref:2610.10600#pg1>.

Lalam: And they’re showing that the performance of this randomized Majority-of-five learner yields a worst-case eCMI of order O(nR(n/five)) and an expected training error rate at most five times R(n/five) <ref:2610.10600#pg1>.

The paper's summary: Tom: So, summarizing what they did, they constructed this randomized Majority-of-five learner which has a worst-case eCMI of order O(nR(n/five)) <ref:2610.10600#pg1>. But the key part is showing that if the base learner itself has an optimal expected error rate of order O(d/n), then this overall worst-case eCMI drops to order O(d).

Jane: That connection is what recovers the optimal expected generalization guarantee in the realizable case, which they call Theorem two point three <ref:2610.10600#pg2>. It means that by using this specific construction, we can achieve that optimal guarantee where we want it most.

Lu: They get there by analyzing the conditional entropy of errors on two n data points, and Lemma six point one shows that after accounting for permutations and duplicate adjustments, the conditional entropy ends up being O(nR(n/five)) <ref:2610.10600#pg1>.

Meng: That part about bounding the conditional probability of error by a squared term due to conditional independence between base classifiers is interesting. It seems like using five learners helps tame that exponential growth rate in the bound.

Lalam: And they also looked at distributional eCMI, where they introduced a simpler algorithm, a Majority-of-three base learner with an optimal expected error rate, which achieves the optimal guarantee on distributional eCMI as well <ref:2610.10600#pg2>.

The paper's improvements: Tom: They suggest some specific improvements to the framework by looking at different learning scenarios. For instance, they study the distributional eCMI and found that a Majority-of-three base learner with an optimal in-expectation generalization guarantee is sufficient for the optimal guarantee on distributional eCMI <ref:2610.10600#pg2>.

Jane: Theorem eight point one states that for any base learner B, if it has the guarantee that expected true error rate and expected training error rate are bounded by R(m) over i <ref:2610.10600#pg2>.i.d. data sets Sm ∼ Dm, then the distributional eCMI of a Majority-of-three of such base learners is O(nR(n/three)) <ref:2610.10600#pg2>.

Lu: This is important because it suggests that for the distributional setting, we don't necessarily need five base learners to get that optimal bound; three are enough if they meet a certain expectation guarantee.

Meng: It simplifies the practical implication for our system design because we can potentially use a simpler learning ensemble when we only care about distributionally robust performance.

Lalam: And they extend this idea to multiclass learning, showing that Theorem two point two and Theorem eight point one also hold for multiclass learning in the realizable case, achieving an optimal worst-case eCMI of order O(dDS), where dDS is the Daniely–Shalev-Shwartz dimension <ref:2610.10600#pg2>.

Conclusion: Tom: So, to wrap up on "The optimal information complexity of VC learning," they provide the first proof that an algorithm can have an eCMI of order O(d), which recovers the optimal PAC generalization guarantee for learning VC classes in the realizable case. This is a significant piece of work because it ties information theory directly to generalization bounds.

Jane: They also show that all these results extend to multiclass learning, where d is now the Daniely–Shalev-Shwartz dimension dDS, and the randomized Majority-of-five learner yields an optimal worst-case eCMI of order O(dDS) <ref:2610.10600#pg1>.

Lu: The distributional analysis confirms that a Majority-of-three base learners with an optimal in expectation generalization guarantee is enough for the optimal guarantee on distributional eCMI <ref:2610.10600#pg2>. That’s a solid result for setting new benchmarks.

Meng: For practical AI systems, knowing this means we can design ensembles whose complexity is tightly controlled by the VC dimension, rather than relying on just empirical risk minimization alone.

Lalam: And ultimately, they've shown that the randomized Majority-of-five learner is a concrete way to achieve this optimal bound for multiclass learning in the realizable case <ref:2610.10600#pg1>.

Tom: That's what we had on "The optimal information complexity of VC learning." It’s a deep dive into how algorithm structure impacts generalization guarantees through information theory. Next up, we're looking at multimodal models and how their performance depends on evaluation protocols.

Department of Computer Science, Purdue University

stat.ML, cs.IT, cs.LG, math.IT, math.ST, stat.TH

Submitted: 2026-10-06

Updated: 2026-10-15

License: http://creativecommons.org/licenses/by/4.0/

Importance score: 87/100

The gist: The optimal information complexity of VC learning presents a randomized Majority-of-5 algorithm that achieves an optimal worst-case eCMI of order O(d) and an expected training error rate of order

Key concepts

Conditional Mutual Information (CMI): CMI is an information-theoretic quantity used to analyze how much information one variable provides about another, conditioned on a third. In this paper, it is evaluated as eCMI to measure the complexity of learning algorithms based on algorithm-dependent quantities.
VC Dimension (d): The VC dimension measures the capacity or complexity of a concept class—the set of functions that can be learned. A higher VC dimension means the class is more complex, and this paper uses 'd' to quantify the complexity that an optimal learning algorithm must handle.
Realizable Case: The realizable case refers to a scenario where the true underlying concept generating the data is present within the hypothesis space being learned. This specific condition allows for a tighter bound on information complexity, leading to better recovery of generalization guarantees.

Terminology

Generalization — 33× in this paper · explained in 13 episodes
Conditional Mutual Information — 12× in this paper
Evaluated Conditional Mutual Information — 4× in this paper
Generalization Bounds — 2× in this paper · explained in 2 episodes
Sample Complexity — 2× in this paper · explained in 20 episodes
Consistency — 1× in this paper · explained in 3 episodes
Information-Theoretic Framework — 1× in this paper · explained in 2 episodes
Langevin Dynamics — 1× in this paper · explained in 3 episodes
List Learning — 1× in this paper · explained in 2 episodes
Loss Function — 1× in this paper · explained in 2 episodes

Summary

The optimal information complexity of VC learning presents a randomized Majority-of-5 algorithm that achieves an optimal worst-case eCMI of order O(d) and an expected training error rate of order O(d/n), recovering the optimal expected generalization guarantee in the realizable case.

Introduction to Information Complexity

The paper investigates the connection between algorithm-dependent information-theoretic quantities, specifically evaluated Conditional Mutual Information (eCMI), and the optimal PAC guarantee for VC classes. It shows that it is possible to recover this optimal 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. The main result presents a randomized Majority-of-5 learner that achieves an optimal worst-case eCMI of order O(d) and an expected training error rate of order O(d/n), thereby recovering the optimal expected generalization guarantee in the realizable case.

The Randomized Majority-of-5 Learner

The proposed algorithm, a randomized Majority-of-5 learner, involves several steps to achieve its performance. The algorithm first performs a uniform random permutation over the n training data points. Then it partitions the training data points into 5 disjoint pieces, each consisting of n/5 training data points, adjusting for duplicates in each set based on relative frequencies to emulate i.i.d. sampling. It then runs a base learner B on each adjusted training data set to obtain output classifiers hβk. Finally, it combines the classifiers with a Majority-of-5 vote. The analysis shows that this construction yields a worst-case eCMI of order O(nR(n/5)) and an expected training error rate of at most 5 · R(n/5).

Bounding the Worst-Case eCMI

The worst-case eCMI of the randomized Majority-of-5 learner is bounded by O(nR(n/5)) and, if the base learner has an optimal expected error rate of order O(d/n), this worst-case eCMI is of order O(d). This bound is derived by analyzing the conditional entropy of errors on 2n data points, where Lemma 6.1 shows that the conditional entropy of errors given permutations and duplicates adjustments is O(nR(n/5)). The proof demonstrates that by using five base learners, the conditional probability of error of the majority vote learner can be bounded by a squared conditional probability of error due to conditional independence, which compensates for the exponential growth rate.

Distributional eCMI and Simpler Learners

The paper also studies distributional eCMI and presents a simpler algorithm, a Majority-of-3 base learner with optimal expected error rate, that achieves the optimal guarantee on distributional eCMI. Theorem 8.1 states that for any base learner B having the guarantee that for i.i.d. data set Sm ∼ Dm, the expected true error rate and expected training error rate satisfy max[ESm∼Dm[erSm(B(Sm))], ESm∼Dm[erD(B(Sm))]] ≤ R(m). The distributional eCMI of a Majority-of-3 of such base learners is eCMID(l(A)) ≤ 192 · nR(n/3).

Conclusion and Extensions

The work provides the first proof that an algorithm can have eCMI of order O(d), where d is the DS dimension of the concept class, which recovers an optimal PAC generalization guarantee for learning VC classes in the realizable case. Furthermore, all results extend to multiclass learning where d is the Daniely–Shalev-Shwartz (DS) dimension dDS. The randomized Majority-of-5 learner yields an optimal worst-case eCMI of order O(dDS). The distributional analysis confirms that a Majority-of-3 base learners with an optimal in-expectation generalization guarantee suffices for the optimal guarantee on distributional eCMI.

Improvements for AI systems

The randomized Majority-of-5 algorithm achieves an optimal worst-case eCMI of order O(d) and an expected training error rate of order O(d/n), recovering the optimal PAC generalization guarantee in the realizable case, as stated in Theorem 2.3: "There exists a randomized algorithm A: (X × 0, 1) n → 0, 1 X with eCMI(l(A)) = O(d), and for every z ∈ (X × 0, 1) n, the expected training error rate of A with respect to the randomness β of the algorithm Eβ[l(A(z), z)] = O(d/n)."
The randomized Majority-of-5 learner can be specifically engineered to achieve an optimal worst-case eCMI bound of O(nR(n 5)) and a corresponding expected training error rate of at most 5 · R(n 5), where R is the expected error rate of the base learner, as derived from Theorem 2.2.
The distributionally optimized Majority-of-3 learner can be used to achieve an optimal guarantee on distributional eCMI, specifically showing that eCMID(l(A)) = O(nR(n 3)) and an expected training error rate of at most 2 · R(n 3), which is sufficient for optimal generalization in the distributional setting.
The system can leverage the conditional independence achieved by partitioning data into disjoint sets, where the output classifiers hβ,σ1,..., hβ5 are conditionally independent given β, which allows bounding the error probability of a Majority-of-5 classifier by a squared conditional probability of error due to the conditional independence of base classifiers.
The system's complexity for multiclass learning can be optimally managed by using a randomized Majority-of-5 learner, as Theorem 2.2 and Theorem 8.1 also hold for multiclass learning in the realizable case, allowing it to achieve an optimal worst-case eCMI of order O(dDS) where dDS is the DS dimension.

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.