机器学习：梯度下降

假定给定函数： ，求解该函数的极小值时，k的取值是多少？

通常做法：对  求导，然后令导数=0，求解 k 值即为所求：

求导解法在复杂实际问题中很难计算。迭代法通过从一个初始估计出发寻找一系列近似解来解决优化问题。其基本形式如下：

其中  被称为学习效率。

假设初始化  ，为了通过迭代让  趋近最优解2， 要满足两个条件：

•  要能使  向最优解逼近。
• 当  达到最优解时， 要等于0。当  达到最优解的时候， 要等于 ，即：

因此，我们的核心问题：寻找  满足上述两个要求。

随着迭代的不断进行， 可以使  向最优值逼近。而且，当  离最优值越近时， 的绝对值就越来越小。当达到最优解时，。

学习速率的取值问题：

• 当  取值较大时，即梯度下降迭代的步长较大，梯度下降迭代过程较快。可以快速迭代到最优解附近，但是可能一直在最优解附近徘徊，无法找出最优解。
• 当  取值较小时，即梯度下降迭代的步长较小，梯度下降迭代过程较慢。

梯度优化：方向+步长

可微函数的梯度  ： 在  处， 表示为是  的偏导数的向量，即：

梯度下降是一种迭代算法：

• 从初始值  开始。
• 在每次迭代中，我们沿着当前点梯度的负方向迈出下一步：

0)" src="https://latex.codecogs.com/gif.latex?w%5E%7Bt+1%7D%3Dw%5Et-%5Ceta%20%5Cbigtriangledown%20f%28w%5E%7B%28t%29%7D%29%28%5Ceta%20%3E0%29" />

其中， 为学习率。直观地说，该算法在梯度点的相反方向上迈出了一小步，从而降低了函数的值。在  次迭代之后，算法输出最后一个向量 。

输出也可以是平均向量 。取平均值是非常有用的，特别是当我们将梯度下降推广到不可微函数和随机情况时。

【证明】，即：梯度不断下降。

由于，。

由于  0" src="https://latex.codecogs.com/gif.latex?%7C%7C%5Cbigtriangledown%20f%28w%5E%7B%28t%29%7D%29%7C%7C_2%20%3E%200" />，学习率  0" src="https://latex.codecogs.com/gif.latex?%5Ceta%20%3E%200" />，所以 ，故：

Lipschitz连续：对于在实数集的子集的函数 ，若存在常数 ，使得  ，则称函数 符合利普希茨条件。

为了分析GD算法的收敛速度，我们仅限于凸 Lipschitz 函数的情况。 是  在 条件下的最小值的点坐标。

• 假设：
• 求证： 有界

凸函数性质（1）：

证明方法（1）：

即，判断上述关系即可：

从图上可以看出，，且趋近于0时取等号。

故，

凸函数性质（2）：

" src="https://latex.codecogs.com/gif.latex?f%28w%5E%7B%28t%29%7D%29-f%28w%5E*%29%5Cleqslant%20%3Cw%5E%7B%28t%29%7D-w%5E*%2C%5Cbigtriangledown%20f%28w%5E%7B%28t%29%7D%29%3E" />

证明：将  进行泰勒展开可得：

 ，且  处为偏导最小处，即  。

 ，且  处为偏导最小处，即  。

即：

故：

因此：

" src="https://latex.codecogs.com/gif.latex?f%28w%5E%7B%28t%29%7D%29-f%28w%5E*%29%5Cleqslant%20%3Cw%5E%7B%28t%29%7D-w%5E*%2C%5Cbigtriangledown%20f%28w%5E%7B%28t%29%7D%29%3E" />

 )" src="https://latex.codecogs.com/gif.latex?f%28%5Chat%7Bw%7D%29-f%28w%5E*%29%5Cleqslant%20%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%28%20%3Cw%5E%7B%28t%29%7D-w%5E*%2C%5Cbigtriangledown%20f%28w%5E%7B%28t%29%7D%29%3E%29" />

合体证明性质（1）（2）：

)" src="https://latex.codecogs.com/gif.latex?%3D%20%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%28%20%3Cw%5E%7B%28t%29%7D-w%5E*%2C%5Cbigtriangledown%20f%28w%5E%7B%28t%29%7D%29%3E%29" />

