# Differentially private multivariate medians

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 23 of its 56 references that are in the map.
- First posted on arXiv 12 Oct 2022.

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

- [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)
- [CoinPress: Practical Private Mean and Covariance Estimation](https://mlsanity.com/paper/2006.06618/) (2020)
- [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)
- [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)
- [Propose, Test, Release: Differentially private estimation with high probability](https://mlsanity.com/paper/2002.08774/) (2020)
- [Private Center Points and Learning of Halfspaces](https://mlsanity.com/paper/1902.10731/) (2019)
- [Optimal Private Median Estimation under Minimal Distributional Assumptions](https://mlsanity.com/paper/2011.06202/) (2020)
- [Exact computation of the halfspace depth](https://mlsanity.com/paper/1411.6927/) (2014)
- [Structure and Sensitivity in Differential Privacy: Comparing K-Norm Mechanisms](https://mlsanity.com/paper/1801.09236/) (2018)
- [Differentially private sub-Gaussian location estimators](https://mlsanity.com/paper/1906.11923/) (2019)
- [Exact Privacy Guarantees for Markov Chain Implementations of the Exponential Mechanism with Artificial Atoms](https://mlsanity.com/paper/2204.01132/) (2022)
- [When does the Tukey median work?](https://mlsanity.com/paper/2001.07805/) (2020)
- [Private Quantiles Estimation in the Presence of Atoms](https://mlsanity.com/paper/2202.08969/) (2022)
- [Archimedes Meets Privacy: On Privately Estimating Quantiles in High Dimensions Under Minimal Assumptions](https://mlsanity.com/paper/2208.07438/) (2022)
- [Approximating the Simplicial Depth](https://mlsanity.com/paper/1512.04856/) (2015)
- [Private Approximations of a Convex Hull in Low Dimensions](https://mlsanity.com/paper/2007.08110/) (2020)

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

- [Robustness Implies Privacy in Statistical Estimation](https://mlsanity.com/paper/2212.05015/) (2022)
- [Computationally tractable robust differentially private mean estimation](https://mlsanity.com/paper/2606.12654/) (2026)

## Abstract (arXiv)

Statistical tools which satisfy rigorous privacy guarantees are necessary for modern data analysis. It is well-known that robustness against contamination is linked to differential privacy. Despite this fact, using multivariate medians for differentially private and robust multivariate location estimation has not been systematically studied. We develop novel finite-sample performance guarantees for differentially private multivariate depth-based medians, which are essentially sharp. Our results cover commonly used depth functions, such as the halfspace (or Tukey) depth, spatial depth, and the integrated dual depth. We show that under Cauchy marginals, the cost of heavy-tailed location estimation outweighs the cost of privacy. We demonstrate our results numerically using a Gaussian contamination model in dimensions up to d = 100, and compare them to a state-of-the-art private mean estimation algorithm. As a by-product of our investigation, we prove concentration inequalities for the output of the exponential mechanism about the maximizer of the population objective function. This bound applies to objective functions that satisfy a mild regularity condition.