My lecture notes state the following: We have, for all $t_0\geq 0$, $$ P\left(\|X(\beta-\beta^*)\|^2\geq 160k \cdot \log(2d/k)+8t_0\cdot k\right) \leq e^{-t_0\cdot k / 10}.$$
Then, using (for non-negative random variables $X$) that $E[X] = \int_0^\infty P(X\geq t) dt$, it follows from the inequality above that $$ E\left(\|X(\beta-\beta^*\|^2\right) \leq \mathcal{O}(\log(d/k))\cdot k $$ Can someone elaborate on how to get this?
Rephrased in an other way, the question is the following: if an non-negative random variable $Y$ satisfies for all $t\geqslant 0$ the inequalit $$ \Pr\left(Y\geqslant C+t\right)\leqslant e^{-t}, $$ what can be said on the expectation of $Y$. Write $\mathbb EY=\int_{0}^C\Pr\left(Y\geqslant s\right)ds+\int_C^{+\infty}\Pr\left(Y\geqslant s\right)ds$, bound the first integral by $C$ and for the second, do the substitution $s=t+C$ and use the bound on the tail of $Y$ to conclude.