mlsanityData to 7 Oct 2026

A Fast Algorithm for Adaptive Private Mean Estimation

arXiv 2301.07078 ↗First posted 17 Jan 2023stat.ML cs.CR cs.DScited by 11

Not on the map. Why?

Abstract (arXiv)

We design an (varepsilon, δ)-differentially private algorithm to estimate the mean of a d-variate distribution, with unknown covariance Sigma, that is adaptive to Sigma. To within polylogarithmic factors, the estimator achieves optimal rates of convergence with respect to the induced Mahalanobis norm ||·||_Sigma, takes time tildeO(n d2) to compute, has near linear sample complexity for sub-Gaussian distributions, allows Sigma to be degenerate or low rank, and adaptively extends beyond sub-Gaussianity. Prior to this work, other methods required exponential computation time or the superlinear scaling n = Omega(d3/2) to achieve non-trivial error with respect to the norm ||·||_Sigma.

Key facts. Cited by 11 papers in the map (data through 7 Oct 2026). Builds on 16 of its 40 references that are in the map. First posted on arXiv 17 Jan 2023.

Builds on

16 of 40 references.

References · 16

  1. 2016Deep Learning with Differential Privacycited by 2,682
  2. 2017Renyi Differential Privacycited by 643
  3. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  4. 2018Privately Learning High-Dimensional Distributionscited by 103
  5. 2020CoinPress: Practical Private Mean and Covariance Estimationcited by 74
  6. 2021Robust and Differentially Private Mean Estimationcited by 66
  7. 2021Differential privacy and robust statistics in high dimensionscited by 64
  8. 2015Between Pure and Approximate Differential Privacycited by 55
  9. 2021Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanismcited by 50
  10. 2022Robustness Implies Privacy in Statistical Estimationcited by 47
  11. 2021Covariance-Aware Private Mean Estimation Without Private Covariance Estimationcited by 46
  12. 2021Private and polynomial time algorithms for learning Gaussians and beyondcited by 39
4 more
  1. 2021Private Robust Estimation by Stabilizing Convex Relaxationscited by 38
  2. 2021Instance-optimal Mean Estimation Under Differential Privacycited by 37
  3. 2021Oneshot Differentially Private Top-k Selectioncited by 16
  4. 2018Issues Encountered Deploying Differential Privacycited by 5

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2023: 8; 2024: 1; 2025: 1; 2026: 1.

11 papers.

  1. 2023Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributionscited by 22
  2. 2023Polynomial Time and Private Learning of Unbounded Gaussian Mixture Modelscited by 19
  3. 2023Better and Simpler Lower Bounds for Differentially Private Statistical Estimationcited by 16
  4. 2023A Bias-Accuracy-Privacy Trilemma for Statistical Estimationcited by 12
  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. 2024On Differentially Private U Statisticscited by 2
  9. 2025Improved subsample-and-aggregate via the private modified winsorized meancited by 1
  10. 2023Statistical Barriers to Affine-equivariant Estimationcited by 0
  11. 2026Computationally tractable robust differentially private mean estimationcited by 0