論文の概要: Cache Replacement as a MAB with Delayed Feedback and Decaying Costs

• arxiv url: http://arxiv.org/abs/2009.11330v4
• Date: Wed, 19 May 2021 04:32:39 GMT
• ステータス: 処理完了
• システム内更新日: 2022-10-15 15:35:07.357608
• Title: Cache Replacement as a MAB with Delayed Feedback and Decaying Costs
• Title（参考訳）: 遅延フィードバックと減衰コストを伴うmabとしてのキャッシュ置換
• Authors: Farzana Beente Yusuf, Vitalii Stebliankin, Giuseppe Vietri, Giri Narasimhan
• Abstract要約: 我々は、よく知られたマルチアームバンディット(MAB)の新しい変種を提案し、解決する。 各アームは異なるキャッシュ置換ポリシーを表しており、必要に応じてキャッシュから削除するようページ上でアドバイスする。 適応型強化学習アルゴリズムEXP4-DFDCを導入する。
• 参考スコア（独自算出の注目度）: 4.358626952482686
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Inspired by the cache replacement problem, we propose and solve a new variant of the well-known multi-armed bandit (MAB), thus providing a solution for improving existing state-of-the-art cache management methods. Each arm (or expert) represents a distinct cache replacement policy, which advises on the page to evict from the cache when needed. Feedback on the eviction comes in the form of a "miss", but at an indeterminate time after the action is taken, and the cost of the eviction is set to be inversely proportional to the response time. The feedback is ignored if it comes after a threshold value for the delay, which we set to be equal to the size of the page eviction history. Thus, for delays beyond the threshold, its cost is assumed to be zero. Consequently, we call this problem with delayed feedback and decaying costs. We introduce an adaptive reinforcement learning algorithm EXP4-DFDC that provides a solution to the problem. We derive an optimal learning rate for EXP4-DFDC that defines the balance between exploration and exploitation and proves theoretically that the expected regret of our algorithm is a vanishing quantity as a function of time. As an application, we show that LeCaR, a recent top-performing machine learning algorithm for cache replacement, can be enhanced with adaptive learning using our formulations. We present an improved adaptive version of LeCaR, called OLeCaR, with the learning rate set as determined by the theoretical derivation presented here to minimize regret for EXP4-DFDC. It then follows that LeCaR and OLeCaR are theoretically guaranteed to have vanishing regret over time.
• Abstract（参考訳）: キャッシュ置換問題に触発されて,よく知られたマルチアーム付きバンディット (mab) の新しい変種を提案,解決し,既存のキャッシュ管理手法を改善するためのソリューションを提供する。 各arm(またはエキスパート)は、異なるキャッシュ置換ポリシーを示し、必要に応じてページ上でキャッシュから退避するようにアドバイスする。 退行に対するフィードバックは「ミス」という形で来るが、アクションが取られた後に不確定なタイミングで行われ、退行のコストは応答時間に逆比例するように設定される。 フィードバックが遅延のしきい値の後にくると無視されるので、ページの省略履歴のサイズに等しいと仮定する。 したがって、しきい値を超える遅延の場合、そのコストはゼロと仮定される。 その結果,フィードバックの遅れやコストの低下が問題となっている。 本稿では,この問題に対する解決策を提供する適応強化学習アルゴリズムexp4-dfdcを提案する。 探索と利用のバランスを定義したEXP4-DFDCの最適学習率を導出し,提案アルゴリズムの期待された後悔は時間の関数としての消滅量であることを理論的に証明する。 アプリケーションとして,最近のキャッシュ置換のためのトップパフォーマンス機械学習アルゴリズムであるlecarが,提案手法を用いた適応学習により拡張可能であることを示す。 本稿では,EXP4-DFDCの後悔を最小限に抑えるため,理論的導出によって決定される学習率を,OLeCaRと呼ばれる改良された適応型LeCaRを提案する。 その後、LeCaRとOLeCaRは理論上、時間の経過とともに後悔が消えることが保証されている。

関連論文リスト

• RPAF: A Reinforcement Prediction-Allocation Framework for Cache Allocation in Large-Scale Recommender Systems [22.87458184871264]
  本稿では,キャッシュアロケーションにおける2つの重要な課題,すなわち,バリューストラテジー依存とストリーミングアロケーションを示す。 これらの問題に対処するための強化予測割当フレームワーク(RPAF)を提案する。 RPAFは、予測とアロケーション段階を含む強化学習ベースの2段階フレームワークである。
  論文  参考訳（メタデータ） (2024-09-20T03:02:42Z)
