On the Information Complexity of Proper Learners for VC Classes in the Realizable Case

We provide a negative resolution to a conjecture of Steinke and Zakynthinou (2020a), by showing that their bound on the conditional mutual information (CMI) of proper learners of Vapnik--Chervonenkis (VC) classes cannot be improved from $d \log n +2$ to $O(d)$, where $n$ is the number of i.i.d. training examples. In fact, we exhibit VC classes for which the CMI of any proper learner cannot be bounded by any real-valued function of the VC dimension only.

cs.LG cs.IT Machine Learning and Algorithms Wireless Communication Security Techniques Computability, Logic, AI Algorithms

View graph Source

Paper

Similar papers

Towards a Unified Information-Theoretic Framework for GeneralizationMahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran et al.2021 · arXiv (Cornell University) · 38 citations In Library

Open Problem: Are all VC classes learnable with computable learners?Sushant Agarwal, Nivasini Ananthakrishnan, Shai Ben-David et al.2021 In Library

Proper Learning, Helly Number, and an Optimal SVM BoundOlivier Bousquet, Steve Hanneke, Shay Moran et al.2020 · arXiv (Cornell University) In Library

Discretized-Vapnik-Chervonenkis Dimension for Analyzing Complexity of Real Function ClassesChao Zhang, Wei Bian, D. Tao et al.2012 · IEEE Transactions on Neural Networks and Learning Systems · 12 citations In Library

VC Classes are Adversarially Robustly Learnable, but Only ImproperlyOmar Montasser, Steve Hanneke, Nathan Srebro2019 · arXiv (Cornell University) In Library

VC Classes are Adversarially Robustly Learnable, but Only ImproperlyOmar Montasser, Steve Hanneke, Nathan Srebro2019 · Conference on Learning Theory In Library

Computing the Vapnik Chervonenkis Dimension for Non-Discrete SettingsMohammed Nechba, Mouhajir Mohamed, Sedjari Yassine2023 · arXiv (Cornell University) In Library

PAC learnability versus VC dimension: a footnote to a basic result of statistical learningV. Pestov2011 · The 2011 International Joint Conference on Neural Networks · 13 citations In Library

Information-Theoretic Bayes Risk Lower Bounds for Realizable ModelsMatthew Nokleby, Ahmad Beirami2021 · arXiv (Cornell University) In Library

Estimated VC dimension for risk boundsD. McDonald, C. Shalizi, M. Schervish2011 · arXiv: Machine Learning · 9 citations In Library

Source of record

arXiv

44B

Welcome.

This panel sticks with you. Pick anything below and it opens right beside it, so you can dig through 60,000-plus records without ever losing your spot here.

Travel 44B

LibraryPapers, policy, standards, statute LabsEvery organization building AI ModelsIntelligence, price, and speed BenchmarksThe evaluation catalog IncidentsAI failures and harms SearchOne field across everything DashboardThe state of AI accountability in NY 44B RegistryThe Art. 44-B compliance portal