设  是向量的任意序列。任何具有初始化  和以下形式的更新规则的算法：

0)" src="https://latex.codecogs.com/gif.latex?w%5E%7B%28t+1%29%7D%3Dw%5Et-%5Ceta%20v_t%28%5Ceta%20%3E0%29" />

满足：

leqslant frac{||w^*||^2}{2eta }+frac{eta }{2}sum_{t=1}^{T}||v_t||^2" src="https://latex.codecogs.com/gif.latex?%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5Et-w%5E*%2Cv_t%3E%5Cleqslant%20%5Cfrac%7B%7C%7Cw%5E*%7C%7C%5E2%7D%7B2%5Ceta%20%7D+%5Cfrac%7B%5Ceta%20%7D%7B2%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%7C%7Cv_t%7C%7C%5E2" />

前提（1）：

前提（2）：

=frac{1}{eta }" src="https://latex.codecogs.com/gif.latex?%3Cw%5Et-w%5E*%2Cv_t%3E%3D%5Cfrac%7B1%7D%7B%5Ceta%20%7D%3Cw%5Et-w%5E*%2C%5Ceta%20v_t%3E" />

根据一正一负抵消，可推出：

=-frac{1 }{2eta }(||w^{t+1}-w^*||^2-||w^1-w^*||^2)+frac{eta ^{2}}{2eta }sum_{t=1}^{T}||v_t||^2" src="https://latex.codecogs.com/gif.latex?%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5Et-w%5E*%2Cv_t%3E%20%3D-%5Cfrac%7B1%20%7D%7B2%5Ceta%20%7D%28%7C%7Cw%5E%7Bt+1%7D-w%5E*%7C%7C%5E2-%7C%7Cw%5E1-w%5E*%7C%7C%5E2%29+%5Cfrac%7B%5Ceta%20%5E%7B2%7D%7D%7B2%5Ceta%20%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%7C%7Cv_t%7C%7C%5E2" />

即：

leqslant frac{||w^*||^2}{2eta }+frac{eta }{2}sum_{t=1}^{T}||v_t||^2" src="https://latex.codecogs.com/gif.latex?T%28f%28%5Chat%7Bw%7D%29-f%28w%5E*%29%29%5Cleqslant%20%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5Et-w%5E*%2Cv_t%3E%5Cleqslant%20%5Cfrac%7B%7C%7Cw%5E*%7C%7C%5E2%7D%7B2%5Ceta%20%7D+%5Cfrac%7B%5Ceta%20%7D%7B2%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%7C%7Cv_t%7C%7C%5E2" />

特别的，对每个  0" src="https://latex.codecogs.com/gif.latex?B%2C%5Crho%3E%200" /> ，如果对所有的  都存在  使得  ，且对每个  且 ，都存在：

leqslant frac{Brho }{sqrt{T}}" src="https://latex.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5Et-w%5E*%2Cv_t%3E%5Cleqslant%20%5Cfrac%7BB%5Crho%20%7D%7B%5Csqrt%7BT%7D%7D" />

证明：由前面可得

leqslant frac{1}{2eta }||w^*||^2+frac{eta }{2}sum_{t=1}^{T}||v_t||^2" src="https://latex.codecogs.com/gif.latex?%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5Et-w%5E*%2Cv_t%3E%20%5Cleqslant%20%5Cfrac%7B1%7D%7B2%5Ceta%20%7D%7C%7Cw%5E*%7C%7C%5E2+%5Cfrac%7B%5Ceta%20%7D%7B2%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%7C%7Cv_t%7C%7C%5E2" />

令 

令  ，可得  得极小值，因此也是T的最小值。

且：

)" src="https://latex.codecogs.com/gif.latex?f%28%5Chat%7Bw%7D%29-f%28w%5E*%29%5Cleqslant%20%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%28%20%3Cw%5E%7B%28t%29%7D-w%5E*%2C%5Cbigtriangledown%20f%28w%5E%7B%28t%29%7D%29%3E%29" />

，当且仅当  

