論文の概要: Independence Testing for Bounded Degree Bayesian Network
- arxiv url: http://arxiv.org/abs/2204.08690v1
- Date: Tue, 19 Apr 2022 06:16:14 GMT
- ステータス: 処理完了
- システム内更新日: 2022-04-20 15:24:29.286827
- Title: Independence Testing for Bounded Degree Bayesian Network
- Title（参考訳）: 有界次数ベイズネットワークの独立性検証
- Authors: Arnab Bhattacharyya, Cl\'ement L. Canonne, and Joy Qiping Yang
- Abstract要約: P$ がスパース構造を持つならば、実際、多くのサンプルしか必要としないことを示す。
また、もし$P$が、基礎となるDAGが$d$で有界なベイズネットワークに対してマルコフであるなら、$tildeTheta (2d/2cdot n/varepsilon2)$サンプルが必要であることも示している。
- 参考スコア（独自算出の注目度）: 4.230271396864461
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the following independence testing problem: given access to samples
from a distribution $P$ over $\{0,1\}^n$, decide whether $P$ is a product
distribution or whether it is $\varepsilon$-far in total variation distance
from any product distribution. For arbitrary distributions, this problem
requires $\exp(n)$ samples. We show in this work that if $P$ has a sparse
structure, then in fact only linearly many samples are required. Specifically,
if $P$ is Markov with respect to a Bayesian network whose underlying DAG has
in-degree bounded by $d$, then $\tilde{\Theta}(2^{d/2}\cdot n/\varepsilon^2)$
samples are necessary and sufficient for independence testing.
- Abstract（参考訳）: p$ over $\{0,1\}^n$ の分布からサンプルにアクセスすると、$p$ が製品分布であるかどうか、あるいは任意の製品分布からの距離の合計で$\varepsilon$-far となるかどうかを判断する。
任意の分布の場合、この問題は$\exp(n)$サンプルを必要とする。
この研究で、$P$ がスパース構造を持つならば、実際は線形に多くのサンプルしか必要としないことを示す。
具体的には、もし$P$が$d$で直交するベイズネットワークに対してマルコフであれば、$\tilde{\Theta}(2^{d/2}\cdot n/\varepsilon^2)$サンプルは独立テストに必要で十分である。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Statistical-Computational Trade-offs for Density Estimation [60.81548752871115]
幅広い種類のデータ構造に対して、それらの境界は著しく改善されないことを示す。
これは密度推定のための新しい統計計算トレードオフである。
論文 参考訳（メタデータ） (2024-10-30T15:03:33Z) - Testing Identity of Distributions under Kolmogorov Distance in Polylogarithmic Space [1.2277343096128712]
本稿では、ストリーミング設定において、空間$O(log4 varepsilon-1)$を使用するアルゴリズムを提供する。
また、私たちは9つの関連するオープンな問題を述べ、それと関連した問題への関心を喚起することを望んでいます。
論文 参考訳（メタデータ） (2024-10-29T15:24:27Z) - Outlier Robust Multivariate Polynomial Regression [27.03423421704806]
1,1]n 回 mathbbR$ は $(mathbfx_i,p(mathbfx_i)$ のうるさいバージョンである。
目標は、$hatp$を$ell_in$-distanceの$O(sigma)$を$p$から出力することである。
論文 参考訳（メタデータ） (2024-03-14T15:04:45Z) - Testing with Non-identically Distributed Samples [20.74768558932617]
本研究では,サンプルが独立に分布するが同一に分布しない設定に対して,サブ線形サンプル特性試験と推定が適用範囲について検討する。
それぞれのディストリビューションから$Theta(k/varepsilon2)$サンプルをサンプリングしても、$textbfp_mathrmavg$は、テレビ距離で$textbfp_mathrmavg$をエラー$varepsilon$内で学習するのに十分である。
論文 参考訳（メタデータ） (2023-11-19T01:25:50Z) - Efficient Sampling of Stochastic Differential Equations with Positive
Semi-Definite Models [91.22420505636006]
本稿では, ドリフト関数と拡散行列を考慮し, 微分方程式からの効率的なサンプリング問題を扱う。
1/varepsilonは$m2d log (1/varepsilon)$である。
以上の結果から,真の解がより滑らかになるにつれて,どのような凸性も必要とせず,次元の呪いを回避できることが示唆された。
論文 参考訳（メタデータ） (2023-03-30T02:50:49Z) - Near-Optimal Bounds for Testing Histogram Distributions [35.18069719489173]
ヒストグラム検査問題はサンプル複雑性$widetilde Theta (sqrtnk / varepsilon + k / varepsilon2 + sqrtn / varepsilon2)$であることを示す。
論文 参考訳（メタデータ） (2022-07-14T01:24:01Z) - 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) - Optimal Testing of Discrete Distributions with High Probability [49.19942805582874]
高確率状態に着目して離散分布を試験する問題について検討する。
一定の要素でサンプル最適である近接性および独立性テストのための最初のアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-09-14T16:09:17Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Sample Amplification: Increasing Dataset Size even when Learning is Impossible [15.864702679819544]
未知のディストリビューションから引き出されたデータである$D$が、このデータセットを増幅し、さらに大きなサンプルセットを$D$から抽出したように見えるように出力することは、どの程度まで可能か?
この問題は次のように定式化する: $left(n, n + Theta(fracnsqrtk)right)$アンプが存在するが、小さな定数全変動距離への分布を学習するには$Theta(d)$サンプルが必要である。
論文 参考訳（メタデータ） (2019-04-26T21:42:44Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。