論文の概要: Primal-Dual Algorithms with Predictions for Online Bounded Allocation
and Ad-Auctions Problems
- arxiv url: http://arxiv.org/abs/2402.08701v1
- Date: Tue, 13 Feb 2024 13:02:11 GMT
- ステータス: 処理完了
- システム内更新日: 2024-02-15 18:22:13.140554
- Title: Primal-Dual Algorithms with Predictions for Online Bounded Allocation
and Ad-Auctions Problems
- Title（参考訳）: オンライン境界割当問題と広告入札問題に対する予測付き原始双対アルゴリズム
- Authors: Eniko Kevi and Nguyen Kim Thang
- Abstract要約: 本稿では,オンライン境界割当問題とオンライン広告入札問題に対する機械学習予測を用いたアルゴリズムを提案する。
予測の質に応じて競合性能を達成するアルゴリズムを構築した。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: Matching problems have been widely studied in the research community,
especially Ad-Auctions with many applications ranging from network design to
advertising. Following the various advancements in machine learning, one
natural question is whether classical algorithms can benefit from machine
learning and obtain better-quality solutions. Even a small percentage of
performance improvement in matching problems could result in significant gains
for the studied use cases. For example, the network throughput or the revenue
of Ad-Auctions can increase remarkably. This paper presents algorithms with
machine learning predictions for the Online Bounded Allocation and the Online
Ad-Auctions problems. We constructed primal-dual algorithms that achieve
competitive performance depending on the quality of the predictions. When the
predictions are accurate, the algorithms' performance surpasses previous
performance bounds, while when the predictions are misleading, the algorithms
maintain standard worst-case performance guarantees. We provide supporting
experiments on generated data for our theoretical findings.
- Abstract（参考訳）: マッチング問題は研究コミュニティ、特にネットワークデザインから広告まで多くのアプリケーションで研究されている。
機械学習の様々な進歩に続いて、ある自然な疑問は、古典的なアルゴリズムが機械学習の恩恵を受け、高品質なソリューションを得ることができるかどうかである。
マッチング問題におけるパフォーマンス改善のごく一部でさえ、研究対象のユースケースに対して大きな利益をもたらす可能性がある。
例えば、ネットワークのスループットや広告の収益は著しく増加する。
本稿では,オンライン境界割当問題とオンライン広告入札問題に対する機械学習予測を用いたアルゴリズムを提案する。
予測の質に応じて競合性能を達成するプライマル・ディレクティブアルゴリズムを構築した。
予測が正確であれば、アルゴリズムの性能は以前の性能限界を超え、予測が誤解を招く場合、アルゴリズムは標準的な最悪の性能保証を維持する。
理論的な発見のために, 生成データに関する実験を行う。
関連論文リスト
- Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。
この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。
本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文 参考訳（メタデータ） (2024-03-12T08:40:21Z) - Online Ad Allocation with Predictions [14.213973379473652]
我々は,マシン学習予測を組み込んだ両問題に対するアルゴリズムを開発し,最悪の場合を超えて性能を向上する。
我々のアルゴリズムは予測なしで最悪ケースのアルゴリズムを一貫して上回っている。
論文 参考訳（メタデータ） (2023-02-03T16:03:49Z) - 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) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳（メタデータ） (2020-10-22T04:51:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。