有界差分（McDiarmid）不等式
/ mək-DAR-mid /
我們在意的往往不是一個簡單的總和，而是許多獨立輸入的複雜函數——一個訓練好的模型的錯誤率、一個隨機網路中最大的群集、兩個隨機字串最長共同子序列的長度。這樣一個糾纏的量，仍可能緊緊集中在它的平均附近嗎？McDiarmid 不等式說可以，只要沒有任何單一輸入能把輸出改變太多。
設定：令 f(X_1, ..., X_n) 為獨立輸入的任意函數，並假設它具有有界差分性質——只改變第 i 個輸入、其餘全部固定，能讓輸出移動至多 c_i。則 f 的集中方式恰如一個霍夫丁總和：P(f - E[f] >= t) <= exp( -2 t^2 / 對 c_i^2 求和 )，下尾也有相同的界。這個函數可以極度非線性、以任何方式糾纏輸入；只有每個輸入的敏感度 c_i 要緊。其證明建構一個杜布鞅——把輸入一個一個揭露、追蹤 f 的條件期望——然後對它套用阿祖瑪-霍夫丁不等式。
這是複雜統計量現代集中分析的引擎，也是統計學習理論的支柱：它顯示，當沒有任何單一資料點佔主導時，經驗風險、Rademacher 複雜度或核統計量都會貼近它的均值。整個分析的重擔，化約成一個檢查——界定一個輸入能把輸出擺動多少。誠實的提醒：McDiarmid 的好壞完全取決於你的界 c_i。若連一個輸入都能大幅改變 f（某個 c_i 很大），這個界就變得沒用，而由單一座標主導的函數（如一個可能大幅跳動的最大值）正是它幫不上忙的情形。
令 f 為一個用 n 個獨立樣本訓練出的模型所誤分類點的比例。替換一個訓練樣本，至多把這個比例改變 c = 1/n。McDiarmid 於是給出 P(|f - E[f]| >= t) <= 2 exp(-2 t^2 / (n (1/n)^2)) = 2 exp(-2 n t^2)：測試誤差集中在它的均值附近。
獨立輸入的任何函數，只要沒有單一輸入能大幅擺動它，就會集中。
McDiarmid 的強度完全由差分界 c_i 決定。只要有一個座標的 c_i 很大（單一輸入就能大幅擺動的函數），這個界就變得沒用。