Talagrand's concentration inequality
/ tah-lah-GRAHN /
Talagrand's concentration inequality is the deep result that concentration of measure on a product space depends not on ordinary Euclidean or Hamming distance, but on a cleverer, geometry-aware notion of distance to a set — and that this refined distance often gives dimension-free, variance-aware bounds where McDiarmid's bounded-differences argument is loose. It was a turning point in the subject: where the martingale method gives concentration set by worst-case sensitivities, Talagrand's inequalities frequently yield the much sharper concentration one would naively expect only for sums.
The setting is a product probability space Omega = Omega_1 x ... x Omega_n with a product measure P (independent coordinates), and a subset A. Talagrand defines a family of distances from a point x to A. The most important is the convex distance d_T(x, A), defined by viewing the discrepancy between x and a point y in A coordinate-wise (the set of coordinates where they differ) and taking a worst-case-over-weights, best-case-over-A optimization: d_T(x, A) = sup over unit vectors alpha >= 0 of inf over y in A of sum_i alpha_i 1[x_i != y_i]. The headline convex-distance inequality then says P(A) * E[exp(d_T(X, A)^2 / 4)] <= 1, which forces: if P(A) is not tiny, then most of the mass lies within convex distance O(1) of A. The general Talagrand inequality is broader still — it controls a whole hierarchy of distances (including a one-with-cost penalty and the abstract 'convex hull distance'), all proved by an induction on the number of coordinates that is the technical heart of the theory.
Why it matters: applied to a function f that is 1-Lipschitz with respect to the convex distance, the inequality gives concentration around a MEDIAN with a rate that scales with the function's true variability, not its worst-case bounded differences. The canonical triumphs are dimension-free: the concentration of a convex Lipschitz function of independent bounded variables (matching the Gaussian-style rate without any Gaussian assumption), the length of the longest increasing subsequence, bin-packing, and the operator norm of a random matrix. The honest caveat: extracting a usable bound requires checking the right Lipschitz/convexity condition for the convex distance, which is more delicate than McDiarmid's mechanical bounded-differences check; the power comes precisely from that extra structural input, and for functions that are merely bounded-differences without convexity, Talagrand need not beat McDiarmid.
Let f(x) be a 1-Lipschitz convex function of n independent variables in [0,1]^n (for instance, the operator norm of a matrix whose entries are the coordinates). Talagrand's convex-distance inequality yields P(|f - M(f)| >= t) <= 4 exp(-t^2 / 4), where M(f) is a median — a clean, dimension-free Gaussian-type tail with NO dependence on n, which the bounded-differences bound (rate exp(-t^2 / 2n)) cannot match.
For convex Lipschitz functions Talagrand gives dimension-free concentration.
Talagrand concentrates around a MEDIAN (or, via Lipschitz comparison, the mean); it requires convexity/Lipschitz structure with respect to the convex distance, which is a genuine hypothesis. Without convexity it may give no improvement over McDiarmid.