Steinke–Zakynthinou's linear CMI conjecture for realizable proper learning

From papers

Let HXY\mathcal H \subseteq \mathcal X\to\mathcal Y be a VC class of dimension dd, and let A\mathcal A be a proper learning algorithm. For a distribution D\mathcal D, write CMID(An)\mathrm{CMI}_{\mathcal D}(\mathcal A_n) for the conditional mutual information of the algorithm on nn samples. Steinke–Zakynthinou's conjecture. There exists a real-valued function ff that is linear in dd and a constant c0c\geq 0 such that, for every nonnegative integer dd and every VC class H\mathcal H of dimension dd, there is a proper learning algorithm satisfying, for every ndn\geq d, CMID(An)f(d)\mathrm{CMI}_{\mathcal D}(\mathcal A_n)\leq f(d) for all distributions D\mathcal D, and, for every realizable sample sZns\in\mathcal Z^n, ER^s(An(s))cd/n\mathbb E\hat R_s(\mathcal A_n(s))\leq c\,d/n. This conjecture was refuted in the paper: the abstract states that the proper-learner CMI bound cannot be improved to O(d)O(d), 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

No solutions have been posted yet.