EE364b笔记

次梯度方法

  • 次梯度方法不一定会使损失函数下降

    与line search方法不同,次梯度方法步长的schedule都是事先确定,因此不一定会导致损失函数下降,因此在证明收敛的时候用到的是\(x^{t+1}-x^*\)的范数。

  • 次梯度的证明框架

    \[\begin{align*} \Vert x^{t+1} - x^{*}\Vert^2 &= \Vert x^{t} -\alpha_t g_t -x^{*}\Vert^2\\ &=\Vert x^{t} -x^{*}\Vert^2 - 2 \alpha_t \langle g_t, x^t-x^*\rangle +\alpha^2_t\Vert g_t\Vert^2\\ &\leq \Vert x^{t} -x^{*}\Vert^2 - 2\alpha_t(f_t-f_*)+\alpha^2_t\Vert g_t\Vert^2\\ &= \Vert x^0 - x^*\Vert^2 - 2 \sum_{k=0}^t \alpha_k (f_k - f_*) +\sum_{k=0}^t \alpha_k^2 \Vert g_t\Vert^2\\ \end{align*} \]

  • 步长选择

    步长选择常用的方法有

    • 常数\(\alpha\)
    • \(\sum \alpha_k =\infty\),\(\alpha_k\to 0\),常用的如\(\frac{1}{\sqrt{k}}\)
    • \(\sum \alpha_k^2\leq\infty\),\(\sum \alpha_k = \infty\),\(a_k\to 0\),常用的如\(\frac{1}{k}\)
  • 收敛分析

    根据次梯度的证明\(f_{best}^t-f_*\leq \frac{R+\sum\alpha_k^2 G}{\sum 2\alpha_k }\)选取不同的步长,有不同的收敛结果但收敛速度都是\(\mathcal{O}(\frac{1}{\sqrt{t}})\)

    • 在常数的情况下,\(f_{best}^t\)和\(f_*\)之间有\(\frac{R}{2t\alpha}\)的误差
    • 在diminish的情况下,\(f_{best}^*\)会收敛到\(f_*\)
  • projected次梯度方法

    根据\(\Vert x^{t+1}-x^*\Vert^2 =\Vert \Pi(z^{t+1})-x^* \Vert^2\leq\Vert z^{t+1}-x^*\Vert ^2\),投影的次梯度方法不会影响收敛情况。

  • Mirror descent

    参看之前的博客

  • adaptive methods

    先看一下polyak's step,根据\(2\alpha_t f^t-f_*\leq\Vert x^{t}-x^* \Vert^2-\Vert x^{t+1}-x^*\Vert^2 +\alpha_t^2\Vert g_t\Vert^2\)得到,当\(\alpha_t=\frac{f(x^{t})-f_*}{\Vert g_t\Vert^2}\)时取得最小值。

参考资料

上一篇:惊呆了,Spring Boot居然这么耗内存!


下一篇:JoyfulPandas 第一章 预备知识