My question has to do with the disagreement coefficient in active learning. I've been trying to solve the following question, where I need an algorithm to derive a confidence interval for $\theta$, the disagreement coefficient of a given distribution $\cal D_\cal X$, defined in these notes by Shai-shalev shwartz:
Let $\mathcal{H}$ be a hyposesis class. We define a pseudo-metric on $\mathcal{H}$, based on the marginal distibution $\mathcal{D_\mathcal{X}}$ over instances, such that:
$$d(h,h')=\Pr\limits_{x\sim D_\mathcal{X}} \left[h(x)\neq h'(x)\right]$$. We define the corresponding ball of radius $r$ around $h^*$:
$$B(h^*,r)=\left\{h\in\mathcal{H} | \; d(h,h')\le r\right\}$$
The disagreement region of a hypothesis subset $V\subseteq\mathcal{H}$ is $$DIS(V)=\left\{x\big| \;\exists h,h'\in V: \; h(x)\neq h'(x)\right\}$$
We can now define the disagreement coefficient:
Let $\cal H$ be an hypothesis class, $\cal D$ be a distribution over $\cal X \times \cal Y$ and $\cal D_\cal X$ be the marginal distribution, i.e., $\Pr_{X\sim\cal D_\cal X}(X=x)=\Pr_{(X,Y)\sim \cal D}(X=x)$. Then given $h\in \cal H$, the $\epsilon$-disagreement coefficient is defined to be $\theta_{h,\epsilon}=\frac{\Pr(X\in DIS(B(h,\epsilon)))}{\epsilon}.$ The $\epsilon$-disagreement coefficient of $\mathcal{H}$ is $\theta_\epsilon = max_{h\in\cal H} \theta_{h,\epsilon}$.
The question is to find an algorithm that given a sequence of $m$ samples $S=(x_1,...,x_m)\sim D_\mathcal{X}^m$ and $\epsilon\in[0,1]$, finds a confidence interval $[\theta_l,\theta_u]$ for $\theta_\epsilon$. That is, we want to guarantee that with probability $\ge 1-\delta$ over the choice of $S$ it holds that $\theta_l\le \theta_\epsilon\le \theta_u$.