Private estimation algorithms for stochastic block models and mixture models
share
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.
READ FULL TEXT