通过并行架构实现随机梯度方法的自适应性

# 通过并行架构实现随机梯度方法的自适应性

来源：https://arxiv.org/html/2607.28902

###### 摘要

我们开发了一个并行框架，将静态梯度方法组装起来以实现更好的自适应性。静态梯度方法记为 \(\mathrm{GD}(x_{0},T)\)，它接受一个初始点 \(x_{0}\in\mathbb{R}^{n}\) 和一个指定迭代次数 \(\lfloor T\rfloor\) 的 \(T\in\mathbb{R}^{+}\) 作为输入。步长选择为 \(s=S(T)\)，其中 \(S(\cdot)\) 是 \(T\) 的预定函数。该方法随后执行迭代
\[
x_{i+1}=x_{i}-\frac{\eta}{s}\cdot g_{i},
\]
其中 \(g_{i}\) 是在 \(x_{i}\) 处评估的随机梯度，\(\eta\) 是缩放因子。对于整数 \(p\geq 1\)，所提出并行框架中的 \(p\) 个处理器根据几何序列搜索合适的 \(T\) 值，使得所得梯度下降满足所需的收敛条件。每个处理器执行由 \(i=1,2,\ldots\) 索引的无限阶段序列。在阶段 \(i\)，处理器 \(j\) 被分配 \(T_{j,i}=h(j,i)\)，其中 \(h:\mathbb{N}\times\mathbb{N}\rightarrow\mathbb{R}^{+}\) 是规定函数。处理器 \(j\)（\(j=0,1,\ldots,p-1\)）在阶段 \(i\) 执行 \(\mathrm{GD}(x_{0},T_{j,i})\)。并行框架的效率通过其 \((p,\alpha_{p})\) 近似保证来衡量。具体而言，对于每个整数 \(T\geq T_{0}\)，存在一个处理器 \(j\) 和一个阶段 \(i\)，使得
\[
T\leq T_{j,i}\leq T_{j,i}^{*}<\alpha_{p}T,
\]
其中 \(T_{j,i}^{*}=\sum_{t=1}^{i}T_{j,t}\) 是处理器 \(j\) 在完成阶段 \(i\) 之前累计执行的迭代次数。因此，\(T_{j,i}^{*}\) 表示处理器 \(j\) 在完成阶段 \(i\) 之前花费的总计算量。设
\[
h(j,i)=b_{p}^{jp+i}\cdot T_{0},
\]
其中 \(b_{p}=(p+1)^{1/p}\)，\(T_{0}\) 是每个处理器任何阶段所分配的最小迭代次数。我们证明该构造实现了 \((p,\alpha_{p})\) 近似，其中
\[
\alpha_{p}=\left(1+\frac{1}{p}\right)(p+1)^{1/p}
\leq 1+\frac{1+\ln(1+p)}{p}+\frac{1}{p^{2}}\left(2\left(\ln(1+p)\right)^{2}+\ln(1+p)\right).
\]
我们进一步证明一个下界：对于任何函数 \(h(j,i)\) 和任何常数 \(d>1\)，如果所得框架实现了 \((p,\alpha_{p})\) 近似，则对所有充分大的 \(p\)，必有
\[
\alpha_{p}\geq\left(1+\frac{1+\ln(1+p)}{p}-\frac{d\ln\ln p}{p}\right).
\]
由于静态梯度方法的收敛分析通常比自适应梯度方法简单得多，我们的并行框架能够在非凸目标函数 \(F(x)\) 上对梯度下降进行更简单的收敛分析，同时保留对参数（如 Lipschitz 光滑常数和随机梯度特征，例如方差或噪声水平）的自适应性。

## 1 引言

