機率引擎：集中與穩定性

超越 Hoeffding：一個工具箱

至此每一個界都仰賴 Hoeffding 不等式——有界獨立變數之和會以類高斯尾部集中於其期望附近。研究級的工作需要更豐富的工具，因為 Hoeffding 很浪費：它只知道每個變數的範圍，卻從不知道其變異數。當損失通常極小卻偶爾很大時，忽略變異數會丟掉大部分訊號，而所得的集中界，恰好在快速速率分析中最關鍵的那個因子上是鬆的。

Hoeffding——有界變數；尾部只用到範圍。粗鈍的預設。
Bernstein——加入變異數項；當損失通常很小時格外銳利。
McDiarmid（有界差分）——適用於任何「換掉一個點時變化甚微」的樣本函數。
Talagrand——經驗過程上確界的集中；局部化背後的引擎。

McDiarmid：不需要是「和」的集中

我們真正在意的量——整個假設類上的最壞情況落差——並不是一個簡單的和，因此 Hoeffding 無法直接套用。McDiarmid 的有界差分不等式拯救了我們：若更換 m 個樣本中的任何單一個，都讓你的函數值至多移動 c，則該函數會以 exp(−2ε²/(m·c²)) 的尾部集中於其期望附近。經驗過程的上確界恰好滿足這個有界差分性質——換一個樣本至多讓上確界移動 O(1/m)——所以即使它高度非線性，仍然會集中。

P\big(f(X_1,\dots,X_n)-\mathbb{E}f\ge t\big)\le\exp\!\left(-\frac{2t^2}{\sum_{i=1}^{n}c_i^2}\right)

麦克迪尔米德有界差分不等式：若任一坐标对 f 的改变都不超过 c_i，则 f 高度集中——无需写成求和形式。

這是標準 Rademacher 證明中承重的一步：McDiarmid 把最壞情況落差集中於其期望附近，一個對稱化（symmetrization）論證把該期望改寫成 Rademacher 複雜度，第 2 篇的一致收斂界便應運而出。你日後讀到的幾乎每個泛化定理，McDiarmid 都藏在這個確切的位置。

穩定性：通往泛化的第二條路

一致收斂談的是整個類別，但 ERM 永遠只輸出一個假設。演算法穩定性（algorithmic stability）走的是一條全然不同的路：它直接研究演算法。若移除或替換單一訓練樣本幾乎不改變演算法回傳的假設——形式上，當你擾動 m 個訓練樣本之一時，任一點上的損失至多改變 β——則稱該演算法是穩定的。穩定性完全不提假設類或其容量；它是學習程序本身的性質。

主定理乾淨俐落：若演算法具有一致穩定度 β，其期望泛化落差至多為 β，而一個 McDiarmid 論證可把它升級為高機率界。於是「能泛化若且唯若穩定」——容量從不登場。這解釋了一致收斂無法解釋的學習器：在一個龐大假設類中，穩定的演算法仍能泛化，因為演算法只探索了該類別中一塊良性的薄片。

\mathbb{E}_{S}\big[R(A_S)-\hat{R}_S(A_S)\big]\le\beta

稳定性主定理：具有一致稳定性 β 的算法，其期望泛化间隙至多为 β。

為何你的正則化項其實是穩定器

穩定性並不神祕；它正是正則化買來的東西。強凸性是橋樑：加入 L2 懲罰使訓練目標成為 λ-強凸，而強凸目標的最小值點在更換一個樣本時至多移動 O(1/(λm))。於是脊正則化（ridge）賦予約 1/(λm) 階的一致穩定度——調大 λ，你便以少許擬合換取大量穩定性，而定理會把它直接轉換成泛化保證。

\beta\le\frac{\rho^2}{\lambda n}

正则化为何带来稳定性：L2 惩罚带来的 λ-强凸性，将正则化 ERM 的一致稳定性界定在 ρ²/(λn) 以内。

同一個視角也照亮了隨機梯度下降（SGD）：以適中的學習率跑夠少的步數，SGD 本身就是演算法穩定的，因為每次更新都只輕柔地觸碰迭代點，任一樣本的影響都保持有界。穩定性因而把最佳化的動力學與泛化繫在一起，全程不需計算任何容量——這條線索，下一篇以及整個 Vol II 關於良性過擬合（benign overfitting）的故事都會接續下去。