論文の概要: An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees
- arxiv url: http://arxiv.org/abs/2405.01263v1
- Date: Thu, 2 May 2024 13:11:53 GMT
- ステータス: 処理完了
- システム内更新日: 2024-05-03 16:34:40.901716
- 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: The commonly used caching policies, such as LRU or LFU, exhibit optimal performance only for 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 makes no assumptions about the request arrival process. These algorithms solve an online optimization problem, enabling continuous adaptation to the context. They offer theoretical guarantees on the regret metric, which is the gap between the gain of the online policy and the gain of the optimal static cache allocation in hindsight. Nevertheless, the high computational complexity of these solutions hinders their practical adoption. In this study, we introduce a groundbreaking gradient-based online caching policy, the first to achieve logarithmic computational complexity relative to catalog size along with regret guarantees. This means our algorithm can efficiently handle large-scale data while minimizing the performance gap between real-time decisions and optimal hindsight choices. As requests arrive, our policy dynamically adjusts the probabilities of including items in the cache, which drive cache update decisions. Our algorithm's streamlined complexity is a key advantage, enabling its application to real-world traces featuring millions of requests and items. This is a significant achievement, as traces of this scale have been out of reach for existing policies with regret guarantees. To the best of our knowledge, our experimental results show for the first time that the regret guarantees of gradient-based caching policies bring significant benefits in scenarios of practical interest.
- Abstract（参考訳）: LRUやLFUなどの一般的なキャッシュポリシは、特定のトラフィックパターンに対してのみ最適なパフォーマンスを示す。
過去の要求データのパターンを検出する高度な機械学習ベースの方法でさえ、将来の要求が過去のトレンドから逸脱した場合に苦労する。
最近、リクエストの到着プロセスについて仮定しない新しいポリシーのクラスが出現しました。
これらのアルゴリズムは、コンテキストへの継続的な適応を可能にするオンライン最適化問題を解決する。
これは、オンラインポリシーの利得と、後見で最適な静的キャッシュ割り当ての利得のギャップである。
それでも、これらの解の計算複雑性が高いことは、その実践的採用を妨げる。
本研究では,カタログサイズに対して対数計算の複雑さを初めて達成し,後悔の保証を伴って,画期的な勾配に基づくオンラインキャッシュポリシーを導入する。
これは,実時間決定と最適後見選択の間の性能差を最小化しながら,大規模データを効率的に処理できることを意味している。
リクエストが到着すると、ポリシーはキャッシュにアイテムを含める確率を動的に調整し、キャッシュの更新決定を駆動します。
我々のアルゴリズムの合理化された複雑さは重要な利点であり、数百万のリクエストとアイテムを特徴とする実世界のトレースを可能にする。
この規模の痕跡は、後悔の保証のある既存の政策には届かなかったため、これは大きな成果である。
我々の知る限り、我々の実験結果は、勾配に基づくキャッシュポリシーの後悔の保証が、実践的な関心のシナリオに多大な利益をもたらすことを初めて示している。
関連論文リスト
- Edge Caching Optimization with PPO and Transfer Learning for Dynamic Environments [3.720975664058743]
動的環境においては、コンテンツの人気の変化や要求率の変化が頻繁に発生し、事前学習されたポリシーが以前の条件に最適化されているため、効果が低下する。
我々は,コンテンツの人気と要求率の変化を検知し,キャッシュ戦略のタイムリーな調整を確保する機構を開発する。
また,事前知識を活用して,新しい環境における収束を加速する伝達学習に基づくPPOアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-14T21:01:29Z) - Last-Iterate Global Convergence of Policy Gradients for Constrained Reinforcement Learning [62.81324245896717]
我々はC-PGと呼ばれる探索非依存のアルゴリズムを導入し、このアルゴリズムは(弱)勾配支配仮定の下でのグローバルな最終点収束を保証する。
制約付き制御問題に対して,我々のアルゴリズムを数値的に検証し,それらを最先端のベースラインと比較する。
論文 参考訳（メタデータ） (2024-07-15T14:54:57Z) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。