# Talagrand's inequality for the discrete cube

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?

• 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. – Matt F. Jun 26 '19 at 17:21
• edited the question accordingly – alesia Jun 26 '19 at 18:17
• @MattF. the wikipedia version is an equivalent form of the same inequality – alesia Jun 26 '19 at 19:08
• 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. – Mateusz Kwaśnicki Jun 27 '19 at 6:39
• @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... – Paata Ivanishvili Jun 27 '19 at 17:46

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)$$.

• 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. – alesia Jun 28 '19 at 3:19
• 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. – Paata Ivanishvili Jun 28 '19 at 3:23
• 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. – Mateusz Kwaśnicki Jun 28 '19 at 6:02

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.

• 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? – Paata Ivanishvili Jun 27 '19 at 17:20
• 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. – Yuval Peres Jun 28 '19 at 7:27