論文の概要: 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つのパラメータ化アルゴリズムを導入する。
最後に,二段階運動量アルゴリズムを適度に導出する連続時間勾配流力学のクラスに対して,条件数と二乗的にスケールする類似の下界を定式化する。
関連論文リスト
- Variational quantum algorithm for enhanced continuous variable optical
phase sensing [0.0]
変分量子アルゴリズム(VQA)は、ノイズ量子デバイスにおける幅広い問題に対処するために用いられるハイブリッド量子古典的アプローチである。
本研究では, 連続変数プラットフォーム上でのパラメータ推定の最適化のために, 圧縮光に基づく変分アルゴリズムを実装した。
論文 参考訳(メタデータ) (2023-12-21T14:11:05Z) - First Order Methods with Markovian Noise: from Acceleration to
Variational Inequalities [114.69800889030142]
本稿では,一階変分法の理論解析のための統一的アプローチを提案する。
提案手法は非線形勾配問題とモンテカルロの強い問題の両方をカバーする。
凸法最適化問題の場合、オラクルに強く一致するような境界を与える。
論文 参考訳(メタデータ) (2023-05-25T11:11:31Z) - Accelerated First-Order Optimization under Nonlinear Constraints [73.2273449996098]
我々は、制約付き最適化のための一階アルゴリズムと非滑らかなシステムの間で、新しい一階アルゴリズムのクラスを設計する。
これらのアルゴリズムの重要な性質は、制約がスパース変数の代わりに速度で表されることである。
論文 参考訳(メタデータ) (2023-02-01T08:50:48Z) - Formal guarantees for heuristic optimization algorithms used in machine
learning [6.978625807687497]
グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。
本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
論文 参考訳(メタデータ) (2022-07-31T19:41:22Z) - Accelerated SGD for Non-Strongly-Convex Least Squares [14.010916616909743]
非強凸設定における最小二乗回帰問題の近似を考察する。
本稿では,問題のノイズに依存して最適な予測誤差率を実現するための,最初の実用的なアルゴリズムを提案する。
論文 参考訳(メタデータ) (2022-03-03T14:39:33Z) - Breaking the Convergence Barrier: Optimization via Fixed-Time Convergent
Flows [4.817429789586127]
本稿では, 固定時間安定力学系の概念に基づいて, 加速を実現するための多言語最適化フレームワークを提案する。
提案手法の高速化された収束特性を,最先端の最適化アルゴリズムに対して様々な数値例で検証する。
論文 参考訳(メタデータ) (2021-12-02T16:04:40Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳(メタデータ) (2020-08-23T20:36:49Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。