論文の概要: Online Caching with no Regret: Optimistic Learning via Recommendations

• arxiv url: http://arxiv.org/abs/2204.09345v1
• Date: Wed, 20 Apr 2022 09:29:47 GMT
• ステータス: 処理完了
• システム内更新日: 2022-04-21 19:38:40.121294
• Title: Online Caching with no Regret: Optimistic Learning via Recommendations
• Title（参考訳）: レジストのないオンラインキャッシング - 推奨による最適学習
• Authors: Naram Mhaisen and George Iosifidis and Douglas Leith
• Abstract要約: ファイル要求の予測を含むFTRL(Follow-the-Regularized-Leader)フレームワークを構築した。 フレームワークを拡張して、多くが利用可能な場合に最適な要求予測器を学習し、利用します。 提案した楽観的な学習キャッシュポリシが,完全予測のためのサブゼロ性能損失(regret)を達成できることを実証する。
• 参考スコア（独自算出の注目度）: 15.877673959068458
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: The design of effective online caching policies is an increasingly important problem for content distribution networks, online social networks and edge computing services, among other areas. This paper proposes a new algorithmic toolbox for tackling this problem through the lens of optimistic online learning. We build upon the Follow-the-Regularized-Leader (FTRL) framework, which is developed further here to include predictions for the file requests, and we design online caching algorithms for bipartite networks with fixed-size caches or elastic leased caches subject to time-average budget constraints. The predictions are provided by a content recommendation system that influences the users viewing activity and hence can naturally reduce the caching network's uncertainty about future requests. We also extend the framework to learn and utilize the best request predictor in cases where many are available. We prove that the proposed {optimistic} learning caching policies can achieve sub-zero performance loss (regret) for perfect predictions, and maintain the sub-linear regret bound $O(\sqrt T)$, which is the best achievable bound for policies that do not use predictions, even for arbitrary-bad predictions. The performance of the proposed algorithms is evaluated with detailed trace-driven numerical tests.
• Abstract（参考訳）: 効果的なオンラインキャッシュポリシーの設計は、コンテンツ配信ネットワーク、オンラインソーシャルネットワーク、エッジコンピューティングサービスなどにおいて、ますます重要な問題となっている。 本稿では,楽観的なオンライン学習のレンズを通してこの問題に取り組むための新しいアルゴリズムツールボックスを提案する。 我々は、ファイル要求の予測を含むFollow-the-Regularized-Leader (FTRL) フレームワークを構築し、時間平均予算制約を考慮した固定サイズキャッシュや弾性リースキャッシュを備えた二部ネットワークのためのオンラインキャッシュアルゴリズムを設計する。 この予測は、ユーザの視聴行動に影響を与えるコンテンツレコメンデーションシステムによって提供され、将来の要求に対するキャッシングネットワークの不確実性が自然に低減される。 また、多くの人が利用できる場合に最適な要求予測器を学習し利用するためにフレームワークを拡張します。 提案した「最適」学習キャッシュポリシは、完全な予測に対してゼロ以下の性能損失(regret)を達成でき、任意のバッド予測であっても予測を使用しないポリシーに対して最も達成可能なサブ線形後悔境界である$O(\sqrt T)$を維持することができる。 提案アルゴリズムの性能は,詳細なトレース駆動数値テストを用いて評価する。

関連論文リスト

• An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees [13.844896723580858]
  我々は、対数計算の複雑さを突破するグラデーションベースのオンラインキャッシュポリシーを新たに導入する。 この進歩により、何百万ものリクエストやアイテムを伴って、大規模で現実世界のトレース上でポリシーをテストすることができます。
  論文  参考訳（メタデータ） (2024-05-02T13:11:53Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Online Network Source Optimization with Graph-Kernel MAB [62.6067511147939]
  大規模ネットワークにおける最適なソース配置をオンラインで学習するためのグラフカーネルマルチアームバンディットアルゴリズムであるGrab-UCBを提案する。 適応グラフ辞書モデルを用いて,ネットワークプロセスを記述する。 我々は、ネットワークパラメータに依存する性能保証を導出し、シーケンシャルな意思決定戦略の学習曲線にさらに影響を及ぼす。
  論文  参考訳（メタデータ） (2023-07-07T15:03:42Z)
• Optimistic No-regret Algorithms for Discrete Caching [6.182368229968862]
  楽観的な学習の文脈において,ファイル全体を限られた容量でキャッシュに格納するという問題を体系的に検討する。 予測支援オンラインキャッシュのための普遍的な下位境界を提供し、様々なパフォーマンス・複雑さのトレードオフを持つ一連のポリシーを設計する。 我々の結果は、最近提案されたすべてのオンラインキャッシュポリシーを大幅に改善し、オラクルの予測を活用できないため、後悔する$O(sqrtT)しか提供できません。
  論文  参考訳（メタデータ） (2022-08-15T09:18:41Z)
• Provably Efficient Reinforcement Learning for Online Adaptive Influence Maximization [53.11458949694947]
  本稿では,リアルタイムフィードバックに基づいてシードノードを逐次活性化する,コンテンツ依存型オンライン影響問題の適応バージョンについて検討する。 提案アルゴリズムは,最適政策を楽観的に改善しつつ,ネットワークモデルの推定を保守し,適応的にシードを選択する。
  論文  参考訳（メタデータ） (2022-06-29T18:17:28Z)
• 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)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)
• A Survey of Deep Learning for Data Caching in Edge Network [1.9798034349981157]
  本稿では,エッジネットワークにおけるデータキャッシングにおけるディープラーニングの利用について要約する。 まず、コンテンツキャッシングにおける典型的な研究トピックを概説し、ネットワーク階層構造に基づく分類を定式化する。 次に、教師なし学習から教師なし学習、強化学習まで、多くの重要なディープラーニングアルゴリズムが提示される。
  論文  参考訳（メタデータ） (2020-08-17T12:02:32Z)

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

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