D.9 Khintchine-Kahane 不等式

以下不等式在多种不同的背景下都很有用，包括在证明线性假设的经验 Rademacher 复杂度下界时（第六章）。

定理 D.9(Khintchine-Kahane 不等式) 设 $\left(\mathbb{H},\parallel \cdot \parallel \right)$ 是一个范数向量空间，且 ${\mathbf{x}}_1,\dots ,{\mathbf{x}}_m$ 是 $\mathbb{H}$ 的 $m\ge 1$ 元素。设 $\sigma ={\left({\sigma }_1,\dots ,{\sigma }_m\right)}^{\top }$ ，其中 ${\sigma }_i$ 是在 $\{-1,+1\}$ (Rademacher 变量)中取值的独立均匀随机变量。那么，以下不等式成立:

$$\frac{1}{2}\underset{\sigma }{\mathbb{E}}\left[{\Vert \begin{array}{c}\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\end{array}\Vert }^2\right]\le {\left(\underset{\sigma }{\mathbb{E}}\left[\Vert \begin{array}{c}\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\end{array}\Vert \right]\right)}^2\le \underset{\sigma }{\mathbb{E}}\left[{\Vert \begin{array}{c}\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\end{array}\Vert }^2\right].\text{\hspace{1em}(D.20)}$$

证明:第二个不等式是 $x\mapsto x^2$ 的凸性和Jensen不等式(定理 B.20)的直接结果。

为了证明左侧不等式，首先注意到对于任何 ${\beta }_1,\dots ,{\beta }_m\in \mathbb{R}$ ，展开乘积 $\prod _{i=1}^m\left(1+{\beta }_i\right)$ 正好得到所有单项式 ${\beta }_1^{{\delta }_1}\dots {\beta }_m^{{\delta }_m}$ 的和，指数 ${\delta }_1,\dots ,{\delta }_m$ 在 $\{0,1\}$ 中。我们将使用 ${\beta }_1^{{\delta }_1}\cdots {\beta }_m^{{\delta }_m}={\beta }^{\delta }$ 和 $\left|\delta \right|=\sum _{i=1}^m{\delta }_m$ 来表示任何 $\delta =\left({\delta }_1,\dots ,{\delta }_m\right)\in \{0,1{\}}^m$ 。基于此，对于任何 $\left({\alpha }_1,\dots ,{\alpha }_m\right)\in {\mathbb{R}}^m$ 和 $t>0$ ，以下等式成立:

$$t^2\prod _{i=1}^m\left(1+{\alpha }_i/t\right)=t^2\sum _{\delta \in \{0,1{\}}^m}{\alpha }^{\delta }/t^{|\delta |}=\sum _{\delta \in \{0,1{\}}^m}{t}^{2-|\delta |}{\alpha }^{\delta }.$$

对两边关于 $t$ 求导，并令 $t=1$ ，得到

$$2\prod _{i=1}^m\left(1+{\alpha }_i\right)-\sum _{j=1}^m{\alpha }_j\prod _{i\ne j}\left(1+{\alpha }_i\right)=\sum _{\delta \in \{0,1{\}}^m}\left(2-\left|\delta \right|\right){\alpha }^{\delta }.\text{\hspace{1em}(D.21)}$$

对于任何 $\sigma \in \{-1,+1{\}}^m$ ，设 $S_{\sigma }$ 由 $S_{\sigma }=\Vert \begin{array}{c}{s}_{\sigma }\end{array}\Vert$ 定义，其中 $s_{\sigma }=\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i$ 。然后，令 ${\alpha }_i={\sigma }_i{\sigma }_i^{\prime }$ ，将 (D.21) 的两边乘以 $S_{\sigma }{S}_{{\sigma }^{\prime }}$ ，并对所有 $\sigma ,{\sigma }^{\prime }\in$ $\{-1,+1{\}}^m$ 求和，得到

