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?


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

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

  • $\begingroup$ 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! $\endgroup$
    – rivana
    Nov 26 at 8:49
  • 1
    $\begingroup$ I think you shared a link of your lectures in this post: cstheory.stackexchange.com/questions/38694/…. But it's not working anymore. $\endgroup$
    – rivana
    Nov 26 at 8:58
  • $\begingroup$ @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 $\endgroup$
    – Aryeh
    Nov 26 at 9:02
  • 1
    $\begingroup$ Thank you so much, it's so kind of you, I just sent you an email! $\endgroup$
    – rivana
    Nov 26 at 9:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.