Approximate ERM with constant conditional mutual information
Let be a domain, let be a class of functions with VC dimension , and let . For a dataset , write for the empirical - loss, and let denote the conditional mutual information of an algorithm's output. Approximate-ERM CMI conjecture. There exists an absolute constant such that, for every such and , there is a randomized or deterministic algorithm satisfying
and, for every ,
This conjecture concerns the agnostic setting, where a perfectly consistent hypothesis need not exist. The allowed empirical error is of the order of worst-case uniform-convergence error, while removing the logarithmic factor from the known CMI bound may require using an approximate rather than exact empirical risk minimizer.
References
- Thomas Steinke and Lydia Zakynthinou, “Reasoning About Generalization via Conditional Mutual Information”, arXiv:2001.09122 (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.