論文の概要: Learning Robust Algorithms for Online Allocation Problems Using
Adversarial Training
- arxiv url: http://arxiv.org/abs/2010.08418v1
- Date: Fri, 16 Oct 2020 14:33:11 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-06 20:20:57.210473
- Title: Learning Robust Algorithms for Online Allocation Problems Using
Adversarial Training
- Title(参考訳): 逆学習を用いたオンライン配置問題に対するロバストアルゴリズムの学習
- Authors: Goran Zuzic, Di Wang, Aranyak Mehta, D. Sivakumar
- Abstract要約: 機械学習アプローチを用いて、オンラインアロケーション(二部マッチング)のアルゴリズムを見つけるという課題に対処する。
本稿では,従来のオンライン予算マッチング問題であるAdWords問題に着目し,理論的および実用的意義の両面から考察する。
- 参考スコア(独自算出の注目度): 10.14260510961573
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We address the challenge of finding algorithms for online allocation (i.e.
bipartite matching) using a machine learning approach. In this paper, we focus
on the AdWords problem, which is a classical online budgeted matching problem
of both theoretical and practical significance. In contrast to existing work,
our goal is to accomplish algorithm design {\em tabula rasa}, i.e., without any
human-provided insights or expert-tuned training data beyond specifying the
objective and constraints of the optimization problem. We construct a framework
based on insights and ideas from game theory, adversarial training and GANs Key
to our approach is to generate adversarial examples that expose the weakness of
any given algorithm. A unique challenge in our context is to generate complete
examples from scratch rather than perturbing given examples and we demonstrate
this can be accomplished for the Adwords problem. We use this framework to
co-train an algorithm network and an adversarial network against each other
until they converge to an equilibrium. This approach finds algorithms and
adversarial examples that are consistent with known optimal results. Secondly,
we address the question of robustness of the algorithm, namely can we design
algorithms that are both strong under practical distributions, as well as
exhibit robust performance against adversarial instances. To accomplish this,
we train algorithm networks using a mixture of adversarial and practical
distributions like power-laws; the resulting networks exhibit a smooth
trade-off between the two input regimes.
- Abstract(参考訳): 機械学習アプローチを用いて、オンラインアロケーション(二部マッチング)のアルゴリズムを見つけるという課題に対処する。
本稿では,従来のオンライン予算マッチング問題であるAdWords問題に着目し,理論的および実用的意義の両面から考察する。
既存の研究とは対照的に、我々のゴールはアルゴリズム設計を達成すること、すなわち、最適化問題の目的と制約を規定する以外に、人為的な洞察や専門家による訓練データがないことである。
我々は,ゲーム理論,敵対的トレーニング,およびGANsキーからの洞察とアイデアに基づくフレームワークを構築し,アルゴリズムの弱点を露呈する敵例を生成する。
私たちのコンテキストにおけるユニークな課題は、与えられた例を摂動するのではなく、スクラッチから完全な例を生成することです。
このフレームワークを用いて,アルゴリズムネットワークと逆ネットワークが平衡に収束するまでの協調学習を行う。
このアプローチは、既知の最適結果と一致するアルゴリズムや逆例を見つける。
次に,本アルゴリズムのロバスト性の問題,すなわち,実用的分布下では強いアルゴリズムを設計でき,また,敵インスタンスに対するロバストな性能を示すことができる。
これを実現するために,電力規則のような逆分布と実用的な分布を混合してアルゴリズムネットワークを訓練し,その結果,二つの入力レジーム間のスムーズなトレードオフを示す。
関連論文リスト
- Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。
この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。
本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文 参考訳(メタデータ) (2024-03-12T08:40:21Z) - Data-driven algorithm design using neural networks with applications to
branch-and-cut [1.597617022056624]
我々は、この研究の行において、最高のパフォーマンスを持つ1つのアルゴリズムを選択する代わりに、そのインスタンスに基づいてアルゴリズムを選択することができるというアイデアを導入することによって、最近の研究の上に構築する。
我々は、このアイデアを形式化し、データ駆動アルゴリズム設計における最近の研究の精神の中で、この学習問題に対する厳密なサンプル複雑性を導出する。
言い換えれば、ニューラルネットワークは混合整数最適化インスタンスを入力として取り、そのインスタンスの小さな分岐とカットツリーをもたらす決定を出力する。
論文 参考訳(メタデータ) (2024-02-04T03:03:27Z) - Dual Algorithmic Reasoning [9.701208207491879]
本稿では,基礎となるアルゴリズム問題の双対性を利用してアルゴリズムを学習することを提案する。
アルゴリズム学習における最適化問題の2つの定義を同時に学習することで、より良い学習が可能になることを実証する。
次に、難易度の高い脳血管分類タスクにデプロイすることで、二元アルゴリズム推論の現実的な実用性を検証する。
論文 参考訳(メタデータ) (2023-02-09T08:46:23Z) - On the Convergence of Distributed Stochastic Bilevel Optimization
Algorithms over a Network [55.56019538079826]
バイレベル最適化は、幅広い機械学習モデルに適用されている。
既存のアルゴリズムの多くは、分散データを扱うことができないように、シングルマシンの設定を制限している。
そこで我々は,勾配追跡通信機構と2つの異なる勾配に基づく分散二段階最適化アルゴリズムを開発した。
論文 参考訳(メタデータ) (2022-06-30T05:29:52Z) - Contextual Model Aggregation for Fast and Robust Federated Learning in
Edge Computing [88.76112371510999]
フェデレーション学習は、ネットワークエッジにおける分散機械学習の第一候補である。
既存のアルゴリズムは、性能の緩やかな収束や堅牢性の問題に直面している。
そこで本稿では,損失低減に対する最適コンテキスト依存境界を実現するためのコンテキストアグリゲーション手法を提案する。
論文 参考訳(メタデータ) (2022-03-23T21:42:31Z) - Adversarial Deep Learning for Online Resource Allocation [12.118811903399951]
私たちはディープニューラルネットワークを使って、リソース割り当てと価格の問題に対するオンラインアルゴリズムをゼロから学習しています。
私たちの研究は、最悪のパフォーマンス保証の観点から、ディープニューラルネットワークを使用してオンラインアルゴリズムを設計した初めてのものです。
論文 参考訳(メタデータ) (2021-11-19T15:48:43Z) - Unsupervised Domain-adaptive Hash for Networks [81.49184987430333]
ドメイン適応型ハッシュ学習はコンピュータビジョンコミュニティでかなりの成功を収めた。
UDAHと呼ばれるネットワークのための教師なしドメイン適応型ハッシュ学習手法を開発した。
論文 参考訳(メタデータ) (2021-08-20T12:09:38Z) - Geometric Deep Reinforcement Learning for Dynamic DAG Scheduling [8.14784681248878]
本稿では,現実的なスケジューリング問題を解決するための強化学習手法を提案する。
高性能コンピューティングコミュニティにおいて一般的に実行されるアルゴリズムであるColesky Factorizationに適用する。
我々のアルゴリズムは,アクター・クリティカル・アルゴリズム (A2C) と組み合わせてグラフニューラルネットワークを用いて,問題の適応表現をオンザフライで構築する。
論文 参考訳(メタデータ) (2020-11-09T10:57:21Z) - A black-box adversarial attack for poisoning clustering [78.19784577498031]
本稿では,クラスタリングアルゴリズムのロバスト性をテストするために,ブラックボックス対逆攻撃法を提案する。
我々の攻撃は、SVM、ランダムフォレスト、ニューラルネットワークなどの教師付きアルゴリズムに対しても転送可能であることを示す。
論文 参考訳(メタデータ) (2020-09-09T18:19:31Z) - Learning to Accelerate Heuristic Searching for Large-Scale Maximum
Weighted b-Matching Problems in Online Advertising [51.97494906131859]
バイパルタイトbマッチングはアルゴリズム設計の基本であり、経済市場や労働市場などに広く適用されている。
既存の正確で近似的なアルゴリズムは、通常そのような設定で失敗する。
我々は、以前の事例から学んだ知識を活用して、新しい問題インスタンスを解決するtextttNeuSearcherを提案する。
論文 参考訳(メタデータ) (2020-05-09T02:48:23Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。