证明随机重排梯度法在非光滑凸优化中比普通近端梯度法更快收敛。
Improved Last-Iterate Convergence of Shuffling Gradient Methods for Nonsmooth Convex Optimization
- 提出非光滑凸优化下随机重排与单次重排的改进收敛分析
- 首次证明随机重排在一般凸情况下达到近乎最优收敛率
- 揭示随机性对优化速度的理论优势，适合关注算法性能的从业者
本文研究了用于最小化有限和函数（带正则化）的随机重排梯度方法的收敛性。该方法按随机排列的顺序逐个应用（近端）梯度下降。尽管其在实践中表现良好且实现简单，但理论理解仍不充分。近期工作（Liu & Zhou, 2024b）首次建立了各种设置下的最后迭代收敛结果，尤其在光滑（强）凸情形下证明了最优速率。然而，其对非光滑（强）凸函数的界仅与近端梯度下降相当。本文首次为非光滑情形提供改进的最后迭代分析，证明广泛使用的随机重排（RR）和单次重排（SS）策略均严格优于近端梯度下降，体现了随机性的优势。重要推论是，在一般凸情况下，首次获得随机重排采样下后缀平均的（近乎）最优收敛结果，与Koren等（2022）给出的下界一致。
原文摘要 · Abstract (English)
We study the convergence of the shuffling gradient method, a popular algorithm employed to minimize the finite-sum function with regularization, in which functions are passed to apply (Proximal) Gradient Descent (GD) one by one whose order is determined by a permutation on the indices of functions. In contrast to its easy implementation and effective performance in practice, the theoretical understanding remains limited. A recent advance by (Liu & Zhou, 2024b) establishes the first last-iterate convergence results under various settings, especially proving the optimal rates for smooth (strongly) convex optimization. However, their bounds for nonsmooth (strongly) convex functions are only as fast as Proximal GD. In this work, we provide the first improved last-iterate analysis for the nonsmooth case demonstrating that the widely used Random Reshuffle ($\textsf{RR}$) and Single Shuffle ($\textsf{SS}$) strategies are both provably faster than Proximal GD, reflecting the benefit of randomness. As an important implication, we give the first (nearly) optimal convergence result for the suffix average under the $\textsf{RR}$ sampling scheme in the general convex case, matching the lower bound shown by (Koren et al., 2022).
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。