We prove new lower bounds for statistical estimation tasks under the constraint of $(\varepsilon, \delta)$-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 $\Omega(d^2)$ samples, and in spectral norm requires $\Omega(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 $\Omega(d/(\alpha^2 \varepsilon))$ lower bound for estimating the mean of a distribution with bounded covariance to $\alpha$-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.
翻译:我们证明了差分隐私限制下统计估计任务的新下界。首先,我们提供了对高斯分布私有协方差估计的紧密下界。我们证明在弗罗贝尼乌斯范数意义下,协方差矩阵的估计需要 $\Omega(d^2)$ 个样本,在谱范数意义下需要 $\Omega(d^{3/2})$ 个样本,均匹配上至对数因子。后一个下界验证了一个猜测的统计差异存在:谱估计高斯协方差的个人与非个人的样本大小差异。我们通过我们的主要技术贡献,将指纹识别方法广泛推广到指数家族,证明了这些下界。此外,使用 Achar、Sun 和 Zhang 的差分隐私 Assouad 方法,我们展示了在 $\ell_2$ 距离下有边界的 $\Omega(d/(\alpha^2 \varepsilon))$ 下界,以 $\alpha$ 误差估计方差有边界的分布平均值。先前已知的所有这些问题的下限要么多项式较弱,要么在更严格的 $(\varepsilon, 0)$ 差分隐私条件下成立。