# Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation

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

## Key facts

- Cited by 25 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 59 references that are in the map.
- First posted on arXiv 1 Nov 2022.

## Builds on (most cited first, 29 of 29)

- [Concentrated Differential Privacy: Simplifications, Extensions, and Lower Bounds](https://mlsanity.com/paper/1605.02065/) (2016)
- [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)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [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)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Reducibility and Statistical-Computational Gaps from Secret Leakage](https://mlsanity.com/paper/2005.08099/) (2020)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Sub-Gaussian estimators of the mean of a random vector](https://mlsanity.com/paper/1702.00482/) (2017)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Robust and Heavy-Tailed Mean Estimation Made Simple, via Regret Minimization](https://mlsanity.com/paper/2007.15839/) (2020)
- [Geographic Spines in the 2020 Census Disclosure Avoidance System](https://mlsanity.com/paper/2203.16654/) (2022)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [Mean Estimation with Sub-Gaussian Rates in Polynomial Time](https://mlsanity.com/paper/1809.07425/) (2018)
- [High-dimensional estimation via sum-of-squares proofs](https://mlsanity.com/paper/1807.11419/) (2018)
- [Fast Mean Estimation with Sub-Gaussian Rates](https://mlsanity.com/paper/1902.01998/) (2019)
- [Differentially Private False Discovery Rate Control](https://mlsanity.com/paper/1807.04209/) (2018)
- [Sum-of-squares proofs and the quest toward optimal algorithms](https://mlsanity.com/paper/1404.5236/) (2014)
- [A Computational Separation between Private Learning and Online Learning](https://mlsanity.com/paper/2007.05665/) (2020)
- [Sampling from Log-Concave Distributions with Infinity-Distance Guarantees](https://mlsanity.com/paper/2111.04089/) (2021)
- [Private False Discovery Rate Control](https://mlsanity.com/paper/1511.03803/) (2015)
- [Learning to be adversarially robust and differentially private](https://mlsanity.com/paper/2201.02265/) (2022)
- [The Sample Complexity of Robust Covariance Testing](https://mlsanity.com/paper/2012.15802/) (2020)
- [Robust Estimation of Discrete Distributions under Local Differential Privacy](https://mlsanity.com/paper/2202.06825/) (2022)
- [An Approach to One-Bit Compressed Sensing Based on Probably Approximately Correct Learning Theory](https://mlsanity.com/paper/1710.07973/) (2017)
- [Can collaborative learning be private, robust and scalable?](https://mlsanity.com/paper/2205.02652/) (2022)

## Built on by (most cited first, 25 of 25)

- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [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)
- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [On the Computational Landscape of Replicable Learning](https://mlsanity.com/paper/2405.15599/) (2024)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [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)
- [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)
- [Sample-Optimal Private Regression in Polynomial Time](https://mlsanity.com/paper/2503.24321/) (2025)
- [PTF Testing Lower Bounds for Non-Gaussian Component Analysis](https://mlsanity.com/paper/2511.19398/) (2025)
- [Differentially-Private Decision Trees and Provable Robustness to Data Poisoning](https://mlsanity.com/paper/2305.15394/) (2023)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [Robust Estimation Under Heterogeneous Corruption Rates](https://mlsanity.com/paper/2508.15051/) (2025)
- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)
- [Privately Estimating a Gaussian: Efficient, Robust and Optimal](https://mlsanity.com/paper/2212.08018/) (2022)
- [Computationally Efficient Replicable Learning of Parities and Applications](https://mlsanity.com/paper/2602.09499/) (2026)

## Abstract (arXiv)

We establish a simple connection between robust and differentially-private algorithms: private mechanisms which perform well with very high probability are automatically robust in the sense that they retain accuracy even if a constant fraction of the samples they receive are adversarially corrupted. Since optimal mechanisms typically achieve these high success probabilities, our results imply that optimal private mechanisms for many basic statistics problems are robust. We investigate the consequences of this observation for both algorithms and computational complexity across different statistical problems. Assuming the Brennan-Bresler secret-leakage planted clique conjecture, we demonstrate a fundamental tradeoff between computational efficiency, privacy leakage, and success probability for sparse mean estimation. Private algorithms which match this tradeoff are not yet known -- we achieve that (up to polylogarithmic factors) in a polynomially-large range of parameters via the Sum-of-Squares method. To establish an information-computation gap for private sparse mean estimation, we also design new (exponential-time) mechanisms using fewer samples than efficient algorithms must use. Finally, we give evidence for privacy-induced information-computation gaps for several other statistics and learning problems, including PAC learning parity functions and estimation of the mean of a multivariate Gaussian.