Sample-Efficient Private Learning of Mixtures of Gaussians

Summary

The paper studies the important problem of private learning of the Gaussian mixture model to estimate the underlying distribution within a desired total variation distance. By combining different techniques, the authors succeed in deriving bounds that are of quadratic dimension, thus significantly improving the existing results.

Strengths

The paper contains several new results that significantly improve the state of the art. These include i) Theorem 1.3, which establishes a bound with quadratic complexity for any dimension, ii) Theorem 1.4, which proposes an improved bound for $d=1$, showing that the sample complexity can be linear in the number of components, iii) Theorem 1.5, which proposes a lower bound on the sample complexity. The latter, combined with Theorem 1.4, shows the optimality of the established bounds for the univariate Gaussian distributions. In addition, the paper is generally well and smoothly written.

Weaknesses

- The paper could benefit from some numerical verifications of the results/algorithms used. - The appendix section is poorly organized. Without an outline and proof, it is difficult to follow such a long appendix.

Questions

1. It would be better to explain more the difference between density estimation and parameter estimation. 2. How do the bounds of Theorems 1.3, 1.4., and 1.5 behave with respect to the failure probability $\beta$ order-wise? 3. Can the authors discuss the assumption $R=n^{100}$ (line 160) a bit more? Why does it depend on $n$ (and not $k$ or $d$?)? Also, is the polynomial dependence restrictive? 4. The first sentence of the informal statement of Theorem 2.1. does not seem rigorous enough. Is such a $\tilde{\Sigma}$ unique? I don't think so. Then, if not, which choice of $\tilde{\Sigma}$ is taken into account when computing $V_{\eta}(\mathbf{X})$? Probably maximum volume? 5. The appendix sections are very difficult to follow. There should be a detailed outline at the beginning to guide the reader as to what each appendix deals with. Also, there should be sufficient references in the main text. For example, after the informal statement of Theorem 2.1., it should be clearly stated where the full statement and proof can be found. Similarly, after each paragraph (e.g., Section 2.1) or after each mentioned previously established result (e.g., advanced composition theorem), there should be an exact pointer to where the complete version can be found in the appendices. 6. Since the submission was allowed for 9 pages, the authors had 1.5 more pages. I think some material from the appendices, for example the algorithms used to privately learn GMM, could be moved to the main text. 7. Finally, what is missing the most is the experimental section. If I'm not mistaken, this should be easy to do. Although not all theoretical work requires experimental verification, I believe that if the experiments verify the theoretical finding, this would greatly increase the importance of the results. Minor comments: - Line 52: it is better to add "The parameters $\alpha$ and $\beta$...". - The constant $c^*$ in Theorem 1.5. does not appear in the bound. - In the first paragraph of Section 2.1, it is mentioned that "... as we can finish the procedure with hypothesis selection, as discussed above". However, hypothesis selection has not been sufficiently discussed. - Is it true that the intuition given in Section 2.1. holds if $ n \gg k^2$? - Typo line 178 (a a) - Is $k$ in lines 203-204 the number of components in the Gaussian mixture? Why does this statement ("if we altered $k$ data points...") only hold for $k$ changes?

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

NA

Summary

This paper investigates the sample complexity of privately learning mixtures of Gaussians. The authors achieve a sample complexity of approximately $O(kd^2+k^{1.5}d^{1.75}+k^2d)\log R$ where $R$ is an upper bound on the condition number of the covariance matrix and the norm of the mean. This result improves upon the previous best bound of $O(k^2d^4)$. Additionally, they constructed a lower bound of $\Omega(kd^2+k\log(1/\delta)/\epsilon)$, which refutes a conjecture from prior work, and they achieve optimal sample complexity when $d=1$.

Strengths

The improvement in sample complexity is significant. The paper provides a thorough technical overview of the upper bound, detailing the incorporation of sample compression and the methods used to enhance dimension independence within the robustness-to-privacy conversion technique.

Weaknesses

The paper is technically dense, making it challenging to understand and verify all the details. The authors do not fully utilize the page limit, which could have been used to explain the techniques more clearly. The technique for establishing the lower bound is not discussed in the main body of the paper. Including formal definitions and crucial lemmas in the main text could help readers better understand the key ideas. For instance, the definition of volume was unclear until I consulted the appendix.

Questions

1. Where does the $k^2$ term come from in the upper bound? 2. Are there alternative methods to address this problem that do not rely on the robustness-to-privacy conversion technique?

Rating

6

Confidence

3

Soundness

3

Presentation

2

Contribution

3

Limitations

Yes

Summary

