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)$ 差分隐私条件下成立。

0
下载
关闭预览

相关内容

Into the Metaverse,93页ppt介绍元宇宙概念、应用、趋势
专知会员服务
47+阅读 · 2022年2月19日
【AAAI 2022】一致性信息瓶颈在域泛化中的应用
专知会员服务
24+阅读 · 2022年1月15日
专知会员服务
50+阅读 · 2020年12月14日
专知会员服务
84+阅读 · 2020年12月5日
专知会员服务
159+阅读 · 2020年1月16日
浅聊对比学习(Contrastive Learning)
极市平台
2+阅读 · 2022年7月26日
浅聊对比学习(Contrastive Learning)第一弹
PaperWeekly
0+阅读 · 2022年6月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
VIP会员
相关资讯
浅聊对比学习(Contrastive Learning)
极市平台
2+阅读 · 2022年7月26日
浅聊对比学习(Contrastive Learning)第一弹
PaperWeekly
0+阅读 · 2022年6月10日
VCIP 2022 Call for Demos
CCF多媒体专委会
1+阅读 · 2022年6月6日
Hierarchically Structured Meta-learning
CreateAMind
26+阅读 · 2019年5月22日
Transferring Knowledge across Learning Processes
CreateAMind
27+阅读 · 2019年5月18日
深度自进化聚类:Deep Self-Evolution Clustering
我爱读PAMI
15+阅读 · 2019年4月13日
逆强化学习-学习人先验的动机
CreateAMind
15+阅读 · 2019年1月18日
相关基金
国家自然科学基金
1+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2015年12月31日
国家自然科学基金
0+阅读 · 2014年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2013年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2012年12月31日
国家自然科学基金
0+阅读 · 2011年12月31日
国家自然科学基金
1+阅读 · 2011年12月31日
国家自然科学基金
0+阅读 · 2009年12月31日
Top
微信扫码咨询专知VIP会员