Gradient Descent Provably Optimizes Over-parameterized Neural Networks 论文阅读

Gradient Descent Provably Optimizes Over-parameterized Neural Networks

论文地址：http://cn.arxiv.org/abs/1810.02054

摘要

神经网络成功的一个谜是可以通过使用随机初始化的一阶方法（如梯度下降）来实现0训练损失，即使是目标函数是非凸和非平滑的。这篇论文发现了使用ReLU激活函数的两层神经网络的一个现象。对于数据量为$n$的数据集和采用ReLU激活函数$m$个隐藏节点的浅层神经网络，我们使用随机初始化的梯度下降法来优化二次损失函数（quadratic loss function），可以证明：只要$m$足够大并且数据是非退化的，将获得具有线性收敛速度的全局最优解。

以上分析主要基于以下观察：过参数化(over-parameterization)和随机初始化联合限制了每个权重向量在所有迭代过程中都接近于初始化，这允许利用强凸性来显示梯度下降将以全局线性速率收敛到全局最优。作者相信这些见解也会有助于分析深度模型以及其他一阶方法。

这篇论文忽略了神经网络的深度，还需要更加努力。而且这篇论文做出的结果是：当隐层神经元个数$m$足够大时，将实现0训练误差（全局最优），个人觉得最重要的是实现测试误差最优。

另外，我很仔细地阅读论文，似乎发现里面有些地方很是粗糙，或是笔误，或是错误，但是对文章整体的结果并没有太大的影响。

问题定义

对于一个使用ReLU（修正线性单元，rectified linear unit）作为激活函数的两层（一个隐层）的神经网络，可以用以下式子来表示：
$$f(W,a,x)=\frac{1}{\sqrt{m}}\sum _{r=1}^m{a}_r\sigma \left(w_r^{T}x\right)$$
其中$x\in {\mathbb{R}}^d$是输入，$w_r\in {\mathbb{R}}^d$是第一层的权重向量，$a_r\in \mathbb{R}$是输出的加权，以及σ(z)=max{0,z}\sigma(z)=max\{0,z\}σ(z)=max{ 0,z}为ReLU函数。

本文主要关注使用二次损失的经验风险最小化问题。对于数据集{(xi,yi)}i=1n\{(x_i,y_i)\}_{i=1}^n{ (xi?,yi?)}i=1n?，我们希望最小化以下目标：
$$\underset{W\in {\mathbb{R}}^{d\times m}}{\min }L(W)=\sum _{i=1}^n\frac{1}{2}(f(W,a,x_i)?y_i{)}^2$$
为了实现这个目标，我们使用梯度下降法来更新权重矩阵：
$$W(k+1)=W(k)?\eta \frac{?L(W(k))}{?W(k)}$$
其中$\eta >0$为步长，对于每个权重向量的具体微分如下：
$$\frac{?L(W)}{?w_r}=\frac{1}{\sqrt{m}}\sum _{i=1}^n(f(W,a,x_i)?y_i)a_r{x}_i\mathbb{I}\left(w_r^T{x}_i\ge 0\right)$$
$\mathbb{I}$为指示函数，为真等于1，为假等于0。

对此，本文将严格地证明对于非退化的数据集以及最够大的$m$，并且正确的随机初始化$a$和$W(0)$，GD能够以线性收敛速率实现零训练损失。即有：
$$?\epsilon >0,?W(K),\mathrm{s}.\mathrm{t}.L(W(K))\le \epsilon \mathrm{i}\mathrm{n}K=O(\log (1/\epsilon ))\mathrm{i}\mathrm{t}\mathrm{e}\mathrm{r}\mathrm{a}\mathrm{t}\mathrm{i}\mathrm{o}\mathrm{n}\mathrm{s}$$

连续时间分析(Continuous Time Analysis)

