研究深度神经网络优化稳定性，证明在一定条件下梯度下降和随机梯度下降方法能有效控制损失函数

假设$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}$

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