假设$F(x;w)$是一个输出标量的深度神经网络，其中$x$是输入，$w$表示权重。假设$F$关于$w$连续可微，并且对于训练数据 { x j , y j } j = 1 m \{x_{j},y_{j}\}_{j=1}^{m} {xj​,yj​}j=1m​过参数化：即存在$w^{\ast }$使得对所有$j$满足$F(x_j;w^{\ast })=y_j$。为了研究训练神经网络时在$w^{\ast }$的局部优化动力学，我们考虑线性化神经网络$\hat{F}(x;w)=F(x;w^{\ast })+(w-w^{\ast }{)}^{\top }\nabla F(x;w^{\ast })$，其损失函数为

$$Loss(w):=\frac{1}{2m}\sum _{j=1}^m(y_j-\hat{F}(x_j;w){)}^2$$。

令$s$表示学习率，梯度下降法为$w_{i+1}=w_i-s\nabla Loss(w_i)$，而随机梯度下降法为$w_{i+1}=w_i-s(\nabla Loss(w_i)+{ϵ}_i)$，其中噪声项${ϵ}_i$满足$\mathbb{E}{ϵ}_i=0$和$\mathbb{E}{ϵ}_i{ϵ}_i^{\top }=M(w_i)/b$, $b$是mini-batch的大小。假设协方差矩阵$M$与

$\Sigma =\frac{1}{m}{\sum }_{j=1}^m\nabla F(x_j;w^{\ast })\nabla F(x_j;w^{\ast }{)}^{\top }$

在以下意义上对齐:

$$\frac{Tr(M(w)\Sigma )}{2(Loss(w){)}^{\frac{3}{2}}\Vert \Sigma {\Vert }_F^2}\ge \delta$$，

对于$\delta >0$和所有$w$成立。这里$\Vert \cdot {\Vert }_F$表示Frobenius范数。

(1) 对于梯度下降，证明如果$\Sigma$的谱范数满足

$\Vert \Sigma {\Vert }_2\le \frac{2}{s}，$则梯度下降是局部稳定的（即对所有t，Loss$(w_t)$是有界的）。（注意，这蕴含了一个依赖维度的界:$\Vert \Sigma {\Vert }_F\le \frac{2\sqrt{d}}{s}$,其中$d$是$w$的维度。)

(2) 对于随机梯度下降，如果$\mathbb{E}Loss(w_t)$对所有$t$都有界，则以独立于维度的不等式必须成立:

$\Vert \Sigma {\Vert }_F\le \frac{\sqrt{b/\delta }}{s}$。

证：

(1)梯度下降的局部稳定性

我们需要证明在使用梯度下降时，损失函数$\text{Loss}(w_t)$是有界的。

考虑梯度下降的更新规则:$w_{i+1}=w_i-s\nabla \text{Loss}(w_i)$

首先，我们计算损失函数的梯度:

$\nabla \text{Loss}(w)=\frac{1}{m}{\sum }_{j=1}^m\left(\hat{F}(x_j;w)-y_j\right)\nabla \hat{F}(x_j;w)$

由于 $\hat{F}(x;w)=F(x;w^{\ast })+(w-w^{\ast }{)}^{\top }\nabla F(x;w^{\ast })$。

我们有:$\nabla \hat{F}(x_j;w)=\nabla F(x_j;w^{\ast })$

因此:

$\nabla \text{Loss}(w)=\frac{1}{m}{\sum }_{j=1}^m\left((w-w^{\ast }{)}^{\top }\nabla F(x_j;w^{\ast })\nabla F(xj;w^{\ast }{)}^{\top }\right)$

定义矩阵(\Sigmal) 为:

$\Sigma =\frac{1}{m}{\sum }_{j=1}^m\nabla F(x_j;w^{\ast })\nabla F(x_j;w^{\ast }{)}^{\top }$

于是:

$\nabla \text{Loss}(w)=\Sigma (w-W^{\ast })$

现在考虑梯度下降的更新:

$w_{i+1}-w^{\ast }=w_j-w^{\ast }-s\nabla \text{Loss}(w_i)$$=w_i-w^{\ast }-s\Sigma (w_i-w^{\ast })$

$=(l-s\Sigma )(w_i-w^{\ast })$

取范数:

$\Vert w_{i+1}-w^{\ast }{\Vert }_2=\Vert 1-s\Sigma {\Vert }_2\Vert w_i-w^{\ast }{\Vert }_2$