在本节中，将给出梯度流（最陡下降曲线）的结果，即具有无穷小步长的梯度下降。为此，我们考虑如下定义的微分方程：
$$\frac{d{w}_r(t)}{dt}=?\frac{?L(W)}{?w_r}$$
对r∈{1,2,...,m}r\in \{1,2,...,m\}r∈{ 1,2,...,m}，定义$u_i(t)=f(W(t),a,x_i)$表示在时间$t$上对输入$x_i$的预测，并且令$u(t)=(u_1(t),u_2(t),...,u_n(t))\in {\mathbb{R}}^n$为在时间$t$上的预测向量。

有以下定理：

Theorem 1(Convergence Rate of Gradient Flow)：假设对所有i∈{1,2,...,n}，∥xi∥2=1，∣yi∣≤Ci\in \{1,2,...,n\}，\lVert x_i\rVert_2=1，|y_i|\le Ci∈{ 1,2,...,n}，∥xi?∥2?=1，∣yi?∣≤C对常数$C$，以及矩阵$H^{\infty }\in {\mathbb{R}}^{n\times n}$，其中Hij∞=Ew?N(0,I)[xiTxjI{wTxi≥0,wTxj≥0}]H^{\infty}_{ij}=\mathbb{E}_{w\sim N(0,I)}[x_i^Tx_j\mathbb{I}\{w^Tx_i\ge0,w^Tx_j\ge0\}]Hij∞?=Ew?N(0,I)?[xiT?xj?I{ wTxi?≥0,wTxj?≥0}]，满足${\lambda }_{\min }(H^{\infty })\stackrel{△}{=}{\lambda }_0>0$。然后对r∈{1,2,...,m}r\in \{1,2,...,m\}r∈{ 1,2,...,m}，初始化$w_r?N(0,I),a_r?unif[?1,1]$，并且令$m=\Omega (\frac{n^6}{{\lambda }_0^4})$，可得：
$$\Vert u(t)?y{\Vert }_2^2\le \exp (?{\lambda }_{0}t)\Vert u(0)?y{\Vert }_2^2$$
其中i∈{1,2,...,n}，∥xr∥2=1，∣yi∣≤Ci\in \{1,2,...,n\}，\lVert x_r\rVert_2=1，|y_i|\le Ci∈{ 1,2,...,n}，∥xr?∥2?=1，∣yi?∣≤C的假设是为了简化，这可以通过简单放缩实现。关键的假设是$H^{\infty }$矩阵是严格正定的(Xie et al. [2017], Tsuchida et al. [2017])。另外，$m$要求为$\Omega (\frac{n^6}{{\lambda }_0^4})$，即$m$依赖于样本数$n$以及${\lambda }_0$，下面将会证明over-parameterized对保证梯度下降找到全局最优起到很关键的作用。最后，我们可以看到$\Vert u(t)?y{\Vert }_2^2$是以指数级递减至0，并且这个速率依赖于${\lambda }_0$，而不依赖于$n$。

Theorem 1的证明

首先计算每个预测的变化：
KaTeX parse error: No such environment: eqnarray at position 8: \begin{?e?q?n?a?r?r?a?y?}? \frac{d}{dt}u_…
其中$H(t)\in {\mathbb{R}}^{n\times n}$，满足：
Hij(t)=1mxiTxj∑r=1mI{xiTwr(t)≥0,xjTwr(t)≥0}H_{ij}(t)=\frac{1}{m}x_i^Tx_j\sum\limits_{r=1}^m\mathbb{I}\{x_i^Tw_r(t)\ge0,x_j^Tw_r(t)\ge0\} Hij?(t)=m1?xiT?xj?r=1∑m?I{ xiT?wr?(t)≥0,xjT?wr?(t)≥0}
有了这个定义后，我们可以用以下简洁的式子来描述：
$$\frac{d}{dt}u(t)=H(t)(y?u(t))$$
注意到$H(t)$是一个时间依赖的对称矩阵，我们先在$t=0$是分析它的属性。我们引出下面这个引理，当$m$很大时，$H(0)$的最小特征值在很大的概率内有下界。

