論文の概要: Differentiable Bilevel Programming for Stackelberg Congestion Games

• arxiv url: http://arxiv.org/abs/2209.07618v3
• Date: Sat, 11 May 2024 02:56:23 GMT
• ステータス: 処理完了
• システム内更新日: 2024-05-15 02:01:31.841784
• Title: Differentiable Bilevel Programming for Stackelberg Congestion Games
• Title（参考訳）: Stackelberg Congestion Gamesのための微分可能なバイレベルプログラミング
• Authors: Jiayang Li, Jing Yu, Qianni Wang, Boyi Liu, Zhaoran Wang, Yu Marco Nie,
• Abstract要約: Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。 本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。 本稿では,SCGの局所探索アルゴリズムを2つ提案する。第1に,微分可能プログラミングを用いてILDをアンロールすることで導関数を求める勾配降下アルゴリズムを提案する。 第二のアルゴリズムは、フォロワーの進化軌道を短くすることでツイストを加える。
• 参考スコア（独自算出の注目度）: 47.60156422249365
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In a Stackelberg congestion game (SCG), a leader aims to maximize their own gain by anticipating and manipulating the equilibrium state at which the followers settle by playing a congestion game. Often formulated as bilevel programs, large-scale SCGs are well known for their intractability and complexity. Here, we attempt to tackle this computational challenge by marrying traditional methodologies with the latest differentiable programming techniques in machine learning. The core idea centers on replacing the lower-level equilibrium problem with a smooth evolution trajectory defined by the imitative logit dynamic (ILD), which we prove converges to the equilibrium of the congestion game under mild conditions. Building upon this theoretical foundation, we propose two new local search algorithms for SCGs. The first is a gradient descent algorithm that obtains the derivatives by unrolling ILD via differentiable programming. Thanks to the smoothness of ILD, the algorithm promises both efficiency and scalability. The second algorithm adds a heuristic twist by cutting short the followers' evolution trajectory. Behaviorally, this means that, instead of anticipating the followers' best response at equilibrium, the leader seeks to approximate that response by only looking ahead a limited number of steps. Our numerical experiments are carried out over various instances of classic SCG applications, ranging from toy benchmarks to large-scale real-world examples. The results show the proposed algorithms are reliable and scalable local solvers that deliver high-quality solutions with greater regularity and significantly less computational effort compared to the many incumbents included in our study.
• Abstract（参考訳）: Stackelberg Congestion Game (SCG) において、リーダーは、群集が集まる平衡状態を予測し、操作することで、自身の利益を最大化することを目的としている。 しばしば二段階プログラムとして定式化され、大規模SCGはその難易度と複雑さでよく知られている。 本稿では,従来の手法と機械学習における最新の微分可能プログラミング技術を組み合わせることで,この計算課題に挑戦する。 中心となる考え方は、低レベルの平衡問題を模倣ロジットダイナミクス (ILD) によって定義された滑らかな進化軌道に置き換えることであり、これは緩やかな条件下での渋滞ゲームの平衡に収束することを証明している。 この理論基盤を基礎として,SCGのための局所探索アルゴリズムを2つ提案する。 1つ目は、微分可能プログラミングを用いてILDをアンロールすることで微分を求める勾配降下アルゴリズムである。 ILDの滑らかさのおかげで、アルゴリズムは効率性とスケーラビリティの両方を約束する。 第2のアルゴリズムは、フォロワーの進化軌道を短くすることでヒューリスティックなツイストを加える。 行動的には、これは、フォロワーの均衡における最良の反応を予想する代わりに、リーダーは限られたステップだけを前にして、その反応を近似しようとすることを意味する。 本研究は,おもちゃのベンチマークから大規模実世界の実例まで,古典的SCGアプリケーションの様々な事例を対象とした数値実験を行った。 その結果,提案アルゴリズムは信頼性が高くスケーラブルな局所解法であり,本研究に含まれる多くの既存手法と比較して,高い正則性と計算労力の少ない高品質な解が得られることがわかった。

関連論文リスト

• Non-convex Bayesian Learning via Stochastic Gradient Markov Chain Monte Carlo [4.656426393230839]
  人工知能(AI)の台頭は、非トリップと不確実性のための現代のディープニューラルネットワーク(DNN)の効率性を重視している。 本論文ではモンテカルロ利用問題を扱うためのツールを提案する。 また,基礎となる正規方程式(ODE)システムに対する2つの動的重要度サンプリングアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-05-30T18:25:11Z)
• On the Convergence of Distributed Stochastic Bilevel Optimization Algorithms over a Network [55.56019538079826]
  バイレベル最適化は、幅広い機械学習モデルに適用されている。 既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。 そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
  論文  参考訳（メタデータ） (2022-06-30T05:29:52Z)
• HessianFR: An Efficient Hessian-based Follow-the-Ridge Algorithm for Minimax Optimization [18.61046317693516]
  HessianFR は理論的な保証を持つ効率的な Hessian-based Follow-the-Ridge アルゴリズムである。 合成および実世界の大規模画像データセットを用いてGAN(Generative Adversarial Network)のトレーニング実験を行った。
  論文  参考訳（メタデータ） (2022-05-23T04:28:52Z)
• Simple Stochastic and Online Gradient DescentAlgorithms for Pairwise Learning [65.54757265434465]
  ペアワイズ学習(Pairwise learning)とは、損失関数がペアインスタンスに依存するタスクをいう。 オンライン降下(OGD)は、ペアワイズ学習でストリーミングデータを処理する一般的なアプローチである。 本稿では,ペアワイズ学習のための手法について,シンプルでオンラインな下降を提案する。
  論文  参考訳（メタデータ） (2021-11-23T18:10:48Z)
• Training Generative Adversarial Networks with Adaptive Composite Gradient [2.471982349512685]
  本稿では,二線形ゲームにおいて線形収束する適応型コンポジットグラディエント法を提案する。 ACGは、各ステップの勾配を計算する必要がないため、半漸進的なアルゴリズムである。 結果は、ACGが以前のアルゴリズムと競合していることを示している。
  論文  参考訳（メタデータ） (2021-11-10T03:13:53Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  通信ネットワークのノード間を分散的に保存するスムーズで強い凸関数の和を最小化するタスクについて検討する。 我々は、これらの下位境界を達成するための2つの最適アルゴリズムを設計する。 我々は,既存の最先端手法と実験的な比較を行うことにより,これらのアルゴリズムの理論的効率を裏付ける。
  論文  参考訳（メタデータ） (2021-06-08T15:54:44Z)
• Single-Timescale Stochastic Nonconvex-Concave Optimization for Smooth Nonlinear TD Learning [145.54544979467872]
  本稿では,各ステップごとに1つのデータポイントしか必要としない2つの単一スケールシングルループアルゴリズムを提案する。 本研究の結果は, 同時一次および二重側収束の形で表される。
  論文  参考訳（メタデータ） (2020-08-23T20:36:49Z)
• Sparsified Linear Programming for Zero-Sum Equilibrium Finding [89.30539368124025]
  我々は、この問題に対して全く異なるアプローチを示し、それは競争力があり、しばしば、以前の最先端技術よりも桁違いに優れている。 ポーカーエンドゲームの実験により、現代の線形プログラムソルバは、ゲーム固有のCFRの現代的な変種でさえも競合することを示した。
  論文  参考訳（メタデータ） (2020-06-05T13:48:26Z)

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

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