最优化算法-6-梯度下降法和Subgradient方式的收敛速度

licemiao

本系列文章是对Youtube 《Optimization Algorithms》课程的学习笔记和总结
课程地址：https://www.youtube.com/playlist?list=PLXsmhnDvpjORzPelSDs0LSDrfJcqyLlZc
文章封面由DALL.E-2创作生成

优化问题的收敛速度不仅和采用的优化方式有关，和方针函数本身的性质也有很大关系，因此本节的分析会操作上一节中介绍的smoothness和strongly convex等性质~~~
考察优化问题的收敛速度，其实就是要考察从一个初始解开始出发，需要颠末多少步，才能收敛到最优解附近

收敛到最优解附近这件事，其实也就是： ||x-x^*||_2\leq \epsilon ， \epsilon 是小量
对于凸函数来说，也等价于： ||f(x)-f(x^*)||_2\leq \epsilon

1 Subgradient法的收敛速度--对于Lipschitz持续的凸函数

由于subgradient方式凡是不需要要求方针函数可微，所以这里考察的是一般的Lipschitz持续的凸函数~~
开始推导之前，可以回顾一下Lipschitz持续和凸函数这两个性质，这意味着函数 f(x) 满足：

• 凸函数： f(y) \geq f(x) + \langle g_x, y-x \rangle
  
• Lipschitz持续： \forall x, \forall g_x\in\partial f(x),||g_x||_2\leq G ， g_x代表次梯度， G 是一个常数
  

基于上述出发点，假设采用subgradient方式进行优化，那么迭代过程为： x_{t+1}=x_t-\eta g_t,~g_t\in\partial f(x_t)
于是，可得： （这里操作了Lipschitz持续和凸函数两个性质）
||x_{t+1}-x^*||_2^2=||x_t-\eta g_t-x^*||_2^2\\ =||x_t-x^*||_2^2 + 2\eta\langle  g_t, x_t-x^* \rangle + \eta^2||g_t||_2^2\\ \leq ||x_t-x^*||_2^2 - 2\eta(f(x_t)-f(x^*)) + \eta^2G^2
进一步对上式移项，可得：
(f(x_t)-f(x^*)) \leq \frac{1}{2\eta}\left(||x_t-x^*||_2^2 - ||x_{t+1}-x^*||_2^2\right)  + \frac{\eta}{2}2G^2
由于上式对于任意 t 成立，所以按照上式，将 t=1 到 t=T 的所有不等式相加： \frac{1}{T}\sum_{t=1}^T(f(x_t)-f(x^*)) \leq \frac{1}{2\eta}\frac{1}{T}\sum_{t=1}^T\left(||x_1-x^*||_2^2 - ||x_{T}-x^*||_2^2\right)  + \frac{\eta}{2}2G^2 \\ \leq \frac{1}{2\eta}\frac{1}{T}\sum_{t=1}^T||x_1-x^*||_2^2  + \frac{\eta}{2}2G^2
再进一步按照凸函数的性质，可得：
f(\frac{1}{T}\sum_{t=1}^T x_t)-f(x^*) \leq \frac{1}{T}\sum_{t=1}^T(f(x_t)-f(x^*)) \leq \frac{1}{2\eta T} R^2 + \frac{\eta}{2}G^2
此中，假设初始解在最优解的必然范围内，即 ||x_1-x^*||_2^2 \leq R^2
拔取最优的 \eta ，即 \eta=\frac{1}{\sqrt{T}} ，上面公式右侧等于 \frac{1}{2\sqrt{T}} (R^2 + G^2) ，最终得到的不等式如下：
f(\frac{1}{T}\sum_{t=1}^T x_t)-f(x^*) \leq \frac{1}{2\sqrt{T}} (R^2 + G^2)
结论：

• T 轮迭代过后， \epsilon \propto \frac{1}{\sqrt{T}} ，即优化误差正比于 \frac{1}{\sqrt{T}}
  
• 换句话说，如果但愿优化误差为 \epsilon ，那么需要迭代的步数也正比于 \frac{1}{\epsilon^2}
  
• 迭代步长 \eta 不能随便选，这里选择了 \eta=\frac{1}{\sqrt{T}} ，也就是随着迭代步数增加，步长变小。如果 \eta 选择为一个固定长度，那么按照上述不等式，很可能最终收敛不了。
  

<hr/>2 梯度下降法的收敛速度--对于 \beta -smooth凸函数

开始推导之前，回顾一下 \beta -smooth这个性质，这意味着函数 f(x) 满足如下的等价性质：

• ||\nabla f(x)-\nabla f(y)||_2\leq \beta ||x-y||_2
  
• f(y)\leq f(x) + \langle \nabla f(x), y-x\rangle + \frac{\beta}{2} ||x-y||^2_2
  
• \nabla^2 f(x) \leq \beta I
  

采用梯度下降法进行优化，意味着迭代过程为： x_{t+1} = x_t - \frac{1}{\beta} \nabla f(x_t),~\eta=\frac{1}{\beta}

注意，迭代步长的拔取是本身定义的，这里选择得斗劲巧妙

