不依赖光滑性假设，提升随机梯度算法的收敛性理论与实用性
Revisiting Convergence: Shuffling Complexity Beyond Lipschitz Smoothness
- 摒弃传统Lipschitz光滑性假设，改用更宽松的有界方差条件
- 在非凸、强凸等三类情况下均达到最优收敛速率
- 适用于实际模型中常见不满足光滑性的场景
随机重排类梯度方法因简洁高效而广受青睐。尽管近年收敛性分析已取得进展，但多数结果依赖Lipschitz光滑性条件，该条件在常见机器学习模型中常不成立。本文通过具体反例揭示此问题，并在无需Lipschitz光滑性假设下重新研究此类算法的收敛速率。基于新的步长策略，算法在弱假设下仍能收敛，并达到当前最优收敛率。我们在随机重排和任意重排两种机制下，分别证明了非凸、强凸及非强凸情形下的收敛性，均基于一般有界方差条件。数值实验进一步验证了所提算法在实际中的有效性。
原文摘要 · Abstract (English)
Shuffling-type gradient methods are favored in practice for their simplicity and rapid empirical performance. Despite extensive development of convergence guarantees under various assumptions in recent years, most require the Lipschitz smoothness condition, which is often not met in common machine learning models. We highlight this issue with specific counterexamples. To address this gap, we revisit the convergence rates of shuffling-type gradient methods without assuming Lipschitz smoothness. Using our stepsize strategy, the shuffling-type gradient algorithm not only converges under weaker assumptions but also match the current best-known convergence rates, thereby broadening its applicability. We prove the convergence rates for nonconvex, strongly convex, and non-strongly convex cases, each under both random reshuffling and arbitrary shuffling schemes, under a general bounded variance condition. Numerical experiments further validate the performance of our shuffling-type gradient algorithm, underscoring its practical efficacy.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。