論文の概要: 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)$サンプルは独立テストに必要で十分である。
関連論文リスト
- 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) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳（メタデータ） (2023-02-18T09:24:15Z) - Near-Optimal Bounds for Testing Histogram Distributions [35.18069719489173]
ヒストグラム検査問題はサンプル複雑性$widetilde Theta (sqrtnk / varepsilon + k / varepsilon2 + sqrtn / varepsilon2)$であることを示す。
論文 参考訳（メタデータ） (2022-07-14T01:24:01Z) - Nonasymptotic one-and two-sample tests in high dimension with unknown
covariance structure [0.0]
テストの問題は、$mu が 0 に対して $eta-閉である場合、すなわち $|mu| geq (eta + delta)$ に対して $|mu| leq eta である。
本研究の目的は,I型とII型の両方の誤差を所定のレベルで制御できるように,最小分離距離$の漸近的上下境界を求めることである。
論文 参考訳（メタデータ） (2021-09-01T06:22:53Z) - The Price of Tolerance in Distribution Testing [31.10049510641336]
サンプルの複雑さは [fracsqrtnvarepsilon2 + fracnlog n cdotmaxleftfracvarepsilon2 であることが示され、この2つの既知事例の間に円滑なトレードオフをもたらす。
また、p$ と$q$ の両方が未知である寛容同値検定の問題についても同様の特徴を与える。
論文 参考訳（メタデータ） (2021-06-25T03:59:42Z) - 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) - Curse of Dimensionality on Randomized Smoothing for Certifiable
Robustness [151.67113334248464]
我々は、他の攻撃モデルに対してスムースな手法を拡張することは困難であることを示す。
我々はCIFARに関する実験結果を示し,その理論を検証した。
論文 参考訳（メタデータ） (2020-02-08T22:02:14Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。