論文の概要: 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を組み合わせることにより,この結果を確立する。
また,本手法は,先行研究で用いたより複雑で問題固有の組合せ論とは対照的に,改良された後悔境界の学習理論的な証明も提供する。
関連論文リスト
- Online Caching with no Regret: Optimistic Learning via Recommendations [15.877673959068458]
ファイル要求の予測を含むFTRL(Follow-the-Regularized-Le ader)フレームワークを構築した。
フレームワークを拡張して、多くが利用可能な場合に最適な要求予測器を学習し、利用します。
提案した楽観的な学習キャッシュポリシが,完全予測のためのサブゼロ性能損失(regret)を達成できることを実証する。
論文 参考訳（メタデータ） (2022-04-20T09:29:47Z) - Online Caching with Optimistic Learning [15.877673959068458]
本稿では,楽観的なオンライン学習のレンズを用いて,この問題に対処するための新しいアルゴリズムツールボックスを提案する。
我々は、時間平均予算制約の下で、固定サイズのキャッシュや弾性的なリースキャッシュを備えた二部ネットワークのためのオンラインキャッシュアルゴリズムを設計する。
提案した楽観的な学習キャッシュポリシは,完全予測に対してゼロ以下の性能損失(regret)を達成でき,任意のバッド予測に対してさえ,最も達成可能なリフレッシュバウンドである$O(sqrt T)を維持できることを示す。
論文 参考訳（メタデータ） (2022-02-22T00:04:30Z) - Online Control of Unknown Time-Varying Dynamical Systems [48.75672260851758]
非確率制御モデルにおいて、未知のダイナミクスを持つ時間変化線形系のオンライン制御について検討する。
本研究では,反省行動 (SLS) や反省反応 (Youla) , 線形フィードバック政策 (線形フィードバックポリシー) といった一般的な政策のクラスに関して, 後悔すべき境界について検討する。
論文 参考訳（メタデータ） (2022-02-16T06:57:14Z) - Adaptivity and Non-stationarity: Problem-dependent Dynamic Regret for
Online Convex Optimization [93.14387921542709]
非定常環境におけるオンライン凸最適化について検討する。
エンファンダイナミックな後悔をパフォーマンス指標として選びます。
本研究では,スムーズさを生かし,動的後悔の中で$T$に依存する新しいオンラインアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-29T02:42:59Z) - Boosting for Online Convex Optimization [64.15578413206715]
多数の専門家とオンライン凸最適化の意思決定フレームワークを検討します。
弱学習アルゴリズムは、基本クラスの専門家に対するおよその後悔を保証するメカニズムとして定義します。
ベースクラスの凸船体に対するほぼ最適の後悔を保証する効率的なブースティングアルゴリズムを提供します。
論文 参考訳（メタデータ） (2021-02-18T12:30:49Z) - Optimization Issues in KL-Constrained Approximate Policy Iteration [48.24321346619156]
多くの強化学習アルゴリズムは、近似ポリシー反復(API)のバージョンと見なすことができる。
標準APIはしばしば動作が悪いが、KL-divergenceによる各ポリシー更新を以前のポリシーに正規化することで学習が安定化できることが示されている。
TRPO、MPO、VMPOなどの一般的な実用的なアルゴリズムは、連続ポリシーのKL分割に関する制約によって正規化を置き換える。
論文 参考訳（メタデータ） (2021-02-11T19:35:33Z) - Non-stationary Online Learning with Memory and Non-stochastic Control [101.89561292986801]
我々は,過去の決定に依拠する損失関数を許容するメモリを用いたオンライン凸最適化(OCO)の問題について検討する。
非定常環境に対してロバストなアルゴリズムを設計するための性能指標として,動的ポリシー後悔を導入する。
我々は,最適な動的ポリシーの後悔を確実に享受するメモリを持つOCOの新しいアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-02-07T09:45:15Z) - Strongly Adaptive OCO with Memory [49.319621885036035]
本稿では,メモリを用いたオンライン学習のための適応型アルゴリズムを提案する。
このアルゴリズムは,線形時間変化システムの制御に強い適応性を持つリセットバウンドをもたらす。
論文 参考訳（メタデータ） (2021-02-02T17:26:08Z) - Optimistic and Adaptive Lagrangian Hedging [11.698607733213226]
オンライン学習では、アルゴリズムは各ラウンドの敵によって選択される可能性のある損失のある環境と対戦する。
私たちは、後悔マッチングとヘッジを含むオンラインアルゴリズムのクラスであるLagrangian hedgingに楽観と適応的なステップを導入します。
論文 参考訳（メタデータ） (2021-01-23T23:32:40Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。