在允许一定误差的情况下：对任意的 0" src="https://latex.codecogs.com/gif.latex?%5Cvarepsilon%20%3E0" /> ，使得：

则必须满足：

即：，T 存在最小值。

次梯度方法是传统的梯度下降方法的拓展，用来处理不可导的凸函数。它的优势是比传统方法处理问题范围大，劣势是算法收敛速度慢。

对于光滑的凸函数而言，我们可以直接采用梯度下降算法求解函数的极值，但是当函数不处处光滑、处处可微的时候，梯度下降就不适合应用了。因此，我们需要计算函数的次梯度。对于次梯度而言，其没有要求函数是否光滑，是否是凸函数，限定条件很少，所以适用范围更广。

允许  是一个开凸集。 函数  是一个凸函数。满足下列条件的向量 ：

" src="https://latex.codecogs.com/gif.latex?%5Cforall%20u%2Cf%28u%29%5Cgeqslant%20f%28w%29+%3Cu-w%2Cv%3E" />

称为  在  处的次梯度。 在 处的次梯度集称为微分集并表示为 。 

【定义法】如果  在  处可微，那么  包含一个元素  在  处的梯度为 。例如： 。

 由于  在  处不可导，因此根据定义：

" src="https://latex.codecogs.com/gif.latex?%7Cu%7C%5Cgeqslant%20%7Cw%7C+%3Cu-w%2Cv%3E" />

 

即：0\ [-1,+1] &x=0 \ -1&x<0 end{Bmatrix}" src="https://latex.codecogs.com/gif.latex?%7Cx%7C%27%3D%5Cbegin%7BBmatrix%7D%201%26%20x%3E0%5C%5C%20%5B-1%2C+1%5D%20%26x%3D0%20%5C%5C%20-1%26x%3C0%20%5Cend%7BBmatrix%7D" />

【对比法】令  关于  的凸可微函数  。存在某些  使得  ，则  。

此时，取值C，D处作为次梯度点。

证明：

前提：" src="https://latex.codecogs.com/gif.latex?%5Cforall%20u%2Cf%28u%29%5Cgeqslant%20f%28w%29+%3Cu-w%2Cv%3E" />

选择 C 作为次梯度点：

即，可得：0\ vgeqslant frac{u}{4}+frac{1}{u}+1 & u<0 end{matrix}right." src="https://latex.codecogs.com/gif.latex?%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20v%5Cleqslant%20%5Cfrac%7Bu%7D%7B4%7D+%5Cfrac%7B1%7D%7Bu%7D+1%20%26%20u%3E0%5C%5C%20v%5Cgeqslant%20%5Cfrac%7Bu%7D%7B4%7D+%5Cfrac%7B1%7D%7Bu%7D+1%20%26%20u%3C0%20%5Cend%7Bmatrix%7D%5Cright." />

可得：

选择 B  作为次梯度点：

即，可得：0\ vgeqslant frac{u}{4}-frac{3}{u}-1 & u<0 end{matrix}right." src="https://latex.codecogs.com/gif.latex?%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%20v%5Cleqslant%20%5Cfrac%7Bu%7D%7B4%7D-%5Cfrac%7B3%7D%7Bu%7D-1%20%26%20u%3E0%5C%5C%20v%5Cgeqslant%20%5Cfrac%7Bu%7D%7B4%7D-%5Cfrac%7B3%7D%7Bu%7D-1%20%26%20u%3C0%20%5Cend%7Bmatrix%7D%5Cright." />

 此时， 无解，故不可作为次梯度点。

在随机梯度下降中，我们不要求更新方向完全基于梯度。相反，我们允许方向为随机向量，并要求其期望值为当前向量处函数的次梯度。

在随机梯度下降中，我们不要求更新方向完全基于梯度。相反，我们允许方向为随机向量，并要求其期望值为当前向量处函数的次梯度。

SGD伪码：在学习问题的背景下，很容易找到期望值为风险函数次梯度的随机向量。例如，每个样本的风险函数梯度。

