Confusion about lower bounds and upper bounds in learning theory

Question

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,

Answer 1

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)$.