梯度下降法 学习笔记

概述

梯度下降法用于求解多变量局部最小值点问题，常用于机器学习。

过程

如果一个函数 $F\left(\mathbf x\right)$ 在邻域内有定义且可导，那么 $F\left(\mathbf x\right)$ 在 $\mathbf a$ 点沿着在 $F$ 在 $a$ 点的负梯度（Gradient）方向 $-\nabla F\left(a\right)$ 下降最快。

$$\mathbf a_{n + 1} = \mathbf a_n - \gamma_n\nabla F\left(\mathbf a_n\right)$$

对于一个足够小的学习率（Learning rate） $\gamma_n \in \mathbb R^{+}$，有 $F\left(\mathbf a_{n + 1}\right) \leq F\left(\mathbf a_n\right)$。我们希望它最后能收敛到局部最小值上。

我们有方法调整 $\gamma_n$，以保证在大多数情况下，它一定能收敛到一个局部最小值上。比如：

$$\gamma_n = \frac{\left\lvert\left(\mathbf x_n - \mathbf x_{n - 1}\right)^T\left(\nabla F\left(\mathbf x_n\right) - \nabla F\left(\mathbf x_{n - 1}\right)\right)\right\rvert}{\left\Vert \nabla F\left(\mathbf x_n\right) - \nabla F\left(\mathbf x_{n - 1}\right)\right\Vert^2}$$

更快的下降

使用过小的 $\gamma$ 会下降太慢，过大的 $\gamma$ 可能导致会错过最低点，或者导致发散。我们实际上可以朝一个偏离最陡下降方向的方向下降，从而补偿距离，维持 $\gamma$。

考虑一个下降的方向 $\mathbf p_n$ 和一个步长 $\gamma_n$ 的转移:

$$\mathbf a_{n + 1} = \mathbf a_n - \gamma_n\mathbf p_n$$

首先我们要让函数值确实地下降，为此必须满足 $\cos \theta_n > 0$，其中 $\theta_n$ 表示 $\nabla F\left(\mathbf a_n\right)$ 与 $\mathbf p_n$ 之间的夹角。

定理 1

设 $g_l\left(W\right) = \nabla_{W_l}F\left(W\right)$，$\theta_l$ 表示 $\Delta W_l$ 和 $-g_l\left(W\right)$ 之间的夹角，如果 $F$ 是连续可导的，则有

$$\boxed{F\left(W + \Delta W\right) \leq F\left(W\right) - \sum\limits_l\left\Vert g_l\left(\mathbf a_n\right)\right\Vert_2\left\Vert\Delta W_l\right\Vert_2\left(\cos\theta_l - \max\limits_{t \in \left[0, 1\right]}\frac{\left\Vert g_l\left(W + t\Delta W\right) - g_l\left(W\right)\right\Vert_2}{\left\Vert g_l\left(W\right)\right\Vert_2}\right)}$$

证明：

由微积分基本定理（Fundamental theorem of calculus）：

$$F\left(W + \Delta W\right) = F\left(W\right) + \sum\limits_l\left(g_l\left(W\right)^T\Delta W_l + \int_0^1\left(g_l\left(W + t\Delta W\right) - g_l\left(W\right)\right)^T\Delta W_l\,dt\right)$$

用点积的余弦公式算右边的第一项，然后用积分估计引理估计第二项，就得到上面的公式。

推论

$$\boxed{F\left(\mathbf a_{n + 1}\right) \leq F\left(\mathbf a_n\right) - \gamma_n\left\Vert \nabla F\left(\mathbf a_n\right)\right\Vert_2\left\Vert\mathbf p_n\right\Vert_2\left(\cos\theta_n - \max\limits_{t \in \left[0, 1\right]}\frac{\left\Vert\nabla F\left(\mathbf a_n - t\gamma_n\mathbf p_n\right) - \nabla F\left(\mathbf a_n\right)\right\Vert_2}{\left\Vert\nabla F\left(\mathbf a_n\right)\right\Vert_2}\right)}$$

实际上，$\max\limits_{t \in \left[0, 1\right]}\frac{\left\Vert\nabla F\left(\mathbf a_n - t\gamma_n\mathbf p_n\right) - \nabla F\left(\mathbf a_n\right)\right\Vert_2}{\left\Vert\nabla F\left(\mathbf a_n\right)\right\Vert_2}$ 描述的是梯度沿下降方向变化的速度。

问题是，计算 $\max\limits_{t \in \left[0, 1\right]}\frac{\left\Vert\nabla F\left(\mathbf a_n - t\gamma_n\mathbf p_n\right) - \nabla F\left(\mathbf a_n\right)\right\Vert_2}{\left\Vert\nabla F\left(\mathbf a_n\right)\right\Vert_2}$ 需要计算 $\nabla F\left(\mathbf a_n - t\gamma_n\mathbf p_n\right)$，额外的梯度计算开销很大。

解决此问题的一些方法是：

• 如果 $F$ 二阶可导，使用 $\nabla^2 F$ 去估计 $\left\Vert\nabla F\left(\mathbf a_n - t\gamma_n\mathbf p_n\right) - \nabla F\left(\mathbf a_n\right)\right\Vert_2 \approx \left\Vert t\gamma_n\nabla^2F\left(\mathbf a_n\right)\mathbf p_n\right\Vert$。使用上述推论确定最好的 $\mathbf p_n$ 和 $\gamma_n$。
• 如果 $F$ 是 Lipschitz 光滑的，使用它的 Lipschitz 常数 $L$ 去估计 $\left\Vert\nabla F\left(\mathbf a_n - t\gamma_n\mathbf p_n\right) - \nabla F\left(\mathbf a_n\right)\right\Vert_2 \leq Lt\gamma_n\left\Vert\mathbf p_n\right\Vert$，然后使用上述推论确定最好的 $\mathbf p_n$ 和 $\gamma_n$

参考

https://en.wikipedia.org/wiki/Gradient_Descent
https://arxiv.org/pdf/2002.03432

---

• Category: AI
• Last update: 2024-07-27 15:14:16^UTC+8
• Tags: No tags