論文の概要: Adversarial Deep Learning for Online Resource Allocation

• arxiv url: http://arxiv.org/abs/2111.10285v1
• Date: Fri, 19 Nov 2021 15:48:43 GMT
• ステータス: 翻訳完了
• システム内更新日: 2021-11-22 14:28:34.774670
• Title: Adversarial Deep Learning for Online Resource Allocation
• Title（参考訳）: オンラインリソースアロケーションのための逆深層学習
• Authors: Bingqian Du, Zhiyi Huang, Chuan Wu
• Abstract要約: 私たちはディープニューラルネットワークを使って、リソース割り当てと価格の問題に対するオンラインアルゴリズムをゼロから学習しています。 私たちの研究は、最悪のパフォーマンス保証の観点から、ディープニューラルネットワークを使用してオンラインアルゴリズムを設計した初めてのものです。
• 参考スコア（独自算出の注目度）: 12.118811903399951
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Online algorithm is an important branch in algorithm design. Designing online algorithms with a bounded competitive ratio (in terms of worst-case performance) can be hard and usually relies on problem-specific assumptions. Inspired by adversarial training from Generative Adversarial Net (GAN) and the fact that competitive ratio of an online algorithm is based on worst-case input, we adopt deep neural networks to learn an online algorithm for a resource allocation and pricing problem from scratch, with the goal that the performance gap between offline optimum and the learned online algorithm can be minimized for worst-case input. Specifically, we leverage two neural networks as algorithm and adversary respectively and let them play a zero sum game, with the adversary being responsible for generating worst-case input while the algorithm learns the best strategy based on the input provided by the adversary. To ensure better convergence of the algorithm network (to the desired online algorithm), we propose a novel per-round update method to handle sequential decision making to break complex dependency among different rounds so that update can be done for every possible action, instead of only sampled actions. To the best of our knowledge, our work is the first using deep neural networks to design an online algorithm from the perspective of worst-case performance guarantee. Empirical studies show that our updating methods ensure convergence to Nash equilibrium and the learned algorithm outperforms state-of-the-art online algorithms under various settings.
• Abstract（参考訳）: オンラインアルゴリズムはアルゴリズム設計において重要な分野である。 オンラインアルゴリズムを(最悪の場合のパフォーマンスの観点から)有界競争比で設計することは困難であり、通常は問題固有の仮定に依存する。 Generative Adversarial Net (GAN) の敵対的トレーニングや,オンラインアルゴリズムの競合比率が最悪のケース入力に基づいているという事実に触発されて,我々は,オフライン最適化と学習したオンラインアルゴリズムのパフォーマンスギャップを最小化して,リソース割り当てと価格問題に対するオンラインアルゴリズムをゼロから学習するために,ディープニューラルネットワークを採用した。 具体的には、2つのニューラルネットワークをそれぞれアルゴリズムと敵として利用し、そのアルゴリズムが相手の入力に基づいて最良の戦略を学習している間に、相手が最悪の入力を生成する責任を負うゼロサムゲームをさせる。 アルゴリズムネットワーク(所望のオンラインアルゴリズムへ)の収束性を確保するため,複数のラウンド間の複雑な依存関係を壊すようなシーケンシャルな決定を処理し,サンプル化されたアクションのみでなく,可能なすべてのアクションに対して更新を行うことが可能な,新しい1ラウンドごとの更新手法を提案する。 我々の知る限りでは、私たちの研究は、最悪のパフォーマンス保証の観点からオンラインアルゴリズムを設計するためにディープニューラルネットワークを使った初めてのものです。 実証研究により,nash均衡への収束を保証し,学習アルゴリズムが様々な条件下で最先端のオンラインアルゴリズムを上回ることを示した。

関連論文リスト

