论文标题
私人估计和广义指纹引理的新下限
New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
论文作者
论文摘要
我们证明了在$（\ Varepsilon，δ）$ - 差异隐私的约束下的统计估计任务的新范围。首先，我们为高斯分布的私人协方差估算提供紧密的下限。我们表明，估计Frobenius Norm中的协方差矩阵需要$ω（d^2）$样本，在频谱规范中需要$ω（d^{3/2}）$样本，这两种都匹配上限至对数因素。后者的结合验证了私人和非私有样品复杂性之间存在统计差距，用于高斯协方差的光谱估计。我们通过我们的主要技术贡献证明了这些界限，这是对指数家庭的指纹方法的广泛概括。此外，使用Acharya，Sun和Zhang的私人Assouad方法，我们显示了一个紧密的$ω（d/（α^2 \ varepsilon））$下限，用于估计具有界限协方差为$α$ -ERROR的平均值，以$ \ ell_2 $ distance。所有这些问题的先前已知的下限是多项式较弱或在$（\ Varepsilon，0）$差异隐私的更严格条件下保持。
We prove new lower bounds for statistical estimation tasks under the constraint of $(\varepsilon, δ)$-differential privacy. First, we provide tight lower bounds for private covariance estimation of Gaussian distributions. We show that estimating the covariance matrix in Frobenius norm requires $Ω(d^2)$ samples, and in spectral norm requires $Ω(d^{3/2})$ samples, both matching upper bounds up to logarithmic factors. The latter bound verifies the existence of a conjectured statistical gap between the private and the non-private sample complexities for spectral estimation of Gaussian covariances. We prove these bounds via our main technical contribution, a broad generalization of the fingerprinting method to exponential families. Additionally, using the private Assouad method of Acharya, Sun, and Zhang, we show a tight $Ω(d/(α^2 \varepsilon))$ lower bound for estimating the mean of a distribution with bounded covariance to $α$-error in $\ell_2$-distance. Prior known lower bounds for all these problems were either polynomially weaker or held under the stricter condition of $(\varepsilon, 0)$-differential privacy.
