論文の概要: Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms

• arxiv url: http://arxiv.org/abs/2209.11920v1
• Date: Sat, 24 Sep 2022 04:26:30 GMT
• ステータス: 処理完了
• システム内更新日: 2022-09-27 18:37:46.096533
• Title: Tradeoffs between convergence rate and noise amplification for momentum-based accelerated optimization algorithms
• Title（参考訳）: 運動量に基づく高速化アルゴリズムにおける収束速度と雑音増幅のトレードオフ
• Authors: Hesameddin Mohammadi, Meisam Razaviyayn, Mihailo R. Jovanovi\'c
• Abstract要約: モーメントに基づく1次最適化アルゴリズムについて検討し,2つのステップから情報を利用する。 強い凸2次問題に対しては、雑音増幅の定量化のために最適化変数における誤差の定常分散を用いる。 連続時間勾配流力学のクラスでは、適切な離散化は2段階の運動量アルゴリズムをもたらす。
• 参考スコア（独自算出の注目度）: 9.646922337783135
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study momentum-based first-order optimization algorithms in which the iterations utilize information from the two previous steps and are subject to an additive white noise. This class of algorithms includes heavy-ball and Nesterov's accelerated methods as special cases. For strongly convex quadratic problems, we use the steady-state variance of the error in the optimization variable to quantify noise amplification and exploit a novel geometric viewpoint to establish analytical lower bounds on the product between the settling time and the smallest/largest achievable noise amplification. For all stabilizing parameters, these bounds scale quadratically with the condition number. We also use the geometric insight developed in the paper to introduce two parameterized families of algorithms that strike a balance between noise amplification and settling time while preserving order-wise Pareto optimality. Finally, for a class of continuous-time gradient flow dynamics, whose suitable discretization yields two-step momentum algorithm, we establish analogous lower bounds that also scale quadratically with the condition number.
• Abstract（参考訳）: モーメントに基づく1次最適化アルゴリズムについて検討し,2つのステップからの情報を利用して付加的な白色雑音を受ける。 このアルゴリズムには特別な場合としてヘビーボールとネステロフの加速法が含まれる。 強凸二次問題に対しては、最適化変数における誤差の定常分散を用いてノイズ増幅を定量化し、新しい幾何学的視点を用いて沈降時間と最小・最大・最大雑音増幅の間の積上の解析的下界を確立する。 すべての安定化パラメータに対して、これらの境界は条件数と2次的にスケールする。 また,本論文で開発された幾何学的洞察を用いて,ノイズ増幅と沈下時間のバランスを保ちながら,次数的にパレートの最適性を保つ2つのパラメータ化アルゴリズムを導入する。 最後に,二段階運動量アルゴリズムを適度に導出する連続時間勾配流力学のクラスに対して,条件数と二乗的にスケールする類似の下界を定式化する。

関連論文リスト

• Breaking the Heavy-Tailed Noise Barrier in Stochastic Optimization Problems [56.86067111855056]
  構造密度の重み付き雑音によるクリップ最適化問題を考察する。 勾配が有限の順序モーメントを持つとき、$mathcalO(K-(alpha - 1)/alpha)$よりも高速な収束率が得られることを示す。 得られた推定値が無視可能なバイアスと制御可能な分散を持つことを示す。
  論文  参考訳（メタデータ） (2023-11-07T17:39:17Z)
• Accelerated stochastic approximation with state-dependent noise [7.4648480208501455]
  勾配観測における2次雑音に対する一般仮定の下での滑らかな凸最適化問題を考察する。 このような問題は、統計学におけるよく知られた一般化された線形回帰問題において、様々な応用において自然に発生する。 SAGDとSGEは、適切な条件下で、最適収束率を達成することを示す。
  論文  参考訳（メタデータ） (2023-07-04T06:06:10Z)
• First Order Methods with Markovian Noise: from Acceleration to Variational Inequalities [91.46841922915418]
  本稿では,一階変分法の理論解析のための統一的アプローチを提案する。 提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。 凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
  論文  参考訳（メタデータ） (2023-05-25T11:11:31Z)
• Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent Flows [4.817429789586127]
  本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。 提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
  論文  参考訳（メタデータ） (2021-12-02T16:04:40Z)
• On the Convergence of Stochastic Extragradient for Bilinear Games with Restarted Iteration Averaging [96.13485146617322]
  本稿では, ステップサイズが一定であるSEG法の解析を行い, 良好な収束をもたらす手法のバリエーションを示す。 平均化で拡張した場合、SEGはナッシュ平衡に確実に収束し、スケジュールされた再起動手順を組み込むことで、その速度が確実に加速されることを証明した。
  論文  参考訳（メタデータ） (2021-06-30T17:51:36Z)
• High Probability Complexity Bounds for Non-Smooth Stochastic Optimization with Heavy-Tailed Noise [51.31435087414348]
  アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。 非滑らか凸最適化の既存の方法は、信頼度に依存した複雑性境界を持つ。 そこで我々は,勾配クリッピングを伴う2つの手法に対して,新たなステップサイズルールを提案する。
  論文  参考訳（メタデータ） (2021-06-10T17:54:21Z)
• Convergence of adaptive algorithms for weakly convex constrained optimization [59.36386973876765]
  モローエンベロープの勾配のノルムに対して$mathcaltilde O(t-1/4)$収束率を証明する。 我々の分析では、最小バッチサイズが1ドル、定数が1位と2位のモーメントパラメータが1ドル、そしておそらくスムーズな最適化ドメインで機能する。
  論文  参考訳（メタデータ） (2020-06-11T17:43:19Z)
• Stochastic Optimization with Heavy-Tailed Noise via Accelerated Gradient Clipping [69.9674326582747]
  そこで本研究では,重み付き分散雑音を用いたスムーズな凸最適化のための,クリップ付きSSTMと呼ばれる新しい1次高速化手法を提案する。 この場合、最先端の結果を上回る新たな複雑さが証明される。 本研究は,SGDにおいて,ノイズに対する光細かな仮定を伴わずにクリッピングを施した最初の非自明な高確率複雑性境界を導出した。
  論文  参考訳（メタデータ） (2020-05-21T17:05:27Z)

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

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