論文の概要: Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms

• arxiv url: http://arxiv.org/abs/2010.11443v1
• Date: Thu, 22 Oct 2020 04:51:01 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-04 08:02:06.837422
• Title: Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms
• Title（参考訳）: 学習提示型オンラインアルゴリズムのための最適ロバストネス・コンシスタンストレードオフ
• Authors: Alexander Wei and Fred Zhang
• Abstract要約: 機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
• 参考スコア（独自算出の注目度）: 85.97516436641533
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We study the problem of improving the performance of online algorithms by incorporating machine-learned predictions. The goal is to design algorithms that are both consistent and robust, meaning that the algorithm performs well when predictions are accurate and maintains worst-case guarantees. Such algorithms have been studied in a recent line of works due to Lykouris and Vassilvitskii (ICML '18) and Purohit et al (NeurIPS '18). They provide robustness-consistency trade-offs for a variety of online problems. However, they leave open the question of whether these trade-offs are tight, i.e., to what extent to such trade-offs are necessary. In this paper, we provide the first set of non-trivial lower bounds for competitive analysis using machine-learned predictions. We focus on the classic problems of ski-rental and non-clairvoyant scheduling and provide optimal trade-offs in various settings.
• Abstract（参考訳）: 機械学習予測を取り入れたオンラインアルゴリズムの性能向上問題について検討する。 目標は、一貫性と堅牢性の両方を持つアルゴリズムを設計することであり、つまり、予測が正確で最悪のケースの保証を維持している場合に、アルゴリズムがうまく機能することを意味する。 このようなアルゴリズムはLykouris と Vassilvitskii (ICML '18) と Purohit et al (NeurIPS '18) によって近年研究されている。 さまざまなオンライン問題に対する堅牢性と一貫性のトレードオフを提供する。 しかし、これらのトレードオフが厳密であるかどうか、すなわち、どの程度のトレードオフが必要なのか、という疑問は残る。 本稿では,機械学習予測を用いた競争分析のための非自明な下限の第一セットを提案する。 我々は,スキーレンタルと非クレアボイラントスケジューリングの古典的な問題に焦点をあて,様々な設定で最適なトレードオフを提供する。

関連論文リスト

• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Improving Online Algorithms via ML Predictions [19.03466073202238]
  我々は,スキーレンタルと非好ましくないジョブスケジューリングの2つの古典的問題を考察し,予測を用いて意思決定を行う新しいオンラインアルゴリズムを得る。 これらのアルゴリズムは予測器の性能を損なうものであり、より良い予測で改善するが、予測が貧弱な場合はあまり劣化しない。
  論文  参考訳（メタデータ） (2024-07-25T02:17:53Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Improved Learning-Augmented Algorithms for the Multi-Option Ski Rental Problem via Best-Possible Competitive Analysis [0.1529342790344802]
  マルチオプションスキーレンタル問題に対する学習向上アルゴリズムを提案する。 提案アルゴリズムは,この問題に対して最も有効なランダム化競合アルゴリズムに基づいている。
  論文  参考訳（メタデータ） (2023-02-14T05:05:03Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Online Search with Predictions: Pareto-optimal Algorithm and its Applications in Energy Markets [32.50099216716867]
  本稿では、揮発性電力市場におけるエネルギー取引のための学習強化アルゴリズムを開発する。 オンライン検索問題に対する競合アルゴリズムの設計には,機械学習による予測が組み込まれている。
  論文  参考訳（メタデータ） (2022-11-12T04:12:10Z)
• 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)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)

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

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