論文の概要: On the Impossibility of Global Convergence in Multi-Loss Optimization

• arxiv url: http://arxiv.org/abs/2005.12649v3
• Date: Sun, 17 Jan 2021 09:14:59 GMT
• ステータス: 処理完了
• システム内更新日: 2022-11-29 00:56:45.732202
• Title: On the Impossibility of Global Convergence in Multi-Loss Optimization
• Title（参考訳）: マルチロス最適化における大域収束の不可能性について
• Authors: Alistair Letcher
• Abstract要約: 所望の収束特性が任意のアルゴリズムに対して同時に保持できないことを証明する。 我々の結果は、それぞれのアルゴリズムよりも、満足のいく結果のないゲームの存在と関係がある。 ML実践者にとって、高次元ゲームにそのような振る舞いが生じるかどうかは、未解決の問題である。
• 参考スコア（独自算出の注目度）: 10.081768261298098
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Under mild regularity conditions, gradient-based methods converge globally to a critical point in the single-loss setting. This is known to break down for vanilla gradient descent when moving to multi-loss optimization, but can we hope to build some algorithm with global guarantees? We negatively resolve this open problem by proving that desirable convergence properties cannot simultaneously hold for any algorithm. Our result has more to do with the existence of games with no satisfactory outcomes, than with algorithms per se. More explicitly we construct a two-player game with zero-sum interactions whose losses are both coercive and analytic, but whose only simultaneous critical point is a strict maximum. Any 'reasonable' algorithm, defined to avoid strict maxima, will therefore fail to converge. This is fundamentally different from single losses, where coercivity implies existence of a global minimum. Moreover, we prove that a wide range of existing gradient-based methods almost surely have bounded but non-convergent iterates in a constructed zero-sum game for suitably small learning rates. It nonetheless remains an open question whether such behavior can arise in high-dimensional games of interest to ML practitioners, such as GANs or multi-agent RL.
• Abstract（参考訳）: 穏やかな規則性条件下では、勾配に基づく方法は単一損失設定において臨界点にグローバルに収束する。 これは、マルチロス最適化に移行する際のバニラ勾配降下を解消することが知られているが、グローバル保証によるアルゴリズムの構築を期待できるだろうか? 我々は,任意のアルゴリズムに対して所望の収束特性が同時に保持できないことを証明し,この問題を負に解決する。 我々の結果は、それぞれのアルゴリズムよりも、満足のいく結果のないゲームの存在と関係がある。 より明確には、損失が強制的かつ分析的であるが、同時に臨界点が厳密な最大値であるゼロサム相互作用を持つ2人のプレイヤーゲームを構築する。 厳密な最大値を避けるために定義された任意の「理性」アルゴリズムは、従って収束しない。 これは、大域的最小値の存在を保っている単損失とは根本的に異なる。 さらに,学習率の小さいゼロサムゲームにおいて,既存のグラデーションベース手法がほぼ確実に有界だが非収束的なイテレートを持つことを実証する。 それにもかかわらず、そのような行動が、GANやマルチエージェントRLのようなML実践者にとって、高次元的なゲームで起こりうるかどうかには疑問が残る。

関連論文リスト

• Revisiting the Last-Iterate Convergence of Stochastic Gradient Methods [25.831462008050387]
  グラディエント・Descent(SGD)アルゴリズムは、実際の性能が良く、理論的な理解が欠如していることから、人々の関心を喚起している。 有限収束がより広い合成最適化や非ユークリッドノルムに証明可能な拡張が可能かどうかはまだ不明である。
  論文  参考訳（メタデータ） (2023-12-13T21:41:06Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• High-Probability Bounds for Stochastic Optimization and Variational Inequalities: the Case of Unbounded Variance [59.211456992422136]
  制約の少ない仮定の下で高確率収束結果のアルゴリズムを提案する。 これらの結果は、標準機能クラスに適合しない問題を最適化するために検討された手法の使用を正当化する。
  論文  参考訳（メタデータ） (2023-02-02T10:37:23Z)
• Global Nash Equilibrium in Non-convex Multi-player Game: Theory and Algorithms [66.8634598612777]
  ナッシュ均衡(NE)はマルチプレイヤーゲームにおいて全てのプレイヤーに受け入れられることを示す。 また、一般理論から一歩ずつ一方的に利益を得ることはできないことも示している。
  論文  参考訳（メタデータ） (2023-01-19T11:36:50Z)
• HSVI can solve zero-sum Partially Observable Stochastic Games [7.293053431456775]
  2-player 0-sum不完全なゲームを解くための最先端の手法は、線形プログラミングや動的後悔の最小化に依存している。 本稿では,線形プログラミングや反復的手法に依存した手法を補完する,有望なアプローチの新たなファミリーを提案する。
  論文  参考訳（メタデータ） (2022-10-26T11:41:57Z)
• Last-iterate Convergence in Extensive-Form Games [49.31256241275577]
  逐次ゲームにおける楽観的アルゴリズムの最後の点収束について検討する。 これらのアルゴリズムはいずれも最終点収束を楽しみ、そのいくつかは指数関数的に高速に収束する。
  論文  参考訳（メタデータ） (2021-06-27T22:02:26Z)
• Exploiting Higher Order Smoothness in Derivative-free Optimization and Continuous Bandits [99.70167985955352]
  強凸関数のゼロ次最適化問題について検討する。 予測勾配降下アルゴリズムのランダム化近似を考察する。 その結果,0次アルゴリズムはサンプルの複雑性や問題パラメータの点でほぼ最適であることが示唆された。
  論文  参考訳（メタデータ） (2020-06-14T10:42:23Z)
• Inexact and Stochastic Generalized Conditional Gradient with Augmented Lagrangian and Proximal Step [2.0196229393131726]
  我々は著者の以前の論文で開発されたCGALPアルゴリズムの不正確さとバージョンを分析した。 これにより、いくつかの勾配、項、および/または線形最小化オラクルを不正確な方法で計算することができる。 ラグランジアンのアフィン制約の最適性と実現可能性への収束を示す。
  論文  参考訳（メタデータ） (2020-05-11T14:52:16Z)
• Finite-Time Last-Iterate Convergence for Multi-Agent Learning in Games [116.0771177871705]
  我々は,$lambda$-cocoerciveゲーム上での連立OGD学習における有限時間最終点収束率を特徴付ける。 新たなダブルストッピング時間法により, この適応アルゴリズムは, 非適応的手法と同じ有限時間終点収束率が得られることを示す。
  論文  参考訳（メタデータ） (2020-02-23T01:46:34Z)
• Replica Exchange for Non-Convex Optimization [4.421561004829125]
  勾配降下(GD)は凸目的関数に対して急速に収束することが知られているが、局所的なミニマに閉じ込められることがある。 ランゲヴィン力学(LD)は状態空間を探索し、大域的な最小値を見つけることができるが、正確な推定を得るためには、LDは小さな離散化ステップサイズで実行し、弱い力を検証する必要がある。 本稿では,これら2つのアルゴリズムとその非スワッピング変種が,単純な交換機構によって協調可能であることを示す。
  論文  参考訳（メタデータ） (2020-01-23T03:13:19Z)

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

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