論文の概要: 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つを境界度ベイズネットに拡張します。
関連論文リスト
- Tester-Learners for Halfspaces: Universal Algorithms [13.13131953359806]
広範に構造化された分布に対して普遍的に成功するハーフ空間に対して、最初のテスタ・ラーナーを与える。
学習者はラベル付きディストリビューションでエラー$mathrmopt + epsilon$を達成します。
論文 参考訳(メタデータ) (2023-05-19T15:52:06Z) - Stochastic Approximation Approaches to Group Distributionally Robust
Optimization [96.26317627118912]
群分散ロバスト最適化(GDRO)
オンライン学習技術は、各ラウンドに必要なサンプル数をm$から1$に減らし、同じサンプルを保持する。
分布依存収束率を導出できる重み付きGDROの新規な定式化。
論文 参考訳(メタデータ) (2023-02-18T09:24:15Z) - On-Demand Sampling: Learning Optimally from Multiple Distributions [87.09946206044332]
社会的・現実世界の考察は、協調的、集団的分布的堅牢性、公正な連合学習など、多分野の学習パラダイムを生み出している。
本稿では、これらの学習パラダイムの最適なサンプル複雑性を確立し、このサンプル複雑性を満たすアルゴリズムを提供する。
私たちのアルゴリズムの設計と分析は、プレイヤーの安価なワンオフサンプルやより高価な再利用可能なサンプルへのアクセスをトレードオフできるミラー・ダイスンの拡張によって実現されます。
論文 参考訳(メタデータ) (2022-10-22T19:07:26Z) - Identity Testing for High-Dimensional Distributions via Entropy
Tensorization [4.370097023410272]
我々は,n$次元分布の同一性テスト問題に対して,改良されたアルゴリズムと,統計的および計算的下界の整合性を示す。
同一性テスト問題では、明示的な分布 $mu$, $varepsilon>0$, and access to a sample oracle for a hidden distribution $pi$ が与えられる。
エントロピーの近似テンソル化として知られる解析的性質が可視分布の$mu$に対して成り立つならば、$tildeO(n/vareps)を使用する隠された$pi$に対して効率的なアイデンティティテストアルゴリズムが存在することを証明している。
論文 参考訳(メタデータ) (2022-07-19T06:49:24Z) - 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) - Testing Determinantal Point Processes [0.0]
配電体の特性試験という新たな視点からDPPについて検討する。
DPPをテストするための最初のアルゴリズムを提案する。
より一般的な対数-部分モジュラ分布のクラスをテストする問題に対して、新しい硬度結果を示す。
論文 参考訳(メタデータ) (2020-08-09T04:45:16Z) - Downsampling for Testing and Learning in Product Distributions [24.48103093661132]
未知確率分布が $mathbbRd$ 上の積分布であるような分布自由なプロパティテストと学習問題について検討する。
ハーフスペースの交叉、しきい値関数、凸集合、および$k$交互関数などの多くの重要な関数のクラスでは、既知のアルゴリズムは、分布のサポートサイズに依存する複雑さを持つ。
本稿では,これらの問題を解消する一般手法として,ダウンログ(downlog)を提案する。
論文 参考訳(メタデータ) (2020-07-15T02:46:44Z) - Quantum Communication Complexity of Distribution Testing [114.31181206328276]
2人のプレーヤーが1つのディストリビューションから$t$のサンプルを受け取ります。
目標は、2つの分布が等しいか、または$epsilon$-far であるかどうかを決定することである。
この問題の量子通信複雑性が$tildeO$(tepsilon2)$ qubitsであることを示す。
論文 参考訳(メタデータ) (2020-06-26T09:05:58Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳(メタデータ) (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト(すべての情報・翻訳含む)の品質を保証せず、本サイト(すべての情報・翻訳含む)を使用して発生したあらゆる結果について一切の責任を負いません。