論文の概要: Mixing predictions for online metric algorithms

• arxiv url: http://arxiv.org/abs/2304.01781v2
• Date: Fri, 15 Dec 2023 20:24:55 GMT
• ステータス: 処理完了
• システム内更新日: 2023-12-19 21:08:42.722414
• Title: Mixing predictions for online metric algorithms
• Title（参考訳）: オンライン計量アルゴリズムの混合予測
• Authors: Antonios Antoniadis and Christian Coester and Marek Eli\'a\v{s} and Adam Polak and Bertrand Simon
• Abstract要約: 我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。 我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。 我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
• 参考スコア（独自算出の注目度）: 34.849039387367455
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: A major technique in learning-augmented online algorithms is combining multiple algorithms or predictors. Since the performance of each predictor may vary over time, it is desirable to use not the single best predictor as a benchmark, but rather a dynamic combination which follows different predictors at different times. We design algorithms that combine predictions and are competitive against such dynamic combinations for a wide class of online problems, namely, metrical task systems. Against the best (in hindsight) unconstrained combination of $\ell$ predictors, we obtain a competitive ratio of $O(\ell^2)$, and show that this is best possible. However, for a benchmark with slightly constrained number of switches between different predictors, we can get a $(1+\epsilon)$-competitive algorithm. Moreover, our algorithms can be adapted to access predictors in a bandit-like fashion, querying only one predictor at a time. An unexpected implication of one of our lower bounds is a new structural insight about covering formulations for the $k$-server problem.
• Abstract（参考訳）: オンラインアルゴリズムの学習における主要なテクニックは、複数のアルゴリズムや予測器を組み合わせることである。 各予測器の性能は時間とともに変化するため、ベンチマークとして最適な予測器ではなく、異なるタイミングで異なる予測器に従う動的組み合わせを使用することが望ましい。 我々は、予測を組み合わせるアルゴリズムを設計し、様々なオンライン問題、すなわちメートル法タスクシステムに対してそのような動的組み合わせと競合する。 最高の(後から見て)$\ell$予測器の制約のない組み合わせに対して、我々は$o(\ell^2)$の競合比を取得し、これが最善であることを示す。 しかし、異なる予測子間のスイッチ数がわずかに制限されたベンチマークでは、$(1+\epsilon)$-competitiveアルゴリズムが得られる。 さらに,我々のアルゴリズムは,バンディットのような方法で予測器にアクセスするように適応することができ,同時に1つの予測器のみを問い合わせることができる。 k$-server問題の定式化をカバーする新しい構造的洞察が、私たちの下限の1つに予期せぬ意味を持つ。

関連論文リスト

• Competitive Algorithms for Online Knapsack with Succinct Predictions [16.793099279933163]
  オンラインのknapsack問題では、異なる値と重みを持つオンラインで到着するアイテムをキャパシティ限定のknapsackにまとめて、受け入れられたアイテムの総価値を最大化する。 この問題に対するテキスト学習強化アルゴリズムについて検討し、機械学習による予測を用いて悲観的な最悪のケースの保証を超えて行動することを目的とする。
  論文  参考訳（メタデータ） (2024-06-26T20:38:00Z)
• Competitive strategies to use "warm start" algorithms with predictions [12.970501425097645]
  本稿では,温暖化開始アルゴリズムの学習と予測利用の問題点について考察する。 この設定では、アルゴリズムは問題のインスタンスと解の予測を与える。 我々は、$k$の予測を考慮に入れたより強力なベンチマークに対して、競争力のある保証を与えます。
  論文  参考訳（メタデータ） (2024-05-06T17:38:20Z)
• Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
  本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。 我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
  論文  参考訳（メタデータ） (2023-05-16T07:52:08Z)
• Streaming Algorithms for Learning with Experts: Deterministic Versus Robust [62.98860182111096]
  エキスパート問題を伴うオンライン学習では、アルゴリズムは、T$day(または時間)ごとに結果を予測する必要がある。 目標は最小限のコストで予測を行うことだ。 最良専門家が$M$の誤りを犯したとき、後悔する$R$を達成するような決定論的アルゴリズムに対して、$widetildeOmegaleft(fracnMRTright)$の空間下界を示す。
  論文  参考訳（メタデータ） (2023-03-03T04:39:53Z)
• Minimalistic Predictions to Schedule Jobs with Online Precedence Constraints [117.8317521974783]
  オンライン優先制約による非サーボ的スケジューリングについて検討する。 アルゴリズムは、任意のジョブ依存に偏りがなく、前任者がすべて完了した場合に限り、ジョブについて学習する。
  論文  参考訳（メタデータ） (2023-01-30T13:17:15Z)
• Algorithms with Prediction Portfolios [23.703372221079306]
  我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。 これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
  論文  参考訳（メタデータ） (2022-10-22T12:58:07Z)
• Memory Bounds for the Experts Problem [53.67419690563877]
  専門家のアドバイスによるオンライン学習は、逐次予測の根本的な問題である。 目標は、予測を処理し、最小コストで予測を行うことです。 アルゴリズムは、そのセットでもっとも優れた専門家と比較してどれだけうまく機能するかによって判断される。
  論文  参考訳（メタデータ） (2022-04-21T01:22:18Z)
• Robustification of Online Graph Exploration Methods [59.50307752165016]
  我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。 本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
  論文  参考訳（メタデータ） (2021-12-10T10:02:31Z)
• Double Coverage with Machine-Learned Advice [100.23487145400833]
  オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。 我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
  論文  参考訳（メタデータ） (2021-03-02T11:04:33Z)
• Online Multivalid Learning: Means, Moments, and Prediction Intervals [16.75129633574157]
  本稿では,様々な意味で「多値」な文脈予測手法を提案する。 得られた見積もりは、単に限界ではなく、$ Y$ラベルのさまざまな統計を正しく予測します。 我々のアルゴリズムは逆選択の例を扱うので、任意の点予測法の残差の統計量を予測するのに等しく使用できる。
  論文  参考訳（メタデータ） (2021-01-05T19:08:11Z)
• Malicious Experts versus the multiplicative weights algorithm in online prediction [85.62472761361107]
  2人の専門家と1人の予測者による予測問題を考える。 専門家の一人が正直で、各ラウンドで確率$mu$で正しい予測をしていると仮定する。 もう一つは悪意のあるもので、各ラウンドで真の結果を知り、予測者の損失を最大化するために予測を行う。
  論文  参考訳（メタデータ） (2020-03-18T20:12:08Z)

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

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