Greedy ステップサイズを用いた Randomized Kaczmarz と SGD の最後項収束性

arXiv cs.LG / 2026/4/14

💬 オピニオンSignals & Early TrendsIdeas & Deep AnalysisModels & Research

共有:

要点

本論文は、補間（interpolation）レジームにおける滑らかな二次問題で、greedy なステップサイズを用いた SGD の last-iterate（最後の反復）収束性を解析し、Randomized Kaczmarz をその特別な場合として含める。
先行研究で課され、検討されていた保証 O(1/t^{1/2}) を改善し、改善された 1反復あたりの収束率 O(1/t^{3/4}) を確立する。
著者らは、関連する決定論的な固有値方程式によってその力学が特徴づけられる確率的収縮過程の枠組みを導入する。
固有値方程式を調べ、収束境界を導くために、離散から連続への還元を用いた証明戦略を展開する。
全体として、本研究は、この設定においてより速い last-iterate 収束を達成することに関する Attia, Schliserman, Sherman, Koren からの未解決問題に答える。

本研究では、補間レジームにおけるなめらかな二次関数上での、貪欲なステップサイズによるSGDの「最後の反復」収束について調べる。この設定は、古典的なRandomized Kaczmarzアルゴリズムだけでなく、他のよく知られた反復型の線形システム解法も捉える。これらの方法について、

t

番目の反復が

O(1/t^{3/4})

の収束率を達成することを示す。これは、この設定に対して

O(1/t^{1/2})

の保証を与えたAttia、Schliserman、Sherman、Korenによって提起された問題に答えるものである。証明では、確率的収縮過程の族を導入し、その挙動は、ある決定論的な固有値方程式の進展によって記述できることを示す。さらに、その方程式を精密な離散から連続への還元によって解析する。

AI Business

日経XTECH

日経XTECH

日経XTECH

VentureBeat