机器学习：梯度下降，次梯度，随机梯度下降

梯度下降（Gradient Descent）是机器学习中最常见的优化算法之一，广泛用于模型训练和参数优化。本篇博客介绍梯度下降的基本原理，并深入探讨批量梯度下降（GD）、随机梯度下降（SGD）及次梯度方法（Subgradient Method）的区别与应用。我们将分析不同算法在收敛速度、计算成本、稳定性等方面的表现，并结合实际案例，帮助读者理解如何选择最适合的优化策略，以应对不同的机器

燕双嘤

9632人浏览 · 2021-11-14 10:55:06

燕双嘤 · 2021-11-14 10:55:06 发布

1，概述

1.1，梯度下降法

假定给定函数： $f(k)=k^2-4k$ ，求解该函数的极小值时，k的取值是多少？

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

$\frac{\partial f(k)}{\partial k}=2k-4=0\Rightarrow k=2$

1.2，迭代与梯度下降求解

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

$k_{t+1}=k_t-\alpha*g(k_t)$

其中 $\alpha$ 被称为学习效率。

假设初始化 $k_0=0$ ，为了通过迭代让 $k_t$ 趋近最优解 2， $g(k_t)$ 要满足两个条件：

$g(k_t)$ 要能使 $k_{t+1}$ 向最优解逼近。

当 $k_t$ 达到最优解时， $g(k_{t+1})$ 要等于0。当 $k_t$ 达到最优解的时候， $k_{t+1}$ 要等于 $k_t$ ，即：

$k_{t+1}=k_t\Rightarrow g(k_t)=0$

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

1.3，求解思路

$\alpha$ 随着迭代的不断进行， $g(k_t)$ 可以使 $k_{t+1}$ 向最优值逼近。而且，当 $k_{k+1}$ 离最优值越近时， $g(k_{t+1})$ 的绝对值就越来越小。当达到最优解时， $g(k_{t+1})=0$ 。

学习速率的取值问题：

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

当 $\alpha$ 取值较小时，即梯度下降迭代的步长较小，梯度下降迭代过程较慢。

梯度优化：方向+步长

2，梯度下降

2.1，可微函数的梯度

可微函数的梯度 $f$ ： $R^d\rightarrow R$ 在 $w$ 处， $\bigtriangledown f(w)$ 表示为是 $f$ 的偏导数的向量，即：

$\bigtriangledown f(w)=(\frac{\partial f(w)}{\partial w1},\frac{\partial f(w)}{\partial w_2},...,\frac{\partial f(w)}{\partial w_d})^T$

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

从初始值 $w(w^1=0)$ 开始。

在每次迭代中，沿着当前点梯度的负方向迈出下一步：

$w^{t+1}=w^t-\eta \bigtriangledown f(w^{(t)})(\eta >0)$

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

输出也可以是平均向量 $\hat{w} = \frac{1}{T}\sum_{t=1}^{T}w_t$ 。取平均值是非常有用的，特别是当我们将梯度下降推广到不可微函数和随机情况时。

【证明】 $f(w^{t+1})\leqslant f(w^t)$ ，即：梯度不断下降。

$f(w^{t+1})=f(w^{(t)}-\eta \bigtriangledown f(w^{(t)}))$

由于， $y^{t+1}=y^t+(x_{t+1}-x_{t}){f}'(x_t)$ 。

$=f(w^{(t)})+(w^{(t)}-\eta \bigtriangledown f(w^{(t)})-w^{(t)})^T\bigtriangledown f(w^{(t)})$

$=f(w^{(t)})-\eta \bigtriangledown f(w^{(t)})^T\bigtriangledown f(w^{(t)})$

$=f(w^{(t)})-\eta ||\bigtriangledown f(w^{(t)})||_2^2$

由于 $||\bigtriangledown f(w^{(t)})||_2 > 0$ ，学习率 $\eta > 0$ ，所以 $-\eta ||\bigtriangledown f(w^{(t)})||_2 < 0$ ，故：

$f(w^{t+1})\leqslant f(w^t)$

2.2，梯度下降算法的收敛速率

Lipschitz连续：对于在实数集的子集的函数 $f:D\subseteq \mathbb{R}\rightarrow \mathbb{R}$ ，若存在常数 $\rho$ ，使得 $\left | f(a)-f(b) \right |\leq \rho \left | a-b \right |,\forall a,b\in D$ ，则称函数 $f$ 符合利普希茨条件。

