論文の概要: Sorting and Hypergraph Orientation under Uncertainty with Predictions
- arxiv url: http://arxiv.org/abs/2305.09245v1
- Date: Tue, 16 May 2023 07:52:08 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-17 15:55:58.381027
- Title: Sorting and Hypergraph Orientation under Uncertainty with Predictions
- Title(参考訳): 予測の不確実性下におけるソルティングとハイパーグラフ配向
- Authors: Thomas Erlebach, Murilo Santos de Lima, Nicole Megow, Jens Schl\"oter
- Abstract要約: 本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。
我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
- 参考スコア(独自算出の注目度): 0.45880283710344055
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Learning-augmented algorithms have been attracting increasing interest, but
have only recently been considered in the setting of explorable uncertainty
where precise values of uncertain input elements can be obtained by a query and
the goal is to minimize the number of queries needed to solve a problem. We
study learning-augmented algorithms for sorting and hypergraph orientation
under uncertainty, assuming access to untrusted predictions for the uncertain
values. Our algorithms provide improved performance guarantees for accurate
predictions while maintaining worst-case guarantees that are best possible
without predictions. For hypergraph orientation, for any $\gamma \geq 2$, we
give an algorithm that achieves a competitive ratio of $1+1/\gamma$ for correct
predictions and $\gamma$ for arbitrarily wrong predictions. For sorting, we
achieve an optimal solution for accurate predictions while still being
$2$-competitive for arbitrarily wrong predictions. These tradeoffs are the best
possible. We also consider different error metrics and show that the
performance of our algorithms degrades smoothly with the prediction error in
all the cases where this is possible.
- Abstract(参考訳): 学習強化アルゴリズムの関心は高まっているが,不確実な入力要素の正確な値がクエリによって得られるような探索不可能な不確実性の設定においては,問題解決に必要なクエリ数を最小化することが目的である。
不確実性下でのソートとハイパーグラフの向き付けのための学習型アルゴリズムについて,不確実性値に対する信頼できない予測へのアクセスを仮定して検討した。
我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
ハイパーグラフの向きについては、任意の$\gamma \geq 2$に対して、正しい予測に対して1+1/\gamma$、任意の間違った予測に対して$\gamma$の競合比を達成するアルゴリズムを与える。
ソートのためには、正確な予測に最適な解を得ると同時に、任意に間違った予測に2ドル競争的である。
これらのトレードオフが最善である。
また、異なるエラーメトリクスを検討し、このことが可能なすべてのケースにおいて、予測誤差によりアルゴリズムの性能がスムーズに低下することを示す。
関連論文リスト
- 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) - Algorithms with Prediction Portfolios [23.703372221079306]
我々は、マッチング、ロードバランシング、非クレアボイラントスケジューリングなど、多くの基本的な問題に対する複数の予測器の使用について検討する。
これらの問題のそれぞれに対して、複数の予測器を利用する新しいアルゴリズムを導入し、その結果のパフォーマンスに限界を証明します。
論文 参考訳(メタデータ) (2022-10-22T12:58:07Z) - Efficient and Differentiable Conformal Prediction with General Function
Classes [96.74055810115456]
本稿では,複数の学習可能なパラメータに対する共形予測の一般化を提案する。
本研究は, クラス内において, ほぼ有効な人口被覆率, ほぼ最適効率を実現していることを示す。
実験の結果,提案アルゴリズムは有効な予測セットを学習し,効率を著しく向上できることがわかった。
論文 参考訳(メタデータ) (2022-02-22T18:37:23Z) - 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) - 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)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。