提出贪心步长SGD在光滑二次函数中实现1/t^{3/4}收敛率。
Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
- 引入随机压缩过程，通过特征值方程分析迭代行为。
- 证明t步迭代达到O(1/t^{3/4})收敛速度，优于此前O(1/t^{1/2})。
- 适用于求解线性系统与优化问题的算法设计者。
我们研究在插值条件下，贪心步长随机梯度下降（SGD）对光滑二次函数的末次迭代收敛性，该设置涵盖了经典随机Kaczmarz算法及其他流行的迭代线性系统求解器。对于这些方法，我们证明第t次迭代可达到O(1/t^{3/4})的收敛速率，解决了Attia、Schliserman、Sherman和Koren提出的疑问，他们此前仅给出O(1/t^{1/2})的保证。证明中引入了随机压缩过程族，其动态可通过特定确定性特征值方程描述，并通过精细的离散-连续化分析进行研究。
原文摘要 · Abstract (English)
We study last-iterate convergence of SGD with greedy step size over smooth quadratics in the interpolation regime, a setting which captures the classical Randomized Kaczmarz algorithm as well as other popular iterative linear system solvers. For these methods, we show that the $t$-th iterate attains an $O(1/t^{3/4})$ convergence rate, addressing a question posed by Attia, Schliserman, Sherman, and Koren, who gave an $O(1/t^{1/2})$ guarantee for this setting. In the proof, we introduce the family of stochastic contraction processes, whose behavior can be described by the evolution of a certain deterministic eigenvalue equation, which we analyze via a careful discrete-to-continuous reduction.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。