Talagrand's Convex-Distance Inequality

Why This Matters

Take $n$ independent coordinates $X_1, \ldots, X_n$ with values in $[0,1]$ and a function $f$ that is convex and 1-Lipschitz for the Euclidean norm. McDiarmid's inequality sees only coordinatewise sensitivity: changing one coordinate moves $f$ by at most 1, so the bound $\exp(-2t^2/n)$ confines $f(X)$ to a window of width of order $\sqrt n$. That window says nothing, since the cube $[0,1]^n$ itself has diameter $\sqrt n$.

Talagrand's convex-distance inequality gives the same function a window of constant width:

$$\mathbb{P}\bigl(|f(X) - M| \ge t\bigr) \le 4 e^{-t^2/4},$$

where $M$ is a median of $f(X)$. The bound does not depend on $n$, and it does not depend on the laws of the $X_i$ beyond independence and the range $[0,1]$. Tao (2009) makes the comparison explicit: Azuma and McDiarmid give concentration of order $\sqrt n$ for such functions, which is trivial on a cube of diameter of order $\sqrt n$, while Talagrand's inequality gives order 1 because it uses convexity and the Lipschitz property in all directions at once.

For Gaussian coordinates, dimension-free concentration of Lipschitz functions is classical (see measure concentration). Talagrand's inequality reaches arbitrary bounded product measures and pays for it with convexity. The same inequality also handles functions that are not convex but have short certificates, such as the length of the longest increasing subsequence (Talagrand 1995, Section 7.1).

Mental Model

McDiarmid charges every coordinate its worst-case influence and adds the squares. The convex distance lets the weights depend on the point: $d_T(x, A)$ is the largest weighted Hamming distance from $x$ to $A$ over all nonnegative weight vectors of unit Euclidean norm. A point is close to $A$ in this sense only if, for every such weighting, some point of $A$ agrees with $x$ on most of the weight. The inequality says that under any product measure, the points that are far from a set of probability $1/2$ in this demanding sense have Gaussian-small probability.

To use the inequality on a function one needs a bridge from $d_T$ to that function. There are two standard bridges:

1. Convexity. A point with small convex distance to a sublevel set is Euclidean-close to the convex hull of that set, and a convex function stays below the level on the hull.
2. Certificates. If $f(x) \ge s$ is witnessed by a small set of coordinates, put the weight on exactly those coordinates.

Formal Setup

Let $\Omega = \Omega_1 \times \cdots \times \Omega_n$ be a product of probability spaces with product measure $P = \mu_1 \otimes \cdots \otimes \mu_n$, and let $X = (X_1, \ldots, X_n) \sim P$. The coordinates are independent; they need not be identically distributed or real-valued. Throughout, $A \subseteq \Omega$ is measurable and the map $x \mapsto d_T(x, A)$ is assumed measurable. Both hold automatically when every $\Omega_i$ is finite.

Definition

Weighted Hamming distance$d_{\alpha }(x,A)$

For $\alpha \in \mathbb{R}^n$ with every $\alpha_i \ge 0$, a point $x \in \Omega$, and a nonempty set $A \subseteq \Omega$,

$$d_\alpha(x, A) = \inf_{y \in A} \sum_{i=1}^n \alpha_i \, \mathbf{1}\{x_i \ne y_i\}.$$

With $\alpha = (1, \ldots, 1)$ this is the Hamming distance $H(x, A)$, the least number of coordinates in which $x$ differs from a point of $A$.

Definition

Convex distance$d_T(x,A)$

$$d_T(x, A) = \sup\Bigl\{ d_\alpha(x, A) : \alpha \in \mathbb{R}^n,\ \alpha_i \ge 0 \text{ for all } i,\ \|\alpha\|_2 = 1 \Bigr\}.$$

The name comes from an equivalent description (Talagrand 1995, Section 4.1). Let

$$U_A(x) = \bigl\{ s \in \{0,1\}^n : \text{there is } y \in A \text{ with } y_i = x_i \text{ whenever } s_i = 0 \bigr\},$$

the patterns of coordinates that $x$ may change to reach $A$, and let $V_A(x)$ be the convex hull of $U_A(x)$ in $\mathbb{R}^n$. Then

$$d_T(x, A) = \min_{s \in V_A(x)} \|s\|_2 ,$$

the Euclidean distance from the origin to $V_A(x)$. Talagrand defines his distance $f_c(A, x)$ this way and records the weighted Hamming form in his Lemma 4.1.2. Tao (2010, Notes 1) calls the same object the combinatorial distance.

