优化算法

定义#

优化算法的通项公式：

\underset{\theta}{\arg\min}\mathcal{R}(\mathcal{D};\theta)=\sum_{i=1}^n\mathcal{L}(y_i, f(x_i; \theta))+\Omega(\theta)

其目标是找到一个参数 $\theta$ 使得结构风险 $\mathcal{R}$ 最小，形式化表达为：

\theta^{(t+1)} \leftarrow \theta^{(t)} - \eta \Delta^{(t)} \underbrace{\left[ \nabla_{\theta}\mathcal{R}\left( \mathcal{D}; \theta^{(t)} \right) \right]}_{\text{gradient}}

其中 $\Delta$ 是一个更新量，表示梯度的函数。

神经网络设计的基本思想就是通过在高维空间中找到一个相对平缓的梯形图(Landscape)使得在一个较好初始点的情况下能够通过优化算法找到全局最小值。

通过一阶泰勒展开去近似

二阶优化方法指的是利用目标函数的二阶导数信息来进行参数更新的优化算法，其使用二阶泰勒展开来近似局部目标函数：

\hat{\mathcal{R}}(\theta) = \mathcal{R}(\theta^t) + \textcolor{red}{\nabla_{\theta}} \mathcal{R}(\theta^t)(\theta - \theta^t) + \frac{1}{2} (\theta - \theta^t)^T \textcolor{blue}{H} (\theta - \theta^t)

opt

海森矩阵刻画了梯形图的曲率特征，确保了优化的稳定性。其元素为：

H_{ij}=\frac{\partial}{\partial\theta_j}g_i

将其进行特征值分解可以得到：

H=Q\Lambda Q^{T}, \hspace{0.2cm} H^{-1}=Q\Lambda^{-1}Q^{T}

其中 $\Lambda$ 为对角矩阵，其对角元素为矩阵 $H$ 的特征值。若特征值全大于 0，则矩阵 $H$ 为正定矩阵，则目标函数在局部存在唯一最小值。若特征值有正有负，则存在鞍点。

将二阶泰勒展开进行求导并取 0 可得到当前 局部区域 的最优参数 $\theta^*$ ：

\nabla_{\theta}\hat{\mathcal{R}}(\theta^{*})=\nabla_\theta\mathcal{R}(\theta^{t})+\textcolor{blue}{H}(\theta^{*}-\theta^{t})=0

然后进行参数更新：

\theta^{t+1}=\theta^{t}-\textcolor{blue}{H^{-1}}\nabla_{\theta}\mathcal{R}(\theta^{t})

因为求的是局部最优参数，所以还是需要迭代更新来获得使得全局目标函数最小的参数。

该方法的收敛速度快于梯度下降，但是计算 $H^{-1}$ 需要 $O(d^2)$ 的时间以及 $O(d^3)$ 的空间， $d$ 是参数的维度。

该方法是一种拟牛顿法， $H^{-1}$ 避免高效开销。

给定一个初始点 $x^{0} \in \mathcal{X}$ 以及单位阵 $H_0=I$ ，步骤为：

计算二阶牛顿的梯度方向 - $\Delta^t=-H_{t-1}\nabla f(x^{t-1})$ ；
更新初始点 - $x^t = x^{t-1}+\eta^{t}\Delta^t$ ；
计算近似值 - $H_t=H_{t-1}+\frac{zz^T}{z^Tv}-\frac{H_{t-1}vv^TH_{t-1}}{v^{T}H^{t-1}v}$

其中 $v=x^t-x^{t-1}$ ， $z=\nabla f(x^t) - \nabla f(x^{t-1})$ 。