論文の概要: Robust Learning-Augmented Caching: An Experimental Study

• arxiv url: http://arxiv.org/abs/2106.14693v1
• Date: Mon, 28 Jun 2021 13:15:07 GMT
• ステータス: 処理完了
• システム内更新日: 2021-06-29 13:59:00.963512
• Title: Robust Learning-Augmented Caching: An Experimental Study
• Title（参考訳）: robust learning-augmented caching: 実験的検討
• Authors: Jakub Ch{\l}\k{e}dowski, Adam Polak, Bartosz Szabucki, Konrad Zolna
• Abstract要約: キャッシュにおける鍵となる最適化問題は、将来を知ることなく最適に解決できない。 学習強化アルゴリズムの新しい分野は、古典的なオンラインキャッシュアルゴリズムを活用するソリューションを提案する。 簡単な手法は、高い性能の予測器よりも低いオーバーヘッドしか持たないことを示す。
• 参考スコア（独自算出の注目度）: 8.962235853317996
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Effective caching is crucial for the performance of modern-day computing systems. A key optimization problem arising in caching -- which item to evict to make room for a new item -- cannot be optimally solved without knowing the future. There are many classical approximation algorithms for this problem, but more recently researchers started to successfully apply machine learning to decide what to evict by discovering implicit input patterns and predicting the future. While machine learning typically does not provide any worst-case guarantees, the new field of learning-augmented algorithms proposes solutions that leverage classical online caching algorithms to make the machine-learned predictors robust. We are the first to comprehensively evaluate these learning-augmented algorithms on real-world caching datasets and state-of-the-art machine-learned predictors. We show that a straightforward method -- blindly following either a predictor or a classical robust algorithm, and switching whenever one becomes worse than the other -- has only a low overhead over a well-performing predictor, while competing with classical methods when the coupled predictor fails, thus providing a cheap worst-case insurance.
• Abstract（参考訳）: 現代のコンピュータシステムの性能には効果的なキャッシュが不可欠である。 キャッシングで発生する重要な最適化問題は、新しいアイテムのために余地を作るために退避するアイテムは、未来を知らずに最適に解決できない。 この問題には多くの古典的近似アルゴリズムがあるが、近年、研究者たちは暗黙の入力パターンを発見し、未来を予測することによって、何を勝ち取るかを決定するために機械学習をうまく適用し始めた。 機械学習は通常、最悪のケースの保証を提供しないが、新しい学習型アルゴリズムの分野は、従来のオンラインキャッシングアルゴリズムを活用して、マシン主導の予測器を堅牢にするソリューションを提案する。 私たちは、これらの学習強化アルゴリズムを、実世界のキャッシュデータセットと最先端のマシン学習予測器で包括的に評価しました。 予測器または古典的ロバストアルゴリズムを盲目的に追従し、一方が他方よりも悪くなると切り換えるという単純な手法は、優れた予測器よりもオーバーヘッドが低く、一方、結合予測器が故障した場合に古典的手法と競合し、安価な最悪の保険を提供する。

関連論文リスト

• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• 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)
• Parsimonious Learning-Augmented Caching [29.975391787684966]
  本稿では,学習補助アルゴリズムが同時に予測を利用できるような設定を導入し,研究する。 定量的に類似した結果が得られるが、予測のサブ線形数のみを用いることを示す。
  論文  参考訳（メタデータ） (2022-02-09T03:40:11Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• A Novel Prediction Setup for Online Speed-Scaling [3.3440413258080577]
  アルゴリズムを設計(スケジュール)する際にエネルギー的考慮を組み込むのが基本である。 本稿では,古典的,期限ベース,オンラインの高速スケーリング問題に対して,両世界の長所を把握しようと試みる。
  論文  参考訳（メタデータ） (2021-12-06T14:46:20Z)
• 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)

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

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