ApX 标志ApX 标志

趋近智

大模型显存计算器硬件课程定价
ApX 标志ApX 标志

趋近智

大模型显存计算器硬件课程定价

所有课程

机器学习高级优化技术
章节 1: 机器学习优化的根本原则
重温梯度下降变体
凸性的作用
理解损失曲面
收敛性分析基本原理
非凸优化中的挑战
数值稳定性考量
实践:分析收敛行为
章节 2: 二阶优化方法
牛顿法:理论与推导
海森矩阵:计算与性质
牛顿法的难点
拟牛顿法:近似Hessian矩阵
BFGS算法详解
有限内存BFGS (L-BFGS)
信赖域方法
动手实践:L-BFGS 的实现
章节 3: 自适应学习率算法
固定学习率的局限性
AdaGrad:根据过往梯度调整学习率
RMSprop:处理AdaGrad学习率递减的问题
Adam:结合动量与RMSprop
Adamax 和 Nadam 变体
AMSGrad:提升 Adam 的收敛性
了解学习率调整策略
实践操作:比较自适应优化器
章节 4: 大规模数据集的优化
随机梯度下降再讨论:方差减小
随机平均梯度 (SAG)
随机方差缩减梯度 (SVRG)
小批量梯度下降的权衡
异步随机梯度下降
数据并行策略
SVRG 的动手实现
章节 5: 分布式优化策略
分布式训练的动机
参数服务器架构
同步更新与异步更新
通信瓶颈与应对策略
All-Reduce 算法
联邦学习优化原理
实践操作:模拟分布式SGD
章节 6: 深度学习中的优化难题
深度学习损失曲面的特点
网络架构对优化的影响
规范化方法与优化
梯度裁剪与梯度爆炸/消失
初始化方法及其影响
正则化方法:优化过程的隐性作用
实践:深度网络优化器调优
章节 7: 高级与专项优化专题
受限优化基本原理
拉格朗日对偶性与KKT条件
投影梯度方法
无导数优化概述
贝叶斯优化用于超参数调优
强化学习策略的优化
实践:实现投影梯度下降

随机平均梯度 (SAG)

随机梯度下降 (gradient descent) (SGD) 是处理大规模机器学习 (machine learning)任务的常用方法。但它依赖于从小批量数据计算出的噪声梯度,可能导致收敛缓慢或不稳定。每一步仅采样一小部分数据引入的方差,通常需要细致调整学习率和更新策略。

随机平均梯度 (SAG) 算法提供了一种有吸引力的替代方案,直接旨在降低这种方差。SAG 由 Schmidt、Le Roux 和 Bach 于 2012 年提出,它试图将 SGD 的低迭代成本与全批量梯度下降常有的更快收敛特性结合起来,特别是对于强凸问题。

主要思想:平均过去的梯度

SAG 背后的理念简单而巧妙:与其只使用当前小批量(或最简单情况下的单个数据点)的梯度,不如借鉴先前迭代中计算出的梯度信息?SAG 会为训练集中的每个独立数据点,记住最近计算出的梯度。

设目标函数是 NNN 个数据点的平均损失: L(θ)=1N∑i=1NLi(θ)L(\theta) = \frac{1}{N} \sum_{i=1}^N L_i(\theta)L(θ)=N1​∑i=1N​Li​(θ) 其中 Li(θ)L_i(\theta)Li​(θ) 是与第 iii 个数据点关联的损失,θ\thetaθ 表示模型参数 (parameter)。

全批量梯度下降 (gradient descent)使用梯度 ∇L(θ)=1N∑i=1N∇Li(θ)\nabla L(\theta) = \frac{1}{N} \sum_{i=1}^N \nabla L_i(\theta)∇L(θ)=N1​∑i=1N​∇Li​(θ)。SGD 最简单形式(批量大小为 1)在迭代 kkk 时选择一个随机索引 iki_kik​,并使用 ∇Lik(θk)\nabla L_{i_k}(\theta_k)∇Lik​​(θk​) 进行更新。

SAG 的工作方式不同。它维护一个包含 NNN 个梯度向量 (vector)的表格,g1,g2,…,gNg_1, g_2, \dots, g_Ng1​,g2​,…,gN​。每个 gig_igi​ 存储了当数据点 iii 在过去某个迭代中被选中时,为其计算出的最近梯度 ∇Li(θ)\nabla L_i(\theta)∇Li​(θ)。

SAG 更新规则

