Fugu-MT 論文翻訳(概要): Private High-Dimensional Hypothesis Testing

論文の概要: Private High-Dimensional Hypothesis Testing

arxiv url: http://arxiv.org/abs/2203.01537v1
Date: Thu, 3 Mar 2022 06:25:48 GMT
ステータス: 処理完了
システム内更新日: 2022-03-04 17:04:40.892175
Title: Private High-Dimensional Hypothesis Testing
Title（参考訳）: プライベート高次元仮説テスト
Authors: Shyam Narayanan
Abstract要約: 我々は高次元分布の個人性テストのための改良された差分プライベートアルゴリズムを提供する。具体的には、ある固定された$mu*$に対して$mathcalN(mu*, Sigma)$、または少なくとも$alpha$の総変動距離を持つ$mathcalN(mu*, Sigma)$に由来するかどうかをテストすることができる。
参考スコア（独自算出の注目度）: 4.133655523622441
License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
Abstract: We provide improved differentially private algorithms for identity testing of high-dimensional distributions. Specifically, for $d$-dimensional Gaussian distributions with known covariance $\Sigma$, we can test whether the distribution comes from $\mathcal{N}(\mu^*, \Sigma)$ for some fixed $\mu^*$ or from some $\mathcal{N}(\mu, \Sigma)$ with total variation distance at least $\alpha$ from $\mathcal{N}(\mu^*, \Sigma)$ with $(\varepsilon, 0)$-differential privacy, using only \[\tilde{O}\left(\frac{d^{1/2}}{\alpha^2} + \frac{d^{1/3}}{\alpha^{4/3} \cdot \varepsilon^{2/3}} + \frac{1}{\alpha \cdot \varepsilon}\right)\] samples if the algorithm is allowed to be computationally inefficient, and only \[\tilde{O}\left(\frac{d^{1/2}}{\alpha^2} + \frac{d^{1/4}}{\alpha \cdot \varepsilon}\right)\] samples for a computationally efficient algorithm. We also provide a matching lower bound showing that our computationally inefficient algorithm has optimal sample complexity. We also extend our algorithms to various related problems, including mean testing of Gaussians with bounded but unknown covariance, uniformity testing of product distributions over $\{\pm 1\}^d$, and tolerant testing. Our results improve over the previous best work of Canonne, Kamath, McMillan, Ullman, and Zakynthinou \cite{CanonneKMUZ20} for both computationally efficient and inefficient algorithms, and even our computationally efficient algorithm matches the optimal \emph{non-private} sample complexity of $O\left(\frac{\sqrt{d}}{\alpha^2}\right)$ in many standard parameter settings. In addition, our results show that, surprisingly, private identity testing of $d$-dimensional Gaussians can be done with fewer samples than private identity testing of discrete distributions over a domain of size $d$ \cite{AcharyaSZ18}, which refutes a conjectured lower bound of Canonne et al. \cite{CanonneKMUZ20}.
Abstract（参考訳）: 高次元分布の同一性検証のための微分プライベートアルゴリズムの改良を提案する。 Specifically, for $d$-dimensional Gaussian distributions with known covariance $\Sigma$, we can test whether the distribution comes from $\mathcal{N}(\mu^*, \Sigma)$ for some fixed $\mu^*$ or from some $\mathcal{N}(\mu, \Sigma)$ with total variation distance at least $\alpha$ from $\mathcal{N}(\mu^*, \Sigma)$ with $(\varepsilon, 0)$-differential privacy, using only \[\tilde{O}\left(\frac{d^{1/2}}{\alpha^2} + \frac{d^{1/3}}{\alpha^{4/3} \cdot \varepsilon^{2/3}} + \frac{1}{\alpha \cdot \varepsilon}\right)\] samples if the algorithm is allowed to be computationally inefficient, and only \[\tilde{O}\left(\frac{d^{1/2}}{\alpha^2} + \frac{d^{1/4}}{\alpha \cdot \varepsilon}\right)\] samples for a computationally efficient algorithm. また,計算効率の悪いアルゴリズムが最適なサンプル複雑性を持つことを示す。またアルゴリズムを様々な関連する問題にも拡張し、有界だが未知の共分散を持つガウス平均検定、$\{\pm 1\}^d$ の積分布の均一性検定、耐性テストなどを行う。従来の計算効率と非効率的なアルゴリズムに対するcanonne, kamath, mcmillan, ullman, zakynthinou \cite{canonnekmuz20} のベストプラクティスよりも精度が向上し,多くの標準パラメータ設定において,計算効率のよいアルゴリズムでさえ,最適な \emph{non-private} サンプル複雑性である $o\left(\frac{\sqrt{d}}{\alpha^2}\right)$ に適合する。さらに, 意外なことに, $d$-dimensional Gaussian のプライベートアイデンティティテストは, $d$ \cite{AcharyaSZ18} の領域上の離散分布のプライベートIDテストよりも少ないサンプルで行うことができる。通称「CanonneKMUZ20」。

論文の概要: Private High-Dimensional Hypothesis Testing

関連論文リスト