# Robustness Implies Privacy in Statistical Estimation

arXiv: https://arxiv.org/abs/2212.05015 · HTML: https://mlsanity.com/paper/2212.05015/

## Key facts

- Cited by 47 papers in the map (data through 14 Oct 2026).
- Builds on 32 of its 50 references that are in the map.
- First posted on arXiv 9 Dec 2022.

## Builds on (most cited first, 30 of 32)

- [Statistical Query Lower Bounds for Robust Estimation of High-dimensional Gaussians and Gaussian Mixtures](https://mlsanity.com/paper/1611.03473/) (2016)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Efficient Algorithms and Lower Bounds for Robust Linear Regression](https://mlsanity.com/paper/1806.00040/) (2018)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Efficient Algorithms for Outlier-Robust Regression](https://mlsanity.com/paper/1803.03241/) (2018)
- [Robust and Differentially Private Mean Estimation](https://mlsanity.com/paper/2102.09159/) (2021)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Private Hypothesis Selection](https://mlsanity.com/paper/1905.13229/) (2019)
- [Average-Case Averages: Private Algorithms for Smooth Sensitivity and Mean Estimation](https://mlsanity.com/paper/1906.02830/) (2019)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Resilience: A Criterion for Learning in the Presence of Arbitrary Outliers](https://mlsanity.com/paper/1703.04940/) (2017)
- [On the Sample Complexity of Privately Learning Unbounded High-Dimensional Gaussians](https://mlsanity.com/paper/2010.09929/) (2020)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [A Private and Computationally-Efficient Estimator for Unbounded Gaussians](https://mlsanity.com/paper/2111.04609/) (2021)
- [New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma](https://mlsanity.com/paper/2205.08532/) (2022)
- [Tight and Robust Private Mean Estimation with Few Users](https://mlsanity.com/paper/2110.11876/) (2021)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Privacy-preserving parametric inference: a case for robust statistics](https://mlsanity.com/paper/1911.10167/) (2019)
- [How Hard Is Robust Mean Estimation?](https://mlsanity.com/paper/1903.07870/) (2019)
- [On robustness and local differential privacy](https://mlsanity.com/paper/2201.00751/) (2022)
- [Polynomial-Time Sum-of-Squares Can Robustly Estimate Mean and Covariance of Gaussians Optimally](https://mlsanity.com/paper/2110.11853/) (2021)
- [Robust and Private Learning of Halfspaces](https://mlsanity.com/paper/2011.14580/) (2020)
- [Differentially private depth functions and their associated medians](https://mlsanity.com/paper/2101.02800/) (2021)

## Built on by (most cited first, 30 of 47)

- [From Robustness to Privacy and Back](https://mlsanity.com/paper/2302.01855/) (2023)
- [On the Privacy-Robustness-Utility Trilemma in Distributed Learning](https://mlsanity.com/paper/2302.04787/) (2023)
- [Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions](https://mlsanity.com/paper/2301.12250/) (2023)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [Differential Privacy Mechanisms in Neural Tangent Kernel Regression](https://mlsanity.com/paper/2407.13621/) (2024)
- [Provable Differentially Private Computation of the Cross-Attention Mechanism](https://mlsanity.com/paper/2407.14717/) (2024)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [A Fast Algorithm for Adaptive Private Mean Estimation](https://mlsanity.com/paper/2301.07078/) (2023)
- [Near Optimal Private and Robust Linear Regression](https://mlsanity.com/paper/2301.13273/) (2023)
- [Lower Bounds for Private Estimation of Gaussian Covariance Matrices under All Reasonable Parameter Regimes](https://mlsanity.com/paper/2404.17714/) (2024)
- [Fast John Ellipsoid Computation with Differential Privacy Optimization](https://mlsanity.com/paper/2408.06395/) (2024)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Efficient Certificates of Anti-Concentration Beyond Gaussians](https://mlsanity.com/paper/2405.15084/) (2024)
- [Distribution Learnability and Robustness](https://mlsanity.com/paper/2406.17814/) (2024)
- [Sample-Optimal Locally Private Hypothesis Selection and the Provable Benefits of Interactivity](https://mlsanity.com/paper/2312.05645/) (2023)
- [Not All Learnable Distribution Classes are Privately Learnable](https://mlsanity.com/paper/2402.00267/) (2024)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [SquarechiPO: Differentially Private and Robust chi2-Preference Optimization in Offline Direct Alignment](https://mlsanity.com/paper/2505.21395/) (2025)
- [Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust](https://mlsanity.com/paper/2405.16663/) (2024)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [The Broader Landscape of Robustness in Algorithmic Statistics](https://mlsanity.com/paper/2412.02670/) (2024)
- [Tukey Depth Mechanisms for Practical Private Mean Estimation](https://mlsanity.com/paper/2502.18698/) (2025)
- [Causality Is Key to Understand and Balance Multiple Goals in Trustworthy ML and Foundation Models](https://mlsanity.com/paper/2502.21123/) (2025)

## Abstract (arXiv)

We study the relationship between adversarial robustness and differential privacy in high-dimensional algorithmic statistics. We give the first black-box reduction from privacy to robustness which can produce private estimators with optimal tradeoffs among sample complexity, accuracy, and privacy for a wide range of fundamental high-dimensional parameter estimation problems, including mean and covariance estimation. We show that this reduction can be implemented in polynomial time in some important special cases. In particular, using nearly-optimal polynomial-time robust estimators for the mean and covariance of high-dimensional Gaussians which are based on the Sum-of-Squares method, we design the first polynomial-time private estimators for these problems with nearly-optimal samples-accuracy-privacy tradeoffs. Our algorithms are also robust to a nearly optimal fraction of adversarially-corrupted samples.