論文の概要: Testing Closeness of Multivariate Distributions via Ramsey Theory
- arxiv url: http://arxiv.org/abs/2311.13154v1
- Date: Wed, 22 Nov 2023 04:34:09 GMT
- ステータス: 処理完了
- システム内更新日: 2023-11-23 16:05:54.834461
- Title: Testing Closeness of Multivariate Distributions via Ramsey Theory
- Title（参考訳）: ラムゼー理論による多変量分布の近接性検証
- Authors: Ilias Diakonikolas, Daniel M. Kane, Sihan Liu
- Abstract要約: 多次元分布に対する近接性(あるいは等価性)検定の統計的課題について検討する。
具体的には、$mathbf p, mathbf q$ on $mathbb Rd$ に対して、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ の2つの未知の分布へのサンプルアクセスが与えられると、$mathbf p=mathbf q$ と $|mathbf p-mathbf q|_A_k > epsilon$ を区別する。
本研究の主な成果は,任意の固定次元におけるサブラーニングサンプルの複雑性を考慮に入れた,この問題に対する最初のクローズネステスタである。
- 参考スコア（独自算出の注目度）: 40.926523210945064
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We investigate the statistical task of closeness (or equivalence) testing for
multidimensional distributions. Specifically, given sample access to two
unknown distributions $\mathbf p, \mathbf q$ on $\mathbb R^d$, we want to
distinguish between the case that $\mathbf p=\mathbf q$ versus $\|\mathbf
p-\mathbf q\|_{A_k} > \epsilon$, where $\|\mathbf p-\mathbf q\|_{A_k}$ denotes
the generalized ${A}_k$ distance between $\mathbf p$ and $\mathbf q$ --
measuring the maximum discrepancy between the distributions over any collection
of $k$ disjoint, axis-aligned rectangles. Our main result is the first
closeness tester for this problem with {\em sub-learning} sample complexity in
any fixed dimension and a nearly-matching sample complexity lower bound.
In more detail, we provide a computationally efficient closeness tester with
sample complexity $O\left((k^{6/7}/ \mathrm{poly}_d(\epsilon))
\log^d(k)\right)$. On the lower bound side, we establish a qualitatively
matching sample complexity lower bound of
$\Omega(k^{6/7}/\mathrm{poly}(\epsilon))$, even for $d=2$. These sample
complexity bounds are surprising because the sample complexity of the problem
in the univariate setting is $\Theta(k^{4/5}/\mathrm{poly}(\epsilon))$. This
has the interesting consequence that the jump from one to two dimensions leads
to a substantial increase in sample complexity, while increases beyond that do
not.
As a corollary of our general $A_k$ tester, we obtain $d_{\mathrm
TV}$-closeness testers for pairs of $k$-histograms on $\mathbb R^d$ over a
common unknown partition, and pairs of uniform distributions supported on the
union of $k$ unknown disjoint axis-aligned rectangles.
Both our algorithm and our lower bound make essential use of tools from
Ramsey theory.
- Abstract（参考訳）: 多次元分布に対する近接性(あるいは同値性)検定の統計的タスクについて検討する。
具体的には、2つの未知分布へのサンプルアクセスが$\mathbf p, \mathbf q$ on $\mathbb R^d$の場合、$\mathbf p=\mathbf q$ vs $\|\mathbf p-\mathbf q\|_{A_k} > \epsilon$, where $\|\mathbf p-\mathbf q\|_{A_k}$は、$\mathbf p$と$\mathbf q$の間の一般化された${A}_k$距離を表す。
我々の主な成果は、任意の固定次元におけるサンプルの複雑さと、ほぼ一致するサンプルの複雑さを下限とするこの問題に対する最初のクローズネステスターである。
より詳しくは、サンプル複雑性$O\left((k^{6/7}/ \mathrm{poly}_d(\epsilon)) \log^d(k)\right)$の計算効率の良いクローズネステスタを提供する。
下界側では、$d=2$であっても$\Omega(k^{6/7}/\mathrm{poly}(\epsilon))$の定性的に一致するサンプル複雑性の下界を確立する。
これらのサンプル複雑性境界は、不定値設定における問題のサンプル複雑性が$\theta(k^{4/5}/\mathrm{poly}(\epsilon))$であるので驚きである。
これは、1次元から2次元へのジャンプがサンプルの複雑さを大幅に増加させる一方、それ以上の増加はしないという興味深い結果をもたらす。
一般的な $a_k$ テスターの仲間として、共通の未知の分割で$\mathbb r^d$ 上の$k$-histogram のペアに対して $d_{\mathrm tv}$-closeness テスターと、$k$ 未知の軸整合長方形の組み合わせでサポートされている一対の均一分布を得る。
我々のアルゴリズムと下界の両方がラムゼー理論のツールを必須に利用している。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Provably learning a multi-head attention layer [55.2904547651831]
マルチヘッドアテンション層は、従来のフィードフォワードモデルとは分離したトランスフォーマーアーキテクチャの重要な構成要素の1つである。
本研究では,ランダムな例から多面的注意層を実証的に学習する研究を開始する。
最悪の場合、$m$に対する指数的依存は避けられないことを示す。
論文 参考訳（メタデータ） (2024-02-06T15:39:09Z) - SQ Lower Bounds for Learning Mixtures of Linear Classifiers [43.63696593768504]
この問題に対する既知のアルゴリズムは、一様混合の特別な場合であっても、本質的には最善であることを示す。
重要な技術的要素は、独立した関心を持つかもしれない球面設計の新たな構築である。
論文 参考訳（メタデータ） (2023-10-18T10:56:57Z) - Near-Optimal Bounds for Learning Gaussian Halfspaces with Random
Classification Noise [50.64137465792738]
この問題に対する効率的なSQアルゴリズムは、少なくとも$Omega(d1/2/(maxp, epsilon)2)$. のサンプル複雑性を必要とする。
我々の下限は、この1/epsilon$に対する二次的依存は、効率的なアルゴリズムに固有のものであることを示唆している。
論文 参考訳（メタデータ） (2023-07-13T18:59:28Z) - Near-Optimal Bounds for Testing Histogram Distributions [35.18069719489173]
ヒストグラム検査問題はサンプル複雑性$widetilde Theta (sqrtnk / varepsilon + k / varepsilon2 + sqrtn / varepsilon2)$であることを示す。
論文 参考訳（メタデータ） (2022-07-14T01:24:01Z) - Learning a Single Neuron with Adversarial Label Noise via Gradient
Descent [50.659479930171585]
モノトン活性化に対する $mathbfxmapstosigma(mathbfwcdotmathbfx)$ の関数について検討する。
学習者の目標は仮説ベクトル $mathbfw$ that $F(mathbbw)=C, epsilon$ を高い確率で出力することである。
論文 参考訳（メタデータ） (2022-06-17T17:55:43Z) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Statistically Near-Optimal Hypothesis Selection [33.83129262033921]
仮説選択問題に対する最適2ドルの近似学習戦略を導出する。
これは、最適な近似係数とサンプルの複雑さを同時に達成する最初のアルゴリズムである。
論文 参考訳（メタデータ） (2021-08-17T21:11:20Z) - Efficient inference of interventional distributions [13.31079561447385]
有限個の観測値から因果ベイズネットワーク内の干渉分布を効率的に推定する問題を考察する。
我々は、$mathbfY$ が任意の集合であるとき、グラフ同型問題を含む統計的ゼロ知識を持つ全ての問題が効率的なランダム化アルゴリズムを持っていなければ、$varepsilon$-close である分布の評価器を$P_bf x(mathbfY)$ に出力する効率的なアルゴリズムは存在しないことを示した。
論文 参考訳（メタデータ） (2021-07-25T02:40:01Z) - Estimation of Shortest Path Covariance Matrices [21.772761365915176]
共分散行列 $mathbfSigma in mathbbRdtimes d$ of a distribution $mathcal D$ over $mathbbRd$ given independent sample。
単に$O(sqrtD)$エントリ複雑性と$tilde O(r)を使って、標準エラーまで$mathbfSigma$を推定するための非常に単純なアルゴリズムを提供する。
論文 参考訳（メタデータ） (2020-11-19T17:37:46Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。