論文の概要: Online Caching with Optimal Switching Regret

• arxiv url: http://arxiv.org/abs/2101.07043v1
• Date: Mon, 18 Jan 2021 12:47:22 GMT
• ステータス: 処理完了
• システム内更新日: 2021-03-27 05:47:04.424254
• Title: Online Caching with Optimal Switching Regret
• Title（参考訳）: 最適スイッチングレグレットによるオンラインキャッシング
• Authors: Samrat Mukhopadhyay, Abhishek Sinha
• Abstract要約: 限られたストレージ容量のキャッシュは、大きなカタログから一度に$c$ファイルを保持することができる。 キャッシュヒットの場合、ポリシーは単位報酬を受け取り、それ以外は報酬を受け取らない。 目的は、キャッシュヒットによる報酬とファイルフェッチによる切り替えコストの両方を考慮して、最小限の後悔を招くキャッシュポリシーを設計することである。
• 参考スコア（独自算出の注目度）: 10.447270433913134
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the classical uncoded caching problem from an online learning point-of-view. A cache of limited storage capacity can hold $C$ files at a time from a large catalog. A user requests an arbitrary file from the catalog at each time slot. Before the file request from the user arrives, a caching policy populates the cache with any $C$ files of its choice. In the case of a cache-hit, the policy receives a unit reward and zero rewards otherwise. In addition to that, there is a cost associated with fetching files to the cache, which we refer to as the switching cost. The objective is to design a caching policy that incurs minimal regret while considering both the rewards due to cache-hits and the switching cost due to the file fetches. The main contribution of this paper is the switching regret analysis of a Follow the Perturbed Leader-based anytime caching policy, which is shown to have an order optimal switching regret. In this pursuit, we improve the best-known switching regret bound for this problem by a factor of $\Theta(\sqrt{C}).$ We conclude the paper by comparing the performance of different popular caching policies using a publicly available trace from a commercial CDN server.
• Abstract（参考訳）: オンライン学習の観点から、古典的なアンコードキャッシュ問題を考察する。 限られたストレージ容量のキャッシュは、大きなカタログから一度に$c$ファイルを保持することができる。 ユーザは、各タイムスロットでカタログから任意のファイルをリクエストする。 ユーザからのファイル要求が到着する前に、キャッシュポリシーは、その選択した$c$ファイルでキャッシュをポピュレートする。 キャッシュヒットの場合、ポリシーは単位報酬を受け取り、それ以外は報酬を受け取らない。 それに加えて、キャッシュへのファイルのフェッチに関連するコストがあります。 目的は、キャッシュヒットによる報酬とファイルフェッチによる切り替えコストの両方を考慮して、最小限の後悔を招くキャッシュポリシーを設計することである。 この論文の主な貢献は、リーダーベースの永続キャッシングポリシーに従う場合の切替後悔分析であり、これは順番に最適な切替後悔を有することを示している。 そこで本研究では,商用cdnサーバから入手可能なトレースを用いて,さまざまなキャッシュポリシのパフォーマンスを比較することにより,この問題に対する最もよく知られたスイッチング後悔を,$\theta(\sqrt{c})という係数で改善する。

関連論文リスト

• On the Regret of Coded Caching with Adversarial Requests [7.171698704686835]
  オンライン学習フレームワークにおいて、よく知られた符号化キャッシュ問題について検討し、リクエストが順次到着する。 本稿では、Follow-The-Perturbed-Leader原則に基づくキャッシュポリシーを導入し、任意の時間水平線Tにおいて、算術的O(sqrt(T))に対するサブ線形後悔を実現することを示す。
  論文  参考訳（メタデータ） (2024-09-19T01:13:03Z)
• Efficient Inference of Vision Instruction-Following Models with Elastic Cache [76.44955111634545]
  我々は,命令追従型大規模視覚言語モデルの効率的なデプロイのための新しい戦略であるElastic Cacheを紹介する。 本稿では,冗長キャッシュを具現化する重要なキャッシュマージ戦略を提案する。 命令符号化では,キャッシュの重要性を評価するために周波数を利用する。 様々なLVLMの結果は、Elastic Cacheが効率を向上するだけでなく、言語生成における既存のプルーニングメソッドよりも優れていることを示している。
  論文  参考訳（メタデータ） (2024-07-25T15:29:05Z)
