<p>I invariably run into this issue when I teach learning theory. Indeed, the common notation causes a lot of confusion and is logically flawed.</p>
<p>To elaborate on Usul's comment. Upper bounds are of the form: Whenever sample size is at least <span class="math-container">$n\ge n_0(\epsilon,\delta,\ldots)$</span>, some generalization guarantee holds. Lower bounds are of the general form: Whenever sample size is less than <span class="math-container">$n_1(\epsilon,\delta,\ldots)$</span>, there exists an adversarial distribution that prevents the generalization bound from holding.</p>
<p>Given this setup, the logical big-O notation is <span class="math-container">$n_0=O(\cdot)$</span> and <span class="math-container">$n_1=\Omega(\cdot)$</span>.</p>

CC BY-SA 4.0
2023-11-26T08:49:55.907Z
With only few lines you removed the whole confusion :). I'm wondering if your lectures are available somewhere, I'd be grateful if you can share!
rivana
CC BY-SA 4.0
2023-11-26T08:58:44.223Z
I think you shared a link of your lectures in this post: https://cstheory.stackexchange.com/questions/38694/rademacher-complexity-and-lowerbounds-in-learning-theory?rq=1. But it's not working anymore.
rivana
CC BY-SA 4.0
2023-11-26T09:02:52.410Z
@rivana yes unfortunately my university disabled that platform and the content had to be taken down. email me and I'll send them to you
Aryeh
CC BY-SA 4.0
2023-11-26T09:14:59.127Z
Thank you so much, it's so kind of you, I just sent you an email!
rivana
CC BY-SA 4.0
2023-11-25T18:14:20.790Z
2023-11-25T18:14:20.790Z
Aryeh
<p>In computer science, lower bounds and upper bounds are defined as follow:</p>
<p><span class="math-container">$$m \geq g(n) \implies m = \Omega(g(n))$$</span></p>
<p><span class="math-container">$$m \leq g(n) \implies m = \mathcal{O}(g(n))$$</span></p>
<p>However, in proving lower bounds and upper bounds for learning algorithms, I get confused, From papers\books Hoeffding inequality always gives you upper bounds, but in every book\paper: <span class="math-container">$ m \geq g(n) \implies m = \mathcal{O}(g(n))$</span> which contradicts classic definitions.</p>
<p>I know I'm wrong somewhere but I can't find the missing puzzle.</p>
<p>The way I understand finding lower bounds and upper bounds for algorithms:</p>
<ul>
<li>Lower bounds allow us to find necessary conditions for the PAC guarantee, that is if <span class="math-container">$m \leq g(n)$</span> we lose the PAC guarantee <span class="math-container">$\mathbb{P}[\mathcal{L}_{\mathcal{D}}(h) \leq \epsilon] \leq \delta$</span></li>
<li>On the other hand, upper bound not only gives you sufficient conditions but also an algorithms that satisfies those conditions.</li>
</ul>
<p>Can someone explains to me where this contradiction comes from and what I don't understand?</p>
<p>Thanks,</p>

CC BY-SA 4.0
2023-11-20T02:06:58.627Z
Are you seeing this: "If $m \geq g(n)$, then learning succeeds, in other words, for learning to succeed, it suffices to choose $m = O(g(n))$."
usul
CC BY-SA 4.0
2023-11-26T08:51:43.073Z
@usul I guess it was my mistake, I didn't interpret papers proofs the way I should.
rivana
CC BY-SA 4.0
2023-11-26T08:56:52.697Z
I don't know if I ever saw a paper giving an intuitive interpretation about the usefulness of the bounds and why we actually look for matching bounds algorithms, that raises another question...
rivana
<lower-bounds><upper-bounds><pac-learning>
Confusion about lower bounds and upper bounds in learning theory
rivana
# Confusion about lower bounds and upper bounds in learning theory

(Asked by: username_0 on 2023-11-19)

In computer science, lower bounds and upper bounds are defined as follow:

$$m \geq g(n) \implies m = \Omega(g(n))$$

$$m \leq g(n) \implies m = \mathcal{O}(g(n))$$

However, in proving lower bounds and upper bounds for learning algorithms, I get confused, From papers\books Hoeffding inequality always gives you upper bounds, but in every book\paper: $ m \geq g(n) \implies m = \mathcal{O}(g(n))$ which contradicts classic definitions.

I know I'm wrong somewhere but I can't find the missing puzzle.

The way I understand finding lower bounds and upper bounds for algorithms:

* Lower bounds allow us to find necessary conditions for the PAC guarantee, that is if $m \leq g(n)$ we lose the PAC guarantee $\mathbb{P}[\mathcal{L}\_{\mathcal{D}}(h) \leq \epsilon] \leq \delta$
* On the other hand, upper bound not only gives you sufficient conditions but also an algorithms that satisfies those conditions.

Can someone explains to me where this contradiction comes from and what I don't understand?

Thanks,

**Tags:** lower-bounds, upper-bounds, pac-learning
> **Comments:**
> **username_1**: Are you seeing this: "If $m \geq g(n)$, then learning succeeds, in other words, for learning to succeed, it suffices to choose $m = O(g(n))$."  
> **username_0**: @usul I guess it was my mistake, I didn't interpret papers proofs the way I should.  
> **username_0**: I don't know if I ever saw a paper giving an intuitive interpretation about the usefulness of the bounds and why we actually look for matching bounds algorithms, that raises another question...  

---

## 1 answers

### Answer by username_2 on 2023-11-25. Score: 3 | Accepted answer

I invariably run into this issue when I teach learning theory. Indeed, the common notation causes a lot of confusion and is logically flawed.

To elaborate on Usul's comment. Upper bounds are of the form: Whenever sample size is at least $n\ge n\_0(\epsilon,\delta,\ldots)$, some generalization guarantee holds. Lower bounds are of the general form: Whenever sample size is less than $n\_1(\epsilon,\delta,\ldots)$, there exists an adversarial distribution that prevents the generalization bound from holding.

Given this setup, the logical big-O notation is $n\_0=O(\cdot)$ and $n\_1=\Omega(\cdot)$.

> **Comments:**
> **username_0**: With only few lines you removed the whole confusion :). I'm wondering if your lectures are available somewhere, I'd be grateful if you can share!  
> **username_0**: I think you shared a link of your lectures in this post: https://cstheory.stackexchange.com/questions/38694/rademacher-complexity-and-lowerbounds-in-learning-theory?rq=1. But it's not working anymore.  
> **username_2**: @rivana yes unfortunately my university disabled that platform and the content had to be taken down. email me and I'll send them to you  
> **username_0**: Thank you so much, it's so kind of you, I just sent you an email!  

---

