論文の概要: Double Coverage with Machine-Learned Advice

• arxiv url: http://arxiv.org/abs/2103.01640v1
• Date: Tue, 2 Mar 2021 11:04:33 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-04 01:41:17.005567
• Title: Double Coverage with Machine-Learned Advice
• Title（参考訳）: マシンラーニングによるダブルカバー
• Authors: Alexander Lindermayr, Nicole Megow, Bertrand Simon
• Abstract要約: オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
• 参考スコア（独自算出の注目度）: 100.23487145400833
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study the fundamental online $k$-server problem in a learning-augmented setting. While in the traditional online model, an algorithm has no information about the request sequence, we assume that there is given some advice (e.g. machine-learned predictions) on an algorithm's decision. There is, however, no guarantee on the quality of the prediction and it might be far from being correct. Our main result is a learning-augmented variation of the well-known Double Coverage algorithm for k-server on the line (Chrobak et al., SIDMA 1991) in which we integrate predictions as well as our trust into their quality. We give an error-dependent competitive ratio, which is a function of a user-defined trustiness parameter, and which interpolates smoothly between an optimal consistency, the performance in case that all predictions are correct, and the best-possible robustness regardless of the prediction quality. When given good predictions, we improve upon known lower bounds for online algorithms without advice. We further show that our algorithm achieves for any k an almost optimal consistency-robustness tradeoff, within a class of deterministic algorithms respecting local and memoryless properties. Our algorithm outperforms a previously proposed (more general) learning-augmented algorithm. It is remarkable that the previous algorithm heavily exploits memory, whereas our algorithm is memoryless. Finally, we demonstrate in experiments the practicability and the superior performance of our algorithm on real-world data.
• Abstract（参考訳）: オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 従来のオンラインモデルでは、アルゴリズムはリクエストシーケンスに関する情報を持たないが、いくつかのアドバイスが与えられた(例)。 アルゴリズムの決定に関する機械的な予測)。 しかし、予測の質は保証されておらず、その正確さには程遠いかもしれない。 私たちの主な結果は、ライン上のkサーバ(Chrobak et al.、SIDMA 1991)のためのよく知られたダブルカバレッジアルゴリズムの学習強化されたバリエーションであり、予測と私たちの信頼を彼らの品質に統合しています。 ユーザ定義信頼度パラメータの関数であり、最適な一貫性、全ての予測が正しい場合のパフォーマンス、そして予測品質に関係なく最適なロバスト性の間をスムーズに補間する誤差依存競争比を与える。 良い予測を与えると、オンラインアルゴリズムの既知の下限をアドバイスなしで改善します。 さらに,本アルゴリズムは局所特性とメモリレス特性を尊重する決定論的アルゴリズムのクラスにおいて,任意のkに対してほぼ最適な一貫性-破壊性トレードオフを達成することを示す。 我々のアルゴリズムは、以前に提案された(より一般的な)学習増強アルゴリズムより優れている。 これまでのアルゴリズムはメモリを多用していたが、我々のアルゴリズムはメモリレスである。 最後に、実世界のデータに対するアルゴリズムの実践性と優れた性能を実験で実証する。

関連論文リスト

• Competitive Algorithms for Online Knapsack with Succinct Predictions [16.793099279933163]
  オンラインのknapsack問題では、異なる値と重みを持つオンラインで到着するアイテムをキャパシティ限定のknapsackにまとめて、受け入れられたアイテムの総価値を最大化する。 この問題に対するテキスト学習強化アルゴリズムについて検討し、機械学習による予測を用いて悲観的な最悪のケースの保証を超えて行動することを目的とする。
  論文  参考訳（メタデータ） (2024-06-26T20:38:00Z)
• 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)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
  非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。 我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。 これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
  論文  参考訳（メタデータ） (2022-02-21T13:18:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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