由于$I-s\Sigma {|}_2\le 1$当且仅当$s\le \frac{2}{{\lambda }_{\max }(\Sigma )}$，即${\Sigma }_2\le \frac{2}{s}$，我们可以得到:

$\Vert w_i-w^{\ast }{\Vert }_2\le \Vert w_0-w^{\ast }{\Vert }_2$

这意味着$\Vert w_i-w^{\ast }{\Vert }_2$ 是有界的，因此$\text{Loss}(w_t)$也是有界的。

(2)随机梯度下降的有界性

对于随机梯度下降，我们需要证明如果$\mathbb{E}\text{Loss}(w_t)$对所有$t$都有界，则必须满足独立于维度的约束$\Vert \Sigma {\Vert }_F\le \frac{\sqrt{b/\delta }}{s}$。

考虑随机梯度下降的更新规则:

$w_{i+1}=w_i-s(\nabla \text{Loss}(w_i)+{ϵ}_i)$

其中${ϵ}_i$是噪声项，满足$\mathbb{E}[{ϵ}_i]=0$ 和 $\mathbb{E}[{ϵ}_i{ϵ}_i^{\top }]=\frac{M(w_i)}{b}$。

我们需要分析$\mathbb{E}[\text{Loss}(w_{i+1})]$。令$w_i-w^{\ast }=z_i$。则：$zi+1=z_i-s(\Sigma z_i+{ϵ}_i)=(I-s\Sigma )zi-s{ϵ}_i$

取范数的平方并取期望:

$\mathbb{E}[\Vert z_{i+1}{\Vert }_2^2]=\mathbb{E}[\Vert (l-s\Sigma )z_i-sϵ-i\_2^2]$

$=\mathbb{E}[\Vert (1-s\Sigma )z_i\_2^2]+s^2\mathbb{E}[\Vert {ϵ}_i{\Vert }_2^2]$

由于${ϵ}_i$的协方差为$\frac{M(w_i)}{b}$。我们有:

$\mathbb{E}[\Vert {ϵ}_i{\Vert }_2^2]=\text{Tr}\left(\frac{M(w_i)}{b}\right)$

并且:

$\mathbb{E}[\Vert z_{i+1}{\Vert }_2^2]=\Vert I-s\Sigma {\Vert }_2^2\mathbb{E}[\Vert z_i{\Vert }_2^2]+\frac{s^2}{b}\text{Tr}(M(w_i))$

为了确保$\mathbb{E}[\Vert z_i{\Vert }_2^2]$的有界性，我们需要:$\Vert I-s\Sigma {\Vert }_2^2\le 1$

即:

$\Vert \Sigma {\Vert }_2\le \frac{2}{s}$

并且我们需要控制噪声项:

$\frac{s^2}{b}\text{Tr}(M(w_i))\le C$

根据题目中的对齐条件:

$\frac{\text{Tr}(M(w)\Sigma )}{2(\text{Loss}(w){)}^{3/2}\Vert \Sigma {\Vert }_F^2}\ge \delta$

我们有:

$\text{Tr}(M(w)\Sigma )\ge 2\delta (\text{Loss}(w){)}^{3/2}\Sigma {\Vert }_F^2$

由于$\text{Tr}(M(w))=\text{Tr}(M(w)l)\le \Vert \Sigma {\Vert }_2\text{Tr}(M(w))$，我们有:$\text{Tr}(M(w))\le \frac{\text{Tr}(M(w)\Sigma )}{\Vert \Sigma {\Vert }_2}$

因此:

$\text{Tr}(M(w))\le \frac{2\delta (\text{Loss}(w){)}^{3/2}\Vert \Sigma {\Vert }_F^2}{\Vert \Sigma {\Vert }_2}$

为了确保$\mathbb{E}[\text{Loss}(w_t)]$有界，我们需要满足:

$\frac{s^2}{b}\cdot \frac{2\delta (\text{Loss}(w){)}^{3/2}\Vert \Sigma {\Vert }_F^2}{\Vert \Sigma {\Vert }_2}\le C$

简化并得出:

$\Vert \Sigma {\Vert }_F\le \frac{\sqrt{b/\delta }}{s}$

综上，我们得到了独立于维度的界，这证明了随机梯度下降的有界性条件。