有限和优化问题的重球随机重排法收敛性分析

《Communications in Nonlinear Science and Numerical Simulation》：Convergence Analysis of the Heavy-Ball Random Reshuffling Method for Finite-sum Optimization

　　

### 摘要
本文提出了一种重球随机重排（HBRR）方法，该方法在标准随机重排（RR）算法的基础上，引入了经典的 重球（Heavy-Ball）动量机制。我们对 HBRR 在强凸、一般凸以及非凸有限和 优化问题下，采用常步长时的收敛性质进行了系统性分析。针对强凸目标函数，我们证明了期望平方距离线性 收缩至一个依赖于步长的残差邻域；针对一般凸目标函数，我们推导了平均迭代序列的函数值误差的子线性收敛界；针对非凸目标函数，我们获得的复杂度界与 RR 处于同一量级。在 Polyak-?ojasiewicz 条件下，期望函数值误差 线性收缩至残差邻域，且当残差消失时精确收敛。所构建的理论框架具有一致性，即当动量参数为零时，该框架精确退化为标准的 RR 收敛结果。在四个基准数据集上的数值实验表明，在 所有测试场景中，HBRR 在收敛速度、解精度和算法稳定性方面均展现出具有竞争力或更优的性能，从而证实了将重球动量整合进随机重排框架的有效性。

### 引言
考虑如下形式的有限和优化问题：
$$\min_{x \in \mathbb{R}^d} f(x) = \frac{1}{n} \sum_{i=1}^{n} f_i(x),$$
其中 $x \in \mathbb{R}^d$ 表示模型参数，$f_i(x)$ 是对应第 $i$ 个样本的局部损失函数。此类问题在机器学习、深度学习和大规模数据分析中经常 出现 [1], [2], [3], [4]。

随机梯度下降（SGD）方法及其变体是求解问题 (1.1) 的典型方法。在标准 SGD 迭代中，通常采用有放回抽样；构造的随机梯度往往具有较高方差，这可能影响收敛速率和最终精度。相比之下，随机重排（RR）方法采用无放回抽样策略，可以更充分地利用有限和结构，因而在理论和实践上均展现出良好的性能 [5], [6], [7], [8], [9], [10], [11]。近年来，在 RR 方法研究方面取得了一系列进展。Shamir [5] 对无放回抽样的随机梯度方法进行了系统性分析；HaoChen 和 Sra [6] 证明在有限 轮次后，RR 能够达到优于经典 SGD 的收敛速率；Gürbüzbalaban 等人 [7] 进一步展示了在强凸条件下 RR 相对于 SGD 的优势；Nagaraj 等人 [8] 为一般光滑凸函数上的无放回抽样 SGD 给出了更尖锐的收敛速率；关于早期分析中常用的有界梯度假设，Safran 和 Shamir [9] 研究了随机重排 SGD 的理论性质；在该设定下，Mishchenko 等人 [10] 给出了 RR 的上界，而 Nguyen 等人 [11] 进一步为 重排类梯度方法建立了统一的分析框架。除 RR 外，还可以考虑另外两种数据访问顺序策略：一次洗牌（SO）和增量梯度（IG）[10]。SO 仅在训练开始时对数据集进行一次随机排列，并在所有后续轮次中 使用固定的顺序；IG 则从确定性顺序开始，在每一轮中以固定或对抗方式依次处理样本，本质上是一种非随机遍历。

在优化中，引入动量项是提高算法性能的一项重要技术 [12]。经典的重球（HB）动量通过积累历史方向信息，常常能够加速高条件数问题的收敛，并减少平坦局部几何结构或高噪声区域中的迭代振荡。同时，Nesterov 型加速及相关动量变体在大规模学习问题中也展现了良好的数值性能 [13], [14], [15]。对于重排方法，Tran 等人 [16] 提出了一种带动量的洗牌梯度方法；Jiang 等人 [17] 考察了一种结合动量和方差缩减的重排方法。此外，关于随机重排和方差缩减的相关研究还包括 [18], [19]。Zeng 等人 [20] 利用 HB 动量进一步加速随机对偶坐标下降以求解线性约束优化问题；Wang 等人 [21] 提出了 AdaGC 算法，通过结合梯度偏差校正与动量项来改进迭代方向和步长，从而提高收敛效率；Yang [22] 提出了 SARAH-M 算法，在随机递归梯度下降框架中引入动量项，显著提升了收敛速度；Xie 等人 [23] 针对广义绝对值方程开发了随机迭代方法，并给出了可解性和误差界保证；Zhang 等人 [24] 设计了 FedFA 框架，利用动量梯度下降更新联邦学习微调中的轻量级适配器参数，加速模型收敛并减少资源消耗；Mei 等人 [25] 将动量对比学习模块引入法律判决预测模型，以增强特征判别能力，从而提高多任务分类性能。Qiu 等人 [26] 研究了带动量的随机重排（RRM），并在可变或递减步长下为非凸问题建立了复杂度和末次迭代收敛保证。这些工作表明，随机抽样和动量已成为该领域一个极具前景的研究方向。

