論文の概要: An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees

• arxiv url: http://arxiv.org/abs/2405.01263v2
• Date: Mon, 17 Jun 2024 12:01:01 GMT
• ステータス: 処理完了
• システム内更新日: 2024-06-19 04:38:09.430623
• Title: An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees
• Title（参考訳）: 対数的複雑度と規則保証を考慮したオンライングラディエント型キャッシングポリシー
• Authors: Damiano Carra, Giovanni Neglia,
• Abstract要約: 我々は、対数計算の複雑さを突破するグラデーションベースのオンラインキャッシュポリシーを新たに導入する。 この進歩により、何百万ものリクエストやアイテムを伴って、大規模で現実世界のトレース上でポリシーをテストすることができます。
• 参考スコア（独自算出の注目度）: 13.844896723580858
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Commonly used caching policies, such as LRU (Least Recently Used) or LFU (Least Frequently Used), exhibit optimal performance only under specific traffic patterns. Even advanced machine learning-based methods, which detect patterns in historical request data, struggle when future requests deviate from past trends. Recently, a new class of policies has emerged that are robust to varying traffic patterns. These algorithms address an online optimization problem, enabling continuous adaptation to the context. They offer theoretical guarantees on the regret metric, which measures the performance gap between the online policy and the optimal static cache allocation in hindsight. However, the high computational complexity of these solutions hinders their practical adoption. In this study, we introduce a new variant of the gradient-based online caching policy that achieves groundbreaking logarithmic computational complexity relative to catalog size, while also providing regret guarantees. This advancement allows us to test the policy on large-scale, real-world traces featuring millions of requests and items - a significant achievement, as such scales have been beyond the reach of existing policies with regret guarantees. To the best of our knowledge, our experimental results demonstrate for the first time that the regret guarantees of gradient-based caching policies offer substantial benefits in practical scenarios.
• Abstract（参考訳）: LRU(Least recent Used)やLFU(Least Frequently Used)といった一般的なキャッシュポリシは、特定のトラフィックパターンの下でのみ最適なパフォーマンスを示す。 過去の要求データのパターンを検出する高度な機械学習ベースの方法でさえ、将来の要求が過去のトレンドから逸脱した場合に苦労する。 近年,交通パターンの変化に頑健な新しいポリシーが出現している。 これらのアルゴリズムは、コンテキストへの継続的な適応を可能にするオンライン最適化問題に対処する。 それらは、オンラインポリシーと後ろ向きの最適な静的キャッシュ割り当ての間のパフォーマンスギャップを測定する、後悔の度合いに関する理論的保証を提供する。 しかし、これらの解の計算複雑性が高いことは、その実践的採用を妨げる。 本研究では,カタログサイズに対する対数計算の複雑さを突破し,かつ,後悔の保証を提供する,勾配に基づくオンラインキャッシュポリシーの新たなバリエーションを提案する。 この進歩により、何百万ものリクエストやアイテムをフィーチャーした大規模で現実世界のトレース上でポリシーをテストすることが可能になります。 我々の知る限り、我々の実験結果は、勾配に基づくキャッシュポリシーの後悔の保証が、現実的なシナリオでかなりの利益をもたらすことを初めて証明した。

関連論文リスト

• Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
  我々はC-PGと呼ばれる探索非依存のアルゴリズムを導入し、このアルゴリズムは(弱)勾配支配仮定の下でのグローバルな最終点収束を保証する。 制約付き制御問題に対して,我々のアルゴリズムを数値的に検証し,それらを最先端のベースラインと比較する。
  論文  参考訳（メタデータ） (2024-07-15T14:54:57Z)
• Online Policy Learning and Inference by Matrix Completion [12.527541242185404]
  行列完備帯域(MCB)として問題を定式化する。 我々は、$epsilon$-greedy banditとオンライン勾配降下について検討する。 より早く崩壊する探索は、より少ない後悔をもたらすが、最適なポリシーをより正確に学習する。
  論文  参考訳（メタデータ） (2024-04-26T13:19:27Z)
