arXiv：cs.LG· Steve Hanneke, Juexiao Wang·· 4 小时前
VC 学习的最优信息复杂度：用 eCMI 恢复最优 PAC 保证
The optimal information complexity of VC learning
AI 导读
研究者构造出一个学习算法，在可实现情形下其评估条件互信息（eCMI）为 O(d)，从而首次从算法相关的 CMI 分析中恢复出 VC 类的最优 PAC 保证，d 为概念类的 VC 维。该算法是 5 个基学习器组成的随机 Majority-of-5，具备最优的期望泛化保证。
正文
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.
| Subjects: | Machine Learning (stat.ML); Information Theory (cs.IT); Machine Learning (cs.LG); Statistics Theory (math.ST) |
| Cite as: | arXiv:2610.10600 [stat.ML] |
| (or arXiv:2610.10600v1 [stat.ML] for this version) | |
| https://doi.org/10.48550/arXiv.2610.10600 arXiv-issued DOI via DataCite (pending registration) |
Submission history
From: Juexiao Wang [view email]
[v1]
Tue, 6 Oct 2026 22:58:21 UTC (31 KB)
来源：arXiv：cs.LG · arxiv.org