the convex-distance inequality
The convex-distance inequality is the most-used concrete form of Talagrand's concentration theory, and the one that most directly beats the bounded-differences method when a function can occasionally be very sensitive but usually is not. Its innovation is to measure distance to a set with a weight vector that you get to optimize against, so that a point is 'far' from a set A only if it differs from every member of A on a heavily-weighted, hence important, collection of coordinates.
Define, for a point x and a target set A in a product space, the convex distance d_T(x, A) = sup over alpha with |alpha| = 1, alpha_i >= 0 of inf over y in A of sum_i alpha_i 1[x_i != y_i]. The inner inf finds the nearest member of A in the alpha-weighted Hamming sense; the outer sup chooses the weighting that makes x look as far from A as possible. The name 'convex' is because this distance equals the Euclidean distance from the indicator-of-disagreement vector to the convex hull of the disagreement vectors achievable using points of A. The inequality states: for any product measure P and any set A, P(A) * E[exp(d_T(X, A)^2 / 4)] <= 1. Equivalently, P(d_T(X, A) >= t) <= (1 / P(A)) exp(-t^2 / 4). Read this as a concentration statement: as long as A captures a fixed fraction of the mass, the convex distance from a random point to A has a Gaussian tail with NO dependence on the dimension n.
The payoff is variance-aware concentration of functions. If f satisfies f(x) <= f(y) + sum_i c_i(x) 1[x_i != y_i] for some weights c_i(x) with sum c_i(x)^2 <= V (a 'self-bounding' or weighted-Lipschitz condition), then f concentrates with rate governed by V rather than the worst-case sum of squared differences. This is exactly why the convex-distance inequality gives the right answer for problems where one coordinate can be pivotal in rare configurations — longest increasing subsequence, traveling-salesman tour length on random points, bin packing — and matches Gaussian concentration for convex Lipschitz functions. Honest caveat: the bound is stated around a median, and converting to the mean costs a constant; also one must genuinely verify the weighted-Lipschitz condition with coordinate-dependent weights c_i(x), which is more work than McDiarmid but is precisely where the extra sharpness is earned.
Let L be the length of the longest increasing subsequence of a random permutation of {1, ..., n} (or of n iid uniform points). One can show L is weighted-Lipschitz with sum c_i^2 ~ E[L] ~ 2 sqrt(n), so the convex-distance inequality gives P(|L - M| >= t) <= 4 exp(-t^2 / (16 sqrt(n))) — concentration on the scale n^(1/4), far sharper than the McDiarmid scale sqrt(n) one would get from worst-case differences.
The convex distance captures that a coordinate is pivotal only rarely.
The convex distance equals the Euclidean distance to a convex hull, which is what lets a few heavily-weighted disagreements, not the raw Hamming count, drive the bound. You must verify the weighted-Lipschitz condition with the optimal coordinate weights, or the variance-like quantity V is wrong.