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

• arxiv url: http://arxiv.org/abs/2509.13628v2
• Date: Fri, 19 Sep 2025 13:19:22 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-09-22 12:06:46.397264
• 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 the context of first-order methods. Our focus is on generalized momentum methods (GMMs)--a broad class that includes Nesterov's accelerated gradient, heavy-ball, and gradient descent methods--for minimizing smooth strongly convex objectives. We allow stochastic gradient errors that may be adversarial and biased, and quantify robustness of these methods to gradient errors 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 in terms of solutions to 2x2 matrix Riccati equations, revealing a Pareto frontier between RSI and convergence rate over the choice of step-size and momentum parameters. We then prove a large-deviation principle for time-averaged suboptimality in the large iteration limit and show that the rate function is, up to a scaling, the convex conjugate of the RSI function. We further show that the rate function and RSI are linked to the $H_\infty$-norm--a measure of robustness to the worst-case deterministic gradient errors--so that stronger worst-case robustness (smaller $H_\infty$-norm) leads to sharper decay of the tail probabilities for the average suboptimality. Beyond quadratics, under potentially biased sub-Gaussian gradient errors, we derive non-asymptotic bounds on a finite-time analogue of the RSI, yielding finite-time high-probability guarantees and non-asymptotic large-deviation bounds for the averaged iterates. In the case of smooth strongly convex functions, we also observe an analogous trade-off between RSI and convergence-rate bounds. To our knowledge, these are the first non-asymptotic guarantees for GMMs with biased gradients and the first risk-sensitive analysis of GMMs. Finally, we provide numerical experiments on a robust regression problem to illustrate our results.
• Abstract（参考訳）: 収束率と勾配誤差に対する頑健性の間のトレードオフを1次手法の文脈で検討する。 我々の焦点は一般化運動量法(GMM)であり、スムーズな凸目標を最小化するためにネステロフの加速勾配、重ボール、勾配降下法を含む幅広いクラスである。 我々は, 確率的勾配誤差を逆数および偏りのあるものとし, 頑健な制御理論からリスク感応指数(RSI)を用いて, これらの手法の頑健さを定量化する。 ガウス雑音の二次目的に対して、2x2行列 Riccati 方程式の解という観点から RSI に対して閉形式表現を与え、ステップサイズと運動量パラメータの選択に対する RSI と収束率の間のパレートフロンティアを明らかにする。 次に, 時間平均的部分最適性に対する大域的決定原理を大反復極限で証明し, RSI関数の凸共役(convex conjungate)であることを示す。 さらに、レート関数とRSIは、最低ケース決定的勾配誤差に対するロバスト性(英語版)の尺度である$H_\infty$-norm(英語版)とリンクしていることを示し、したがって、より強い最悪のケースのロバスト性(より小さい$H_\infty$-norm)は、平均的な準最適性に対するテール確率のより急激な崩壊をもたらす。 二次性を超えて、潜在的にバイアスのある準ガウス勾配誤差の下では、RSIの有限時間アナログ上の非漸近境界を導出し、有限時間高確率保証と平均化されたイテレートに対する非漸近大偏差を与える。 滑らかな凸関数の場合、RSIと収束率境界との間の類似のトレードオフも観察する。 我々の知る限り、これらは偏りのあるGMMに対する最初の非漸近的保証であり、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)

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

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