The equivalence is a short projection argument. For $\alpha \ge 0$ the linear map $s \mapsto \langle \alpha, s \rangle$ has the same infimum over $U_A(x)$ as over its convex hull, and that infimum equals $d_\alpha(x, A)$: each $y \in A$ contributes its disagreement pattern $(\mathbf{1}\{x_i \ne y_i\})_i \in U_A(x)$, and each $s \in U_A(x)$ dominates the disagreement pattern of its witness coordinatewise. Cauchy-Schwarz then gives $d_\alpha(x, A) \le \|\alpha\|_2 \min_{s \in V_A(x)} \|s\|_2$. For the reverse inequality let $s^\star$ be the point of $V_A(x)$ nearest the origin. If $s^\star \ne 0$, the weight $\alpha = s^\star/\|s^\star\|_2$ is nonnegative, and the projection inequality $\langle s, s^\star \rangle \ge \|s^\star\|_2^2$ for $s \in V_A(x)$ gives $d_\alpha(x, A) \ge \|s^\star\|_2$.

Three facts are used repeatedly:

1. $d_T(x, A) = 0$ if and only if $x \in A$.
2. $H(x, A)/\sqrt n \le d_T(x, A) \le \sqrt{H(x, A)}$ (Exercise 1).
3. $d_T$ is not a metric on $\Omega$. It compares a point with a set, and the optimal weights depend on the point.

The Convex-Distance Inequality

Theorem

Talagrand's Convex-Distance Inequality

Statement

$$\mathbb{P}(X \in A)\;\mathbb{E}\exp\!\left(\frac{d_T(X, A)^2}{4}\right) \le 1 .$$

Consequently, for every $t \ge 0$,

$$\mathbb{P}(X \in A)\;\mathbb{P}\bigl(d_T(X, A) \ge t\bigr) \le e^{-t^2/4},$$

and if $\mathbb{P}(X \in A) \ge 1/2$ then $\mathbb{P}(d_T(X, A) \ge t) \le 2e^{-t^2/4}$ (Talagrand 1995, Theorem 4.1.1).

Intuition

Build $d_T(X, A)^2$ one coordinate at a time. For the newest coordinate there are two options: insist that it match, which costs nothing but restricts attention to a section of $A$ that may be small, or give it up, which costs 1 but only requires the other coordinates to reach the larger projection of $A$. The proof mixes the two options with weights $\lambda$ and $1 - \lambda$. Hölder's inequality turns the mixture into a geometric mean of the two probabilities, and a one-variable inequality shows that the product $\mathbb{P}(A)\,\mathbb{E}e^{d_T^2/4}$ never exceeds 1 when a coordinate is added.

Proof Sketch

The proof is by induction on $n$ and follows Talagrand (1995, Section 4.1).

A numerical lemma. For $0 \le r \le 1$,

$$\inf_{0 \le \lambda \le 1} r^{-\lambda} \exp\!\left(\frac{(1-\lambda)^2}{4}\right) \le 2 - r$$

(Talagrand 1995, Lemma 4.1.3). If $r < e^{-1/2}$, take $\lambda = 0$; the claim $e^{1/4} \le 2 - r$ holds because $e^{1/4} + e^{-1/2} < 2$. If $r \ge e^{-1/2}$, take $\lambda = 1 + 2\log r$. After taking logarithms the claim becomes $g(r) = \log(2 - r) + \log r + (\log r)^2 \ge 0$. Since $g(1) = 0$ and $r g'(r)$ vanishes at $r = 1$ and has derivative $2/r - 2/(2-r)^2 \ge 0$, $g$ is nonincreasing on $(0, 1]$.

One coordinate. If $n = 1$, then $d_T(x, A) = 0$ for $x \in A$ and $d_T(x, A) = 1$ otherwise. With $p = \mathbb{P}(X \in A)$ the claim reads $p\,\bigl(p + (1 - p)e^{1/4}\bigr) \le 1$. The left side is increasing in $p \in [0, 1]$ and equals 1 at $p = 1$.

Adding a coordinate. Write a point of $\Omega \times \Omega_{n+1}$ as $z = (x, \omega)$, and write $P$ for the product measure on the first $n$ coordinates. For a set $A$ in the larger space let $A(\omega) = \{x : (x, \omega) \in A\}$ be its section and $B$ its projection onto $\Omega$. If $s \in U_{A(\omega)}(x)$ then $(s, 0) \in U_A(z)$, and if $u \in U_B(x)$ then $(u, 1) \in U_A(z)$. Taking convex combinations, for $s \in V_{A(\omega)}(x)$, $u \in V_B(x)$ and $\lambda \in [0, 1]$ the point $(\lambda s + (1 - \lambda) u,\ 1 - \lambda)$ lies in $V_A(z)$. Convexity of $v \mapsto \|v\|_2^2$ gives

$$d_T(z, A)^2 \le (1 - \lambda)^2 + \lambda\, d_T\bigl(x, A(\omega)\bigr)^2 + (1 - \lambda)\, d_T(x, B)^2 .$$

