論文の概要: A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints
- arxiv url: http://arxiv.org/abs/2009.11359v4
- Date: Tue, 27 Apr 2021 00:53:41 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-15 15:54:17.497557
- Title: A Unified Analysis of First-Order Methods for Smooth Games via Integral
Quadratic Constraints
- Title（参考訳）: 積分二次制約による球技の1次法の統一解析
- Authors: Guodong Zhang, Xuchan Bao, Laurent Lessard, Roger Grosse
- Abstract要約: 本研究では、滑らかで強可変なゲームやイテレーションのための一階法に積分二次的制約理論を適用する。
我々は、負の運動量法(NM)に対して、既知の下界と一致する複雑性$mathcalO(kappa1.5)$で、初めて大域収束率を与える。
一段階のメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば,高速化は不可能であることを示す。
- 参考スコア（独自算出の注目度）: 10.578409461429626
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: The theory of integral quadratic constraints (IQCs) allows the certification
of exponential convergence of interconnected systems containing nonlinear or
uncertain elements. In this work, we adapt the IQC theory to study first-order
methods for smooth and strongly-monotone games and show how to design tailored
quadratic constraints to get tight upper bounds of convergence rates. Using
this framework, we recover the existing bound for the gradient method~(GD),
derive sharper bounds for the proximal point method~(PPM) and optimistic
gradient method~(OG), and provide \emph{for the first time} a global
convergence rate for the negative momentum method~(NM) with an iteration
complexity $\mathcal{O}(\kappa^{1.5})$, which matches its known lower bound. In
addition, for time-varying systems, we prove that the gradient method with
optimal step size achieves the fastest provable worst-case convergence rate
with quadratic Lyapunov functions. Finally, we further extend our analysis to
stochastic games and study the impact of multiplicative noise on different
algorithms. We show that it is impossible for an algorithm with one step of
memory to achieve acceleration if it only queries the gradient once per batch
(in contrast with the stochastic strongly-convex optimization setting, where
such acceleration has been demonstrated). However, we exhibit an algorithm
which achieves acceleration with two gradient queries per batch.
- Abstract（参考訳）: 積分二次制約の理論(iqcs)は、非線形あるいは不確定要素を含む相互接続系の指数収束の証明を可能にする。
本研究では, IQC理論を適用し, スムーズかつ強単調なゲームのための一階法について検討し, 厳密な収束率を得るための2次制約を設計する方法を示す。
このフレームワークを用いて、勾配法~(GD)、近点法~(PPM)および楽観的勾配法~(OG)に対するよりシャープな境界を導出し、負の運動量法~(NM)に対する大域収束率を、その既知の下界と一致する反復複雑性$\mathcal{O}(\kappa^{1.5})$で表す。
さらに, 時間変化系では, 最適ステップサイズの勾配法が2次リアプノフ関数を用いた最速の最低ケース収束率を達成することを証明した。
最後に,解析を確率ゲームに拡張し,乗法ノイズが異なるアルゴリズムに与える影響について検討する。
本稿では,1ステップのメモリを持つアルゴリズムでは,バッチ毎に1回だけ勾配を問合せすれば高速化は不可能であることが示される(そのような高速化が実証された確率的強凸最適化設定とは対照的に)。
しかし,1バッチに2つの勾配クエリで高速化を実現するアルゴリズムを示す。
関連論文リスト
- An Adaptive Stochastic Gradient Method with Non-negative Gauss-Newton Stepsizes [17.804065824245402]
機械学習の応用では、各損失関数は非負であり、平方根とその実数値平方根の構成として表すことができる。
本稿では, ガウス・ニュートン法やレフスカルト法を適用して, 滑らかだが非負な関数の平均を最小化する方法を示す。
論文 参考訳（メタデータ） (2024-07-05T08:53:06Z) - Formal guarantees for heuristic optimization algorithms used in machine
learning [6.978625807687497]
グラディエント・Descent(SGD)とその変種は、大規模最適化機械学習(ML)問題において支配的な手法となっている。
本稿では,いくつかの凸最適化手法の形式的保証と改良アルゴリズムの提案を行う。
論文 参考訳（メタデータ） (2022-07-31T19:41:22Z) - Communication Acceleration of Local Gradient Methods via an Accelerated
Primal-Dual Algorithm with Inexact Prox [11.564643329398438]
我々はMishchenko et al (2022)と同じ通信加速度を得る代替アルゴリズムを提案する。
我々のアプローチはChambolle and Pock (2011) の有名な手法に基づいており、いくつかの非自明な修正を加えている。
提案手法は,ネットワーク上での最適化にも適用可能であり,理論的改善も得られている。
論文 参考訳（メタデータ） (2022-07-08T15:24:13Z) - Faster One-Sample Stochastic Conditional Gradient Method for Composite
Convex Minimization [61.26619639722804]
滑らかで非滑らかな項の和として形成される凸有限サム目標を最小化するための条件勾配法(CGM)を提案する。
提案手法は, 平均勾配 (SAG) 推定器を備え, 1回に1回のサンプルしか必要としないが, より高度な分散低減技術と同等の高速収束速度を保証できる。
論文 参考訳（メタデータ） (2022-02-26T19:10:48Z) - Nesterov Accelerated Shuffling Gradient Method for Convex Optimization [15.908060383231371]
このアルゴリズムは,統一シャッフル方式を用いて,$mathcalO (1/T)$の改善率を示す。
我々の収束解析は有界領域や有界勾配条件に関する仮定を必要としない。
数値シミュレーションはアルゴリズムの効率を実証する。
論文 参考訳（メタデータ） (2022-02-07T21:23:17Z) - A Two-Time-Scale Stochastic Optimization Framework with Applications in Control and Reinforcement Learning [13.908826484332282]
最適化問題の解法として,新しい2段階勾配法を提案する。
最初の貢献は、提案した2時間スケール勾配アルゴリズムの有限時間複雑性を特徴づけることである。
我々は、強化学習における勾配に基づく政策評価アルゴリズムに適用する。
論文 参考訳（メタデータ） (2021-09-29T23:15:23Z) - Leveraging Non-uniformity in First-order Non-convex Optimization [93.6817946818977]
目的関数の非一様洗練は、emphNon-uniform Smoothness(NS)とemphNon-uniform Lojasiewicz inequality(NL)につながる
新しい定義は、古典的な$Omega (1/t2)$下界よりも早く大域的最適性に収束する新しい幾何学的一階法を刺激する。
論文 参考訳（メタデータ） (2021-05-13T04:23:07Z) - Acceleration Methods [57.202881673406324]
まず2次最適化問題を用いて加速法を2つ導入する。
我々は、ネステロフの精巧な研究から始まる運動量法を詳細に論じる。
我々は、ほぼ最適な収束率に達するための一連の簡単な手法である再起動スキームを議論することで結論付ける。
論文 参考訳（メタデータ） (2021-01-23T17:58:25Z) - Zeroth-Order Hybrid Gradient Descent: Towards A Principled Black-Box
Optimization Framework [100.36569795440889]
この作業は、一階情報を必要としない零次最適化(ZO)の反復である。
座標重要度サンプリングにおける優雅な設計により,ZO最適化法は複雑度と関数クエリコストの両面において効率的であることを示す。
論文 参考訳（メタデータ） (2020-12-21T17:29:58Z) - Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth
Nonlinear TD Learning [145.54544979467872]
本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。
本研究の結果は, 同時一次および二重側収束の形で表される。
論文 参考訳（メタデータ） (2020-08-23T20:36:49Z) - Towards Better Understanding of Adaptive Gradient Algorithms in
Generative Adversarial Nets [71.05306664267832]
適応アルゴリズムは勾配の歴史を用いて勾配を更新し、深層ニューラルネットワークのトレーニングにおいてユビキタスである。
本稿では,非コンケーブ最小値問題に対するOptimisticOAアルゴリズムの変種を解析する。
実験の結果,適応型GAN非適応勾配アルゴリズムは経験的に観測可能であることがわかった。
論文 参考訳（メタデータ） (2019-12-26T22:10:10Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。