• Neural Algorithmic Reasoning Without Intermediate Supervision [21.852775399735005]
  我々は、中間的監督に訴えることなく、入出力ペアからのみニューラルネットワーク推論を学ぶことに集中する。 我々は、アルゴリズムの軌跡にアクセスできることなく、モデルの中間計算を正規化できる自己教師対象を構築する。 CLRSic Algorithmic Reasoning Benchmarkのタスクにおいて,提案手法はトラジェクトリを教師する手法と競合することを示す。
  論文  参考訳（メタデータ） (2023-06-23T09:57:44Z)
• Neural Algorithmic Reasoning for Combinatorial Optimisation [20.36694807847833]
  ニューラル推論の最近の進歩を活用して,CO問題の学習を改善することを提案する。 私たちは、COインスタンスでトレーニングする前に、関連するアルゴリズムでニューラルネットワークを事前トレーニングすることを提案します。 以上の結果から,この学習装置を用いることで,非アルゴリズム的情報深層学習モデルよりも優れた性能が得られることが示された。
  論文  参考訳（メタデータ） (2023-05-18T13:59:02Z)
• The Cascaded Forward Algorithm for Neural Network Training [61.06444586991505]
  本稿では,ニューラルネットワークのための新しい学習フレームワークであるCascaded Forward(CaFo)アルゴリズムを提案する。 FFとは異なり、我々のフレームワークは各カスケードブロックのラベル分布を直接出力する。 我々のフレームワークでは、各ブロックは独立して訓練できるので、並列加速度システムに容易に展開できる。
  論文  参考訳（メタデータ） (2023-03-17T02:01:11Z)
• Dual Algorithmic Reasoning [9.701208207491879]
  本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。 アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。 次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
  論文  参考訳（メタデータ） (2023-02-09T08:46:23Z)
• Improved Algorithms for Neural Active Learning [74.89097665112621]
  非パラメトリックストリーミング設定のためのニューラルネットワーク(NN)ベースの能動学習アルゴリズムの理論的および経験的性能を改善する。 本研究では,SOTA(State-of-the-art (State-the-art)) 関連研究で使用されるものよりも,アクティブラーニングに適する人口減少を最小化することにより,2つの後悔の指標を導入する。
  論文  参考訳（メタデータ） (2022-10-02T05:03:38Z)
• Solving the Online Assignment Problem with Machine Learned Advice [0.0]
  オンライン代入問題に対するオンラインアルゴリズムは、事前に入力全体を予測する機械学習アルゴリズムをシミュレートして提供する。 機械学習予測誤差が増加するにつれて、解の質が低下することを示す。
  論文  参考訳（メタデータ） (2022-08-08T09:54:22Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Online Adversarial Attacks [57.448101834579624]
  我々は、実世界のユースケースで見られる2つの重要な要素を強調し、オンライン敵攻撃問題を定式化する。 まず、オンライン脅威モデルの決定論的変種を厳格に分析する。 このアルゴリズムは、現在の最良の単一しきい値アルゴリズムよりも、$k=2$の競争率を確実に向上させる。
  論文  参考訳（メタデータ） (2021-03-02T20:36:04Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Evolving Reinforcement Learning Algorithms [186.62294652057062]
  メタラーニング強化学習アルゴリズムの手法を提案する。 学習アルゴリズムはドメインに依存しないため、トレーニング中に見えない新しい環境に一般化することができる。 従来の制御タスク、gridworld型タスク、atariゲームよりも優れた一般化性能を得る2つの学習アルゴリズムに注目した。
  論文  参考訳（メタデータ） (2021-01-08T18:55:07Z)
• Learning Robust Algorithms for Online Allocation Problems Using Adversarial Training [10.14260510961573]
  機械学習アプローチを用いて、オンラインアロケーション(二部マッチング)のアルゴリズムを見つけるという課題に対処する。 本稿では,従来のオンライン予算マッチング問題であるAdWords問題に着目し,理論的および実用的意義の両面から考察する。
  論文  参考訳（メタデータ） (2020-10-16T14:33:11Z)

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

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