論文の概要: Algorithms for Caching and MTS with reduced number of predictions

• arxiv url: http://arxiv.org/abs/2404.06280v2
• Date: Wed, 10 Apr 2024 16:30:07 GMT
• ステータス: 処理完了
• システム内更新日: 2024-04-11 16:28:25.479441
• Title: Algorithms for Caching and MTS with reduced number of predictions
• Title（参考訳）: キャッシングとMTSの予測数削減のためのアルゴリズム
• Authors: Karim Abdel Sadek, Marek Elias,
• Abstract要約: キャッシュとMSSを動作予測付きで同期するアルゴリズムを設計する。 キャッシングのアルゴリズムは1-consistentで頑健であり,そのスムーズさは予測値の減少とともに低下する。 本稿では, 予測数の減少とともに, 整合性と滑らかさが線形にスケールする一般MTSのアルゴリズムを提案する。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: ML-augmented algorithms utilize predictions to achieve performance beyond their worst-case bounds. Producing these predictions might be a costly operation -- this motivated Im et al. '22 to introduce the study of algorithms which use predictions parsimoniously. We design parsimonious algorithms for caching and MTS with action predictions, proposed by Antoniadis et al. '20, focusing on the parameters of consistency (performance with perfect predictions) and smoothness (dependence of their performance on the prediction error). Our algorithm for caching is 1-consistent, robust, and its smoothness deteriorates with the decreasing number of available predictions. We propose an algorithm for general MTS whose consistency and smoothness both scale linearly with the decreasing number of predictions. Without the restriction on the number of available predictions, both algorithms match the earlier guarantees achieved by Antoniadis et al. '20.
• Abstract（参考訳）: ML拡張アルゴリズムは、予測を利用して、最悪のケース境界を超えるパフォーマンスを達成する。 このIm et al '22は、予測を同義に使用するアルゴリズムの研究を導入する動機となった。 我々は,Antoniadisらによって提案された動作予測を用いたキャッシングとTSの類似アルゴリズムを設計し,一貫性(完全予測性能)と滑らかさ(予測誤差依存性)のパラメータに着目した。 キャッシングのアルゴリズムは, 1-consistent, robust, and its smoothness with the decrease of available predictions。 本稿では, 予測数の減少とともに, 整合性と滑らかさが線形にスケールする一般MTSのアルゴリズムを提案する。 利用可能な予測数の制限がなければ、両方のアルゴリズムはAntoniadisらによる以前の保証と一致している。

関連論文リスト

• Improving Online Algorithms via ML Predictions [19.03466073202238]
  我々は,スキーレンタルと非好ましくないジョブスケジューリングの2つの古典的問題を考察し,予測を用いて意思決定を行う新しいオンラインアルゴリズムを得る。 これらのアルゴリズムは予測器の性能を損なうものであり、より良い予測で改善するが、予測が貧弱な場合はあまり劣化しない。
  論文  参考訳（メタデータ） (2024-07-25T02:17:53Z)
• Non-clairvoyant Scheduling with Partial Predictions [17.387787159892287]
  本稿では, 頑健性, 一貫性, 滑らかさの基準を満たす学習補助アルゴリズムを提案する。 また,予測数を制限するシナリオに固有の一貫性と滑らかさの新たなトレードオフも提示する。
  論文  参考訳（メタデータ） (2024-05-02T05:29:22Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• Paging with Succinct Predictions [25.959849403994202]
  予測情報を最小限に抑えるという新たな視点から学習増強型ページングについて検討する。 学習強化アルゴリズムの3つの望ましい特性をすべて満たす2つの設定のアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2022-10-06T09:26:34Z)
• Efficient and Differentiable Conformal Prediction with General Function Classes [96.74055810115456]
  本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。 本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。 実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
  論文  参考訳（メタデータ） (2022-02-22T18:37:23Z)
• 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)

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

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