2021/06/24 by Gavin Brown, Brown, Gavin, Marco Gaboardi +7 · 4 citations
Computer Science · Economics, Econometrics and Finance · Mathematics · #Adversarial Robustness in Machine Learning #Cryptography and Data Security #Economic and Environmental Valuation #FOS: Computer and information sciences #Machine Learning (cs.LG) #Privacy-Preserving Technologies in Data #Statistical Methods and Bayesian Inference
paper · pdf · doi:10.48550/arxiv.2106.13329
openalex publication_date 2021/06/24 · openalex created_date 2022/07/25 · openalex updated_date 2026/07/28
We present two sample-efficient differentially private mean estimators for\nd-dimensional (sub)Gaussian distributions with unknown covariance.\nInformally, given n gtrsim d/\α2 samples from such a distribution with\nmean \μ and covariance \Σ, our estimators output μ such that\n\‖ μ - \μ \‖\Σ \≤ \α, where \‖ \⋅ \‖\Σ is\nthe Mahalanobis distance. All previous estimators with the same guarantee\neither require strong a priori bounds on the covariance matrix or require\n\Ω(d3/2) samples.\n Each of our estimators is based on a simple, general approach to designing\ndifferentially private mechanisms, but with novel technical steps to make the\nestimator private and sample-efficient. Our first estimator samples a point\nwith approximately maximum Tukey depth using the exponential mechanism, but\nrestricted to the set of points of large Tukey depth. Its accuracy guarantees\nhold even for data sets that have a small amount of adversarial corruption.\nProving that this mechanism is private requires a novel analysis. Our second\nestimator perturbs the empirical mean of the data set with noise calibrated to\nthe empirical covariance, without releasing the covariance itself. Its sample\ncomplexity guarantees hold more generally for subgaussian distributions, albeit\nwith a slightly worse dependence on the privacy parameter. For both estimators,\ncareful preprocessing of the data is required to satisfy differential privacy.\n