Concentration of coordinatewise Lipschitz function

872 Views Asked by At

Let $f:\mathbb R^n \to \mathbb R$ be coordinatewise $1$-Lipschitz, i.e $|f(x')-f(x)| \le |x'_k-x_k|$ whenever $x=(x_1,\ldots,x_n)$ and $x' = (x'_1,\ldots,x_n')$ are two vectors in $\mathbb R^n$ which only differ in their $k$th coordinates. Let $X=(X_1,\ldots,X_n)$ be a random vector in $\mathbb R^n$ with coordinates drawn iid from $\mathcal N(0,1)$ and define $Y:=f(X)$

Question. What is a non-trivial concentration inequality for $Y$ ?

Note. The particular function I have in mind is $f(x) := \max_{i \ne j} |x_i - x_j|$.

Observation

If one is too lazy, one can observe that any such $f$ is $n$-Lipschitz w.r.t the euclidean norm, and so by a standard result, we get $\mathbb P(|Y - \mathbb E[Y]| \ge t) \le 2e^{-t^2/(2n^2)}$. I'm hoping for a concentration inequality with a much better dependence on the dimension $n$. It is in this sense that I mean "nontrivial concentration inequality".

1

There are 1 best solutions below

0
On BEST ANSWER

You can get a tighter dependence on $n$ by using McDiarmid for Rademacher r.v.'s then using a standard "tensorization trick" to have the result carry over to the Gaussian measure: essentially, looking at $(\{-1,1\}^m)^n$ and define your new function $g\colon \{-1,1\}^{mn} \to \mathbb{R}$ by $$ g(x) = f\!\left( \frac{1}{\sqrt{m}}\sum_{k=1}^m x_k, \frac{1}{\sqrt{m}}\sum_{k=m1}^{2m} x_k, \dots, \frac{1}{\sqrt{m}}\sum_{k=(n-1)m+1}^{nm} x_k\right) $$ and applying McDiarmid to $g$ (which is $1/\sqrt{m}$-Lipschitz in each coordinate), before letting $m\to\infty$. See, e.g., Corollary 2.1 in these lecture notes.

This gives that, under your assumption of coordinate-wise $1$-Lipschitzness of $f\colon\mathbb{R}\to\mathbb{R}$ and under the standard Gaussian distribution, $$ \mathbb{P}\{ |f(X)-\mathbb{E}[f(X)] | \geq t \} \leq 2e^{-2t^2/n} \tag{$\dagger$} $$

Moreover, this bound is tight, as one can check by taking $f(x) = \sum_{k=1}^n x_k$ (as then $f(X)$ is itself Gaussian with mean $0$ and variance $n$).