Lemma 1.1

Lemma 1.1：如果$m=\Omega (\frac{n^2}{{\lambda }_0^2}{\log }^2(\frac{n}{\delta }))$，有$P({\lambda }_{\min }(H(0))\ge \frac{3}{4}{\lambda }_0)\ge 1?\delta$。

证明：

Hoeffding inequality：

假定$X_1,X_2,...,X_n$为有界独立随机变量，且$X_i\in [a_i,b_i]$，定义经验均值变量$\overline{X}=\frac{1}{n}\sum _{i=1}^n{X}_i$，满足不等式：
$$\begin{gathered} P(\overline{X}?\mathbb{E}[\overline{X}]\ge t)\le \exp (?\frac{2n^2{t}^2}{{\sum }_{i=1}^n(b_i?a_i{)}^2})或 \\ P(\overline{X}?\mathbb{E}[\overline{X}]\le t)\ge 1?\exp (?\frac{2n^2{t}^2}{{\sum }_{i=1}^n(b_i?a_i{)}^2}) \end{gathered}$$
这里我们有:
Hij(0)=1m∑r=1mxiTxjI{xiTwr≥0,xjTwr≥0}Hij∞=Ew?N(0,I)[xiTxjI{wTxi≥0,wTxj≥0}]=E[Hij(0)]H_{ij}(0)=\frac{1}{m}\sum\limits_{r=1}^mx_i^Tx_j\mathbb{I}\{x_i^Tw_r\ge0,x_j^Tw_r\ge0\}\\ H^{\infty}_{ij}=\mathbb{E}_{w\sim N(0,I)}[x_i^Tx_j\mathbb{I}\{w^Tx_i\ge0,w^Tx_j\ge0\}]=\mathbb{E}[H_{ij}(0)] Hij?(0)=m1?r=1∑m?xiT?xj?I{ xiT?wr?≥0,xjT?wr?≥0}Hij∞?=Ew?N(0,I)?[xiT?xj?I{ wTxi?≥0,wTxj?≥0}]=E[Hij?(0)]
以下是论文上提出的结果：
$$P(|H_{ij}(0)?H_{ij}^{\infty }|\le \frac{2\log (1/{\delta }^{\prime })}{\sqrt{m}})\ge 1?{\delta }^{\prime }$$
那么至少有概率$1?\delta$，使得：
$$|H_{ij}(0)?H_{ij}^{\infty }|\le \frac{4\log (n/\delta )}{\sqrt{m}}$$
所以有：
$$\Vert H(0)?H^{\infty }{\Vert }_2^2\le \Vert H(0)?H^{\infty }{\Vert }_F^2\le \sum _{i,j}|H_{ij}(0)?H_{ij}^{\infty }|\le \frac{16n^2{\log }^2(n/\delta )}{m}$$
因此如果$m=\Omega (\frac{n^2{\log }^2(n/\delta )}{{\lambda }_0^2})$，就可以得到想要的结果。

但是我试了一下，似乎应该做出一些变动！！！

