8
$\begingroup$

Talagrand showed that if $f$ is a convex $1$-Lipschitz function on $\mathbb{R}^n$, and if $\mu$ is a product of probability measures supported over the interval, then $f$ has Gaussian concentration w.r.t. to $\mu$: $$ P(\vert f - E_{\mu}f\vert > \epsilon) < C \exp(-c\epsilon^2) $$ for some absolute constants $c$ and $C$.

I would like to understand to what extent convexity is necessary in the special case where $\mu$ is the uniform measure on the discrete hypercube $\{0,1\}^n$. What are "representative" counterexamples if convexity is not assumed?

$\endgroup$
  • $\begingroup$ Will you provide a more precise statement or a reference for an appropriate version of Talagrand's inequality? Wikipedia has en.wikipedia.org/wiki/Talagrand%27s_concentration_inequality but that does not have an explicit Lipschitz hypothesis. The comment there, "this provides insufficient context for those unfamiliar with the subject", applies here too. $\endgroup$ – Matt F. Jun 26 at 17:21
  • $\begingroup$ edited the question accordingly $\endgroup$ – alesia Jun 26 at 18:17
  • $\begingroup$ @MattF. the wikipedia version is an equivalent form of the same inequality $\endgroup$ – alesia Jun 26 at 19:08
  • $\begingroup$ Any function on $\{0,1\}^n$ can be extended to a "piecewise affine" convex function on $[0,1]^n$, and if I am not mistaken, this extension does not increase the Lipschitz constant. So it appears that for this particular $\mu$ one can completely drop the assumption that $f$ is convex. $\endgroup$ – Mateusz Kwaśnicki Jun 27 at 6:39
  • 1
    $\begingroup$ @MateuszKwaśnicki, Can you provide a reference that such extension will not increase Lipschitz constant? I am asking this because I think if you would take a convex envelope then the Lipschitz constant can increase. It may be some sort of Kirszbraun theorem but I do not remember any convexity assumptions... $\endgroup$ – Paata Ivanishvili Jun 27 at 17:46
5
$\begingroup$

there is no convexity assumption needed there.

Nevertheless here is a counterexample of $1$-Lipschitz function on $\mathbb{R}^{N}$ which fails to satisfy concentration inequality on the Hamming cube $\{-1,1\}^{N}$ as $N$ goes to infinity.

Take $N$ to be even. Let $$ A = \left\{ (x_{1}, \ldots, x_{N}) \in \{0,1\}^{N}\, : x_{1}+\ldots+x_{N}\leq \frac{N}{2}\right\}. $$ Next, define a function

$$ f(x) = \inf_{y \in A} \| x-y\|_{\mathbb{R}^{N}} $$ Since $f$ is the distance function to a nonempty subset it follows that $f$ is $1$-Lipschitz (an exercise).

On the other hand notice that $f(x) = \sqrt{\max\{x_{1}+\ldots+x_{N} - \frac{N}{2},0\}}$ on $\{0,1\}^N$. Then as $N$ goes to infinity we have $$ \begin{aligned} P(|f & -\mathbb{E}f| > N^{1/4}) \\ & = P\biggl(\biggl|\sqrt{\max\{\frac{(2x_{1}-1)+\ldots+(2x_{N}-1)}{\sqrt{N}},0\}} \\ & \qquad\qquad - \mathbb{E}\sqrt{\max\{\frac{(2x_{1}-1)+\ldots+(2x_{N}-1)}{\sqrt{N}},0\}} \biggr|>\sqrt{2} \biggr) \\ & \to P\left( | \sqrt{\max\{\xi, 0\}} - \mathbb{E} \sqrt{\max\{\xi, 0\}}|>\sqrt{2}\right)>10^{-10}, \end{aligned} $$ where we used the central limit theorem, and $\xi$ is the standard normal Gaussian $\xi\in N(0,1)$.

$\endgroup$
  • 1
    $\begingroup$ Shouldn't there be square roots appearing in the limit as well (if so it's a detail)? Nice example anyway, wouldn't have expected that even the variance can get that large. $\endgroup$ – alesia Jun 28 at 3:19
  • $\begingroup$ Yes there should be square roots, I will fix it, thank you. This detail is not important because it will only change the number $\frac{1}{10^{6}}$ which is till again nonzero. I will put $10^{-10}$ just to be on the safe side. $\endgroup$ – Paata Ivanishvili Jun 28 at 3:23
  • $\begingroup$ Very nice example! I edited it so that the big display fits my screen, and I also added a note that the inequality $f(x) \geqslant \sqrt{\max\{\ldots\}}$ only holds on $\{0,1\}^N$; hope you do not mind this edit. $\endgroup$ – Mateusz Kwaśnicki Jun 28 at 6:02
7
$\begingroup$

Talagrand's inequality is more general. The inequality you ask about is Mcdiarmid's bounded-difference inequality (see, e.g., https://en.wikipedia.org/wiki/Doob_martingale and McDiarmid, Colin (1989). "On the Method of Bounded Differences". Surveys in Combinatorics. 141: 148–188), which is a direct consequence of the Hoeffding-Azuma inequality. there is no convexity assumption needed there. McDiarmid's bound (which leads to weaker concentration) is essentially sharp for functions that are Lipschitz in the $\ell^1$ metric, which is often the most relevant to combinatorial applications; in that case convexity is not needed and does not help: Consider $f(x_1,x_2,...,x_n)=\sum_i x_i$. Requiring Lipschitz in $\ell^2$ is a much stronger requirement, which also leads to better concentration for convex functions and I now understand that was the assumption of interest to the OP.

$\endgroup$
  • 1
    $\begingroup$ But Mcdiarmid's bounded-difference inequality gives the bound $P(|f-\mathbb{E}f|>t) \leq C e^{-ct^{2}/n}$ since $|f(x_{1}, \ldots,x_{j}, \ldots x_{n})-f(x_{1}, \ldots, 1-x_{j}, \ldots, x_{n})|\leq 1=c_{j}$, $\sum c_{j}^{2} =n$. But the question is with bound independent of $n$. Am I missing something? $\endgroup$ – Paata Ivanishvili Jun 27 at 17:20
  • 1
    $\begingroup$ McDiarmid's bound is essentially sharp for functions that are Lipschitz in the $\ell^1$ metric, which is often the most relevant to combinatorial applications; in that case convexity is not needed and does not help. Requiring Lipschitz in $\ell^2$ is a much stronger requirement, which also leads to better concentration for convex functions. I will edit my answer to reflect this. $\endgroup$ – Yuval Peres Jun 28 at 7:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.