# Private estimation algorithms for stochastic block models and mixture models

arXiv: https://arxiv.org/abs/2301.04822 · HTML: https://mlsanity.com/paper/2301.04822/

## Key facts

- Cited by 21 papers in the map (data through 14 Oct 2026).
- Builds on 36 of its 66 references that are in the map.
- First posted on arXiv 11 Jan 2023.

## Builds on (most cited first, 30 of 36)

- [Community Detection and Stochastic Block Models](https://mlsanity.com/paper/1703.10146/) (2017)
- [Robust Estimators in High Dimensions without the Computational Intractability](https://mlsanity.com/paper/1604.06443/) (2016)
- [Agnostic Estimation of Mean and Covariance](https://mlsanity.com/paper/1604.06968/) (2016)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Finite Sample Differentially Private Confidence Intervals](https://mlsanity.com/paper/1711.03908/) (2017)
- [Recent Advances in Algorithmic High-Dimensional Robust Statistics](https://mlsanity.com/paper/1911.05911/) (2019)
- [Learning from Untrusted Data](https://mlsanity.com/paper/1611.02315/) (2016)
- [Mixture Models, Robustness, and Sum of Squares Proofs](https://mlsanity.com/paper/1711.07454/) (2017)
- [Exact Recovery in the Stochastic Block Model](https://mlsanity.com/paper/1405.3267/) (2014)
- [Differential privacy and robust statistics in high dimensions](https://mlsanity.com/paper/2111.06578/) (2021)
- [Efficient Mean Estimation with Pure Differential Privacy via a Sum-of-Squares Exponential Mechanism](https://mlsanity.com/paper/2111.12981/) (2021)
- [Community detection thresholds and the weak Ramanujan property](https://mlsanity.com/paper/1311.3085/) (2013)
- [Private and polynomial time algorithms for learning Gaussians and beyond](https://mlsanity.com/paper/2111.11320/) (2021)
- [Private Robust Estimation by Stabilizing Convex Relaxations](https://mlsanity.com/paper/2112.03548/) (2021)
- [A Proof Of The Block Model Threshold Conjecture](https://mlsanity.com/paper/1311.4115/) (2013)
- [FriendlyCore: Practical Differentially Private Aggregation](https://mlsanity.com/paper/2110.10132/) (2021)
- [On Learning Mixtures of Well-Separated Gaussians](https://mlsanity.com/paper/1710.11592/) (2017)
- [Clustering Mixtures with Almost Optimal Separation in Polynomial Time](https://mlsanity.com/paper/2112.00706/) (2021)
- [Differentially Private Algorithms for Learning Mixtures of Separated Gaussians](https://mlsanity.com/paper/1909.03951/) (2019)
- [Minimax Rates of Community Detection in Stochastic Block Models](https://mlsanity.com/paper/1507.05313/) (2015)
- [Consistency Thresholds for the Planted Bisection Model](https://mlsanity.com/paper/1407.1591/) (2014)
- [Robust Sparse Mean Estimation via Sum of Squares](https://mlsanity.com/paper/2206.03441/) (2022)
- [Community detection in sparse networks via Grothendieck's inequality](https://mlsanity.com/paper/1411.4686/) (2014)
- [How Robust are Reconstruction Thresholds for Community Detection?](https://mlsanity.com/paper/1511.01473/) (2015)
- [Sparse PCA: Algorithms, Adversarial Perturbations and Certificates](https://mlsanity.com/paper/2011.06585/) (2020)
- [Robust recovery for stochastic block models](https://mlsanity.com/paper/2111.08568/) (2021)
- [Private Graphon Estimation for Sparse Graphs](https://mlsanity.com/paper/1506.06162/) (2015)
- [Differentially-Private Clustering of Easy Instances](https://mlsanity.com/paper/2112.14445/) (2021)
- [Differentially Private Community Detection for Stochastic Block Models](https://mlsanity.com/paper/2202.00636/) (2022)
- [Revealing Network Structure, Confidentially: Improved Rates for Node-Private Graphon Estimation](https://mlsanity.com/paper/1810.02183/) (2018)

## Built on by (most cited first, 21 of 21)

- [Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models](https://mlsanity.com/paper/2303.04288/) (2023)
- [Private Distribution Learning with Public Data: The View from Sample Compression](https://mlsanity.com/paper/2308.06239/) (2023)
- [A Bias-Accuracy-Privacy Trilemma for Statistical Estimation](https://mlsanity.com/paper/2301.13334/) (2023)
- [Differentially-Private Hierarchical Clustering with Provable Approximation Guarantees](https://mlsanity.com/paper/2302.00037/) (2023)
- [A Polynomial Time, Pure Differentially Private Estimator for Binary Product Distributions](https://mlsanity.com/paper/2304.06787/) (2023)
- [Mixtures of Gaussians are Privately Learnable with a Polynomial Number of Samples](https://mlsanity.com/paper/2309.03847/) (2023)
- [Differentially private exact recovery for stochastic block models](https://mlsanity.com/paper/2406.02644/) (2024)
- [Private graphon estimation via sum-of-squares](https://mlsanity.com/paper/2403.12213/) (2024)
- [A Differentially Private Clustering Algorithm for Well-Clustered Graphs](https://mlsanity.com/paper/2403.14332/) (2024)
- [Private Edge Density Estimation for Random Graphs: Optimal, Efficient and Robust](https://mlsanity.com/paper/2405.16663/) (2024)
- [Agnostic Private Density Estimation for GMMs via List Global Stability](https://mlsanity.com/paper/2407.04783/) (2024)
- [On the Price of Differential Privacy for Spectral Clustering over Stochastic Block Models](https://mlsanity.com/paper/2505.05816/) (2025)
- [Contrastive Explainable Clustering with Differential Privacy](https://mlsanity.com/paper/2406.04610/) (2024)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)
- [Computation-Utility-Privacy Tradeoffs in Bayesian Estimation](https://mlsanity.com/paper/2603.18254/) (2026)
- [PrIsing: Privacy-Preserving Peer Effect Estimation via Ising Model](https://mlsanity.com/paper/2401.16596/) (2024)
- [Sample-Efficient Private Learning of Mixtures of Gaussians](https://mlsanity.com/paper/2411.02298/) (2024)
- [Signal Recovery from Random Dot-Product Graphs Under Local Differential Privacy](https://mlsanity.com/paper/2504.17274/) (2025)
- [Differentially Private Spectral Graph Clustering: Balancing Privacy, Accuracy, and Efficiency](https://mlsanity.com/paper/2510.07136/) (2025)
- [Privacy utility trade offs for parameter estimation in degree heterogeneous higher order networks](https://mlsanity.com/paper/2602.03948/) (2026)
- [Near-optimal node-private community estimation in polynomial-time](https://mlsanity.com/paper/2607.09441/) (2026)

## Abstract (arXiv)

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.