Notice: This website is continuously updated as new conference proceedings and journal volumes are published. Consequently, the figures presented here may differ from those reported in our publications.
A brief overview of our methodology is provided on the Methods page, along with references to publications documenting our approach and links to the code and data used in each study.
The reproducibility variables underlying each score are classified using an automated LLM-based pipeline, validated against a manually labeled dataset. LLM-based classification introduces uncertainty and potential bias; scores should be interpreted as estimates.
Sample-Efficient Private Learning of Mixtures of Gaussians
Authors: Hassan Ashtiani, Mahbod Majid, Shyam Narayanan
NeurIPS 2024 | Venue PDF | LLM Run Details | Input Tokens: 55,319 Total number of tokens sent to the LLM as input for this paper's analysis. | Output Tokens: 2,351 Total number of tokens produced by the LLM (including reasoning/thinking tokens) for this paper's analysis.
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our work purely focuses on sample complexity, and as noted in Theorems 1.4 and 1.5, they do not have polynomial time algorithms. We note that the previous works of [AAL21, AAL24b] also do not run in polynomial time. Indeed, there is reason to believe that even non-privately, it is impossible to learn GMMs in polynomial time (in terms of the optimal sample complexity) [DKS17, BRST21, GVV22].Our results are on theoretical guarantees on the sample complexity of privately learning Mixtures of Gaussians. We do not provide any efficient or practical algorithms, and focus on statistical guarantees. |
| Researcher Affiliation | Collaboration | Hassan Ashtiani Mc Master University EMAIL Mahbod Majid MIT EMAIL Shyam Narayanan Citadel Securities EMAIL |
| Pseudocode | Yes | Algorithm 1: FINE-ESTIMATE(X1, X2, . . . , Xn Rd, d, k, k , ε, α, G, {(ˆµj, ˆΣj)}j k ) Algorithm 2: ESTIMATE(X1, X2, . . . , Xn+n Rd, k, ε, δ, α) Algorithm 3: ESTIMATE1D(X1, X2, . . . , Xn+n R, k, ε, δ, α) |
| Open Source Code | No | Our results are on theoretical guarantees on the sample complexity of privately learning Mixtures of Gaussians. We do not provide any efficient or practical algorithms, and focus on statistical guarantees. Our paper does not release any new assets. |
| Open Datasets | No | No experiments. |
| Dataset Splits | No | No experiments. |
| Hardware Specification | No | No experiments. |
| Software Dependencies | No | No experiments. |
| Experiment Setup | No | No experiments. |