# A confidence interval algorithm for Disagreement coefficient

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

– D.W.
Jul 25 at 5:24
• Please give a proper citation for all copied material. See cs.stackexchange.com/help/referencing
– D.W.
Jul 25 at 5:24

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.

• Why in the case of $d(h,h')\neq \epsilon$ there is $\eta >0$ that works for all $h\in \cal H$? and why do we assume $d(h,h')\neq \epsilon$ in the first place? Say it was $\epsilon$ for some pairs, wouldn't we be able to argue the same thing? Jul 27 at 16:42
• Think of a ball of radius $\epsilon$ around $h$. If no other hypothesis lies on the surface, you can "thicken" it without including new points. Formally, all other hypotheses lie at distance $d$ from $h$ satisfying $\epsilon-\delta_h<d<\epsilon+\delta_h$. Thus, to wrongly place $h'\notin B(h,\epsilon)$ in the estimated ball it must be the case that $|\hat{d}(h,h')-d(h,h')|>\delta_h$. Same goes for wrongly leaving out $h'\in B(h,\epsilon)$ from the estimated ball. Now $\eta = \min_h \delta_h$. Jul 27 at 17:41
• If a point lies on the surface we need to do something else (the estimated ball will likely be different than the real one, making the disagreement set different). Jul 27 at 17:43
• I suppose a good choice for $\zeta$ would be the minimal distance between any two hypotheses. In regards to what you said about $\eta,\zeta$ not being computable exactly because the distribution is unknown to the algorithm, I can see why $\zeta$ would need to be computed, but why would we want to compute $\eta$? Isn't $\eta$ essential for the proof only? Wouldn't it be possible to just estimate the balls based on the empirical data, and the proof is an explanation of why that is a good estimate? Jul 29 at 9:45
• Also, this seems like this algorithm provides an estimate for the balls and therefore for $\theta$ but how is this an interval for $\theta$? Jul 29 at 9:45