Research map / Federated learning and privacy / Differential privacy
Sample-Efficient Private Learning of Mixtures of Gaussians
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Shows that about kd^2 + k^1.5 d^1.75 + k^2 d samples suffice for (eps,delta)-DP density estimation of k arbitrary Gaussians, and k/alpha^2-type linear-in-k bounds for univariate mixtures, via robustness-to-privacy, sample compression and a sorted-differences histogram.
Problem
Private density estimation (total variation learning) of mixtures of k unrestricted Gaussians in d dimensions, where prior sample complexity was k^2 d^4 and univariate was quadratic in k.
Approach
Combine the robustness-to-privacy conversion (inverse-sensitivity-style exponential mechanism) with a score function based on robust Gaussian covariance estimation on compressed subsets, plus a sorted-consecutive-differences private histogram for the univariate case, and then private hypothesis selection to finish.
Key results
- Upper bound of roughly kd^2 + k^1.5 d^1.75 + k^2 d samples for (eps,delta)-DP learning of k arbitrary d-dimensional Gaussians, improving the prior k^2 d^4.
- Univariate mixtures learnable with O~(k/alpha^2 + k log(1/delta)/(alpha eps)) samples, linear in k versus previous quadratic bound.
- Lower bound Omega~(kd^2/alpha^2 + kd^2/(alpha eps) + k log(1/delta)/(alpha eps)) matches the univariate upper bound up to log factors.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use the proposed private learner instead of the previous private GMM learner | Private learning of arbitrary full-dimensional Gaussian mixtures · GMMs (d dimensions) | sample complexity: \widetilde{O}\left(\frac{k^2 d^4 + kd^2 \log(1/delta)}{\alpha^2 \varepsilon} + \frac{kd \log(1/delta)}{\alpha^3 \varepsi | Helped |
| Use the proposed private learner instead of the previous private univariate GMM learner | Private learning of arbitrary univariate Gaussian mixtures · Univariate GMMs | sample complexity: \widetilde{O}\left(\frac{k^2 \log^{3/2}(1/\delta)}{\alpha^2 \varepsilon}\right) -> \widetilde{O}\left(\frac{k}{\alpha^2} | Helped |
Surprising findings
- The conjectured lower bound from prior work is refuted in the univariate case when delta is extremely small.
Limitations
- Algorithms are computationally inefficient (exponential time).
- Realizable setting only; not robust to agnostic corruption.
- Only the sample complexity is optimized; the general-d bound is not matched by the lower bound in all regimes.
Experimental setup
Metrics: sample complexity (theoretical) total variation distance
Baselines: Aden-Ali, Ashtiani, Kamath (k^2 d^4 private GMM learner) Ashtiani et al. univariate/axis-aligned private GMM bound
Builds on: inverse sensitivity mechanism robustness-to-privacy conversion (Hopkins et al.) private hypothesis selection advanced composition truncated Laplace mechanism
Closest papers by meaning
- Differentially Private Algorithms for Learning Mixtures of Separated Gaussians (NeurIPS 2019 · similarity 0.94)
- Polynomial Time and Private Learning of Unbounded Gaussian Mixture Models (ICML 2023 · similarity 0.93)
- Privately Learning Mixtures of Axis-Aligned Gaussians (NeurIPS 2021 · similarity 0.93)
- Private Distribution Learning with Public Data: The View from Sample Compression (NeurIPS 2023 · similarity 0.93)
- Tractable MCMC for Private Learning with Pure and Gaussian Differential Privacy (ICLR 2024 · similarity 0.87)
- Exactly Minimax-Optimal Locally Differentially Private Sampling (NeurIPS 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.