I having some trouble proving Lemma 5 of http://ttic.uchicago.edu/~dmcallester/margins.ps Any help would be greatly appreciated. I want to prove the following:
Let $X \in \mathbb{R}$ be a random variable such that $Pr(X \leq x) \leq e^{-m f(x)}$, where $f(x)$ is non-negative. Then $$Pr(e^{(m-1)f(X)} \geq \nu) \leq min(1, \nu^{-m/(m-1)}).$$
The only thing I can think would be applicable here is the Markov's inequality but the result does not follow from it.
Looks like the inequality follows from pure algebra but not without additional assumptions on the function $f$. For instance, it seems like $f(x)$ has to be a decreasing function of $x$ and invertible. \begin{align*} Pr(e^{(m-1) f(X)} \geq \nu) &= Pr(e^{-(m-1) f(X)} \leq \nu^{-1}) \\ &= Pr(e^{-f(X)} \leq \nu^{-1/(m-1)}) \\ &= Pr(-f(X) \leq \ln \nu^{-1/(m-1)}) \\ &= Pr(f(X) \geq \ln \nu^{1/(m-1)}) \\ &= Pr(X \leq f^{-1}(\ln \nu^{1/(m-1)})) && (\text{Here we use that f is decreasing}) \\ &\leq \exp\{-m \ln \nu^{1/(m-1)}\} = \nu^{-m/(m-1)} \end{align*}