机器学习：支持向量机（SVM）_燕双嘤-CSDN博客1，算法描述支持向量机（SVM）是用来解决分类问题的。作为数据挖掘领域中一项非常重要的任务，分类目前在商业上应用最多（比如分析型CRM里面的客户分类模型、客户流失模型、客户盈利等，其本质上都属于分类问题）。而分类的目的则是构造一个分类函数或分类模型，该模型能吧数据库中的数据项映射到给定类别中的某一个，从而可以用来预测未知类别。先考虑最简单的情况，比如豌豆和米粒，用筛子很快可以分离它们，小颗粒漏下去，大颗粒保留。用函数来表示就是当直径d大于某个值D，就判定其为豌豆，小于D就是米粒。在数轴上就是D左边https://shao12138.blog.csdn.net/article/details/121164645当最优化时的函数不是全区间可微时，无法通过对偶问题解决，此时可以使用SGD实现SVM。

为了应用SGD，我们必须将上式中的优化问题转化为无约束问题：

更新规则：

求梯度可得：

：在迭代  选择的随机例子上， 处损失函数的次梯度。

 特别的，对每个  0" src="https://latex.codecogs.com/gif.latex?B%2C%5Crho%3E%200" /> ，如果对所有的  都存在  使得  ，且对每个  且 ，都存在：

证明：

由2.3节证明的性质可得：

]" src="https://latex.codecogs.com/gif.latex?%5Cleqslant%20E%5B%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5E%7B%28t%29%7D-w%5E*%2Cv_t%3E%5D" />

下面过程同2.4节，得：

leqslant frac{1}{T} (frac{||w^*||^2}{2eta }+frac{eta }{2}sum_{t=1}^{T}||v_t||^2)leqslant frac{1}{T}( frac{1}{2eta }B^2+frac{eta }{2}Trho^2)" src="https://latex.codecogs.com/gif.latex?f%28%5Chat%7Bw%7D%29-f%28w%5E*%29%5Cleqslant%20%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5Et-w%5E*%2Cv_t%3E%5Cleqslant%20%5Cfrac%7B1%7D%7BT%7D%20%28%5Cfrac%7B%7C%7Cw%5E*%7C%7C%5E2%7D%7B2%5Ceta%20%7D+%5Cfrac%7B%5Ceta%20%7D%7B2%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%7C%7Cv_t%7C%7C%5E2%29%5Cleqslant%20%5Cfrac%7B1%7D%7BT%7D%28%20%5Cfrac%7B1%7D%7B2%5Ceta%20%7DB%5E2+%5Cfrac%7B%5Ceta%20%7D%7B2%7DT%5Crho%5E2%29" />

leqslant frac{1}{T}(frac{B^2}{2eta }+frac{eta Trho^2}{2})" src="https://latex.codecogs.com/gif.latex?%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5Et-w%5E*%2Cv_t%3E%20%5Cleqslant%20%5Cfrac%7B1%7D%7BT%7D%28%5Cfrac%7BB%5E2%7D%7B2%5Ceta%20%7D+%5Cfrac%7B%5Ceta%20T%5Crho%5E2%7D%7B2%7D%29" />

，

故：

]leqslant E[frac{Brho }{sqrt{T}}]=frac{Brho }{sqrt{T}}" src="https://latex.codecogs.com/gif.latex?E%5Bf%28%5Chat%7Bw%7D%29%5D-f%28w%5E*%29%5Cleqslant%20E%5B%5Cfrac%7B1%7D%7BT%7D%5Csum_%7Bt%3D1%7D%5E%7BT%7D%3Cw%5E%7B%28t%29%7D-w%5E*%2Cv_t%3E%5D%5Cleqslant%20E%5B%5Cfrac%7BB%5Crho%20%7D%7B%5Csqrt%7BT%7D%7D%5D%3D%5Cfrac%7BB%5Crho%20%7D%7B%5Csqrt%7BT%7D%7D" />

即证明：

同理，如果使得  都成立，则要求：

即：，T 存在最小值。

在之前对GD和SGD算法的分析中，我们要求  ，这相当于对  划定了一个半径为  的区间，然后进行选择。

但大部分时候我们无法保证全部的   的时候，可以采用增加投影的方法求解问题： 

，不考虑范围求得一个值。

，然后投影到  上。

我们可以求得，D为最近的点，即投影点，B，E也是，但是不是最小的投影点。