This works focuses on the task of density estimation of a mixture of Gaussians under the restriction of differential privacy. Unlike parameter estimation, density estimation does not require accurately estimating the mixture's parameters, but instead bounds the total variation distance between estimated and true distributions. This task can be achieved even without any boundedness or separation assumptions on the parameters of the components. This task is known to require sample size of $O(k d^{2}/\alpha^{2})$ even in the non-private setting, where $k$ is the number of components, $d$ is the dimension, $\alpha$ is the bound on the TV distance, and the $O$ notation ignores logarithmic factors. In the private setting, previous work [1] achieved $\alpha$ accuracy guarantee under $(\epsilon, \delta)$-DP with $O(k^{2} d^{4}/\alpha^{2} \epsilon)$ (the exact bound includes several other terms that depend on $\log(1/\delta)$ as well). This work provides an improved bound, reducing the dependence on the parameters to $O \left(\frac{k d^{2}}{\alpha^{2}} + \frac{k d^{2}}{\alpha \epsilon} \right)$ in the high dimensional regime, $O \left(\frac{k}{\alpha^{2}} + \frac{k \cdot \log(1/\delta)}{\alpha \epsilon} \right)$ in the univariate setting, and lower bounds which asymptotically match the upper bound in the univariate case and nearly match it in the multivariate one. The proposed algorithm relays on first achieving crude estimation of the parameters and then using hypothesis selection to improve the estimation. The crude estimation is achieved using robust GMM estimation techniques and robusteness-to-privacy conversion, based on an inverse sensitivity-like instantiation of the exponential mechanism. This method is computationally inefficient. [1] Mohammad Afzali, Hassan Ashtiani, and Christopher Liaw. Mixtures of gaussians are privately learnable with a polynomial number of samples. In Algorithmic Learning Theory, pages 1–27. PMLR, 2024.

Strengths

The results presented in this work provide a significant improvement over the previously known ones. Though the proof technique is highly involved, the authors presented the proof outline in a relatively intuitive way, and provided motivation for the various steps it includes.

Weaknesses

Despite the great work done by the authors and my best efforts, I was not able to follow up all the proof structure. In particular, I could not find the justification for some of terms that appeared in the bound presented on Theorem 1.3. It seems to me like a section that "puts everything together" will be of great benefit. I will try to describe my current understanding and existing gaps. To the best of my understanding: * The $\frac{k d^{2}}{\alpha^{2}}$ and $\frac{k d^{2}}{\alpha \epsilon}$ were explained at the "Reducing to “crude approximation”" section, and they represent the sample size required to accurately and privately learn the GMM given some crude estimation of its components, using hypothesis selection method. * The $\frac{d^{1.75} k^{1.5} \sqrt{\log(1/\delta)}}{\alpha \epsilon}$ was explained at the "Improving Dimension Dependence" section, where $\frac{d^{1.75} k}{\alpha \epsilon}$ results from the fact $O\left(\frac{d^{1.75} k}{c \epsilon} \right)$ points are required to get the crude estimation of the parameters of a single component under $c$-robustness, which then can be translated to a DP estimation with $\alpha$ accuracy using rubousteness-to-privacy conversion techniques (Theorem 2.1), and the additional $\sqrt{k \cdot \log(1/\delta)}$ term results from advanced composition over $k$ components. * I failed to understand where the additional two terms ($\frac{(k \cdot \log(1/\delta))^{1.5}}{\alpha \epsilon}$ and $\frac{k^{2} d}{\alpha}$) come from, and I suspect they were accumulated at some point during the rubousteness-to-privacy transformation.

Questions

As I mentioned before, I will find an additional section that brings all the components together to outline the final proof method, focusing on the final achieved bound, to be very useful.

Rating

6

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

N/A

Summary

The paper studies the problem of learning a mixture of $k$ $d$-dimensional Gaussians using a differentially private mechanism with respect to the samples. It provides an improved sample complexity which has asymptotically optimal dependence on the dimension $d$ for small $k$, the lower bound is also given by the paper. Additionally, for $d=1$ the paper provides optimal sample complexity. The paper follows a high level approach of obtaining crude approximations of the mean and covariances of the component Gaussians, which can be used to reduce – using a net based argument – the problem to private hypothesis selection for which existing algorithm (needing only log the size of the net number of samples) can be used. To obtain the crude approximations respecting the DP guarantee, the paper uses a variant of the exponential mechanism with a carefully constructed scoring function measuring the distance between the a candidate Gaussian and any “heavy” component of Gaussian mixture. This uses a number of samples depending on the size of the sample set $n$ and the dimensionality the hypotheses $d^2$. A naive approach fails due to the blowup incurred, and the paper utilizes sample compression to reduce the dependence to $O(d\\log n)$ and improves the dimensionality dependence to $O(d)$ via an estimation argument. The above is outlined in more detail in the main paper and proved formally in the appendices. While all the details have not been verified by the reviewer, the approach taken by the paper seems correct.

Strengths

1. The paper proves improved (and in some cases optimal) sample complexity for privately learning Gaussian mixtures. 2. The paper uses a novel crude approximation based approach paired with existing algorithm for private hypothesis selection. 3. The paper leverages inverse sensitivity mechanisms for decoding the crude approximations, techniques for sample compression, and combines them with a way to improve the dimensionality dependence. 4. The main result as well the one for univariate case and the lower bound together constitute notable progress on a well studied problem. 5. The paper is well written and the provided roadmap greatly aids the understanding.

Weaknesses

1. The sample complexity does not match the lower bound in the dependence on $k$. 2. The degradation on the dependence on $k$ from the univariate to the multi-variate case is not explained in the main paper. 3. The details of the various technical parts are tedious and could be alleviated by better presentation, e.g. by listing all the parameters and their dependencies in a table.

Questions

It will be useful to combine definitions 1.1 and 1.2 into a precise definition of privately learning GMMs.

Rating

7

Confidence

3

Soundness

3

Presentation

4

Contribution

3

Limitations

Yes, addressed.