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

m a t h b b R^{n}

satisfies [ gamma_{n} left({ x : | f(x) - M_{f} | geqslant t } ight) leqslant 2 e^{ - frac{t^2}{ 2L^2} }, quad t>0, ] where

g a m m a_{n}

is the standard Gaussian measure on

m a t h b b 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

m V a r (f)

(with respect to

g a m m a_{n}

) satisfies

a l p h a L l e q s l a n t s q r t m V a r (f)

for some

0 < a l p h a l e q s l a n t 1

, then [ gamma_{n} left({ x : | f(x) - M_{f} | geqslant t } ight) geqslant c e^{ -C frac{t^2}{ L^2} } , quad t>0 ,] where

c, C > 0

are constants depending only on

a l p h a

.

Recommendations

Cites Work

Cited In (14)

This page was built for publication: On the tightness of Gaussian concentration for convex functions