論文の概要: Binary Search with Distributional Predictions
- arxiv url: http://arxiv.org/abs/2411.16030v1
- Date: Mon, 25 Nov 2024 01:15:31 GMT
- ステータス: 翻訳完了
- システム内更新日: 2024-11-26 14:18:33.371629
- Title: Binary Search with Distributional Predictions
- Title（参考訳）: 分布予測を用いたバイナリ探索
- Authors: Michael Dinitz, Sungjin Im, Thomas Lavastida, Benjamin Moseley, Aidin Niaparast, Sergei Vassilvitskii,
- Abstract要約: 本研究では,予測自体が分布である分布予測を用いたアルゴリズムについて検討する。
従来の予測に基づくアルゴリズムを1つの予測で使用すると、予測が不十分な単純な分布が存在することを示す。
これはまた、二分探索木を最適に計算する古典的な問題に対する最初の分散ロバストアルゴリズムをもたらす。
- 参考スコア（独自算出の注目度）: 26.193119064206304
- License:
- Abstract: Algorithms with (machine-learned) predictions is a powerful framework for combining traditional worst-case algorithms with modern machine learning. However, the vast majority of work in this space assumes that the prediction itself is non-probabilistic, even if it is generated by some stochastic process (such as a machine learning system). This is a poor fit for modern ML, particularly modern neural networks, which naturally generate a distribution. We initiate the study of algorithms with distributional predictions, where the prediction itself is a distribution. We focus on one of the simplest yet fundamental settings: binary search (or searching a sorted array). This setting has one of the simplest algorithms with a point prediction, but what happens if the prediction is a distribution? We show that this is a richer setting: there are simple distributions where using the classical prediction-based algorithm with any single prediction does poorly. Motivated by this, as our main result, we give an algorithm with query complexity $O(H(p) + \log \eta)$, where $H(p)$ is the entropy of the true distribution $p$ and $\eta$ is the earth mover's distance between $p$ and the predicted distribution $\hat p$. This also yields the first distributionally-robust algorithm for the classical problem of computing an optimal binary search tree given a distribution over target keys. We complement this with a lower bound showing that this query complexity is essentially optimal (up to constants), and experiments validating the practical usefulness of our algorithm.
- Abstract（参考訳）: 機械学習した)予測を伴うアルゴリズムは、従来の最悪のアルゴリズムと現代の機械学習を組み合わせるための強力なフレームワークである。
しかし、この分野のほとんどの研究は、たとえそれが確率過程(例えば機械学習システム)によって生成されるとしても、予測自体が確率的ではないと仮定している。
これは、分散を自然に生成するモダンなML、特にモダンなニューラルネットワークに適していない。
予測自体が分布である分布予測を伴うアルゴリズムの研究を開始する。
私たちは、バイナリ検索(またはソートされた配列の検索)という最も単純だが基本的な設定の1つに焦点を当てています。
この設定は、ポイント予測を持つ最も単純なアルゴリズムの1つを持っているが、その予測が分布であればどうなるのか?
これはよりリッチな設定であり、単一の予測で古典的予測に基づくアルゴリズムが不十分な単純な分布が存在することを示している。
ここで、$H(p)$は真分布のエントロピーで$p$と$\eta$は地球移動子の$p$と予測分布の$\hat p$の間の距離である。
これはまた、ターゲットキー上の分布を与えられた最適な二分探索木を演算する古典的な問題に対する最初の分散ロバストアルゴリズムを与える。
我々は,このクエリの複雑さが本質的に最適であること(定数まで)と,アルゴリズムの実用性を検証する実験によってこれを補足する。
関連論文リスト
- 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) - Private estimation algorithms for stochastic block models and mixture
models [63.07482515700984]
効率的なプライベート推定アルゴリズムを設計するための一般的なツール。
最初の効率的な$(epsilon, delta)$-differentially private algorithm for both weak recovery and exact recovery。
論文 参考訳（メタデータ） (2023-01-11T09:12:28Z) - Scheduling with Speed Predictions [10.217102227210669]
本稿では,ジョブの処理時間ではなく,マシンの速度が不明な速度ロスのスケジューリング問題について検討する。
我々の主な結果は、$mineta2 (1+epsilon)2 (1+epsilon)(2+2/alpha)$近似を達成するアルゴリズムである。
予測が正確であれば、この近似は以前最もよく知られた2-1/m$の近似よりも改善される。
論文 参考訳（メタデータ） (2022-05-02T23:39:41Z) - The Quantum Version of Prediction for Binary Classification Problem by
Ensemble Methods [0.0]
本稿では、量子アルゴリズムを用いてバイナリ分類問題の結果を予測する性能について考察する。
我々は$Oleft(sqrtN cdot Tright)$で機能するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-26T10:25:34Z) - Robustification of Online Graph Exploration Methods [59.50307752165016]
我々は、古典的で有名なオンライングラフ探索問題の学習強化版について研究する。
本稿では,予測をよく知られたNearest Neighbor(NN)アルゴリズムに自然に統合するアルゴリズムを提案する。
論文 参考訳（メタデータ） (2021-12-10T10:02:31Z) - Faster Matchings via Learned Duals [31.61057940283721]
機械学習予測のアイデアと「スタート・ウォーム」原始二元アルゴリズムのアイデアを組み合わせる。
まず、予測可能な双対は実現不可能である可能性があるので、予測できない双対を近くの実現可能な解に効率的にマッピングするアルゴリズムを提供する。
第二に、一度双対が実現可能ならば、それらは最適ではないかもしれない。
論文 参考訳（メタデータ） (2021-07-20T21:11:09Z) - Double Coverage with Machine-Learned Advice [100.23487145400833]
オンラインの基本的な$k$-serverの問題を学習強化環境で研究する。
我々のアルゴリズムは任意の k に対してほぼ最適の一貫性-破壊性トレードオフを達成することを示す。
論文 参考訳（メタデータ） (2021-03-02T11:04:33Z) - List-Decodable Mean Estimation in Nearly-PCA Time [50.79691056481693]
高次元におけるリストデコタブル平均推定の基本的な課題について検討する。
我々のアルゴリズムは、すべての$k = O(sqrtd) cup Omega(d)$に対して$widetildeO(ndk)$で実行されます。
我々のアルゴリズムの変種は、すべての$k$に対してランタイム$widetildeO(ndk)$を持ち、リカバリ保証の$O(sqrtlog k)$ Factorを犠牲にしている。
論文 参考訳（メタデータ） (2020-11-19T17:21:37Z) - Efficient Computation of Expectations under Spanning Tree Distributions [67.71280539312536]
本稿では,エッジファクター,非プロジェクティブ・スパンニングツリーモデルにおいて,一階期待と二階期待の重要なケースに対する統一アルゴリズムを提案する。
我々のアルゴリズムは勾配と期待の基本的な関係を利用しており、効率的なアルゴリズムを導出することができる。
論文 参考訳（メタデータ） (2020-08-29T14:58:26Z) - A New Minimax Theorem for Randomized Algorithms [1.2284934135116514]
新しいタイプのミニマックス定理を導入し、全てのバイアスレベルに一度に作用するハード分布の$mu$を提供する。
ランダム化クエリの複雑性,ランダム化通信の複雑性,近似度数,近似対数に対して有効であることを示す。
また、Impagliazzoのハードコアの改良版も証明した。
論文 参考訳（メタデータ） (2020-02-25T11:46:08Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。