Fugu-MT 論文翻訳(概要): Last-Iterate Convergence of Randomized Kaczmarz and SGD with Greedy Step Size

論文の概要: 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
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})$保証を与える。本研究では,ある決定論的固有値方程式の進化によって振る舞いが説明できる確率的収縮過程のファミリを紹介する。

関連論文リスト

Finite-Time Analysis of Discounted Exponential-Utility Reinforcement Learning [9.748884794669346]
モデルなし割引指数効用強化学習における最初の有限時間保証を提供する。これらの結果は、モデルなし割引指数効用強化学習における最初の有限時間保証を提供する。
論文参考訳（メタデータ） (2026-08-03T08:50:07Z)
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)
High Probability Bounds for a Class of Nonconvex Algorithms with AdaGrad Stepsize [55.0090961425708]
本研究では,AdaGradのスムーズな非確率問題に対する簡易な高確率解析法を提案する。我々はモジュラーな方法で解析を行い、決定論的設定において相補的な$mathcal O (1 / TT)$収束率を得る。我々の知る限りでは、これは真に適応的なスキームを持つAdaGradにとって初めての高い確率である。
論文参考訳（メタデータ） (2022-04-06T13:50:33Z)
Optimal and instance-dependent guarantees for Markovian linear stochastic approximation [47.912511426974376]
標準スキームの最後の繰り返しの2乗誤差に対して、$t_mathrmmix tfracdn$の非漸近境界を示す。マルコフ雑音による政策評価について,これらの結果のまとめを導出する。
論文参考訳（メタデータ） (2021-12-23T18:47:50Z)
Navigating to the Best Policy in Markov Decision Processes [68.8204255655161]
マルコフ決定過程における純粋探索問題について検討する。エージェントはアクションを逐次選択し、結果のシステム軌道から可能な限り早くベストを目標とする。
論文参考訳（メタデータ） (2021-06-05T09:16:28Z)
ROOT-SGD: Sharp Nonasymptotics and Near-Optimal Asymptotics in a Single Algorithm [71.13558000599839]
第一次アルゴリズムを用いて,厳密な凸と滑らかな非制約最適化問題の解法について検討する。我々は,過去の勾配を平均化し,実装が容易な小説「Recursive One-Over-T SGD」を考案した。有限サンプル, 漸近感覚, 感覚の両面において, 最先端の性能を同時に達成できることを実証する。
論文参考訳（メタデータ） (2020-08-28T14:46:56Z)
On the Almost Sure Convergence of Stochastic Gradient Descent in Non-Convex Problems [75.58134963501094]
本稿では,勾配降下(SGD)の軌跡を解析する。我々はSGDが厳格なステップサイズポリシーのために1ドルでサドルポイント/マニフォールドを避けることを示す。
論文参考訳（メタデータ） (2020-06-19T14:11:26Z)
Almost sure convergence rates for Stochastic Gradient Descent and Stochastic Heavy Ball [17.33867778750777]
一般近似問題に対する勾配降下法(SGD)と重球法(SHB)について検討した。 SGD の場合、凸と滑らかな設定において、イテレートの重み付き平均に対して、最初の最も確実な収束式を提供する。
論文参考訳（メタデータ） (2020-06-14T11:12:05Z)

関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。