Private estimation algorithms for stochastic block models and mixture models

2023/01/11 by Hongjie Chen, Vincent Cohen-Addad, Chen, Hongjie +11 · 4 citations
Mathematics · #Algorithm #Artificial intelligence #Block (permutation group theory) #Combinatorics #Computational complexity theory #Computer science #Cryptography and Security (cs.CR) #Data Structures and Algorithms (cs.DS) #Discrete mathematics #Euclidean geometry #FOS: Computer and information sciences #Geometry #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Markov Chains and Monte Carlo Methods #Mathematics #Norm (philosophy) #Polynomial #Random Matrices and Applications #Sample complexity #Statistical Methods and Inference #Time complexity #Upper and lower bounds

paper · pdf · doi:10.48550/arxiv.2301.04822

published in arXiv (Cornell University) (Cornell University)

openalex publication_date 2023/01/11 · openalex created_date 2023/01/14 · openalex updated_date 2026/08/04

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
• Locally Differentially Private Graph Clustering via the Power Iteration Method
• On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models
• Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy

Related

• Differentially Private Algorithms for Learning Mixtures of Separated 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