次梯度与次微分

为了看懂为什么在logistic regression 里面加上正则化可以约束待估计的参数的稀疏性，需要对凸优化方法里面的部分知识，现在记录一下这方面的内容

既然是凸优化，首先就要有一个凸函数，看下面的定义

设是一个凸函数，并且 是一个凸集。如果f是可微的，那么可以得到下面的表达式：

其中，,表示在的微分，可以看出，不等式右边其实就是普通的一阶微分的近似表示，那么肯定会有误差，如果误差等于0，那么取到等号

对不可微的情况下，我们同样可以构造一个表达式来近似真实情况，见下式子：

其中，向量 就叫做次梯度

对于一个给定的点，可能不止一个这样的次梯度存在，而是一个次梯度的集合，这样的集合就叫做次微分，表示为：

注意，如果微分存在的情况下，这样的次微分集合只包含一个元素，就是该点的梯度值，也就是蜕化为正常的梯度方式，所以说这是梯度的一种扩展

对次梯度表达式做一个变形可以得到

这个变形可以用来快速估计一些简单函数的次微分，比如一个一维函数在处

由于

自此可以看出，有界，因此有

这里写下一些次微分的一些性质

• 在x附近是非空并且有限的，如果函数是凸函数
• 是紧凸集（closed convex set）
• 等价于是可微的并且
• 尺度变换性
• 可加性

假定我们有一个凸函数：我们的目标是求：

如果函数是可微的，那么最值就是求函数的梯度为0的取值

如果函数不可微的，那么最值的条件就是如下的形式

我们看看不可微条件下的最值条件是怎么得来的，还是从次梯度的定义开始,令可以得到

可以看出，最小值是在次梯度向量为0的时候取得，这就提供了一种方法，在某些不可微的情况下，对凸函数可以用次梯度去代替梯度进行梯度下降学习算法

参考文章：

http://select.cs.cmu.edu/class/10725-S10/recitations/r7/Subgradients.pdf