Private Robust Estimation by Stabilizing Convex Relaxations
Private Robust Estimation by Stabilizing Convex Relaxations
复制标题
DOI：
--
复制
发表时间：
2021-12
期刊：
影响因子：
--
通讯作者：
Pravesh Kothari;Pasin Manurangsi;A. Velingker
中科院分区：
文献类型：
--
作者：
Pravesh Kothari;Pasin Manurangsi;A. Velingker
我们给出了第一个多项式时间和样本(ε，δ)-差分私有(DP)算法，以估计在存在恒定比例敌对异常值的情况下的均值、协方差和高阶矩。我们的算法成功地应用于满足两个稳健估计性质的分布族：方向矩的可证明的次高斯性和二次多项式的可证明的超缩性。我们的恢复保证在“右仿射不变范数”中成立：均值的马氏距离、乘法谱距离和相对Frobenius距离保证协方差和高阶矩的内射范数。前人的工作得到了协方差有界的次高斯分布的均值估计的私人稳健算法。对于协方差估计，我们的算法是第一个在没有任何条件数假设的情况下成功的有效算法(即使在没有异常值的情况下)。我们的算法源于一个新的框架，当算法在运行中产生正确性证明时，该框架提供了修改稳健估计的凸松弛的一般蓝图，以满足适当参数范数下的强最坏情况稳定性保证。我们验证了对标准平方和(SOS)半定规划松弛的修改的稳健估计的这种保证。我们的隐私保证是通过将稳定性保证与一种新的“依赖于估计”的噪声注入机制相结合来获得的，在该机制中，噪声根据估计协方差的特征值进行缩放。我们相信这个框架在获得稳健估计的DP对应项时会更普遍地有用。除了我们的工作之外，Ashtiani和Liaw(2021)还得到了高斯分布的多项式时间和样本私人稳健估计算法。
We give the first polynomial time and sample (ε, δ)-differentially private (DP) algorithm to estimate the mean, covariance and higher moments in the presence of a constant fraction of adversarial outliers. Our algorithm succeeds for families of distributions that satisfy two well-studied properties in prior works on robust estimation: certifiable subgaussianity of directional moments and certifiable hypercontractivity of degree 2 polynomials. Our recovery guarantees hold in the “right affine-invariant norms”: Mahalanobis distance for mean, multiplicative spectral and relative Frobenius distance guarantees for covariance and injective norms for higher moments. Prior works obtained private robust algorithms for mean estimation of subgaussian distributions with bounded covariance. For covariance estimation, ours is the first efficient algorithm (even in the absence of outliers) that succeeds without any condition-number assumptions. Our algorithms arise from a new framework that provides a general blueprint for modifying convex relaxations for robust estimation to satisfy strong worst-case stability guarantees in the appropriate parameter norms whenever the algorithms produce witnesses of correctness in their run. We verify such guarantees for a modification of standard sum-of-squares (SoS) semidefinite programming relaxations for robust estimation. Our privacy guarantees are obtained by combining stability guarantees with a new “estimate dependent” noise injection mechanism in which noise scales with the eigenvalues of the estimated covariance. We believe this framework will be useful more generally in obtaining DP counterparts of robust estimators. Independently of our work, Ashtiani and Liaw (2021) also obtained a polynomial time and sample private robust estimation algorithm for Gaussian distributions.