在每次迭代 k+1k+1k+1 时:

  1. 采样: 从 {1,2,…,N}\{1, 2, \dots, N\}{1,2,…,N} 中随机选择一个索引 iki_kik​。
  2. 计算当前梯度: 使用当前参数 (parameter) θk\theta_kθk​ 计算所选数据点的梯度:vik=∇Lik(θk)v_{i_k} = \nabla L_{i_k}(\theta_k)vik​​=∇Lik​​(θk​)。
  3. 更新平均梯度估计: SAG 的核心是使用存储梯度的平均值作为更新方向。这个平均值可以高效地更新。设 Gk=1N∑j=1NgjG_k = \frac{1}{N} \sum_{j=1}^N g_jGk​=N1​∑j=1N​gj​ 是存储到迭代 kkk 的梯度平均值。新的平均值 Gk+1G_{k+1}Gk+1​ 通过在求和中用新计算的梯度 vikv_{i_k}vik​​ 有效地替换旧的存储梯度 gikg_{i_k}gik​​ 来计算: Gk+1=Gk+1N(vik−gik)G_{k+1} = G_k + \frac{1}{N} (v_{i_k} - g_{i_k})Gk+1​=Gk​+N1​(vik​​−gik​​) 这避免了在每一步重新求和所有 NNN 个存储的梯度。
  4. 更新参数: 使用这个噪声较少的平均梯度估计更新参数: θk+1=θk−ηGk+1\theta_{k+1} = \theta_k - \eta G_{k+1}θk+1​=θk​−ηGk+1​ 其中 η\etaη 是学习率。
  5. 更新记忆: 将新计算的梯度 vikv_{i_k}vik​​ 存储到记忆表格中,替换掉 gikg_{i_k}gik​​ 的先前值: gik←vikg_{i_k} \leftarrow v_{i_k}gik​​←vik​​

最初,存储的梯度 gig_igi​ 可以初始化为零向量 (vector)或根据初始参数猜测计算。

单次 SAG 迭代的流程。采样一个数据点 iki_kik​,计算其当前梯度,这个新梯度同时更新运行中的平均梯度估计 (Gk+1G_{k+1}Gk+1​) 和存储的梯度记忆 (gikg_{i_k}gik​​)。

收敛性质

SAG 的主要优点之一是其收敛速度。对于强凸且光滑的目标函数,SAG 实现了线性收敛速度。这相比于标准 SGD 在这类问题上通常的次线性速度是一个显著提升。简单来说,SAG 在达到一定精度所需的迭代次数方面收敛更快,接近全批量梯度下降 (gradient descent)的理想特性。与每迭代成本随 NNN 线性增加的全批量梯度下降不同,SAG 的收敛速度不会随着数据集大小 NNN 的增加而显著下降。

计算成本与内存

  • 计算: SAG 的每次迭代成本主要由单个梯度 ∇Lik(θk)\nabla L_{i_k}(\theta_k)∇Lik​​(θk​) 的计算以及向量 (vector)加法/减法决定。这与 SGD(批量大小为 1)的每次迭代成本相当。它比全批量梯度下降 (gradient descent)便宜得多,后者每迭代需要计算 NNN 个梯度。
  • 内存: SAG 的主要缺点是其内存需求。它需要存储 NNN 个梯度向量,其中 NNN 是训练集中的数据点总数。如果参数 (parameter)维度 ddd 很大且 NNN 数量庞大(数十亿样本),存储 N×dN \times dN×d 个浮点数可能变得不切实际甚至不可能。

SAG 与 SGD 对比

  • 方差: SAG 通过平均梯度显著降低了相比 SGD 的方差。这带来更稳定的更新和更快的收敛。
  • 内存: SGD 的内存开销最小(仅存储参数 (parameter)和当前小批量梯度),而 SAG 需要存储 NNN 个梯度。
  • 收敛速度(迭代次数): 对于强凸问题,SAG 通常比 SGD(次线性)收敛快得多(线性)。
  • 实现复杂度: 由于需要管理梯度记忆表,SAG 的实现略微复杂。

SAG 代表了弥合 SGD 可扩展性与批量方法快速收敛之间差距的重要一步。然而,其内存需求限制了它在 NNN 极大情景下的适用性。这一限制推动了后续方差削减技术(如 SVRG,我们接下来会讨论)的发展,旨在保留快速收敛优势的同时减轻内存负担。

  • Optimization Methods for Large-Scale Machine Learning, Léon Bottou, Frank E. Curtis, and Jorge Nocedal, 2018 SIAM Review, Vol. 60 (Society for Industrial and Applied Mathematics) DOI: 10.1137/16M1080173 - 一篇关于大规模机器学习优化方法的全面综述,其中包含SAG。
  • Accelerating Stochastic Gradient Descent using Predictive Variance Reduction, Rie Johnson, Tong Zhang, 2013 Advances in Neural Information Processing Systems 26 (NIPS 2013) (Curran Associates Inc.) DOI: 10.55989/NIPS-2013-1070 - 这篇论文介绍了随机方差缩减梯度 (SVRG),它是SAG的后续算法,旨在解决其内存限制。

© 2026 ApX Machine Learning