論文の概要: No-Regret Mixing of LRU and LFU with Optimal Switching Cost

• arxiv url: http://arxiv.org/abs/2609.07566v1
• Date: Mon, 07 Sep 2026 14:44:51 GMT
• ステータス: 翻訳完了
• システム内更新日: 2026-09-10 19:44:08.446816
• Title: No-Regret Mixing of LRU and LFU with Optimal Switching Cost
• Title（参考訳）: 最適切換コストを考慮したLRUとLFUの非反応性混合
• Abstract要約: キャッシングシステムは、LRU(Last recent Used)やLast Frequently Used(LFU)のような単純な消去ポリシーに依存していることが多い。 我々はLeCarが歴史的にさえも、不愉快な敵に対して線形後悔を経験していることを示します。 次に,Hedge を用いた仮想 LRU と LFU を混合した H-MC を提案する。
• 参考スコア（独自算出の注目度）: 2.363388546004777
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Caching systems often rely on simple eviction policies such as Least Recently Used (LRU) and Least Frequently Used (LFU), which perform well in complementary request regimes. Recent policies such as LeCar and Cacheus combine LRU and LFU using ideas from the experts problem in online learning. Specifically, upon a miss, they randomize between the two eviction rules using probabilities derived from scores updated by tracking the history of past evictions. While these policies exhibit strong empirical performance, it remains unclear whether they are guaranteed, on every request sequence, to perform asymptotically as well as the better of LRU and LFU, i.e., whether they achieve sublinear regret with respect to this benchmark. We first show that LeCar suffers linear regret against an oblivious adversary, even with unbounded history. We then propose H-MC, a Hedge-based mixture of virtual LRU and LFU caches that preserves Hedge's selection probabilities, and hence its regret guarantees, while minimizing the switching cost among all joint selection rules with these marginals.
• Abstract（参考訳）: キャッシングシステムは、しばしばLRU(Last recently Used)やLFU(Last Frequently Used)といった、補完的な要求システムでよく機能する単純な排除ポリシーに依存している。 LeCarやCacheusといった最近のポリシーは、オンライン学習のエキスパート問題のアイデアを使ってLRUとLFUを組み合わせている。 特に、過ちを犯すと、過去の逸脱履歴を追跡することで更新されたスコアから得られる確率を用いて、2つの逸脱規則をランダム化する。 これらのポリシーは、強い経験的性能を示すが、どの要求シーケンスでも、漸近的に、LRUやLFUよりも優れていることを保証されているかどうか、すなわち、このベンチマークに関してサブ線形後悔を達成しているかどうかは不明である。 私たちはまず、LeCarが、歴史が無関係であっても、不利な敵に対して線形後悔を経験していることを示します。 次に,Hedge を用いた仮想 LRU と LFU キャッシュを混合した H-MC を提案する。

関連論文リスト

• Continuous Semantic Caching for Low-Cost LLM Serving [29.887977985331972]
  セマンティックに類似したクエリを持つユーザが再利用できるように、レスポンスのキャッシュは、推論コストとレイテンシを低減する上で重要な戦略となっている。 既存のキャッシュフレームワークでは、離散的なクエリの有限な宇宙を仮定して、キャッシュに対するクエリ応答を決定する方法が提案されている。 我々は,連続的なクエリ空間におけるLLM応答キャッシングを不確実性の下で意味付けるための,最初の厳密な理論的枠組みを確立する。
  論文  参考訳（メタデータ） (2026-04-21T21:56:43Z)
• Decision from Suboptimal Classifiers: Excess Risk Pre- and Post-Calibration [52.70324949884702]
  バッチ二分決定における近似的後続確率を用いた余剰リスクの定量化を行う。 我々は、再校正のみが後悔のほとんどに対処する体制と、後悔が集団的損失に支配される体制を識別する。 NLP実験では、これらの量によって、より高度なポストトレーニングの期待値が運用コストに値するかどうかが分かる。
  論文  参考訳（メタデータ） (2025-03-23T10:52:36Z)
• Utilize the Flow before Stepping into the Same River Twice: Certainty Represented Knowledge Flow for Refusal-Aware Instruction Tuning [68.57166425493283]
  Refusal-Aware Instruction Tuning (RAIT) により、Large Language Models (LLM) は未知の質問に答えることを拒否できる。 この粗末なアプローチは、LLMが正しく答えられる可能性のある質問に答えることを過剰に拒否する可能性がある。 本稿では,CRaFT(Certainty Represented Knowledge Flow for Refusal-Aware Instructions Tuning)を提案する。
  論文  参考訳（メタデータ） (2024-10-09T14:12:51Z)
