論文の概要: Optimistic No-regret Algorithms for Discrete Caching

• arxiv url: http://arxiv.org/abs/2208.06414v1
• Date: Mon, 15 Aug 2022 09:18:41 GMT
• ステータス: 処理完了
• システム内更新日: 2022-08-16 15:01:18.229371
• Title: Optimistic No-regret Algorithms for Discrete Caching
• Title（参考訳）: 離散キャッシングのための最適非線形アルゴリズム
• Authors: Naram Mhaisen, Abhishek Sinha, Georgios Paschos, Georgios Iosifidis
• Abstract要約: 楽観的な学習の文脈において,ファイル全体を限られた容量でキャッシュに格納するという問題を体系的に検討する。 予測支援オンラインキャッシュのための普遍的な下位境界を提供し、様々なパフォーマンス・複雑さのトレードオフを持つ一連のポリシーを設計する。 我々の結果は、最近提案されたすべてのオンラインキャッシュポリシーを大幅に改善し、オラクルの予測を活用できないため、後悔する$O(sqrtT)しか提供できません。
• 参考スコア（独自算出の注目度）: 6.182368229968862
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: We take a systematic look at the problem of storing whole files in a cache with limited capacity in the context of optimistic learning, where the caching policy has access to a prediction oracle (provided by, e.g., a Neural Network). The successive file requests are assumed to be generated by an adversary, and no assumption is made on the accuracy of the oracle. In this setting, we provide a universal lower bound for prediction-assisted online caching and proceed to design a suite of policies with a range of performance-complexity trade-offs. All proposed policies offer sublinear regret bounds commensurate with the accuracy of the oracle. Our results substantially improve upon all recently-proposed online caching policies, which, being unable to exploit the oracle predictions, offer only $O(\sqrt{T})$ regret. In this pursuit, we design, to the best of our knowledge, the first comprehensive optimistic Follow-the-Perturbed leader policy, which generalizes beyond the caching problem. We also study the problem of caching files with different sizes and the bipartite network caching problem. Finally, we evaluate the efficacy of the proposed policies through extensive numerical experiments using real-world traces.
• Abstract（参考訳）: 楽観的な学習の文脈では、キャッシュポリシが予測オラクル(ニューラルネットワークなどによって提供される)にアクセス可能な場合において、キャッシュに全ファイルを限られた容量で保存するという問題を体系的に検討する。 連続したファイル要求は、敵によって生成されると仮定され、オラクルの正確さについて仮定されることはない。 この設定では、予測支援オンラインキャッシングのための普遍的な下限を提供し、様々なパフォーマンス・複雑さのトレードオフを備えた一連のポリシーの設計を進めます。 提案されたすべてのポリシーは、神託の正確さに相応しいサブ線形後悔境界を提供する。 我々の結果は、最近提案された全てのオンラインキャッシュポリシーを大幅に改善し、オラクルの予測を活用できないため、後悔する$O(\sqrt{T})しか提供できません。 この追求において、私たちは、私たちの知る限り、キャッシュ問題を超えて一般化する最初の包括的な楽観的フォローザパーチャベッドリーダーポリシーを設計します。 また,サイズの異なるファイルのキャッシュの問題や,ネットワークキャッシュの問題についても検討する。 最後に,提案手法の有効性を実世界トレースを用いた広範な数値実験により評価した。

関連論文リスト

• 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)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• A Universal Error Measure for Input Predictions Applied to Online Graph Problems [57.58926849872494]
  本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。 この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
  論文  参考訳（メタデータ） (2022-05-25T15:24:03Z)
• Online Caching with no Regret: Optimistic Learning via Recommendations [15.877673959068458]
  ファイル要求の予測を含むFTRL(Follow-the-Regularized-Leader)フレームワークを構築した。 フレームワークを拡張して、多くが利用可能な場合に最適な要求予測器を学習し、利用します。 提案した楽観的な学習キャッシュポリシが,完全予測のためのサブゼロ性能損失(regret)を達成できることを実証する。
  論文  参考訳（メタデータ） (2022-04-20T09:29:47Z)
• Online Caching with Optimistic Learning [15.877673959068458]
  本稿では,楽観的なオンライン学習のレンズを用いて,この問題に対処するための新しいアルゴリズムツールボックスを提案する。 我々は、時間平均予算制約の下で、固定サイズのキャッシュや弾性的なリースキャッシュを備えた二部ネットワークのためのオンラインキャッシュアルゴリズムを設計する。 提案した楽観的な学習キャッシュポリシは,完全予測に対してゼロ以下の性能損失(regret)を達成でき,任意のバッド予測に対してさえ,最も達成可能なリフレッシュバウンドである$O(sqrt T)を維持できることを示す。
  論文  参考訳（メタデータ） (2022-02-22T00:04:30Z)
• Accelerating Deep Learning Classification with Error-controlled Approximate-key Caching [72.50506500576746]
  我々は、近似キーキャッシングと名付けた新しいキャッシングパラダイムを提案する。 近似キャッシュはDL推論の負荷を軽減し、システムのスループットを向上するが、近似誤差を導入する。 我々は古典的なLRUと理想的なキャッシュのキャッシュシステム性能を解析的にモデル化し、期待される性能のトレース駆動評価を行い、提案手法の利点を最先端の類似キャッシュと比較した。
  論文  参考訳（メタデータ） (2021-12-13T13:49:11Z)
• Learning from Images: Proactive Caching with Parallel Convolutional Neural Networks [94.85780721466816]
  本稿では,プロアクティブキャッシングのための新しいフレームワークを提案する。 モデルベースの最適化とデータ駆動技術を組み合わせて、最適化問題をグレースケールのイメージに変換する。 数値計算の結果,提案手法は71.6%の計算時間を0.8%のコストで削減できることがわかった。
  論文  参考訳（メタデータ） (2021-08-15T21:32:47Z)
• Cocktail Edge Caching: Ride Dynamic Trends of Content Popularity with Ensemble Learning [10.930268276150262]
  エッジキャッシングは、新興のコンテンツ豊富なアプリケーションを促進する上で重要な役割を果たす。 それは、特に、非常にダイナミックなコンテンツ人気と異種キャッシュ計算など、多くの新しい課題に直面しています。 アンサンブル学習による動的人気と不均一性に対処するCocktail Edge Cachingを提案する。
  論文  参考訳（メタデータ） (2021-01-14T21:59:04Z)
• Reinforcement Learning for Caching with Space-Time Popularity Dynamics [61.55827760294755]
  キャッシングは次世代ネットワークにおいて重要な役割を果たすと想定されている。 コンテンツをインテリジェントにプリフェッチし、保存するためには、キャッシュノードは、何といつキャッシュするかを学ばなければならない。 本章では、近似キャッシングポリシー設計のための多目的強化学習に基づくアプローチを提案する。
  論文  参考訳（メタデータ） (2020-05-19T01:23:51Z)
• Non-Cooperative Game Theory Based Rate Adaptation for Dynamic Video Streaming over HTTP [89.30855958779425]
  Dynamic Adaptive Streaming over HTTP (DASH)は、新興かつ有望なマルチメディアストリーミング技術であることを示した。 本稿では,サーバの限られた輸出帯域幅をマルチユーザに対して最適に割り当てるアルゴリズムを提案し,その品質・オブ・エクスペリエンス(QoE)を公平性で最大化する。
  論文  参考訳（メタデータ） (2019-12-27T01:19:14Z)

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

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