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 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(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 minimum separation at least O(√k) as well as an explicit upper bound on the Euclidean norm of the centers.