演算法穩定性

對一個學習演算法問：若我替換掉一個訓練樣本，訓練出的模型會變很多嗎？若輸出在任一單點被替換時幾乎不動，這個演算法就是穩定的，而光是穩定性就足以保證泛化——完全不需數假設或度量類別容量。直覺上，若模型不依附於任何單一訓練點，它就沒有死記那些點，因此其訓練誤差能忠實反映真實誤差。

最乾淨的版本「一致穩定性」說：替換 m 個訓練點之一，對任一固定測試點的損失至多改變 beta。一條基礎定理便把期望泛化落差以 beta 界定，而高機率版本經精煉後給出約 beta 乘以 m 的平方根之控制。關鍵在於：此分析針對演算法的特定輸出，而非類別上的上確界，故能在一致收斂變得空泛之處仍然奏效。正則化（如脊迴歸）與隨機梯度下降的步長排程，都能買到穩定性。

穩定性是解釋「強凸、正則化目標為何泛化」的理論支柱；一個著名結果以「你訓練多久、步長多大」來界定隨機梯度下降自身的穩定性——這給了早停為何有幫助的一個學習論理由。它也連到差分隱私，後者是穩定性的一種強形式。侷限是：對非凸深度學習建立緊的穩定性常數仍然困難。