技术摘要：SILAGE

问题陈述

本文研究了大规模数据集上的非凸经验风险最小化（ERM）问题，这些数据集具有嵌套的双重有限和结构（nested double finite-sum structure）。目标函数公式如下：
$$\min_{x \in \mathbb{R}^d} f(x) := \frac{1}{n} \sum_{i=1}^n f_i(x), \quad \text{其中} \quad f_i(x) := \frac{1}{m} \sum_{j=1}^m f_{i,j}(x)$$
这里，$N = nm$代表总样本数，这些样本被划分为$n$ 个块（或称 silo/孤岛），每个块的大小为 $m$。这种结构自然存在于中心化场景中，例如汇总的数据湖（如来自多家医院的医疗记录）、数据量超过内存限制的离线学习（out-of-core learning），或通过聚类进行的刻意分层。

现有的方差缩减（VR）方法在这种机制下面临着关键的权衡：

1. 递归估计器（例如 PAGE, SARAH）： 虽然实现了最优的预言复杂度（oracle complexities），但需要周期性地对所有 $nm$ 个样本进行全局全梯度刷新（global full-gradient refreshes）。这些刷新计算成本极高，并造成了扩展瓶颈。
2. 基于内存的估计器（例如 SILVER, SAGA）： 避免了全局刷新，但需要为每一个单独的样本存储一个控制变量，这对于大规模数据集而言，其 $\mathcal{O}(nm)$ 的内存占用 是不切实际的。

目标是设计一种算法，在消除周期性全局刷新的同时，保持仅与块数量（$\mathcal{O}(n)$）成正比的内存占用，而非与总样本数成正比。

方法论：SILAGE

作者提出了 SILAGE（SIngle Loop Average Gradient Estimator），一种专为嵌套结构设计的单循环方差缩减算法。SILAGE 结合了两种方差缩减的哲学：

• SILVER 式的内存结构： 每个块维护一个控制变量（梯度估计器），总共 $n$ 个条目，而不是每个样本一个。
• PAGE 式的递归追踪： 使用随机梯度递归地更新这些估计器。

算法根据块的数量（$n$）与块大小（$m$）的关系进行不同的操作：

1. $m \ge n$ 机制（算法 1）

在此机制下，块的大小大于或等于块的数量。

• 机制： 一个单一的全局硬币投掷决定迭代类型。以概率 $p$，均匀随机选择一个块 $i_t$，并计算其局部全梯度 $\nabla f_{i_t}(x_{t+1})$（即“锚点重置”）。以概率 $1-p$，不进行任何块重置；相反，通过从每个块中采样一个成分梯度来递归更新所有 $n$ 个块。
• 耦合： 概率 $p$ 设置为 $n/m$。这确保了任何特定块被刷新的边际概率为 $1/m$，与标准 PAGE 在平坦数据集上的刷新率相匹配，同时保证每次迭代中最多只有一个块被刷新。
• 代价： 每轮迭代的成本为 $\mathcal{O}(m)$（由单个局部全梯度或 $n$ 个成分梯度主导）。

2. $n > m$ 机制（算法 2）

在此机制下，块的数量超过了块的大小。

• 机制： 如果需要更新许多块，即使计算一个块的全梯度相对于总预算也是昂贵的。SILAGE 选择一个锚点块 $i_t$ 进行全量重置，并选择一个大小为 $b_{grp}-1$ 的小型活跃子集 $\Omega_t$ 进行递归更新。
• 共享漂移（Shared Drift）： 对于剩余的 $n - b_{grp}$ 个未被采样的块，算法不计算新鲜梯度。相反，它应用一个共享漂移 $d_t$（计算为活跃子集中随机差异的平均值）来更新它们的估计器。
• 实现效率： 为了避免使用 $\mathcal{O}(n)$ 的成本显式更新所有 $n$ 个估计器，作者提出了一个实现高效的形式（算法 3），使用一个共享累加器 $q_t$，将簿记成本降低到 $\mathcal{O}(b_{grp})$。

核心贡献

1. 通过嵌套结构实现的内存效率

