論文の概要: Online Covering with Multiple Experts

• arxiv url: http://arxiv.org/abs/2312.14564v1
• Date: Fri, 22 Dec 2023 09:48:45 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-25 15:26:55.483510
• Title: Online Covering with Multiple Experts
• Title（参考訳）: 複数の専門家によるオンラインカバレッジ
• Authors: Enik\H{o} Kevi and Kim-Thang Nguyen
• Abstract要約: 我々は,複数の専門家によるオンラインアルゴリズムの設計について研究する。 性能保証が$O(log K)$である新しい動的ベンチマークに競合アルゴリズムを提示する。
• 参考スコア（独自算出の注目度）: 5.955727366271805
• License: http://creativecommons.org/licenses/by-nc-sa/4.0/
• Abstract: Designing online algorithms with machine learning predictions is a recent technique beyond the worst-case paradigm for various practically relevant online problems (scheduling, caching, clustering, ski rental, etc.). While most previous learning-augmented algorithm approaches focus on integrating the predictions of a single oracle, we study the design of online algorithms with \emph{multiple} experts. To go beyond the popular benchmark of a static best expert in hindsight, we propose a new \emph{dynamic} benchmark (linear combinations of predictions that change over time). We present a competitive algorithm in the new dynamic benchmark with a performance guarantee of $O(\log K)$, where $K$ is the number of experts, for $0-1$ online optimization problems. Furthermore, our multiple-expert approach provides a new perspective on how to combine in an online manner several online algorithms - a long-standing central subject in the online algorithm research community.
• Abstract（参考訳）: 機械学習の予測でオンラインアルゴリズムを設計することは、スケジューリング、キャッシュ、クラスタリング、スキーレンタルなど、様々な実践的なオンライン問題に対する最悪のパラダイムを越えている。 従来の学習強化アルゴリズムのアプローチでは,単一オラクルの予測の統合に重点を置いていたが,オンラインアルゴリズムの設計をemph{multiple}の専門家と検討した。 静的なベストエキスパートの人気のあるベンチマークを越えて、新しい \emph{dynamic}ベンチマーク(時間とともに変化する予測の線形組み合わせ)を提案します。 我々は,新しい動的ベンチマークにおいて,専門家数を$k$とし,オンライン最適化問題に対して$0-1$の性能保証を行うアルゴリズムを提案する。 さらに,マルチエキスパートアプローチは,オンラインアルゴリズム研究コミュニティにおける長年の中心的なテーマである,いくつかのオンラインアルゴリズムをオンラインに結合する方法に関する新たな視点を提供する。

関連論文リスト

• Learning-Augmented Algorithms for Online Concave Packing and Convex Covering Problems [4.9826534303287335]
  本稿では,2つの基本的な最適化設定のための学習強化アルゴリズムフレームワークを提案する。 コンケーブ目的のオンラインパッキングでは、アドバイスと最先端のオンラインアルゴリズムを切り替える、単純だが包括的な戦略を提示します。 我々のアルゴリズムは、アドバイスが正確であるとき、そしてアドバイスが間違っていても、最先端の古典的オンラインアルゴリズムと同等のパフォーマンスを維持しながら、不可能な結果を破ることを示した。
  論文  参考訳（メタデータ） (2024-11-13T04:27:25Z)
• A Simple Learning-Augmented Algorithm for Online Packing with Concave Objectives [4.9826534303287335]
  本稿では,線形制約付きオンラインパッキング問題に対する単純な学習拡張アルゴリズムの導入と解析を行う。 さらに、このような単純なブラックボックス解が最適である場合に必要かつ十分な条件を理解するという問題を提起する。
  論文  参考訳（メタデータ） (2024-06-05T18:39:28Z)
• Learning-Augmented Algorithms with Explicit Predictors [67.02156211760415]
  アルゴリズム設計の最近の進歩は、過去のデータと現在のデータから得られた機械学習モデルによる予測の活用方法を示している。 この文脈における以前の研究は、予測器が過去のデータに基づいて事前訓練され、ブラックボックスとして使用されるパラダイムに焦点を当てていた。 本研究では,予測器を解き,アルゴリズムの課題の中で生じる学習問題を統合する。
  論文  参考訳（メタデータ） (2024-03-12T08:40:21Z)
• Efficient Methods for Non-stationary Online Learning [67.3300478545554]
  本稿では, 動的後悔と適応的後悔を最適化する効率的な手法を提案し, ラウンド当たりの投影回数を$mathcalO(log T)$から$ $1$まで削減した。 本手法は,パラメータフリーオンライン学習において開発された還元機構を基礎として,非定常オンライン手法に非自明なツイストを必要とする。
  論文  参考訳（メタデータ） (2023-09-16T07:30:12Z)
• 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)
• Online Algorithms with Multiple Predictions [17.803569868141647]
  本稿では,複数の機械学習予測を付加したオンラインアルゴリズムについて検討する。 我々のアルゴリズムは、オンラインアルゴリズムの古典的ポテンシャルに基づく分析に予測の利用を取り入れている。
  論文  参考訳（メタデータ） (2022-05-08T17:33:01Z)
• Learning Predictions for Algorithms with Predictions [49.341241064279714]
  予測器を学習するアルゴリズムに対して,一般的な設計手法を導入する。 オンライン学習の手法を応用して、敵のインスタンスに対して学習し、堅牢性と一貫性のあるトレードオフを調整し、新しい統計的保証を得る。 両部マッチング,ページマイグレーション,スキーレンタル,ジョブスケジューリングの手法を解析することにより,学習アルゴリズムの導出におけるアプローチの有効性を実証する。
  論文  参考訳（メタデータ） (2022-02-18T17:25:43Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• The Primal-Dual method for Learning Augmented Algorithms [10.2730668356857]
  我々は、オンラインアルゴリズムの原始二重法を拡張し、次のアクションについてオンラインアルゴリズムにアドバイスする予測を組み込む。 我々のアルゴリズムは、予測が正確である場合にも、予測が誤解を招くとき、適切な保証を維持しながら、どのオンラインアルゴリズムよりも優れていることを示す。
  論文  参考訳（メタデータ） (2020-10-22T11:58:47Z)
• Optimal Robustness-Consistency Trade-offs for Learning-Augmented Online Algorithms [85.97516436641533]
  機械学習予測を取り入れたオンラインアルゴリズムの性能向上の課題について検討する。 目標は、一貫性と堅牢性の両方を備えたアルゴリズムを設計することだ。 機械学習予測を用いた競合解析のための非自明な下界の最初のセットを提供する。
  論文  参考訳（メタデータ） (2020-10-22T04:51:01Z)

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

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