If we can $\epsilon-$cover one set with $\frac{K}{2}$ elements and another with 2 elements why isn't their set product $2^{\frac{K}{2}}$ cover?

Question

I was reading the following paper on Robustness and Generalization (and covering numbers)and I was reading their example 1:

which didn't quite make sense to me. The reason it didn't make sense is that intuitively it seems to me that each region $X_i$ could have the label either +1 or -1, so it seems to me that the partition of Z should be exponential:

$$2^{\frac{K}{2}}$$

because it region can have either label +1 or -1. However, instead it seems to be that instead if 2 times the epsilon cover of the other set X, which seems puzzling. Any ideas why?

---

Ok for background definition:

Epsilon cover means the smallest set size that can $\epsilon$ cover some target set T. i.e.:

$$ N(\epsilon,T,\rho) = \min \{ |\hat T | \mid T \subset \cup_{\hat t \in \hat T} B(\hat t; \epsilon, \rho ) \}$$

where $B(\hat t; \epsilon, \rho ) = \{ x \mid \rho(\hat t, x) \leq \epsilon \}$ is the epsilon ball around $\hat t$.

Ab algorithm $A_s(x)$ has a margin $\gamma$ if every point in the input space around it would be classified the same way. i.e. as the paper wrote:

$$ A_{s}(x) = A_s(s_{j | x}) ; \forall x: \| x - s_{j|x}\|_2 < \gamma $$

for more definition the paper has them pretty much on the page and the page before Example 1 I am referencing.

Answer 1

Given a cover for $\mathcal{X}$, you seek to "cover" $\mathcal{X}\times\{-1,1\}$. To do so, you take any set $A$ from the cover of $\mathcal{X}$, and consider the sets $A\times\{1\}$, $A\times\{-1\}$. If your original cover was of size $K$, then this process results in $2K$ sets (the reason you don't end up with $2^K$ sets is that fixing the label for one set does not affect the labeling of another, so there is no multiplication going on).

In a more straightforward approach, let $\mathcal{C}$ be your original $\frac{\gamma}{2}$-cover for $\mathcal{X}$, then a partition $\mathcal{P}$ of $\mathcal{X}\times\{-1,1\}$ such that for all $ p\in\mathcal{P}$ and $(x_1,y_1),(x_2,y_2)\in p$ it holds that $y_1=y_2$ and $||x_1-x_2||\le\gamma$, is given by $\mathcal{C}\times\{-1,1\}$, which is of size $2|\mathcal{C}|$.

Answer 2

I think the answer is easiest to explain with an example. Say that we want to cover $T = \{ t_1, t_2,t_3 \}$ (where $t_i$ can just be $R^d$ vectors). Say the distance between the $t_i$'s is 1 and that we are requiring an epsilon cover with $\epsilon = 0.5$. Therefore $N(0.5,T,\| \cdot \|_2) = 3$ (just take the covering set to be $\hat T$ be an small enough perturbation of $t_i$'s or the $t_i$'s themselves). I like to intuitively imagine as radius balls around the centers $\hat t$ (or even RBFs using those centers). Now when we include $\cal Y = \{-1,+1\}$ as coordinate that means that we need to choose new centers with an extra coordinate but this extra coordinate can only be $+1$ or $-1$.

Now consider the new set we want to cover $T_{new} = T \times \cal Y$:

$$ T_{new} = \{ (t_1,-1), (t_2,-1), (t_3,-1), (t_1,+1), (t_2,+1), (t_3,+1) \}$$

consider the same set as the cover for it $\hat T_{new} = T_{new}$ (or just perturb the first d coordinates a little bit if you want). The that means we only need:

$$ | T_{first}| \cdot | T_{second}| = 2|T_{new}|$$

note that we do have $2^{|T|}$ potential labelings for individual "training points" but that is irrelevant because we are not considering sequences or potential training sets.

In a way we are only interested in how to cover some subset of the new space $\cal Z = \cal X \times \cal Y $. We consider the "data points" with all its possible labels but we can see them all at once in the space $\cal Z$. i.e. We since $(t_1,-1),(t_1,+1)$ are both part of the new set that requires covering, we can just choose a way to cover both, but in the problem since they are both part of the set there is no sense of order. We are just considering the new set to be covered in the new space.