論文の概要: Sorting from Counterexamples
- arxiv url: http://arxiv.org/abs/2608.21579v1
- Date: Fri, 21 Aug 2026 19:29:39 GMT
- ステータス: 翻訳完了
- システム内更新日: 2026-08-25 13:29:43.295575
- Title: Sorting from Counterexamples
- Title(参考訳): Sorting (複数形 Sortings)
- Abstract要約: 未知の線形順序をn$アイテムで学習する問題について検討する。
返却された反例の最大$k$は非現実的であり、$k$は事前に知られていない。
最適なクエリの複雑さを定数要素まで決定する。
- 参考スコア(独自算出の注目度): 21.887990428338384
- License: http://creativecommons.org/licenses/by/4.0/
- Abstract: Consider the following problem of learning an unknown linear order on $n$ items. In each round, the learner guesses a complete ordering of the items and receives either confirmation that the guess is correct or a counterexample: a pair of items in the wrong order. The goal is to identify the unknown order using as few queries as possible. We study this problem when up to $k$ of the returned counterexamples may be untruthful, where $k$ is not known in advance. We determine the optimal query complexity up to constant factors: \[ Θ(n\log n + nk). \] Thus, while the noiseless complexity matches the classical complexity of sorting, each untruthful counterexample incurs an additional cost of order $n$. The upper bound is based on a geometric representation of permutations and Grünbaum's theorem, while the lower bound combines sorting arguments with a Condorcet-type construction. We also study the case where the target ranking has a low-dimensional geometric representation: each item is represented by a point in $\mathbb{R}^d$, and the ranking is obtained by projecting the points onto an unknown direction. For these classes we give an upper bound of $O(d^2\log n+dk)$ and a lower bound of $Ω(d\log n+dk)$, leaving a factor of $d$ gap in the noiseless term.
- Abstract(参考訳): 未知の線形順序を$n$アイテムで学習する際の次の問題を考える。
各ラウンドにおいて、学習者はアイテムの完全な順序を推測し、その推測が正しいか、あるいは逆例であるアイテムのペアが間違った順序で正しいかの確認を受ける。
目標は、クエリを可能な限り少なくして、未知の順序を特定することです。
我々は、返却された反例のうち最大$k$が非現実的かもしれない場合にこの問題を研究する。
最適クエリの複雑性を定数因子まで決定する: \[[[n\log n + nk]。
したがって、ノイズレスの複雑さはソートという古典的な複雑さと一致するが、それぞれの非現実的な反例は、追加で$n$のコストを発生させる。
上界は置換の幾何学的表現とグリュンバウムの定理に基づいており、下界はソート論法とコンドルチェット型構成を結合する。
また、対象のランクが低次元の幾何学的表現を持つ場合、各項目は$\mathbb{R}^d$の点で表され、その点を未知の方向に投影することによってランクを得る。
これらのクラスに対して、上界の$O(d^2\log n+dk)$と下界の$Ω(d\log n+dk)$を与える。
関連論文リスト
- Quantum Query Complexity of Finding a Tarski Fixed Point on a High-Dimensional Grid [31.45779401617503]
クナスター・タルスキーの不動点定理(Knaster-Tarski fixed-point theorem)は、完備格子上のすべての単調函数が不動点を持つという定理である。
非負スペクトル逆法を用いて、$[n]k$上の単調関数の固定点を求めるために、$(klog n)$量子クエリローバウンドを証明した。
論文 参考訳(メタデータ) (2026-09-03T13:06:12Z) - Faster quantum linear system solver beyond the condition number [50.84794327094274]
線形系の正規化解 $|xrangle$ を生成する2つの量子アルゴリズムを、条件数$=lVert A-1rVert$ に依存しない複雑性を持つ精度 $Ax=| b rangle$ に提示する。
フィルタベースのソルバは非常にシンプルで、実行時プレファクタが適しています。
論文 参考訳(メタデータ) (2026-07-08T17:49:40Z) - Statistical and computational challenges in ranking [53.03724383992195]
質問に対する回答の正しさに基づいて,専門家の能力に応じて$n$をランク付けする問題を考察する。
ここでは,この問題に対する統計的に最適かつ計算学的に効率的な手順の存在について検討する。
論文 参考訳(メタデータ) (2025-12-24T11:18:06Z) - Learning Partitions with Optimal Query and Round Complexities [16.815943270621638]
未知の$n$要素を少なくとも$k$集合に分割することの基本的な問題を考える。
非適応アルゴリズムには$Theta(n2)$クエリが必要ですが、適応アルゴリズムには$Theta(nk)$クエリが必要です。
我々のアルゴリズムは、最適な$O(nk)$クエリ複雑性を達成するために、$O(log log n)$ラウンドしか必要としない。
論文 参考訳(メタデータ) (2025-05-08T07:27:29Z) - Lower Bounds for Greedy Teaching Set Constructions [12.186950360560145]
我々は、小さな$k$に対してgreedyアルゴリズムの性能の低いバウンダリを証明した。
ほとんどの場合、我々の下界は小さな定数$c>0$に対して$k le lceil c d rceil$まで伸びる。
論文 参考訳(メタデータ) (2025-05-06T06:30:01Z) - From Contextual Combinatorial Semi-Bandits to Bandit List Classification: Improved Sample Complexity with Sparse Rewards [26.147671458980117]
我々は、入力コンテキストを、可能なアクションの集合の$m$のサブセットにマッピングするコンテキスト半帯域の問題を研究する。
文脈的包帯の原型的応用により、我々は$s$スパース体制に焦点をあてる。
本フレームワークは,二項報酬ベクトルの特別な場合として,帯域フィードバックを用いたリスト多クラス分類問題を一般化する。
論文 参考訳(メタデータ) (2025-02-13T12:13:25Z) - Optimal level set estimation for non-parametric tournament and crowdsourcing problems [49.75262185577198]
クラウドソーシングによって動機づけられた我々は、$d$の質問に対する$n$の専門家の回答の正しさを部分的に観察する問題を考える。
本稿では、専門家$i$が疑問に答える確率を含む行列$M$が、行と列の置換までの双等方性であることを仮定する。
我々は,この分類問題に対して最小限のアルゴリズムを最適に構築する。
論文 参考訳(メタデータ) (2024-08-27T18:28:31Z) - Measuring quantum relative entropy with finite-size effect [53.64687146666141]
相対エントロピー$D(rho|sigma)$を$sigma$が知られているときに推定する。
我々の推定器は次元$d$が固定されたときにCram'er-Rao型境界に達する。
論文 参考訳(メタデータ) (2024-06-25T06:07:20Z) - Efficiently Learning One-Hidden-Layer ReLU Networks via Schur
Polynomials [50.90125395570797]
正方形損失に関して、標準的なガウス分布の下での$k$ReLU活性化の線形結合をPAC学習する問題をmathbbRd$で検討する。
本研究の主な成果は,この学習課題に対して,サンプルおよび計算複雑性が$(dk/epsilon)O(k)$で,epsilon>0$が目標精度である。
論文 参考訳(メタデータ) (2023-07-24T14:37:22Z) - Randomised Composition and Small-Bias Minimax [0.9252523881586053]
クエリ複雑性に関する2つの結果が、$mathrmR(f)$であることを示す。
まず、「線形化」複雑性測度$mathrmLR$を導入し、内部衝突合成定理を満たすことを示す: $mathrmR(f) geq Omega(mathrmR(f) mathrmLR(g))$ for all partial $f$と$g$。
論文 参考訳(メタデータ) (2022-08-26T23:32:19Z) - Near-Optimal Regret Bounds for Contextual Combinatorial Semi-Bandits
with Linear Payoff Functions [53.77572276969548]
我々は、C$2$UCBアルゴリズムが分割マトロイド制約に対して最適な後悔結合$tildeO(dsqrtkT + dk)$を有することを示した。
一般的な制約に対して,C$2$UCBアルゴリズムで腕の報酬推定値を変更するアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-01-20T04:29:18Z) - An Optimal Separation of Randomized and Quantum Query Complexity [67.19751155411075]
すべての決定木に対して、与えられた順序 $ellsqrtbinomdell (1+log n)ell-1,$ sum to at least $cellsqrtbinomdell (1+log n)ell-1,$ where $n$ is the number of variables, $d$ is the tree depth, $c>0$ is a absolute constant。
論文 参考訳(メタデータ) (2020-08-24T06:50:57Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。