論文の概要: On the Regret of Coded Caching with Adversarial Requests

• arxiv url: http://arxiv.org/abs/2409.12387v1
• Date: Thu, 19 Sep 2024 01:13:03 GMT
• ステータス: 処理完了
• システム内更新日: 2024-11-07 15:14:47.090643
• Title: On the Regret of Coded Caching with Adversarial Requests
• Title（参考訳）: 逆数要求による符号化キャッシングのレジストレーションについて
• Authors: Anupam Nayak, Kota Srinivas Reddy, Nikhil Karamchandani,
• Abstract要約: オンライン学習フレームワークにおいて、よく知られた符号化キャッシュ問題について検討し、リクエストが順次到着する。 本稿では、Follow-The-Perturbed-Leader原則に基づくキャッシュポリシーを導入し、任意の時間水平線Tにおいて、算術的O(sqrt(T))に対するサブ線形後悔を実現することを示す。
• 参考スコア（独自算出の注目度）: 7.171698704686835
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We study the well-known coded caching problem in an online learning framework, wherein requests arrive sequentially, and an online policy can update the cache contents based on the history of requests seen thus far. We introduce a caching policy based on the Follow-The-Perturbed-Leader principle and show that for any time horizon T and any request sequence, it achieves a sub-linear regret of \mathcal{O}(\sqrt(T) ) with respect to an oracle that knows the request sequence beforehand. Our study marks the first examination of adversarial regret in the coded caching setup. Furthermore, we also address the issue of switching cost by establishing an upper bound on the expected number of cache updates made by our algorithm under unrestricted switching and also provide an upper bound on the regret under restricted switching when cache updates can only happen in a pre-specified subset of timeslots. Finally, we validate our theoretical insights with numerical results using a real-world dataset
• Abstract（参考訳）: オンライン学習フレームワークでは,要求が順次届き,これまでの要求履歴に基づいて,オンラインポリシによってキャッシュ内容を更新することが可能である。 本稿では、Follow-The-Perturbed-Leaderの原則に基づくキャッシュポリシーを導入し、任意の時間水平線Tおよび任意のリクエストシーケンスに対して、事前に要求シーケンスを知っている託宣について \mathcal{O}(\sqrt(T))のサブ線形後悔を達成することを示す。 本研究は,符号化キャッシングセットアップにおける敵意的後悔の初診である。 さらに,制限のない切換条件下でのアルゴリズムのキャッシュ更新数に対する上限の設定や,予め指定されたタイムスロットのサブセットでしかキャッシュ更新ができない場合にのみ,制限された切換条件下での後悔量に対する上限の設定により,スイッチングコストの問題にも対処する。 最後に,実世界のデータセットを用いた数値計算による理論的知見の検証を行った。

関連論文リスト

• 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)
• No-Regret Caching with Noisy Request Estimates [12.603423174002254]
  要求推定値がノイズである場合,従来のFPLの変種であるNoisy-Follow-the-Perturbed-Leader (NFPL)アルゴリズムを提案する。 提案手法は,要求推定器の特定の条件下でのサブ線形後悔を有することを示す。
  論文  参考訳（メタデータ） (2023-09-05T08:57:35Z)
• Mitigating Catastrophic Forgetting in Task-Incremental Continual Learning with Adaptive Classification Criterion [50.03041373044267]
  本稿では,継続的学習のための適応型分類基準を用いた教師付きコントラスト学習フレームワークを提案する。 実験により, CFLは最先端の性能を達成し, 分類基準に比べて克服する能力が強いことが示された。
  論文  参考訳（メタデータ） (2023-05-20T19:22:40Z)
• 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)
• Online Caching with Optimal Switching Regret [10.447270433913134]
  限られたストレージ容量のキャッシュは、大きなカタログから一度に$c$ファイルを保持することができる。 キャッシュヒットの場合、ポリシーは単位報酬を受け取り、それ以外は報酬を受け取らない。 目的は、キャッシュヒットによる報酬とファイルフェッチによる切り替えコストの両方を考慮して、最小限の後悔を招くキャッシュポリシーを設計することである。
  論文  参考訳（メタデータ） (2021-01-18T12:47:22Z)
• An Imitation Learning Approach for Cache Replacement [23.03767134871606]
  キャッシュアクセスパターンを自動的に学習するための模倣学習手法を提案する。 我々は過去のアクセスのみに条件付きポリシーを訓練し、多様な複雑なアクセスパターンでもベラディの情報を正確に近似する。 Parrotは、現在の最先端よりもキャッシュミス率を20%向上させる。
  論文  参考訳（メタデータ） (2020-06-29T17:58:40Z)
• Query Resolution for Conversational Search with Limited Supervision [63.131221660019776]
  本稿では,双方向トランスフォーマに基づくニューラルクエリ解決モデルQuReTeCを提案する。 我々はQuReTeCが最先端モデルより優れており、また、QuReTeCのトレーニングに必要な人為的なデータ量を大幅に削減するために、我々の遠隔監視手法が有効であることを示す。
  論文  参考訳（メタデータ） (2020-05-24T11:37:22Z)
• Reinforcement Learning for Caching with Space-Time Popularity Dynamics [61.55827760294755]
  キャッシングは次世代ネットワークにおいて重要な役割を果たすと想定されている。 コンテンツをインテリジェントにプリフェッチし、保存するためには、キャッシュノードは、何といつキャッシュするかを学ばなければならない。 本章では、近似キャッシングポリシー設計のための多目的強化学習に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-19T01:23:51Z)

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

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