次梯度方法
-
次梯度方法不一定会使损失函数下降
与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}\)时取得最小值。