5个学习器投票，eCMI仅O(d)，VC学习最优PAC保证被CMI框架搞定！
The optimal information complexity of VC learning
📖 AI 总结
这篇论文研究VC学习的信息复杂度问题。作者基于Steinke和Zakynthinou（2020）提出的条件互信息（CMI）框架，聚焦其中的评估条件互信息（eCMI）这一算法相关量，探讨能否通过CMI的算法依赖分析恢复VC类的最优PAC保证。论文给出了肯定答案：在可实现情形下，作者构造了一种学习算法，其eCMI为O(d)量级，其中d为概念类的VC维。该算法采用随机化的“五选多数”基学习器集成策略，并具备最优的期望泛化保证。这一结果的意义在于，它表明算法依赖的信息论分析足以刻画VC学习的最优样本复杂度，从而在信息复杂度与经典VC理论之间建立了更紧密的联系，为理解学习算法的信息论本质提供了新的视角。
🔑 关键词速览
| 条件互信息 (CMI) | 一种基于算法依赖的信息论度量，用于分析学习算法的信息复杂度。 |
| 评估条件互信息 (eCMI) | CMI框架中的一种具体信息量，衡量算法在给定数据上的条件互信息。 |
| VC维 (VC-dimension) | 概念类复杂度的组合度量，表示能被概念类打散的最大点集大小。 |
| PAC保证 | 可能近似正确（Probably Approximately Correct）学习框架下的泛化误差保证。 |
| 多数投票 (Majority-of-5) | 一种集成方法，通过组合5个基学习器的预测结果进行多数投票来提升性能。 |
📱 每天一份 AI 前沿日报
关注公众号，每天 09:00 推送 · 不错过任何重磅