1

I'm trying to prove the following:

$$m_H(2n) \le m_H(n)^2$$

So far the only thing I've been able to come up with is that they both are upper bounded by $2^{2n}$ using the definition of the growth function :

$$m_H(n) \le 2^n$$

Although that doesn't make much sense to me. Intuitively I would think that $m_H(2n)$ would be upper bounded by $m_H(n)^2$, so it doesn't make sense that they would have the same upper bound ?

W.R.P.S
  • 1,399
CPerkins
  • 13
  • Just curious, what is $m_H$? – Zoran Loncarevic Dec 31 '16 at 11:40
  • Sorry I should have stated in the post. $m_H(n)$ is the growth function that denotes the maximum number of ways to label n data points in a hypothesis space H. – CPerkins Dec 31 '16 at 11:43
  • Are you trying to prove this asymptotically or for all $n$? I think this may not be true for all $n$ and for all growth functions, but I believe that, for all growth functions, there exists an $N$ such that for all $n \ge N$, $m_H(2n) \le m_H(n)^2$. – Enrico Borba Dec 31 '16 at 12:56
  • I'm not sure. I assumed it meant for all n since my assignment didn't specify. I've been trying to find some answers in my books and the internet, but haven't found anything that made sense yet. Any help would be appreciated. – CPerkins Dec 31 '16 at 13:22

1 Answers1

1

So I assume you are familiar with the formalization of break points, or the minimum number $k$ of points such, for all arrangement of $k$ points, the number of decidable dichotomies is less than $2^k$.

Now, for a given growth function $m_H$, $k$ is the smallest number such that $m_H(k) < 2^k$ (emphasis on the sharp inequality). Some growth functions have no such breakpoints, and therefore, for these specific growth functions $m_H(n) = 2^n$ for all $n$. For these functions, we say the breakpoints are infinite, $k = \infty$. There is a theorem (proof sketch given here), that states:

Given a hypothesis set $H$ which has a finite breakpoint $k$, $$m_H(n) \le \sum_{i=0}^{k-1} \binom{n}{i} \in n^{O(1)}$$

Furthermore, in practice, growth functions with finite breakpoints are always bounded by polynomial on both sides. That is, using asymptotic notation, there exists a $c$ such that

$$ m_H(n) \sim n^c $$

So, now we wish to show

$$m_H(2n) \le m_H(n)^2$$

So, assume $H$ has an infinite breakpoint. Then, $m_H(n) = 2^n$ for all $n$. Thus, the inequality holds since $2^{2n} \le 2^{2n}$.

Assuming there is a finite breakpoint $k$, then, there exists a $c$ such that $m_H(n) \sim n^c$. Thus, we can see that, since $$2^cn^c \le n^{2c},$$

for large values of $n$, $m_H(2n) \le m_H(n)^2$.

Note: This is quite informal. The only real restrictions on the forms of growth functions is that they are bounded by $2^N$, if a finite breakpoint exists than they are upper bounded by a polynomial, and they are monotonically increasing. Because these aren't extremely strong restrictions, I feel that there exist conceivable growth functions for strange hypothesis sets such that the inequality we wish to prove is not true for all $N$. However, in practice, growth functions are polynomial and this is definitely true asymptotically.

Enrico Borba
  • 782
  • Ok great. That makes sense. My last question is couldn't we make the same conclusion by simply using the definition of the growth function like I did in the original post? – CPerkins Dec 31 '16 at 13:41
  • $m_h(2n) \le 2^{2n}$

    $m_h(n)^2 \le {(2^n)}^2 = 2^{2n}$

     – CPerkins Dec 31 '16 at 13:44
  • Well, since the both have the same upper bound, that isn't extremely useful. If the breakpoint is infinite, then yes, $m_H(2n) = m_H(n)^2 = 2^{2n}$. However, if the breakpoint if finite, the fact that we can say $m_H(n) \sim n^c$ is what allows us to say $2^cn^c \le n^{2c}$, which is what completes the proof. – Enrico Borba Dec 31 '16 at 13:45
  • Right on. I'll have to study your comment a bit more closely then so I understand it fully. Thank's a lot for the response :) – CPerkins Dec 31 '16 at 13:47
  • No problem, leave a comment if you have any doubts. – Enrico Borba Dec 31 '16 at 13:48