• LLM4DSR: Leveraging Large Language Model for Denoising Sequential Recommendation [27.255048063428077]
  シーケンスレコメンダは、ユーザの過去のインタラクションシーケンスに基づいてレコメンデーションを生成する。 これらの配列は、しばしばノイズ相互作用によって汚染され、レコメンデーション性能を著しく損なう。 広い言語モデル (LLM) には広い知識と意味論的推論能力が備わっており、この情報ギャップを埋めるための有望な道筋を提供する。 LLMを用いてシーケンシャルなレコメンデーションを識別するLLM4DSRを提案する。
  論文  参考訳（メタデータ） (2024-08-15T15:18:46Z)
• Data-Dependent Bounds for Online Portfolio Selection Without Lipschitzness and Smoothness [2.315156126698557]
  我々は,非Lipschitz,非滑らかな損失を伴って,オンライン凸最適化のためのデータ依存境界の最初の例を紹介する。 最悪事例におけるサブ線形後悔率を示すアルゴリズムを提案するとともに、データが「容易」である場合の対数的後悔を実現する。
  論文  参考訳（メタデータ） (2023-05-23T11:16:01Z)
• Benign Overfitting in Linear Classifiers and Leaky ReLU Networks from KKT Conditions for Margin Maximization [59.038366742773164]
  ロジスティック損失の勾配流によって訓練された線形および漏洩ReLUは、KKT条件を満たすための暗黙の偏りを持つ。 本研究では、線形分類器や2層リークReLUネットワークにおいて、これらの条件の満足度が良性オーバーフィットを意味するような設定を多数確立する。
  論文  参考訳（メタデータ） (2023-03-02T18:24:26Z)
• Offline Minimax Soft-Q-learning Under Realizability and Partial Coverage [100.8180383245813]
  オフライン強化学習(RL)のための値ベースアルゴリズムを提案する。 ソフトマージン条件下でのバニラQ関数の類似した結果を示す。 我々のアルゴリズムの損失関数は、推定問題を非線形凸最適化問題とラグランジフィケーションとしてキャストすることによって生じる。
  論文  参考訳（メタデータ） (2023-02-05T14:22:41Z)
• Generative Slate Recommendation with Reinforcement Learning [49.75985313698214]
  強化学習アルゴリズムは、レコメンデータシステムのユーザエンゲージメントを最適化するために使用することができる。 しかし、RLアプローチはスレートレコメンデーションシナリオでは難解である。 この設定では、アクションはアイテムの組み合わせを含むことができるスレートに対応する。 本研究では,変分オートエンコーダによって学習された連続低次元ラテント空間におけるスレートの符号化を提案する。 我々は、(i)以前の作業で要求される仮定を緩和し、(ii)完全なスレートをモデル化することで、アクション選択の品質を向上させることができる。
  論文  参考訳（メタデータ） (2023-01-20T15:28:09Z)
• On the Effectiveness of Lipschitz-Driven Rehearsal in Continual Learning [17.179898279925155]
  データの小さなプールに対する繰り返し最適化は、必然的に厳密で不安定な決定境界につながる。 リプシッツ・ドリヴエン・リハーサル(Lidschitz-DrivEn Rehearsal, LiDER)を提案する。 大規模な実験により,LiDERの適用はいくつかの最先端のリハーサルCL手法に安定した性能向上をもたらすことが示された。
  論文  参考訳（メタデータ） (2022-10-12T17:45:13Z)
• Continuous Doubly Constrained Batch Reinforcement Learning [93.23842221189658]
  環境とのオンラインインタラクションではなく、固定されたオフラインデータセットのみを使用して効果的なポリシーを学ぶバッチRLのアルゴリズムを提案する。 バッチRLにおける制限されたデータは、トレーニングデータに不十分に表現された状態/動作の値推定に固有の不確実性をもたらす。 この分散を減らすための政策制約と、過度に楽観的な見積もりを妨げる価値制約という2つの簡単な罰則によってこの問題を軽減することを提案する。
  論文  参考訳（メタデータ） (2021-02-18T08:54:14Z)
• Fast OSCAR and OWL Regression via Safe Screening Rules [97.28167655721766]
  順序付き$L_1$ (OWL)正規化回帰は、高次元スパース学習のための新しい回帰分析である。 近勾配法はOWL回帰を解くための標準手法として用いられる。 未知の順序構造を持つ原始解の順序を探索することにより、OWL回帰の最初の安全なスクリーニングルールを提案する。
  論文  参考訳（メタデータ） (2020-06-29T23:35:53Z)

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

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