易证xitxjI{xiTwr≥0,xjTwr≥0}∈[?1,1]x_i^tx_j\mathbb{I}\{x_i^Tw_r\ge0,x_j^Tw_r\ge0\}\in[-1,1]xit?xj?I{ xiT?wr?≥0,xjT?wr?≥0}∈[?1,1]，根据Hoeffding inequality，有：
$$P(|H_{ij}(0)?H_{ij}^{\infty }|\le t)\ge 1?2\exp (?\frac{m{t}^2}{2})$$
令$t=\sqrt{\frac{2\log (2/{\delta }^{\prime })}{m}}$，得：
KaTeX parse error: No such environment: eqnarray at position 8: \begin{?e?q?n?a?r?r?a?y?}? P\left(|H_{ij}…
那么至少有概率$1?\delta$，使得：
$$|H_{ij}(0)?H_{ij}^{\infty }|\le \sqrt{\frac{2\log (2/\delta )}{m}}$$
所以有：
$$\Vert H(0)?H^{\infty }{\Vert }_2^2\le \Vert H(0)?H^{\infty }{\Vert }_F^2\le \sum _{i,j}|H_{ij}(0)?H_{ij}^{\infty }{|}^2\le \frac{2n^2\log (2/\delta )}{m}$$
因此只需$m=\Omega (\frac{n^2\log (2/\delta )}{{\lambda }_0^2})$

Lemma 1.2

Lemma 1.2：假设给定时间$t$，$?c>0$，对所有的r∈{1,2,...,m}r\in \{1,2,...,m\}r∈{ 1,2,...,m}，有$\Vert w_r(t)?w_r(0)\Vert \le \frac{c{\lambda }_0}{n^2}\stackrel{△}{=}R$，那么在初始化上有很大的概率使得${\lambda }_{\min }(H(t))\ge \frac{{\lambda }_0}{2}$。

证明：

定义事件:
$$A_{ir}=\left\{?w:\Vert w?w_r(0)\Vert \le R,\mathbb{I}\left\{x_i^T{w}_r(0)\ge 0\right\}?=\mathbb{I}\left\{x_i^{T}w\ge 0\right\}\right\}.$$
注意到这个事件当且仅当$|w_r(0{)}^T{x}_0|<R$时发生。（此处应该是作者笔误，应该是$|w_r(0{)}^T{x}_i|<R$）。另外注意到$w_r(0)?N(0,I)$，那么有：$P(A_{ir})=P(|w_r(0{)}^T{x}_i|<R)\le P_{w_r?N(0,I)}(|w_r|<R)\le \frac{2R}{\sqrt{2\pi }}$，

又由Cauthy不等式有：$|x_i^T{x}_j|\le \Vert x_i{\Vert }_2\Vert x_j{\Vert }_2=1$，而且易得以下式子：
∣(I{wr(0)Txi≥0,wr(0)Txj≥0}?I{wr(t)Txi≥0,wr(t)Txj≥0})∣≤I{Air∪Ajr}\bigg|\left(\mathbb{I}\left\{w_r(0)^Tx_i\ge0,w_r(0)^Tx_j\ge0\right\}-\mathbb{I}\left\{w_r(t)^Tx_i\ge0,w_r(t)^Tx_j\ge0\right\}\right)\bigg|\le\mathbb{I}\{A_{ir}\cup A_{jr}\}\\ ∣∣∣∣?(I{ wr?(0)Txi?≥0,wr?(0)Txj?≥0}?I{ wr?(t)Txi?≥0,wr?(t)Txj?≥0})∣∣∣∣?≤I{ Air?∪Ajr?}
故：
KaTeX parse error: No such environment: align at position 8: \begin{?a?l?i?g?n?}? &\mathbb{E}[|H…
于是，有：
$$\mathbb{E}?\sum _{(i,j)=(1,1)}^{(n,n)}|H_{ij}(t)?H_{ij}(0)|?\le \frac{4n^{2}R}{\sqrt{2\pi }}$$
根据Markov Inequality：对于一个非负的随机变量$X$以及$a>0$，有
$$P(X\ge a)\le \frac{\mathbb{E}(X)}{a}orP(X\le a)\ge 1?\frac{\mathbb{E}(X)}{a}$$
所以对一个很大的绝对常数$C$，有：
$$P?\sum _{(i,j)=(1,1)}^{(n,n)}|H_{ij}(t)?H_{ij}(0)|\le C{n}^{2}R?\ge 1?\frac{4}{\sqrt{2\pi }C}$$
也就是说有很大的概率使得${\sum }_{(i,j)=(1,1)}^{(n,n)}|H_{ij}(t)?H_{ij}(0)|\le C{n}^{2}R$成立，又有：
$$\Vert H(t)?H(0){\Vert }_2\le \Vert H(t)?H(0){\Vert }_F\le \sum _{(i,j)=(1,1)}^{(n,n)}|H_{ij}(t)?H_{ij}(0)|\le C{n}^{2}R$$
最后通过调整$R=\frac{c{\lambda }_0}{n^2}$来控制最小特征值下界：
$${\lambda }_{\min }(H(t))\ge {\lambda }_{\min }(H(0))?C{n}^{2}R\ge \frac{{\lambda }_0}{2}$$

得证。

Lemma 1.3

Lemma 1.3：假设对$0\le s\le t$ ，有${\lambda }_{\min }(H(s))\ge \frac{{\lambda }_0}{2}$，那么我们有$\Vert y?u(t){\Vert }_2^2\le \exp ({\lambda }_{0}t)\Vert y?u(0){\Vert }_2^2$，以及对所有的r∈{1,2,...,m}r\in\{1,2,...,m\}r∈{ 1,2,...,m}，有$\Vert w_r(t)?w_r(0){\Vert }_2^2\le \frac{2\sqrt{n}\Vert y?u(0){\Vert }_2}{\sqrt{m}{\lambda }_0}\stackrel{△}{=}{R}^{\prime }$

证明：

计算损失函数的变化有：
$$\frac{d}{dt}\Vert y?u(t){\Vert }_2^2=?2(y?u(t){)}^{T}H(t)(y?u(t))\le ?{\lambda }_0\Vert y?u(t){\Vert }_2^2$$
即有到:
$$\frac{d}{dt}\left(\exp ({\lambda }_{0}t)\Vert y?u(t){\Vert }_2^2\right)\le 0$$
也就是有函数$\exp ({\lambda }_{0}t)\Vert y?u(t){\Vert }_2^2$单调递减，所以有：
$$\exp ({\lambda }_{0}t)\Vert y?u(t){\Vert }_2^2\le \Vert y?u(0){\Vert }_2^2$$
即有$\Vert y?u(t){\Vert }_2^2\le \exp (?{\lambda }_{0}t)\Vert y?u(0){\Vert }_2^2$，这说明$u(t)\to y$以指数级速率。

接下来我们确定梯度的边界，对$0\le s\le t$，有：
KaTeX parse error: No such environment: eqnarray at position 8: \begin{?e?q?n?a?r?r?a?y?}? \left\lVert\fr…

对梯度积分，有：
$$\Vert w_r(t)?w_r(0){\Vert }_2\le {\int }_0^t{\Vert \frac{d}{ds}{w}_r(s)\Vert }_{2}ds\le \frac{2\sqrt{n}\Vert y?u(0){\Vert }_2}{\sqrt{m}{\lambda }_0}$$
得证。

下面这个引理将会证明如果$R^{\prime }\le R$，Lemma1.2和Lemma1.3将会对所有$t\ge 0$成立。

Lemma 1.4

Lemma 1.4：如果$R^{\prime }\le R$，我们有对所有$t\ge 0$，有${\lambda }_{\min }(H(t))\ge \frac{1}{2}{\lambda }_0$，并且对所有r∈{1,2,...,m}r\in\{1,2,...,m\}r∈{ 1,2,...,m}，有

$\Vert w_r(t)?w_r(0)\Vert >R^{\prime }$以及$\Vert y?u(t){\Vert }_2^2\le \exp (?{\lambda }_{0}t)\Vert y?u(0){\Vert }_2^2.$

证明：

假设结论在$t$时不成立，即?r∈{1,2,...,m}\exists\ r\in\{1,2,...,m\}? r∈{ 1,2,...,m}，有$\Vert w_r(t)?w_r(0)\Vert \ge R^{\prime }$或者$\Vert y?u(t){\Vert }_2^2>\exp (?{\lambda }_{0}t)\Vert y?u(0){\Vert }_2^2$成立，那么根据Lemma1.3知道，存在$s\le t$，使得${\lambda }_{\min }(H(s))<\frac{1}{2}{\lambda }_0$，根据Lemma1.2知存在：
t0=inf?{t&gt;0:max?r∈{1,2,...,m}∥wr(t)?wr(0)∥22&gt;R}t_0=\inf \left\{t&gt;0:\max_{r\in\{1,2,...,m\}}\lVert w_r(t)-w_r(0)\rVert_2^2&gt; R\right\} t0?=inf{ t>0:r∈{ 1,2,...,m}max?∥wr?(t)?wr?(0)∥22?>R}
因此在$t_0$处，存在r∈{1,2,...,m}r\in\{1,2,...,m\}r∈{ 1,2,...,m}，有$\Vert w_r(t)?w_r(0){\Vert }_2^2=R$，根据Lemma1.2，有${\lambda }_{\min }(H(s))\ge \frac{1}{2}{\lambda }_0$，对$t^{\prime }\le t_0$，然而根据Lemma1.3，得$\Vert w_r(t)?w_r(0){\Vert }_2^2\le R^{\prime }\le R$，矛盾！

另一方面，在$t$时，${\lambda }_{\min }(H(t))<\frac{1}{2}{\lambda }_0$，证明类似！

当$m=\Omega \left(\frac{n^5\Vert y?u(0){\Vert }_2^2}{{\lambda }_0^4}\right)$，有$R^{\prime }<R$成立。我们限制 $\mathbb{E}\left[\Vert y?u(0){\Vert }_2^2\right]={\sum }_{i=1}^n(y_i^2+1)=O(n)$，那么根据Markov’s inequality有很大的概率使得$\Vert y?u(0){\Vert }_2^2=O(n)$，则有$m=\Omega (\frac{n^6}{{\lambda }_0^4})$，Theorem1得证！

离散时间分析(Discrete Time Analysis)

这节将要展示的是随机初始化的梯度下降，在使用恒定的步长下，将以线性速率收敛到全局最小值，首先介绍以下定理。

Theorem 2(Convergence Rate of Gradient Descent)：假设对所有i∈{1,2,...,n}，∥xi∥2=1，∣yi∣≤Ci\in \{1,2,...,n\}，\lVert x_i\rVert_2=1，|y_i|\le Ci∈{ 1,2,...,n}，∥xi?∥2?=1，∣yi?∣≤C对常数$C$，以及矩阵$H^{\infty }\in {\mathbb{R}}^{n\times n}$，其中Hij∞=Ew?N(0,I)[xiTxjI{wTxi≥0,wTxj≥0}]H^{\infty}_{ij}=\mathbb{E}_{w\sim N(0,I)}[x_i^Tx_j\mathbb{I}\{w^Tx_i\ge0,w^Tx_j\ge0\}]Hij∞?=Ew?N(0,I)?[xiT?xj?I{ wTxi?≥0,wTxj?≥0}]，满足${\lambda }_{\min }(H^{\infty })\stackrel{△}{=}{\lambda }_0>0$。然后对r∈{1,2,...,m}r\in \{1,2,...,m\}r∈{ 1,2,...,m}，初始化$w_r?N(0,I),a_r?unif[?1,1]$，令$m=\Omega (\frac{n^6}{{\lambda }_0^4})$，并且设置步长$\eta =O(\frac{{\lambda }_0}{n^2})$，那么有很大的概率使得：对$k=0,1,2,...$
$$\Vert u(k)?y{\Vert }_2^2\le {\left(1?\frac{\eta {\lambda }_0}{2}\right)}^k\Vert u(0)?y{\Vert }_2^2$$
Theorem2展示了即使目标函数是非凸和非平滑的，梯度下降也会以线性的收敛速度。

Theorem 2的证明

Condition 2.1：在第$k$轮迭代中，有$\Vert u(k)?y{\Vert }_2^2\le {\left(1?\frac{\eta {\lambda }_0}{2}\right)}^k\Vert u(0)?y{\Vert }_2^2$

Corollary 2.1

Corollary 2.1：如果对$k^{\prime }=0,...,k$都有Condition 2.1成立，那么我们对每个r∈{1,2,...,m}r \in \{1,2,...,m\}r∈{ 1,2,...,m}，有：
$$\Vert w_r(k+1)?w_r(0){\Vert }_2\le \frac{4\sqrt{n}\Vert y?u(0){\Vert }_2}{\sqrt{m}{\lambda }_0}\stackrel{△}{=}{R}^{\prime }$$

证明：
KaTeX parse error: No such environment: eqnarray at position 8: \begin{?e?q?n?a?r?r?a?y?}? \lVert w_r(k+1…

如前面一样定义事件：
$$A_{ir}=\left\{?w:\Vert w?w_r(0)\Vert \le R,\mathbb{I}\left\{x_i^T{w}_r(0)\ge 0\right\}?=\mathbb{I}\left\{x_i^{T}w\ge 0\right\}\right\}.$$
其中$R=\frac{c{\lambda }_0}{n^2}$，$c$为一个小的正数，不同于梯度流(gradient flow)，梯度下降需要一个更精确的分析。为此，令Si={r∈{1,2,...,m}:I{Air=1}}S_i=\{r\in \{1,2,...,m\}:\mathbb{I}\{A_{ir}=1\}\}Si?={ r∈{ 1,2,...,m}:I{ Air?=1}}以及Si⊥={1,2,...,m}\SiS_i^\perp=\{1,2,...,m\}\backslash S_iSi⊥?={ 1,2,...,m}\Si?，接下来的引理将会确定$|S_i^{\perp }|$的范围。

Lemma 2.1

Lemma 2.1：有很大的概率， $?C>0$，s.t. ${\sum }_{i=1}^n|S_i^{\perp }|\le CmnR$。

证明：

对一个固定的i∈{1,2,...,n}i \in \{1,2,...,n\}i∈{ 1,2,...,n}和r∈{1,2,...,m}r\in\{1,2,...,m\}r∈{ 1,2,...,m}，根据前面的证明知 ：$P(A_{ir}\le \frac{2R}{\sqrt{2\pi }})$，因此可以得到
$$\mathbb{E}\left[\left|S_i^{\perp }\right|\right]=\sum _{r=1}^{m}P(A_{ir})\le \frac{2mR}{\sqrt{2\pi }}$$

故有：
$$\mathbb{E}\left[\sum _{i=1}^n\left|S_i^{\perp }\right|\right]\le \frac{2mnR}{\sqrt{2\pi }}$$
根据Markov Inequality，对一个很大的常数$C>0$，有很大的概率使得：
$$\sum _{i=1}^n\left|S_i^{\perp }\right|\le CmnR$$
得证。

此时有：
$$P(\sum _{i=1}^n|S_i^{\perp }|\le CmnR)\ge 1?\frac{2}{\sqrt{2\pi }C}$$
接下来，计算两相邻迭代之间预测的差
KaTeX parse error: No such environment: eqnarray at position 8: \begin{?e?q?n?a?r?r?a?y?}? u_i(k+1)-u_i(k…
我们将RHS分成两部分，如下：
$$\begin{gathered} I_1^i\stackrel{△}{=}\frac{1}{\sqrt{m}}\sum _{r\in S_i}{a}_r\left(\sigma \left({\left(w_r(k)?\eta \frac{?L(W(k))}{?w_r(k)}\right)}^T{x}_i\right)?\sigma \left(w_r(k{)}^T{x}_i\right)\right) \\ {I}_2^i\stackrel{△}{=}\frac{1}{\sqrt{m}}\sum _{r\in S_i^{\perp }}{a}_r\left(\sigma \left({\left(w_r(k)?\eta \frac{?L(W(k))}{?w_r(k)}\right)}^T{x}_i\right)?\sigma \left(w_r(k{)}^T{x}_i\right)\right) \end{gathered}$$
由于ReLU是1-Lipschitz函数，并且$|a_r|\le 1$，所以我们有：
∣I2i∣≤ηm∑r∈Si⊥∣(?L(W(k))?wr(k))Txi∣≤η∣Si⊥∣mmax?r∈{1,2,...,m}∥?L(W(k))?wr(k)∥2≤η∣Si⊥∣n∥u(k)?y∥2m|I_2^i|\le\frac{\eta}{\sqrt m}\sum_{r\in S_i^\perp}\left|\left(\frac{\partial L(W(k))}{\partial w_r(k)}\right)^Tx_i\right|\le\frac{\eta|S_i^\perp|}{\sqrt m}\max_{r\in\{1,2,...,m\}}\left\lVert\frac{\partial L(W(k))}{\partial w_r(k)}\right\rVert_2\le\frac{\eta|S_i^\perp|\sqrt n \lVert u(k)-y\rVert_2}{m} ∣I2i?∣≤m ?η?r∈Si⊥?∑?∣∣∣∣∣?(?wr?(k)?L(W(k))?)Txi?∣∣∣∣∣?≤m ?η∣Si⊥?∣?r∈{ 1,2,...,m}max?∥∥∥∥??wr?(k)?L(W(k))?∥∥∥∥?2?≤mη∣Si⊥?∣n ?∥u(k)?y∥2??
对于$I_1^i$，根据Corollary 4.1，我们知道?r∈{1,2,...,m}\forall r \in \{1,2,...,m\}?r∈{ 1,2,...,m}有$\Vert w_r(k+1)?w_r(0)\Vert \le R^{\prime }$以及$\Vert w_r(k)?w_r(0)\Vert \le R^{\prime }$，另一方面：
KaTeX parse error: No such environment: eqnarray at position 8: \begin{?e?q?n?a?r?r?a?y?}? I_1^i&=&-\frac…
其中Hij(k)=1m∑r=1mxiTxjI{wr(k)Txi≥0,wr(k)Txj≥0}H_{ij}(k)=\frac{1}{m}\sum_{r=1}^mx_i^Tx_j\mathbb{I}\{w_r(k)^Tx_i\ge0,w_r(k)^Tx_j\ge0\}Hij?(k)=m1?∑r=1m?xiT?xj?I{ wr?(k)Txi?≥0,wr?(k)Txj?≥0}，是前面定义的Gram矩阵的离散形式，另外

Hij⊥(k)=1m∑r∈SiperpxiTxjI{wr(k)Txi≥0,wr(k)Txj≥0}H_{ij}^\perp(k)=\frac{1}{m}\sum_{r\in S_i^perp}x_iTx_j\mathbb{I}\{w_r(k)^Tx_i\ge0,w_r(k)^Tx_j\ge0\}Hij⊥?(k)=m1?∑r∈Sip?erp?xi?Txj?I{ wr?(k)Txi?≥0,wr?(k)Txj?≥0}。根据Lemma 2，有很大的概率使得：
$${\Vert H^{\perp }(k)\Vert }_2\le \sum _{(i,j)=(1,1)}^{(n,n)}\left|H_{ij}^{\perp }(k)\right|\le \frac{n{\sum }_{i=1}^n|S_i^{\perp }|}{m}\le \frac{C{n}^{2}mR}{m}=n^{2}CR$$
另外，类似于梯度的经典分析，可以得到：
$$\Vert u(k+1)?u(k){\Vert }_2^2\le {\eta }^2\sum _{i=1}^n\frac{1}{m}{\left(\sum _{r=1}^m\Vert \frac{?L(W(k))}{?w_r(k)}\Vert \right)}^2\le {\eta }^2{n}^2\Vert y?u(k){\Vert }_2^2$$
基于前面的这些估计，做出对Theorem 2的证明如下：
KaTeX parse error: No such environment: eqnarray at position 8: \begin{?e?q?n?a?r?r?a?y?}? \lVert y-u(k+1…
其中$R=\frac{c{\lambda }_0}{n^2}$，显然可以调节$c，C$，让上式的有足够大的概率成立。

那么，就证明了Theorem 2。