論文の概要: Convergent First-Order Methods for Bi-level Optimization and Stackelberg Games

• arxiv url: http://arxiv.org/abs/2302.01421v1
• Date: Thu, 2 Feb 2023 21:21:14 GMT
• ステータス: 処理完了
• システム内更新日: 2023-02-06 18:17:17.033811
• Title: Convergent First-Order Methods for Bi-level Optimization and Stackelberg Games
• Title（参考訳）: 双レベル最適化とスタックルバーグゲームのための収束一階法
• Authors: Chinmay Maheshwari and S. Shankar Sasty and Lillian Ratliff and Eric Mazumdar
• Abstract要約: 本稿では,2段階最適化問題のクラスを1次情報のみを用いて解くアルゴリズムを提案する。 現代のアルゴリズムとは異なり、このアルゴリズムは2レベル対象の勾配を推定するために推定器を必要としない。
• 参考スコア（独自算出の注目度）: 1.5074950361970196
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We propose an algorithm to solve a class of bi-level optimization problems using only first-order information. In particular, we focus on a class where the inner minimization has unique solutions. Unlike contemporary algorithms, our algorithm does not require the use of an oracle estimator for the gradient of the bi-level objective or an approximate solver for the inner problem. Instead, we alternate between descending on the inner problem using na\"ive optimization methods and descending on the upper-level objective function using specially constructed gradient estimators. We provide non-asymptotic convergence rates to stationary points of the bi-level objective in the absence of convexity of the closed-loop function and further show asymptotic convergence to only local minima of the bi-level problem. The approach is inspired by ideas from the literature on two-timescale stochastic approximation algorithms.
• Abstract（参考訳）: 本稿では,2段階最適化問題のクラスを1次情報のみを用いて解くアルゴリズムを提案する。 特に、内部最小化がユニークな解を持つクラスに焦点を当てる。 現代のアルゴリズムとは異なり、このアルゴリズムはoracle estimatorをbiレベル目標の勾配に使用する必要はなく、内部問題に対する近似解法も必要としない。 代わりに、Na\ の最適化手法を用いて内部問題を下降し、特別に構築された勾配推定器を用いて上層目標関数を下降する。 閉ループ関数の凸性がない場合,両レベル対象の定常点に非漸近収束率を与えるとともに,双レベル問題の局所最小値にのみ漸近収束を示す。 この手法は2時間確率近似アルゴリズムの文献から着想を得たものである。

関連論文リスト

• Actions Speak What You Want: Provably Sample-Efficient Reinforcement Learning of the Quantal Stackelberg Equilibrium from Strategic Feedbacks [94.07688076435818]
  本研究では,量子スタックルバーグ平衡(QSE)学習のための強化学習を,リーダ・フォロワー構造を持つエピソディックマルコフゲームで研究する。 このアルゴリズムは, (i) 最大推定による量子応答モデル学習と (ii) リーダーの意思決定問題を解決するためのモデルフリーまたはモデルベースRLに基づく。
  論文  参考訳（メタデータ） (2023-07-26T10:24:17Z)
• Computing the optimal distributionally-robust strategy to commit to [32.1464237233989]
  分布的に不安定なスタックルバーグ均衡は、常に幅広い不確実性モデルにわたって存在することを示す。 そこで我々は,分散ロバストな強いスタックルバーグ均衡を計算するための2つのアルゴリズムを提案する。 実験は,従来のStackelbergゲーム上でのアルゴリズムのトラクタビリティを裏付けるものである。
  論文  参考訳（メタデータ） (2022-09-15T23:20:26Z)
• Large-Scale Sequential Learning for Recommender and Engineering Systems [91.3755431537592]
  本稿では,現在の状況に適応してパーソナライズされたランキングを提供する自動アルゴリズムの設計に焦点を当てる。 前者はSAROSと呼ばれる新しいアルゴリズムを提案し,インタラクションの順序を学習するためのフィードバックの種類を考慮に入れている。 提案手法は, 電力網の故障検出に対する初期アプローチと比較して, 統計的に有意な結果を示す。
  論文  参考訳（メタデータ） (2022-05-13T21:09:41Z)
• Optimal Propagation for Graph Neural Networks [51.08426265813481]
  最適グラフ構造を学習するための二段階最適化手法を提案する。 また、時間的複雑さをさらに軽減するために、低ランク近似モデルについても検討する。
  論文  参考訳（メタデータ） (2022-05-06T03:37:00Z)
• No-Regret Learning in Dynamic Stackelberg Games [31.001205916012307]
  Stackelbergゲームでは、リーダーがランダム化された戦略にコミットし、フォロワーがレスポンスでベスト戦略を選択する。 このゲームは、リーダーの報酬や利用可能な戦略に影響を与える基礎となる状態空間を持ち、リーダーとフォロワーの選択した戦略に依存するマルコフ的な方法で進化する。
  論文  参考訳（メタデータ） (2022-02-10T01:07:57Z)
• Bayesian Graph Contrastive Learning [55.36652660268726]
  本稿では,ランダムな拡張がエンコーダにつながることを示すグラフコントラスト学習手法の新たな視点を提案する。 提案手法は,各ノードを決定論的ベクトルに埋め込む既存の手法とは対照的に,各ノードを潜在空間の分布で表現する。 いくつかのベンチマークデータセットにおける既存の最先端手法と比較して,性能が大幅に向上したことを示す。
  論文  参考訳（メタデータ） (2021-12-15T01:45:32Z)
• Stackelberg Actor-Critic: Game-Theoretic Reinforcement Learning Algorithms [13.649494534428745]
  アクター批判に基づく強化学習アルゴリズムにおけるアクターと批評家の階層的相互作用は、ゲーム理論の解釈に自然に結びつく。 そこで我々は,従来の個人勾配ではなく,その目的の全体微分をリーダプレイヤーが追従する,Stackelbergアクタ批判アルゴリズムのメタフレームワークを提案する。 OpenAIのジム環境での実験では、Stackelbergのアクター批判アルゴリズムは常に、少なくとも同じようにパフォーマンスし、標準的なアクター批判アルゴリズムよりもはるかに優れていることが示されている。
  論文  参考訳（メタデータ） (2021-09-25T06:18:41Z)
• Policy Gradient for Continuing Tasks in Non-stationary Markov Decision Processes [112.38662246621969]
  強化学習は、マルコフ決定プロセスにおいて期待される累積報酬を最大化するポリシーを見つけることの問題を考える。 我々は、ポリシーを更新するために上昇方向として使用する値関数の偏りのないナビゲーション勾配を計算する。 ポリシー勾配型アルゴリズムの大きな欠点は、定常性の仮定が課せられない限り、それらがエピソジックなタスクに限定されていることである。
  論文  参考訳（メタデータ） (2020-10-16T15:15:42Z)
• Optimally Deceiving a Learning Leader in Stackelberg Games [123.14187606686006]
  MLコミュニティの最近の結果は、リーダーがStackelbergゲームでコミットする最適な戦略を計算するために使用される学習アルゴリズムが、フォロワーによる操作に影響を受けやすいことを明らかにしている。 本稿は、リーダーとフォロワー間の学習相互作用に関する様々なシナリオにおいて、フォロワーが(最適に近い)ペイオフを計算することは、常に可能であることを示す。
  論文  参考訳（メタデータ） (2020-06-11T16:18:21Z)

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

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