I have been working on a lemma (page 419 Understanding Machine Learning) and I understand every component of the proof but I do not understand how "the proof follows". Essentially I need help piecing the components of the proof together to obtain the result.
The proof is as follows:
LEMMA A.1 Let $a>0$. Then: $x\geq 2a\ln(a)\Rightarrow x\geq a\ln(x)$. It follows that a neccessary condition for the inequality $x<a\ln(x)$ to hold is that $x<2a\ln(a)$.
Proof. First note that for $a\in(0,\sqrt{e}]$ the inequality $x\geq a\ln(x)$ holds unconditionally and therefore the claim is trivial. From now on, assume that $a>\sqrt{e}$. Consider the function $f(x)=x-a\ln(x)$. The derivative is $f'(x)=1-a/x$. Thus, for $x>a$ the derivative is positive and the function increases. In addition,
\begin{eqnarray} f(2a\ln(a))&=&2a\ln(a)-a\ln(2a\ln(a))\\ &=&2a\ln(a)−a\ln(a)−a\ln(2\ln(a))\\ &=&a\ln(a)−a\ln(2\ln(a)). \end{eqnarray}
Since $a-2\ln(a)>0$ for all $a>0$, the proof follows.
I think I need to prove $x<a\log(x)\Rightarrow x<2a\log(a)$ rather than $x\geq 2a\log(a)\Rightarrow x\geq a\log(x)$ since the components of the proof involve strict inequalities?
What you suggest, $x<a\log(x)\Rightarrow x<2a\log(a)$, does not follow from the proposition.
The argument in the task is an argument taken from formal logic: A implies ($\Rightarrow$) B, is equivalent to saying: $\bar A$ is a necessary condition for $\bar B$.
Example: if it rains (A), (this implies that) the street is wet (B). This is equivalent to: for the street to be dry ($\bar B$), it is necessary that it doesn't rain ($\bar A$). It's not sufficient, since somebody can spill water on the street.
However, all of that is never being used in their proof. I guess they will use the argument later. For the proof, they always directly prove A ($\Rightarrow$) B .
In the proof's chain of arguments, they first prove that directly (for $a\in(0,\sqrt{e}]$), and then (for $a>\sqrt{e}$) they prove that $f(x)=x-a\ln(x) > 0$, or $x > a\ln(x)$, (B), when $x\geq 2a\ln(a)$ holds (A).
A little piece is missing. They say: "Thus, for $x>a$ the derivative is positive and the function increases." However, what they can take for granted is $x>2a\log(a)$. So they must show that $x>2a\log(a)$ implies $x>a$. That will be the case for $2 \log(a) > 1$ . Since we are in the domain $a>\sqrt{e}$, we have indeed $2 \log(a) > 2 \log \sqrt{e} = 1 $. So here we see that it makes sense to split the domain for $a$.