Steinke–Zakynthinou's linear CMI conjecture for realizable proper learning
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 , . This conjecture was refuted in the paper: the abstract states that the proper-learner CMI bound cannot be improved to , and the discussion explicitly says that the conjecture is refuted.
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Sources & referencesView supporting material
Primary 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).
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.