动机
期望保证描述重复抽样的平均情况,但我们通常只观察一份训练样本,然后便要使用所得预测器。若要为这次程序附上概率保证,单有对称化仍不足够:一致偏差可能高于其期望,而样本上算出的复杂度又可能低于其期望。以观测复杂度作右边的界,必须同时处理这两种波动。
另一个困难来自损失变换。我们往往容易估计预测函数类的几何性质,真正需要的却是经过非线性损失后的函数类。还有,单一粗网格可能浪费信息;逐层修正的链可以分别计算各尺度的细小变化,避免每个区分都按最大距离付费。
以下始终使用带绝对值的 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 量级。