Abstract
The iterative nature of the expectation maximization (EM) algorithm presents a challenge for privacy-preserving estimation, as each iteration increases the amount of noise needed. We propose a practical, differentially private version of the EM algorithm. By combining a "moment perturbation" strategy with advanced privacy composition methods (Moments Accountant and zCDP), we significantly reduce the additive noise required for iterative learning, making private EM viable for complex models like Gaussian Mixtures and Factor Analysis.
Introduction
The Expectation Maximization (EM) algorithm is a fundamental tool in statistics for estimating parameters in models with latent variables, such as Gaussian Mixture Models (GMMs). However, implementing EM under Differential Privacy (DP) constraints is challenging. Standard DP approaches require adding random noise at every iteration to mask individual data points. Under basic composition rules, this noise accumulates rapidly with the number of iterations and data dimensionality, often rendering the resulting model useless or forcing premature termination before convergence.
Methodology
To address the privacy-utility tradeoff in iterative learning, we introduce two primary innovations:
- Moment Perturbation: For models in the exponential family, parameters are deterministic functions of expected sufficient statistics (moments). Instead of perturbing final parameters, we add noise to the moments calculated during the E-step. This ensures privacy for the entire iteration while maintaining the structural integrity of the model updates.
- Advanced Composition (MA and zCDP): We utilize the Moments Accountant (MA) and zero-mean Concentrated Differential Privacy (zCDP) to track privacy leakage. Unlike standard "Advanced Composition," these methods provide much tighter bounds, allowing for a higher privacy budget per iteration and significantly reducing the total additive noise.
Empirical Evaluation
We evaluated DP-EM across several real-world datasets, including the Stroke dataset (50,345 patients), Life Science data (26,733 records), and high-dimensional image data from the Olivetti Faces set.
Key Results
- Utility and Convergence: On the Stroke and Life Science datasets, DP-EM achieved test log-likelihoods nearly identical to non-private EM. In contrast, versions using standard linear composition failed to produce useful models.
- Composition Efficiency: Our results demonstrate that zCDP and MA are vastly superior to previous gold standards like Advanced Composition. We recommend zCDP for its computational simplicity and performance.
- Factor Analysis Efficiency: A unique finding for Factor Analysis (FA) is that the algorithm only requires perturbing the data's second moment matrix once. Subsequent EM iterations are treated as "post-processing," incurring no additional privacy cost regardless of the iteration count.
Discussion and Conclusion
DP-EM provides a robust framework for private estimation in exponential family models. By moving away from naive noise composition and leveraging the deterministic relationship between moments and parameters, we achieve high utility even under strict privacy budgets. While the method requires careful data pre-processing (such as L2-norm clipping) and hyperparameter tuning for the number of iterations, it represents a significant step toward making private machine learning practical for complex statistical models. Future work will explore extending this framework to non-exponential family models, such as deep latent variable architectures.
Summary updated