Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models

2023/03/07 by Jamil Arbas, Arbas, Jamil, Hassan Ashtiani +3 · 7 citations
Computer Science · Mathematics · #Algorithm #Artificial intelligence #Bayesian Methods and Mixture Models #Computer science #Constant (computer programming) #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Gaussian #Information Theory (cs.IT) #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Mathematics #Mixture model #Overhead (engineering) #Polynomial #Running time #Sample (material) #Sample complexity #Statistical Methods and Inference #Time complexity #Upper and lower bounds

paper · pdf · doi:10.48550/arxiv.2303.04288

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2023/03/07 · openalex created_date 2023/03/10 · openalex updated_date 2026/07/28

Abstract

We study the problem of privately estimating the parameters of d-dimensional Gaussian Mixture Models (GMMs) with k components. For this, we develop a technique to reduce the problem to its non-private counterpart. This allows us to privatize existing non-private algorithms in a blackbox manner, while incurring only a small overhead in the sample complexity and running time. As the main application of our framework, we develop an (ε, δ)-differentially private algorithm to learn GMMs using the non-private algorithm of Moitra and Valiant [MV10] as a blackbox. Consequently, this gives the first sample complexity upper bound and first polynomial time algorithm for privately learning GMMs without any boundedness assumptions on the parameters. As part of our analysis, we prove a tight (up to a constant factor) lower bound on the total variation distance of high-dimensional Gaussians which can be of independent interest.

Cited by

• Optimal Bounds for Tyler's M-Estimator for Elliptical Distributions
• Self-concordant Schrödinger operators: spectral gaps and optimization without condition numbers
• Mixtures Closest to a Given Measure: A Semidefinite Programming Approach
• Energy-independent tomography of Gaussian states
• Robust Learnability of Sample-Compressible Distributions under Noisy or Adversarial Perturbations
• Private Training & Data Generation by Clustering Embeddings
• Spectra of contractions of the Gaussian Orthogonal Tensor Ensemble

Related

• Differentially Private Algorithms for Learning Mixtures of Separated Gaussians
• Sample-Efficient Private Learning of Mixtures of Gaussians
• Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples
• Private estimation algorithms for stochastic block models and mixture models
• Private and polynomial time algorithms for learning Gaussians and beyond