$$\sum _{\sigma ,{\sigma }^{\prime }\in \{-1,+1{\}}^m}\left(2\prod _{i=1}^m\left(1+{\sigma }_i{\sigma }_i^{\prime }\right)-\sum _{j=1}^m{\sigma }_j{\sigma }_j^{\prime }\prod _{i\ne j}\left(1+{\sigma }_i{\sigma }_i^{\prime }\right)\right)S_{\sigma }{S}_{{\sigma }^{\prime }}$$ $$=\sum _{\sigma ,{\sigma }^{\prime }\in \{-1,+1{\}}^m}\sum _{\delta \in \{0,1{\}}^m}\left(2-\left|\delta \right|\right){\sigma }^{\delta }{\sigma }^{\prime \delta }{S}_{\sigma }{S}_{{\sigma }^{\prime }}$$ $$=\sum _{\delta \in \{0,1{\}}^m}\left(2-\left|\delta \right|\right)\sum _{\sigma ,{\sigma }^{\prime }\in \{-1,+1{\}}^m}{\sigma }^{\delta }{\sigma }^{\prime \delta }{S}_{\sigma }{S}_{{\sigma }^{\prime }}\text{\hspace{1em}(D.22)}$$ $$=\sum _{\delta \in \{0,1{\}}^m}\left(2-\left|\delta \right|\right){\left[\sum _{\sigma \in \{-1,+1{\}}^m}{\sigma }^{\delta }{S}_{\sigma }\right]}^2.$$

注意，右侧和中的 $\left|\delta \right|\ge 2$ 项是非正的。带有 $\left|\delta \right|=1$ 的项为零:因为 $S_{\sigma }=S_{-\sigma }$ ，在这种情况下我们有 $\sum _{\sigma \in \{-1,+1{\}}^m}{\sigma }^{\bar{\delta }}{S}_{\sigma }=0$ 。因此，右侧可以被 $\delta =0$ 项所界定，即 $2{\left(\sum _{\sigma \in \{-1,+1{\}}^m}{S}_{\sigma }\right)}^2$ 。(D.22) 的左侧可以重写如下:

$$\sum _{\sigma \in \{-1,+1{\}}^m}\left(2^{m+1}-m{2}^{m-1}\right)S_{\sigma }^2+2^{m-1}\sum _{\begin{array}{c}\sigma \in \{-1,+1{\}}^m\\ {\sigma }^{\prime }\in B\left(\sigma ,1\right)\end{array}}{S}_{\sigma }{S}_{{\sigma }^{\prime }}$$ $$=2^m\sum _{\sigma \in \{-1,+1{\}}^m}{S}_{\sigma }^2+2^{m-1}\sum _{\sigma \in \{-1,+1{\}}^m}{S}_{\sigma }\left(\sum _{{\sigma }^{\prime }\in B\left(\sigma ,1\right)}{S}_{{\sigma }^{\prime }}-\left(m-2\right)S_{\sigma }\right),\text{\hspace{1em}(D.23)}$$

其中 $B\left(\sigma ,1\right)$ 表示与 $\sigma$ 在恰好一个坐标 $j\in \left[m\right]$ 上不同的 ${\sigma }^{\prime }$ 的集合，即与 $\sigma$ 的汉明距离为1的 ${\sigma }^{\prime }$ 的集合。注意，对于任何这样的 ${\sigma }^{\prime },s_{\sigma }-s_{{\sigma }^{\prime }}=2{\sigma }_j{\mathbf{x}}_j$ ，对于其中一个坐标 $j\in \left[m\right]$ ，因此 $\sum _{{\sigma }^{\prime }\in B\left(\sigma ,1\right)}{s}_{\sigma }-s_{{\sigma }^{\prime }}=2s_{\sigma }$ 。鉴于这一点，并使用三角不等式，我们可以写出

$$\left(m-2\right)S_{\sigma }=\Vert \begin{array}{c}m{s}_{\sigma }\end{array}\Vert -\Vert \begin{array}{c}2s_{\sigma }\end{array}\Vert =\Vert \begin{array}{c}\sum _{{\sigma }^{\prime }\in B\left(\sigma ,1\right)}{s}_{\sigma }\end{array}\Vert -\Vert \begin{array}{c}\sum _{{\sigma }^{\prime }\in B\left(\sigma ,1\right)}{s}_{\sigma }-s_{{\sigma }^{\prime }}\end{array}\Vert$$ $$\le \Vert \begin{array}{c}\sum _{{\sigma }^{\prime }\in B\left(\sigma ,1\right)}{s}_{{\sigma }^{\prime }}\end{array}\Vert \le \sum _{{\sigma }^{\prime }\in B\left(\sigma ,1\right)}{S}_{{\sigma }^{\prime }}.$$

