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

Abstract

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.

arXiv comment68 pages, 3 figures

References in corpus (14)

• Gaussian Differential Privacy
• Alternating Minimization for Mixed Linear Regression
• Global analysis of Expectation Maximization for mixtures of two Gaussians
• The Cost of Privacy: Rates of Convergence for Parameter Estimation with Differential Privacy
• Privacy-preserving parametric inference: a case for robust statistics
• Private Mean Estimation of Heavy-Tailed Distributions
• Guidelines for Implementing and Auditing Differentially Private Systems
• The Cost of Privacy in Generalized Linear Models: Algorithms and Minimax Lower Bounds
• Differentially Private False Discovery Rate Control
• The Price of Selection in Differential Privacy
• The EM Algorithm gives Sample-Optimality for Learning Mixtures of Well-Separated Gaussians
• Evading Curse of Dimensionality in Unconstrained Private GLMs via Private Gradient Descent
• Estimation, Confidence Intervals, and Large-Scale Hypotheses Testing for High-Dimensional Mixed Linear Regression
• Differentially Private (Gradient) Expectation Maximization Algorithm with Statistical Guarantees