# Proving a certain hypothesis class on a given distribution is not learnable

I had this question in Learning theory, but it's really just a question in probability theory to be honest, so I'm gonna try to rephrase it in a way that really emphasizes what I was trying to do to solve it:

Let $$\mathcal X_N=\{0,1\}^N$$, $$\mathcal Y=\{0,1\}$$ and define a uniform distribution, $$\mathcal D_N$$, on $$\mathcal X_N \times \mathcal Y$$. Prove that for any $$m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$$ there exists a number $$N$$ such that $$\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: L_\mathcal D(i) > \epsilon \,\wedge \forall \, 1\leq j \leq m, \,x_j(i)=y_j)>\delta$$

Original phrasing:

Let $$\mathcal X_N=\{0,1\}^N$$, $$\mathcal Y=\{0,1\}$$ and define a uniform distribution, $$\mathcal D_N$$, on $$\mathcal X_N \times \mathcal Y$$. Define the hypothesis class $$\mathcal H_N = \{h_i: \mathcal X_N \to \mathcal Y \mid 1 \leq i \leq N \}$$, where $$h_i(x) = x(i)$$.

Prove that for any $$m, \epsilon\in(0,\frac{1}{2}), \delta \in(0,1)$$ there exists a number $$N$$ such that $$\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: L_\mathcal D(i) > \epsilon \,\wedge L_S(h)=0)>\delta$$

So a few things:

$$S$$ is obtained by randomly and independently drawing $$(x,y)$$ pairs from $$\mathcal D_N$$,

$$L_D(i) = \mathbb P_{(x,y)\sim \mathcal D} (x(i)\neq y)$$,

x(i) - is the i'th coordinate of the $$N$$ dimensional vector x.

What I tried to do was:

First of all, fix an $$i\in \{1,...,N\}$$ and consider $$\mathbb P_{(x,y)\sim \mathcal D} (x(i)\neq y) = 2\frac{2^{N-1}}{2^{N+1}} = \frac{1}{2} > \epsilon$$ for any $$\epsilon \in (0,\frac{1}{2})$$ so the first requirement is rather redundant.

Second, independently drawing a sequence $$S$$ of $$m$$ pairs (with repetition) such that every pair has $$x(i)=y$$ is with probability $$\mathbb P_{S\sim \mathcal D^m} (\forall \, 1\leq j \leq m : x_j(i)=y_j) = \prod_{j=1}^m \mathbb P_{(x,y)\sim \mathcal D} (x_j(i)=y_j) = \frac{1}{2^m}$$.

Now that's for a single fixed $$i\in [N]$$, trying to lower bound the probability of an existence of such an $$i$$ could either be done by just ignoring the rest and saying $$\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: \forall \, 1\leq j \leq m, \,x_j(i)=y_j)\geq \frac{1}{2^m} > \delta$$
But that is a very gross estimation so I calculated the probability exactly using inclusion-exclusion principle like so:

let $$1 \leq i_1 < i_2 <... < i_k \leq N\,$$ then $$\mathbb P_{S\sim \mathcal D^m} (\bigwedge_{t=1}^k \{ \forall \, 1\leq j \leq m, \,x_j(i_t)=y_j\}) = (\prod_{t=1}^k \mathbb P_{S\sim \mathcal D^m} (x(i)=y))^m = \frac{1}{2^{km}}$$

finally we get:

$$\mathbb P_{S\sim \mathcal D^m} (\exists \,1\leq i \leq N: \forall \, 1\leq j \leq m, \,x_j(i)=y_j) = \sum_{i=1}^N (-1)^{i-1}{{N}\choose{i}}(\frac{1}{2^m})^i$$

And now my goal is to lower bound this by $$\delta$$ and using some closed form of this expression.

My question is first, is my analysis even correct and second, how would you proceed?

Since each $$x$$ is uniformly chosen, the probability of having a certain value at the $$i$$'th spot is independent of the probability of finding some other certain value in the $$j$$'th spot. You showed this already, but notice it means that you dont need the inclusion-exclusion principle, and instead the probability will just be the probability of the complement, which is $$1-\frac{1}{2^{km}}$$. You can now easily choose $$k$$ such that this probability would be bigger than $$\delta$$
• You are right about the independence in choosing each coordinate of the vector and each vector in $S$, hence the probabilities $\frac{1}{2^{mk}},\, k\in \{1,2,...,N\}$ but these aren't the events that intersect. The events $A(i): \{\forall \,1\leq j \leq m : x_j(i)=y_j \}$ are not independent, it is very much possible for a single vector (or even all m vectors) to have both the i'th and j'th coordinate equal to y. Plus this solution doesn't depend on $N$. The complement of what I'm trying to calculate would be $\mathbb P (\text{no } i \in [N] \text{satisifies } : \forall j\in [m]: x_j(i)=y_j)$ – se718 Mar 30 at 9:34
• I believe what you've calculated is the probability that for $k$ fixed $i\in [N]\,$ values at least one of them doesn't satisfy the property of having the coordinate same as $y$. – se718 Mar 30 at 9:39
• You need to know the probability that a certain index wont be a good hypothesis, then from independence, raise that number to the power of $N$ (here it was $k$) to get the probability that no hypothesis is correct. Its complement would have probability $1-\frac{1}{2^{Nm}}$ and now choose $N$ big enough so this value will be larger than $\delta$ – nir shahar Mar 30 at 11:02
• But the probability that a certain index, say $i$ isn't a good hypothesis on $S$ isn't $\frac{1}{2^m}$ since it suffices that at least one of $j=1,2,...,m$ have $x_j(i)\neq y_j$. Unless I got it all wrong and that is the probability, although an explanation on why that is would be helpful. – se718 Mar 30 at 11:07
$$\sum\limits_{i=1}^N (-1)^{i-1} {N\choose i}\frac{1}{2^{mi}}=1-\sum\limits_{i=0}^{N}(-1)^i {N\choose i}\frac{1}{2^{mi}}=1-\left(1-\frac{1}{2^m}\right)^N\ge 1-e^{-N/2^m}\ge\delta$$,
Where the last inequality holds for $$N\ge 2^m\log\frac{1}{1-\delta}$$.