凸距離不等式（convex-distance inequality）
凸距離不等式是塔拉格朗集中理論最常用的具體形式，也是當一個函數偶爾可能極度敏感卻通常不然時，最直接勝過有界差分方法的那一個。它的創新在於用一個你可以拿來對抗最佳化的權重向量來度量到集合的距離，使得一個點只有在它與 A 的每個成員都在一個被重權、因而重要的座標集合上不同時，才算「遠離」A。
對於乘積空間中的點 x 與目標集 A，定義凸距離 d_T(x, A) = sup（在 |alpha| = 1, alpha_i >= 0 上）inf（在 y in A 上）sum_i alpha_i 1[x_i != y_i]。內層 inf 在 alpha 加權漢明意義下找出 A 中最近的成員；外層 sup 選取使 x 看起來離 A 盡可能遠的權重。「凸」之名是因為此距離等於「不一致指示向量」到「使用 A 中各點可達的不一致向量之凸包」的歐氏距離。不等式陳述：對任何乘積測度 P 與任何集合 A，P(A) * E[exp(d_T(X, A)^2 / 4)] <= 1。等價地，P(d_T(X, A) >= t) <= (1 / P(A)) exp(-t^2 / 4)。把它讀作集中陳述：只要 A 捕捉了固定比例的質量，從隨機點到 A 的凸距離就有一個對維度 n「無依賴」的高斯尾。
回報是函數的變異數感知集中。若 f 滿足 f(x) <= f(y) + sum_i c_i(x) 1[x_i != y_i]，其中某組權重 c_i(x) 滿足 sum c_i(x)^2 <= V（「自界」或加權 Lipschitz 條件），則 f 以由 V 而非最壞情形平方差之和支配的速率集中。這正是凸距離不等式對於「某座標在罕見組態下可成關鍵」的問題給出正確答案的原因——最長遞增子序列、隨機點上的旅行推銷員巡迴長度、裝箱問題——並對凸 Lipschitz 函數匹配高斯集中。誠實的提醒：界是圍繞中位數陳述的，轉換到均值花費一個常數；且必須以座標相關的權重 c_i(x) 真正驗證加權 Lipschitz 條件，這比 McDiarmid 費功，但正是額外尖銳性所賺得之處。
設 L 為 {1, ..., n} 之隨機排列（或 n 個獨立同分布均勻點）之最長遞增子序列的長度。可證 L 為加權 Lipschitz 且 sum c_i^2 ~ E[L] ~ 2 sqrt(n)，故凸距離不等式給出 P(|L - M| >= t) <= 4 exp(-t^2 / (16 sqrt(n)))——在 n^(1/4) 尺度上的集中，遠比由最壞情形差分所得的 McDiarmid 尺度 sqrt(n) 尖銳。
凸距離捕捉了某座標只在罕見情形下才是關鍵的事實。
凸距離等於到一個凸包的歐氏距離，這正是讓少數被重權的不一致、而非原始漢明計數，來驅動界的原因。你必須以最佳座標權重驗證加權 Lipschitz 條件，否則類變異數的量 V 就錯了。