次梯度法
次梯度算法
- 目标函数并不一定光滑、或者处处可微，这时就需要用到次梯度下降算法。
- 次梯度法可以用于目标函数，不可微
* 引言
- 是凸函数定义的另一种形式
- 不可微分，即导数不存在
- 次梯度是存在g，满足
- f可以是凸函数或者非凸函数
- 次梯度不一定唯一
* 为什么次微分
- 对于光滑的凸函数而言，我们可以直接采用梯度下降算法求解函数的极值，但是当函数不处处光滑，处处可微的时候，梯度下降就不适合应用了。因此，我们需要计算函数的次梯度。对于次梯度而言，其没有要求函数是否光滑，是否是凸函数，限定条件很少，所以适用范围更广。
2. 次梯度算法
- 与梯度下降算法类似，仅仅用次梯度代替梯度，即：
* 与梯度下降算法不同的地方在于，次梯度算法并不是下降算法，每次对于参数的更新并不能保证代价函数是呈单调递减的趋势
* 另一点与梯度下降算法不同的是：次梯度算法没有明确的步长选择方法
* 收敛分析
- 次梯度收敛到某最优值的领域
- 基本次梯度法性能差（和步长的选择有关）
* 改进
- 原始-对偶次梯度法：使用两个序列来更新
- 投影次梯度法（有约束）
* 次梯度
- 收敛性：选择合适的步长，总会收敛
- 收敛慢：需要大量的迭代
- 非单调收敛：不一定是下降方向
- 没有很好的收敛准则
* 次梯度和L1
http://wulc.me/2017/05/20/%E5%87%B8%E4%BC%98%E5%8C%96%E6%80%BB%E7%BB%93/
- 用于解决求导时某些连续不可导的函数梯度不存在的问题
- 非光滑凸函数
- 对于可微的凸函数有一阶特性，即
将g替换，g是次梯度
- 而 subgradient descent 与 gradient descent 的不同地方就是当函数不可微的时候，将 gradient descent 中更新公式中的 gradient 换成 subgradient。
* lasso-regression问题
