論文の概要: Towards Optimal Robustness in Learning-Augmented Paging

• arxiv url: http://arxiv.org/abs/2606.01342v3
• Date: Mon, 08 Jun 2026 06:33:53 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-06-09 14:42:04.765313
• Title: Towards Optimal Robustness in Learning-Augmented Paging
• Title（参考訳）: 学習増強型ページングにおける最適ロバスト性を目指して
• Authors: Peng Chen, Hailiang Zhao, Xueyan Tang, Yixuan Wang, Shuiguang Deng,
• Abstract要約: 単純なMLベースのアプローチに対する大きな利点は、予測が不正確であっても最悪のケースパフォーマンスを保証する、エンハンウンドロバスト性である。 事前の作業はランダムな設定で2H_k + O(1)$のバウンダリを達成し、最適競合比$H_k$にギャップを残している。 我々は,学習増強型ページングのための加算定数まで,最も可能性の高いロバスト性を実現する新しいフレームワークを開発した。
• 参考スコア（独自算出の注目度）: 22.25755140482832
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Learning-augmented paging has been extensively studied in recent years. A key advantage over naive ML-based approaches is \emph{bounded robustness}, which guarantees worst-case performance even when predictions are inaccurate, making these algorithms valuable for real-world systems. Prior work achieves robustness bounds of $2H_k + O(1)$ in the randomized setting, leaving a gap to the optimal competitive ratio $H_k$. In this paper, we study how to close this gap. We begin by reviewing online optimality and proving a new property of the latest $H_k$-competitive algorithm, which facilitates our analysis in the learning-augmented setting. Then, we review existing learning-augmented paging algorithms and introduce a unifying primitive, the \emph{relative prediction budget}, which captures the essence of establishing robustness and reveals that prior algorithms either overuse or underutilize predictions. Guided by the above analysis, we develop a new framework that achieves the best-possible robustness up to an additive constant for learning-augmented paging: $H_k + O(1)$. Experiments further demonstrate strong practical performance.
• Abstract（参考訳）: 近年,学習増強型ページングの研究が盛んに行われている。 ナイーブなMLベースのアプローチに対する大きな利点は、予測が不正確であっても最悪のケースパフォーマンスを保証する、‘emph{bounded robustness’である。 事前の作業は、ランダムな設定で2H_k + O(1)$のロバスト性バウンダリを達成し、最適な競合比$H_k$にギャップを残している。 本稿では,このギャップを埋める方法について検討する。 我々はまず、オンライン最適性をレビューし、最新の$H_k$-competitiveアルゴリズムの新たな特性を証明することから始める。 そして、既存の学習強化型ページングアルゴリズムをレビューし、統一プリミティブである 'emph{relative prediction budget} を導入し、ロバスト性を確立することの本質を捉え、事前アルゴリズムが過剰使用または過小評価することを明らかにする。 以上の分析で導かれた新たなフレームワークは、学習増強型ページングのための加算定数まで、最も可能性の高いロバスト性を実現する。 実験は、さらに強力な実用性能を示す。

関連論文リスト

• Learning-Augmented Online Scheduling with Parsimonious Preemption [49.18367863905825]
  レイテンシを最適化しながらプリエンプションを抑制する学習強化スケジューリングに関する最初の体系的研究を行う。 その結果,1ジョブ当たり$O(1)$プリエンプションのみを精度良く予測する単一および非関連並列マシンに対して$O(1)$-competitiveアルゴリズムが得られた。
  論文  参考訳（メタデータ） (2026-05-22T05:58:52Z)
• Is Best-of-N the Best of Them? Coverage, Scaling, and Optimality in Inference-Time Alignment [54.787826863212146]
  推論時間計算は、言語モデルのパフォーマンスをスケールするための強力な軸を提供する。 我々は, (i) 応答品質, (ii) 計算量の観点から, 推論時アライメントアルゴリズムの性能を解析する。 我々は$textttInferenceTimePessimism$を紹介した。これは推論時間計算の故意使用を通じて報酬ハッキングを緩和する新しいアルゴリズムである。
  論文  参考訳（メタデータ） (2025-03-27T18:00:08Z)
• Overcoming Brittleness in Pareto-Optimal Learning-Augmented Algorithms [6.131022957085439]
  本稿では,ユーザ特定プロファイルを用いて,アルゴリズムの性能のスムーズさを強制する新しいフレームワークを提案する。 我々は、この新しいアプローチを、よく研究されたオンライン問題、すなわち片道取引問題に適用する。
  論文  参考訳（メタデータ） (2024-08-07T23:15:21Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• 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)
• Robust Learning-Augmented Caching: An Experimental Study [8.962235853317996]
  キャッシュにおける鍵となる最適化問題は、将来を知ることなく最適に解決できない。 学習強化アルゴリズムの新しい分野は、古典的なオンラインキャッシュアルゴリズムを活用するソリューションを提案する。 簡単な手法は、高い性能の予測器よりも低いオーバーヘッドしか持たないことを示す。
  論文  参考訳（メタデータ） (2021-06-28T13:15:07Z)
• Debiased Off-Policy Evaluation for Recommendation Systems [8.63711086812655]
  A/Bテストは信頼できるが、時間と費用がかかり、失敗のリスクが伴う。 提案手法は,履歴データに対するアルゴリズムの性能を推定する手法である。 提案手法は,最先端手法よりも平均2乗誤差が小さい。
  論文  参考訳（メタデータ） (2020-02-20T02:30:02Z)

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

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