Fix $\omega$ and integrate in $x$. Hölder's inequality with exponents $1/\lambda$ and $1/(1 - \lambda)$, followed by the induction hypothesis for $A(\omega)$ and for $B$, gives

$$\int \exp\!\left(\frac{d_T((x, \omega), A)^2}{4}\right) dP(x) \le \frac{1}{P(B)}\; r^{-\lambda} \exp\!\left(\frac{(1 - \lambda)^2}{4}\right), \qquad r = \frac{P(A(\omega))}{P(B)} \le 1 .$$

Only now choose $\lambda$, depending on $\omega$, from the numerical lemma, so the right side is at most $(2 - r)/P(B)$. Talagrand describes declining to optimize over $\lambda$ before this point as the main trick of the proof. When $r = 0$ the lemma uses $\lambda = 0$, so an empty section causes no trouble. Integrating over $\omega$ with Fubini's theorem and writing $v = \mathbb{P}(A)/P(B)$,

$$\mathbb{E}\exp\!\left(\frac{d_T(Z, A)^2}{4}\right) \le \frac{2 - v}{P(B)} = \frac{v\,(2 - v)}{\mathbb{P}(A)} \le \frac{1}{\mathbb{P}(A)},$$

because $v(2 - v) \le 1$ for every real $v$.

Tail form. Markov's inequality applied to $\exp(d_T(X, A)^2/4)$ turns the first display of the statement into the second.

Why It Matters

The theorem is a statement about sets, and applications follow one template: choose a set $A$ of probability at least $1/2$, usually a sublevel set of the quantity of interest; show that a point where the quantity is large has large convex distance to $A$; read off the tail. Talagrand (1995) runs this template on bin packing (Section 6), longest increasing and longest common subsequences (Section 7), percolation (Section 8), the chromatic number of random graphs (Section 9), the assignment problem (Section 10), and geometric probability, including the traveling salesman problem (Section 11). No martingale structure and no smoothness of the coordinate distributions is needed.

Failure Mode

Independence is used in the Hölder and Fubini steps and cannot be dropped. Let $X_1 = \cdots = X_n$ be one fair bit copied $n$ times and let $A$ be the set of $x \in \{0,1\}^n$ with at least $n/2$ zeros, so $\mathbb{P}(X \in A) = 1/2$. From $x = (1, \ldots, 1)$ every pattern in $U_A(x)$ has at least $n/2$ ones, so every $s \in V_A(x)$ has coordinate sum at least $n/2$ and Euclidean norm at least $\sqrt n/2$. Hence $\mathbb{P}(d_T(X, A) \ge \sqrt n/2) = 1/2$, while the product-measure bound would force it to be at most $2e^{-n/16}$, which is less than $1/2$ for $n \ge 23$.

The theorem also says nothing directly about Euclidean or Hamming distance. Passing from $d_T$ to a function of interest needs extra structure, and without it the conclusion can fail for the function even though it holds for $d_T$ (Exercise 3).

report a correction →

Convex Lipschitz Functions

Lemma

Convex Distance Controls Euclidean Distance to the Convex Hull

Statement

If $x \in [0,1]^n$ and $A \subseteq [0,1]^n$ is nonempty, then

$$\operatorname{dist}_2\bigl(x, \operatorname{conv} A\bigr) \le d_T(x, A).$$

Proof Sketch

Let $s \in V_A(x)$ attain $\|s\|_2 = d_T(x, A)$ and write $s = \sum_k \theta_k s^k$ as a convex combination of patterns $s^k \in U_A(x)$ with witnesses $y^k \in A$, so $y^k_i = x_i$ whenever $s^k_i = 0$. Put $w = \sum_k \theta_k y^k \in \operatorname{conv} A$. All coordinates lie in $[0,1]$, so $|x_i - y^k_i| \le s^k_i$ for every $i$ and $k$, and therefore $|x_i - w_i| \le \sum_k \theta_k |x_i - y^k_i| \le s_i$. Hence $\|x - w\|_2 \le \|s\|_2$.

report a correction →

Tao (2010, Notes 1, Lemma 10) proves the same comparison for convex sets in a product of unit disks, where the factor is 2 because a disk has diameter 2.

Corollary

Concentration of Convex Lipschitz Functions

Statement

Let $X_1, \ldots, X_n$ be independent with values in $[a, b]$, let $f : [a, b]^n \to \mathbb{R}$ be convex and $L$-Lipschitz with respect to $\|\cdot\|_2$, and let $M$ be a median of $f(X)$. For every $t \ge 0$,

$$\mathbb{P}\bigl(f(X) \ge M + t\bigr) \le 2\exp\!\left(-\frac{t^2}{4L^2(b - a)^2}\right), \qquad \mathbb{P}\bigl(f(X) \le M - t\bigr) \le 2\exp\!\left(-\frac{t^2}{4L^2(b - a)^2}\right).$$

