← All problems

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

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.

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

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.