Privately Learning Mixtures of Axis-Aligned Gaussians
Journal Articles
Overview
Research
Additional Document Info
View All
Overview
abstract
We consider the problem of learning mixtures of Gaussians under the
constraint of approximate differential privacy. We prove that
$\widetilde{O}(k^2 d \log^{3/2}(1/\delta) / \alpha^2 \varepsilon)$ samples are
sufficient to learn a mixture of $k$ axis-aligned Gaussians in $\mathbb{R}^d$
to within total variation distance $\alpha$ while satisfying $(\varepsilon,
\delta)$-differential privacy. This is the first result for privately learning
mixtures of unbounded axis-aligned (or even unbounded univariate) Gaussians. If
the covariance matrices of each of the Gaussians is the identity matrix, we
show that $\widetilde{O}(kd/\alpha^2 + kd \log(1/\delta) / \alpha \varepsilon)$
samples are sufficient.
Recently, the "local covering" technique of Bun, Kamath, Steinke, and Wu has
been successfully used for privately learning high-dimensional Gaussians with a
known covariance matrix and extended to privately learning general
high-dimensional Gaussians by Aden-Ali, Ashtiani, and Kamath. Given these
positive results, this approach has been proposed as a promising direction for
privately learning mixtures of Gaussians. Unfortunately, we show that this is
not possible.
We design a new technique for privately learning mixture distributions. A
class of distributions $\mathcal{F}$ is said to be list-decodable if there is
an algorithm that, given "heavily corrupted" samples from $f\in \mathcal{F}$,
outputs a list of distributions, $\widehat{\mathcal{F}}$, such that one of the
distributions in $\widehat{\mathcal{F}}$ approximates $f$. We show that if
$\mathcal{F}$ is privately list-decodable, then we can privately learn mixtures
of distributions in $\mathcal{F}$. Finally, we show axis-aligned Gaussian
distributions are privately list-decodable, thereby proving mixtures of such
distributions are privately learnable.
