在隐私保护下高效学习高维高斯混合模型，样本量大幅减少且理论最优。
Sample-Efficient Private Learning of Mixtures of Gaussians
- 结合反敏感机制与分布压缩技术，设计私有学习算法。
- 仅需约 $kd^2 + k^{1.5}d^{1.75} + k^2d$ 个样本即可实现低总变差距离学习。
- 首次证明一维高斯混合学习的样本复杂度为线性于 $k$，适合高维数据隐私建模。
我们研究了在近似差分隐私约束下学习高斯混合模型的问题。证明了大约 $kd^2 + k^{1.5}d^{1.75} + k^2d$ 个样本足以在低总变差距离下学习任意 $k$ 个 $d$-维高斯混合模型，且满足差分隐私。该结果优于此前最佳成果 [AAL24b]（需约 $k^2d^4$ 样本），当 $d$ 远大于 $k^2$ 时可证明为理论最优。此外，我们给出了首个关于 $k$ 个一维高斯混合模型的最优样本复杂度边界。关键发现是：私有学习一维高斯混合模型的样本复杂度为 $k$ 的线性函数，而先前最优结果 [AAL21] 为 $k$ 的二次函数。算法利用反敏感机制 [AD20b, AD20a, HKMN23]、分布的样本压缩 [ABDH+20] 以及和集体积界等方法。
原文摘要 · Abstract (English)
We study the problem of learning mixtures of Gaussians with approximate differential privacy. We prove that roughly $kd^2 + k^{1.5} d^{1.75} + k^2 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^2 d^4$ samples) and is provably optimal when $d$ is much larger than $k^2$. Moreover, we give the first optimal bound for privately learning mixtures of $k$ univariate (i.e., $1$-dimensional) Gaussians. Importantly, we show that the sample complexity for privately learning mixtures of univariate Gaussians is linear in the number of components $k$, whereas the previous best sample complexity [AAL21] was quadratic in $k$. Our algorithms utilize various techniques, including the inverse sensitivity mechanism [AD20b, AD20a, HKMN23], sample compression for distributions [ABDH+20], and methods for bounding volumes of sumsets.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。