Sample-Efficient Private Learning of Mixtures of Gaussians

We would like to thank the reviewer for their detailed feedback. In the following we answer the raised questions.

1. To clarify this further, the goal of density estimation is to learn the overall distribution’s PDF (up to low total variation distance), whereas in parameter estimation we want to learn every Gaussian component’s mean and covariance. One can construct two different Gaussian mixtures with very similar PDFs, but with somewhat different components (in which case identifying the wrong Gaussian mixture is OK for density estimation but not for parameter estimation). We will add this discussion to the paper.

2. For the sake of clarity of the presentation we tried to avoid writing down the exact dependency on beta in our bounds. However, note that the sample complexity scales at most logarithmically with 1/beta. The reason is that any method that achieves a failure probability of < 0.50 can be boosted to have failure probability of beta with a mild (logarithmically in 1/beta) increase in the sample complexity. This can be done by running the estimator on log(1/beta) data sets, and then simply running private hypothesis selection on the outcomes. We will add this discussion to the paper.

3. The choice of $n^{100}$ is just for convenience, and the effect of the constant 100 on the sample complexity is negligible (i.e., the sample complexity does not change in terms of the $\tilde{O}(.)$ notation). In Line 157, we mention that the sample complexity (after the crude approximation is obtained) depends on $\log R$, so even if $R = n^{100}$ this only blows up the sample complexity by $\log(n^{100}) = O(\log n)$.

4. Indeed, the $\tilde{\Sigma}$ is not unique, and the volume in Theorem 2.1 refers to the volume (i.e., Lebesgue measure) of the set of all possible $\tilde{\Sigma}$, for a fixed choice of dataset $X$. As an example, if $d = 1$ (in which case $\tilde{\Sigma}$ is just a variance) and every $\tilde{\Sigma}$ between $1$ and $4$ satisfies the score function, then the volume is 3. In general, we use higher dimensional Lebesgue measure (see Appendix C.1) to formally define the volume.

5 and 6. We thank the reviewer for their suggestions about improving the presentation of the paper and the appendices. We will use the remaining space to give more details in the main paper (and will also improve the structure of the appendix to make it easier to navigate)

7. We would like to emphasize that our work focuses on the fundamental problem of determining the number of samples for learning a GMM privately. However, our algorithm is not computationally efficient. Note that even without privacy, it is not known whether GMMs can be learned efficiently in high dimensions. This remains an intriguing open problem in the field of computational statistics.

Minor comments:

Regarding Theorem 1.5, we note that $c^*$ will be some universal constant, so it can be hidden in the $\Omega$ notation. The intuition in Section 2.1 holds as long as $n \gg k$, so it also holds if $n \gg k^2$. In lines 203-204, the use of $k$ is a mistake - we will use $t$ (or another variable) to avoid confusing it with the number of components $k$. For all other comments, we agree with you and we will incorporate your feedback.

We would like to thank the reviewer for their detailed feedback. We would like to emphasize that our bound does not depend on the condition number of the covariance matrix nor on the magnitude of the mean, i.e., our sample complexity has no dependence on $\log R$. (Otherwise, proving an upper bound would have been easy, e.g., by using private hypothesis selection on a finite cover for the set of possible mixtures.) We agree with the comments about the presentation of the paper, and will improve it in the next version (including adding more details about the definitions,lemmas, or proof sketches in the main paper). In the following we answer the raised questions.

1. To explain the $\frac{k^2 d}{\alpha}$ term, the point is that for the private algorithm to work, we need two things. First, the private algorithm finds a covariance matrix (or more precisely, a mean-covariance pair $(\tilde{\mu}, \tilde{\Sigma})$) with low score (see Line 932 and the above few lines for the definition). Second, if a mean-covariance pair has a low score, then it is actually similar to a true mixture component $(\mu_i, \Sigma_i)$. The term $\frac{d^{1.75} k^{1.5} \sqrt{\log (1/\delta)}}{\alpha \epsilon}$ is needed for the first part. However, the $\frac{k^2 d}{\alpha}$ term is needed for the second part: that any mean-covariance pair of low score is similar to some true mixture component (this is the goal of Proposition E.4 in our paper).

The reason for the $k^2$ dependence in this second term is nontrivial so here’s a high-level intuition. Given a dataset $X$ and mean-covariance pair $(\tilde{\mu}, \tilde{\Sigma})$, the score $S((\tilde{\mu}, \tilde{\Sigma}), X)$ is small if there exists roughly $\alpha/k$ fraction of data points that “look like” they came from $\mathcal{N}(\tilde{\mu}, \tilde{\Sigma})$. The point is that one can have one point come from each of $k$ different mixture components which, together, look like $k$ samples from a totally different Gaussian from any of the $k$ mixture components. As a result, we need to make sure we have more than $k^2/\alpha$ total points, because then an $\alpha/k$ fraction of the data points is more than $k$ total samples. We actually need an additional factor of $d$, because it turns out that we can even have $\Omega(d)$ points from each of the mixture components which look like $\Omega(kd)$ samples from a totally different Gaussian.

