非凸有限和优化的加速方差缩减随机重排梯度下降算法：理论收敛性与应用验证

《Expert Systems with Applications》：Accelerated variance-reduced random reshuffling gradient descent algorithm for nonconvex finite-sum optimization

本文提出了一种创新的加速方差缩减随机重排梯度下降算法（AVR-RRGD），通过结合负动量（negative momentum）与方差缩减技术，有效解决了非凸有限和优化中随机重排（RR）引起的梯度方差问题。研究在KL（Kurdyka-?ojasiewicz）不等式框架下建立了强极限点收敛性，并推导出依赖于KL指数p的收敛速率。在岭回归和逻辑回归任务上的实验验证了算法的高效性，为大规模非凸优化（如神经网络训练）提供了新思路。

　　

亮点（Highlights）

• •
  提出融合负动量与方差缩减的随机重排梯度算法（AVR-RRGD），显著降低随机采样方差
• •
  在梯度Lipschitz连续性与KL不等式假设下，首次建立非凸设置中随机重排的强极限点收敛理论
• •
  推导基于KL指数^p的收敛速率（次线性/线性），并拓展至完全随机环境
• •
  岭回归与逻辑回归实验证实算法在基准数据集上优于现有方法

收敛性分析（Convergence analysis）

本研究强调算法1本质为随机过程，其随机性源于每轮迭代中随机排列{σ_t}的选择。我们首先分析随机轨迹{x_t}的收敛特性，尽管分析框架为确定性，但可直接推导出几乎必然收敛结果。在梯度Lipschitz连续性假设与适当步长条件下，我们逐步证明：

1. 1.
   算法梯度范数的弱收敛性
2. 2.
   基于KL性质的强极限点收敛
3. 3.
   在PL（Polyak-?ojasiewicz）条件下的线性收敛速率
4. 4.
   动态步长策略下的扩展收敛保证

数值实验（Numerical experiments）

本节对比AVR-RRGD与标准RR算法，重点评估：

1. 1.
   算法在正则化岭回归/逻辑回归任务上的性能优势
2. 2.
   动量参数θ∈(0,1]的数值影响
   所有数据源自LIBSVM库，实验表明AVR-RRGD在收敛速度与稳定性上显著优于对照方法，尤其在高维数据场景下方差控制效果突出。

结论（Conclusion）

本研究通过整合负动量与方差缩减技术，提出解决非凸有限和优化的创新算法。理论层面建立了随机重排框架下首例强收敛性证明，实验验证了算法在经典机器学习任务上的有效性，为大规模非凸优化提供了新范式。