論文の概要: Better and Simpler Lower Bounds for Differentially Private Statistical
Estimation
- arxiv url: http://arxiv.org/abs/2310.06289v2
- Date: Thu, 4 Jan 2024 07:36:29 GMT
- ステータス: 処理完了
- システム内更新日: 2024-01-05 17:06:07.276260
- Title: Better and Simpler Lower Bounds for Differentially Private Statistical
Estimation
- Title（参考訳）: 微分プライベート統計量推定のための改良と簡易化
- Authors: Shyam Narayanan
- Abstract要約: 任意の$alpha le O(1)$に対して、ガウスの共分散をスペクトル誤差まで推定するには$tildeOmegaleft(fracd3/2alpha varepsilon + fracdalpha2right)$サンプルが必要である。
次に、有界な$k$thモーメントで重み付き分布の平均を推定するには$tildeOmegaleft(fracdalphak/(k-1) varepsilon +
- 参考スコア（独自算出の注目度）: 7.693388437377614
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: We provide optimal lower bounds for two well-known parameter estimation (also
known as statistical estimation) tasks in high dimensions with approximate
differential privacy. First, we prove that for any $\alpha \le O(1)$,
estimating the covariance of a Gaussian up to spectral error $\alpha$ requires
$\tilde{\Omega}\left(\frac{d^{3/2}}{\alpha \varepsilon} +
\frac{d}{\alpha^2}\right)$ samples, which is tight up to logarithmic factors.
This result improves over previous work which established this for $\alpha \le
O\left(\frac{1}{\sqrt{d}}\right)$, and is also simpler than previous work.
Next, we prove that estimating the mean of a heavy-tailed distribution with
bounded $k$th moments requires $\tilde{\Omega}\left(\frac{d}{\alpha^{k/(k-1)}
\varepsilon} + \frac{d}{\alpha^2}\right)$ samples. Previous work for this
problem was only able to establish this lower bound against pure differential
privacy, or in the special case of $k = 2$.
Our techniques follow the method of fingerprinting and are generally quite
simple. Our lower bound for heavy-tailed estimation is based on a black-box
reduction from privately estimating identity-covariance Gaussians. Our lower
bound for covariance estimation utilizes a Bayesian approach to show that,
under an Inverse Wishart prior distribution for the covariance matrix, no
private estimator can be accurate even in expectation, without sufficiently
many samples.
- Abstract（参考訳）: 近似微分プライバシーを持つ高次元の2つのよく知られたパラメータ推定(統計的推定とも呼ばれる)タスクに対して最適な下界を提供する。
まず、任意の$\alpha \le O(1)$に対して、ガウスの共分散をスペクトル誤差まで推定するには$\tilde{\Omega}\left(\frac{d^{3/2}}{\alpha \varepsilon} + \frac{d}{\alpha^2}\right)$サンプルが必要である。
この結果は、$\alpha \le o\left(\frac{1}{\sqrt{d}}\right)$という従来の仕事よりも改善され、また以前の仕事よりも単純である。
次に、有界な$k$thモーメントで重み付き分布の平均を推定するには、$\tilde{\Omega}\left(\frac{d}{\alpha^{k/(k-1)} \varepsilon} + \frac{d}{\alpha^2}\right)$サンプルが必要であることを証明する。
この問題に対する以前の研究は、純粋な差分プライバシーに対して、あるいは特別な場合、$k = 2$に対して、この低い境界を確立することしかできなかった。
我々の技術は指紋認証の手法に従っており、概して非常に単純である。
重み付き推定の低い境界は、個人的同一性共分散ガウスのブラックボックス削減に基づいている。
共分散行列に対する逆ウィッシュアート事前分布の下では、十分多くのサンプルを使わずに、期待してもプライベートな推定器が正確ではないことをベイズ法を用いて証明する。
関連論文リスト
- Dimension-free Private Mean Estimation for Anisotropic Distributions [55.86374912608193]
以前の$mathRd上の分布に関する民間推定者は、次元性の呪いに苦しむ。
本稿では,サンプルの複雑さが次元依存性を改善したアルゴリズムを提案する。
論文 参考訳（メタデータ） (2024-11-01T17:59:53Z) - Sum-of-squares lower bounds for Non-Gaussian Component Analysis [33.80749804695003]
非ガウス成分分析(Non-Gaussian Component Analysis、NGCA)は、高次元データセットにおいて非ガウス方向を求める統計的タスクである。
本稿では Sum-of-Squares フレームワークにおける NGCA の複雑さについて考察する。
論文 参考訳（メタデータ） (2024-10-28T18:19:13Z) - $L^1$ Estimation: On the Optimality of Linear Estimators [64.76492306585168]
この研究は、条件中央値の線型性を誘導する$X$上の唯一の先行分布がガウス分布であることを示している。
特に、条件分布 $P_X|Y=y$ がすべての$y$に対して対称であるなら、$X$ はガウス分布に従う必要がある。
論文 参考訳（メタデータ） (2023-09-17T01:45:13Z) - Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance
Estimation for Subgaussian Distributions [8.40077201352607]
我々は,高次元共分散認識平均推定のための高速,微分プライベートなアルゴリズムを提案する。
我々のアルゴリズムは$tildemu$を生成し、$|mu|_Sigma leq alpha$が$n gtrsim tfrac d alpha2 + tfracd sqrtlog 1/deltaalpha varepsilon+fracdlog 1/deltavarepsilon$である。
論文 参考訳（メタデータ） (2023-01-28T16:57:46Z) - New Lower Bounds for Private Estimation and a Generalized Fingerprinting
Lemma [10.176795938619417]
統計的推定タスクの新たな下限を$(varepsilon, delta)$-differential privacyの制約の下で証明する。
フロベニウスノルムの推定には$Omega(d2)$サンプルが必要であり、スペクトルノルムでは$Omega(d3/2)$サンプルが必要である。
論文 参考訳（メタデータ） (2022-05-17T17:55:10Z) - Covariance-Aware Private Mean Estimation Without Private Covariance Estimation [10.036088581191592]
2つのサンプル係数差分プライベート平均推定器を$d$-dimensional(sub)Gaussian分布に対して提案する。
我々の推定子は、$| tildemu - mu |_Sigma leq alpha$, where $| cdot |_Sigma$がマハラノビス距離であるような$tildemu$を出力します。
論文 参考訳（メタデータ） (2021-06-24T21:40:07Z) - 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 Mean Estimation without a Variance [103.26777953032537]
本研究では,データ生成分布の分散が存在しない環境での重み付き平均推定問題について検討する。
最小の信頼区間を$n,d,delta$の関数として得る推定器を設計する。
論文 参考訳（メタデータ） (2020-11-24T22:39:21Z) - Consistent regression when oblivious outliers overwhelm [8.873449722727026]
我々の研究に先立ち、ガウスの$X$でさえ、$beta*$ の見積子は、このモデルでは一貫性がないことが知られていた。
ほぼ線形なサンプルサイズと逆ポリノミアル不整分率で一貫した推定が可能であることを示す。
ここで研究したモデルは、最初の瞬間さえも持たない重い尾の雑音の分布も捉えている。
論文 参考訳（メタデータ） (2020-09-30T16:21:34Z) - Optimal Robust Linear Regression in Nearly Linear Time [97.11565882347772]
学習者が生成モデル$Y = langle X,w* rangle + epsilon$から$n$のサンプルにアクセスできるような高次元頑健な線形回帰問題について検討する。
i) $X$ is L4-L2 hypercontractive, $mathbbE [XXtop]$ has bounded condition number and $epsilon$ has bounded variance, (ii) $X$ is sub-Gaussian with identity second moment and $epsilon$ is
論文 参考訳（メタデータ） (2020-07-16T06:44:44Z) - Locally Private Hypothesis Selection [96.06118559817057]
我々は、$mathcalQ$から$p$までの総変動距離が最良の分布に匹敵する分布を出力する。
局所的な差分プライバシーの制約は、コストの急激な増加を引き起こすことを示す。
提案アルゴリズムは,従来手法のラウンド複雑性を指数関数的に改善する。
論文 参考訳（メタデータ） (2020-02-21T18:30:48Z)
関連論文リストは本サイト内にある論文のタイトル・アブストラクトから自動的に作成しています。
指定された論文の情報です。
本サイトの運営者は本サイト（すべての情報・翻訳含む）の品質を保証せず、本サイト（すべての情報・翻訳含む）を使用して発生したあらゆる結果について一切の責任を負いません。