論文の概要: Metrical Task Systems with Online Machine Learned Advice
- arxiv url: http://arxiv.org/abs/2012.09394v1
- Date: Thu, 17 Dec 2020 04:56:51 GMT
- ステータス: 処理完了
- システム内更新日: 2021-05-02 23:48:21.565547
- Title: Metrical Task Systems with Online Machine Learned Advice
- Title（参考訳）: オンラインマシン学習アドバイスを用いた計量タスクシステム
- Authors: Kevin Rao
- Abstract要約: 機械学習予測器によるオンラインアルゴリズムの強化は,予測器の精度が適切であれば,競争比を確実に低下させることができることを示す。
我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(log n)$競争である。
- 参考スコア（独自算出の注目度）: 0.0
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Machine learning algorithms are designed to make accurate predictions of the
future based on existing data, while online algorithms seek to bound some
performance measure (typically the competitive ratio) without knowledge of the
future. Lykouris and Vassilvitskii demonstrated that augmenting online
algorithms with a machine learned predictor can provably decrease the
competitive ratio under as long as the predictor is suitably accurate.
In this work we apply this idea to the Online Metrical Task System problem,
which was put forth by Borodin, Linial, and Saks as a general model for dynamic
systems processing tasks in an online fashion. We focus on the specific class
of uniform task systems on $n$ tasks, for which the best deterministic
algorithm is $O(n)$ competitive and the best randomized algorithm is $O(\log
n)$ competitive.
By giving an online algorithms access to a machine learned oracle with
absolute predictive error bounded above by $\eta_0$, we construct a
$\Theta(\min(\sqrt{\eta_0}, \log n))$ competitive algorithm for the uniform
case of the metrical task systems problem. We also give a $\Theta(\log
\sqrt{\eta_0})$ lower bound on the competitive ratio of any randomized
algorithm.
- Abstract（参考訳）: 機械学習アルゴリズムは、既存のデータに基づいて、将来の正確な予測を行うように設計されているが、オンラインアルゴリズムは、将来を知らずに、いくつかのパフォーマンス指標(通常、競争比率)に縛り付けようとしている。
lykourisとvassilvitskiiは、オンラインアルゴリズムを機械学習予測器で拡張することで、予測器が適当に正確である限り、競争比が確実に低下することを示した。
そこで本稿では,boodin,linial,saks らによって提起されたオンライン計量タスクシステム問題に対して,動的システム処理タスクの汎用モデルとして,この概念を適用した。
我々は、$n$タスク上の一様タスクシステムの特定のクラスに焦点を当て、最良の決定論的アルゴリズムは$O(n)$競争であり、最良のランダム化アルゴリズムは$O(\log n)$競争である。
オンラインのアルゴリズムで学習したオラクルに絶対的な予測誤差を$\eta_0$で有界でアクセスすることで、メートル法タスクシステムの一様問題に対して$\Theta(\min(\sqrt{\eta_0}, \log n))$の競合アルゴリズムを構築する。
また、任意のランダム化アルゴリズムの競合比に対して、$\Theta(\log \sqrt{\eta_0})$低い境界を与える。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Mixing predictions for online metric algorithms [34.849039387367455]
我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。
我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。
我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
論文 参考訳（メタデータ） (2023-04-04T13:18:00Z) - Streaming Algorithms for Learning with Experts: Deterministic Versus
Robust [62.98860182111096]
エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。
目標は最小限のコストで予測を行うことだ。
最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
論文 参考訳（メタデータ） (2023-03-03T04:39:53Z) - Solving the Online Assignment Problem with Machine Learned Advice [0.0]
オンライン代入問題に対するオンラインアルゴリズムは、事前に入力全体を予測する機械学習アルゴリズムをシミュレートして提供する。
機械学習予測誤差が増加するにつれて、解の質が低下することを示す。
論文 参考訳（メタデータ） (2022-08-08T09:54:22Z) - 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) - Choosing the Right Algorithm With Hints From Complexity Theory [16.33500498939925]
我々は,メトロポリスのアルゴリズムが,合理的な問題サイズを考慮に入れた全てのアルゴリズムの中で,明らかに最良のものであることを示す。
このタイプの人工アルゴリズムは、$O(n log n)$ランタイムを持つので、重要度に基づくコンパクト遺伝的アルゴリズム(sig-cGA)は、高い確率で、DLB問題を解くことができる。
論文 参考訳（メタデータ） (2021-09-14T11:12:32Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online
Algorithms [85.97516436641533]
機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。
目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。
機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
論文 参考訳（メタデータ） (2020-10-22T04:51:01Z) - Fast Learning for Renewal Optimization in Online Task Scheduling [18.935043109084543]
本稿では,リニューアル・リワードシステムのオンライン最適化について考察する。
タスク型ベクトルの確率分布は未知である。
提案アルゴリズムは,古典的なRobins-Monroイテレーションに従って更新される補助変数を用いる。
論文 参考訳（メタデータ） (2020-07-18T22:44:13Z) - Online Page Migration with ML Advice [26.929268665630342]
提案手法は,エムページマイグレーション問題に対するオンラインアルゴリズムで,予測が不完全である可能性があり,その性能向上を図っている。
アルゴリズムが入力シーケンスの予測を与えられると、競合比が1ドルになることを示す。
我々の成果は、機械学習を使って古典的なアルゴリズムの性能を向上させる、最近の仕事の本体に追加される。
論文 参考訳（メタデータ） (2020-06-09T03:15:34Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。