PAC Learning From Countable Hypothesis Family

We generalize the PAC learning problem of finding an hypothesis from a finite hypothesis family to the one from a countable hypothesis family.

Problem Setting

1. $\mathcal{X}:$ the input space.

2. $\mathcal{Y} \doteq \{-1, 1\}:$ the output space.

3. $\mathcal{Z} \doteq \mathcal{X} \times \mathcal{Y}:$ the product space of $\mathcal{X}$ and $\mathcal{Y}$.

4. $\mathcal{D}:$ an unknown distribution defined on $\mathcal{X} \times \mathcal{Y}$.

5. $\mathcal{H}:$ an countable family of hypothesis, s.t., each $h \in \mathcal{H}$ is a function from $\mathcal{X}$ to $\mathcal{Y}$.

6. $\ell: \mathcal{Y} \times \mathcal{Y} \rightarrow [0, 1]$, a loss function that takes two points in $\mathcal{Y}$ and outputs a value between $0$ and $1$.

7. $L_\mathcal{D} (h):$ the expected loss of a hypothesis $h$ is defined as

   $$L_\mathcal{D} (h) = \mathbb{E}_{ (x, y) \sim \mathcal{D} } [ \ell( h(x), y) ]$$

   where $(x, y) \sim \mathcal{D}$ implies that the pair $(x, y) \in \mathcal{Z}$ is sampled according to the distribution $\mathcal{D}$.

8. $h^* \doteq \arg\min_{h \in \mathcal{H} } L_\mathcal{D} (h):$ the hypothesis that minimize the expected loss.

9. $\mu_h:$ an alias for $L_\mathcal{D} (h)$, when the distribution $\mathcal{D}$ discussed in the context is unique.

10. $B(\mu_h, \epsilon) \doteq \{ r \in \mathbb{R} : |r - \mu_h | < \epsilon \}:$ an open ball, which is an open interval in $\mathbb{R}$ centered at $\mu_h$ with length $2 \epsilon$, where $\epsilon > 0$.

11. $S \sim \mathcal{D}^n:$ a set of $n$ i.i.d samples drawn from $\mathcal{D}$, where $n \in \mathbb{N}^+$ is some positive integer. In particular, when $S \sim \mathcal{D}^n$, it can be represented as

    $$S = \{ (x_1, y_1), (x_2, y_2), ..., (x_n, y_n) : (x_i, y_i) \sim \mathcal {D}, \forall i \in [n] \}.$$

    We also view $S$ as a point in $\mathcal{Z}^n$.

12. $L_{S}(h) \doteq \frac{1}{ |S| } \sum_{ (x, y) \in S } \ell( h(x) , y ) :$ the empirical loss of a hypothesis $h$ on a sample set $S$.

13. Given a $h \in \mathcal{H}$, its restriction on $\mathcal{C} \subset \mathcal{X}$ is a function $h_S$ defined on $S$, such that

14. The restriction of $\mathcal{H}$ on $\mathcal{C}$ is the set of possible restriction of a function in $\mathcal{H}$ to $\mathcal{C}$

    $$\mathcal{H}_\mathcal{C} = \{ h_\mathcal{C} : \mathcal{C} \rightarrow \mathcal{Y} : h \in \mathcal{H} \}$$

    As $\mathcal{Y} = \{ -1, +1 \}$, the set of possible functions defined on $\mathcal{C}$ is bounded by $2^{n}$. Hence,

    $$|\mathcal{H}_\mathcal{C} | \le 2^{n}.$$

15. The growth function $\Pi_{\mathcal{H} } (n): \mathbb{N}^+ \rightarrow \mathbb{N}^+$ of $\mathcal{H}$ is defined as

Ideally, we would like to find $h^*$. The problem is difficult, as

• The space $\mathcal{X} \times \mathcal{Y}$ could be infinite.
• The distribution $\mathcal{D}$ is unknown.

To deal with the possibly infinite space $\mathcal{X} \times \mathcal{Y}$ and the unknown distribution $\mathcal{D}$, we investigate $\mathcal{H}$ on a finite sample set $S$. Due to the randomness inherited in sampling $S$, we allow our solution to be approximate and to make error. For a given pair of parameters of $\epsilon > 0$ and $\delta > 0$, we relax the goal to designing an $(\epsilon, \delta)$-learning algorithm $A$ that returns an $h'$, that is