受此启发，本文研究了一种基于 HB 动量的随机重排方法，即 HB 随机重排（HBRR）方法。我们研究常步长机制，该机制保持更新尺度固定，简化了实现和调参。我们针对强凸、一般凸、非凸以及 Polyak-?ojasiewicz (PL) 目标函数，推导了显式的收缩项和残差项。在数值实验中，我们将 HBRR 与现有的有限和方法进行比较。从算法角度来看，当问题具有高条件数或局部平坦几何结构时，RR 方法可能在迭代后期出现显著振荡或停滞；适当引入 HB 动量有望平滑优化轨迹，减少振荡，并提高算法稳定性。

本文的主要贡献有三点。首先，我们研究了采用常步长和显式 HB 动量的 HBRR 方法，阐明了其与 RR [10] 和 RRM [26] 的联系。其次，我们建立了强凸、一般凸和非凸条件下的收敛保证。在 PL 条件下，我们还证明了常步长下向残差邻域的线性收缩。第三，我们在强凸、一般凸和非凸模型上将 HBRR 与现有的有限和方法进行了比较。

本文的结构如下。第 2 节介绍 HBRR 方法的计算框架。第 3 节对 HBRR 进行收敛性分析。第 4 节通过数值实验考察 HBRR 的性能。第 5 节总结全文。

#### 2. HBRR 方法
我们采用双上标记号 $x^{(i,t)}$ 表示模型参数的迭代序列，其中轮次索引为 $t=0,1,\cdots,T-1$，步索引为 $i=0,1,\cdots,n-1$。在每一轮开始时，对样本索引集 $[n]:=\{1,2,\cdots,n\}$ 进行均匀无放回抽样，生成一个随机排列序列，记为 $U^{(t)}=(U^{(0,t)},U^{(1,t)},\cdots,U^{(n-1,t)})$。基于该序列，RR 方法依次计算局部梯度并更新参数。其更新规则为：
$$x^{(i+1,t)}$$

#### 3. 收敛性分析
本节系统地分析 HBRR 的收敛性，依次讨论 $\mu$-强凸、一般凸和非凸情况。首先，我们给出必要的定义、假设、引理及相关结果。

**定义 3.1** 设 $f:\mathbb{R}^d \to \mathbb{R}$ 为连续可微函数。若存在常数 $L>0$，使得对任意 $x,y\in\mathbb{R}^d$，有
$$\|\nabla f(x)-\nabla f(y)\| \leq L\|x-y\|,$$
则称 $f$ 是 $L$-光滑的。

**定义 3.2** 设 $f:\mathbb{R}^d \to \mathbb{R}$ 为连续可微函数。若存在常数 $\mu>0$，使得对任意 $x,y\in\mathbb{R}^d$，有
$$f(x) \geq f(y) + \langle \text{...}$$

#### 4. 数值实验
本节在强凸、一般凸和非凸问题上考察 HBRR 的经验性能，并将其与 SGD [1], [2], [3], [4]、IG [27]、RR [10] 和 RRM [26] 进行比较。我们还将 HBRR 与 RMSProp [28]、Adam [29] 和 AdamW [30] 进行对比。实验与理论章节保持一致：对于强凸问题，我们重点关注收敛速度、后期稳定性以及最终误差；对于一般凸问题，我们考察函数值的下降行为，以及…

#### 5. 结论
本文研究了一种 HB 随机重排（HBRR）方法，旨在进一步提高随机重排算法 [10] 的计算效率和误差分析。我们建立了强凸、一般凸和非凸目标函数的收敛结果。在 PL 条件下，我们还证明了常步长收缩。对于强凸目标函数，我们证明了终端误差至残差项的线性收缩。对于一般凸目标函数，我们推导了一个…

未引用浮标
图 6。
未引用参考文献
[33], [34], [35], [36], [37], [38], [39]。
CRediT 作者贡献声明
Wei-Hao Li：撰写—原稿撰写，软件，资源，数据整理。Nian-Ci Wu：撰写—审阅与编辑，监督，方法学。
利益冲突声明
作者声明，他们没有已知的、可能影响本文所报告工作的竞争经济利益或个人关系。
Wei-Hao Li | Nian-Ci Wu
中南民族大学数学与统计学院，武汉，430074，中华人民共和国