論文の概要: Accelerated Multiplicative Weights Update Avoids Saddle Points almost always

• arxiv url: http://arxiv.org/abs/2204.11407v1
• Date: Mon, 25 Apr 2022 02:54:05 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-26 21:17:52.698977
• Title: Accelerated Multiplicative Weights Update Avoids Saddle Points almost always
• Title（参考訳）: 加速乗算重み更新は、ほとんど常にサドルポイントを避ける
• Authors: Yi Feng, Ioannis Panageas, Xiao Wang
• Abstract要約: 単純化の積である制約を伴う非最適化問題を考察する。 この種の問題を解決するのによく使われるアルゴリズムは、ゲーム理論、機械学習、マルチエージェントシステムで広く使われているMultiplicative Descents Update (MWU) である。
• 参考スコア（独自算出の注目度）: 17.200312130814403
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We consider non-convex optimization problems with constraint that is a product of simplices. A commonly used algorithm in solving this type of problem is the Multiplicative Weights Update (MWU), an algorithm that is widely used in game theory, machine learning and multi-agent systems. Despite it has been known that MWU avoids saddle points, there is a question that remains unaddressed:"Is there an accelerated version of MWU that avoids saddle points provably?" In this paper we provide a positive answer to above question. We provide an accelerated MWU based on Riemannian Accelerated Gradient Descent, and prove that the Riemannian Accelerated Gradient Descent, thus the accelerated MWU, almost always avoid saddle points.
• Abstract（参考訳）: 単純化の産物である制約付き非凸最適化問題を考える。 この種の問題を解決するのによく使われるアルゴリズムは、ゲーム理論、機械学習、マルチエージェントシステムで広く使われているMultiplicative Weights Update (MWU) である。 MWUがサドル点を避けることは知られているが、「サドル点を確実に避けるMWUの加速バージョンはあるか?」という疑問が残る。 本稿では,上記の質問に対する肯定的な回答を提供する。 我々は、リーマン加速度勾配 Descent に基づく加速MWUを提供し、リーマン加速度勾配 Descent が証明されるので、加速MWUは、ほぼ常にサドル点を避けることができる。

関連論文リスト

• The inexact power augmented Lagrangian method for constrained nonconvex optimization [44.516958213972885]
  この研究は、強大な拡張ラグランジアン用語を導入し、拡大項はユークリッドのノルムを権力へと引き上げる。 その結果, 長期化に低消費電力を用いると, 残余の減少が遅くなるにもかかわらず, より高速な成長が期待できることがわかった。 以上の結果より, 持続時間の短縮には低消費電力が有効であるが, 残留率が低下する傾向が示唆された。
  論文  参考訳（メタデータ） (2024-10-26T11:31:56Z)
• Riemannian stochastic optimization methods avoid strict saddle points [68.80251170757647]
  研究中のポリシーは、確率 1 の厳密なサドル点/部分多様体を避けていることを示す。 この結果は、アルゴリズムの極限状態が局所最小値にしかならないことを示すため、重要な正当性チェックを提供する。
  論文  参考訳（メタデータ） (2023-11-04T11:12:24Z)
• Momentum Provably Improves Error Feedback! [54.93799845077906]
  未処理の場合、圧縮による誤差は指数的トレーニングの振る舞いを伝播させる。 EF21-SGDMは、従来のエラーフィードバックアルゴリズムの通信とサンプルの複雑さを改善している。
  論文  参考訳（メタデータ） (2023-05-24T13:52:02Z)
• Learning to Optimize with Stochastic Dominance Constraints [103.26714928625582]
  本稿では,不確実量を比較する問題に対して,単純かつ効率的なアプローチを開発する。 我々はラグランジアンの内部最適化をサロゲート近似の学習問題として再考した。 提案したライト-SDは、ファイナンスからサプライチェーン管理に至るまで、いくつかの代表的な問題において優れた性能を示す。
  論文  参考訳（メタデータ） (2022-11-14T21:54:31Z)
• Adiabatic Quantum Computing for Multi Object Tracking [170.8716555363907]
  マルチオブジェクト追跡(MOT)は、オブジェクト検出が時間を通して関連付けられているトラッキング・バイ・検出のパラダイムにおいて、最もよくアプローチされる。 これらの最適化問題はNPハードであるため、現在のハードウェア上の小さなインスタンスに対してのみ正確に解決できる。 本手法は,既成整数計画法を用いても,最先端の最適化手法と競合することを示す。
  論文  参考訳（メタデータ） (2022-02-17T18:59:20Z)
• Optimal No-Regret Learning in General Games: Bounded Regret with Unbounded Step-Sizes via Clairvoyant MWU [27.438327151960657]
  一定のステップサイズで絶え間なく後悔するアルゴリズムを提案する。 ステップサイズが大きくなるにつれて,アルゴリズムの累積後悔は線形的に減少する。
  論文  参考訳（メタデータ） (2021-11-29T17:42:24Z)
• A Riemannian Accelerated Proximal Extragradient Framework and its Implications [52.31775617527208]
  高速ユークリッド法を得るための強力なフレームワークである citetmonteiro2013accelerated の EmphAccelerated Hybrid Proximal Extragradient (A-HPE) 法を再検討する。
  論文  参考訳（メタデータ） (2021-11-04T11:32:20Z)
• A proximal-proximal majorization-minimization algorithm for nonconvex tuning-free robust regression problems [4.261680642170457]
  非回帰問題に対する PMM (proximal-proximal majorization-minimization) アルゴリズムを提案する。 提案アルゴリズムは既存の最先端アルゴリズムよりも優れている。
  論文  参考訳（メタデータ） (2021-06-25T15:07:13Z)
• A H\"olderian backtracking method for min-max and min-min problems [0.0]
  本稿では,凸空間外におけるmin-maxあるいはmin-min問題の解法を提案する。 我々は、学習においてユビキタスな剛性を仮定し、この手法を多くの最適化問題に適用する。
  論文  参考訳（メタデータ） (2020-07-17T08:12:31Z)
• Accelerated Message Passing for Entropy-Regularized MAP Inference [89.15658822319928]
  離散値のランダムフィールドにおけるMAP推論の最大化は、機械学習の基本的な問題である。 この問題の難しさから、特殊メッセージパッシングアルゴリズムの導出には線形プログラミング(LP)緩和が一般的である。 古典的加速勾配の根底にある手法を活用することにより,これらのアルゴリズムを高速化するランダム化手法を提案する。
  論文  参考訳（メタデータ） (2020-07-01T18:43:32Z)
• On Distributed Non-convex Optimization: Projected Subgradient Method For Weakly Convex Problems in Networks [13.385373310554327]
  Moreau subgradient 法は、機械学習における線形シャープネス問題を収束させる。 理論的保証を伴う下位段階法の分散実装を提案する。
  論文  参考訳（メタデータ） (2020-04-28T01:01:49Z)

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

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