論文の概要: Efficient and Optimal No-Regret Caching under Partial Observation

• arxiv url: http://arxiv.org/abs/2503.02758v1
• Date: Tue, 04 Mar 2025 16:21:33 GMT
• ステータス: 翻訳完了
• システム内更新日: 2025-03-05 19:13:58.375285
• Title: Efficient and Optimal No-Regret Caching under Partial Observation
• Title（参考訳）: 部分観察による効率・最適非回帰キャッシング
• Authors: Younes Ben Mazziane, Francescomaria Faticanti, Sara Alouf, Giovanni Neglia,
• Abstract要約: 我々は、過去の要求のごく一部しか観測されない、より制限的な環境でキャッシュ問題を調査する。 本稿では,従来のオンライン学習アルゴリズムであるFollow-the-Perturbed-Leaderに基づいて,サブ線形後悔を伴うランダム化キャッシュポリシーを提案する。
• 参考スコア（独自算出の注目度）: 11.537072761243344
• License:
• Abstract: Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios like caching at a cellular base station. Therefore, we study the caching problem in a more restrictive setting where only a fraction of past requests are observed, and we propose a randomized caching policy with sublinear regret based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL). Our caching policy is the first to attain the asymptotically optimal regret bound while ensuring asymptotically constant amortized time complexity in the partial observability setting of requests. The experimental evaluation compares the proposed solution against classic caching policies and validates the proposed approach under synthetic and real-world request traces.
• Abstract（参考訳）: オンライン学習アルゴリズムは、要求シーケンスに関する統計的仮定なしで、要求の総数においてサブリニアな後悔を伴うキャッシュポリシーの設計に成功している。 既存のアルゴリズムの多くは計算に高価な演算を伴い、過去の全ての要求の知識を必要とする。 しかし、これは携帯電話基地局でのキャッシュのような現実的なシナリオでは実現できないかもしれない。 そこで本稿では,従来のオンライン学習アルゴリズムであるFollow-the-Perturbed-Leader(FPL)に基づく,サブ線形後悔を伴うランダム化キャッシュポリシーを提案する。 私たちのキャッシングポリシは、リクエストの部分的可観測性設定において、漸近的に一定なアモータイズされた時間複雑性を確保しながら、漸近的に最適な後悔境界に達した最初のものです。 実験により,提案手法を古典的なキャッシュポリシーに対して比較し,提案手法を合成および実世界の要求トレース下で検証した。

関連論文リスト

• On the Regret of Coded Caching with Adversarial Requests [7.171698704686835]
  オンライン学習フレームワークにおいて、よく知られた符号化キャッシュ問題について検討し、リクエストが順次到着する。 本稿では、Follow-The-Perturbed-Leader原則に基づくキャッシュポリシーを導入し、任意の時間水平線Tにおいて、算術的O(sqrt(T))に対するサブ線形後悔を実現することを示す。
  論文  参考訳（メタデータ） (2024-09-19T01:13:03Z)
• An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees [13.844896723580858]
  我々は、対数計算の複雑さを突破するグラデーションベースのオンラインキャッシュポリシーを新たに導入する。 この進歩により、何百万ものリクエストやアイテムを伴って、大規模で現実世界のトレース上でポリシーをテストすることができます。
  論文  参考訳（メタデータ） (2024-05-02T13:11:53Z)
• No-Regret Caching with Noisy Request Estimates [12.603423174002254]
  要求推定値がノイズである場合,従来のFPLの変種であるNoisy-Follow-the-Perturbed-Leader (NFPL)アルゴリズムを提案する。 提案手法は,要求推定器の特定の条件下でのサブ線形後悔を有することを示す。
  論文  参考訳（メタデータ） (2023-09-05T08:57:35Z)
• Iteratively Refined Behavior Regularization for Offline Reinforcement Learning [57.10922880400715]
  本稿では,保守的政策反復に基づく行動規則化を大幅に強化する新しいアルゴリズムを提案する。 行動規則化に使用される基準ポリシーを反復的に洗練することにより、保守的な政策更新は徐々に改善される。 D4RLベンチマークの実験結果から,本手法は従来のタスクのベースラインよりも優れていたことが示唆された。
  論文  参考訳（メタデータ） (2023-06-09T07:46:24Z)
• Optimistic No-regret Algorithms for Discrete Caching [6.182368229968862]
  楽観的な学習の文脈において,ファイル全体を限られた容量でキャッシュに格納するという問題を体系的に検討する。 予測支援オンラインキャッシュのための普遍的な下位境界を提供し、様々なパフォーマンス・複雑さのトレードオフを持つ一連のポリシーを設計する。 我々の結果は、最近提案されたすべてのオンラインキャッシュポリシーを大幅に改善し、オラクルの予測を活用できないため、後悔する$O(sqrtT)しか提供できません。
  論文  参考訳（メタデータ） (2022-08-15T09:18:41Z)
• Fast Offline Policy Optimization for Large Scale Recommendation [74.78213147859236]
  我々は、カタログサイズと対数的にスケールするこれらのポリシー学習アルゴリズムの近似を導出する。 私たちの貢献は3つの新しいアイデアの組み合わせに基づいている。 我々の推定器は、単純なアプローチよりも桁違いに速いが、等しく良いポリシーを生成する。
  論文  参考訳（メタデータ） (2022-08-08T11:54:11Z)
• Universal Caching [8.208569626646034]
  オンラインキャッシュ問題の文脈において,後悔の最小化というより強い概念を考察する。 適応的なサブ線形後悔境界を持つ効率的なオンラインキャッシュポリシーを提案する。 私たちの知る限りでは、ユニバーサルキャッシング問題で知られている最初のデータ依存の後悔だ。
  論文  参考訳（メタデータ） (2022-05-10T13:00:10Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  我々は、近似キーキャッシングと名付けた新しいキャッシングパラダイムを提案する。 近似キャッシュはDL推論の負荷を軽減し、システムのスループットを向上するが、近似誤差を導入する。 我々は古典的なLRUと理想的なキャッシュのキャッシュシステム性能を解析的にモデル化し、期待される性能のトレース駆動評価を行い、提案手法の利点を最先端の類似キャッシュと比較した。
  論文  参考訳（メタデータ） (2021-12-13T13:49:11Z)
• Local policy search with Bayesian optimization [73.0364959221845]
  強化学習は、環境との相互作用によって最適な政策を見つけることを目的としている。 局所探索のための政策勾配は、しばしばランダムな摂動から得られる。 目的関数の確率モデルとその勾配を用いたアルゴリズムを開発する。
  論文  参考訳（メタデータ） (2021-06-22T16:07:02Z)
• Variance-Reduced Off-Policy Memory-Efficient Policy Search [61.23789485979057]
  政治政策の最適化は強化学習において難しい問題である。 オフポリシーアルゴリズムはメモリ効率が高く、オフポリシーサンプルから学ぶことができる。
  論文  参考訳（メタデータ） (2020-09-14T16:22:46Z)
• Optimizing for the Future in Non-Stationary MDPs [52.373873622008944]
  本稿では,今後の性能予測を最大化するポリシ勾配アルゴリズムを提案する。 我々のアルゴリズムであるPrognosticatorは2つのオンライン適応手法よりも非定常性に頑健であることを示す。
  論文  参考訳（メタデータ） (2020-05-17T03:41:19Z)

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

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