論文の概要: Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds

• arxiv url: http://arxiv.org/abs/2509.13628v1
• Date: Wed, 17 Sep 2025 01:56:31 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-18 18:41:50.688828
• Title: Accelerated Gradient Methods with Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, and Large Deviation Bounds
• Title（参考訳）: Biased Gradient Estimates: Risk Sensitivity, High-Probability Guarantees, Large Deviation Bounds
• Authors: Mert Gürbüzbalaban, Yasa Syed, Necdet Serhat Aybat,
• Abstract要約: 一階法における収束率と強靭性への勾配のトレードオフについて検討する。 我々はロバスト制御理論からリスク・センシティブ・インデックス(RSI)を通してロバスト性を定量化する。 また、滑らかな凸関数に対するRSIと収束率境界との類似のトレードオフも観察する。
• 参考スコア（独自算出の注目度）: 12.025550076793396
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study trade-offs between convergence rate and robustness to gradient errors in first-order methods. Our focus is on generalized momentum methods (GMMs), a class that includes Nesterov's accelerated gradient, heavy-ball, and gradient descent. We allow stochastic gradient errors that may be adversarial and biased, and quantify robustness via the risk-sensitive index (RSI) from robust control theory. For quadratic objectives with i.i.d. Gaussian noise, we give closed-form expressions for RSI using 2x2 Riccati equations, revealing a Pareto frontier between RSI and convergence rate over stepsize and momentum choices. We prove a large-deviation principle for time-averaged suboptimality and show that the rate function is, up to scaling, the convex conjugate of the RSI. We further connect RSI to the $H_{\infty}$-norm, showing that stronger worst-case robustness (smaller $H_{\infty}$ norm) yields sharper decay of tail probabilities. Beyond quadratics, under biased sub-Gaussian gradient errors, we derive non-asymptotic bounds on a finite-time analogue of the RSI, giving finite-time high-probability guarantees and large-deviation bounds. We also observe an analogous trade-off between RSI and convergence-rate bounds for smooth strongly convex functions. To our knowledge, these are the first non-asymptotic guarantees and risk-sensitive analysis of GMMs with biased gradients. Numerical experiments on robust regression illustrate the results.
• Abstract（参考訳）: 一階法における収束率と勾配誤差とのトレードオフについて検討する。 我々の焦点は一般化運動量法(GMM)であり、ネステロフの加速勾配、重ボール、勾配勾配を含むクラスである。 確率的勾配誤差を逆数・偏りとして許容し、ロバスト制御理論からリスク感応指数(RSI)を介してロバスト性を定量化する。 ガウス雑音の二次目的に対して、2x2 Riccati 方程式を用いて RSI に対して閉形式表現を行い、ステップサイズと運動量選択に対する収束率のパレートフロンティアを明らかにする。 我々は、時間平均的部分最適性に対する大きな決定原理を証明し、その速度関数がRSIの凸共役であることを示す。 さらに RSI を $H_{\infty}$-norm に結び付け、より強い最悪のケースのロバスト性 (より小さい$H_{\infty}$ノルム) がテール確率のよりシャープな崩壊をもたらすことを示す。 二次性を超えて、バイアス付き準ガウス勾配誤差の下では、RSIの有限時間アナログ上の非漸近境界を導出し、有限時間高確率保証と大偏差境界を与える。 また、滑らかな凸関数に対するRSIと収束率境界との類似のトレードオフも観察する。 我々の知る限り、これらは非漸近的保証であり、偏りのあるGMMのリスク感受性分析である。 頑健な回帰に関する数値実験は、その結果を示している。

関連論文リスト

• A Piecewise Lyapunov Analysis of Sub-quadratic SGD: Applications to Robust and Quantile Regression [22.917692982875025]
  一階微分しか持たない関数を$f$で扱える新しいLyapunov関数を導入する。 一般の減少段数と定数段数の下で有限時間モーメント境界を導出する。 我々の結果は、特にオンライン統計手法に広く応用されている。
  論文  参考訳（メタデータ） (2025-04-11T00:20:37Z)
• Faster Convergence of Stochastic Accelerated Gradient Descent under Interpolation [51.248784084461334]
  我々はNesterov加速度アンダーホ条件の一般化版に対する新しい収束率を証明した。 本分析により, 従来の研究に比べて, 強い成長定数への依存度を$$$から$sqrt$に下げることができた。
  論文  参考訳（メタデータ） (2024-04-03T00:41:19Z)
• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Distributionally Robust Optimization with Bias and Variance Reduction [9.341215359733601]
  勾配に基づくアルゴリズムであるProspectは、スムーズな正規化損失に対する線形収束を享受していることを示す。 また、勾配法のようなベースラインよりも2～3$times$早く収束できることも示している。
  論文  参考訳（メタデータ） (2023-10-21T00:03:54Z)
• Utilising the CLT Structure in Stochastic Gradient based Sampling : Improved Analysis and Faster Algorithms [14.174806471635403]
  粒子ダイナミック(IPD)に対するグラディエント・ランゲヴィン・ダイナミクス(SGLD)やランダムバッチ法(RBM)などのサンプリングアルゴリズムの近似を考察する。 近似によって生じる雑音は中央極限定理(CLT)によりほぼガウス的であるが、ブラウン運動はまさにガウス的である。 この構造を利用して拡散過程内の近似誤差を吸収し、これらのアルゴリズムの収束保証を改善する。
  論文  参考訳（メタデータ） (2022-06-08T10:17:40Z)
• On the Double Descent of Random Features Models Trained with SGD [78.0918823643911]
  勾配降下(SGD)により最適化された高次元におけるランダム特徴(RF)回帰特性について検討する。 本研究では, RF回帰の高精度な非漸近誤差境界を, 定常および適応的なステップサイズSGD設定の下で導出する。 理論的にも経験的にも二重降下現象を観察する。
  論文  参考訳（メタデータ） (2021-10-13T17:47:39Z)
• High-probability Bounds for Non-Convex Stochastic Optimization with Heavy Tails [55.561406656549686]
  我々は、勾配推定が末尾を持つ可能性のある一階アルゴリズムを用いたヒルベルト非最適化を考える。 本研究では, 勾配, 運動量, 正規化勾配勾配の収束を高確率臨界点に収束させることと, 円滑な損失に対する最もよく知られた繰り返しを示す。
  論文  参考訳（メタデータ） (2021-06-28T00:17:01Z)

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

指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。