<p>Learning model:</p>
<ul>
<li>Domain set: <span class="math-container">$\mathcal{X}$</span>,</li>
<li>Label set: <span class="math-container">$\{0,1\}$</span>,</li>
<li>Hypothesis class: a set <span class="math-container">$\mathcal{H}$</span> of binary hypotheses <span class="math-container">$h:\mathcal{X}\to\{0,1\}$</span></li>
<li>Data-labels generating distribution: <span class="math-container">$\mathcal{D}$</span> over <span class="math-container">$\mathcal{X}\times\{0,1\}$</span>,</li>
<li>Training set: <span class="math-container">$S\sim\mathcal{D}^m$</span> of size <span class="math-container">$m\in\mathbb{N}$</span>, where <span class="math-container">$S\sim\mathcal{D}^m$</span> means the elements of <span class="math-container">$S$</span> are drawn i.i.d. according to <span class="math-container">$\mathcal{D}$</span>.</li>
</ul>
<p>Given some <span class="math-container">$h\in\mathcal{H}$</span>, we measure the performance of <span class="math-container">$h$</span> by its risk <span class="math-container">$R(h):=\mathbb{P}_{(x,y)\sim\mathcal{D}}(h(x)\neq y)$</span>.</p>
<p>Now, consider the following definition of <em>agnostic PAC learnability</em>.</p>
<p><span class="math-container">$\mathbf{Definition.}$</span> Hypothesis class <span class="math-container">$\mathcal{H}$</span> is <em>agnostic PAC learnable</em> if there exists a learning algorithm <span class="math-container">$A$</span> and a function <span class="math-container">$m_\mathcal{H}:(0,1)^2\to\mathbb{N}$</span> such that for every <span class="math-container">$\varepsilon,\delta\in(0,1)$</span>, every distribution <span class="math-container">$\mathcal{D}$</span> over <span class="math-container">$\mathcal{X}\times\{0,1\}$</span>, and every training set <span class="math-container">$S$</span> of size <span class="math-container">$m\geq m_{\mathcal{H}}(\varepsilon,\delta)$</span> we have
<span class="math-container">$$
\mathbb{P}_{S\sim \mathcal{D}^m}\Bigl(R(h_S)\leq\inf_{h\in\mathcal{H}}R(h)+\varepsilon\Bigr)\geq 1-\delta\;,\;h_S=A(S)\,.
$$</span></p>
<p>I am wondering whether this definition is equivalent to the following definition.</p>
<p><span class="math-container">$\mathbf{Definition.}$</span> Hypothesis class <span class="math-container">$\mathcal{H}$</span> is <em>agnostic PAC learnable</em> if there exists a learning algorithm <span class="math-container">$A$</span> and a function <span class="math-container">$m_\mathcal{H}:(0,1)^2\to\mathbb{N}$</span> such that for every <span class="math-container">$\varepsilon,\delta\in(0,1)$</span>, every distribution <span class="math-container">$\mathcal{D}$</span> over <span class="math-container">$\mathcal{X}\times\{0,1\}$</span>, every <span class="math-container">$h\in\mathcal{H}$</span>, and every training set <span class="math-container">$S$</span> of size <span class="math-container">$m\geq m_{\mathcal{H}}(\varepsilon,\delta)$</span> we have
<span class="math-container">$$
\mathbb{P}_{S\sim \mathcal{D}^m}\Bigl(R(h_S)\leq R(h)+\varepsilon\Bigr)\geq 1-\delta\;,\;h_S=A(S)\,.
$$</span></p>
<p>What is obvious to me is that</p>
<p><span class="math-container">$$
\mathbb{P}_{S\sim \mathcal{D}^m}\Bigl(R(h_S)\leq\inf_{h\in\mathcal{H}}R(h)+\varepsilon\Bigr)\geq 1-\delta
$$</span></p>
<p>implies</p>
<p><span class="math-container">$$
\mathbb{P}_{S\sim \mathcal{D}^m}\Bigl(\forall h\in\mathcal{H}:R(h_S)\leq R(h)+\varepsilon\Bigr)\geq 1-\delta\,.
$$</span></p>
<p>But I am unsure whether the all-quantifier can be <strong>put outside</strong> the probability as in my alternative definition. I feel this is allowed here but I am missing a solid argument and would be happy about some help. It might be this is a silly question so that I apologize in advance.</p>

