Sample-Efficient Private Learning of Mixtures of Gaussians

We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly kd² + k^1.5d^1.75 + k²d samples suffice to learn a mixture of k arbitrary d-dimensional Gaussians up to low total variation distance, with differential privacy. Our work improves over the previous best result [AAL24b] (which required roughly k²d⁴ samples) and is provably optimal when d is much larger than k². Moreover, we give the …