• Iteratively Refined Behavior Regularization for Offline Reinforcement Learning [57.10922880400715]
  本稿では,保守的政策反復に基づく行動規則化を大幅に強化する新しいアルゴリズムを提案する。 行動規則化に使用される基準ポリシーを反復的に洗練することにより、保守的な政策更新は徐々に改善される。 D4RLベンチマークの実験結果から,本手法は従来のタスクのベースラインよりも優れていたことが示唆された。
  論文  参考訳（メタデータ） (2023-06-09T07:46:24Z)
• Efficient Online Reinforcement Learning with Offline Data [78.92501185886569]
  オンライン学習時にオフラインデータを活用するために、既存のオフライン手法を単純に適用できることを示します。 私たちはこれらの設計選択を広範囲に改善し、パフォーマンスに最も影響を与える重要な要因を示します。 これらのシンプルなレコメンデーションの正しい適用によって、既存のアプローチよりも$mathbf2.5times$の改善が得られます。
  論文  参考訳（メタデータ） (2023-02-06T17:30:22Z)
• Optimistic No-regret Algorithms for Discrete Caching [6.182368229968862]
  楽観的な学習の文脈において,ファイル全体を限られた容量でキャッシュに格納するという問題を体系的に検討する。 予測支援オンラインキャッシュのための普遍的な下位境界を提供し、様々なパフォーマンス・複雑さのトレードオフを持つ一連のポリシーを設計する。 我々の結果は、最近提案されたすべてのオンラインキャッシュポリシーを大幅に改善し、オラクルの予測を活用できないため、後悔する$O(sqrtT)しか提供できません。
  論文  参考訳（メタデータ） (2022-08-15T09:18:41Z)
• Universal Caching [8.208569626646034]
  オンラインキャッシュ問題の文脈において,後悔の最小化というより強い概念を考察する。 適応的なサブ線形後悔境界を持つ効率的なオンラインキャッシュポリシーを提案する。 私たちの知る限りでは、ユニバーサルキャッシング問題で知られている最初のデータ依存の後悔だ。
  論文  参考訳（メタデータ） (2022-05-10T13:00:10Z)
• Online Caching with no Regret: Optimistic Learning via Recommendations [15.877673959068458]
  ファイル要求の予測を含むFTRL(Follow-the-Regularized-Leader)フレームワークを構築した。 フレームワークを拡張して、多くが利用可能な場合に最適な要求予測器を学習し、利用します。 提案した楽観的な学習キャッシュポリシが,完全予測のためのサブゼロ性能損失(regret)を達成できることを実証する。
  論文  参考訳（メタデータ） (2022-04-20T09:29:47Z)
• MUSBO: Model-based Uncertainty Regularized and Sample Efficient Batch Optimization for Deployment Constrained Reinforcement Learning [108.79676336281211]
  データ収集とオンライン学習のための新しいポリシーの継続的展開はコスト非効率か非現実的かのどちらかである。 モデルベース不確実性正規化とサンプル効率的なバッチ最適化という新しいアルゴリズム学習フレームワークを提案する。 本フレームワークは,各デプロイメントの新規で高品質なサンプルを発見し,効率的なデータ収集を実現する。
  論文  参考訳（メタデータ） (2021-02-23T01:30:55Z)
• Non-stationary Online Learning with Memory and Non-stochastic Control [71.14503310914799]
  我々は,過去の決定に依拠する損失関数を許容するメモリを用いたオンライン凸最適化(OCO)の問題について検討する。 本稿では,非定常環境に対してロバストなアルゴリズムを設計するための性能指標として,動的ポリシーの後悔を紹介する。 我々は,時間的地平線,非定常度,メモリ長といった面で,最適な動的ポリシーの後悔を確実に享受するメモリ付きOCOの新しいアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-02-07T09:45:15Z)
• Optimizing for the Future in Non-Stationary MDPs [52.373873622008944]
  本稿では,今後の性能予測を最大化するポリシ勾配アルゴリズムを提案する。 我々のアルゴリズムであるPrognosticatorは2つのオンライン適応手法よりも非定常性に頑健であることを示す。
  論文  参考訳（メタデータ） (2020-05-17T03:41:19Z)

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

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