論文の概要: Online Saddle Point Problem and Online Convex-Concave Optimization

• arxiv url: http://arxiv.org/abs/2312.06957v2
• Date: Fri, 15 Dec 2023 16:04:24 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-18 18:09:55.923931
• Title: Online Saddle Point Problem and Online Convex-Concave Optimization
• Title（参考訳）: オンラインサドルポイント問題とオンライン凸凹最適化
• Authors: Qing-xin Meng and Jian-wei Liu
• Abstract要約: 本稿では,オンラインコンベックス・コンキャブ最適化(OCCO)フレームワークについて述べる。 本稿では、性能指標として一般化双対性ギャップ(Dual-Gap)を提案し、OCCOとDual-Gapとオンライン凸最適化(OCO)の並列性を確立する。
• 参考スコア（独自算出の注目度）: 5.689388032721778
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Centered around solving the Online Saddle Point problem, this paper introduces the Online Convex-Concave Optimization (OCCO) framework, which involves a sequence of two-player time-varying convex-concave games. We propose the generalized duality gap (Dual-Gap) as the performance metric and establish the parallel relationship between OCCO with Dual-Gap and Online Convex Optimization (OCO) with regret. To demonstrate the natural extension of OCCO from OCO, we develop two algorithms, the implicit online mirror descent-ascent and its optimistic variant. Analysis reveals that their duality gaps share similar expression forms with the corresponding dynamic regrets arising from implicit updates in OCO. Empirical results further substantiate the effectiveness of our algorithms. Simultaneously, we unveil that the dynamic Nash equilibrium regret, which was initially introduced in a recent paper, has inherent defects.
• Abstract（参考訳）: 本稿では,オンライン・サドルポイント問題を解くことを中心に,オンライン・コンベックス・コンベブ最適化(occo)フレームワークを紹介する。 本稿では、性能指標として一般化双対性ギャップ(Dual-Gap)を提案し、OCCOとDual-Gapとオンライン凸最適化(OCO)の並列性を確立する。 OCOからのOCCOの自然な拡張を示すために、暗黙のオンラインミラー降下指数と楽観的な変種という2つのアルゴリズムを開発した。 分析の結果、OCOの暗黙的な更新によって生じる動的後悔と、それらの双対性ギャップが類似した表現形式を共有することが明らかとなった。 実験結果は、アルゴリズムの有効性をさらに実証する。 同時に,最近の論文で紹介された動的ナッシュ均衡の後悔には本質的な欠陥があることを明らかにした。

関連論文リスト

• Proximal Point Method for Online Saddle Point Problem [4.815933988302869]
  本稿では,2プレイヤの時間変動コンベックス・コンベレーブゲームの連続を含むオンラインサドル点問題に焦点を当てる。 環境の非定常性を考えると、アルゴリズム設計のパフォーマンス指標として双対性ギャップと動的ナッシュ均衡の後悔を採用する。 点法には3つの変種がある: Online Proximal Point Method (OPPM), Optimistic OPPM (OptOPPM), OptOPPM with multiple predictor。
  論文  参考訳（メタデータ） (2024-07-05T15:40:15Z)
• ALEXR: An Optimal Single-Loop Algorithm for Convex Finite-Sum Coupled Compositional Stochastic Optimization [53.14532968909759]
  ALEXRと呼ばれる,効率的な単ループプリマルデュアルブロックコーディネートアルゴリズムを提案する。 本研究では, ALEXR の凸面および強凸面の収束速度を滑らか性および非滑らか性条件下で確立する。 本稿では,ALEXRの収束速度が,検討されたcFCCO問題に対する1次ブロック座標アルゴリズムの中で最適であることを示すために,より低い複雑性境界を示す。
  論文  参考訳（メタデータ） (2023-12-04T19:00:07Z)
• Stable Nonconvex-Nonconcave Training via Linear Interpolation [51.668052890249726]
  本稿では,ニューラルネットワークトレーニングを安定化(大規模)するための原理的手法として,線形アヘッドの理論解析を提案する。 最適化過程の不安定性は、しばしば損失ランドスケープの非単調性によって引き起こされるものであり、非拡張作用素の理論を活用することによって線型性がいかに役立つかを示す。
  論文  参考訳（メタデータ） (2023-10-20T12:45:12Z)
• Distributed Online Non-convex Optimization with Composite Regret [31.53784277195043]
  本稿では,分散オンライン一般損失に対する新たなネットワーク後悔を伴う,新たな複合後悔を提案する。 我々の知る限り、オンラインの非線形学習における最初の後悔である。
  論文  参考訳（メタデータ） (2022-09-21T04:16:33Z)
• Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
  本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。 この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
  論文  参考訳（メタデータ） (2021-12-29T02:42:59Z)
• Stochastic Gradient Descent-Ascent and Consensus Optimization for Smooth Games: Convergence Analysis under Expected Co-coercivity [49.66890309455787]
  本稿では,SGDA と SCO の最終的な収束保証として,期待されるコヒーレンシティ条件を導入し,その利点を説明する。 定常的なステップサイズを用いた場合、両手法の線形収束性を解の近傍に証明する。 我々の収束保証は任意のサンプリングパラダイムの下で保たれ、ミニバッチの複雑さに関する洞察を与える。
  論文  参考訳（メタデータ） (2021-06-30T18:32:46Z)
• An Improved Two-Archive Evolutionary Algorithm for Constrained Multi-Objective Optimization [5.760976250387322]
  近年,制約付き多目的最適化(C-TAEA)のための2階層進化アルゴリズムが最新のアルゴリズムとして提案されている。 C-TAEA-IIと呼ばれる改良版C-TAEAを提案する。
  論文  参考訳（メタデータ） (2021-03-10T23:04:02Z)
• Linear Convergent Decentralized Optimization with Compression [50.44269451541387]
  圧縮を伴う既存の分散アルゴリズムは主にDGD型アルゴリズムの圧縮に焦点を当てている。 原始双対アルゴリズムによって動機付けられた本論文は、最初のアンダーラインLinunderlineEAr収束を提案する。 underline Decentralized with compression, LEAD。
  論文  参考訳（メタデータ） (2020-07-01T04:35:00Z)
• Cogradient Descent for Bilinear Optimization [124.45816011848096]
  双線形問題に対処するために、CoGDアルゴリズム(Cogradient Descent Algorithm)を導入する。 一方の変数は、他方の変数との結合関係を考慮し、同期勾配降下をもたらす。 本アルゴリズムは,空間的制約下での1変数の問題を解くために応用される。
  論文  参考訳（メタデータ） (2020-06-16T13:41:54Z)

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

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