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

About 6 years old · traced to

Let H⊆X→Y\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 c≥0c\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 n≥dn\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 s∈Zns\in\mathcal Z^n, ER^s(An(s))≤c d/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.

References

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).

Progress summary

Never refreshed

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.