mlsanityData to 7 Oct 2026

Private Robust Estimation by Stabilizing Convex Relaxations

arXiv 2112.03548 ↗First posted 7 Dec 2021stat.ML cs.CR cs.DScited by 38

Not on the map. Why?

Abstract (arXiv)

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 [AL21] also obtained a polynomial time and sample private robust estimation algorithm for Gaussian distributions.

Key facts. Cited by 38 papers in the map (data through 7 Oct 2026). Builds on 52 of its 83 references that are in the map. First posted on arXiv 7 Dec 2021.

Builds on

52 of 83 references.

References · 52

  1. 2016Membership Inference Attacks against Machine Learning Modelscited by 2,221
  2. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  3. 2016Robust Estimators in High Dimensions without the Computational Intractabilitycited by 209
  4. 2017Collecting Telemetry Data Privatelycited by 147
  5. 2016Agnostic Estimation of Mean and Covariancecited by 131
  6. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  7. 2018Privately Learning High-Dimensional Distributionscited by 103
  8. 2019Recent Advances in Algorithmic High-Dimensional Robust Statisticscited by 100
  9. 2017Being Robust (in High Dimensions) Can Be Practicalcited by 83
  10. 2013Fingerprinting Codes and the Price of Approximate Differential Privacycited by 81
  11. 2017Mixture Models, Robustness, and Sum of Squares Proofscited by 81
  12. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
38 more
  1. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  2. 2018Efficient Algorithms for Outlier-Robust Regressioncited by 72
  3. 2021Robust and Differentially Private Mean Estimationcited by 66
  4. 2021Differential privacy and robust statistics in high dimensionscited by 64
  5. 2019Private Hypothesis Selectioncited by 60
  6. 2017Prochlo: Strong Privacy for Analytics in the Crowdcited by 51
  7. 2019Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimationcited by 51
  8. 2020On Differentially Private Stochastic Convex Optimization with Heavy-tailed Datacited by 51
  9. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  10. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  11. 2020Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimizationcited by 44
  12. 2017Resilience: A Criterion for Learning in the Presence of Arbitrary Outlierscited by 43
  13. 2019List-Decodable Linear Regressioncited by 42
  14. 2020Robust Linear Regression: Optimal Rates in Polynomial Timecited by 42
  15. 2019Quantum Entropy Scoring for Fast Robust Mean Estimation and Improved Outlier Detectioncited by 41
  16. 2020Robust Meta-learning for Mixed Linear Regression with Small Batchescited by 41
  17. 2020On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussianscited by 41
  18. 2017Robustly Learning a Gaussian: Getting Optimal Error, Efficientlycited by 39
  19. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
  20. 2019List Decodable Learning via Sum of Squarescited by 37
  21. 2019Generalized Resilience and Robust Statisticscited by 37
  22. 2014Interactive Fingerprinting Codes and the Hardness of Preventing False Discoverycited by 35
  23. 2020Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packingcited by 35
  24. 2021FriendlyCore: Practical Differentially Private Aggregationcited by 34
  25. 2021A Private and Computationally-Efficient Estimator for Unbounded Gaussianscited by 34
  26. 2018Mean Estimation with Sub-Gaussian Rates in Polynomial Timecited by 33
  27. 2019Faster Algorithms for High-Dimensional Robust Covariance Estimationcited by 28
  28. 2020Robustly Learning any Clusterable Mixture of Gaussianscited by 28
  29. 2017Outlier-robust moment-estimation via sum-of-squarescited by 27
  30. 2019Differentially Private Algorithms for Learning Mixtures of Separated Gaussianscited by 27
  31. 2014Dictionary Learning and Tensor Decomposition via the Sum-of-Squares Methodcited by 22
  32. 2017Better Agnostic Clustering Via Relaxed Tensor Normscited by 21
  33. 2020Differentially Private Confidence Intervalscited by 20
  34. 2020Outlier-Robust Clustering of Non-Spherical Mixturescited by 19
  35. 2019Private Identity Testing for High-Dimensional Distributionscited by 15
  36. 2020Privately Learning Markov Random Fieldscited by 14
  37. 2021Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimallycited by 14
  38. 2020Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Timecited by 9

50 most cited of 52 All 52 (JSON)

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 7; 2023: 16; 2024: 10; 2025: 3; 2026: 2.

38 papers.

Sort:

  1. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  2. 2022Private Estimation with Public Datacited by 31
  3. 2023From Robustness to Privacy and Backcited by 27
  4. 2022Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimationcited by 25
  5. 2022DP-PCA: Statistically Optimal and Differentially Private PCAcited by 24
  6. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  7. 2023Private estimation algorithms for stochastic block models and mixture modelscited by 21
  8. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  9. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  10. 2022Differentially Private Covariance Revisitedcited by 15
  11. 2023Private Distribution Learning with Public Data: The View from Sample Compressioncited by 14
  12. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
26 more
  1. 2023A Fast Algorithm for Adaptive Private Mean Estimationcited by 11
  2. 2022Differentially Private Regression with Unbounded Covariatescited by 10
  3. 2024SoS Certifiability of Subgaussian Distributions and its Algorithmic Applicationscited by 10
  4. 2023Near Optimal Private and Robust Linear Regressioncited by 9
  5. 2023PLAN: Variance-Aware Private Mean Estimationcited by 6
  6. 2023A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributionscited by 5
  7. 2023Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samplescited by 5
  8. 2024Efficient Certificates of Anti-Concentration Beyond Gaussianscited by 4
  9. 2024Distribution Learnability and Robustnesscited by 4
  10. 2023Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivitycited by 3
  11. 2024Not All Learnable Distribution Classes are Privately Learnablecited by 3
  12. 2025An Iterative Algorithm for Differentially Private k-PCA with Adaptive Noisecited by 3
  13. 2024Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robustcited by 2
  14. 2024Agnostic Private Density Estimation for GMMs via List Global Stabilitycited by 2
  15. 2024The Broader Landscape of Robustness in Algorithmic Statisticscited by 2
  16. 2024On Differentially Private Subspace Estimation in a Distribution-Free Settingcited by 1
  17. 2024Perturb-and-Project: Differentially Private Similarities and Marginalscited by 1
  18. 2025Optimal Differentially Private Sampling of Unbounded Gaussianscited by 1
  19. 2022Privately Estimating a Gaussian: Efficient, Robust and Optimalcited by 0
  20. 2023Robust and differentially private stochastic linear banditscited by 0
  21. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0
  22. 2023Instance-Specific Asymmetric Sensitivity in Differential Privacycited by 0
  23. 2024Sample-Efficient Private Learning of Mixtures of Gaussianscited by 0
  24. 2025A Private Approximation of the 2nd-Moment Matrix of Any Subsamplable Inputcited by 0
  25. 2026Computationally tractable robust differentially private mean estimationcited by 0
  26. 2026On the SoS Certifiability of Log-Concave Distributionscited by 0