On Dimension-dependent concentration for convex Lipschitz functions in product spaces

Abstract

Let $n\ge 1$, $K>0$, and let $X=(X_1,X_2,\dots ,X_n)$ be a random vector in ${\mathbb{R}}^n$ with independent $K$--subgaussian components. We show that for every $1$--Lipschitz convex function $f$ in ${\mathbb{R}}^n$ (the Lipschitzness with respect to the Euclidean metric), $$\max \left(\mathbb{P}\right\{f(X)-\mathrm{Med}f(X)\ge t\},\mathbb{P}\{f(X)-\mathrm{Med}f(X)\le -t\left\}\right)\le \exp (-\frac{c{t}^2}{K^2\log (2+\frac{n}{t^2/K^2})}),t>0,$$ where $c>0$ is a universal constant. The estimates are optimal in the sense that for every $n\ge \tilde{C}$ and $t>0$ there exist a product probability distribution $X$ in ${\mathbb{R}}^n$ with $K$--subgaussian components, and a $1$--Lipschitz convex function $f$, with $$\mathbb{P}\left\{\right|f(X)-\mathrm{Med}f(X)|\ge t\}\ge \tilde{c}\exp (-\frac{\tilde{C}{t}^2}{K^2\log (2+\frac{n}{t^2/K^2})}).$$ The obtained deviation estimates for subgaussian variables are in sharp contrast with the case of variables with bounded $\Vert X_i{\Vert }_{{\psi }_p}$--norms for $p\in [1,2)$.