論文の概要: Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
- arxiv url: http://arxiv.org/abs/2604.09909v1
- Date: Fri, 10 Apr 2026 21:09:52 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-04-14 20:13:15.742782
- Title: Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size
- Title（参考訳）: グレディステップサイズを有するランダム化KaczmarzとSGDのLast-Iterate Convergence
- Authors: Michał Dereziński, Xiaoyu Dong,
- Abstract要約: 本研究では,SGDの2次スムーズなステップサイズにおける最終点収束について検討した。
我々は、ある決定論的固有値方程式の進化によって記述できる、離散収縮過程の族を紹介する。
- 参考スコア（独自算出の注目度）: 4.3761172849639705
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: 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.
- Abstract（参考訳）: 本稿では,古典的ランダム化カッツマルツアルゴリズムや,他のよく知られた反復線形システム解法をとらえた,補間系における滑らかな2次数に対して,SGDの最終定値収束度と欲求的なステップサイズについて検討する。
これらの方法では、$t$-thイテレートが$O(1/t^{3/4})$収束率に達し、Attia, Schliserman, Sherman, Korenによって提起された質問に対処し、この設定に対して$O(1/t^{1/2})$保証を与える。
本研究では,ある決定論的固有値方程式の進化によって振る舞いが説明できる確率的収縮過程のファミリを紹介する。
関連論文リスト
- Bayesian Risk-Sensitive Policy Optimization For MDPs With General Loss Functions [8.16996766356341]
我々は、一般的な損失関数と未知のパラメータを持つマルコフ決定過程(MDP)を考察する。
我々はベイズ的手法を用いてデータからパラメータを推定し、損失にコヒーレントなリスク関数を課す。
本稿では,コヒーレントリスク尺度の二重表現を利用した政策勾配最適化手法を提案する。
論文 参考訳（メタデータ） (2025-09-19T01:16:59Z) - Fast Last-Iterate Convergence of SGD in the Smooth Interpolation Regime [26.711510824243803]
本研究では, 最適騒音が0または0に近い政権において, 円滑な凸目標に対する勾配降下(SGD)の集団収束保証について検討した。
十分に調整されたステップサイズでは、最後の繰り返しに対してほぼ最適な$widetildeO (1/T + sigma_star/sqrtT)$レートを得る。
論文 参考訳（メタデータ） (2025-07-15T12:52:47Z) - From Continual Learning to SGD and Back: Better Rates for Continual Linear Models [50.11453013647086]
以前見られたタスクの損失を、$k$の繰り返しの後、忘れること、すなわち、分析する。
実現可能な最小二乗の設定において、新しい最上界を創出する。
我々は、タスクを繰り返しないランダム化だけで、十分に長いタスクシーケンスで破滅的な事態を防げることを初めて証明した。
論文 参考訳（メタデータ） (2025-04-06T18:39:45Z) - Nonasymptotic Analysis of Stochastic Gradient Descent with the Richardson-Romberg Extrapolation [22.652143194356864]
本研究では, 勾配勾配勾配(SGD)を一定のステップサイズで解くことで, 密接な凸と滑らかな問題を解く問題に対処する。
得られた推定子の平均二乗誤差を、反復数$n$に対して拡張する。
我々の分析は、時相マルコフ連鎖と見なされるSGDの特性に依存している。
論文 参考訳（メタデータ） (2024-10-07T15:02:48Z) - Combinatorial Stochastic-Greedy Bandit [79.1700188160944]
我々は,選択した$n$のアームセットのジョイント報酬以外の余分な情報が観測されない場合に,マルチアームのバンディット問題に対する新規グリーディ・バンディット(SGB)アルゴリズムを提案する。
SGBは最適化された拡張型コミットアプローチを採用しており、ベースアームの大きなセットを持つシナリオ用に特別に設計されている。
論文 参考訳（メタデータ） (2023-12-13T11:08:25Z) - Extra-Newton: A First Approach to Noise-Adaptive Accelerated
Second-Order Methods [57.050204432302195]
本研究では,2次スムーズな凸関数を最小化するための普遍的かつ適応的な2次法を提案する。
我々のアルゴリズムは、オラクルフィードバックが分散$sigma2$であるときに$O(sigma / sqrtT)$収束を達成し、決定論的オラクルで$O(1 / T3)$に収束を改善する。
論文 参考訳（メタデータ） (2022-11-03T14:12:51Z) - Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。
マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文 参考訳（メタデータ） (2021-12-23T18:47:50Z) - On the Almost Sure Convergence of Stochastic Gradient Descent in
Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。
我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文 参考訳（メタデータ） (2020-06-19T14:11:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。