On the tightness of Gaussian concentration for convex functions

Abstract

The concentration of measure phenomenon in Gauss' space states that every $L$-Lipschitz map $f$ on ${\mathbb{R}}^n$ satisfies \[ γ_{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{Var}(f)$ (with respect to ${\gamma }_n$) satisfies $\alpha L⩽\sqrt{\mathrm{Var}(f)}$ for some $0<\alpha ⩽1$, then \[ γ_{n} \left(\{ x : | f(x) - M_{f} | \geqslant t \}\right) \geqslant c e^{ -C \frac{t^2}{ L^2} } , \quad t>0 ,\] where $c,C>0$ are constants depending only on $\alpha$.

14 pages; preliminary version