論文の概要: Universal Caching
- arxiv url: http://arxiv.org/abs/2205.04860v1
- Date: Tue, 10 May 2022 13:00:10 GMT
- ステータス: 処理完了
- システム内更新日: 2022-05-12 21:35:39.203204
- Title: Universal Caching
- Title（参考訳）: ユニバーサルキャッシング
- Authors: Ativ Joshi and Abhishek Sinha
- Abstract要約: オンラインキャッシュ問題の文脈において,後悔の最小化というより強い概念を考察する。
適応的なサブ線形後悔境界を持つ効率的なオンラインキャッシュポリシーを提案する。
私たちの知る限りでは、ユニバーサルキャッシング問題で知られている最初のデータ依存の後悔だ。
- 参考スコア（独自算出の注目度）: 8.208569626646034
- License: http://creativecommons.org/licenses/by-nc-nd/4.0/
- Abstract: In the learning literature, the performance of an online policy is commonly
measured in terms of the static regret metric, which compares the cumulative
loss of an online policy to that of an optimal benchmark in hindsight. In the
definition of static regret, the benchmark policy remains fixed throughout the
time horizon. Naturally, the resulting regret bounds become loose in
non-stationary settings where fixed benchmarks often suffer from poor
performance. In this paper, we investigate a stronger notion of regret
minimization in the context of an online caching problem. In particular, we
allow the action of the offline benchmark at any round to be decided by a
finite state predictor containing arbitrarily many states. Using ideas from the
universal prediction literature in information theory, we propose an efficient
online caching policy with an adaptive sub-linear regret bound. To the best of
our knowledge, this is the first data-dependent regret bound known for the
universal caching problem. We establish this result by combining a
recently-proposed online caching policy with an incremental parsing algorithm,
e.g., Lempel-Ziv '78. Our methods also yield a simpler learning-theoretic proof
of the improved regret bound as opposed to the more involved and
problem-specific combinatorial arguments used in the earlier works.
- Abstract（参考訳）: 学習文献では、オンラインポリシーのパフォーマンスは一般的に、オンラインポリシーの累積損失と後から見て最適なベンチマークとを比較する静的後悔の指標を用いて測定される。
静的後悔の定義では、ベンチマークポリシーは時間軸を通じて固定されている。
当然、修正されたベンチマークがパフォーマンスの低下に苦しむ非定常な設定では、結果として生じる後悔の限界は緩やかになる。
本稿では,オンラインキャッシュ問題における後悔の最小化という概念について検討する。
特に、任意のラウンドにおけるオフラインベンチマークの動作は、任意に多数の状態を含む有限状態予測器によって決定される。
情報理論における普遍予測文献のアイデアを用いて,適応型サブリニア・リットバウンドを持つ効率的なオンラインキャッシングポリシーを提案する。
私たちの知る限りでは、ユニバーサルキャッシング問題で知られている最初のデータ依存の後悔だ。
本稿では,最近提案されているオンラインキャッシングポリシとインクリメンタル解析アルゴリズム,例えばlempel-ziv '78を組み合わせることにより,この結果を確立する。
また,本手法は,先行研究で用いたより複雑で問題固有の組合せ論とは対照的に,改良された後悔境界の学習理論的な証明も提供する。
関連論文リスト
- An Online Gradient-Based Caching Policy with Logarithmic Complexity and Regret Guarantees [13.844896723580858]
我々は、対数計算の複雑さを突破するグラデーションベースのオンラインキャッシュポリシーを新たに導入する。
この進歩により、何百万ものリクエストやアイテムを伴って、大規模で現実世界のトレース上でポリシーをテストすることができます。
論文 参考訳（メタデータ） (2024-05-02T13:11:53Z) - Improving Adaptive Online Learning Using Refined Discretization [44.646191058243645]
リプシッツ損失を伴う制約のないオンライン線形最適化について検討する。
インスタンス最適性の追求に動機づけられ,我々は新しいアルゴリズムを提案する。
これらの結果の中心は、オンライン学習に対する継続的な時間的アプローチである。
論文 参考訳（メタデータ） (2023-09-27T21:54:52Z) - Iteratively Refined Behavior Regularization for Offline Reinforcement
Learning [57.10922880400715]
本稿では,保守的政策反復に基づく行動規則化を大幅に強化する新しいアルゴリズムを提案する。
行動規則化に使用される基準ポリシーを反復的に洗練することにより、保守的な政策更新は徐々に改善される。
D4RLベンチマークの実験結果から,本手法は従来のタスクのベースラインよりも優れていたことが示唆された。
論文 参考訳（メタデータ） (2023-06-09T07:46:24Z) - Improved Online Conformal Prediction via Strongly Adaptive Online
Learning [86.4346936885507]
我々は、強い適応的後悔を最小限に抑える新しいオンライン共形予測手法を開発した。
提案手法は,すべての区間において,ほぼ最適に適応的な後悔を同時に達成できることを実証する。
実験により,本手法は実世界のタスクにおける既存の手法よりも,より優れたカバレッジと予測セットが得られることがわかった。
論文 参考訳（メタデータ） (2023-02-15T18:59:30Z) - Optimistic No-regret Algorithms for Discrete Caching [6.182368229968862]
楽観的な学習の文脈において,ファイル全体を限られた容量でキャッシュに格納するという問題を体系的に検討する。
予測支援オンラインキャッシュのための普遍的な下位境界を提供し、様々なパフォーマンス・複雑さのトレードオフを持つ一連のポリシーを設計する。
我々の結果は、最近提案されたすべてのオンラインキャッシュポリシーを大幅に改善し、オラクルの予測を活用できないため、後悔する$O(sqrtT)しか提供できません。
論文 参考訳（メタデータ） (2022-08-15T09:18:41Z) - Online Caching with no Regret: Optimistic Learning via Recommendations [15.877673959068458]
ファイル要求の予測を含むFTRL(Follow-the-Regularized-Leader)フレームワークを構築した。
フレームワークを拡張して、多くが利用可能な場合に最適な要求予測器を学習し、利用します。
提案した楽観的な学習キャッシュポリシが,完全予測のためのサブゼロ性能損失(regret)を達成できることを実証する。
論文 参考訳（メタデータ） (2022-04-20T09:29:47Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for Online Convex Optimization [70.4342220499858]
本稿では,スムーズさを生かし,問題依存量による動的後悔のT$への依存を補う新しいオンラインアルゴリズムを提案する。
この結果が本質的な難易度に適応しているのは, 既往の結果よりも厳密であり, 最悪の場合, 同一レートの保護が可能であるからである。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Non-stationary Online Learning with Memory and Non-stochastic Control [71.14503310914799]
我々は,過去の決定に依拠する損失関数を許容するメモリを用いたオンライン凸最適化(OCO)の問題について検討する。
本稿では,非定常環境に対してロバストなアルゴリズムを設計するための性能指標として,動的ポリシーの後悔を紹介する。
我々は,時間的地平線,非定常度,メモリ長といった面で,最適な動的ポリシーの後悔を確実に享受するメモリ付きOCOの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-07T09:45:15Z) - Strongly Adaptive OCO with Memory [49.319621885036035]
本稿では,メモリを用いたオンライン学習のための適応型アルゴリズムを提案する。
このアルゴリズムは,線形時間変化システムの制御に強い適応性を持つリセットバウンドをもたらす。
論文 参考訳（メタデータ） (2021-02-02T17:26:08Z) - Temporal Variability in Implicit Online Learning [15.974402990630402]
最強の後悔分析は、オンラインミラー・ダイスンよりも限界的な改善しか示さない。
損失関数列の時間的変動に依存する新しい静的な後悔境界を証明した。
本稿では、時間的変動の事前知識を必要とせずに、この後悔を抑える適応アルゴリズムを提案する。
論文 参考訳（メタデータ） (2020-06-12T22:50:34Z) - Minimizing Dynamic Regret and Adaptive Regret Simultaneously [60.17824125301273]
動的後悔と適応的後悔を同時に最小化できる新しいオンラインアルゴリズムを提案する。
我々の理論的保証は、あるアルゴリズムが任意の間隔で動的後悔を最小化できるという意味でさらに強い。
論文 参考訳（メタデータ） (2020-02-06T03:32:37Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。