Fugu-MT 論文翻訳(概要): Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

論文の概要: Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples

arxiv url: http://arxiv.org/abs/2610.11145v1
Date: Thu, 08 Oct 2026 03:10:12 GMT
ステータス: 翻訳完了
システム内更新日: 2026-10-10 02:36:53.756222
Title: Tight Bounds for Equivalence Testing with Non-Adaptive Conditional Samples
Title（参考訳）: 非適応条件サンプルを用いた等価テストのためのタイト境界
Abstract要約: 2つの未知の分布が、全変動距離において互いに等しいか、または$varepsilon$-farに等しいかを決定する。我々のアルゴリズムと下限は、$tilde left(fraclog nvarepsilon2right)$ queryが問題に対して必要で十分であることを示している。
参考スコア（独自算出の注目度）: 5.76899890843843
License: http://creativecommons.org/licenses/by/4.0/
Abstract: We study distribution testing with access to non-adaptive conditional samples. Specifically, we give tight bounds for equivalence testing, determining whether two unknown distributions are equal to or $\varepsilon$-far from each other in total variation distance. Our algorithm and lower bound show that $\tilde Θ\left(\frac{\log n}{\varepsilon^2}\right)$ queries are necessary and sufficient for this problem. These results demonstrate that the complexity of uniformity, identity, and equivalence testing with non-adaptive conditional samples are all $\tilde Θ(\log n)$.
Abstract（参考訳）: 非適応型条件付きサンプルへのアクセスによる分散テストについて検討する。具体的には、2つの未知の分布が全変動距離において互いに等しいか、または$\varepsilon$-farであるかどうかを判定する同値性試験に厳密な境界を与える。我々のアルゴリズムと下界は、$\tilde >\left(\frac{\log n}{\varepsilon^2}\right)$クエリが問題に対して必要で十分であることを示している。これらの結果は、非適応条件付きサンプルによる一様性、恒等性、同値性テストの複雑さがすべて$\tilde >(\log n)$であることを示している。

関連論文リスト

Two-Sample Testing via Generative Processes [60.42943145582429]
生成輸送は、2つのサンプルが同じ分布から来るかどうかを決定する新しい方法を提供する。 2つのサンプルの間に直接補間体を構築し、対称スケジュールでは、その法則が時間反射の下で不変であることを観察する。したがって、t と 1-t の辺辺が、Jensen-Shannon の発散を計算することで一致するかどうかをテストする。
論文参考訳（メタデータ） (2026-10-06T12:48:27Z)
Counterfactual Probing for Parallel Unmasking with Hidden Forest Structure [50.58119214447535]
マスク付き生成モデルは並列トークン予測を提供するが、正確な並列サンプリングはトークンを考慮しなければならない。本研究は,発見を含む全評価がシーケンス長$N$のサブ線形であるかどうかを考察する。本研究では, 森林構造を隠蔽した離散分布を, 固定された近似条件オラクルを通してアクセスする。
論文参考訳（メタデータ） (2026-09-29T15:39:50Z)
On the Power of Adaptivity in Testing Quantum States in Fidelity [11.9849496670021]
本稿では,量子状態認証,等価性試験,独立性試験の問題点について検討する。証明において、未知の量子状態のサンプル$$が与えられた場合、ゴールは$=$か、または$$$と$$が与えられた距離測度において遥かに遠いかどうかをテストすることである。同値テストでは、$は未知であり、サンプルを通してのみアクセス可能である。
論文参考訳（メタデータ） (2026-09-08T13:30:06Z)
A complete characterization of sequential testability and change detectability in i.i.d. models [42.75529349751914]
あらゆる代替品に対してパワー 1 のレベル-() テストが存在するのは、その代替品が有限ブロック事象の可算族によってヌルから分離されているときである。実際に同じ条件は、オプションの水平平均ラン長制御の下での変更検出可能性も特徴付ける。
論文参考訳（メタデータ） (2026-09-04T22:11:07Z)
Hypothesis Testing with Conditional Queries: Learnability and the Value of Interaction [0.0]
学習容易性は、2つのクラスが2つの条件付き確率で正の分離を持つ場合にのみ成立することを示す。一定の適応的なクエリ複雑性と$_varepsilon(N2)$非適応的なクエリ複雑性を持つマッチングファミリを構築する。
論文参考訳（メタデータ） (2026-08-06T16:54:10Z)
Sample Complexity of Multicalibration for Multilevel Properties [52.27687531970317]
我々は、前のプロパティが固定されたときに各プロパティが識別可能な$k$プロパティの列に対する多重校正について検討する。多対数的に多くの二元群が存在するにもかかわらず、多重校正誤差$varepsilon$を達成するには$widetilde(varepsilon-(k+2))$サンプルが必要である。
論文参考訳（メタデータ） (2026-08-04T23:38:54Z)
Entropy Equivalence Testing [43.089793195592115]
本稿では,確率分布のエンヘントロピー同値検定の問題を紹介する。この課題に対する最適なサンプルの複雑さは、クローズネステストよりも著しく低いことを示します。我々はこの結果を利用して、低次EmphBayesianネットワークの(標準)クローズネスに対する最初の非自明なテストアルゴリズムを提供する。
論文参考訳（メタデータ） (2026-05-22T04:35:04Z)
High-accuracy log-concave sampling with stochastic queries [70.90863485771405]
サブエクスフォデンシャルテールの繰り返し勾配を用いて,ログコンケーブサンプリングの精度保証が達成可能であることを示す。また、このフレームワークは、0番目の順序(値)クエリの下でも、同様の高精度な保証を提供する。
論文参考訳（メタデータ） (2026-02-15T23:19:07Z)
Permutation tests for quantum state identity [0.0]
n$未知の量子状態が等しいか不等であるかを決定する問題は、量子状態アイデンティティ問題として知られている。置換テストはこのタスクに最適であることが知られており、2つの入力状態に対してはよく知られたスワップテストと一致する。この研究は、量子状態のアイデンティティ問題(きめ細かい定式化)の基盤となる構造を捉えようとする。
論文参考訳（メタデータ） (2024-05-15T18:00:07Z)
Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文参考訳（メタデータ） (2020-09-14T16:09:17Z)

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