論文の概要: Phase Transitions in the Detection of Correlated Databases
- arxiv url: http://arxiv.org/abs/2302.03380v2
- Date: Thu, 4 May 2023 06:19:51 GMT
- ステータス: 処理完了
- システム内更新日: 2023-05-05 19:01:00.568317
- Title: Phase Transitions in the Detection of Correlated Databases
- Title（参考訳）: 相関データベース検出における位相遷移
- Authors: Dor Elimelech and Wasim Huleihel
- Abstract要約: 本稿では,2つのガウスデータベースの相関関係を$mathsfXinmathbbRntimes d$と$mathsfYntimes d$で検出する問題について検討する。
この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
- 参考スコア（独自算出の注目度）: 12.010807505655238
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We study the problem of detecting the correlation between two Gaussian
databases $\mathsf{X}\in\mathbb{R}^{n\times d}$ and $\mathsf{Y}^{n\times d}$,
each composed of $n$ users with $d$ features. This problem is relevant in the
analysis of social media, computational biology, etc. We formulate this as a
hypothesis testing problem: under the null hypothesis, these two databases are
statistically independent. Under the alternative, however, there exists an
unknown permutation $\sigma$ over the set of $n$ users (or, row permutation),
such that $\mathsf{X}$ is $\rho$-correlated with $\mathsf{Y}^\sigma$, a
permuted version of $\mathsf{Y}$. We determine sharp thresholds at which
optimal testing exhibits a phase transition, depending on the asymptotic regime
of $n$ and $d$. Specifically, we prove that if $\rho^2d\to0$, as $d\to\infty$,
then weak detection (performing slightly better than random guessing) is
statistically impossible, irrespectively of the value of $n$. This compliments
the performance of a simple test that thresholds the sum all entries of
$\mathsf{X}^T\mathsf{Y}$. Furthermore, when $d$ is fixed, we prove that strong
detection (vanishing error probability) is impossible for any
$\rho<\rho^\star$, where $\rho^\star$ is an explicit function of $d$, while
weak detection is again impossible as long as $\rho^2d\to0$. These results
close significant gaps in current recent related studies.
- Abstract（参考訳）: 2つのガウスデータベース間の相関を検知する問題について検討する。 $\mathsf{x}\in\mathbb{r}^{n\times d}$と$\mathsf{y}^{n\times d}$であり、それぞれが$d$の機能を持つ$n$ユーザで構成されている。
この問題は、ソーシャルメディア、計算生物学などの分析に関係している。
null仮説では、これらの2つのデータベースは統計的に独立しています。
しかし、この代替案の下では、$n$ ユーザ(または行の置換)の集合の上に、未知の置換 $\sigma$ が存在し、$\mathsf{x}$ は$\mathsf{y}^\sigma$、$\mathsf{y}$ の置換版である$\mathsf{y}^\sigma$ と関連している。
最適試験が相転移を示すシャープしきい値を決定する。
具体的には、$\rho^2d\to0$ を$d\to\infty$ とすると、弱い検出(ランダムな推測よりもわずかに良い)は統計的に不可能である。
これは、$\mathsf{X}^T\mathsf{Y}$の全てのエントリを閾値付けする単純なテストのパフォーマンスを補完する。
さらに、$d$を固定すると、$\rho<\rho^\star$は$d$の明示的な関数であり、$\rho^2d\to0$の弱い検出は$\rho^2d\to0$の限り再び不可能である。
これらの結果は最近の研究で大きなギャップを埋めている。
関連論文リスト
- Guarantees for Nonlinear Representation Learning: Non-identical Covariates, Dependent Data, Fewer Samples [24.45016514352055]
我々は、関数クラス$mathcal F times Mathcal G$から、T+1$関数$f_star(t) circ g_star$を学習する際のサンプル複雑度について研究する。
タスク数が$T$になるにつれて、サンプル要件とリスクバウンドの両方が$r$次元回帰に収束することを示す。
論文 参考訳（メタデータ） (2024-10-15T03:20:19Z) - 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 Dependency of Unlabeled Databases [5.384630221560811]
2つのランダムデータベース $mathsfXinmathcalXntimes d$ と $mathsfYinmathcalYntimes d$ は統計的に依存するかどうかによって異なる。
最適テストが情報理論上不可能かつ可能なしきい値の特徴付けを行う。
論文 参考訳（メタデータ） (2023-11-10T05:17:03Z) - Statistical Learning under Heterogeneous Distribution Shift [71.8393170225794]
ground-truth predictor is additive $mathbbE[mathbfz mid mathbfx,mathbfy] = f_star(mathbfx) +g_star(mathbfy)$.
論文 参考訳（メタデータ） (2023-02-27T16:34:21Z) - 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) - Threshold Phenomena in Learning Halfspaces with Massart Noise [56.01192577666607]
ガウス境界の下でのマスアートノイズ付きmathbbRd$におけるPAC学習ハーフスペースの問題について検討する。
この結果は,Massartモデルにおける学習ハーフスペースの複雑さを定性的に特徴づけるものである。
論文 参考訳（メタデータ） (2021-08-19T16:16:48Z) - Mediated Uncoupled Learning: Learning Functions without Direct
Input-output Correspondences [80.95776331769899]
ペア化されたデータがない場合、$X$から$Y$を予測するタスクを考えます。
単純なアプローチは、$S_X$で$U$から$U$を予測し、$S_Y$で$U$から$Y$を予測することである。
我々は$U$を予測しない新しい方法を提案するが、$f(X)$と$S_X$をトレーニングすることで$Y = f(X)$を直接学習し、$h(U)$を予測する。
論文 参考訳（メタデータ） (2021-07-16T22:13:29Z) - Optimal Spectral Recovery of a Planted Vector in a Subspace [80.02218763267992]
我々は、$ell_4$ノルムが同じ$ell$ノルムを持つガウスベクトルと異なるプラントベクトル$v$の効率的な推定と検出について研究する。
規則$n rho gg sqrtN$ では、大クラスのスペクトル法(そしてより一般的には、入力の低次法)は、植込みベクトルの検出に失敗する。
論文 参考訳（メタデータ） (2021-05-31T16:10:49Z) - The Sparse Hausdorff Moment Problem, with Application to Topic Models [5.151973524974052]
我々は$m=2k$iid二進確率変数のサンプルを用いて$k$-mixtureを同定するアルゴリズムを提案する。
加法精度$w_mincdotzetaO(k)$のモーメントを知るだけで十分である。
論文 参考訳（メタデータ） (2020-07-16T04:23:57Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z) - Agnostic Q-learning with Function Approximation in Deterministic
Systems: Tight Bounds on Approximation Error and Sample Complexity [94.37110094442136]
本稿では,決定論的システムにおける関数近似を用いたQ$学習の問題について検討する。
もし$delta = Oleft(rho/sqrtdim_Eright)$なら、$Oleft(dim_Eright)$を使って最適なポリシーを見つけることができる。
論文 参考訳（メタデータ） (2020-02-17T18:41:49Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。