論文の概要: Proximal Point Method for Online Saddle Point Problem
- arxiv url: http://arxiv.org/abs/2407.04591v2
- Date: Tue, 08 Oct 2024 09:40:07 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-10-10 14:25:40.043440
- Title: Proximal Point Method for Online Saddle Point Problem
- Title(参考訳): オンラインサドルポイント問題の近点法
- Authors: Qing-xin Meng, Jian-wei Liu,
- Abstract要約: 本稿では,2プレイヤの時間変動コンベックス・コンベレーブゲームの連続を含むオンラインサドル点問題に焦点を当てる。
環境の非定常性を考えると、アルゴリズム設計のパフォーマンス指標として双対性ギャップと動的ナッシュ均衡の後悔を採用する。
点法には3つの変種がある: Online Proximal Point Method (OPPM), Optimistic OPPM (OptOPPM), OptOPPM with multiple predictor。
- 参考スコア(独自算出の注目度): 4.815933988302869
- License:
- 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. The technical appendix and code can be found at https://github.com/qingxin6174/PPM-for-OSP.
- Abstract(参考訳): 本稿では,2プレイヤの時間変動コンベックス・コンベレーブゲームの連続を含むオンラインサドル点問題に焦点を当てる。
環境の非定常性を考えると、アルゴリズム設計のパフォーマンス指標として双対性ギャップと動的ナッシュ均衡の後悔を採用する。
近位点法には,オンライン近位点法(OPPM),オプティミスティックOPPM(OptOPPM),複数の予測器を備えたオプトOPPMの3種類がある。
各アルゴリズムは、双対性ギャップと動的ナッシュ平衡の後悔の両方に対して上限を保証し、双対性ギャップに対して測定するとほぼ最適となる。
具体的には、定常的なペイオフ関数の列のような特定の良質な環境では、これらのアルゴリズムはほぼ一定の距離境界を維持している。
実験結果はこれらのアルゴリズムの有効性をさらに検証する。
最後に,動的ナッシュ平衡後悔を性能指標として用いた際の潜在的信頼性の懸念について論じる。
技術的な付録とコードはhttps://github.com/qingxin6174/PPM-for-OSPにある。
関連論文リスト
- 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 [62.51015395213579]
2プレイヤゼロサム連続ゲームにおける非AL平衡非漸近目的関数について考察する。
提案アルゴリズムは粒子の動きを利用して$ilon$-mixed Nash平衡のランダム戦略の更新を表現する。
論文 参考訳(メタデータ) (2023-03-02T05:08:15Z) - 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) - Convergence and Stability of the Stochastic Proximal Point Algorithm
with Momentum [14.158845925610438]
運動量を持つ勾配近位アルゴリズム(PPA)は、より優れた縮退係数を持つ近位アルゴリズム(PPA)と比較して、近傍への高速収束を可能にすることを示す。
論文 参考訳(メタデータ) (2021-11-11T12:17:22Z) - Near-Optimal High Probability Complexity Bounds for Non-Smooth
Stochastic Optimization with Heavy-Tailed Noise [63.304196997102494]
アルゴリズムが高い確率で小さな客観的残差を与えることを理論的に保証することが不可欠である。
既存の非滑らか凸最適化法は、負のパワーまたは対数的な信頼度に依存する境界の複雑さを持つ。
クリッピングを用いた2つの勾配法に対して, 新たなステップサイズルールを提案する。
論文 参考訳(メタデータ) (2021-06-10T17:54:21Z) - Optimal Algorithms for Differentially Private Stochastic Monotone
Variational Inequalities and Saddle-Point Problems [5.051036968777244]
差分プライバシー制約下における変動不等式(SVI)とサドル点不等式問題の最初の系統的研究--(DP)
NISPP(Noisy Inexact Proximal Point)とNSEG(Noisy Extragradient)の2つのアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-04-07T08:37:07Z) - Distributed Saddle-Point Problems: Lower Bounds, Near-Optimal and Robust
Algorithms [125.99533416395765]
本稿では,サドル点問題の分散最適化に着目する。
本論文は,本研究における分散手法の有効性を実験的に示すものである。
論文 参考訳(メタデータ) (2020-10-25T13:13:44Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。