Approximate ERM with constant conditional mutual information

Let $\mathcal{X}$ be a domain, let $\mathcal{W}$ be a class of functions $f:\mathcal{X}\to\{0,1\}$ with VC dimension $d\geq 1$, and let $n\geq 1$. For a dataset $(x,y)\in(\mathcal{X}\times\{0,1\})^n$, write $\ell(h,(x,y))$ for the empirical $0$-$1$ loss, and let $\mathsf{CMI}(A)$ denote the conditional mutual information of an algorithm's output. Approximate-ERM CMI conjecture. There exists an absolute constant $c$ such that, for every such $\mathcal{W}$ and $n$, there is a randomized or deterministic algorithm $A:(\mathcal{X}\times\{0,1\})^n\to\mathcal{W}$ satisfying

$$\mathsf{CMI}(A)\leq c d$$

and, for every $(x,y)\in(\mathcal{X}\times\{0,1\})^n$,

$$\mathbb{E}[\ell(A(x,y),(x,y))]\leq\inf_{h\in\mathcal{W}}\ell(h,(x,y))+c\sqrt{\frac{d}{n}}.$$

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.