New Lower Bounds for Private Estimation and a Generalized Fingerprinting Lemma
Authors: Gautam Kamath, Argyris Mouzakis, Vikrant Singhal
NeurIPS 2022 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove new lower bounds for statistical estimation tasks under the constraint of (ε, δ)-differential privacy. First, we provide tight lower bounds for private covariance estimation of Gaussian distributions. We show that estimating the covariance matrix in Frobenius norm requires Ω(d2) samples, and in spectral norm requires Ω(d3/2) samples, both matching upper bounds up to logarithmic factors. If you are including theoretical results... Did you include complete proofs of all theoretical results? [Yes] See Appendices A-G. |
| Researcher Affiliation | Academia | Gautam Kamath Cheriton School of Computer Science University of Waterloo Waterloo, ON N2L 3G1, Canada g@csail.mit.edu Argyris Mouzakis Cheriton School of Computer Science University of Waterloo Waterloo, ON N2L 3G1, Canada amouzaki@uwaterloo.ca Vikrant Singhal Cheriton School of Computer Science University of Waterloo Waterloo, ON N2L 3G1, Canada vikrant.singhal@uwaterloo.ca |
| Pseudocode | Yes | For the full algorithm, see Algorithm 2, and for the propositions that formally establish the reduction see Lemma C.4 and Corollary C.5. (Referring to Algorithm 2 in Appendix C.1) and "Algorithm 1: CovarianceMatrixConstruction" (in Appendix C.1). |
| Open Source Code | No | The paper does not explicitly state that source code for its methodology is available or provide a link to a code repository. The reproducibility checklist states: 'Did you include the code, data, and instructions needed to reproduce the main experimental results (either in the supplemental material or as a URL)? [N/A]'. |
| Open Datasets | No | The paper is theoretical and focuses on proving lower bounds for statistical estimation tasks. It does not describe experiments using empirical datasets for training, validation, or testing, nor does it provide access information for any such datasets. |
| Dataset Splits | No | The paper is theoretical and focuses on proving lower bounds for statistical estimation tasks. It does not describe experiments using empirical datasets for training, validation, or testing, and therefore does not provide specific dataset split information. |
| Hardware Specification | No | The paper is purely theoretical and does not report on any computational experiments, thus no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is purely theoretical and does not describe any computational experiments or implementations, so it does not list any software dependencies with specific version numbers. |
| Experiment Setup | No | The paper is purely theoretical, presenting mathematical proofs and lower bounds, and therefore does not include details about an experimental setup, hyperparameters, or training configurations. |