論文の概要: When Momentum Helps Polyak--Ruppert Averaging
- arxiv url: http://arxiv.org/abs/2610.27990v1
- Date: Tue, 20 Oct 2026 10:29:50 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-10-21 21:58:47.763797
- Title: When Momentum Helps Polyak--Ruppert Averaging
- Title（参考訳）: MomentumがPolyakを助けるとき--Ruppert平均化
- Abstract要約: 有限ランの到達速度と、それらがどの程度並列化できるかを特徴付ける。
加法雑音を伴う強凸二次群に対しては、オンライン・オフライン橋の証明を行う。
- 参考スコア（独自算出の注目度）: 75.70186756364649
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Polyak--Ruppert averaging gives SGD and momentum methods the same asymptotic covariance. We characterize how fast finite runs reach it and how far they can be parallelized. For strongly convex quadratics with additive noise, we prove an online--offline bridge: the empirical risk minimizer on the samples of a tail average is one Newton step from the tail-averaged query point of any online procedure. For SGD, heavy ball, and Nesterov's method with constant momentum, this step is a boundary term at the two ends of the tail and splits the gap to the offline estimator into center, covariance, and shape errors. Necessary and sufficient conditions show that, on the least curved direction, the center error sets the pace: SGD needs $m\ggκ^2$ rounds but momentum only $m\ggκ$, where $κ$ is the condition number, so at sample size $N$ the critical batch size grows from $Θ(\sqrt{N}/κ)$ to $Θ(\sqrt{N/κ})$. The covariance error separates the momentum methods: heavy ball has relative variance excess $Θ(κ^{3/2}/m)$ along the stiffest direction, whereas Nesterov has relative error $O(\sqrtκ/m)$ in every direction. The shape error is method-independent by a Berry--Esseen bound uniform in $κ$ and batch size, so confidence intervals are valid when the other two errors vanish. We further examine how the conclusions change under heavy-tailed or state-dependent noise and clipping, and establish a first-order comparison with ERM for nonlinear Nesterov averaging under explicit conditions.
- Abstract（参考訳）: Polyak-Ruppert averaging は、SGD と運動量法に同じ漸近的共分散を与える。我々は、有限ランがそれに到達する速度と、それがどこまで並列化できるかを特徴付けている。
SGD, ヘビーボール, ネステロフの運動量一定の場合、このステップは尾部の2端の境界項であり、オフライン推定器とのギャップを中央、共分散、形状誤差に分割する。
SGD は $m\ggκ^2$ のラウンドを必要とするが、運動量のみ$m\ggκ$ であり、そこでは$κ$ は条件数であるので、サンプルサイズ$N$ のクリティカルバッチサイズは $ (\sqrt{N}/κ)$ から $ (\sqrt{N/κ})$ へと増加する。
この共分散誤差は運動量法を分離する: 重いボールは最も硬い方向に沿って、相対的な分散が$(κ^{3/2}/m)$ であるのに対して、ネステロフは全ての方向に相対的な誤差$O(\sqrtκ/m)$ を持つ。
形状誤差は、Berry-Esseen境界の均一な$κ$とバッチサイズでメソッド非依存であるため、他の2つのエラーが消えると、信頼区間が有効になる。
さらに、重み付きノイズや状態依存のノイズやクリッピングの下での結論の変化について検討し、明示的な条件下での非線形ネステロフ平均化におけるERMとの1次比較を確立する。
関連論文リスト
- WEIRDO: WEak resIdual Regularized DOob's h-transform diffusion alignment [0.0]
本研究では,拡散生成モデルを用いて学習した分布を推定する方法について検討する。
得られた誘導推定値の2乗誤差に基づいて高確率境界を導出する。
論文 参考訳（メタデータ） (2026-09-30T11:32:29Z) - Clipped or Unclipped? Finite-Sample Trade-offs for Averaged SGD under Heavy-Tailed Noise [66.13091490213743]
グラディエントクリッピングはトレーニングを安定させるために広く用いられているが、平均的なSGDの統計的精度を改善する必要はない。
有限条件の$p$-th モーメント,$pge2$ の条件下で, クリッピングおよび非クリッピングのPolyak-Ruppert平均 SGD の比較を導出した。
我々の主な結果は、$p>2$の場合、ガウス項が未開偏差境界を独占する明確な精度と信頼条件を与える。
論文 参考訳（メタデータ） (2026-09-26T21:47:14Z) - Ordinary Nonconvex SGD under Distance-Dependent Moments: Finite-Horizon Stationarity and Nagaev Bounds [1.6582968942719265]
一様雑音-モーメンタリティ境界は、距離によって変動が増加する勾配を除外する。
直接降下すると、スムーズな転位引数が3エプシロン6$を回復する。
局所化半径は、非レート仮定、クリッピング正規化、運動量、バッチサイズの増加といった境界から導かれる。
論文 参考訳（メタデータ） (2026-09-24T19:37:07Z) - Same Flow, Different Paths: Variance Reduction in Flow Matching [67.12978375116599]
最適化の観点から,この経路の選択について検討する。
我々の主な発見は、パス $g_t$ の選択は、SGDの収束率を根本的に変えることができるということである。
論文 参考訳（メタデータ） (2026-09-15T15:01:04Z) - Constrained Online Learning with Noisy Constraint Values [55.29259818039367]
一般的な実現可能性の下では、我々のLEDGERアルゴリズムは、期待される損失$O(sqrt T)と期待される予算違反$O(sqrtTlog(eT))を達成します。
スレーター条件、フィードバックチャネル間の独立性、絶対的制約値境界は不要である。
論文 参考訳（メタデータ） (2026-09-07T01:38:41Z) - When Does $\ell_2$-Boosting Overfit Benignly? High-Dimensional Risk Asymptotics and the $\ell_1$ Implicit Bias [15.113649527486276]
良性オーバーフィッティングが線形レートで失敗することを示します。
この局所化機構は信号の存在下で持続するべきであるが、正確な信号-雑音分解は未解決の問題である。
論文 参考訳（メタデータ） (2026-05-07T14:14:09Z) - Online Covariance Estimation in Averaged SGD: Improved Batch-Mean Rates and Minimax Optimality via Trajectory Regression [12.805268849262243]
我々はPolyak-Ruppert averaged gradient descent (SGD)のオンライン共分散行列推定について検討した。
この構造は、このボトルネックがSGDドリフトからヘッセンの情報をサブ線形に蓄積していることを明らかにする。
論文 参考訳（メタデータ） (2026-04-12T20:49:33Z) - Beyond likelihood ratio bias: Nested multi-time-scale stochastic approximation for likelihood-free parameter estimation [49.78792404811239]
確率分析形式が不明なシミュレーションベースモデルにおける推論について検討する。
我々は、スコアを同時に追跡し、パラメータ更新を駆動する比率のないネスト型マルチタイムスケール近似(SA)手法を用いる。
我々のアルゴリズムは、オリジナルのバイアス$Obig(sqrtfrac1Nbig)$を排除し、収束率を$Obig(beta_k+sqrtfracalpha_kNbig)$から加速できることを示す。
論文 参考訳（メタデータ） (2024-11-20T02:46:15Z) - Estimation of entropy-regularized optimal transport maps between
non-compactly supported measures [15.857723276537248]
本稿では,ガウシアン以下の音源と目標測度の間の2乗ユークリッドコストでエントロピー規則化された最適輸送マップを推定する問題に対処する。
論文 参考訳（メタデータ） (2023-11-20T17:18:21Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。