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

• Activity Number: 120 - Challenges and Recent Advances in Private Data Analysis
• Type: Topic-Contributed
• Date/Time: Monday, August 9, 2021 : 1:30 PM to 3:20 PM
• Sponsor: Section on Nonparametric Statistics
• Author(s): Zhe Zhang* and Linjun Zhang
• Companies: Rutgers University, New Brunswick and Rutgers University
• Keywords: EM algorithm; High-dimensional statistics; Differential Privacy

Abstract

In this paper, we develop novel differentially private expectation-maximization (EM) algorithms, in both high-dimensional and classic low-dimensional settings. In the high dimensional case, a private EM algorithm based on the noisy iterative hard-thresholding algorithm is proposed and theoretically shown to attain a nearly minimax optimal rate of convergence. To show the generality of our algorithm, the proposed method is then applied to three specific models, Gaussian Mixture, Mixture of Regression and Regression with Missing Covariates models. In the low-dimensional settings, a nearly minimax optimal private EM algorithm is also proposed. Simulations are conducted to support our results under a variety of settings.