論文の概要: No-Regret Caching via Online Mirror Descent

• arxiv url: http://arxiv.org/abs/2101.12588v5
• Date: Tue, 6 Jun 2023 14:06:09 GMT
• ステータス: 処理完了
• システム内更新日: 2023-06-08 00:21:33.618814
• Title: No-Regret Caching via Online Mirror Descent
• Title（参考訳）: オンラインミラー降下によるノンリグレットキャッシング
• Authors: T. Si Salem, G. Neglia and S. Ioannidis
• Abstract要約: 本稿では、リモートサーバからの検索コストを回避するため、ローカルキャッシュでリクエストを配信できるオンラインキャッシュ問題について検討する。 我々は, 後悔の限界は, 多様性比R/hで提供される要求プロセスの多様性に大きく依存していることを示す。 また,キャッシュがファイル全体を格納しなければならない場合,一部ではなく,無作為な保証を保ったランダムなラウンドリングスキームと OMD 戦略が結合可能であることも証明した。
• 参考スコア（独自算出の注目度）: 0.0
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We study an online caching problem in which requests can be served by a local cache to avoid retrieval costs from a remote server. The cache can update its state after a batch of requests and store an arbitrarily small fraction of each file. We study no-regret algorithms based on Online Mirror Descent (OMD) strategies. We show that bounds for the regret crucially depend on the diversity of the request process, provided by the diversity ratio R/h, where R is the size of the batch, and h is the maximum multiplicity of a request in a given batch. We characterize the optimality of OMD caching policies w.r.t. regret under different diversity regimes. We also prove that, when the cache must store the entire file, rather than a fraction, OMD strategies can be coupled with a randomized rounding scheme that preserves regret guarantees, even when update costs cannot be neglected. We provide a formal characterization of the rounding problem through optimal transport theory, and moreover we propose a computationally efficient randomized rounding scheme.
• Abstract（参考訳）: 本研究では,リモートサーバからの検索コストを回避するために,ローカルキャッシュで要求を処理できるオンラインキャッシング問題について検討する。 キャッシュは、リクエストのバッチ後に状態を更新し、各ファイルの任意に小さな部分を保存することができる。 オンラインミラー・ディクシブ(OMD)戦略に基づくノンレグレットアルゴリズムについて検討する。 本稿では,r がバッチのサイズであり,h が与えられたバッチにおける要求の最大重複度であるダイバーシティ比 r/h によって与えられる要求プロセスの多様性に,後悔の限度が決定的に依存することを示す。 我々は多様性の異なる体制下でのOMDキャッシュポリシーの最適性を特徴付ける。 また,キャッシュがファイル全体を保存する必要がある場合,更新コストを無視できない場合でも,不注意な保証を保持するランダムなラウンドリングスキームに,OMD戦略が組み合わさることも証明した。 最適輸送理論による丸め問題の形式的特徴付けを行い,さらに計算効率の高いランダム化丸めスキームを提案する。

関連論文リスト

• 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)
• 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)
• No-Regret Caching with Noisy Request Estimates [12.603423174002254]
  要求推定値がノイズである場合,従来のFPLの変種であるNoisy-Follow-the-Perturbed-Leader (NFPL)アルゴリズムを提案する。 提案手法は,要求推定器の特定の条件下でのサブ線形後悔を有することを示す。
  論文  参考訳（メタデータ） (2023-09-05T08:57:35Z)
• Unrolled Compressed Blind-Deconvolution [77.88847247301682]
  sparse multi channel blind deconvolution (S-MBD) はレーダー/ソナー/超音波イメージングなどの多くの工学的応用で頻繁に発生する。 そこで本研究では,受信した全信号に対して,はるかに少ない測定値からブラインドリカバリを可能にする圧縮手法を提案する。
  論文  参考訳（メタデータ） (2022-09-28T15:16:58Z)
• 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)
• ARCH: Efficient Adversarial Regularized Training with Caching [91.74682538906691]
  逆正則化は、多くの自然言語処理タスクにおけるモデル一般化を改善することができる。 本稿では,複数のエポック毎に摂動を発生・キャッシュする新たな逆正則化手法ARCHを提案する。 提案手法をニューラルネットワーク翻訳と自然言語理解タスクのセットで評価する。
  論文  参考訳（メタデータ） (2021-09-15T02:05:37Z)
• Cache Replacement as a MAB with Delayed Feedback and Decaying Costs [4.358626952482686]
  我々は、よく知られたマルチアームバンディット(MAB)の新しい変種を提案し、解決する。 各アームは異なるキャッシュ置換ポリシーを表しており、必要に応じてキャッシュから削除するようページ上でアドバイスする。 適応型強化学習アルゴリズムEXP4-DFDCを導入する。
  論文  参考訳（メタデータ） (2020-09-23T18:26:48Z)
• A Non-Stationary Bandit-Learning Approach to Energy-Efficient Femto-Caching with Rateless-Coded Transmission [98.47527781626161]
  小セルネットワークにおける共同キャッシュと送信のためのリソース割り当て問題について検討する。 次に、各放送ラウンドの送信電力レベルとともに、キャッシュからファイルを選択するという問題を定式化する。 最先端の研究とは対照的に、提案手法は時変統計特性を持つネットワークに特に適している。
  論文  参考訳（メタデータ） (2020-04-13T09:07:17Z)

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

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