无约束凸优化问题求解——Gradient Descent(三)

介绍

梯度下降(Gradient Descent)在深度学习中，被作为最基本的优化神经网络参数的算法。对于一个学过微积分的人来说，梯度下降的一个直观解释是：沿着目标函数下降最快的方向(梯度的负方向)走一小步。

重复进行：

1. 确定下降方向： d_k = -\nabla f(x_k)

2. 直线搜索步长： 0} f(x_k + \alpha d_k )">\alpha_k = \arg\min_{\alpha > 0} f(x_k + \alpha d_k )

3. 修改： x_{k+1}= x_k - \alpha_k d_k

这里，我想回答以下几个问题：对于无约束的凸优化问题，即目标函数是凸函数，

梯度下降一定可以找到全局最小值吗？梯度下降为什么能找到全局最小值？梯度下降的收敛速度如何？凸函数

(阅读过我的专栏里凸优化问题介绍的，可以跳过这部分！！!)

凸函数可以说是目标函数中最容易优化的一类函数。首先给出凸函数的定义：

对于定义域 dom(f) 是凸集的函数 f: \mathbb{R^n} \mapsto \mathbb{R}， f(x) 是凸函数 \Leftrightarrow f(\alpha x+(1-\alpha)y) \geq \alpha f(x) + (1-\alpha) f(y) \quad \forall x, y \in dom(f), \alpha \in [0, 1] \\

(a)图：凸函数的另一种等价定义的解释：弦位于函数的上方。(b)图：凸函数不可能有局部极小值的直观解释。

凸函数没有局部最优解。

\mathit{Proof:}

假设 x^* 是凸函数 f 的全局最优解；如果 x^* 是局部最优解，那么必存在 \bar x \ne x^* 使得 f(\bar x) \leq f(x^*) 。根据凸函数的定义：

\begin{split} f(\alpha \bar x+ (1- \alpha) x^*) &\leq \alpha f(\bar x) + (1-\alpha) f(x^*) \\ &\leq \alpha f(x^*) + (1 - \alpha) f(x^*) \\ & \leq f(x^*) \end{split}

也就是说，位于 \bar x 和 x^* 之间的线段上的函数值都小于 f(x^*) ，这与 x^* 是局部最优解矛盾，因此 x^* 只能是全局最优解。迭代算法

迭代算法旨在产生一个序列 \{x_k\} 满足 f(x_{k+1}) \leq f(x_k) 。对于凸函数，如果我们能够找到这么一个序列的话，因为凸函数没有局部最优解，那么我们一定可以找到全局最优解。下面的问题就是如何构造这么一个序列 \{x_k\} 。

首先给出可微凸函数的另一种等价定义。

对于定义域 dom(f) 是凸集的函数 f: \mathbb{R^n} \mapsto \mathbb{R}，且 f(x) 一阶可导。 f(x) 是凸函数 \Leftrightarrow

f(y) \geq f(x) + \nabla f(x)^T (y-x) \quad \forall x, y \in dom(f) \\

可导凸函数的一阶Lower Bound：任意一点的切线位于函数曲线的下方。

令 y = x_{k+1}, x = x_{k} ，如果 \nabla f(x_k) (x_{k+1} - x_k) \ge 0 ，我们可以发现

f(x_{k+1}) - f(x_k) \ge \nabla f(x_k)^T (x_{k+1} - x_k) \ge 0 \\

所以迭代序列 \{x_k\} 下降的必要条件是 \nabla f(x_k)^T (x_{k+1} - x_k) \leq 0 。

梯度下降

首先，我们来验证梯度下降产生的序列 \{x_k\} 满足迭代序列下降的要求。

\nabla f(x_k) ^T (x_{k+1} - x_k) = - \alpha_k \nabla f(x_k)^T \nabla f(x_k) \leq 0 \\

接下来，我们来回答梯度下降是如何找到全局最优解，以及收敛速率问题。

1）定界

这里，我们假设函数 f(x) 是强凸的，强凸函数 f(x) 有如下Quadratic Bound：