2. The only other known approach for privately learning unbounded and high-dimensional GMMs (density estimation) is [AAL24] that uses sample-and-aggregate. For the univariate setting (density estimation for GMMs with unbounded parameters), there is another approach that uses stability-based histograms [AAL21].

We would like to thank the reviewer for their detailed feedback. We are happy to add some description that puts everything together and explain where each of the terms come from, as suggested by the reviewer. In the following, we explain the terms in the sample complexity that the reviewer asked about.

To explain the $\frac{(k \log (1/\delta))^{1.5}}{\alpha \epsilon}$ term, we note that in the crude estimation part, the sample complexity (from applying Theorem C.3, the formal version of Theorem 2.1) also has an assumption (see the “Volume” bullet) that $n \ge \frac{\log (1/\delta_0)}{\epsilon_0 \cdot \eta^*}$. Here, $\epsilon_0, \delta_0$ represent the privacy terms for a single iteration of the crude estimation (to learn one parameter), and $\eta^*$ will represent the robustness threshold, and ends up being roughly $\alpha/k$. The reason the robustness threshold depends on $k$ like this is that each component on average has weight $1/k$, so you can corrupt $1/k$ fraction points and completely alter a component. Also, since we run the crude estimation $k$ times, we can use advanced composition to say that if each iteration was $(\epsilon_0, \delta_0) = (\frac{\epsilon}{\sqrt{k \log (1/\delta)}}, \frac{\delta}{k})$-DP, the overall algorithm is $(\epsilon, \delta)$-DP. With all of these parameters set, we precisely get $\frac{\log (1/\delta_0)}{\epsilon_0 \cdot \eta^*} = \Theta\left(\frac{(k \log (1/\delta))^{1.5}}{\alpha \epsilon}\right)$.

To explain the $\frac{k^2 d}{\alpha}$ term, the point is that for the private algorithm to work, we need two things. First, the private algorithm finds a covariance matrix (or more precisely, a mean-covariance pair $(\tilde{\mu}, \tilde{\Sigma})$) with low score (see Line 932 and the above few lines for the definition). Second, if a mean-covariance pair has a low score, then it is actually similar to a true mixture component $(\mu_i, \Sigma_i)$. The previous terms of $\frac{d^{1.75} k^{1.5} \sqrt{\log (1/\delta)}}{\alpha \epsilon}$ and $\frac{(k \log (1/\delta))^{1.5}}{\alpha \epsilon}$ are needed for the first part. However, the $\frac{k^2 d}{\alpha}$ term is needed for the second part: that any mean-covariance pair of low score is similar to some true mixture component (this is the goal of Proposition E.4 in our paper).

The reason for the $k^2$ dependence is nontrivial so here’s a high-level intuition. Given a dataset $X$ and mean-covariance pair $(\tilde{\mu}, \tilde{\Sigma})$, the score $S((\tilde{\mu}, \tilde{\Sigma}), X)$ is small if there exists roughly $\alpha/k$ fraction of data points that “look like” they came from $\mathcal{N}(\tilde{\mu}, \tilde{\Sigma})$. The point is that one can have one point come from each of $k$ different mixture components which, together, look like $k$ samples from a totally different Gaussian from any of the $k$ mixture components. As a result, we need to make sure we have more than $k^2/\alpha$ total points, because then an $\alpha/k$ fraction of the data points is more than $k$ total samples. We actually need an additional factor of $d$, because it turns out that we can even have $\Omega(d)$ points from each of the mixture components which look like $\Omega(kd)$ samples from a totally different Gaussian.

We would like to thank the reviewer for their detailed feedback. We now address some of the issues/questions raised by the reviewer.

Note that the algorithm for the univariate case (Section F) is completely different from the multivariate case (Section E). The algorithm in the univariate case requires us to order the data points from smallest to largest, which doesn’t make sense in high dimensions. So, it only works for $d = 1$. We could use the multivariate algorithm when $d = 1$ as well, but we would get a worse dependence on $k$ (more specifically, we would get $k^2$ in the bound rather than linear dependence on $k$).

We are happy to list our results, along with previous results, in a table so that one can easily compare our work with previous work (as well as compare upper/lower bounds). We also agree that a final definition combining Definitions 1.1 and 1.2 would be useful, we will add that immediately after these two definitions.