按照 \beta -smooth 函数的性质，并把x_{t+1} 带入，可以得到：
f(x_{t+1})\leq f(x_{t}) + \langle \nabla f(x_t), x_{t+1}-x_t\rangle + \frac{\beta}{2} ||x_{t+1}-x_{t}||^2_2=f(x_{t})-\frac{1}{2\beta}||\nabla f(x_t)||_2^2 \\ \leq f(x_{t})-\frac{\eta}{2}||\nabla f(x_t)||_2^2
注意，上述式子在 \eta \leq \frac{1}{\beta} 的条件下成立~~~
进一步地，操作凸函数的性质，可以得到： f(x_{t+1}) \leq f(x_{t})-\frac{\eta}{2}||\nabla f(x_t)||_2^2 \\ \leq f(x^{*}) + \langle \nabla f(x_t), x_{t}-x^*\rangle -\frac{\eta}{2}||\nabla f(x_t)||_2^2\\ = f(x^{*}) + \frac{1}{2\eta}\left( ||x_t-x^*||_2^2 - ||x_t-x^*-\eta\nabla f(x_t)||_2^2 \right)\\ = f(x^{*}) + \frac{1}{2\eta}\left( ||x_t-x^*||_2^2 - ||x_{t+1}-x^*||_2^2 \right)
由于上式对于任意 t 成立，所以按照上式，将 t=1 到 t=T 的所有不等式相加：  f(\frac{1}{T}\sum_{t=1}^T x_t)-f(x^*) \leq \frac{1}{T}\sum_{t=1}^T(f(x_t)-f(x^*)) \leq \frac{1}{T}\frac{1}{2\eta}\left( ||x_1-x^*||_2^2 - ||x_{T}-x^*||_2^2 \right)\\ \leq \frac{1}{T}\frac{1}{2\eta}||x_1-x^*||_2^2 = \frac{1}{T}\frac{\beta}{2} R^2
此中，假设初始解在最优解的必然范围内，即 ||x_1-x^*||_2^2 \leq R^2
最终得到的不等式如下：
f(\frac{1}{T}\sum_{t=1}^T x_t) - f(x^*) \leq \frac{1}{T}\frac{\beta}{2} R^2
结论：

• T 轮迭代过后， \epsilon \propto \frac{1}{T} ，即优化误差正比于 \frac{1}{T}
  
• 换句话说，如果但愿优化误差为 \epsilon ，那么需要迭代的步数也正比于 \frac{1}{\epsilon}
  
• 梯度下降法的迭代步长具有self-tunning的性质，因为靠近最优解的时候， \nabla f(x) 会自动趋于0。因此，步长 \eta 的拔取只需要满足： \eta \leq \frac{1}{\beta}
  

<hr/>3 梯度下降法的收敛速度--对于 \beta -smooth且 \alpha -strongly convex 函数

这里的证明斗劲复杂，就不再赘述~~下面直接给结论：
最终的不等式为：
||x_{t+1}-x^*||_2 \leq \left(\frac{\beta/\alpha-1}{\beta/\alpha+1}\right)^t ||x_{1}-x^*||_2
此中，可以记 \kappa=\beta/\alpha 为condition number
结论：

• T 轮迭代过后， \epsilon \propto \left(\frac{\kappa-1}{\kappa+1}\right)^T ，即优化误差正比于 \left(\frac{\kappa-1}{\kappa+1}\right)^T
  
• 换句话说，如果但愿优化误差为 \epsilon ，那么需要迭代的步数也正比于 \kappa\log(1/\epsilon)
  

关于 \alpha 、 \beta 和 \kappa 取值的一些讨论：

• \beta-smooth意味着，可以找到一个二次函数约束  f(x)  的上界，\beta 越小，说明这个作为上界的二次函数越平滑，因此使得 f(x) 也越平滑
  
• \alpha-strongly convex意味着，可以找到一个二次函数约束  f(x)  的下界，\alpha 越大，说明 f(x)  爬升得越快，凸性越强
  
• 条件数 \kappa 是 \beta 和 \alpha 的比值，我们但愿的是， \alpha 和  \beta  越接近越好，使得 \kappa  接近于 1，这样优化误差可以在 T 轮后收敛到0
  
• 如果  \beta  很大，\alpha 很小，那么 \kappa 会很大，这会使得优化误差变大
  

关于Hessian矩阵条件数的讨论：

• 对于 \beta -smooth且 \alpha -strongly convex 函数来说，它的Hessian矩阵满足： \alpha I \leq \nabla^2 f(x) \leq \beta I
  
• 对于一个一般的方阵来说，它满足性质： \lambda_{min} I \leq M \leq \lambda_{max} I
  
• Hessian矩阵的条件数定义为： \kappa=\frac{\lambda_{max}}{\lambda_{min}}
  
• 按照上述阐述，我们很容易发现，这里定义的条件数其实就是 f(x) 的Hessian矩阵的条件数
  
• 因此，我们可以得到如下结论：
  

方针函数的Hessian矩阵的条件数越小，越接近于1，那么优化的速度越快，越容易收敛。反之，可能会使得优化速度变慢，优化的误差变大。
<hr/>4 Oracle lower bound

oracle lower bound 说的是优化算法最快的收敛速度，具体来说就是：
假设对于一个优化问题 \min f(x) ，我们只能用 f(x) 和 \nabla f(x) ，也就是只能用函数值和函数梯度，不能用高阶导数信息，最少需要迭代多少轮才可以使得优化误差收敛到 \epsilon 内？
以下是一些结论：

• 对于Lipschitz持续的凸函数来说，最少需要 O(\frac{1}{T}) 次迭代
  
• 对于 \beta -smooth的凸函数来说，最少需要 O(\frac{1}{T^2}) 次迭代
  
• 对于 \beta -smooth且 \alpha -strongly convex函数来说，最少需要 O((\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1})^T) 次迭代
  

因此，对于后面两种函数来说，梯度下降法的收敛速度显然没有达到最优的状态，因此存在改良的空间~~~