2025年线性收敛的随机优化算法之 SAG、SVRG（随机梯度下降）

科技前沿 • 2025-01-26 17:33 • 阅读 44

大家好，我是讯享网，很高兴认识大家。

原文出处：https://zhuanlan.zhihu.com/p/?utm_source=tuicool&utm_medium=referral

这篇文章回顾了基于梯度的随机优化算法在这几年的重要发展 -- SAG、SVRG。

很多常见的机器学习模型的目标（比如最小二乘做线性回归、逻辑回归）都可以概括成以下这种一般形式：

$\min_{\mathbf{w}} \frac{1}{N} \sum_{i=1}^N f(\mathbf{x}_i, \mathbf{w}) + \lambda h(\mathbf{w})$
讯享网

其中 $f(\mathbf{x}_i, \mathbf{w})$ 代表样本 $\mathbf{x}_i$ 的损失函数， $\mathbf{w}$ 是模型的参数， $h(\mathbf{w})$ 代表正则化项（用于控制模型复杂度或者模型稀疏度等等），有些时候这个正则化项是不平滑的，也就是说它可能不可导。

暂时先不考虑这个正则化项，只考虑样本上的损失，并且对符号做一点简化（ $f(\mathbf{x}_i,\mathbf{w}) \triangleq f_i(\mathbf{w})$ ），考虑下面这个优化目标：

$\min_{\mathbf{w}}\frac{1}{N}\sum_{i=1}^N f_i( \mathbf{w})$

这个形式非常简单，只要每个 $f_i(\mathbf{w})$ 都可导，就可以用梯度下降法（Gradient Descent）迭代求解:

$\mathbf{w}_{t+1} = \mathbf{w}_t - \eta \frac{1}{N}\sum_{i=1}^N \triangledown f_i(\mathbf{w}_t)$ ，其中 $\mathbf{w}_{t+1}$ 表示第 t+1 次更新后的参数。

梯度下降对于样本数目比较多的时候有一个很大的劣势，那就是每次需要求解所有样本的梯度，样本数多的时候，导致计算量大增，所以实际生产环境中，往往采用随机梯度下降算法（Stochastic Gradient Descent），一般简写做SGD。

SGD每次迭代的时候均匀随机得选择一个样本或者mini-batch做更新：

$\mathbf{w}_{t+1} = \mathbf{w}_t - \eta \triangledown f_i(\mathbf{w}_t)$

相对于梯度下降，SGD的好处非常明显，就是可以减少每次更新的计算代价，但是SGD带来的问题是收敛速度不如梯度下降（收敛速度是衡量优化算法计算复杂度的基本工具，具体定义可以参考https://en.wikipedia.org/wiki/Rate_of_convergence 或者其他优化相关的教材），也就是说为了达到同样的精度，SGD需要的总迭代次数要大于梯度下降，但是，单次迭代的计算量要小得多。从收敛速度分析上看，SGD能够在目标函数强凸并且递减步长的情况下做到 O(1/T) 的次线性收敛（sublinear convergence），而梯度下降则可以在目标函数强凸的情况下做到 $O(\rho^T)$ ( $\rho < 1$ ) 的线性收敛（linear convergence）。总结起来就是，如果想快速得到一个可以勉强接受的解，SGD比梯度下降更加合适，但是如果想得到一个精确度高的解，应当选择梯度下降。

SGD后来后来也衍生出了非常多的变种，尤其是一类分析regret的online算法，包括Adagrad、Dual Averaging、FTRL等。但是，始终学术界对于SGD还有一种期待，就是：是否可以把SGD做到和梯度下降一样的线性收敛。直到2012和2013年，SAG[1]与SVRG[2]算法发表在NIPS上，成为近几年SGD类算法的最大突破。

SAG算法（算法框图摘自[4]，这里的 f_i'(.) 是指梯度函数 $\triangledown f_i(.)$ ，而是指上文中的优化参数 $\mathbf{w}$ ）

2025年线性收敛的随机优化算法之 SAG、SVRG（随机梯度下降）

相关推荐