• $\epsilon$-approximate: $\mu_{h'} \le \mu_{h^*} + \epsilon$,
• probably correct: $A$ return an $h'$ that does not satisfies the above condition with probability at most $\delta$.

Combined, $A$ should return an $\epsilon$-approximate solution $h'$ with probability at least $1 - \delta$.

The Algorithm

An $(\epsilon, \delta)$ approximate algorithm $A$

1. Draw a set $S$ of $n =$ samples independently from $\mathcal{D}$.
2. Return an $h'$ such that

$$h' = \arg\min_{h \in \mathcal{H} } L_{S} (h)$$

A key result of the algorithm states that $L_S(h)$ is a good approximation of $\mu_h$ for all $h \in \mathcal{H}$ simultaneously.

Theorem. If $n \ge$, then

$$\Pr_{S \sim \mathcal{D}^n } [ \exists h \in \mathcal{H} : L_S(h) \notin B(\mu_h, \epsilon / 2 ) ] \le \delta$$

An immediate corollary is that $h'$ is $\epsilon$-approximate with probability at least $1 - \delta$:

Proof of The Theorem

The proof relies on a technique called double sampling. Alongside with $S$, we create another sample set $S' \sim \mathcal{D}^n$ independently, termed the "ghost sample". Let

and

Then, we define

16. $\sigma:$ a random swap that exchanges the $i$-th ($i \in [n]$) element of $S$ and $S'$ independently with probability 0.5. Call the resulting sample sets $\sigma S$ and $\sigma S'$. Let $\sigma S[i]$ ($\sigma S'[i]$) be the $i$-th element of $\sigma S[i]$ ($\sigma S'[i]$). So$$\Pr \left[ \sigma S [i] = (x_i, y_i) \wedge \sigma S'[i] = (x_i', y_i') \right] = 0.5 \\ \Pr \left[ \sigma S [i] = (x_i', y_i') \wedge \sigma S'[i] = (x_i, y_i) \right] = 0.5$$

We use the gap of $|L_{\sigma S} (h) - L_{\sigma S'} (h)|$ as a proxy of $|L_S(h) - \mu_h|$. This enables us to focus on finite sets $S$ and $S'$ without worrying about the infinite size of $\mathcal{H}$.

For convenience, we use $\underset{S}{\Pr}[\cdot]$ ($\underset{S'}{\Pr}[\cdot]$) as shorthand for $\underset{S \sim \mathcal{D}^n}{\Pr}[\cdot]$ ($\underset{S' \sim \mathcal{D}^n}{\Pr}[\cdot]$). The road map of our proof is as follows.

Lemma 1.

$$\Pr_{S}[ \exists h : L_S(h) \notin B(\mu_h, \epsilon ) ] \le 2 \max_{S, S' \in \mathcal{Z}^n } \Pr_\sigma \left[ \exists h : |L_{ \sigma S} (h) - L_{ \sigma S' } (h) | \ge \frac{\epsilon}{2} \right]$$

On the left hand side of the inequality, the probability measures the event of a random set $S$ sampling from $\mathcal{D}$. On the right hand side, we can pick a fixed pair of $S$ and $S'$ that maximize

and the probability measures the event of the random swap $\sigma$. Fixing $S$ and $S'$ significantly simplifies the structure of $\mathcal{H}$. By Hoeffding inequality and union bound, we will prove that

Lemma 2. For any fixed pair of $S, S' \in \mathcal{Z}^n$,

$$\Pr_\sigma \left[ \exists h : |L_{ \sigma S} (h) - L_{ \sigma S' } (h) | \ge \frac{\epsilon}{2} \right] \le 2 \Pi_\mathcal{H} (2n) \exp( - \frac{n^2 \epsilon^2 }{2} )$$

Proof of Lemma 1.

The proof of Lemma 1 consists of three steps.

Step 1

$$\Pr_{S}[ \exists h : L_S(h) \notin B(\mu_h, \epsilon ) ] \le 2 \Pr_{S , S'} [ \exists h : L_S (h) \notin B(\mu_h, \epsilon ) \wedge L_{S'} (h) \in B(\mu_h, \epsilon / 2) ].$$

Proof. By Hoeffding inequality, for a fixed $h \in \mathcal{H}$, when $n \ge \frac{2}{\epsilon^2} \ln 4$

It follows that

$\square$

Remark: Mathematically, I don't know how to make prove this step rigorously. Suppose that for every $i \in [n]$, we know that the events $E_i$ and $F_i$ are measurable and independent. If $\Pr[ F_i ] \ge 1 / 2$, then $\Pr[ E_i \wedge F_i ] \ge 1 / 2$. But, can we claim that

Step 2

$$\Pr_{S} [ \exists h : L_S (h) \notin B(\mu_h, \epsilon ) \wedge L_{S'} (h) \in B(\mu_h, \epsilon / 2) ] \le \Pr_{S, S'} \left[ \exists h : |L_S (h) - L_{S'} (h) | \ge \frac{\epsilon}{2} \right]$$

Proof. Observe that

By monotonicity of probability, we finish the proof.

$\square$

Step 3

$$\Pr_{S, S' } \left[ \exists h : |L_S (h) - L_{S'} (h) | \ge \frac{\epsilon}{2} \right] \le \max_{S, S' \in \mathcal{Z}^n } \Pr_\sigma \left[ \exists h : |L_{ \sigma S} (h) - L_{ \sigma S' } (h) | \ge \frac{\epsilon}{2} \right]$$

Proof. We claim that $\sigma S$ and $\sigma S'$ have the same joint distribution as $S$ and $S'$ (if $S, S' \sim \mathcal{D}^n$). For points $\forall Z, Z' \in \mathcal{Z}^n$, by symmetry, it holds that

The right hand side can be viewed as the successful probability of the following experiment:

• Sample independently $S \sim \mathcal{D}^n$ and $S' \sim \mathcal{D}^n$.
• For each $i \in [n]$, exchange the $i$-th elements of $S$ and $S'$ independently with probability $0.5$.
• After the random swap, $\sigma S = Z$ and $\sigma S' = Z'$.

Now, $\forall \mathcal{E} \subset \mathcal{Z}^{2n}$, it holds that

Replacing $\mathcal{E}$ with the set $\{Z, Z' \in \mathcal{Z}^n : \exists h : |L_Z (h) - L_{Z'} (h) | \ge \frac{\epsilon}{2} \}$ finishes the proof.

$\square$

Proof of Lemma 2.

Let

and

be a pair of fixed sample sets. Define the set $\mathcal{C} = \{ x_1, x_2, ..., x_n, x_1', x_2', ..., x_n' \} \subset \mathcal{X}$ (with duplicates removed). The size of $\mathcal{C}$ is bounded by $2n$ and therefore the size of restriction of $\mathcal{H}$ on $\mathcal{C}$ is bounded by $\Pi_\mathcal{H} (2n)$.

First, fix a hypothesis $h$. For all $i \in [n]$, define $a_i = |\ell( h( x_i ), y_i) - \ell( h( x_i' ), y_i' ) | \le 1$ and let $V_i \in \{-1, 1\}$ be a random variable with equal probability:

If we apply a random swap $\sigma$ to $(S, S')$, then $L_{ \sigma S} (h_S) - L_{ \sigma S' } (h_S)$ has the same distribution as $\sum_{i \in [n] } \frac{1}{n} a_i V_i$. Since

by Hoeffding inequality,

The last inequality follows from that $\sum_{i \in [n] } a_i^2 \le n$.

Since for each $h \in \mathcal{H}$, it has the same behavior on $\mathcal{C}$ as some function in $\mathcal{H}_\mathcal{C}$. We can apply union bound on $\mathcal{H}_\mathcal{C}$.

$\square$

Reference

[1] Ethan Fetaya, "Lecture 02 - Introduction to Statistical Learning Theory", Weizmann Institute of Science, 2016

[2].R. Schapire and D. Bieber, “Lecture 05 - COS 511: Theoretical Machine Learning,”, Princeton University, 2013