为了分析GD算法的收敛速度，我们仅限于凸 Lipschitz 函数的情况。 $w^*$ 是 $f(w)$ 在 $||w^*|| \leqslant B$ 条件下的最小值的点坐标。

假设： $\hat{w} = \frac{1}{T}\sum_{t=1}^{T}w^{(t)}$

求证： $f(\hat{w})-f(w^*)$ 有界

2.3，凸函数性质

凸函数性质（1）：

$f(\hat{w})-f(w^*)\leqslant \frac{1}{T}\sum_{t=1}^{T}(f(w^{(t)})-f(w^*))$

证明方法（1）：

$f(\hat{w})-f(w^*) (?) \frac{1}{T}\sum_{t=1}^{T}(f(w^{(t)})-f(w^*))$

$f(\hat{w})-f(w^*) (?) \frac{1}{T}\sum_{t=1}^{T}f(w^{(t)})-f(w^*)$

$f(\hat{w})(?) \frac{1}{T}\sum_{t=1}^{T}f(w^{(t)})$

$f(\frac{1}{T}\sum_{t=1}^{T}w^{(t)})(?) \frac{1}{T}\sum_{t=1}^{T}f(w^{(t)})$

即，判断上述关系即可：

从图上可以看出， $y(x_C)=\frac{y(x_A)+y(x_B)}{2}\geqslant y(x_{\frac{x_A+x_B}{2}})=y(x_D)$ ，且趋近于0时取等号，不失一般性，可推广到其他凸函数上。

故， $f(\frac{1}{T}\sum_{t=1}^{T}w^{(t)})\leqslant \frac{1}{T}\sum_{t=1}^{T}f(w^{(t)})$

凸函数性质（2）：

$f(w^{(t)})-f(w^*)\leqslant <w^{(t)}-w^*,\bigtriangledown f(w^{(t)})>$

证明：将 $f(w^*)$ 进行泰勒展开可得：

$f(w^*) \geqslant f(w^{(t)})+(w^*-w^{(t)})\bigtriangledown f(w^{t})+\frac{1}{2!}(w^*-w^{(t)})\bigtriangledown f'(w^{t})+...$

$f(w^*)-f(w^{(t)}) \geqslant (w^*-w^{(t)})\bigtriangledown f(w^{t})+\frac{1}{2!}(w^*-w^{(t)})\bigtriangledown f'(w^{t})+...$

$f(w^{(t)})-f(w^*) \leqslant (w^{(t)}-w^*)\bigtriangledown f(w^{t})+\frac{1}{2!}(w^{(t)}-w^*)\bigtriangledown f'(w^{t})+...$

$w^{(t)}-w^* \geqslant 0$ ，且 $w^*$ 处为偏导最小处，即 $\bigtriangledown f(w^{t}) \geqslant 0$ 。

$w^{(t)}-w^* \leqslant 0$ ，且 $w^*$ 处为偏导最小处，即 $\bigtriangledown f(w^{t}) \leqslant 0$ 。

即： $(w^{(t)}-w^*)\bigtriangledown f(w^{t})\geqslant 0$

即：Hessian矩阵 $\bigtriangledown f'(w^{t})$ 半正定，可以忽略非负项

故： $f(w^{(t)})-f(w^*) \leqslant (w^{(t)}-w^*)\bigtriangledown f(w^{t})$

因此：

凸函数性质（1）： $f(\hat{w})-f(w^*)\leqslant \frac{1}{T}\sum_{t=1}^{T}(f(w^{(t)})-f(w^*))$

凸函数性质（2）： $f(w^{(t)})-f(w^*)\leqslant <w^{(t)}-w^*,\bigtriangledown f(w^{(t)})>$

合体证明：

$f(\hat{w})-f(w^*)= f(\frac{1}{T}\sum_{t=1}^{T}w^t)-f(w^*)$

$\leqslant \frac{1}{T}\sum_{t=1}^{T}f(w^t)-f(w^*)$

$= \frac{1}{T}\sum_{t=1}^{T}(f(w^t)-f(w^*))$

$= \frac{1}{T}\sum_{t=1}^{T}( <w^{(t)}-w^*,\bigtriangledown f(w^{(t)})>)$

2.4，求解收敛速率

设 $v_1,v_2,...,v_T$ 是向量的任意序列。任何具有初始化 $w^{(1)}=0$ 和以下形式的更新规则的算法：

