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 k-mixture when the minimum separation is at least O(k1/t t). For all choices of t, this algorithm requires sample complexity n kO(1)dO(t) and time complexity (nd)O(t). Prior work required either an additional additive Ω( logn) term in the minimum separation or an explicit upper bound on the Euclidean norm of the centers.