論文の概要: Proximal Point Method for Online Saddle Point Problem
- arxiv url: http://arxiv.org/abs/2407.04591v1
- Date: Fri, 5 Jul 2024 15:40:15 GMT
- ステータス: 処理完了
- システム内更新日: 2024-07-08 13:01:09.246329
- Title: Proximal Point Method for Online Saddle Point Problem
- Title（参考訳）: オンラインサドルポイント問題の近点法
- Authors: Qing-xin Meng, Jian-wei Liu,
- Abstract要約: 本稿では,2プレイヤの時間変動コンベックス・コンベレーブゲームの連続を含むオンラインサドル点問題に焦点を当てる。
環境の非定常性を考えると、アルゴリズム設計のパフォーマンス指標として双対性ギャップと動的ナッシュ均衡の後悔を採用する。
- 参考スコア（独自算出の注目度）: 4.815933988302869
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper focuses on the online saddle point problem, which involves a sequence of two-player time-varying convex-concave games. Considering the nonstationarity of the environment, we adopt the duality gap and the dynamic Nash equilibrium regret as performance metrics for algorithm design. We present three variants of the proximal point method: the Online Proximal Point Method~(OPPM), the Optimistic OPPM~(OptOPPM), and the OptOPPM with multiple predictors. Each algorithm guarantees upper bounds for both the duality gap and dynamic Nash equilibrium regret, achieving near-optimality when measured against the duality gap. Specifically, in certain benign environments, such as sequences of stationary payoff functions, these algorithms maintain a nearly constant metric bound. Experimental results further validate the effectiveness of these algorithms. Lastly, this paper discusses potential reliability concerns associated with using dynamic Nash equilibrium regret as a performance metric.
- Abstract（参考訳）: 本稿では,2プレイヤの時間変動コンベックス・コンベレーブゲームの連続を含むオンラインサドル点問題に焦点を当てる。
環境の非定常性を考えると、アルゴリズム設計のパフォーマンス指標として双対性ギャップと動的ナッシュ均衡の後悔を採用する。
近点法には3つの変種がある: Online Proximal Point Method~(OPPM), Optimistic OPPM~(OptOPPM), OptOPPM with multiple predictor。
各アルゴリズムは、双対性ギャップと動的ナッシュ平衡の後悔の両方に対して上限を保証し、双対性ギャップに対して測定するとほぼ最適となる。
具体的には、定常的なペイオフ関数の列のような特定の良質な環境では、これらのアルゴリズムはほぼ一定の距離境界を維持している。
実験結果はこれらのアルゴリズムの有効性をさらに検証する。
最後に,動的ナッシュ平衡後悔を性能指標として用いた際の潜在的信頼性の懸念について論じる。
関連論文リスト
- Sound Heuristic Search Value Iteration for Undiscounted POMDPs with Reachability Objectives [16.101435842520473]
本稿では,POMDPにおける最大到達可能性確率問題(indefinite-horizon)と呼ばれる問題について検討する。
割引問題に対するポイントベース手法の成功に触発され,MRPPへの拡張について検討した。
本稿では,これらの手法の強みを有効活用し,信念空間を効率的に探索するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-06-05T02:33:50Z) - PAPAL: A Provable PArticle-based Primal-Dual ALgorithm for Mixed Nash Equilibrium [58.26573117273626]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
連続分布戦略のための粒子ベースアルゴリズムに関する新しい知見を述べる。
論文 参考訳（メタデータ） (2023-03-02T05:08:15Z) - A relaxed proximal gradient descent algorithm for convergent
plug-and-play with proximal denoiser [6.2484576862659065]
本稿では,新しいコンバーゼントなPlug-and-fidelity Descent (Play)アルゴリズムを提案する。
このアルゴリズムは、より広い範囲の通常の凸化パラメータに収束し、画像のより正確な復元を可能にする。
論文 参考訳（メタデータ） (2023-01-31T16:11:47Z) - Proximal Point Imitation Learning [48.50107891696562]
我々は、無限地平線模倣学習のための厳密な効率保証を備えた新しいアルゴリズムを開発した。
我々は、最適化、特に近点法(PPM)と双対平滑化から古典的ツールを活用する。
線形関数とニューラルネットワーク関数の近似の双方に対して、説得力のある経験的性能を実現する。
論文 参考訳（メタデータ） (2022-09-22T12:40:21Z) - Learning Two-Player Mixture Markov Games: Kernel Function Approximation
and Correlated Equilibrium [157.0902680672422]
非線形関数近似を用いた2プレイヤーゼロサムマルコフゲームにおけるナッシュ平衡の学習について検討する。
双対性ギャップを最小化してナッシュ均衡を求める新しいオンライン学習アルゴリズムを提案する。
論文 参考訳（メタデータ） (2022-08-10T14:21:54Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Bayesian imaging using Plug & Play priors: when Langevin meets Tweedie [13.476505672245603]
本稿では,ベイズ推定を事前に行うための理論,方法,および証明可能な収束アルゴリズムを開発する。
モンテカルロサンプリングとMMSEに対する-ULA(Unadjusted Langevin)アルゴリズム推論と、推論のための定量的SGD(Stochastic Gradient Descent)の2つのアルゴリズムを紹介します。
このアルゴリズムは、点推定や不確実性の可視化や規則性に使用される画像のノイズ除去、インペインティング、ノイズ除去などのいくつかの問題で実証されています。
論文 参考訳（メタデータ） (2021-03-08T12:46:53Z) - A Momentum-Assisted Single-Timescale Stochastic Approximation Algorithm
for Bilevel Optimization [112.59170319105971]
問題に対処するための新しいアルゴリズム - Momentum- Single-timescale Approximation (MSTSA) を提案する。
MSTSAでは、低いレベルのサブプロブレムに対する不正確な解決策のため、反復でエラーを制御することができます。
論文 参考訳（メタデータ） (2021-02-15T07:10:33Z) - Fast Objective & Duality Gap Convergence for Non-Convex Strongly-Concave
Min-Max Problems with PL Condition [52.08417569774822]
本稿では,深層学習(深層AUC)により注目度が高まっている,円滑な非凹部min-max問題の解法に焦点をあてる。
論文 参考訳（メタデータ） (2020-06-12T00:32:21Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。