投影梯度下降（Projected gradient descen

作者: 十年磨剑_莫回首 | 来源:发表于2020-03-16 04:29 被阅读0次

投影梯度下降（Projected gradient descen
神经网络优化2
机器学习笔记（六）—— 梯度下降
机器学习系列（十四）——梯度下降法Gradient Descen
数据挖掘面试总结
随机梯度下降法与批量梯度下降法的区别
梯度下降算法
机器学习系列（十六）——随机梯度下降Stochastic Gra
[机器学习入门] 李宏毅机器学习笔记-3 （Gradient D
全梯度下降算法从零实现，基于Numpy

对于上面有条件的优化问题，可以采用这样的的一种思路：

采用梯度下降的思路，更新 $x^t$ ，再将这样的更新值向定义域C 作投影，以此来获得该优化问题在一定条件下的优化。

$投影定理：\\ 假设空间集合C是封闭的凸集合，那么当且仅当：\\ (x-x_C)^T(z-x_C) \leq0, \quad \forall z \in C \\ 那么x_C是x在集合C上的投影该式子可以进一步拓展：\\ 将x换成x^t-\eta^t▽f(x^t), z换成x^*\\ 那么我们有：\\ (x^t-x_c-\eta^t▽f(x^t))(x^*-x_c)\leq 0 \\ \implies (g_c(x^t)-▽f(x^t))(x^*-x_c) \leq0\\ \implies ▽f(x^t)^T(x_c-x^*) \leq g_c(x^t)(x_c-x^*) \\ 其中，g_c(x)=L(x-x^*), \eta^t= \frac{1}{L}$

梯度方向

$-▽f(x^t)^T(x^{t+1}-x^t) \geq 0$

$x^{t+1}-x^t和最速梯度下降方向是正相关。$

投影的非拓展性

$\forall x,z \quad ||P_C(x)-P_C(z)|_2 \leq ||x-z||_2 总是成立的$

收敛性

$对于无约束条件的优化问题，我们知道：\\ ||x^{t}-x^||_2 \leq( \frac{K-1}{K+1})||x^t-x^||_2$

投影梯度下降的收敛性：

$||x^{t+1}-x^*||_2=||P_C(x^t-\eta^t▽f(x^t))-x^*||_2\\ \leq||x^t-\eta^t▽f(x^t)-x^*||_2 \leq (\frac{K-1}{K+1})||x^t-x^*||_2 \\ 部分证明在梯度下降中，此处些许省略。$

对于u-strongly convex 和 L-smooth 的函数f(x)

如果步长 $\eta^t$ 取为 $\frac{1}{L}$ ，那么我们有这样的式子：

$||x^t-x^*||_2^2 \leq (1- \frac{\mu}{L})^t||x^0-x^*||_2^2$

$下面证明：\\ x^+:=P_C(x-\frac{1}{L}▽f(x))，g_C(x):=L(x-x^+) \quad 在上面已经证明了：\\ ▽f(x)^T(x+-x^*) \leq g_C(x)^T(x^+-x^*),以下证明将用到该式。\\ 证明：\\ 0 \leq f(x^+)-f(x^*)=f(x^+)-f(x)+f(x)-f(x^*)\\ \implies 0 \leq ▽f(x)^T(x^+-x)+ \frac{L}{2}||x^+-x||^2_2+▽f(x)^T(x-x^*)- \frac{\mu}{2}||x-x^*||^2_2 (前面是L-smooth性质，后面是u-convex性质)\\ \implies 0 \leq ▽f(x)^T(x^+-x^*)+ \frac{1}{2L}||g_C(x)||^2_2+▽f(x)^T(x-x^*)- \frac{\mu}{2}||x-x^*||^2_2\quad \\ 由于： ▽f(x)^T(x^+-x^*) \leq g_C(x)^T(x^+-x^*)=g_C(x)^T(x-x^*)- \frac{1}{L}||x-x^*||^2_2 \\ \implies 0 \leq L(x-x^+)(x-x^*)- \frac{1}{L}||g_C(x)||^2_2+ \frac{1}{2L}||g_C(x)||_2^2- \frac{\mu}{2}||x-x^*||^2_2 \\ \implies 0 \leq L(x-x^+)(x-x^*)- \frac{1}{2L}||L(x-x^*-(x^+-x^*))||^2_2- \frac{\mu}{2}||x-x^*||^2_2 \\ 展开合并最后可以得到：\\ (L-u)||x-x^*||_2^2 \geq L||x^+-x^*||_2^2\\ \implies ||x^+-x^*||_2^2 \leq (1- \frac{\mu}{L})||x-x^*||_2^2 \\ 直接循环推导，可以得到最后的收敛式子$

总结

对于投影梯度递降法来说：

1）如果处理的是一个convex&smooth 问题，那们一般设置步长是 $\eta^t=\eta \equiv \frac{1}{L}$

收敛速率是 $O(\frac{1}{t})$ ，循环的复杂度是 $O(\frac{1}{\varepsilon})，其中\varepsilon 为误差精度要求$

2）对于strongly-convex&smooth 问题，其步长依旧是 $\eta^t=\eta \equiv \frac{1}{L}$ ，收敛速率是 $O((1- \frac{1}{K})^t)$ ，循环复杂度是 $O(K*log \frac{1}{\varepsilon})，其中K为条件数$

投影梯度下降（Projected gradient descen
对于上面有条件的优化问题，可以采用这样的的一种思路：采用梯度下降的思路，更新，再将这样的更新值向定义域C 作投...
神经网络优化2
梯度下降梯度下降法批梯度下降法（Batch Gradient Descent，BGD）是最常用的梯度下降形式，...
机器学习笔记（六）—— 梯度下降
梯度下降批量梯度下降（Batch Gradient Descent，BGD）批量梯度下降法是最原始的形式，它是...
机器学习系列（十四）——梯度下降法Gradient Descen
梯度下降法梯度下降法本身不是一个机器学习算法，而是一种基于搜索的最优化方法，它是人工智能领域非常重要的一种方法。...
数据挖掘面试总结
随机梯度下降三种梯度下降： Gradient Descent(GD)、SGD(stochastic gradie...
随机梯度下降法与批量梯度下降法的区别
批量梯度下降法（batch gradient decent）就是我们平时所说的梯度下降，也就是梯度下降过程中，每次...
梯度下降算法
1. 三种梯度下降算法： Batch Gradient Descent：全部样本梯度下降一次，批梯度下降每次更新...
机器学习系列（十六）——随机梯度下降Stochastic Gra
随机梯度下降法Stochastic Gradient Descent 在之前的梯度下降法解决线性回归问题中，梯度向...
[机器学习入门] 李宏毅机器学习笔记-3 （Gradient D
[机器学习入门] 李宏毅机器学习笔记-3 （Gradient Descent ；梯度下降） Review 梯度下降...
全梯度下降算法从零实现，基于Numpy
批量梯度下降法BGD Github 批量梯度下降法（Batch Gradient Descent，简称BGD）是梯...