Proof of the following inequality from the given inequalities

Question

The following inequality is from Vapnik Statistical learning theory p.128 which I have no idea how to solve the following set of inequalities. In the context, $R(\alpha), R_{emp}(\alpha)$ are random variables, so the following inequalities are considered pointwisely.

Given \begin{align*} \epsilon = \sqrt{2\frac{\ln(N)-\ln\eta}{l}}, \qquad \frac{R(\alpha)-R_{emp}(\alpha)}{\sqrt{R(\alpha})}\leq \epsilon \end{align*}

It concludes

\begin{align} R(\alpha) < R_{emp}(\alpha)+\frac{\ln N-\ln\eta}{l}\left(1+ \sqrt{1 + 2\frac{R_{emp}(\alpha)l}{\ln N-\ln\eta}}\right) \end{align}

If written in $\epsilon$, it is of the form \begin{align} R(\alpha)<R_{emp}(\alpha)+ \frac{\epsilon^2}{2}\left(1+ \sqrt{1 + \frac{4 R_{emp}(\alpha)}{\epsilon^2}}\right) \end{align}

My attempt is like \begin{align} \frac{R(\alpha)-R_{emp}(\alpha)}{\sqrt{R(\alpha})}\leq \epsilon \quad &\Longleftrightarrow \quad R(\alpha)-R_{emp}(\alpha)\leq \epsilon \sqrt{R(\alpha})\\ &\Longleftrightarrow \quad R(\alpha)\leq R_{emp}(\alpha)+ \epsilon \sqrt{R(\alpha})\\ &\Longrightarrow \quad R(\alpha)\leq R_{emp}(\alpha)+ \epsilon \sqrt{\epsilon \sqrt{R(\alpha)}+R_{emp}(\alpha)}\\ &\Longrightarrow \quad R(\alpha)\leq R_{emp}(\alpha)+ \frac{\epsilon^2}{2}\sqrt{\frac{4\sqrt{R(\alpha)}}{\epsilon}+\frac{4R_{emp}(\alpha)}{\epsilon^2}} \end{align}

Somehow this is pretty closed to the target inequality. However, I just have no idea how to complete the last step. Also, in the context it is known \begin{align} 0\leq R(\alpha), R_{emp}(\alpha)\leq 1 \end{align} Does anyone have any idea?

Thanks in advance!

Answer 1

Since this is pointwise inequality, it seems that it's just the elementary solution of the quadratic equation.

For convenience, denote $R(\alpha) = x$ and $R_{emp}(\alpha) = R$. Then

$$\frac{R(\alpha)-R_{emp}(\alpha)}{\sqrt{R(\alpha})} \leq \epsilon ~~\implies ~ x-R \leq \epsilon \sqrt x ~~\implies ~ x^2- (2R+\epsilon^2)x + R^2\leq 0 $$ The fact that the leading coefficient of the quadratic form is positive means the solution is of the form $x_{-} \leq x \leq x_{+}$, where $$x_{\pm}=\frac12\left( 2R+\epsilon^2 \pm \sqrt{(2R+\epsilon^2)^2-4R^2}\right) = R + \frac{\epsilon^2}{2}\left(1 \pm \sqrt{1 + \frac{4 R}{\epsilon^2}} \right)$$

Given that $0<x<1$, presumably the minus solution $x_{-}$ is out (for being negative?) due to context, yielding $0< x \leq x_{+}$ as desired.