論文の概要: LeadCache: Regret-Optimal Caching in Networks
- arxiv url: http://arxiv.org/abs/2009.08228v4
- Date: Tue, 26 Oct 2021 13:59:48 GMT
- ステータス: 処理完了
- システム内更新日: 2022-10-17 12:22:40.688587
- Title: LeadCache: Regret-Optimal Caching in Networks
- Title（参考訳）: LeadCache: ネットワークにおけるレグレット最適キャッシュ
- Authors: Debjit Paria, Abhishek Sinha
- Abstract要約: 本稿では、Follow-the-Perturbed-Leaderパラダイムに基づく効率的なオンラインキャッシュポリシーを提案する。
我々は、$textttLeadCache$が、ユーザの数である$tildeO(n3/8)まで、後悔の最適であることを示す。
- 参考スコア（独自算出の注目度）: 8.208569626646034
- License: http://creativecommons.org/licenses/by-nc-sa/4.0/
- Abstract: We consider an online prediction problem in the context of network caching.
Assume that multiple users are connected to several caches via a bipartite
network. At any time slot, each user may request an arbitrary file chosen from
a large catalog. A user's request at a slot is met if the requested file is
cached in at least one of the caches connected to the user. Our objective is to
predict, prefetch, and optimally distribute the files on the caches at each
slot to maximize the total number of cache hits. The problem is non-trivial due
to the non-convex and non-smooth nature of the objective function. In this
paper, we propose $\texttt{LeadCache}$ - an efficient online caching policy
based on the Follow-the-Perturbed-Leader paradigm. We show that
$\texttt{LeadCache}$ is regret-optimal up to a factor of $\tilde{O}(n^{3/8}),$
where $n$ is the number of users. We design two efficient implementations of
the $\texttt{LeadCache}$ policy, one based on Pipage rounding and the other
based on Madow's sampling, each of which makes precisely one call to an
LP-solver per iteration. Furthermore, with a Strong-Law-type assumption, we
show that the total number of file fetches under $\texttt{LeadCache}$ remains
almost surely finite over an infinite horizon. Finally, we derive an
approximately tight regret lower bound using results from graph coloring. We
conclude that the learning-based $\texttt{LeadCache}$ policy decisively
outperforms the state-of-the-art caching policies both theoretically and
empirically.
- Abstract（参考訳）: ネットワークキャッシングにおけるオンライン予測問題について考察する。
複数のユーザがバイパーティイトネットワークを介して複数のキャッシュに接続されていると仮定する。
いつでも、各ユーザーは大きなカタログから選択した任意のファイルを要求することができる。
要求されたファイルがユーザに接続された少なくとも1つのキャッシュにキャッシュされた場合、スロットでのユーザの要求が満たされる。
我々の目標は、各スロットのキャッシュ上のファイルを予測し、プリフェッチし、最適に配布し、キャッシュヒットの総数を最大化することである。
問題は、対象関数の非凸性と非滑らか性のため、非自明である。
本稿では、Follow-the-Perturbed-Leaderパラダイムに基づく効率的なオンラインキャッシュポリシーである$\texttt{LeadCache}$を提案する。
我々は、$\texttt{leadcache}$ は$\tilde{o}(n^{3/8}) の係数まで後悔に最適であることを示し、ここで $n$ はユーザ数である。
我々は、$\texttt{leadcache}$ ポリシーの効率的な実装を2つ設計し、1つは pipage rounding に基づいており、もう1つは madow のサンプリングに基づいている。
さらに、Strong-Law型仮定では、$\texttt{LeadCache}$のファイルフェッチの総数は、無限の地平線上でほぼ確実に有限であることを示す。
最後に,グラフカラー化の結果を用いて,ほぼ後悔の少ない下界を導出する。
学習ベースの$\texttt{LeadCache}$ポリシーは、理論的にも経験的にも、最先端のキャッシュポリシーを決定的に上回っていると結論づける。
関連論文リスト
- InstCache: A Predictive Cache for LLM Serving [9.878166964839512]
本稿では,命令整合 LLM によるユーザインストラクションの予測と,それを予測キャッシュ,いわゆる InstCache に格納することを提案する。
実験の結果、InstCacheはLMSysデータセット上で最大51.34%のヒット率を達成でき、メモリコストは4.5GBに過ぎなかった。
論文 参考訳（メタデータ） (2024-11-21T03:52:41Z) - Efficient Inference of Vision Instruction-Following Models with Elastic Cache [76.44955111634545]
我々は,命令追従型大規模視覚言語モデルの効率的なデプロイのための新しい戦略であるElastic Cacheを紹介する。
本稿では,冗長キャッシュを具現化する重要なキャッシュマージ戦略を提案する。
命令符号化では,キャッシュの重要性を評価するために周波数を利用する。
様々なLVLMの結果は、Elastic Cacheが効率を向上するだけでなく、言語生成における既存のプルーニングメソッドよりも優れていることを示している。
論文 参考訳（メタデータ） (2024-07-25T15:29:05Z) - MeanCache: User-Centric Semantic Cache for Large Language Model Based Web Services [8.350378532274405]
キャッシングは、繰り返しクエリの推論コストを削減するための自然なソリューションである。
本稿では,LLMベースのサービスのためのユーザ中心セマンティックキャッシュであるMeanCacheを紹介する。
MeanCacheは、セマンティックに類似したクエリを特定して、キャッシュヒットやミスを判定する。
論文 参考訳（メタデータ） (2024-03-05T06:23:50Z) - 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) - On Optimal Caching and Model Multiplexing for Large Model Inference [66.50550915522551]
大きな言語モデル(LLM)や他の大きな基盤モデルは注目すべき成功を収めているが、そのサイズは既存のリソース消費とレイテンシーの問題を悪化させている。
キャッシュを用いて以前のクエリを格納し、モデルの多重化を学習し、クエリ処理のためのモデルの集合から選択する。
論文 参考訳（メタデータ） (2023-06-03T05:01:51Z) - 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) - Quantum Differentially Private Sparse Regression Learning [132.1981461292324]
我々は、スパース回帰問題を解くために、効率的な量子微分プライベート(QDP)ラッソ推定器を考案する。
最後に、QDP Lasso はプライバシー保証付きで $tildeO(N-2/3)$ に近い最適ユーティリティを実現していることを示す。
論文 参考訳（メタデータ） (2020-07-23T10:50:42Z) - Reinforcement Learning for Caching with Space-Time Popularity Dynamics [61.55827760294755]
キャッシングは次世代ネットワークにおいて重要な役割を果たすと想定されている。
コンテンツをインテリジェントにプリフェッチし、保存するためには、キャッシュノードは、何といつキャッシュするかを学ばなければならない。
本章では、近似キャッシングポリシー設計のための多目的強化学習に基づくアプローチを提案する。
論文 参考訳（メタデータ） (2020-05-19T01:23:51Z) - PA-Cache: Evolving Learning-Based Popularity-Aware Content Caching in
Edge Networks [14.939950326112045]
本稿では,エッジネットワークにおけるPAキャッシュという,学習ベースのコンテンツキャッシュポリシを提案する。
時間変化のあるコンテンツの人気を適応的に学習し、キャッシュが満杯になったときにどのコンテンツを置き換えるべきかを決定する。
提案するPAキャッシュの性能を,大規模オンラインビデオオンデマンドサービスプロバイダによる実世界のトレースで広範囲に評価した。
論文 参考訳（メタデータ） (2020-02-20T15:38:01Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。