論文の概要: Paging with Succinct Predictions

• arxiv url: http://arxiv.org/abs/2210.02775v1
• Date: Thu, 6 Oct 2022 09:26:34 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-07 18:05:37.434577
• Title: Paging with Succinct Predictions
• Title（参考訳）: 簡潔な予測によるパッシング
• Authors: Antonios Antoniadis, Joan Boyar, Marek Eli\'a\v{s}, Lene M. Favrholdt, Ruben Hoeksma, Kim S. Larsen, Adam Polak, Bertrand Simon
• Abstract要約: 予測情報を最小限に抑えるという新たな視点から学習増強型ページングについて検討する。 学習強化アルゴリズムの3つの望ましい特性をすべて満たす2つの設定のアルゴリズムを開発する。
• 参考スコア（独自算出の注目度）: 25.959849403994202
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Paging is a prototypical problem in the area of online algorithms. It has also played a central role in the development of learning-augmented algorithms -- a recent line of research that aims to ameliorate the shortcomings of classical worst-case analysis by giving algorithms access to predictions. Such predictions can typically be generated using a machine learning approach, but they are inherently imperfect. Previous work on learning-augmented paging has investigated predictions on (i) when the current page will be requested again (reoccurrence predictions), (ii) the current state of the cache in an optimal algorithm (state predictions), (iii) all requests until the current page gets requested again, and (iv) the relative order in which pages are requested. We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. More specifically, the predictions obtained alongside each page request are limited to one bit only. We consider two natural such setups: (i) discard predictions, in which the predicted bit denotes whether or not it is ``safe'' to evict this page, and (ii) phase predictions, where the bit denotes whether the current page will be requested in the next phase (for an appropriate partitioning of the input into phases). We develop algorithms for each of the two setups that satisfy all three desirable properties of learning-augmented algorithms -- that is, they are consistent, robust and smooth -- despite being limited to a one-bit prediction per request. We also present lower bounds establishing that our algorithms are essentially best possible.
• Abstract（参考訳）: ページングはオンラインアルゴリズムの分野における典型的な問題である。 これは、アルゴリズムに予測へのアクセスを与えることで、古典的な最悪のケース分析の欠点を改善することを目的としている最近の研究である。 このような予測は通常、機械学習のアプローチで生成されるが、本質的には不完全である。 学習増強型ページングに関する先行研究は、予測について調査している。 (i)現在のページが再び要求される場合(再帰予測) (ii)最適なアルゴリズム(状態予測)におけるキャッシュの現在の状態 (iii)現在のページが再びリクエストされるまでの全リクエスト (iv)ページが要求される相対順序 予測情報の最小化を求める新たな視点から学習増強ページングについて検討する。 より具体的には、各ページリクエストで得られた予測は1ビットに限られる。 2つの自然な設定を考える。 (i)予測ビットが、このページを退去させるのに ``safe'' であるか否かを示す予測を破棄し、 (ii) フェーズ予測では、ビットは次のフェーズで現在のページが要求されるかどうかを示す(入力を適切なフェーズに分割する)。 当社では,1リクエストあたり1ビットの予測に制限があるにも関わらず,学習型アルゴリズムの3つの望ましい特性すべて – すなわち一貫性,堅牢性,スムース – を満たした,2つのセットアップ毎にアルゴリズムを開発しています。 アルゴリズムが本質的に最善であることを示す下限も提示します。

関連論文リスト

• Non-clairvoyant Scheduling with Partial Predictions [17.387787159892287]
  本稿では, 頑健性, 一貫性, 滑らかさの基準を満たす学習補助アルゴリズムを提案する。 また,予測数を制限するシナリオに固有の一貫性と滑らかさの新たなトレードオフも提示する。
  論文  参考訳（メタデータ） (2024-05-02T05:29:22Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Best of Many in Both Worlds: Online Resource Allocation with Predictions under Unknown Arrival Model [16.466711636334587]
  オンライン意思決定者は、到着や要求など、将来の変数に関する予測を得ることが多い。 意思決定者にとって予測精度は未知であるため、予測に盲目的に追従することは有害である。 我々は未知の予測精度に頑健な方法で予測を利用するアルゴリズムを開発した。
  論文  参考訳（メタデータ） (2024-02-21T04:57:32Z)
• 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)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
  論文  参考訳（メタデータ） (2022-05-25T15:24:03Z)
• 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)
• Online Paging with a Vanishing Regret [6.520803851931362]
  本稿では,オンラインアルゴリズムが複数の予測器にアクセスでき,ページ到着時刻の予測列を生成するオンラインページング問題の変種について考察する。 予測器は時折予測誤差を発生させ、そのうちの少なくとも1つが予測誤差のサブ線形数を生成すると仮定する。 この仮定は、最適オフラインアルゴリズムに対する時間平均後悔が無限大になる傾向にあるランダム化オンラインアルゴリズムの設計に十分であることを示す。
  論文  参考訳（メタデータ） (2020-11-18T18:17:49Z)

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

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