随机梯度下降（SGD）[24](https://arxiv.org/html/2607.28902#bib.bib24) 是深度学习中应用最广泛的优化方法之一，因为它在训练大规模神经网络时具有高效性和可扩展性。与每次迭代使用整个训练数据集计算梯度的批量梯度下降不同，SGD 使用单个训练样本或小批量来更新模型参数。因此，SGD 所需的内存显著减少，每次迭代的计算成本也更低。由于每一步只处理一小部分数据，SGD 在实践中往往收敛更快，尤其适用于大规模数据集。

具有递减步长的梯度下降有着悠久的历史。经典随机逼近理论表明，步长 \(\eta_{i}\) 应满足
\[
\sum_{i=1}^{\infty}\eta_{i}=+\infty
\quad\text{且}\quad
\sum_{i=1}^{\infty}\eta_{i}^{2}<+\infty
\]
以保证收敛到稳定点 [24](https://arxiv.org/html/2607.28902#bib.bib24)。对于光滑非凸函数的随机优化，采用常数步长或递减步长 \(\eta_{i}=O(1/\sqrt{i})\) 的梯度下降以 \(O(1/\sqrt{T})\) 的速率收敛到稳定点 [10](https://arxiv.org/html/2607.28902#bib.bib10)。特别地，[10](https://arxiv.org/html/2607.28902#bib.bib10) 中的分析将步长选择为
\[
\eta_{i}=\min\left(\frac{1}{L},\sqrt{\frac{2(F(x_{1})-F(x^{*}))}{L\sigma_{0}^{2}N}}\right),
\]
该步长依赖于 Lipschitz 光滑常数 \(L\)、随机梯度方差参数 \(\sigma_{0}\) 以及最优性间隙 \(F(x_{1})-F(x^{*})\)，其中 \(F(x^{*})=\inf_{x}(F(x))\)。由于这些与问题相关的参数通常事先未知，所得的静态梯度方法是非自适应的。此外，\(O(1/\sqrt{T})\) 的收敛速率已知是最优的，与相应的下界匹配 [3](https://arxiv.org/html/2607.28902#bib.bib3), [1](https://arxiv.org/html/2607.28902#bib.bib1)。

近年来，自适应梯度下降方法在深度学习中得到了广泛应用。与静态梯度方法不同，自适应方法在训练过程中根据各参数的梯度历史动态调整学习率。这种自适应机制减少了对学习率手动调节的需求，并在广泛的机器学习任务中通常能提高优化效率和鲁棒性。大量研究已在各种假设和优化设置下建立了自适应梯度方法的收敛保证和收敛速率 [8](https://arxiv.org/html/2607.28902#bib.bib8), [17](https://arxiv.org/html/2607.28902#bib.bib17), [19](https://arxiv.org/html/2607.28902#bib.bib19), [16](https://arxiv.org/html/2607.28902#bib.bib16), [27](https://arxiv.org/html/2607.28902#bib.bib27), [28](https://arxiv.org/html/2607.28902#bib.bib28), [29](https://arxiv.org/html/2607.28902#bib.bib29)。自 AdaGrad [8](https://arxiv.org/html/2607.28902#bib.bib8) 提出以来，已涌现出众多自适应梯度方法，包括 AdaDelta [29](https://arxiv.org/html/2607.28902#bib.bib29)、Adam [12](https://arxiv.org/html/2607.28902#bib.bib12)、AdamW [15](https://arxiv.org/html/2607.28902#bib.bib15)、AdaFTRL [20](https://arxiv.org/html/2607.28902#bib.bib20)、SGD-BB [25](https://arxiv.org/html/2607.28902#bib.bib25)、AdaBatch [7](https://arxiv.org/html/2607.28902#bib.bib7)、SC-AdaGrad [18](https://arxiv.org/html/2607.28902#bib.bib18)、AMSGrad [22](https://arxiv.org/html/2607.28902#bib.bib22) 和 Padam [4](https://arxiv.org/html/2607.28902#bib.bib4)。这些发展反映了通过提高效率、鲁棒性、理论保证以及大规模机器学习应用中的易用性来改进自适应梯度方法的持续努力。

自适应随机梯度下降方法根据预定义的更新规则动态调整步长。例如，AdaGrad-Norm [27](https://arxiv.org/html/2607.28902#bib.bib27) 将累积缩放因子和模型参数更新为
\[
s_{i+1}=s_{i}+\|G(\xi,x_{i})\|^{2},
\]
以及
\[
x_{i+1}=x_{i}-\frac{\eta}{\sqrt{s_{i+1}}}\cdot G(\xi,x_{i}),
\]
其中 \(G(\xi,x_{i})\) 表示在 \(x_{i}\) 处评估的随机梯度。自适应随机梯度方法的收敛性质已在 [27](https://arxiv.org/html/2607.28902#bib.bib27), [28](https://arxiv.org/html/2607.28902#bib.bib28), [9](https://arxiv.org/html/2607.28902#bib.bib9), [26](https://arxiv.org/html/2607.28902#bib.bib26) 中得到广泛研究。在适当假设下，这些方法被证明以最优收敛速率 \(O(1/\sqrt{N})\) 收敛到稳定点。

并行梯度下降已成为大规模机器学习和科学计算的重要优化框架，因为它能使梯度计算分布在多个处理器上，从而显著减少训练时间并提高可扩展性。并行和异步迭代优化的早期理论基础由 Dimitri P. Bertsekas 和 John N. Tsitsiklis 建立 [2](https://arxiv.org/html/2607.28902#bib.bib2)，他们分析了延迟和分布式更新下的收敛性质。后来，大规模机器学习推动了并行 SGD 算法的发展，如 Hogwild [21](https://arxiv.org/html/2607.28902#bib.bib21)、参数服务器架构 [14](https://arxiv.org/html/2607.28902#bib.bib14) 和分布式深度学习系统 [6](https://arxiv.org/html/2607.28902#bib.bib6)。近年来的自适应并行方法进一步将分布式计算与自适应学习率机制相结合，以获得更好的收敛行为 [23](https://arxiv.org/html/2607.28902#bib.bib23)。更近期的研究集中于自适应和通信高效的分布式优化，包括自适应 SGD 方法 [5](https://arxiv.org/html/2607.28902#bib.bib5) 和多时间尺度分布式自适应优化框架 [11](https://arxiv.org/html/2607.28902#bib.bib11)。

### 1.1 我们的贡献

我们的目标是通过并行框架赋予静态梯度方法自适应性。静态梯度方法记为 \(\mathrm{GD}(x_{0},T)\)，它接受一个初始点 \(x_{0}\) 和一个指定迭代次数的整数 \(T\) 作为输入。步长由 \(s=S(T)\) 决定，其中 \(S(\cdot)\) 是 \(T\) 的预定函数。该方法随后执行迭代
\[
x_{i+1}=x_{i}-\frac{\eta}{s}\cdot g_{i},
\]
其中 \(g_{i}\) 是在 \(x_{i}\) 处评估的随机梯度，\(\eta\) 是缩放因子。应用静态梯度方法的一个基本挑战是选择合适的 \(T\) 值。参数 \(T\) 必须足够大以保证期望的收敛性，但所需迭代次数通常依赖于未知的问题特征，如 Lipschitz 光滑常数和随机梯度参数。我们的并行框架通过并行执行来搜索合适的 \(T\) 值，从而解决了这一挑战。

我们为梯度下降开发了一个并行框架，该框架根据精心设计的几何序列并行搜索合适的迭代预算 \(T\)。该框架将多个静态梯度方法组装成一种自适应梯度下降方法。它由 \(p\) 个并行运行的处理器组成。在阶段 \(i\) 分配给处理器 \(j\) 的迭代次数由
\[
T_{j,i}=h(j,i)
\]
确定。处理器 \(j\)（\(j=0,1,\ldots,p-1\)）在阶段 \(i\) 执行 \(\mathrm{GD}(x_{0},T_{j,i})\)。我们选择
\[
h(j,i)=b_{p}^{jp+i}T_{0},
\]
其中 \(b_{p}=(p+1)^{1/p}\)，\(T_{0}\) 是任何阶段分配的最小迭代次数。我们证明，对于每个 \(T\geq T_{0}\)，存在一个处理器 \(j\) 和一个阶段 \(i\)，使得
\[
T\leq T_{j,i}\leq T_{j,i}^{*}<\alpha_{p}T,
\]
其中 \(T_{j,i}^{*}=\sum_{t=1}^{i}T_{j,t}\) 是处理器 \(j\) 在阶段 \(i\) 之前执行的总迭代次数，且
\[
\alpha_{p}=\left(1+\frac{1}{p}\right)(p+1)^{1/p}
\leq 1+\frac{1+\ln(1+p)}{p}+\frac{1}{p^{2}}\left(2(\ln(1+p))^{2}+\ln(1+p)\right).
\]
近似因子 \(\alpha_{p}\) 衡量在一个处理器达到足以满足期望收敛保证的迭代预算之前所产生的计算开销。\(\alpha_{p}\) 的值越小，表示在前面阶段浪费的迭代次数越少。

我们进一步通过证明以下结论建立了一个近乎匹配的下界：对于任何调度函数 \(h(j,i)\) 和任何常数 \(d>1\)，每个 \((p,\alpha_{p})\) 近似都必须满足
\[
\alpha_{p}\geq\left(1+\frac{1+\ln(1+p)}{p}-\frac{d\ln\ln p}{p}\right)
\]
对所有充分大的 \(p\) 成立。因此，所得并行算法的收敛行为与底层静态梯度方法 \(\mathrm{GD}(\cdot)\) 基本相同，后者的收敛性由迭代预算 \(T\) 决定。因此，我们的框架在保留静态梯度方法相对简单的收敛分析的同时，提供了并行搜索的自适应性。理论分析建立了 \(\alpha_{p}\) 的几乎匹配的上界和下界，揭示了并行性、自适应性和计算开销之间的内在权衡。

我们在以下 \((\lambda,\sigma_{0},\sigma_{1})\) 随机模型下开发了一种静态梯度下降方法。设 \(\xi\) 为随机变量，并设 \(G(\xi,x)\) 表示 \(F(x)\) 的随机梯度。我们假设
\[
\left\langle \mathbb{E}_{\xi}[G(\xi,x)],\nabla F(x)\right\rangle\geq\lambda\|\nabla F(x)\|^{2}
\]
对某个 \(\lambda\in(0,\infty)\) 成立；且
\[
\mathbb{E}_{\xi}\left[\|\nabla F(x)-G(\xi,x)\|^{2}\right]\leq\sigma_{0}^{2}+\sigma_{1}^{2}\|\nabla F(x)\|^{2}
\]
对某个 \(\sigma_{0},\sigma_{1}\in[0,\infty)\) 成立。该模型推广了标准随机梯度模型，后者假设
\[
\mathbb{E}_{\xi}[G(\xi,x)]=\nabla F(x),
\]
且
\[
\mathbb{E}_{\xi}\left[\|\nabla F(x)-G(\xi,x)\|^{2}\right]\leq\sigma_{0}^{2}
\]
对某个 \(\sigma_{0}\in[0,\infty)\) 成立。

严格分析随机和自适应梯度方法的收敛性对于理解其理论行为、改进其性能并确保其在一系列机器学习任务中的可靠性至关重要。此类分析还揭示了收敛性如何依赖于问题特征和算法超参数，从而指导设计更鲁棒的优化算法。据我们所知，在上述 \((\lambda,\sigma_{0},\sigma_{1})\) 随机模型下——其中三个参数 \(\lambda\)、\(\sigma_{0}\) 和 \(\sigma_{1}\) 均允许为正——的收敛保证在现有文献中尚未建立。我们在此模型下建立了以下收敛结果。

我们在所提出的 \((\lambda,\sigma_{0},\sigma_{1})\) 随机模型下开发了一种新的梯度下降方法。给定 \(T\) 步的迭代预算，该方法执行更新
\[
x_{j+1}=x_{j}-\frac{\eta}{s_{T}}G(\xi,x_{j}),
\]
其中
\[
s_{T}=2^{\left\lceil\frac{\lceil\log T\rceil}{2}\right\rceil},
\]
且 \(\eta>0\) 是任意输入参数。假设目标函数满足标准的 \(L\)-Lipschitz 光滑条件：
\[
\|\nabla F(x)-\nabla F(y)\|\leq L\|x-y\|,
\]