• Training-Free Exponential Context Extension via Cascading KV Cache [49.608367376911694]
  カスケードサブキャッシュバッファを利用して,最も関連性の高いトークンを選択的に保持する機構を導入する。 本手法は,1Mトークンのフラッシュアテンションと比較して,プリフィルステージ遅延を6.8倍削減する。
  論文  参考訳（メタデータ） (2024-06-24T03:59:17Z)
• Get More with LESS: Synthesizing Recurrence with KV Cache Compression for Efficient LLM Inference [78.65321721142624]
  我々はキー値(KV)キャッシュによって課されるメモリボトルネックに焦点を当てる。 既存のKVキャッシュ手法は、比較的重要でないKVペアの大きなスワストを刈り取ったり、取り除いたりすることでこの問題に対処する。 本稿では,固定サイズキャッシュと退避型キャッシュを簡易に統合したLESSを提案する。
  論文  参考訳（メタデータ） (2024-02-14T18:54:56Z)
• A Learning-Based Caching Mechanism for Edge Content Delivery [2.412158290827225]
  5GネットワークとIoT(Internet of Things)の台頭により、ネットワークのエッジはますます拡大している。 このシフトは、特に限られたキャッシュストレージとエッジにおける多様な要求パターンのために、ユニークな課題をもたらす。 HR-Cacheは、ハザードレート(HR)順序付けの原則に基づく学習ベースのキャッシュフレームワークである。
  論文  参考訳（メタデータ） (2024-02-05T08:06:03Z)
• Optimistic No-regret Algorithms for Discrete Caching [6.182368229968862]
  楽観的な学習の文脈において,ファイル全体を限られた容量でキャッシュに格納するという問題を体系的に検討する。 予測支援オンラインキャッシュのための普遍的な下位境界を提供し、様々なパフォーマンス・複雑さのトレードオフを持つ一連のポリシーを設計する。 我々の結果は、最近提案されたすべてのオンラインキャッシュポリシーを大幅に改善し、オラクルの予測を活用できないため、後悔する$O(sqrtT)しか提供できません。
  論文  参考訳（メタデータ） (2022-08-15T09:18:41Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  我々は、近似キーキャッシングと名付けた新しいキャッシングパラダイムを提案する。 近似キャッシュはDL推論の負荷を軽減し、システムのスループットを向上するが、近似誤差を導入する。 我々は古典的なLRUと理想的なキャッシュのキャッシュシステム性能を解析的にモデル化し、期待される性能のトレース駆動評価を行い、提案手法の利点を最先端の類似キャッシュと比較した。
  論文  参考訳（メタデータ） (2021-12-13T13:49:11Z)
• LeadCache: Regret-Optimal Caching in Networks [8.208569626646034]
  本稿では、Follow-the-Perturbed-Leaderパラダイムに基づく効率的なオンラインキャッシュポリシーを提案する。 我々は、$textttLeadCache$が、ユーザの数である$tildeO(n3/8)まで、後悔の最適であることを示す。
  論文  参考訳（メタデータ） (2020-09-17T12:13:26Z)
• Reinforcement Learning for Caching with Space-Time Popularity Dynamics [61.55827760294755]
  キャッシングは次世代ネットワークにおいて重要な役割を果たすと想定されている。 コンテンツをインテリジェントにプリフェッチし、保存するためには、キャッシュノードは、何といつキャッシュするかを学ばなければならない。 本章では、近似キャッシングポリシー設計のための多目的強化学習に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-19T01:23:51Z)
• A Non-Stationary Bandit-Learning Approach to Energy-Efficient Femto-Caching with Rateless-Coded Transmission [98.47527781626161]
  小セルネットワークにおける共同キャッシュと送信のためのリソース割り当て問題について検討する。 次に、各放送ラウンドの送信電力レベルとともに、キャッシュからファイルを選択するという問題を定式化する。 最先端の研究とは対照的に、提案手法は時変統計特性を持つネットワークに特に適している。
  論文  参考訳（メタデータ） (2020-04-13T09:07:17Z)

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

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