論文の概要: Testing Product Distributions: A Closer Look
- arxiv url: http://arxiv.org/abs/2012.14632v1
- Date: Tue, 29 Dec 2020 07:02:32 GMT
- ステータス: 処理完了
- システム内更新日: 2021-04-18 20:27:12.596301
- Title: Testing Product Distributions: A Closer Look
- Title(参考訳): 製品配布をテストする - 詳しく見て
- Authors: Arnab Bhattacharyya, Sutanu Gayen, Saravanan Kandasamy, N. V.
Vinodchandran
- Abstract要約: 私たちは、$n$次元製品分布のアイデンティティと近接性テストの問題を研究します。
私たちの研究は、耐性試験のサンプルの複雑さが製品分布の距離測定とどのように異なるか、きめ細かい理解を与えます。
- 参考スコア(独自算出の注目度): 14.104329627455893
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problems of identity and closeness testing of $n$-dimensional
product distributions. Prior works by Canonne, Diakonikolas, Kane and Stewart
(COLT 2017) and Daskalakis and Pan (COLT 2017) have established tight sample
complexity bounds for non-tolerant testing over a binary alphabet: given two
product distributions $P$ and $Q$ over a binary alphabet, distinguish between
the cases $P = Q$ and $d_{\mathrm{TV}}(P, Q) > \epsilon$. We build on this
prior work to give a more comprehensive map of the complexity of testing of
product distributions by investigating tolerant testing with respect to several
natural distance measures and over an arbitrary alphabet. Our study gives a
fine-grained understanding of how the sample complexity of tolerant testing
varies with the distance measures for product distributions. In addition, we
also extend one of our upper bounds on product distributions to bounded-degree
Bayes nets.
- Abstract(参考訳): 我々は,n$-dimensional 製品分布の同一性と密接性テストの問題点について検討する。
Canonne, Diakonikolas, Kane and Stewart (COLT 2017) と Daskalakis and Pan (COLT 2017) による以前の研究は、バイナリアルファベット上での非耐性テストのための厳密なサンプル複雑性境界を確立した: バイナリアルファベット上での2つの積分布$P$と$Q$が与えられた場合、$P = Q$と$d_{\mathrm{TV}}(P, Q) > \epsilon$。
この先行研究に基づいて、いくつかの自然距離測度および任意のアルファベット上での耐久試験を調査することにより、製品分布のテストの複雑さのより包括的なマップを提供する。
本研究は, 耐久試験における試料の複雑さが, 製品分布の距離測定値とどのように異なるか, 詳細に把握する。
さらに、製品分布の上限の1つを境界度ベイズネットに拡張します。
関連論文リスト
- Sharp Constants in Uniformity Testing via the Huber Statistic [16.384142529375435]
一様性テスト(英: Uniformity testing)は、プロパティテストにおいて最もよく研究されている問題の1つである。
1-デルタ確率を持つ任意の$epsilon$-far分布と$m$要素上の均一分布を区別する最適なサンプル複雑性は$nであることが知られている。
衝突試験機は, 均一入力と非一様入力の分離の標準偏差数において, 急激な最大定数を達成することを示す。
論文 参考訳(メタデータ) (2022-06-21T20:43:53Z) - Optimal SQ Lower Bounds for Robustly Learning Discrete Product
Distributions and Ising Models [45.14286976373306]
我々は、離散的な高次元分布の特定の族をしっかりと学習するために、最適な統計的クエリー(SQ)の下位境界を確立する。
我々のSQローバウンドは、これらの問題に対する既知のアルゴリズムのエラー保証と一致し、これらのタスクの現在の上限が最善であることを示す。
論文 参考訳(メタデータ) (2022-06-09T16:10:23Z) - Robust Sparse Mean Estimation via Sum of Squares [48.07596965953344]
本研究では,高次元スパース平均推定の問題点を,逆数外乱の$epsilon$-fractionの存在下で検討する。
我々のアルゴリズムは、サム・オブ・スクエア(Sum-of-Squares)ベースのアルゴリズムアプローチに従う。
論文 参考訳(メタデータ) (2022-06-07T16:49:54Z) - Communication-constrained hypothesis testing: Optimality, robustness,
and reverse data processing inequalities [6.939768185086755]
通信制約下での単純な二項仮説テストのサンプルの複雑さは、少なくとも制約のない設定よりも大きい対数係数であることが示される。
我々のフレームワークは、分布が全変動距離で破壊されるような頑健な仮説テストにまで拡張する。
論文 参考訳(メタデータ) (2022-06-06T17:42:11Z) - Exact Paired-Permutation Testing for Structured Test Statistics [67.71280539312536]
構造化されたテスト統計群のペア置換テストに対して,効率的な正確なアルゴリズムを提案する。
我々の正確なアルゴリズムはモンテカルロ近似よりも10ドル速く、共通のデータセットに20000ドルのサンプルがある。
論文 参考訳(メタデータ) (2022-05-03T11:00:59Z) - Independence Testing for Bounded Degree Bayesian Network [4.230271396864461]
P$ がスパース構造を持つならば、実際、多くのサンプルしか必要としないことを示す。
また、もし$P$が、基礎となるDAGが$d$で有界なベイズネットワークに対してマルコフであるなら、$tildeTheta (2d/2cdot n/varepsilon2)$サンプルが必要であることも示している。
論文 参考訳(メタデータ) (2022-04-19T06:16:14Z) - Testing distributional assumptions of learning algorithms [5.204779946147061]
テストレーナー対 $(mathcalA,mathcalT)$ の設計について検討する。
データ中の例の分布がテスタを$mathcalT$に渡せば、データ上の非依存な$mathcalA$の出力を安全に信頼できることを示す。
論文 参考訳(メタデータ) (2022-04-14T19:10:53Z) - Robust Learning of Optimal Auctions [84.13356290199603]
本研究では、入札者の評価値のサンプルを逆向きに破損させたり、逆向きに歪んだ分布から引き出すことができる場合に、サンプルから収益-最適マルチバイダオークションを学習する問題について検討する。
我々は,コルモゴロフ-スミルノフ距離における元の分布に対して$alpha$-closeの「全ての真の分布」に対して,収入がほぼ同時に最適であるメカニズムを学習できる新しいアルゴリズムを提案する。
論文 参考訳(メタデータ) (2021-07-13T17:37:21Z) - Tightening the Dependence on Horizon in the Sample Complexity of
Q-Learning [59.71676469100807]
この研究は、同期Q-ラーニングのサンプルの複雑さを、任意の$0varepsilon 1$に対して$frac|mathcalS| (1-gamma)4varepsilon2$の順序に絞る。
計算やストレージを余分に必要とせずに、高速なq-learningにマッチするvanilla q-learningの有効性を明らかにした。
論文 参考訳(メタデータ) (2021-02-12T14:22:05Z) - The Sample Complexity of Robust Covariance Testing [56.98280399449707]
i. i. d.
形式 $Z = (1-epsilon) X + epsilon B$ の分布からのサンプル。ここで $X$ はゼロ平均で未知の共分散である Gaussian $mathcalN(0, Sigma)$ である。
汚染がない場合、事前の研究は、$O(d)$サンプルを使用するこの仮説テストタスクの単純なテスターを与えた。
サンプル複雑性の上限が $omega(d2)$ for $epsilon$ an arbitrarily small constant and $gamma であることを証明します。
論文 参考訳(メタデータ) (2020-12-31T18:24:41Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。