因此，(D.23)的第二项是非负的，且(D.22)的左侧可以由第一项 $2^m\sum _{\sigma \in \{-1,+1{\}}^m}{S}_{\sigma }^2$ 从下面界定。将此与为(D.22)找到的上界相结合，得到

$$2^m\sum _{\sigma \in \{-1,+1{\}}^m}{S}_{\sigma }^2\le 2{\left[\sum _{\sigma \in \{-1,+1{\}}^m}{S}_{\sigma }\right]}^2.$$

双方除以 $2^{2m}$ 并使用 $\mathbb{P}\left[\sigma \right]=1/2^m$ 得到 ${\mathbb{E}}_{\sigma }\left[S_{\sigma }^2\right]\le 2{\left({\mathbb{E}}_{\sigma }\left[S_{\sigma }\right]\right)}^2$ ，从而完成了证明。

在(D.20)的第一个不等式中出现的常数 $1/2$ 是最优的。为了看到这一点，考虑 $m=2$ 和 ${\mathbf{x}}_1={\mathbf{x}}_2=\mathbf{x}$ 对于某个非零向量 $\mathbf{x}\in \mathbb{H}$ 的情况。那么，第一个不等式左侧是 $\frac{\bar{1}}{2}\sum _{i=1}^{m^{-}}\parallel {\mathbf{x}}_i{\parallel }^2=\parallel \mathbf{x}{\parallel }^2$ ，右侧是 ${\left({\mathbb{E}}_{\sigma }\left[\parallel \left({\sigma }_1+{\sigma }_2\right)\mathbf{x}\parallel \right]\right)}^2=$ $\parallel \mathbf{x}{\parallel }^2{\left({\mathbb{E}}_{\sigma }\left[\left|{\sigma }_1+{\sigma }_2\right|\right]\right)}^2=\parallel \overline{\mathbf{x}}{\parallel }^2.$

注意，当范数 $\parallel \cdot \parallel$ 对应于内积，如在希尔伯特空间 $\mathbb{H}$ 的情况下，我们可以写出

$$\underset{\sigma }{\mathbb{E}}\left[{\Vert \begin{array}{c}\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\end{array}\Vert }^2\right]=\sum _{i,j=1}^m\underset{\sigma }{\mathbb{E}}\left[{\sigma }_i{\sigma }_j\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)\right]=\sum _{i,j=1}^m\underset{\sigma }{\mathbb{E}}\left[{\sigma }_i{\sigma }_j\right]\left({\mathbf{x}}_i\cdot {\mathbf{x}}_j\right)=\sum _{i=1}^m{\Vert \begin{array}{c}{\mathbf{x}}_i\end{array}\Vert }^2,$$

因为由随机变量 ${\sigma }_i$ 的独立性，对于 $i\ne j,{\mathbb{E}}_{\sigma }\left[{\sigma }_i{\sigma }_j\right]={\mathbb{E}}_{\sigma }\left[{\sigma }_i\right]{\mathbb{E}}_{\sigma }\left[{\sigma }_j\right]=0$ 。因此，(D.20)可以重写如下:

$$\frac{1}{2}\sum _{i=1}^m{\Vert \begin{array}{c}{\mathbf{x}}_i\end{array}\Vert }^2\le {\left(\mathbb{E}\left[\Vert \begin{array}{c}\sum _{i=1}^m{\sigma }_i{\mathbf{x}}_i\end{array}\Vert \right]\right)}^2\le \sum _{i=1}^m{\Vert \begin{array}{c}{\mathbf{x}}_i\end{array}\Vert }^2\text{\hspace{1em}(D.24)}$$