動機
期望保證描述重複抽樣的平均情況,但我們通常只觀察一份訓練樣本,然後便要使用所得預測器。若要為這次程序附上概率保證,單有對稱化仍不足夠:一致偏差可能高於其期望,而樣本上算出的複雜度又可能低於其期望。以觀察複雜度作右邊的界,必須同時處理這兩種波動。
另一個困難來自損失變換。我們往往容易估計預測函數類的幾何性質,真正需要的卻是經過非線性損失後的函數類。還有,單一粗網格可能浪費資訊;逐層修正的鏈可以分別計算各尺度的細小變化,避免每個區分都按最大距離付費。
以下始終使用帶絕對值的 Rademacher 上確界。把另一種單邊定義的常數直接搬來,可能產生錯誤結論。我們把集中、損失壓縮及多尺度近似的常數逐步寫出,建立可用的高概率保證,而不聲稱常數最佳,也不把發散的熵和當作有用的有限界。
定義
設 S = ( Z 1 , … , Z n ) S=(Z_1,\ldots,Z_n) S = ( Z 1 , … , Z n ) 獨立同分佈,分佈為 P P P ;G \mathcal G G 是預先固定、值域在 [ 0 , 1 ] [0,1] [ 0 , 1 ] 的可測函數類。假設所用上確界可測,例如有限類或適當可分的類。記
D ( S ) = sup g ∈ G ∣ P g − P n g ∣ , r ( S ) = E σ sup g ∈ G ∣ 1 n ∑ i σ i g ( Z i ) ∣ . D(S)=\sup_{g\in\mathcal G}|Pg-P_ng|,
\qquad r(S)=\mathbb E_\sigma\sup_{g\in\mathcal G}
\left|\frac1n\sum_i\sigma_i g(Z_i)\right|. D ( S ) = g ∈ G sup ∣ P g − P n g ∣ , r ( S ) = E σ g ∈ G sup n 1 i ∑ σ i g ( Z i ) .
符號與樣本獨立。前面的泛化筆記已用幽靈樣本及成對交換證明 E D ≤ 2 E r \mathbb ED\le2\mathbb Er E D ≤ 2 E r ;本節進一步控制兩者相對於期望的波動。
若只改變第 i i i 個獨立觀察,函數 F F F 的值至多改變 c i c_i c i ,便稱它有座標敏感度 c i c_i c i 。固定樣本後,評估向量的距離用 d ( v , w ) = ∥ v − w ∥ 2 / n d(v,w)=\|v-w\|_2/\sqrt n d ( v , w ) = ∥ v − w ∥ 2 / n 。有限 ϵ \epsilon ϵ -網讓每個向量與某中心的距離不超過 ϵ \epsilon ϵ 。以下覆蓋數均依此樣本距離,並非總體範數。
壓縮所用的 ϕ i \phi_i ϕ i 可隨位置不同,但固定樣本後亦須固定,在有關預測範圍及零點上為 A A A -Lipschitz,且 ϕ i ( 0 ) = 0 \phi_i(0)=0 ϕ i ( 0 ) = 0 。零點條件控制絕對值約定中的偏移。平方損失只在有界預測及標籤範圍上具有所需 Lipschitz 性質,並非全域如此。
定理/命題
若各座標獨立且敏感度為 c i c_i c i ,則
P { F − E F ≥ t } ≤ exp ( − 2 t 2 ∑ i c i 2 ) , t > 0. \mathbb P\{F-\mathbb EF\ge t\}\le
\exp\left(-\frac{2t^2}{\sum_i c_i^2}\right),\qquad t>0. P { F − E F ≥ t } ≤ exp ( − ∑ i c i 2 2 t 2 ) , t > 0. 對 E F − F \mathbb EF-F E F − F 亦有同樣估計。因此,對 0 < δ < 1 0<\delta<1 0 < δ < 1 ,以至少 1 − δ 1-\delta 1 − δ 的概率有
D ( S ) ≤ 2 r ( S ) + 3 log ( 2 / δ ) 2 n . D(S)\le2r(S)+3\sqrt{\frac{\log(2/\delta)}{2n}}. D ( S ) ≤ 2 r ( S ) + 3 2 n log ( 2/ δ ) . 對此損失類作 ε o p t \varepsilon_{\rm opt} ε opt -近似 ERM,其超額總體風險不超過右邊的兩倍再加 ε o p t \varepsilon_{\rm opt} ε opt 。
若 T ⊂ R n T\subset\mathbb R^n T ⊂ R n 有界,而各映射滿足上述條件,則
E σ sup v ∈ T ∣ 1 n ∑ i σ i ϕ i ( v i ) ∣ ≤ 2 A E σ sup v ∈ T ∣ 1 n ∑ i σ i v i ∣ . \mathbb E_\sigma\sup_{v\in T}\left|\frac1n\sum_i\sigma_i\phi_i(v_i)\right|
\le2A\,\mathbb E_\sigma\sup_{v\in T}\left|\frac1n\sum_i\sigma_i v_i\right|. E σ v ∈ T sup n 1 i ∑ σ i ϕ i ( v i ) ≤ 2 A E σ v ∈ T sup n 1 i ∑ σ i v i . 建立鏈時,取對稱集合 T ∪ ( − T ) ∪ { 0 } T\cup(-T)\cup\{0\} T ∪ ( − T ) ∪ { 0 } ,滿足 sup v d ( v , 0 ) ≤ R \sup\limits_v d(v,0)\le R v sup d ( v , 0 ) ≤ R 。令 ϵ j = R 2 − j \epsilon_j=R2^{-j} ϵ j = R 2 − j ,選該集合內的有限 ϵ j \epsilon_j ϵ j -網 A j A_j A j ,大小為 N j N_j N j ,並令 A 0 = { 0 } , N 0 = 1 A_0=\{0\},N_0=1 A 0 = { 0 } , N 0 = 1 。每個整數 J ≥ 1 J\ge1 J ≥ 1 均有
r T ≤ ϵ J + ∑ j = 1 J 3 ϵ j 2 log ( 2 N j N j − 1 ) n , r_T\le\epsilon_J+
\sum_{j=1}^J3\epsilon_j
\sqrt{\frac{2\log(2N_jN_{j-1})}{n}}, r T ≤ ϵ J + j = 1 ∑ J 3 ϵ j n 2 log ( 2 N j N j − 1 ) , 其中 r T r_T r T 是原評估集合的絕對 Rademacher 平均。
這些網可依固定樣本而改變。無窮和只有在有限時才給有用的極限界;有限 J J J 的公式則始終成立。若 R = 0 R=0 R = 0 ,全部向量為零,複雜度亦零,無須建立鏈。
證明思路
逐一揭示座標,設 M i = E [ F ∣ Z 1 , … , Z i ] M_i=\mathbb E[F\mid Z_1,\ldots,Z_i] M i = E [ F ∣ Z 1 , … , Z i ] 。固定過去,再積分尚未揭示的未來。由原敏感度對每個未來實現都成立,改變目前座標後,此條件期望至多改變 c i c_i c i 。所以 M i − M i − 1 M_i-M_{i-1} M i − M i − 1 的條件值域寬度至多 c i c_i c i ,條件均值為零。
均值為零、位於寬度 c c c 區間的變量,其矩母函數不超過 e λ 2 c 2 / 8 e^{\lambda^2c^2/8} e λ 2 c 2 /8 。證明是將對數矩母函數微分兩次,得到指數傾斜分佈下的方差。分佈仍在原區間,方差不超過相對於區間中點的平方偏差上界 c 2 / 4 c^2/4 c 2 /4 。零點的值與一階導數消失,積分兩次便得所需估計。條件化後反覆用塔式性質,有
E e λ ( F − E F ) ≤ exp ( λ 2 8 ∑ i c i 2 ) . \mathbb E e^{\lambda(F-\mathbb EF)}
\le\exp\left(\frac{\lambda^2}8\sum_i c_i^2\right). E e λ ( F − E F ) ≤ exp ( 8 λ 2 i ∑ c i 2 ) . 用指數 Markov 不等式,取最佳參數 λ = 4 t / ∑ i c i 2 \lambda=4t/\sum\limits_i c_i^2 λ = 4 t / i ∑ c i 2 ,即得上尾;對 − F -F − F 重做便得下尾。若全部敏感度為零,函數幾乎必然為常數,直接處理即可。
改變一個觀察,各經驗平均至多變 1 / n 1/n 1/ n ,所以 D D D 的敏感度亦為 1 / n 1/n 1/ n 。對固定符號,上確界絕對平均的變化同樣不超過 1 / n 1/n 1/ n ,取符號期望後仍成立,故 r r r 有同一敏感度。令 t = log ( 2 / δ ) / ( 2 n ) t=\sqrt{\log(2/\delta)/(2n)} t = log ( 2/ δ ) / ( 2 n ) ,聯合界給出同時成立的 D ≤ E D + t D\le\mathbb ED+t D ≤ E D + t 與 E r ≤ r + t \mathbb Er\le r+t E r ≤ r + t 。代入對稱化便得 D ≤ 2 r + 3 t D\le2r+3t D ≤ 2 r + 3 t 。ERM 比較先用 R ( h ^ ) ≤ R ^ ( h ^ ) + D R(\widehat h)\le\widehat R(\widehat h)+D R ( h ) ≤ R ( h ) + D ,再在接近總體下確界的成員用反向比較。即使下確界未取到,令比較容許誤差趨零仍可完成證明。
反例模式
有界差分需要獨立的座標 聲稱:只要敏感度小,即使觀察值互相依賴,尾界仍然成立。把一個公平符號 Z Z Z 複製成 Z 1 = ⋯ = Z n = Z Z_1=\cdots=Z_n=Z Z 1 = ⋯ = Z n = Z ,令 F = 1 n ∑ i Z i F=\frac1n\sum\limits_iZ_i F = n 1 i ∑ Z i 。在 { − 1 , 1 } \{-1,1\} { − 1 , 1 } 中改變一個座標,F F F 至多改變 2 / n 2/n 2/ n ,故 ∑ i c i 2 = 4 / n \sum\limits_ic_i^2=4/n i ∑ c i 2 = 4/ n ,而 t = 1 t=1 t = 1 時的界會是 e − n / 2 e^{-n/2} e − n /2 。但 F = Z F=Z F = Z 、E F = 0 \mathbb EF=0 E F = 0 ,且對每個 n ≥ 2 n\ge2 n ≥ 2 都有 P { F ≥ 1 } = 1 / 2 > e − n / 2 \mathbb P\{F\ge1\}=1/2\gt e^{-n/2} P { F ≥ 1 } = 1/2 > e − n /2 。修正就是獨立性:證明對未揭示的座標積分時,所用的分佈不依賴已揭示的座標。
壓縮不等式在凍結其餘符號的情況下逐個座標證明。絕對值留到最後才處理,因子二正是在那裏出現。
先對有限集合 T T T 逐座標證明單邊不等式 E sup v ∈ T ∑ i σ i ϕ i ( v i ) ≤ E sup v ∈ T ∑ i A σ i v i \mathbb E\sup\limits_{v\in T}\sum\limits_i\sigma_i\phi_i(v_i)\le\mathbb E\sup\limits_{v\in T}\sum\limits_iA\sigma_iv_i E v ∈ T sup i ∑ σ i ϕ i ( v i ) ≤ E v ∈ T sup i ∑ A σ i v i 。固定座標 i i i 及其餘全部符號,把它們的貢獻寫成 B v B_v B v 。對目前符號取平均,得到
1 2 sup v [ B v + ϕ i ( v i ) ] + 1 2 sup w [ B w − ϕ i ( w i ) ] = 1 2 sup v , w [ B v + B w + ϕ i ( v i ) − ϕ i ( w i ) ] . \frac12\sup_{v}[B_v+\phi_i(v_i)]+\frac12\sup_{w}[B_w-\phi_i(w_i)]
=\frac12\sup_{v,w}\bigl[B_v+B_w+\phi_i(v_i)-\phi_i(w_i)\bigr]. 2 1 v sup [ B v + ϕ i ( v i )] + 2 1 w sup [ B w − ϕ i ( w i )] = 2 1 v , w sup [ B v + B w + ϕ i ( v i ) − ϕ i ( w i ) ] . Lipschitz 性把最後的差界為 A ∣ v i − w i ∣ A|v_i-w_i| A ∣ v i − w i ∣ 。由於 B v + B w B_v+B_w B v + B w 對 v , w v,w v , w 對稱,帶 A ∣ v i − w i ∣ A|v_i-w_i| A ∣ v i − w i ∣ 的上確界等於帶 A ( v i − w i ) A(v_i-w_i) A ( v i − w i ) 的上確界,而後者正是把 ϕ i ( v i ) \phi_i(v_i) ϕ i ( v i ) 換成 A v i Av_i A v i 後的同一平均。對每個座標重做即可。
處理絕對上確界時,先把零向量加入 T T T 。因 ϕ i ( 0 ) = 0 \phi_i(0)=0 ϕ i ( 0 ) = 0 ,新加入的向量對兩個絕對平均的貢獻都是零,所以兩者都不變。正上確界 sup v ∑ i σ i ϕ i ( v i ) \sup\limits_v\sum\limits_i\sigma_i\phi_i(v_i) v sup i ∑ σ i ϕ i ( v i ) 與負上確界 sup v ( − ∑ i σ i ϕ i ( v i ) ) \sup\limits_v(-\sum\limits_i\sigma_i\phi_i(v_i)) v sup ( − i ∑ σ i ϕ i ( v i )) 現在都非負;最大值不超過兩者之和,而由於 σ \sigma σ 與 − σ -\sigma − σ 同分佈,兩者期望相同。對正部分套用單邊結果,再把 T ∪ { 0 } T\cup\{0\} T ∪ { 0 } 上 ∑ i A σ i v i \sum\limits_iA\sigma_iv_i i ∑ A σ i v i 的單邊上確界以 T T T 上的絕對上確界界住。除以 n n n 便得所示因子 2 A 2A 2 A ;先對有限集合證明,再經可分近似推廣。
證明透視
壓縮證明為何付出因子二 單邊一步只用 Lipschitz 性與符號獨立,沒有用到 ϕ i ( 0 ) = 0 \phi_i(0)=0 ϕ i ( 0 ) = 0 ,也不損失常數。關鍵一步是把對單一符號的平均寫成對一對 ( v , w ) (v,w) ( v , w ) 的上確界:兩個分開的上確界因此合成一個式子,其中 ϕ i ( v i ) − ϕ i ( w i ) \phi_i(v_i)-\phi_i(w_i) ϕ i ( v i ) − ϕ i ( w i ) 以差的形式出現,Lipschitz 界才可用上。再利用 ( v , w ) (v,w) ( v , w ) 的對稱性,絕對值 ∣ v i − w i ∣ |v_i-w_i| ∣ v i − w i ∣ 便可無代價地去掉。
置中假設只在加入零向量時用了一次。沒有它,新加入的向量會改變變換後的平均,正負上確界亦未必非負,於是「最大值不超過和」一步失效;下面的常數損失反例顯示結論本身亦隨之失效。因子二是這個以和界最大值的步驟的代價,而非 Lipschitz 比較的代價。由於單邊論證在其餘符號固定下依次替換座標,經過 n n n 次替換便完成。
鏈界既不需要 Lipschitz 映射,除了符號平均的有限最大值估計外,也不需要其他集中不等式。
對每個 v v v 選 π j v ∈ A j \pi_jv\in A_j π j v ∈ A j ,距離不超過 ϵ j \epsilon_j ϵ j ,並令 π 0 v = 0 \pi_0v=0 π 0 v = 0 。把 v v v 拆成終端餘項及相鄰中心增量。Cauchy–Schwarz 令餘項的帶符號平均至多 ϵ J \epsilon_J ϵ J ;每個增量的正規化範數至多 ϵ j + ϵ j − 1 = 3 ϵ j \epsilon_j+\epsilon_{j-1}=3\epsilon_j ϵ j + ϵ j − 1 = 3 ϵ j 。對 M M M 個範數不超過 b b b 的向量,符號矩母函數及最佳參數給出絕對最大值期望至多 b 2 log ( 2 M ) / n b\sqrt{2\log(2M)/n} b 2 log ( 2 M ) / n 。第 j j j 層至多有 N j N j − 1 N_jN_{j-1} N j N j − 1 個增量,逐層相加便得公式。尺度之間毋須獨立:和的上確界不超過上確界之和。
證明透視
鏈比單一網優勝在哪裏 逐層相消把 v v v 寫成 v = ( v − π J v ) + ∑ j = 1 J ( π j v − π j − 1 v ) v=(v-\pi_Jv)+\sum\limits_{j=1}^J(\pi_jv-\pi_{j-1}v) v = ( v − π J v ) + j = 1 ∑ J ( π j v − π j − 1 v ) ,其中 π 0 v = 0 \pi_0v=0 π 0 v = 0 。終端部分無須計數:Cauchy–Schwarz 給出 ∣ 1 n ∑ i σ i u i ∣ ≤ d ( u , 0 ) |\frac1n\sum\limits_i\sigma_iu_i|\le d(u,0) ∣ n 1 i ∑ σ i u i ∣ ≤ d ( u , 0 ) ,所以它至多花費 ϵ J \epsilon_J ϵ J 。關鍵一步是:雖然 v v v 走遍無限集合,尺度 j j j 的增量至多只取 N j N j − 1 N_jN_{j-1} N j N j − 1 個值,每個範數至多 3 ϵ j 3\epsilon_j 3 ϵ j ,因此有限極大估計可逐個尺度使用。若只用尺度 ϵ J \epsilon_J ϵ J 的單一網,就要以完整半徑 R R R 對應 log N J \log N_J log N J ;鏈則把每個大的計數配上小的半徑。
如何解讀熵估計
若網大小隨逆半徑作多項式增長,其對數只隨尺度指標線性增長,而半徑幾何下降,故和收斂。若熵估計過大,應保留有限終端誤差並選截斷層數,不能把無窮界說成有資訊。距離的正規化也影響常數;未除以 n \sqrt n n 的歐幾里得(Euclid)範數會改變全部半徑。
例題詳解
取 n = 2000 , δ = 0.05 n=2000,\delta=0.05 n = 2000 , δ = 0.05 ,觀察到的損失絕對複雜度為 r ( S ) = 0.02 r(S)=0.02 r ( S ) = 0.02 。此時 t = log 40 / 4000 ≈ 0.03037 t=\sqrt{\log40/4000}\approx0.03037 t = log 40/4000 ≈ 0.03037 ,一致偏差界約為 0.13110 0.13110 0.13110 ,精確 ERM 超額風險界約為 0.26221 0.26221 0.26221 。若最優化容許誤差為 0.005 0.005 0.005 ,超額界便恰好加上此值。計算這個超額比較毋須用到訓練誤差;若要控制絕對風險,則把偏差界加到訓練誤差上。
預測與標籤在 [ − 1 , 1 ] [-1,1] [ − 1 , 1 ] 時,設 ϕ i ( t ) = ( t − y i ) 2 − y i 2 \phi_i(t)=(t-y_i)^2-y_i^2 ϕ i ( t ) = ( t − y i ) 2 − y i 2 。它在零消失,導數絕對值至多四,所以壓縮給出預測複雜度的八倍。原損失另加 y i 2 y_i^2 y i 2 ,該向量的符號平均至多 ∑ i y i 4 / n ≤ 1 / n \sqrt{\sum\limits_i y_i^4}/n\le1/\sqrt n i ∑ y i 4 / n ≤ 1/ n 。故損失複雜度至多為八倍預測複雜度加 1 / n 1/\sqrt n 1/ n 。原平方損失值域為 [ 0 , 4 ] [0,4] [ 0 , 4 ] ;要套用值域 [ 0 , 1 ] [0,1] [ 0 , 1 ] 的概率定理,必須先除以四。
令 v w = ( w x 1 , … , w x n ) v_w=(wx_1,\ldots,wx_n) v w = ( w x 1 , … , w x n ) ,w ∈ [ − 1 , 1 ] w\in[-1,1] w ∈ [ − 1 , 1 ] 且 ∣ x i ∣ ≤ 1 |x_i|\le1 ∣ x i ∣ ≤ 1 。對稱集合的半徑至多一,在 ϵ j = 2 − j \epsilon_j=2^{-j} ϵ j = 2 − j 可用參數網給出 N j ≤ 2 j + 1 + 1 ≤ 2 j + 2 N_j\le2^{j+1}+1\le2^{j+2} N j ≤ 2 j + 1 + 1 ≤ 2 j + 2 。因此 log ( 2 N j N j − 1 ) ≤ ( 2 j + 4 ) log 2 \log(2N_jN_{j-1})\le(2j+4)\log2 log ( 2 N j N j − 1 ) ≤ ( 2 j + 4 ) log 2 ,在 j = 1 j=1 j = 1 時這是較粗的界。鏈界為終端半徑加 3 2 log 2 / n ∑ j = 1 J 2 − j 2 j + 4 3\sqrt{2\log2/n}\sum\limits_{j=1}^J2^{-j}\sqrt{2j+4} 3 2 log 2/ n j = 1 ∑ J 2 − j 2 j + 4 。幾何因子壓過平方根,無窮和有限,故有正確的 n − 1 / 2 n^{-1/2} n − 1/2 量級;直接計算線性類仍有較佳常數。
常見錯誤
反例模式
未置中的常數破壞粗心的壓縮結論 預測類只有零向量,而 ϕ ( t ) = 1 \phi(t)=1 ϕ ( t ) = 1 。此映射為零-Lipschitz,變換後的絕對複雜度卻是 E ∣ ∑ i σ i ∣ / n > 0 \mathbb E|\sum\limits_i\sigma_i|/n>0 E ∣ i ∑ σ i ∣/ n > 0 ,原複雜度則為零。缺少的條件是置中:先減去零點值,再另外計算偏移的符號平均。有界標籤不會讓絕對值中的偏移自行消失。
置信事件同時控制所有成員,包括依數據選出的 ERM,但假設類須預先固定,否則要計入設計搜尋。這個事件的隨機性是重新抽取整份訓練樣本。觀察到某份樣本後,不能把定理理解成「此預測器的固定風險有某概率落在界內」,而應理解為抽樣程序至少以指定比例產生滿足所列關係的樣本。訓練程序若另有隨機性亦無妨,因為一致事件涵蓋所宣告假設類內的任何最終選擇。鏈只估計樣本條件複雜度,真正連到總體風險的是對稱化及集中。如果數值上界超過最大可能損失,它可以正確但沒有資訊;不能據此斷言預測表現差。
只對 D D D 用有界差分,再把觀察到的 r ( S ) r(S) r ( S ) 代替 E r \mathbb Er E r ,便得 D ≤ 2 r ( S ) + t D\le2r(S)+t D ≤ 2 r ( S ) + t 。這忽略了 r ( S ) r(S) r ( S ) 可以低於其期望。正確的數據依賴界把 δ / 2 \delta/2 δ /2 分給兩個事件,為 D D D 付出 t t t ,為加倍的複雜度付出 2 t 2t 2 t ,因此是 2 r ( S ) + 3 t 2r(S)+3t 2 r ( S ) + 3 t 。若已知期望複雜度,單一事件則給出 D ≤ 2 E r + log ( 1 / δ ) / ( 2 n ) D\le2\mathbb Er+\sqrt{\log(1/\delta)/(2n)} D ≤ 2 E r + log ( 1/ δ ) / ( 2 n ) 。
複雜度本身包含上確界,未必容易精確計算。可證明的數值上界可以代入整個概率結論;只搜尋部分候選函數得到的卻是上確界的下界,不能冒充上界。統計定理並沒有自動驗證估計複雜度項所用的數值方法。
總結
有界差分同時控制偏差及複雜度的波動;壓縮把幾何轉移至置中的 Lipschitz 損失;鏈則按尺度分配近似成本。三者的假設互補,任何一個都不能代替其餘兩個。
練習
快速檢查
(若全部損失位於寬度 b b b 的共同區間,推導帶適當集中項的觀察複雜度偏差界。)
解答 · 答案 改變一個觀察使函數值至多變 b b b ,故兩種敏感度均為 b / n b/n b / n ,對稱化不變。在所述事件上得到 D ≤ 2 r + 3 b log ( 2 / δ ) / ( 2 n ) D\le2r+3b\sqrt{\log(2/\delta)/(2n)} D ≤ 2 r + 3 b log ( 2/ δ ) / ( 2 n ) 。非零區間偏移已包括在 r r r 中;區間寬度控制波動,不控制複雜度本身的絕對大小。
快速檢查
(取 n = 2 n=2 n = 2 ,計算常數向量 ( 1 , 1 ) (1,1) ( 1 , 1 ) 的絕對 Rademacher 平均,並以數值解釋壓縮反例。)
解答 · 答案 符號和為 2 , 0 , − 2 2,0,-2 2 , 0 , − 2 的概率分別為 1 / 4 , 1 / 2 , 1 / 4 1/4,1/2,1/4 1/4 , 1/2 , 1/4 ,其絕對值期望除以二為 1 / 2 1/2 1/2 。原零類的複雜度為零,常數變換卻得到 1 / 2 1/2 1/2 ,即使 Lipschitz 常數為零。
快速檢查
(證明把固定向量 a a a 加到評估類,絕對複雜度至多增加 ∥ a ∥ 2 / n \|a\|_2/n ∥ a ∥ 2 / n 。)
解答 · 答案 對每個符號向量,用三角不等式把平移後的類與 ∑ i σ i a i / n \sum\limits_i\sigma_i a_i/n i ∑ σ i a i / n 分開。由期望中的 Cauchy–Schwarz,E ∣ ∑ i σ i a i ∣ ≤ E ( ∑ i σ i a i ) 2 = ∥ a ∥ 2 \mathbb E|\sum\limits_i\sigma_i a_i|\le\sqrt{\mathbb E(\sum\limits_i\sigma_i a_i)^2}=\|a\|_2 E ∣ i ∑ σ i a i ∣ ≤ E ( i ∑ σ i a i ) 2 = ∥ a ∥ 2 。除以 n n n 即得。
快速檢查
(若 N j ≤ e C j N_j\le e^{Cj} N j ≤ e C j 、C > 0 C>0 C > 0 ,證明無窮鏈收斂,並指出固定 R , C R,C R , C 時對 n n n 的依賴。)
解答 · 答案 對數至多 log 2 + C ( 2 j − 1 ) \log2+C(2j-1) log 2 + C ( 2 j − 1 ) ,第一層用 N 0 = 1 N_0=1 N 0 = 1 只會更小。因此每項至多為常數乘 R 2 − j j / n R2^{-j}\sqrt{j/n} R 2 − j j / n 。相鄰 2 − j j 2^{-j}\sqrt j 2 − j j 的比趨於 1 / 2 1/2 1/2 ,故收斂;終端半徑趨零,固定 R , C R,C R , C 下得到 n − 1 / 2 n^{-1/2} n − 1/2 量級。