CC BY-SA 4.0
2024-12-11T18:25:01.817Z
Do you agree they are trivially equivalent for finite classes? For finite classes, given any distribution, there is an $h$ that minimizes $R$, so you only need to care about the inequality for that $h$. For infinite classes, they are also equivalent, and the argument is easy but a bit less trivial (you just need $\mathbb{P}[X \le Y+\alpha] \ge \beta$ for all $\alpha > 0$ implies $\mathbb{P}[X \le Y] \ge \beta$).
mathworker21
CC BY-SA 4.0
2024-12-12T12:56:23.653Z
Yes, for finite $\mathcal{H}$ it was obvious to me, which is where my intuition of the equivalence originated from. And now it is also obvious to me why both definitions are also equivalent in case of infinite classes. Indeed, all the learning model notation kind of blocked my view to the essence $\forall\alpha>0:\mathbb{P}(X\leq Y+\alpha)\geq\beta)\,\Rightarrow\,\mathbb{P}(X\leq Y)\geq\beta$. Really sad -.-. Thanks much for your help.
VK88
<machine-learning><pac-learning>
Agnostic PAC learning - equivalent definitions?
VK88
# Agnostic PAC learning - equivalent definitions?

(Asked by: username_0 on 2024-12-11)

Learning model:

* Domain set: $\mathcal{X}$,
* Label set: $\{0,1\}$,
* Hypothesis class: a set $\mathcal{H}$ of binary hypotheses $h:\mathcal{X}\to\{0,1\}$
* Data-labels generating distribution: $\mathcal{D}$ over $\mathcal{X}\times\{0,1\}$,
* Training set: $S\sim\mathcal{D}^m$ of size $m\in\mathbb{N}$, where $S\sim\mathcal{D}^m$ means the elements of $S$ are drawn i.i.d. according to $\mathcal{D}$.

Given some $h\in\mathcal{H}$, we measure the performance of $h$ by its risk $R(h):=\mathbb{P}\_{(x,y)\sim\mathcal{D}}(h(x)\neq y)$.

Now, consider the following definition of *agnostic PAC learnability*.

$\mathbf{Definition.}$ Hypothesis class $\mathcal{H}$ is *agnostic PAC learnable* if there exists a learning algorithm $A$ and a function $m\_\mathcal{H}:(0,1)^2\to\mathbb{N}$ such that for every $\varepsilon,\delta\in(0,1)$, every distribution $\mathcal{D}$ over $\mathcal{X}\times\{0,1\}$, and every training set $S$ of size $m\geq m\_{\mathcal{H}}(\varepsilon,\delta)$ we have
$$
\mathbb{P}\_{S\sim \mathcal{D}^m}\Bigl(R(h\_S)\leq\inf\_{h\in\mathcal{H}}R(h)+\varepsilon\Bigr)\geq 1-\delta\;,\;h\_S=A(S)\,.
$$

I am wondering whether this definition is equivalent to the following definition.

$\mathbf{Definition.}$ Hypothesis class $\mathcal{H}$ is *agnostic PAC learnable* if there exists a learning algorithm $A$ and a function $m\_\mathcal{H}:(0,1)^2\to\mathbb{N}$ such that for every $\varepsilon,\delta\in(0,1)$, every distribution $\mathcal{D}$ over $\mathcal{X}\times\{0,1\}$, every $h\in\mathcal{H}$, and every training set $S$ of size $m\geq m\_{\mathcal{H}}(\varepsilon,\delta)$ we have
$$
\mathbb{P}\_{S\sim \mathcal{D}^m}\Bigl(R(h\_S)\leq R(h)+\varepsilon\Bigr)\geq 1-\delta\;,\;h\_S=A(S)\,.
$$

What is obvious to me is that

$$
\mathbb{P}\_{S\sim \mathcal{D}^m}\Bigl(R(h\_S)\leq\inf\_{h\in\mathcal{H}}R(h)+\varepsilon\Bigr)\geq 1-\delta
$$

implies

$$
\mathbb{P}\_{S\sim \mathcal{D}^m}\Bigl(\forall h\in\mathcal{H}:R(h\_S)\leq R(h)+\varepsilon\Bigr)\geq 1-\delta\,.
$$

But I am unsure whether the all-quantifier can be **put outside** the probability as in my alternative definition. I feel this is allowed here but I am missing a solid argument and would be happy about some help. It might be this is a silly question so that I apologize in advance.

**Tags:** machine-learning, pac-learning

> **Comments:**
> **username_1**: Do you agree they are trivially equivalent for finite classes? For finite classes, given any distribution, there is an $h$ that minimizes $R$, so you only need to care about the inequality for that $h$. For infinite classes, they are also equivalent, and the argument is easy but a bit less trivial (you just need $\mathbb{P}[X \le Y+\alpha] \ge \beta$ for all $\alpha > 0$ implies $\mathbb{P}[X \le Y] \ge \beta$).  
> **username_0**: Yes, for finite $\mathcal{H}$ it was obvious to me, which is where my intuition of the equivalence originated from. And now it is also obvious to me why both definitions are also equivalent in case of infinite classes. Indeed, all the learning model notation kind of blocked my view to the essence $\forall\alpha>0:\mathbb{P}(X\leq Y+\alpha)\geq\beta)\,\Rightarrow\,\mathbb{P}(X\leq Y)\geq\beta$. Really sad -.-. Thanks much for your help.  

---

## 0 answers

