論文の概要: Online Ad Allocation with Predictions

• arxiv url: http://arxiv.org/abs/2302.01827v2
• Date: Wed, 24 May 2023 23:45:19 GMT
• ステータス: 処理完了
• システム内更新日: 2023-05-26 22:48:41.995625
• Title: Online Ad Allocation with Predictions
• Title（参考訳）: 予測付きオンライン広告アロケーション
• Authors: Fabian Spaeh, Alina Ene
• Abstract要約: 我々は,マシン学習予測を組み込んだ両問題に対するアルゴリズムを開発し,最悪の場合を超えて性能を向上する。 我々のアルゴリズムは予測なしで最悪ケースのアルゴリズムを一貫して上回っている。
• 参考スコア（独自算出の注目度）: 14.213973379473652
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Display Ads and the generalized assignment problem are two well-studied online packing problems with important applications in ad allocation and other areas. In both problems, ad impressions arrive online and have to be allocated immediately to budget-constrained advertisers. Worst-case algorithms that achieve the ideal competitive ratio are known, but might act overly conservative given the predictable and usually tame nature of real-world input. Given this discrepancy, we develop an algorithm for both problems that incorporate machine-learned predictions and can thus improve the performance beyond the worst-case. Our algorithm is based on the work of Feldman et al. (2009) and similar in nature to Mahdian et al. (2007) who were the first to develop a learning-augmented algorithm for the related, but more structured Ad Words problem. We use a novel analysis to show that our algorithm is able to capitalize on a good prediction, while being robust against poor predictions. We experimentally evaluate our algorithm on synthetic and real-world data on a wide range of predictions. Our algorithm is consistently outperforming the worst-case algorithm without predictions.
• Abstract（参考訳）: ディスプレイ広告と一般化された割り当て問題は、広告アロケーションやその他の分野における重要な応用に関する2つのよく研究されたオンラインパッキング問題である。 どちらの問題においても、広告インプレッションはオンラインで公開され、予算に縛られた広告主に直ちに割り当てられる必要がある。 理想的な競合比を達成できる最悪のアルゴリズムは知られているが、現実の入力の予測可能で通常タメな性質を考えると、過度に保守的である。 この不一致を考慮し,機械学習予測を取り入れ,最悪の場合を超えて性能を向上させるアルゴリズムを開発した。 我々のアルゴリズムはfeldman et al. (2009) の研究に基づいており、本質的にはmahdian et al. (2007) と類似している。 我々は,新しい解析手法を用いて,予測の貧弱さに対して頑健でありながら,良好な予測を実現できることを示す。 提案アルゴリズムは,広範囲の予測に基づいて,合成および実世界のデータに対して実験的に評価する。 我々のアルゴリズムは予測なしで最悪ケースのアルゴリズムを一貫して上回っている。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Primal-Dual Algorithms with Predictions for Online Bounded Allocation and Ad-Auctions Problems [0.0]
  本稿では,オンライン境界割当問題とオンライン広告入札問題に対する機械学習予測を用いたアルゴリズムを提案する。 予測の質に応じて競合性能を達成するアルゴリズムを構築した。
  論文  参考訳（メタデータ） (2024-02-13T13:02:11Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• The Primal-Dual method for Learning Augmented Algorithms [10.2730668356857]
  我々は、オンラインアルゴリズムの原始二重法を拡張し、次のアクションについてオンラインアルゴリズムにアドバイスする予測を組み込む。 我々のアルゴリズムは、予測が正確である場合にも、予測が誤解を招くとき、適切な保証を維持しながら、どのオンラインアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-22T11:58:47Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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