Machine learning: Characteristics of the growth function 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 ?
 A: 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.
