論文の概要: Sorting with Predictions
- arxiv url: http://arxiv.org/abs/2311.00749v1
- Date: Wed, 1 Nov 2023 18:00:03 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-03 16:07:53.669167
- Title: Sorting with Predictions
- Title（参考訳）: 予測でソートする
- Authors: Xingjian Bai, Christian Coester
- Abstract要約: 学習強化アルゴリズムのレンズをソートする根本的な問題について検討する。
我々は,$O(sum_i log eta_i)$の正確な比較だけで,新しい,シンプルなアルゴリズムを設計する。
比較複雑性は, 検証された誤差測度に対して理論的に最適であることを示す。
- 参考スコア（独自算出の注目度）: 1.7042264000899532
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: We explore the fundamental problem of sorting through the lens of
learning-augmented algorithms, where algorithms can leverage possibly erroneous
predictions to improve their efficiency. We consider two different settings: In
the first setting, each item is provided a prediction of its position in the
sorted list. In the second setting, we assume there is a "quick-and-dirty" way
of comparing items, in addition to slow-and-exact comparisons. For both
settings, we design new and simple algorithms using only $O(\sum_i \log
\eta_i)$ exact comparisons, where $\eta_i$ is a suitably defined prediction
error for the $i$th element. In particular, as the quality of predictions
deteriorates, the number of comparisons degrades smoothly from $O(n)$ to
$O(n\log n)$. We prove that the comparison complexity is theoretically optimal
with respect to the examined error measures. An experimental evaluation against
existing adaptive and non-adaptive sorting algorithms demonstrates the
potential of applying learning-augmented algorithms in sorting tasks.
- Abstract（参考訳）: 本稿では,アルゴリズムが誤予測を利用して効率を向上する,学習強化アルゴリズムのレンズをソートする根本的な問題を考察する。
最初の設定では、各項目はソートされたリストにおけるその位置の予測が提供される。
2つ目の設定では、アイテムを比較する「クイック・アンド・ダーティ」な方法と、スロー・アンド・エクティヴな比較が存在すると仮定する。
どちらの設定でも、$O(\sum_i \log \eta_i)$と$O(\sum_i \eta_i)$の正確な比較だけで、新しいアルゴリズムと単純なアルゴリズムを設計します。
特に、予測の質が悪化するにつれて、比較の数は$O(n)$から$O(n\log n)$に滑らかに低下する。
比較複雑性は, 検証された誤差測度に対して理論的に最適であることを示す。
既存の適応型および非適応型ソートアルゴリズムに対する実験的評価は、学習型ソートアルゴリズムをソートタスクに適用する可能性を実証する。
関連論文リスト
- Perturb-and-Project: Differentially Private Similarities and Marginals [73.98880839337873]
差分プライバシーのための入力摂動フレームワークを再検討し、入力にノイズを付加する。
まず、ペアワイズ・コサイン類似性をプライベートにリリースするための新しい効率的なアルゴリズムを設計する。
我々は,$k$の辺縁クエリを$n$の機能に対して計算する新しいアルゴリズムを導出する。
論文 参考訳（メタデータ） (2024-06-07T12:07:16Z) - Rahmani Sort: A Novel Variant of Insertion Sort Algorithm with O(nlogn) Complexity [0.0]
本稿では,2進探索機構の新たな手法を用いて,前述した左サブアレイへの次のキー項目のソート位置を探索するアルゴリズムを提案する。
その結果,従来の挿入ソートアルゴリズムやマージソートアルゴリズムよりも,新しいアルゴリズムの方が優れた性能を示した。
論文 参考訳（メタデータ） (2024-02-29T12:38:57Z) - Faster Convergence with Multiway Preferences [99.68922143784306]
本稿では,符号関数に基づく比較フィードバックモデルについて考察し,バッチとマルチウェイの比較による収束率の解析を行う。
本研究は,マルチウェイ選好による凸最適化の問題を初めて研究し,最適収束率を解析するものである。
論文 参考訳（メタデータ） (2023-12-19T01:52:13Z) - Sorting and Hypergraph Orientation under Uncertainty with Predictions [0.45880283710344055]
本研究では,不確実性下でのソートとハイパーグラフ配向のための学習強化アルゴリズムについて検討する。
我々のアルゴリズムは、予測なしで最良となる最悪の保証を維持しつつ、精度の高い予測性能を保証する。
論文 参考訳（メタデータ） (2023-05-16T07:52:08Z) - Mixing predictions for online metric algorithms [34.849039387367455]
我々は予測を組み合わせるアルゴリズムを設計し、このような動的組み合わせと競合する。
我々のアルゴリズムは、バンディットのような方法で予測者にアクセスするように適応することができ、一度に1つの予測者しかクエリできない。
我々の下界の1つが予想外の意味を持つのは、$k$-server問題に対する定式化のカバーに関する新しい構造的洞察である。
論文 参考訳（メタデータ） (2023-04-04T13:18:00Z) - Adaptive Sampling for Heterogeneous Rank Aggregation from Noisy Pairwise
Comparisons [85.5955376526419]
ランキングアグリゲーション問題では、各項目を比較する際に、様々な精度レベルが示される。
本稿では,ノイズのあるペアワイズ比較によってアイテムのランクを推定する,除去に基づくアクティブサンプリング戦略を提案する。
提案アルゴリズムは,商品の真のランキングを高い確率で返却できることを示す。
論文 参考訳（メタデータ） (2021-10-08T13:51:55Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - Ranking a set of objects: a graph based least-square approach [70.7866286425868]
同一労働者の群集によるノイズの多いペアワイズ比較から始まる$N$オブジェクトのランク付けの問題について考察する。
品質評価のために,最小二乗内在的最適化基準に依存する非適応的ランキングアルゴリズムのクラスを提案する。
論文 参考訳（メタデータ） (2020-02-26T16:19:09Z) - Learning Sparse Classifiers: Continuous and Mixed Integer Optimization
Perspectives [10.291482850329892]
混合整数計画法(MIP)は、(最適に) $ell_0$-正規化回帰問題を解くために用いられる。
数分で5万ドルの機能を処理できる正確なアルゴリズムと、$papprox6$でインスタンスに対処できる近似アルゴリズムの2つのクラスを提案する。
さらに,$ell$-regularizedsに対する新しい推定誤差境界を提案する。
論文 参考訳（メタデータ） (2020-01-17T18:47:02Z) - Optimal Clustering from Noisy Binary Feedback [75.17453757892152]
本稿では,二元的ユーザフィードバックから一組のアイテムをクラスタリングする問題について検討する。
最小クラスタ回復誤差率のアルゴリズムを考案する。
適応選択のために,情報理論的誤差下界の導出にインスパイアされたアルゴリズムを開発する。
論文 参考訳（メタデータ） (2019-10-14T09:18:26Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。