$w^{(t+1)}=w^t-\eta v_t(\eta >0)$

满足：

$\sum_{t=1}^{T}<w^t-w^*,v_t>\leqslant \frac{||w^*||^2}{2\eta }+\frac{\eta }{2}\sum_{t=1}^{T}||v_t||^2$

前提（1）：

$x^T*y=-\frac{1}{2}(||x-y||^2-||x||^2-||y||^2)$

前提（2）：

$<w^t-w^*,v_t>=\frac{1}{\eta }<w^t-w^*,\eta v_t>$

$=-\frac{1}{2\eta }(||w^t-w^*-\eta v_t||^2-||w^t-w^*||^2-\eta^2||v_t||^2)$

$=-\frac{1}{2\eta }(||w^{t+1}-w^*||^2-||w^t-w^*||^2-\eta^2||v_t||^2)$

根据下一轮结果求和后一正一负抵消，可推出：

$\sum_{t=1}^{T}<w^t-w^*,v_t> =-\frac{1 }{2\eta }(||w^{t+1}-w^*||^2-||w^1-w^*||^2)+\frac{\eta ^{2}}{2\eta }\sum_{t=1}^{T}||v_t||^2$

$\leqslant \frac{1}{2\eta }(||w^1-w^*||^2)+\frac{\eta }{2}\sum_{t=1}^{T}||v_t||^2$

$= \frac{1}{2\eta }||w^*||^2+\frac{\eta }{2}\sum_{t=1}^{T}||v_t||^2$

即：

$T(f(\hat{w})-f(w^*))\leqslant \sum_{t=1}^{T}<w^t-w^*,v_t>\leqslant \frac{||w^*||^2}{2\eta }+\frac{\eta }{2}\sum_{t=1}^{T}||v_t||^2$

特别的，对每个 $B,\rho> 0$ ，如果对所有的 $t$ 都存在 $||v_t||\leqslant \rho$ 使得 $\eta =\sqrt{\frac{B^2}{\rho^2T}}$ ，且对每个 $w^*$ 且 $||w^*||\leqslant B$ ，都存在：

$\frac{1}{T}\sum_{t=1}^{T}<w^t-w^*,v_t>\leqslant \frac{B\rho }{\sqrt{T}}$

证明：由前面可得

$\sum_{t=1}^{T}<w^t-w^*,v_t> \leqslant \frac{1}{2\eta }||w^*||^2+\frac{\eta }{2}\sum_{t=1}^{T}||v_t||^2$

$\leqslant \frac{1}{2\eta }B^2+\frac{\eta }{2}T\rho^2$

令 $f(\eta )=\frac{1}{2\eta }B^2+\frac{\eta }{2}T\rho^2$

则 $f'(\eta )=-\frac{B^2}{2\eta ^2}+\frac{T\rho ^2}{2}=0$ ，可得 $f(\eta )$ 得极小值，因此也是 $T$ 的最小值。

$\eta =\sqrt{\frac{B^2}{\rho^2T}}$

$T = \frac{B^2}{\rho ^2\eta ^2}$

且：

$f(\hat{w})-f(w^*)\leqslant \frac{1}{T}\sum_{t=1}^{T}( <w^{(t)}-w^*,\bigtriangledown f(w^{(t)})>)$

$\sum_{t=1}^{T}( <w^{(t)}-w^*,\bigtriangledown f(w^{(t)})>)\leqslant \frac{1}{2\eta }B^2+\frac{\eta }{2}T\rho^2$

带入 $\eta$ 可得： $f(\hat{w})-f(w^*)\leqslant \frac{B\rho }{\sqrt{T}}$

当且仅当 $v_t=\bigtriangledown f(w^{(t)})$

在允许一定误差的情况下：对任意的 $\varepsilon >0$ ，使得：

$f(\hat{w})-f(w^*)\leqslant \varepsilon$

则必须满足： $\frac{B\rho }{\sqrt{T}} \leqslant \varepsilon$

即： $T \geqslant \frac{B^2\rho ^2}{\varepsilon ^2}$ ，T 存在最小值。

3，次梯度

3.1，为何需要次梯度

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

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

允许 $S$ 是一个开凸集。 $A$ 函数 $f:S \rightarrow R$ 是一个凸函数。满足下列条件的向量 $v$ ：

$\forall u,f(u)\geqslant f(w)+<u-w,v>$