• Ada-KV: Optimizing KV Cache Eviction by Adaptive Budget Allocation for Efficient LLM Inference [19.447729423696096]
  大規模言語モデルは様々な分野で優れているが、メモリと時間効率の課題に直面している。 最近の取り組みでは、KVキャッシュのサイズを所定のメモリ予算に減らし、実行中に巨大な非クリティカルキャッシュ要素を排除しようとしている。
  論文  参考訳（メタデータ） (2024-07-16T09:53:32Z)
• Cache-Aware Reinforcement Learning in Large-Scale Recommender Systems [10.52021139266752]
  キャッシュ対応強化学習(CARL)は、リアルタイム計算とキャッシュによる推薦を協調的に最適化する手法である。 CARLは、結果キャッシュを考慮すると、ユーザのエンゲージメントを大幅に改善できる。 CARLはKwaiアプリで完全にローンチされ、1億人以上のユーザーにサービスを提供している。
  論文  参考訳（メタデータ） (2024-04-23T12:06:40Z)
• Improved Regret for Efficient Online Reinforcement Learning with Linear Function Approximation [69.0695698566235]
  線形関数近似による強化学習と,コスト関数の逆変化について検討した。 本稿では,未知のダイナミクスと帯域幅フィードバックの一般設定に挑戦する,計算効率のよいポリシ最適化アルゴリズムを提案する。
  論文  参考訳（メタデータ） (2023-01-30T17:26:39Z)
• Online Nonsubmodular Minimization with Delayed Costs: From Full Information to Bandit Feedback [98.7678704343537]
  我々は,オンラインおよび近似的オンライン帯域勾配勾配アルゴリズムのいくつかの変種に対する後悔の保証を,特別な構造を持つ非部分モジュラ関数のクラスに焦点をあてる。 我々は,決定の選択と帰属費用の受け取りの遅れが無拘束である場合でも,エージェントの完全な情報と盗賊のフィードバック設定に対する後悔の限界を導出する。
  論文  参考訳（メタデータ） (2022-05-15T08:27:12Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  我々は、近似キーキャッシングと名付けた新しいキャッシングパラダイムを提案する。 近似キャッシュはDL推論の負荷を軽減し、システムのスループットを向上するが、近似誤差を導入する。 我々は古典的なLRUと理想的なキャッシュのキャッシュシステム性能を解析的にモデル化し、期待される性能のトレース駆動評価を行い、提案手法の利点を最先端の類似キャッシュと比較した。
  論文  参考訳（メタデータ） (2021-12-13T13:49:11Z)
• ARCH: Efficient Adversarial Regularized Training with Caching [91.74682538906691]
  逆正則化は、多くの自然言語処理タスクにおけるモデル一般化を改善することができる。 本稿では,複数のエポック毎に摂動を発生・キャッシュする新たな逆正則化手法ARCHを提案する。 提案手法をニューラルネットワーク翻訳と自然言語理解タスクのセットで評価する。
  論文  参考訳（メタデータ） (2021-09-15T02:05:37Z)
• Confidence-Budget Matching for Sequential Budgeted Learning [69.77435313099366]
  問合せ予算で意思決定問題を定式化する。 我々は,多腕バンディット,線形バンディット,強化学習問題を考察する。 我々は,CBMに基づくアルゴリズムが逆性の存在下で良好に動作することを示す。
  論文  参考訳（メタデータ） (2021-02-05T19:56:31Z)
• Online Markov Decision Processes with Aggregate Bandit Feedback [74.85532145498742]
  本稿では,オンライン有限水平マルコフ決定過程の新たな変種について検討する。 各エピソードにおいて、学習者は、エピソードの選択した方針によって実現された軌道に沿って蓄積された損失を被り、総括的盗聴フィードバックを観察する。 我々の主な結果は計算効率のよいアルゴリズムで、$O(sqrtK)$ regret for this set, where $K$ is the number of episodes。
  論文  参考訳（メタデータ） (2021-01-31T16:49:07Z)
• No-Regret Caching via Online Mirror Descent [0.0]
  本稿では、リモートサーバからの検索コストを回避するため、ローカルキャッシュでリクエストを配信できるオンラインキャッシュ問題について検討する。 我々は, 後悔の限界は, 多様性比R/hで提供される要求プロセスの多様性に大きく依存していることを示す。 また,キャッシュがファイル全体を格納しなければならない場合,一部ではなく,無作為な保証を保ったランダムなラウンドリングスキームと OMD 戦略が結合可能であることも証明した。
  論文  参考訳（メタデータ） (2021-01-29T13:56:51Z)

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

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