m > 0">\forall x, y \in dom(f), \exists M > m > 0 ，

\begin{equation} f(y) \geq f(x) + \nabla f(x)^T(y-x) + \frac{m}{2} ||y-x||^2 \quad\quad\quad(1) \\ \end{equation} f(y) \leq f(x) + \nabla f(x)^T(y-x) + \frac{M}{2} ||y-x||^2 \quad\quad\quad (2) \\

令 x^* = \arg\min_x{f(x)}, \, p^* = f(x^*) ，则 \forall x \in dom(f) ，对不等式(1)两边同时关于 y 求最大值（注意不等式右边是关于 y 的二次函数）：

p^* \geq f(x) - \frac{1}{2m}||\nabla f(x)||^2 \\

整理后：

f(x) \leq p^* + \frac{1}{2m}||\nabla f(x)||^2 \\

则对任意一个迭代中间值 f(x_k) ，其与最优值 p^* 的误差不超过 ||\nabla f(x_k) ||^2 。

2）收敛性

令 g(\alpha) = f(x_k - \alpha \nabla f(x_k)) ，将 y = x_k - \alpha \nabla f(x_k) 代入到上面的不等式(2)中，有：

g(\alpha) \leq f(x_k) - \alpha||\nabla f(x_k)||^2 + \frac{M{\alpha}^2}{2} ||\nabla f(x_k)||^2 \\

在梯度下降算法的第二步进行直线搜索的时候，我们会对上式关于 \alpha 求最小（注意不等式的右边是关于 \alpha 的二次函数），得到 \alpha 的最优解 \alpha^* 。

f(x_{k+1}) = g(\alpha^*) \leq f(x_k) - \frac{1}{2M} ||\nabla f(x)||^2 \\

上式两边同时减去 p^* 有：

f(x_{k+1}) - p^* \leq f(x_k) - p^* - \frac{1}{2M}||\nabla f(x_k)||^2 \\

结合1）中的结论： ||\nabla f(x) ||^2 \geq 2m(f(x_k) - p*) ，有：

f(x_{k+1}) - p^* \leq (1-\frac{m}{M})(f(x_k) - p^*) \\

注意到上式是对 \forall k \geq 0 成立，从 k=0, 1,\cdots, n 应用上式，有：

\begin{split} f(x_n) - p^* &\leq c (f(x_{n-1}) - p^*) \\ &\leq c^2(f(x_{n-2}) - p^*) \\ & \leq \cdots \\ &\leq c^n(f(x_0) - p^*) \end{split}

其中， c= 1 - \frac{m}{M} < 1 于是，当 n \to \infty 时， f(x_n) \to p^* 。因此，梯度下降是一个压缩算子。

3）收敛速度

给定精度 \epsilon ，代入到上面的不等式，可以解出迭代次数 n :

n \leq \frac{\log\Big((f(x_0)-p^*)/\epsilon \Big)}{\log(1/c)} \\

当 \frac{M}{m} 比较大的时候直线搜索方法,无约束优化方法,约束优化方法， \log(1/c) = -\log (1- m/M) \approx m/M ，因此

n \sim O(\frac{M}{m}) \\

因此梯度下降是线性收敛速度。总结

至此我们回答了刚开始提出的3个问题：

1. 梯度下降一定可以找到全局最小值吗？

2. 梯度下降为什么能找到全局最小值？

梯度下降一定可以找到无约束的凸函数的全局最小值，因为凸函数没有局部最小值，且迭代算子(为压缩算子)保证其可以收敛到最优解。

3. 梯度下降的收敛速度如何？

关于\frac{M}{m} (由函数本身性质决定)的线性收敛。

阅读本系列的其他文章

凸优化系列(一)凸优化问题介绍(二)无约束凸优化问题求解——Gradient Descent(三)无约束凸优化问题求解——Newton Method(四)带约束凸优化问题最优解的存在条件——KKT条件(五)带等式约束凸优化问题的求解——Newton Method(六)带不等式约束凸优化问题的求解——内点法(七)

（编辑：温州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!