Private estimation algorithms for stochastic block models and mixture models

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 algorithms for both weak recovery and exact recovery. Previously known algorithms achieving comparable guarantees required quasi-polynomial time. We complement these results with an information-theoretic lower bound that highlights how the guarantees of our algorithms are almost tight. For the latter, we design an ( , )-differentially private algorithm that recovers the centers of the -mixture when the minimum separation is at least ( 1/ √ ). For all choices of , this algorithm requires sample complexity (1) ( ) and time complexity ( ) ( ) . Prior work required either an additional additive Ω( log ) term in the minimum separation or an explicit upper bound on the Euclidean norm of the centers.