有界差分（McDiarmid）不等式（bounded-differences inequality）
/ mick-DAR-mid /
McDiarmid 不等式是從「和」的集中躍升到獨立變數之「任意函數」的集中。統計與學習中的許多量根本不是和——最大值、中位數、訓練模型的經驗風險、最大特徵值、最長遞增子序列的長度——然而它們圍繞其均值尖銳集中，理由與和相同：沒有任何單一座標太過重要。McDiarmid 不等式透過「有界差分」條件把這個直覺精確化。
陳述如下：設 X_1、…、X_n 獨立（各取值於某空間，不必為實數），且函數 f 滿足帶常數 c_1、…、c_n 的有界差分條件：單獨改變第 i 個引數而固定其餘者，至多使 f 改變 c_i。即對 x 與 x_i' 取上確界，|f(x_1,...,x_i,...,x_n) - f(x_1,...,x_i',...,x_n)| <= c_i。則對每個 t > 0，P(f - E[f] >= t) <= exp(-2 t^2 / sum_i c_i^2)，雙邊版本使界加倍。注意右側只依賴有界差分常數，恰如 Hoeffding 只依賴值域——McDiarmid 是函數版的 Hoeffding，當 f 為和時特化為 Hoeffding（此時 c_i = b_i - a_i）。其背後機制是鞅（Azuma）方法：把 f - E[f] 寫成鞅差 D_i = E[f | X_1..X_i] - E[f | X_1..X_{i-1}] 的伸縮和，每個 D_i 的值域受 c_i 界定，再對該鞅套用 Azuma-Hoeffding。
McDiarmid 是統計學習理論中最常用的單一集中工具，因為經驗過程的上確界（它支配泛化誤差）在每個樣本上通常具有有界差分 c_i ~ 1/n，給出 exp(-t^2 n / 2) 量級的指數集中。然而它誠實的限制是：它完全不顧變異數；如同 Hoeffding，其速率由「最壞情形」差分之和 sum c_i^2 設定，即便 f 通常遠不那麼敏感。當某個座標偶爾能造成大改變但很少如此時，有界差分界就鬆，須用 Talagrand 的凸距離不等式或熵方法（它們使用「自界」或類變異數的量）來捕捉真正較小的波動。
設 f 為固定預測器 h 的經驗風險 (1/n) sum loss(h, Z_i)，損失值落在 [0,1]，對獨立樣本 Z_i 取之。改變一個 Z_i 至多使 f 改變 1/n，故 c_i = 1/n，McDiarmid 給出 P(|經驗風險 - 真風險| >= t) <= 2 exp(-2 n t^2)——單一假設的基本泛化界，尚未動用聯集界或 VC 論證。
有界差分把任何對資料穩定的函數變成集中的函數。
McDiarmid 的速率用最壞情形差分 c_i 而非 f 的變異數，故當 f 通常不敏感卻偶爾擺動時就鬆。它也需要 X_i 的獨立性；單有有界差分而無獨立性並不足夠。