論文の概要: Online Paging with a Vanishing Regret
- arxiv url: http://arxiv.org/abs/2011.09439v2
- Date: Thu, 19 Nov 2020 02:18:08 GMT
- ステータス: 処理完了
- システム内更新日: 2022-09-24 05:13:30.502533
- Title: Online Paging with a Vanishing Regret
- Title（参考訳）: オンラインのパージングは、後悔をなくした
- Authors: Yuval Emek, Shay Kutten, Yangguang Shi
- Abstract要約: 本稿では,オンラインアルゴリズムが複数の予測器にアクセスでき,ページ到着時刻の予測列を生成するオンラインページング問題の変種について考察する。
予測器は時折予測誤差を発生させ、そのうちの少なくとも1つが予測誤差のサブ線形数を生成すると仮定する。
この仮定は、最適オフラインアルゴリズムに対する時間平均後悔が無限大になる傾向にあるランダム化オンラインアルゴリズムの設計に十分であることを示す。
- 参考スコア（独自算出の注目度）: 6.520803851931362
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: This paper considers a variant of the online paging problem, where the online
algorithm has access to multiple predictors, each producing a sequence of
predictions for the page arrival times. The predictors may have occasional
prediction errors and it is assumed that at least one of them makes a sublinear
number of prediction errors in total. Our main result states that this
assumption suffices for the design of a randomized online algorithm whose
time-average regret with respect to the optimal offline algorithm tends to zero
as the time tends to infinity. This holds (with different regret bounds) for
both the full information access model, where in each round, the online
algorithm gets the predictions of all predictors, and the bandit access model,
where in each round, the online algorithm queries a single predictor. While
online algorithms that exploit inaccurate predictions have been a topic of
growing interest in the last few years, to the best of our knowledge, this is
the first paper that studies this topic in the context of multiple predictors
for an online problem with unbounded request sequences. Moreover, to the best
of our knowledge, this is also the first paper that aims for (and achieves)
online algorithms with a vanishing regret for a classic online problem under
reasonable assumptions.
- Abstract（参考訳）: 本稿では,オンラインアルゴリズムが複数の予測器にアクセスでき,ページ到着時刻の予測列を生成するオンラインページング問題の変種について考察する。
予測器は時折予測誤差を発生させ、そのうちの少なくとも1つが予測誤差のサブ線形数を生成すると仮定する。
この仮定は、最適オフラインアルゴリズムに対する時間平均後悔が無限大になる傾向にあるランダム化オンラインアルゴリズムの設計に十分であることを示す。
これは、全情報アクセスモデル、各ラウンドにおいてオンラインアルゴリズムがすべての予測者の予測を受け取り、各ラウンドにおいてオンラインアルゴリズムが単一の予測子をクエリするバンディットアクセスモデルの両方に対して(異なる後悔の範囲で)保持される。
不正確な予測を利用するオンラインアルゴリズムは、ここ数年で関心が高まりつつあるが、私たちの知る限りでは、このトピックを、無制限な要求シーケンスを持つオンライン問題に対する複数の予測器の文脈で研究する最初の論文である。
さらに、私たちの知る限りでは、この論文は、合理的な仮定の下で古典的なオンライン問題に対する後悔をなくし、オンラインアルゴリズムを目標とする(そして達成する)最初の論文でもある。
関連論文リスト
- Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。
この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。
本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
論文 参考訳（メタデータ） (2024-03-12T08:40:21Z) - Paging with Succinct Predictions [25.959849403994202]
予測情報を最小限に抑えるという新たな視点から学習増強型ページングについて検討する。
学習強化アルゴリズムの3つの望ましい特性をすべて満たす2つの設定のアルゴリズムを開発する。
論文 参考訳（メタデータ） (2022-10-06T09:26:34Z) - Online TSP with Predictions [3.8411077568039866]
古典的オンライン旅行セールスマン問題(OLTSP)について検討する。
他の研究の予測モデルとは異なり、OLTSPの実際の要求はその到着時間と位置に関連しており、予測された要求と一致しないかもしれない。
我々の主な成果は、様々な予測モデルと設計アルゴリズムを研究し、異なる設定で最もよく知られた結果を改善することである。
論文 参考訳（メタデータ） (2022-06-30T15:35:53Z) - A Universal Error Measure for Input Predictions Applied to Online Graph
Problems [57.58926849872494]
本稿では,入力予測における誤差の定量化のための新しい尺度を提案する。
この尺度は、予測されていない要求と予測されていない実際の要求によるエラーをキャプチャする。
論文 参考訳（メタデータ） (2022-05-25T15:24:03Z) - Online Algorithms with Multiple Predictions [17.803569868141647]
本稿では,複数の機械学習予測を付加したオンラインアルゴリズムについて検討する。
我々のアルゴリズムは、オンラインアルゴリズムの古典的ポテンシャルに基づく分析に予測の利用を取り入れている。
論文 参考訳（メタデータ） (2022-05-08T17:33:01Z) - Memory Bounds for the Experts Problem [53.67419690563877]
専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。
目標は、予測を処理し、最小コストで予測を行うことです。
アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
論文 参考訳（メタデータ） (2022-04-21T01:22:18Z) - Non-Clairvoyant Scheduling with Predictions Revisited [77.86290991564829]
非論理的スケジューリングでは、優先度不明な処理条件でジョブをスケジューリングするためのオンライン戦略を見つけることが課題である。
我々はこのよく研究された問題を、アルゴリズム設計に(信頼できない)予測を統合する、最近人気の高い学習強化された設定で再検討する。
これらの予測には所望の特性があり, 高い性能保証を有するアルゴリズムと同様に, 自然な誤差測定が可能であることを示す。
論文 参考訳（メタデータ） (2022-02-21T13:18:11Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Learning-Augmented Algorithms for Online Steiner Tree [14.506230077020994]
本稿では,どの端末がオンラインにやってくるかを予測するアルゴリズムについて考察する。
予測は誤りであり、アルゴリズムのパフォーマンスは誤って予測された端末の数によってパラメータ化される。
新たなオンラインアルゴリズムは,適度に正確な予測でも高い性能を示す。
論文 参考訳（メタデータ） (2021-12-10T06:18:19Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - The Primal-Dual method for Learning Augmented Algorithms [10.2730668356857]
我々は、オンラインアルゴリズムの原始二重法を拡張し、次のアクションについてオンラインアルゴリズムにアドバイスする予測を組み込む。
我々のアルゴリズムは、予測が正確である場合にも、予測が誤解を招くとき、適切な保証を維持しながら、どのオンラインアルゴリズムよりも優れていることを示す。
論文 参考訳（メタデータ） (2020-10-22T11:58:47Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。