# From Robustness to Privacy and Back

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

## Key facts

- Cited by 27 papers in the map (data through 14 Oct 2026).
- Builds on 29 of its 57 references that are in the map.
- First posted on arXiv 3 Feb 2023.

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

- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Being Robust (in High Dimensions) Can Be Practical](https://mlsanity.com/paper/1703.00893/) (2017)
- [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)
- [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)
- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Covariance-Aware Private Mean Estimation Without Private Covariance Estimation](https://mlsanity.com/paper/2106.13329/) (2021)
- [Geographic Spines in the 2020 Census Disclosure Avoidance System](https://mlsanity.com/paper/2203.16654/) (2022)
- [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)
- [Robust Sub-Gaussian Principal Component Analysis and Width-Independent Schatten Packing](https://mlsanity.com/paper/2006.06980/) (2020)
- [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021)
- [Faster Algorithms for High-Dimensional Robust Covariance Estimation](https://mlsanity.com/paper/1906.04661/) (2019)
- [Differentially Private SQL with Bounded User Contribution](https://mlsanity.com/paper/1909.01917/) (2019)
- [LinkedIn's Audience Engagements API: A Privacy Preserving Data Analytics System at Scale](https://mlsanity.com/paper/2002.05839/) (2020)
- [Privacy Induces Robustness: Information-Computation Gaps and Sparse Mean Estimation](https://mlsanity.com/paper/2211.00724/) (2022)
- [Near Instance-Optimality in Differential Privacy](https://mlsanity.com/paper/2005.10630/) (2020)
- [Robust Regression via Mutivariate Regression Depth](https://mlsanity.com/paper/1702.04656/) (2017)
- [Private Identity Testing for High-Dimensional Distributions](https://mlsanity.com/paper/1905.11947/) (2019)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [Differentially private sub-Gaussian location estimators](https://mlsanity.com/paper/1906.11923/) (2019)
- [Robust Gaussian Covariance Estimation in Nearly-Matrix Multiplication Time](https://mlsanity.com/paper/2006.13312/) (2020)
- [Robust and Private Learning of Halfspaces](https://mlsanity.com/paper/2011.14580/) (2020)

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

- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [The Bayesian Stability Zoo](https://mlsanity.com/paper/2310.18428/) (2023)
- [A Huber Loss Minimization Approach to Mean Estimation under User-level Differential Privacy](https://mlsanity.com/paper/2405.13453/) (2024)
- [On Private and Robust Bandits](https://mlsanity.com/paper/2302.02526/) (2023)
- [A Meta-learning Framework for Tuning Parameters of Protection Mechanisms in Trustworthy Federated Learning](https://mlsanity.com/paper/2305.18400/) (2023)
- [Dimension-free Private Mean Estimation for Anisotropic Distributions](https://mlsanity.com/paper/2411.00775/) (2024)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Not All Learnable Distribution Classes are Privately Learnable](https://mlsanity.com/paper/2402.00267/) (2024)
- [SoS Certificates for Sparse Singular Values and Their Applications: Robust Statistics, Subspace Distortion, and More](https://mlsanity.com/paper/2412.21203/) (2024)
- [A Game-theoretic Framework for Privacy-preserving Federated Learning](https://mlsanity.com/paper/2304.05836/) (2023)
- [About the Cost of Central Privacy in Density Estimation](https://mlsanity.com/paper/2306.14535/) (2023)
- [Sparse Decentralized Federated Learning](https://mlsanity.com/paper/2308.16671/) (2023)
- [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)
- [Balancing Privacy, Robustness, and Efficiency in Machine Learning](https://mlsanity.com/paper/2312.14712/) (2023)
- [Bridging Privacy and Robustness for Trustworthy Machine Learning](https://mlsanity.com/paper/2403.16591/) (2024)
- [Optimal Differentially Private Sampling of Unbounded Gaussians](https://mlsanity.com/paper/2503.01766/) (2025)
- [Robust Estimation Under Heterogeneous Corruption Rates](https://mlsanity.com/paper/2508.15051/) (2025)
- [Privately Estimating Black-Box Statistics](https://mlsanity.com/paper/2510.00322/) (2025)
- [Sample-Efficient Private Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2411.02298/) (2024)
- [Robust Privacy: Inference-Stage Privacy through Certified Robustness](https://mlsanity.com/paper/2601.17360/) (2026)
- [Computationally Efficient Replicable Learning of Parities and Applications](https://mlsanity.com/paper/2602.09499/) (2026)
- [Robust Statistical Estimators with Bounded Empirical Sensitivity](https://mlsanity.com/paper/2605.21860/) (2026)
- [Enhancing Differentially Private Mechanisms via Empirical Bayes](https://mlsanity.com/paper/2606.21107/) (2026)

## Abstract (arXiv)

We study the relationship between two desiderata of algorithms in statistical inference and machine learning: differential privacy and robustness to adversarial data corruptions. Their conceptual similarity was first observed by Dwork and Lei (STOC 2009), who observed that private algorithms satisfy robustness, and gave a general method for converting robust algorithms to private ones. However, all general methods for transforming robust algorithms into private ones lead to suboptimal error rates. Our work gives the first black-box transformation that converts any adversarially robust algorithm into one that satisfies pure differential privacy. Moreover, we show that for any low-dimensional estimation task, applying our transformation to an optimal robust estimator results in an optimal private estimator. Thus, we conclude that for any low-dimensional task, the optimal error rate for varepsilon-differentially private estimators is essentially the same as the optimal error rate for estimators that are robust to adversarially corrupting 1/varepsilon training samples. We apply our transformation to obtain new optimal private estimators for several high-dimensional tasks, including Gaussian (sparse) linear regression and PCA. Finally, we present an extension of our transformation that leads to approximate differentially private algorithms whose error does not depend on the range of the output space, which is impossible under pure differential privacy.