# Confusion about lower bounds and upper bounds in learning theory

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,

• 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
Nov 20 at 2:06
• @usul I guess it was my mistake, I didn't interpret papers proofs the way I should. Nov 26 at 8:51
• 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... Nov 26 at 8:56

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