塔拉格朗集中不等式（Talagrand's concentration inequality）
/ tah-lah-GRAHN /
塔拉格朗集中不等式是一個深刻結果：乘積空間上的測度集中並不依賴普通的歐氏或漢明距離，而是依賴一個更巧妙、具幾何意識的「到集合的距離」概念——且這個精煉距離往往給出無維度、變異數感知的界，而 McDiarmid 的有界差分論證在此處是鬆的。它是這門學問的轉捩點：鞅方法給出由最壞情形敏感度設定的集中，而塔拉格朗不等式常常產生人們天真以為只有對和才能期望的、更為尖銳的集中。
場景是乘積機率空間 Omega = Omega_1 x ... x Omega_n 配上乘積測度 P（座標獨立），以及子集 A。塔拉格朗定義了一族從點 x 到 A 的距離。最重要者是凸距離 d_T(x, A)，其定義是逐座標地看 x 與 A 中某點 y 的差異（它們不同的座標集合），並做「對權重取最壞、對 A 取最好」的最佳化：d_T(x, A) = sup（在單位向量 alpha >= 0 上）inf（在 y in A 上）sum_i alpha_i 1[x_i != y_i]。招牌的凸距離不等式遂說 P(A) * E[exp(d_T(X, A)^2 / 4)] <= 1，這迫使：若 P(A) 不微小，則大部分質量落在到 A 的凸距離 O(1) 之內。一般的塔拉格朗不等式更為廣泛——它控制一整族距離（包括帶成本懲罰者與抽象的「凸包距離」），全部由對座標數的歸納法證明，那正是此理論的技術核心。
為何重要：套用於對凸距離為 1-Lipschitz 的函數 f，不等式給出圍繞「中位數」的集中，其速率隨函數的真實變異性而非最壞情形有界差分縮放。標誌性的勝利都是無維度的：獨立有界變數之凸 Lipschitz 函數的集中（不需任何高斯假設即匹配高斯型速率）、最長遞增子序列的長度、裝箱問題，以及隨機矩陣的算子範數。誠實的提醒：要萃取可用的界，須對凸距離檢驗正確的 Lipschitz／凸性條件，這比 McDiarmid 機械式的有界差分檢驗更為微妙；威力正來自那額外的結構輸入，而對於僅有有界差分而無凸性的函數，塔拉格朗不一定勝過 McDiarmid。
設 f(x) 為 [0,1]^n 中 n 個獨立變數的 1-Lipschitz 凸函數（例如，以這些座標為元素的矩陣之算子範數）。塔拉格朗凸距離不等式給出 P(|f - M(f)| >= t) <= 4 exp(-t^2 / 4)，其中 M(f) 為中位數——一個乾淨、無維度、對 n 無依賴的高斯型尾，這是有界差分界（速率 exp(-t^2 / 2n)）無法匹敵的。
對於凸 Lipschitz 函數，塔拉格朗給出無維度的集中。
塔拉格朗圍繞「中位數」集中（或經由 Lipschitz 比較圍繞均值）；它需要對凸距離的凸性／Lipschitz 結構，這是個實質假設。無凸性時它可能相對 McDiarmid 毫無改進。