Private estimation algorithms for stochastic block models and mixture models

2023/01/11 by Chen, Hongjie, Cohen-Addad, Vincent, d'Orsi, Tommaso +4 · 1 citation
#Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.2301.04822

Abstract

We introduce general tools for designing efficient private estimation algorithms, in the high-dimensional settings, whose statistical guarantees almost match those of the best known non-private algorithms. To illustrate our techniques, we consider two problems: recovery of stochastic block models and learning mixtures of spherical Gaussians. For the former, we present the first efficient (ε, δ)-differentially private algorithm for both weak recovery and exact recovery. Previously known algorithms achieving comparable guarantees required quasi-polynomial time. For the latter, we design an (ε, δ)-differentially private algorithm that recovers the centers of the k-mixture when the minimum separation is at least O(k^1/t√(t)). For all choices of t, this algorithm requires sample complexity n≥ k^O(1)d^O(t) and time complexity (nd)^O(t). Prior work required minimum separation at least O(√(k)) as well as an explicit upper bound on the Euclidean norm of the centers.

Cited by

• Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency

Related

• Differentially Private Algorithms for Learning Mixtures of Separated\n Gaussians
• Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models
• Sample-Efficient Private Learning of Mixtures of Gaussians
• Privately Learning High-Dimensional Distributions
• Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples