الملخص
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.
الكلمات المفتاحية
الموضوع
بيانات النشر
- المجلة
- غير متاح
- وصول مفتوح
- وصول مفتوح أخضر
اقتبس هذه المقالة
APA 7
Hanneke, S., & Wang, J. (2026). The optimal information complexity of VC learning. https://omanscience.com/ar/articles/the-optimal-information-complexity-of-vc-learning
MLA 9
Hanneke, Steve, and Juexiao Wang. "The optimal information complexity of VC learning." https://omanscience.com/ar/articles/the-optimal-information-complexity-of-vc-learning.
شيكاغو (المؤلف–التاريخ)
Hanneke, Steve, and Juexiao Wang. 2026. "The optimal information complexity of VC learning." https://omanscience.com/ar/articles/the-optimal-information-complexity-of-vc-learning.
هارفارد
Hanneke, S. and Wang, J. (2026) 'The optimal information complexity of VC learning', Available at: https://omanscience.com/ar/articles/the-optimal-information-complexity-of-vc-learning.
فانكوفر
Hanneke S, Wang J. The optimal information complexity of VC learning. https://omanscience.com/ar/articles/the-optimal-information-complexity-of-vc-learning
IEEE
S. Hanneke, and J. Wang, "The optimal information complexity of VC learning," https://omanscience.com/ar/articles/the-optimal-information-complexity-of-vc-learning.