次高斯的一般 Hoeffding 不等式（general Hoeffding inequality）
/ HUF-ding /
一般 Hoeffding 不等式把經典的有界變數 Hoeffding 界（第一冊）提升到整個次高斯類。初階課程中 Hoeffding 不等式說：各自限定在區間 [a_i, b_i] 的獨立變數之和，偏離其均值達 t 的機率至多為 exp(-2t^2 / sum (b_i - a_i)^2)。一般版以「次高斯」取代「有界」，這是恰當的廣度層次，因為證明除了用以產生變異數代理外，從未真正用到有界性。
陳述如下：若 X_1、…、X_n 獨立、置中、且為次高斯，變異數代理為 sigma_1^2、…、sigma_n^2（等價地 psi_2 範數 K_i），則對每個 t > 0，P(sum_i X_i >= t) <= exp(-t^2 / (2 sum_i sigma_i^2))，雙邊版本帶因子 2。證明與第一冊相同的三步，但讓類別來承擔工作：Chernoff（對指數套用 Markov，P(sum >= t) <= e^(-lambda t) E[exp(lambda sum)]）；獨立性（動差母函數因式分解，E[exp(lambda sum)] = product E[exp(lambda X_i)]）；次高斯定義（每個因子 <= exp(sigma_i^2 lambda^2 / 2)，故乘積 <= exp(lambda^2 sum sigma_i^2 / 2)）；然後對 lambda 最佳化，取 lambda = t / sum sigma_i^2。以奧利奇範數形式有一個等價陳述，對加權和 P(|sum a_i X_i| >= t) <= 2 exp(-c t^2 / (||X||_psi2^2 sum a_i^2))，這正是隨機投影與高維論證所用的形式。
這一個界是機器學習理論中幾乎每個集中估計的基礎：它給出經驗平均的偏差、蒙地卡羅的準確度、Rademacher 隨機投影的誤差，以及對有限多個事件取聯集界的基石。它的限制、也是 Bernstein 與 Bennett 存在的原因，在於它只依賴變異數「代理」而非真變異數。當變數有界但變異數小時，代理 (b-a)^2/4 過於悲觀，Hoeffding 留下了高斯與卜瓦松之間的差距未利用；對於這種小變異數、大值域的區段，必須使用變異數感知的不等式。
從 n 個獨立同分布樣本估計一個代理為 sigma^2 的次高斯變數之均值 mu。由於 X_i - mu 的代理為 sigma^2，和 (1/n) sum (X_i - mu) 的代理為 sigma^2/n，故 P(|經驗均值 - mu| >= t) <= 2 exp(-n t^2 / (2 sigma^2))。要以信心 1 - delta 得到誤差 t，需要 n >= 2 sigma^2 log(2/delta) / t^2 個樣本。
樣本數約以 sigma^2 log(1/delta) / t^2 縮放——這是基本的學習理論速率。
Hoeffding 忽略真變異數而只用代理，故對於變異數小的有界變數，它鬆了一個高斯／Bernstein 因子。它也需要獨立性；對於相依的和，改用 Azuma／McDiarmid。