技术摘要：修正的随机洗牌 SARAH

问题陈述

本文解决了机器学习中常见的有限和最小化问题：
$$\min_{w \in \mathbb{R}^d} P(w) := \frac{1}{n} \sum_{i=1}^n f_i(w)$$
其中 $n$ 是数据样本的数量，每个 $f_i$ 是一个平滑函数。虽然梯度下降（GD）提供了快速的线性收敛，但其每次迭代的 $O(n)$ 成本对于大规模数据集而言是难以承受的。随机梯度下降（SGD）将此成本降低至 $O(1)$，但遭受高方差的困扰，需要递减的步长并导致次线性收敛。像 SARAH 和 SVRG 这样的方差缩减（VR）方法改进了收敛速率，但通常需要在每个外层循环开始时计算完整梯度 $\nabla P(\tilde{w})$，从而维持了 $O(n)$ 的瓶颈。

现有的基于洗牌的 VR 方法（例如洗牌 SARAH、洗牌 SVRG）试图将无放回采样（洗牌）的实际效率与方差缩减相结合。然而，目前的理论分析表明，这些方法在总复杂度中通常保留了对数据集大小 $n$ 的线性依赖（例如 $O(n\kappa \log(1/\varepsilon))$）。这种线性缩放限制了它们在 $n$ 巨大的现代大规模场景中的效率。

方法论：修正的随机洗牌 SARAH

作者提出了修正的随机洗牌 SARAH，这是一种将洗牌策略集成到递归 SARAH 框架中的新颖算法。其核心创新在于内循环中的动态加权机制以及双模式操作结构。

算法结构

该算法在 $s = 1, \dots, S$ 个周期（epochs）中运行。在每个周期内，它使用数据集索引的排列 $\pi_s$ 执行大小为 $m$ 的内循环。

1. 初始化：设置 $w_0 = \tilde{w}_{s-1}$。使用大小为 $m$ 的小批量计算完整梯度的随机近似值 $v_0$。
2. 内循环更新：对于 $t = 1, \dots, m$，梯度估计量递归更新：
   $$v_t = \left( \frac{m+1}{m+1-t} \right) \left( \nabla f_{\pi_t^s}(w_t) - \nabla f_{\pi_t^s}(w_{t-1}) \right) + v_{t-1}$$
   参数 $w_{t+1}$ 通过 $w_{t+1} = w_t - \eta v_t$ 更新。
3. 周期完成：设置 $\tilde{w}_s = w_{m+1}$。

关键机制

• 动态加权：与使用系数 1 的标准 SARAH 或洗牌 SARAH 不同，该算法将梯度差项乘以 $\frac{m+1}{m+1-t}$。当 $t \to m$ 时，该系数增大，放大了内循环末尾附近梯度差的贡献。这种设计确保排列中的每个数据点对总周期更新的贡献相等，平衡了排列中早期项和晚期项的权重。
• 双模式：
  • 精确模式（$m=n$）：使用数据集的完整排列。它在周期开始时计算完整梯度（或全批量近似）。此模式针对高精度收敛。
  • 非精确模式（$m < n$）：使用大小为 $m$ 的子集的随机重洗牌。初始向量 $v_0$ 是一个小批量估计量。此模式专为大规模数据集的可扩展性而设计。

理论分析与结果

本文在标准假设（$L$-平滑、$\mu$-强凸性和有界方差）下，提供了强凸和非凸设置下的收敛性分析。

1. 精确模式性能

在精确模式（$m=n$）下，该算法达到了洗牌方差缩减方法已知的最佳理论保证：

• 强凸：实现了 $O(n\kappa \log(1/\varepsilon))$ 的总复杂度。
• 非凸：实现了 $O(nL/\varepsilon^2)$ 的总复杂度。
  这些结果证实，与现有的最先进洗牌 VR 方法相比，动态加权并未降低收敛速率。

2. 非精确模式性能（可扩展性）

主要的理论贡献是对非精确模式（$m < n$）的分析。作者证明，通过仔细选择内循环大小 $m$，当 $n$ 足够大时，总复杂度可以独立于数据集大小 $n$。

• 强凸：总复杂度为 $O\left( \min\left\{ \frac{\sigma^2}{\mu\varepsilon}, n \right\} \kappa \log\left(\frac{1}{\varepsilon}\right) \right)$。当 $n$ 很大时，复杂度缩放为 $O\left( \frac{\sigma^2}{\mu\varepsilon} \kappa \log(1/\varepsilon) \right)$，消除了对 $n$ 的线性依赖。
• 非凸：总复杂度为 $O\left( \min\left\{ \frac{\sigma^2 L}{\varepsilon^4}, \frac{nL}{\varepsilon^2} \right\} \right)$。在大规模场景下，这变为 $O\left( \frac{\sigma^2 L}{\varepsilon^4} \right)$，同样独立于 $n$。

这代表了相对于现有洗牌 VR 算法的重大改进，后者通常无论数据集大小如何，都随 $n$ 线性缩放。

实证验证

作者在三个数据集 w8a、ijcnn1 和 fashion-mnist 上使用带有 $l_2$ 正则化的逻辑回归对二元分类任务评估了修正的随机洗牌 SARAH。

• 比较：该方法与随机重洗牌（RR）SVRG 和 RR SARAH 进行了比较。
• 结果：该算法表现出具有竞争力的性能。在某些数据集（例如 w8a）上，它最初收敛速度慢于竞争对手，但在大约 20 个周期后实现了最小的梯度范数和更优越的长期收敛。在其他数据集上，它保持了与基线相当的性能。结果验证了动态加权机制不会阻碍实际性能，同时提供了理论上的可扩展性优势。

意义与主张

本文主张，修正的随机洗牌 SARAH 是第一个在大规模场景下实现总复杂度独立于数据集大小 $n$ 的洗牌方差缩减算法。

• 可扩展性：通过在非精确模式中解耦计算复杂度与 $n$，该方法为大规模数据集提供了一种严格优于现有洗牌方法的替代方案。
• 理论平衡：该算法成功平衡了收敛精度（精确模式）与计算可扩展性（非精确模式）之间的权衡。
• 局限性：作者谦逊地指出，虽然他们的精确模式达到了洗牌算法已知的最佳速率，但在标准假设下，洗牌方法是否能达到标准均匀采样 VR 方法（如标准 SVRG/SARAH）所实现的优化速率，仍然是一个未解决的问题。

总之，这项工作通过引入一种动态加权方案，推进了洗牌方法的复杂度分析，该方案在不牺牲精确区域理论保证的情况下，实现了可扩展的、独立于 $n$ 的复杂度区域。