Rademacher 複雜度

取你的函數類別與一組固定樣本，對每個樣本擲一枚公正硬幣，產生隨機的正負一雜訊標記。問：平均而言（對硬幣結果取期望），這個類別能與純雜訊相關到什麼程度？一個靈活到能追逐任意隨機模式的類別有高 Rademacher 複雜度；僵硬的類別做不到，故複雜度低。它本質上度量一個類別能多大程度地去擬合無意義的東西，而且是在你手上的真實資料上計算。

一個類別在某樣本上的經驗 Rademacher 複雜度，是對類別中的函數取上確界、再對 sigma_i 乘以 f(x_i) 的平均取期望，其中 sigma_i 是獨立均勻的正負一 Rademacher 變數。對稱化論證顯示，經驗風險與真實風險之間的期望一致落差，被這個量的兩倍所界定，泛化落差因此直接得出。與 VC 維度不同，它是實數值、對尺度敏感、且與資料相依：它看得見輸入分布與類別的幾何，對核方法、間隔、以及範數受限的網路給出更緊的界。

因為它與資料相依、又能乾淨地組合——Lipschitz 損失的收縮性、可加性、以及透過覆蓋數的上界——Rademacher 複雜度成為證明深度與核學習泛化的現代主力工具。它的侷限是：基本的全域版本仍隨整個類別的最壞情況波動而縮放，而局部化（把注意力限制在低風險函數上）後來把它銳化為快速收斂率。