# High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees

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

## Key facts

- Cited by 2 papers in the map (data through 14 Oct 2026).
- Builds on 27 of its 60 references that are in the map.
- First posted on arXiv 1 Apr 2021.

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

- [Renyi Differential Privacy](https://mlsanity.com/paper/1702.07476/) (2017)
- [RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response](https://mlsanity.com/paper/1407.6981/) (2014)
- [Collecting Telemetry Data Privately](https://mlsanity.com/paper/1712.01524/) (2017)
- [Statistical guarantees for the EM algorithm: From population to sample-based analysis](https://mlsanity.com/paper/1408.2156/) (2014)
- [Differentially Private Empirical Risk Minimization: Efficient Algorithms and Tight Error Bounds](https://mlsanity.com/paper/1405.7085/) (2014)
- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Fingerprinting Codes and the Price of Approximate Differential Privacy](https://mlsanity.com/paper/1311.3158/) (2013)
- [Private Mean Estimation of Heavy-Tailed Distributions](https://mlsanity.com/paper/2002.09464/) (2020)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Between Pure and Approximate Differential Privacy](https://mlsanity.com/paper/1501.06095/) (2015)
- [Privacy-preserving Prediction](https://mlsanity.com/paper/1803.10266/) (2018)
- [Ten Steps of EM Suffice for Mixtures of Two Gaussians](https://mlsanity.com/paper/1609.00368/) (2016)
- [Singularity, Misspecification, and the Convergence Rate of EM](https://mlsanity.com/paper/1810.00828/) (2018)
- [Global analysis of Expectation Maximization for mixtures of two Gaussians](https://mlsanity.com/paper/1608.07630/) (2016)
- [Differentially Private Algorithms for Learning Mixtures of Separated Gaussians](https://mlsanity.com/paper/1909.03951/) (2019)
- [Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent](https://mlsanity.com/paper/2006.06783/) (2020)
- [Global Convergence of EM Algorithm for Mixtures of Two Component Linear Regression](https://mlsanity.com/paper/1810.05752/) (2018)
- [On the Minimax Optimality of the EM Algorithm for Learning Two-Component Mixed Linear Regression](https://mlsanity.com/paper/2006.02601/) (2020)
- [Regularized EM Algorithms: A Unified Framework and Statistical Guarantees](https://mlsanity.com/paper/1511.08551/) (2015)
- [Privacy-preserving parametric inference: a case for robust statistics](https://mlsanity.com/paper/1911.10167/) (2019)
- [Differentially Private False Discovery Rate Control](https://mlsanity.com/paper/1807.04209/) (2018)
- [The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds](https://mlsanity.com/paper/2011.03900/) (2020)
- [Guidelines for Implementing and Auditing Differentially Private Systems](https://mlsanity.com/paper/2002.04049/) (2020)
- [The Price of Selection in Differential Privacy](https://mlsanity.com/paper/1702.02970/) (2017)
- [Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regression](https://mlsanity.com/paper/2011.03598/) (2020)
- [Differentially Private Inference for Binomial Data](https://mlsanity.com/paper/1904.00459/) (2019)
- [High-dimensional cluster analysis with the Masked EM Algorithm](https://mlsanity.com/paper/1309.2848/) (2013)

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

- [Differentially Private Federated Learning: Servers Trustworthiness, Estimation, and Statistical Inference](https://mlsanity.com/paper/2404.16287/) (2024)
- [Better Locally Private Sparse Estimation Given Multiple Samples Per User](https://mlsanity.com/paper/2408.04313/) (2024)

## Abstract (arXiv)

In this paper, we develop a general framework to design differentially private expectation-maximization (EM) algorithms in high-dimensional latent variable models, based on the noisy iterative hard-thresholding. We derive the statistical guarantees of the proposed framework and apply it to three specific models: Gaussian mixture, mixture of regression, and regression with missing covariates. In each model, we establish the near-optimal rate of convergence with differential privacy constraints, and show the proposed algorithm is minimax rate optimal up to logarithm factors. The technical tools developed for the high-dimensional setting are then extended to the classic low-dimensional latent variable models, and we propose a near rate-optimal EM algorithm with differential privacy guarantees in this setting. Simulation studies and real data analysis are conducted to support our results.