A confidence interval algorithm for Disagreement coefficient

Question

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

Answer 1

I present here the general direction rather than a complete answer.

If you had known $D=D_\mathcal{X}$ then you could have computed $\theta_\epsilon$ yourself, since you can compute the real distances $d(h,h')$ for all $h,h'\in\mathcal{H}$, the real balls $B(h,\epsilon)$ (where by real I mean relative to the distribution $D$), and finally given a ball you could compute its disagreement set and its mass (you actually don't really need $D$ to compute the disagreement set of some $V\subseteq\mathcal{H}$, but you do need it to compute its mass). Unfortunately you don't know $D$, so what you could try is to evaluate all the above objects relative to the empirical distribution $\hat{D}_S(x)=\frac{1}{m}\sum\limits_{i=1}^m \mathbb{1}_{x=x_i}$.

Suppose that $\forall h,h'\in\mathcal{H}$ we have $d(h,h')\neq\epsilon$. In that case there exists $\eta>0$ such that $\forall h\in\mathcal{H}: B(h,\epsilon)=B(h,\epsilon-\eta)=B(h,\epsilon+\eta)$. Let $A$ denote the event that there exists $h,h'$ such that $|\widehat{d}(h,h')-d(h,h')|\ge\eta$, where $\widehat{d}(h,h')=\frac{1}{m}\sum\limits_{i=1}^m \mathbb{1}_{h(x_i)\neq h'(x_i)}$ is the empirical distance. Note that applying Chernoff's inequality and the union bound you can bound the probability of $A$ occurring (it decays exponentially in $m$). Conditioned on $A^C$ (the event that we were $\eta$-close to the real distance for all pairs $h,h'$), it holds that $B_D(h,\epsilon)=B_{\widehat{D}}(h,\epsilon)$ for all $h\in\mathcal{H}$. Thus, up to an exponentially small probability, all the $\epsilon$-empirical balls are in agreement with the real $\epsilon$ balls, which means the empirical and real disagreement sets are also equal.

Finally, to evaluate $\theta_\epsilon$, just go over all $h\in\mathcal{H}$ and compute the empirical mass of the disagreement set of the empirical ball $B_{\widehat{d}}(h,\epsilon)$. Conditioned on $A^C$, $\forall h\in\mathcal{H} :B_d(h,\epsilon)=B_{\widehat{d}}(h,\epsilon)$, and your problem is reduced to evaluating the mass of some disagreement set. Luckily, as $\mathcal{H}$ is finite, there are at most $2^{|\mathcal{H}|}$ disagreements sets, and again by Chernoff and the union bound for large enough $m$ the mass of every set in this family is close to its empirical mass (with high probability). I leave the details to you, observe that this is a distribution dependent bound (because of $\eta$) and we didn't handle the case of $d(h,h')=\epsilon$ for some pair $h,h'$. To handle this you could simply estimate the $\epsilon+\zeta$ ball instead of the epsilon ball (in this manner you will, with high probability, agree with the real $\epsilon$ ball). I leave the right choice of $\zeta$ to you (you want it positive to handle points exactly on the surface, but not too big as to include new points, where points here are in the hypotheses space). Recall that while we could use distribution dependent parameters, namely $\eta$, in the gurantees proof, our algorithm can't acess them (it does not know $D$), so $\zeta$ must be based on the empirical distances.