論文の概要: Differentiable Bilevel Programming for Stackelberg Congestion Games
- arxiv url: http://arxiv.org/abs/2209.07618v1
- Date: Thu, 15 Sep 2022 21:32:23 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-19 13:36:47.709033
- Title: Differentiable Bilevel Programming for Stackelberg Congestion Games
- Title（参考訳）: stackelberg congestionゲームのための微分可能双レベルプログラミング
- Authors: Jiayang Li, Jing Yu, Qianni Wang, Boyi Liu, Zhaoran Wang, Yu Marco Nie
- Abstract要約: Stackelberg Congestion Game (SCG) は、リーダーが利得を最大化するための二段階のプログラムである。
本研究は,従来の手法と機械学習の最新の発展を融合した,微分可能プログラミングによるSCGにアプローチする。
- 参考スコア（独自算出の注目度）: 53.99859235245136
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: A Stackelberg congestion game (SCG) is a bilevel program in which a leader
aims to maximize their own gain by anticipating and manipulating the
equilibrium state at which followers settle by playing a congestion game.
Large-scale SCGs are well known for their intractability and complexity. This
study approaches SCGs through differentiable programming, which marries the
latest developments in machine learning with conventional methodologies. The
core idea centers on representing the lower-level equilibrium problem using an
evolution path formed by the imitative logit dynamics. It enables the use of
automatic differentiation over the evolution path towards equilibrium, leading
to a double-loop gradient descent algorithm. We further show the fixation on
the lower-level equilibrium may be a self-imposed computational obstacle.
Instead, the leader may only look ahead along the followers' evolution path for
a few steps, while updating their decisions in sync with the followers through
a co-evolution process. The revelation gives rise to a single-loop algorithm
that is more efficient in terms of both memory consumption and computation
time. Through numerical experiments that cover a wide range of benchmark
problems, we find the single-loop algorithm consistently strikes a good balance
between solution quality and efficiency, outperforming not only the standard
double-loop implementation but also other methods from the literature.
Importantly, our results highlight both the wastefulness of "full anticipation"
and the peril of "zero anticipation". If a quick-and-dirty heuristic is needed
for solving a really large SCG, the proposed single-loop algorithm with a
one-step look-ahead makes an ideal candidate.
- Abstract（参考訳）: スタックルバーグ混雑ゲーム(英: stackelberg crowded game, scg)は、リーダーが、混雑ゲームを行うことでフォロワーが落ち着く平衡状態を予測し、操作することで、自身の利益を最大化することを目指す、二段階のプログラムである。
大規模scgはその難易度と複雑さでよく知られている。
本研究は,従来の手法と機械学習の最新の発展を融合した,微分可能プログラミングによるSCGにアプローチする。
核となるアイデアは、模倣ロジットダイナミクスによって形成された進化経路を用いて、低レベルの平衡問題を表現することに集中する。
これにより、平衡への進化経路上の自動微分が可能となり、二重ループ勾配降下アルゴリズムが実現される。
さらに, 低次平衡の固定は, 自発的計算障害である可能性が示唆された。
代わりに、リーダーはフォロワの進化経路に沿って数ステップしか前進しないが、共同進化プロセスを通じてフォロワと同期して決定を更新できる。
この啓示により、メモリ消費と計算時間の両方においてより効率的なシングルループアルゴリズムが生まれる。
幅広いベンチマーク問題をカバーする数値実験により、単一ループアルゴリズムはソリューションの品質と効率のバランスが良く、標準のダブルループ実装だけでなく、文献からの他の手法よりも優れていることがわかった。
以上より,「完全な期待」の無駄さと「ゼロ期待」の危険を浮き彫りにした。
非常に大きな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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。