The optimal information complexity of VC learning
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.
Related
- The information geometry of product-reference discrete diffusion: Interaction growth complexity and optimal scheduling
- Near-Optimal Sample Complexity for Recursive Entropic Risk Reinforcement Learning with a Generative Model
- Sparse Dictionary Learning for Measure-Valued Data via Linearized Optimal Transport: Efficient Algorithms and Sample Complexity
- Differentially Private Learning of Markov Chains: Near-Optimal Sample Complexity for Item and User Level Privacy
- Algorithmic Information Dynamics of Learning: A Certified, Differentiable Complexity Controller for Grokking
BibTeX
@misc{hanneke2026optimal,
title = {{The optimal information complexity of VC learning}},
author = {Steve Hanneke and Juexiao Wang},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10600},
eprint = {2610.10600},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10600},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - The optimal information complexity of VC learning
AU - Steve Hanneke
AU - Juexiao Wang
PY - 2026
DA - 2026/10/15
PB - arXiv
DO - 10.48550/arxiv.2610.10600
UR - https://arxiv.org/abs/2610.10600
AB - 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.
ER -