On the tightness of Gaussian concentration for convex functions

The concentration of measure phenomenon in Gauss’ space states that every $L$-Lipschitz map $f$ on ${\mathbb{R}}^n$ satisfies [ \gamma_{n} \left({ x : | f(x) - M_{f} | \geqslant t } \right) \leqslant 2 e^{

• \frac{t^2}{ 2L^2} }, \quad t>0, ] where ${\gamma }_n$ is the standard Gaussian measure on ${\mathbb{R}}^n$ and $M_f$ is a median of $f$. In this work, we provide necessary and sufficient conditions for when this inequality can be reversed, up to universal constants, in the case when $f$ is additionally assumed to be convex. In particular, we show that if the variance $\mathrm{V}\mathrm{a}\mathrm{r}(f)$ (with respect to ${\gamma }_n$) satisfies $ \alpha L \leqslant \sqrt{ {\rm Var}(f) } $forsome$ 0<\alpha \leqslant 1$, then $${\gamma }_n(\{x:\mathrm{\mid }f(x)-M_f\mathrm{\mid }⩾t\})⩾c{e}^{-C\frac{t^2}{L^2}},t>0,$$ where $c,C>0$ are constants depending only on $\alpha$.