Privately Estimating a Gaussian: Efficient, Robust, and Optimal
Privately Estimating a Gaussian: Efficient, Robust, and Optimal
复制标题
私下估计高斯：高效、稳健且最优
DOI：
10.1145/3564246.3585194
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Zhang, Fred
中科院分区：
文献类型：
--
作者：
Alabi, Daniel;Kothari, Pravesh K.;Tankala, Pranay;Venkat, Prayaag;Zhang, Fred
在这项工作中，我们给出了有效的算法，私人估计高斯分布在纯和近似差分隐私（DP）模型与最佳的依赖于样本复杂度的维度。在纯DP设置，我们给出了一个有效的算法，估计未知维高斯分布到任意微小的总变差误差使用O（d2logκ）样本，同时容忍恒定比例的敌对离群值。这里，κ是目标协方差矩阵的条件数。样本界匹配最好的非私人估计的依赖的维度（多对数因子）。我们证明了差分私有协方差估计的一个新的下界，以表明在上述样本界中对条件数κ的依赖也是紧密的。在我们的工作之前，只有可识别性结果（产生低效的超多项式时间算法）是已知的problem.In近似DP设置，我们给出了一个有效的算法来估计未知的高斯分布到任意微小的总变异误差usingO（d2）样本，同时容忍一个常数部分的敌对离群值。在此之前，我们的工作，所有有效的近似DP算法产生超二次样本成本或不离群鲁棒。对于均值估计的特殊情况，我们的算法实现了O（d）的最佳样本复杂度，改进了以前工作的O（d1.5）界。我们的纯DP算法依赖于一个递归的私有预处理子例程，该子例程利用了霍普金斯等人（STOC 2022）关于私有均值估计的最新工作。我们的近似DP算法是基于Kothari等人（COLT 2022）引入的稳定凸松弛方法的实质性升级。特别是，我们通过使用一个新的非归一化熵正则化和一个新的和令人惊讶的简单的机制，私下释放协方差改进他们的机制。
In this work, we give efficient algorithms for privately estimating a Gaussian distribution in both pure and approximate differential privacy (DP) models with optimal dependence on the dimension in the sample complexity.In the pure DP setting, we give an efficient algorithm that estimates an unknownd-dimensional Gaussian distribution up to an arbitrary tiny total variation error usingO(d2logκ) samples while tolerating a constant fraction of adversarial outliers. Here, κ is the condition number of the target covariance matrix. The sample bound matches best non-private estimators in the dependence on the dimension (up to a polylogarithmic factor). We prove a new lower bound on differentially private covariance estimation to show that the dependence on the condition number κ in the above sample bound is also tight. Prior to our work, only identifiability results (yielding inefficient super-polynomial time algorithms) were known for the problem.In the approximate DP setting, we give an efficient algorithm to estimate an unknown Gaussian distribution up to an arbitrarily tiny total variation error usingO(d2) samples while tolerating a constant fraction of adversarial outliers. Prior to our work, all efficient approximate DP algorithms incurred a super-quadratic sample cost or were not outlier-robust. For the special case of mean estimation, our algorithm achieves the optimal sample complexity ofO(d), improving on aO(d1.5) bound from prior work.Our pure DP algorithm relies on a recursive private preconditioning subroutine that utilizes recent work of Hopkins et al. (STOC 2022) on private mean estimation. Our approximate DP algorithms are based on a substantial upgrade of the method of stabilizing convex relaxations introduced by Kothari et al. (COLT 2022). In particular, we improve on their mechanism by using a new unnormalized entropy regularization and a new and surprisingly simple mechanism for privately releasing covariances.
登录
查看更多内容
通过平方和指数机制实现具有纯差分隐私的高效均值估计
DOI：
--
发表时间：
2021
期刊：
Symposium on the Theory of Computing
影响因子：
--
作者：
Samuel B. Hopkins;Gautam Kamath;Mahbod Majid
通讯作者：
Mahbod Majid
DOI：
10.1137/1.9781611975031.171
发表时间：
2017-04
期刊：
ArXiv
影响因子：
--
作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
通讯作者：
Ilias Diakonikolas;Gautam Kamath;D. Kane;Jerry Li;Ankur Moitra;Alistair Stewart
DOI：
--
发表时间：
2018-05
期刊：
--
影响因子：
--
作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
通讯作者：
Gautam Kamath;Jerry Li;Vikrant Singhal;Jonathan Ullman
DOI：
--
发表时间：
2021-12
期刊：
--
影响因子：
--
作者：
Pravesh Kothari;Pasin Manurangsi;A. Velingker
通讯作者：
Pravesh Kothari;Pasin Manurangsi;A. Velingker
FriendlyCore：实用的差分私有聚合
DOI：
--
发表时间：
2021
期刊：
International Conference on Machine Learning
影响因子：
--
作者：
Eliad Tsfadia;E. Cohen;Haim Kaplan;Y. Mansour;Uri Stemmer
通讯作者：
Uri Stemmer