称为 $f$ 在 $w$ 处的次梯度。 $f$ 在 $w$ 处的次梯度集称为微分集并表示为 $\partial f(w)$ 。

3.2，计算次梯度

如果 $f$ 在 $w$ 处可微，那么 $\partial f(w)$ 包含一个元素 $f$ 在 $w$ 处的梯度为 $\bigtriangledown f(w)$ 。

例如： $|x|$ 。

由于 $|w|$ 在 $w=0$ 处不可导，因此根据定义：

$|u|\geqslant |w|+<u-w,v>$

$|u|\geqslant uv$

$\Rightarrow v \in [-1,+1]$

即： $|x|'=\begin{Bmatrix} 1& x>0\\ [-1,+1] &x=0 \\ -1&x<0 \end{Bmatrix}$

求： $f(w)=max\left \{ 0,1-y_iw^Tx_i \right \}$

变换后得： $f(w)=\left\{\begin{matrix} 0 &y_iw^Tx_i\geqslant 1 \\ 1-y_iw^Tx_i & y_iw^Tx_i< 1 \end{matrix}\right.$

当取 $1-y_iw^Tx_i$ 时， $1-y_iu^Tx_i\geqslant 1-y_iw^Tx_i+<u-w,v>$

$1-y_iu^Tx_i\geqslant 1-y_ix_i+(u^T-1)v$

$y_i(1-u^T)x_i\geqslant (u^T-1)v$

$v\geqslant -y_ix_i(w<1)$

当取 0 时， $0\geqslant 0+<u-1,v>$

$0\geqslant uv-1v$

$0\geqslant v(u>1)$

严谨写法：

$f'(w)=\left\{\begin{matrix} 0& y_iw^Tx_i> 1\\ Co\left \{ 0,-y_ix_i \right \}&y_iw^Tx_i= 1 \\ -y_ix_i& y_iw^Tx_i< 1\end{matrix}\right.$

令 $g(w)=max_{1\leqslant i\leqslant r}g_i(w)$ 关于 $r$ 的凸可微函数 $g_1,g_2,...,g_r$ 。存在某些 $w$ 使得 $j \in arg\, \, max_{1\leqslant i\leqslant r}g_i(w)$ ，则 $\bigtriangledown g_j(w)\in \partial g(w)$ 。

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

证明：

前提： $\forall u,f(u)\geqslant f(w)+<u-w,v>$

选择 C 作为次梯度点：

$(\frac{u}{2}+1)^2\geq 0+uv$

即，可得： $\left\{\begin{matrix} v\leqslant \frac{u}{4}+\frac{1}{u}+1 & u>0\\ v\geqslant \frac{u}{4}+\frac{1}{u}+1 & u<0 \end{matrix}\right.$

可得： $v\in [0,2]$

选择 B 作为次梯度点：

$(\frac{u}{2}-1)^2\geq 4+uv$

即，可得： $\left\{\begin{matrix} v\leqslant \frac{u}{4}-\frac{3}{u}-1 & u>0\\ v\geqslant \frac{u}{4}-\frac{3}{u}-1 & u<0 \end{matrix}\right.$

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

4，随机梯度下降

4.1，核心思想

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

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

4.2，使用SGD实现SVM

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

$\underset{w,\varepsilon }{min} \frac{\lambda }{2}||w||^2+\sum_{i=1}^{n}\xi_i\, \, \, s.t.\, \, \, y_i(w^Tx_i)\geqslant 1-\xi_i,\xi_i\geqslant 0,\forall i$

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

$\underset{w,\varepsilon }{min} \frac{\lambda }{2}||w||^2+\sum_{i=1}^{n}max\left \{ 0,1-y_i(w^Tx_i) \right \}$

更新规则：

一个次梯度为： $\lambda w^{(t)}+v_t$

$v_t$ ：在迭代 $t$ 选择的随机例子上 $w^{(t)}$ 处损失函数的次梯度。

$w^{(t+1)}=w^{(t)}-\frac{1}{\lambda t}(\lambda w^{(t)}+v_t)$ ，其中 $\frac{1}{\lambda t}$ 为学习率。

$=\frac{t-1}{t}w^{(t)}-\frac{1}{\lambda t}v_t$

$=\frac{t-1}{t}(\frac{t-2}{t-1}w^{(t-1)}-\frac{1}{\lambda (t-1)}v_{t-1})-\frac{1}{\lambda t}v_t$

$......,w^{0}=0$

$=-\frac{1}{\lambda t}\sum_{i=1}^{t}v_i$

4.3，SGD的收敛速度

特别的，对每个 $B,\rho> 0$ ，如果对所有的 $t$ 都存在 $||v_t||\leqslant \rho$ 使得 $\eta =\sqrt{\frac{B^2}{\rho^2T}}$ ，且对每个 $w^*$ 且 $||w^*||\leqslant B$ ，都存在：

$E[f(\hat{w})]-f(w^*)\leqslant \frac{B\rho }{\sqrt{T}}$

证明：

$E[f(\hat{w})]-f(w^*)=E[f(\hat{w})-f(w^*)]$

$= E[f(\frac{1}{T}\sum_{t=1}^{T}w^{(t)})-f(w^*)]$

$\leqslant E[\frac{1}{T}\sum_{t=1}^{T}f(w^{(t)})-f(w^*)]$

$= E[\frac{1}{T}\sum_{t=1}^{T}(f(w^{(t)})-f(w^*))]$

由2.3节证明的性质可得：

$\leqslant E[\frac{1}{T}\sum_{t=1}^{T}<w^{(t)}-w^*,v_t>]$

下面过程同2.4节，得：

$f(\hat{w})-f(w^*)\leqslant \frac{1}{T}\sum_{t=1}^{T}<w^t-w^*,v_t>\leqslant \frac{1}{T} (\frac{||w^*||^2}{2\eta }+\frac{\eta }{2}\sum_{t=1}^{T}||v_t||^2)\leqslant \frac{1}{T}( \frac{1}{2\eta }B^2+\frac{\eta }{2}T\rho^2)$

$\frac{1}{T}\sum_{t=1}^{T}<w^t-w^*,v_t> \leqslant \frac{1}{T}(\frac{B^2}{2\eta }+\frac{\eta T\rho^2}{2})$

带入， $\eta =\sqrt{\frac{B^2}{\rho^2T}}$

$\sum_{t=1}^{T}<w^t-w^*,v_t>=\frac{B\rho }{\sqrt{T}}$

故：

$E[f(\hat{w})]-f(w^*)\leqslant E[\frac{1}{T}\sum_{t=1}^{T}<w^{(t)}-w^*,v_t>]\leqslant E[\frac{B\rho }{\sqrt{T}}]=\frac{B\rho }{\sqrt{T}}$

即证明： $E[f(\hat{w})]-f(w^*)\leqslant \frac{B\rho }{\sqrt{T}}$

同理，如果使得 $E[f(\hat{w})]-f(w^*)\leqslant \varepsilon$ 都成立，则要求：

$\frac{B\rho }{\sqrt{T}} \leqslant \varepsilon$

即： $T \geqslant \frac{B^2\rho ^2}{\varepsilon ^2}$ ，T 存在最小值。

4.4，投影步骤

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

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

$w^{(t+\frac{1}{2})}=w^{(t)}-\eta v_t$ ，不考虑范围求得一个值。

$w^{(t+1)}=argmin_{w \in H}||w-w^{(t+\frac{1}{2})}||$ ，然后投影到 $B$ 上。

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

EazyDevelop社区

一站式 AI 云服务平台

更多推荐

探秘深海：一款强大的深度学习框架——DeepSea

在人工智能领域中，深度学习是推动科技进步的一股强大动力。今天，我们要向大家推荐的是一个专为深度学习爱好者和开发者打造的强大框架——DeepSea。该项目由Team-Neptune团队开发，并托管在Gitcode平台上，旨在简化和加速深度学习模型的研发过程。## 技术分析### 灵活的架构设计DeepSea采用模块化的设计，允许用户根据需求选择不同的组件，如优化器、损失函数等，以构建定制

EazyDevelop社区

从零开始搭建个人RAG知识库：RAGFlow+DeepSeek保姆级教程！

EazyDevelop社区

taosync：适用于AList v3的自动化同步工具

在现代生活中，数据同步和备份已成为维护数据安全的关键环节。taosync是一款专为AList v3设计的自动化同步工具，能够帮助用户轻松地同步和备份他们的数据到多个网盘或FTP存储服务。这款工具的开发初衷是为了保存孩子的成长照片，其名称“taoSync”也因此而来。taosync以开源免费的形式提供，支持几乎所有的常用平台，并且提供了完善的日志记录、任务管理以及安全的密码加密功能。## 项目技