知识点：方差减小技术

知识点概述

方差减小（Variance Reduction）技术旨在克服随机梯度下降（SGD）中梯度估计方差过大、导致收敛慢的缺点。通过巧妙地结合随机梯度和周期性计算的完整梯度，这类算法在保持低迭代成本的同时，实现了像批梯度下降一样的快速线性收敛。

动机: SGD的收敛速度受限于其梯度估计的方差。为了达到高精度解，SGD必须使用逐渐减小的步长，这限制了其收敛速度。
核心思想: 构造一个梯度估计量，它既是无偏的（或在期望意义上接近真实梯度），又具有比朴素SGD更小的方差。
著名算法:
- SAG (Stochastic Average Gradient): 在内存中维护一个历史上所有样本梯度的平均值。每次迭代，只计算当前样本的新梯度，并用它来更新这个平均梯度。更新方向使用这个平均梯度。缺点是需要存储所有样本的梯度。
- SVRG (Stochastic Variance Reduced Gradient): 采用双层循环。在外循环的开始，计算一次完整的梯度 $μ$ 。在内循环中，每次迭代的更新方向为 $g_{k} = \nabla f_{i_{k}} (x_{k}) - (\nabla f_{i_{k}} (\tilde{x}) - μ)$ ，其中 $\tilde{x}$ 是外循环开始时的快照。这个梯度估计是无偏的，且当 $x_{k}$ 和 $\tilde{x}$ 都接近最优解时，其方差会趋于零。
- SAGA: SVRG的变体，无需双层循环，更易于实现和分析。