Steinke–Zakynthinou's linear CMI conjecture for realizable proper learning
Let be a VC class of dimension , and let be a proper learning algorithm. For a distribution , write for the conditional mutual information of the algorithm on samples. Steinke–Zakynthinou's conjecture. There exists a real-valued function that is linear in and a constant such that, for every nonnegative integer and every VC class of dimension , there is a proper learning algorithm satisfying, for every , for all distributions , and, for every realizable sample , .
References
Status
- Refuted: Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran, and Daniel M. Roy. On the information complexity of proper learners for VC classes in the realizable case (arXiv preprint, 2020) https://ar5iv.labs.arxiv.org/html/2011.02970
Source: Mahdi Haghifam, Gintare Karolina Dziugaite, Shay Moran and Daniel M. Roy, “On the Information Complexity of Proper Learners for VC Classes in the Realizable Case”, arXiv:2011.02970 (2020).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.