SILAGE 仅需 $\mathcal{O}(n)$ 内存（存储每个块的一个 $d$ 维向量以及少量辅助向量）。与 SILVER 等扁平化方法相比，这实现了显著的减少，后者需要 $\mathcal{O}(nm)$ 的内存。

2. 消除了周期性的全局刷新

与 PAGE 及其变体不同，SILAGE 从未执行全局全梯度遍历所有 $nm$个成分的操作。它每轮迭代最多只评估一个局部组梯度$\nabla f_i$（成本为$\mathcal{O}(m)$）。初始化可以是任意的（例如零），从而避免了初始全局梯度计算的需求。

3. 利用嵌套相似性

其收敛分析引入了一种对数据几何结构的全新两级依赖，避免了悲观的最坏情况 Lipschitz 常数（$L_{\max}$）：

• 跨组相似性 ($\delta_1$)： 衡量组梯度与全局梯度之间的偏差。
• 组内相似性 ($\delta_2$)： 衡量样本梯度与其局部组平均值之间的偏差。
  收敛速率显式地适应了这些常数。在 $m \ge n$ 的机制中，速率主要取决于 $\delta_2$（组内方差）。在 $n > m$ 的机制中，$\delta_1$ 和 $\delta_2$ 都会影响复杂度，但算法根据运行机制将它们解耦。

4. 统一现有方法

SILAGE 将现有方法统一为极限情况：

• 当 $n=1$（单个块）时，SILAGE 退化为 PAGE。
• 当 $m=1$（每个块只有一个样本）时，SILAGE 退化为 SILVER。

结果与收敛

论文提供了寻找 $\epsilon$-近似驻点（$\mathbb{E}[\|\nabla f(\tilde{x})\|^2] \le \epsilon$）的紧凑非凸收敛保证。

• 机制 $m \ge n$：
  梯度复杂度为 $\mathcal{O}\left(nm + \frac{(nL + \sqrt{nm}\delta_2)\Delta_0}{\epsilon}\right)$（假设精确初始化）。至关重要的是，领先项取决于 $\delta_2$（组内方差），而非全局平坦相似性或 $L_{\max}$。
• 机制 $n > m$：
  复杂度为 $\mathcal{O}\left(nm + \frac{(mL + m\sqrt{n-m}\delta_1 + \sqrt{nm}\delta_2)\Delta_0}{\epsilon}\right)$。
  在此，算法平衡了跨组异质性 ($\delta_1$) 和组内异质性 ($\delta_2$) 的成本。

与基准方法相比：

• 对比 ZeroSARAH： SILAGE 用结构化的 $L, \delta_1, \delta_2$ 取代了最坏情况下的 $L_{\max}$，提供了显著的改进。
• 对比 SILVER： SILAGE 在实现相似或更优的梯度复杂度时，将内存从 $\mathcal{O}(nm)$ 降低到了 $\mathcal{O}(n)$。
• 对比 D-PAGE： 虽然 D-PAGE 提供了具有竞争力的复杂度，但它需要周期性的全局刷新。SILAGE 彻底消除了这些刷新，通过增加极少量的内存（从 $\mathcal{O}(1)$ 到 $\mathcal{O}(n)$）换取了消除大规模中心化训练中最昂贵操作的能力。

意义与主张

作者声称 SILAGE 解决了中心化大规模优化中的一个基本扩展瓶颈。通过主动利用嵌套的双重求和结构，SILAGE 实现了“两全其美”的方案：

1. 它避免了递归估计器所需的周期性全局全梯度刷新带来的计算瓶颈。
2. 它避免了存储每个样本控制变量所需的内存瓶颈。

论文强调，由于依赖于嵌套相似性常数 ($\delta_1, \delta_2$)，其理论速率比现有界限更具结构性紧凑性，而这些常数可以显著小于扁平化相似性常数或最坏情况下的平滑参数，特别是在存在冗余块或同质化孤岛的机制中。在合成非凸逻辑回归任务上的实验结果证实，SILAGE 的表现符合其理论预测，在嵌套相似性结构有利的情况下，其收敛速度快于基准方法。