小轮次下随机重排梯度下降可能极慢，尤其在病态问题中。
Incremental Gradient Descent with Small Epoch Counts is Surprisingly Slow on Ill-Conditioned Problems
- 分析确定性增量梯度下降（IGD）在小轮次下的收敛性
- 即使所有子函数强凸，小轮次时收敛仍可能极慢
- 适合研究小轮次优化行为的学者参考
近期理论研究表明，基于随机重排的SGD（如随机重排SGD）的收敛速度优于均匀采样SGD；然而这些研究主要集中在大轮次情形，即轮次数 $K$ 超过条件数 $κ$。相比之下，当 $K < κ$ 时知之甚少，且尚存开放问题：在小轮次下，基于重排的SGD能否更快收敛（Safran and Shamir, 2021）。为填补这一空白，我们研究了平滑且强凸函数上的朴素确定性变体——增量梯度下降（IGD）。我们的下界分析表明，在小轮次情形下，即使所有分量函数均为强凸，IGD仍可能表现出令人意外的缓慢收敛。此外，当部分分量函数允许非凸时，我们证明IGD在整个小轮次区间内的最优性差距可能显著更差。分析揭示，基于重排的SGD在小轮次下的收敛性质会因分量函数假设的不同而产生剧烈差异。最后，我们补充了IGD在大轮次情形下的紧致上下界。
原文摘要 · Abstract (English)
Recent theoretical results demonstrate that the convergence rates of permutation-based SGD (e.g., random reshuffling SGD) are faster than uniform-sampling SGD; however, these studies focus mainly on the large epoch regime, where the number of epochs $K$ exceeds the condition number $κ$. In contrast, little is known when $K$ is smaller than $κ$, and it is still a challenging open question whether permutation-based SGD can converge faster in this small epoch regime (Safran and Shamir, 2021). As a step toward understanding this gap, we study the naive deterministic variant, Incremental Gradient Descent (IGD), on smooth and strongly convex functions. Our lower bounds reveal that for the small epoch regime, IGD can exhibit surprisingly slow convergence even when all component functions are strongly convex. Furthermore, when some component functions are allowed to be nonconvex, we prove that the optimality gap of IGD can be significantly worse throughout the small epoch regime. Our analyses reveal that the convergence properties of permutation-based SGD in the small epoch regime may vary drastically depending on the assumptions on component functions. Lastly, we supplement the paper with tight upper and lower bounds for IGD in the large epoch regime.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。