Proving concentration from CDF

Question

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.

Answer 1

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*}