Hence $\mathbb{P}(|f(X) - M| \ge t) \le 4\exp(-t^2/(4L^2(b-a)^2))$, and integrating the tail gives $\mathbb{E}|f(X) - M| \le 4\sqrt{\pi}\,L(b - a)$.

Intuition

A convex function stays below $M$ on the whole convex hull of its sublevel set $\{f \le M\}$. If $f(x) \ge M + t$, the Lipschitz property puts $x$ at Euclidean distance at least $t/L$ from that hull, and the lemma converts distance to the hull into convex distance to the set. The theorem bounds the probability of being that far.

Proof Sketch

The affine change of variables $u \mapsto a + (b - a)u$, followed by division by $L(b - a)$, reduces to $[a, b] = [0, 1]$ and $L = 1$.

Upper tail: let $A = \{y : f(y) \le M\}$, so $\mathbb{P}(X \in A) \ge 1/2$. If $f(x) \ge M + t$ and $w \in \operatorname{conv} A$, then $f(w) \le M$ by convexity, so $t \le f(x) - f(w) \le \|x - w\|_2$. The lemma gives $d_T(x, A) \ge t$, and the theorem gives $\mathbb{P}(f(X) \ge M + t) \le 2e^{-t^2/4}$.

Lower tail: let $A = \{y : f(y) \le M - t\}$. The same argument shows $d_T(x, A) \ge t$ whenever $f(x) \ge M$, an event of probability at least $1/2$. The theorem gives $\mathbb{P}(X \in A) \cdot \tfrac{1}{2} \le e^{-t^2/4}$.

Why It Matters

The window width $L(b - a)$ does not involve $n$. McDiarmid applied to the same function has bounded-difference constants $c_i = L(b - a)$ and tail $\exp(-2t^2/(nL^2(b - a)^2))$, a window of width of order $\sqrt n\,L(b - a)$. A mean-centered version with a better constant also holds: for independent coordinates in $[0, 1]$ and differentiable convex $f$, van Handel (2016, Corollary 4.23) shows that $f(X)$ is $\sigma^2$-subgaussian with $\sigma^2 = \sup_x \|\nabla f(x)\|_2^2$. For a 1-Lipschitz $f$ this gives $\mathbb{P}(f(X) - \mathbb{E}f(X) \ge t) \le e^{-t^2/2}$ and the same bound for the lower tail. His proof goes through a transportation inequality (van Handel 2016, Section 4.3) rather than the induction above.

Failure Mode

Convexity is used in both tails and cannot be replaced by the Lipschitz property alone: Exercise 3 builds a 1-Lipschitz, non-convex function on $\{0,1\}^n$ whose fluctuations are of order $n^{1/4}$. The Lipschitz constant must be taken for the Euclidean norm. A function that is 1-Lipschitz for $\|\cdot\|_1$, such as $\sum_i x_i$, can have Euclidean Lipschitz constant $\sqrt n$, and then the bound is no better than McDiarmid's. Boundedness enters through $(b - a)^2$; for unbounded coordinates the corollary gives nothing without truncation.

report a correction →

Worked Example: The Largest Eigenvalue of a Random Symmetric Matrix

Example

Top eigenvalue and operator norm with bounded entries

Let $W$ be an $n \times n$ symmetric random matrix whose entries $W_{ij}$ with $i \le j$ are independent, satisfy $|W_{ij}| \le 1$, and determine the rest through $W_{ji} = W_{ij}$. Treat $\lambda_{\max}(W)$ as a function of the $N = n(n+1)/2$ independent coordinates $w = (W_{ij})_{i \le j} \in [-1, 1]^N$.

Convexity. $\lambda_{\max}(W) = \sup_{\|v\|_2 = 1} v^\top W v$ is a supremum of linear functions of $w$, so it is convex. The same holds for $\|W\|_{\mathrm{op}} = \sup_{\|u\|_2 = \|v\|_2 = 1} u^\top W v$.

Lipschitz constant. For symmetric $W$ and $W'$ with coordinate vectors $w$ and $w'$,

$$|\lambda_{\max}(W) - \lambda_{\max}(W')| \le \|W - W'\|_{\mathrm{op}} \le \|W - W'\|_F = \Bigl(\sum_{i} (w_{ii} - w'_{ii})^2 + 2\sum_{i < j} (w_{ij} - w'_{ij})^2\Bigr)^{1/2} \le \sqrt{2}\,\|w - w'\|_2 .$$

Tail. The corollary with $L = \sqrt 2$ and $b - a = 2$ gives, for a median $M$ of $\lambda_{\max}(W)$,

$$\mathbb{P}\bigl(|\lambda_{\max}(W) - M| \ge t\bigr) \le 4 e^{-t^2/32},$$

and the same bound holds for $\|W\|_{\mathrm{op}}$ around its median. This is the $s = 1$ case of Alon, Krivelevich, and Vu (2002, Theorem 1), who use Talagrand's inequality to bound the deviation of the $s$-th largest eigenvalue from its median by $4e^{-t^2/(32 s^2)}$. Tao (2010, Notes 3, Proposition 14) proves the analogous operator-norm bound, with unspecified absolute constants, for the non-symmetric model in which all $n^2$ entries are independent, mean zero, and bounded by 1.

Scale. For a symmetric random sign matrix every column has Euclidean norm $\sqrt n$, so $\|W\|_{\mathrm{op}} \ge \sqrt n$, and $\|W\|_{\mathrm{op}} = O(\sqrt n)$ with overwhelming probability (Tao 2010, Notes 3, Corollary 8). The median of the norm is therefore of order $\sqrt n$, and the window above is small relative to it. McDiarmid on the same coordinates has $c_{ij} = 2$ for each of the $N$ coordinates and gives $\exp(-t^2/(2N))$, a window of order $n$, which is larger than the median itself. The inequality is not sharp: Tao (2010, Notes 3) notes that under additional assumptions the Tracy-Widom law gives fluctuations of order $n^{-1/6}$. Talagrand's inequality also says nothing about where the median is; that requires the moment method or matrix concentration.

Worked Example: Longest Increasing Subsequence

The length of the longest increasing subsequence is not a convex function of the points, but it has short certificates, and the convex distance handles those directly.

Example

Fluctuations of the longest increasing subsequence

Let $X_1, \ldots, X_N$ be independent and uniform on $[0, 1]$, let $L_N(x)$ be the length of the longest increasing subsequence of $x_1, \ldots, x_N$, and let $A(a) = \{y : L_N(y) \le a\}$.

Certificate step (Talagrand 1995, Lemma 7.1.1). Fix $x$ with $L_N(x) = m$ and let $I$ index an increasing subsequence of length $m$. Take $\alpha = m^{-1/2}\mathbf{1}_I$. The weighted Hamming form of $d_T$ yields $y \in A(a)$ that differs from $x$ on at most $\sqrt m\, d_T(x, A(a))$ indices of $I$. The remaining indices of $I$ still carry an increasing subsequence of $y$, so

$$a \ge L_N(y) \ge m - \sqrt m\; d_T\bigl(x, A(a)\bigr), \qquad \text{that is,} \qquad d_T\bigl(x, A(a)\bigr) \ge \frac{m - a}{\sqrt m}.$$

Tails. Let $M$ be a median of $L_N = L_N(X)$. For $a \ge 0$ the map $m \mapsto (m - a)/\sqrt m$ is increasing. Taking $a = M$ and applying the theorem gives the upper tail. Taking $a = M - u$ and using $\mathbb{P}(L_N \ge M) \ge 1/2$ gives the lower tail:

$$\mathbb{P}(L_N \ge M + u) \le 2\exp\!\left(-\frac{u^2}{4(M + u)}\right), \qquad \mathbb{P}(L_N \le M - u) \le 2\exp\!\left(-\frac{u^2}{4M}\right)$$

(Talagrand 1995, Theorem 7.1.2).

Scale. For i.i.d. uniform points, $L_N$ has the law of the longest increasing subsequence of a uniform random permutation of $\{1, \ldots, N\}$ (Talagrand 1995, Section 7.1). Baik, Deift, and Johansson (1999) show that this length, centered by $2\sqrt N$ and scaled by $N^{1/6}$, converges in distribution to the Tracy-Widom law. So $M$ is of order $\sqrt N$ and Talagrand's bound confines $L_N$ to a window of order $N^{1/4}$. McDiarmid, with $c_i = 1$, gives only $\exp(-2u^2/N)$, a window of order $N^{1/2}$ (see the example on the McDiarmid page). Neither bound reaches the true $N^{1/6}$ scale.

The argument uses only one property of $L_N$: its value at $x$ is certified by a set of coordinates whose size equals that value. Talagrand calls such functions configuration functions and proves the same two tail bounds for all of them (Talagrand 1995, Theorem 7.1.3).

Comparison with McDiarmid, Gaussian Concentration, and Other Talagrand Results

The rows come from McDiarmid's inequality as stated on its page, van Handel (2016, Theorem 3.25) for Gaussian coordinates, the corollary above, Bousquet (2002, Theorem 2.3), and Massart (1990).

Against McDiarmid. Bounded differences constrain $f$ one coordinate at a time. For a convex $L$-Lipschitz function of coordinates in $[a, b]$ the coordinatewise constants add up to $\sum_i c_i^2 = nL^2(b - a)^2$, even though $f$ is $L$-Lipschitz in every direction simultaneously. Tao (2009) notes that Azuma's inequality uses the Lipschitz property only along coordinate directions, and in exchange works as well for the larger $\ell^1$ metric. McDiarmid keeps two advantages: it needs no convexity, and it is centered at the mean with an explicit constant.

Against Gaussian concentration. For standard Gaussian coordinates every 1-Lipschitz $f$ satisfies $\mathbb{P}(f(X) - \mathbb{E}f(X) \ge t) \le e^{-t^2/2}$ (van Handel 2016, Theorem 3.25), with no convexity. On the discrete cube $\{0,1\}^n$, convexity cannot be dropped (Exercise 3). The uniform law on $[0,1]^n$ behaves differently: $X_i = \Phi(G_i)$ for standard Gaussian $G_i$, and the Gaussian distribution function $\Phi$ is $(2\pi)^{-1/2}$-Lipschitz, so every 1-Lipschitz function of uniform coordinates is a Lipschitz function of Gaussian ones. In Tao's (2009) summary, Lipschitz functions of Gaussian variables concentrate as if they were Gaussian, and Talagrand's inequality says the same for convex Lipschitz functions of Bernoulli variables.

Where It Is Used in Learning Theory and ML

Rademacher sums conditional on the data. Fix a sample $x_1, \ldots, x_n$ and a class $\mathcal{F}$ with $\sigma_{\mathcal{F}} = \sup_{f \in \mathcal{F}} \bigl(\sum_i f(x_i)^2\bigr)^{1/2} < \infty$. For signs $\varepsilon \in \{-1, 1\}^n$ let

$$Z(\varepsilon) = \sup_{f \in \mathcal{F}} \sum_{i=1}^n \varepsilon_i f(x_i).$$

$Z$ is convex in $\varepsilon$ as a supremum of linear functions, and Cauchy-Schwarz makes it $\sigma_{\mathcal{F}}$-Lipschitz for $\|\cdot\|_2$. With independent Rademacher signs, the corollary on $[-1, 1]^n$ gives $\mathbb{P}(|Z - M| \ge t) \le 4\exp(-t^2/(16\sigma_{\mathcal{F}}^2))$, so one draw of signs estimates $\mathbb{E}_\varepsilon Z$, which is $n$ times the empirical Rademacher complexity, to within a multiple of $\sigma_{\mathcal{F}}$. McDiarmid on the same variable uses $c_i = 2\sup_f |f(x_i)|$, so its scale is $\bigl(\sum_i \sup_f f(x_i)^2\bigr)^{1/2}$: the supremum sits inside the sum instead of outside. For the linear class $\{x \mapsto \langle w, x \rangle : \|w\|_2 \le B\}$ with data matrix $X \in \mathbb{R}^{n \times d}$, the two scales are $B\|X\|_{\mathrm{op}}$ and $B\|X\|_F$. Their squared ratio is the stable rank of $X$, which can be as large as $\min(n, d)$ (Exercise 5).

Random matrices. For matrices with independent bounded entries, the eigenvalue example splits a norm bound into two separate questions: the fluctuation, which is $O(1)$ by Talagrand's inequality whatever the dimension, and the location of the median, which needs the moment method or matrix concentration.

Suprema of empirical processes. Uniform deviation bounds need the supremum $\sup_{g} \sum_i g(X_i)$ to concentrate around its mean. Bounded differences give a range-based tail. Talagrand's empirical-process inequality, in Bousquet's form, gives an upper tail driven by $v = n\sigma^2 + 2\mathbb{E}Z$. Its hypotheses are i.i.d. $X_i$, a countable class of functions $g$ with $\mathbb{E}g(X_1) = 0$ and $g \le 1$, and $\sigma^2 \ge \sup_g \mathrm{Var}\, g(X_1)$ (Bousquet 2002, Theorem 2.3). The proxy $v$ is small when the functions have small variance. Bousquet proves it with the entropy method (Bousquet 2002, Section 3). It is a different theorem from the convex-distance inequality on this page, and it still needs a bound on $\mathbb{E}Z$ from empirical processes and chaining.

Common Confusions

Watch Out

Talagrand's name is on at least four different results

• The convex-distance inequality on this page (Talagrand 1995, Theorem 4.1.1): concentration of product measures, stated for sets, centered at a median in its functional forms.
• The concentration inequality for suprema of empirical processes (Talagrand 1996): in the form of Bousquet (2002, Theorem 2.3), a Bennett-type tail for $\sup_g \sum_i g(X_i)$ above its mean, with a variance term.
• The Ledoux-Talagrand contraction principle (contraction inequality): a comparison of expected Rademacher suprema under Lipschitz maps, with no tail bound in it.
• Generic chaining and majorizing measures (empirical processes and chaining): bounds on the expected supremum of a process through the $\gamma_2$ functional.

Quoting one result with the hypotheses of another produces wrong constants and wrong conditions. The empirical-process inequality needs a supremum of sums and gives a mean-centered Bernstein or Bennett type tail. The convex-distance inequality needs convexity or certificates and gives a median-centered Gaussian tail.

Watch Out

DKW is not a Talagrand inequality

The Dvoretzky-Kiefer-Wolfowitz inequality concerns one empirical process, the empirical CDF on the real line. Massart (1990) proved $\mathbb{P}(\sqrt n \sup_x \lvert F_n(x) - F(x) \rvert > \lambda) \le 2e^{-2\lambda^2}$ with no restriction on $\lambda$. It bounds the supremum itself, for that single class, with an explicit constant and no variance term. Talagrand's empirical-process inequality covers general classes, in Bousquet's form bounds deviations above $\mathbb{E}Z$, and must be combined with a separate estimate of $\mathbb{E}Z$. The convex-distance inequality is a third statement about product measures that mentions neither.

Watch Out

The convex distance is not the Euclidean distance

$d_T(x, A)$ compares a point with a set using weights chosen for that point. It lies between $H(x, A)/\sqrt n$ and $\sqrt{H(x, A)}$. Euclidean distance enters only through the lemma above, which needs bounded coordinates and passes to the convex hull of $A$. That is why the Euclidean corollary requires $f$ to be convex.

Watch Out

The window is dimension-free but not the true fluctuation scale

The $O(1)$ window for convex 1-Lipschitz functions cannot be improved in general: $f(x) = x_1$ already fluctuates on that scale. For a particular function the true scale can be much smaller. Under additional assumptions the operator norm of a random matrix fluctuates on scale $n^{-1/6}$ (Tao 2010, Notes 3), and $L_N$ fluctuates on scale $N^{1/6}$ (Baik, Deift, and Johansson 1999), while the inequality certifies $O(1)$ and $N^{1/4}$. The bounds are also centered at a median; for convex Lipschitz functions the mean lies within $4\sqrt\pi\,L(b - a)$ of it.

Summary

• $d_T(x, A) = \sup_{\alpha \ge 0,\ \|\alpha\|_2 = 1} \inf_{y \in A} \sum_i \alpha_i \mathbf{1}\{x_i \ne y_i\}$, the distance from the origin to the convex hull of the patterns $U_A(x)$.
• For every product measure, $\mathbb{P}(A)\,\mathbb{E}e^{d_T(X, A)^2/4} \le 1$, hence $\mathbb{P}(A)\,\mathbb{P}(d_T(X, A) \ge t) \le e^{-t^2/4}$.
• The proof inducts on dimension, mixes matching and releasing the new coordinate with weight $\lambda$, applies Hölder, and closes with $\inf_\lambda r^{-\lambda}e^{(1-\lambda)^2/4} \le 2 - r$.
• For convex $L$-Lipschitz $f$ of independent coordinates in $[a, b]$: $\mathbb{P}(\lvert f(X) - M \rvert \ge t) \le 4e^{-t^2/(4L^2(b-a)^2)}$, with no dependence on $n$.
• Certificates give the same template for combinatorial functions: $L_N$ has a window of order $N^{1/4}$.
• It is not the empirical-process inequality, not DKW, not the contraction principle, and not generic chaining.

Exercises

ExerciseCore

Problem

Show that $H(x, A)/\sqrt n \le d_T(x, A) \le \sqrt{H(x, A)}$ for every nonempty $A$, where $H(x, A)$ is the Hamming distance from $x$ to $A$. Then show that the upper bound is attained when $A$ is a single point, and the lower bound is attained when $A$ is the set of points that differ from $x$ in at least $k \ge 1$ coordinates (assume every $\Omega_i$ has at least two points).

Hint

Reveal Solution

ExerciseCore

Problem

Redo the eigenvalue example when the independent entries $W_{ij}$, $i \le j$, take values in $[0, 1]$ instead of $[-1, 1]$. What tail bound do you get for $\lambda_{\max}(W)$ around its median, and what does it say about the adjacency matrix of the random graph $G(n, p)$?

Hint

Reveal Solution

ExerciseAdvanced

Problem

Let $n \ge 8$, let $X$ be uniform on $\{0, 1\}^n$, let $m = \lfloor n/2 - \sqrt n \rfloor$, and let $A = \{y \in \{0,1\}^n : \sum_i y_i \le m\}$. Define $g(x) = \operatorname{dist}_2(x, A)$ for $x \in \mathbb{R}^n$. Show that $g$ is 1-Lipschitz but not convex, compute $g$ on $\{0, 1\}^n$, and show that $g(X)$ has fluctuations of order $n^{1/4}$. Why does this not contradict Talagrand's inequality?

Hint

Reveal Solution

ExerciseAdvanced

Problem

Let $X$ be uniform on $\{-1, 1\}^n$ and let $V \subseteq \mathbb{R}^n$ be a subspace of dimension $d$. Show that $\mathbb{P}(\lvert \operatorname{dist}(X, V) - M \rvert \ge t) \le 4e^{-t^2/16}$ for a median $M$ of $\operatorname{dist}(X, V)$, and then show that $\lvert M - \sqrt{n - d} \rvert \le 8$.

Hint

Reveal Solution

ExerciseAdvanced

Problem

Let $X \in \mathbb{R}^{n \times d}$ have rows $x_1, \ldots, x_n$, and let $Z(\varepsilon) = \sup_{\|w\|_2 \le 1} \sum_i \varepsilon_i \langle w, x_i \rangle$ with independent Rademacher signs. Compute the scale in the Talagrand bound and the scale in the McDiarmid bound for $Z$. Evaluate both when (i) $n = d$ and $X$ has orthonormal rows, and (ii) every row equals the same unit vector $u$.

Hint

Reveal Solution

References

Canonical:

• Talagrand, M. (1995). "Concentration of measure and isoperimetric inequalities in product spaces." Publications Mathématiques de l'IHÉS 81, 73-205. Section 4.1 (Theorem 4.1.1, Lemmas 4.1.2 and 4.1.3), Section 6 (bin packing), Section 7.1 (Lemma 7.1.1, Theorems 7.1.2 and 7.1.3). doi:10.1007/BF02699376, preprint arXiv:math/9406212.
• Ledoux, M. (2001). The Concentration of Measure Phenomenon. Mathematical Surveys and Monographs 89, American Mathematical Society. Chapter 4 (concentration in product spaces: martingale methods, convex hull approximation, control by several points).
• Boucheron, S., Lugosi, G., and Massart, P. (2013). Concentration Inequalities: A Nonasymptotic Theory of Independence. Oxford University Press. Section 6.1 (bounded differences), Section 6.6 (convex Lipschitz functions), Sections 7.4 and 7.5 (convex distance inequality, convex Lipschitz functions revisited), Section 8.4 (convex distance inequality by transportation).

Lecture notes and expositions:

• Tao, T. (2009). "Talagrand's concentration inequality." What's new blog, 9 June 2009. Propositions 1 to 4 and Remark 2. https://terrytao.wordpress.com/2009/06/09/talagrands-concentration-inequality/
• Tao, T. (2010). "254A, Notes 1: Concentration of measure." What's new blog, 3 January 2010. Theorem 9, Lemmas 10 and 11. https://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/
• Tao, T. (2010). "254A, Notes 3: The operator norm of a random matrix." What's new blog, 9 January 2010. Proposition 14 and Remark 16. https://terrytao.wordpress.com/2010/01/09/254a-notes-3-the-operator-norm-of-a-random-matrix/
• van Handel, R. (2016). Probability in High Dimension. Princeton APC 550 lecture notes. Theorem 3.25 (Gaussian concentration), Section 4.3 (Theorem 4.20, Corollary 4.23). https://web.math.princeton.edu/~rvan/APC550.pdf

Applications and neighboring results:

• Alon, N., Krivelevich, M., and Vu, V. H. (2002). "On the concentration of eigenvalues of random symmetric matrices." Israel Journal of Mathematics 131, 259-267. Theorem 1. doi:10.1007/BF02785860
• Baik, J., Deift, P., and Johansson, K. (1999). "On the distribution of the length of the longest increasing subsequence of random permutations." Journal of the American Mathematical Society 12(4), 1119-1178. arXiv:math/9810105
• Talagrand, M. (1996). "New concentration inequalities in product spaces." Inventiones Mathematicae 126, 505-563. doi:10.1007/s002220050108
• Bousquet, O. (2002). "A Bennett concentration inequality and its application to suprema of empirical processes." Comptes Rendus Mathématique 334(6), 495-500. Theorem 2.3. doi:10.1016/S1631-073X(02)02292-6
• Massart, P. (1990). "The tight constant in the Dvoretzky-Kiefer-Wolfowitz inequality." Annals of Probability 18(3), 1269-1283. doi:10.1214/aop/1176990746

Next Topics

• Matrix concentration: bounds on the expected operator norm, the location that Talagrand's inequality does not supply
• Random matrix theory overview: spectra beyond the top eigenvalue and the Tracy-Widom scale
• Empirical processes and chaining: expected suprema, the input that Talagrand's empirical-process inequality needs
• Rademacher complexity: the complexity measure behind the Rademacher-sum example
• Contraction inequality: the Ledoux-Talagrand comparison principle, a different result