Characterizing the Sample Complexity of Pure Private Learners
Authors: Amos Beimel, Kobbi Nissim, Uri Stemmer
JMLR 2019 | Venue PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We give a combinatorial characterization of the sample size sufficient and necessary to learn a class of concepts under pure differential privacy. This characterization is analogous to the well known characterization of the sample complexity of non-private learning in terms of the VC dimension of the concept class. We introduce the notion of probabilistic representation of a concept class, and our new complexity measure Rep Dim corresponds to the size of the smallest probabilistic representation of the concept class. We show that any private learning algorithm for a concept class C with sample complexity m implies Rep Dim(C) = O(m), and that there exists a private learning algorithm with sample complexity m = O(Rep Dim(C)). |
| Researcher Affiliation | Academia | Amos Beimel EMAIL Ben-Gurion University Kobbi Nissim EMAIL Georgetown University Uri Stemmer EMAIL Ben-Gurion University |
| Pseudocode | No | The paper describes algorithms (like the exponential mechanism and learning algorithms) but does not present them in structured pseudocode or algorithm blocks. It contains definitions, theorems, lemmas, and proofs. |
| Open Source Code | No | The paper discusses its license (CC-BY 4.0) and attribution requirements for the publication itself, but there is no explicit statement or link indicating the release of source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and discusses 'concept classes' and 'distributions on Xd' abstractly. It does not refer to any specific named or publicly available datasets for empirical evaluation. |
| Dataset Splits | No | The paper does not present empirical experiments using specific datasets, therefore, there is no mention of dataset splits like training, testing, or validation sets. |
| Hardware Specification | No | The paper is theoretical and does not describe any experiments that would require specific hardware. Therefore, no hardware specifications are mentioned. |
| Software Dependencies | No | The paper is theoretical and does not describe any computational implementations. Consequently, there are no mentions of software dependencies with version numbers. |
| Experiment Setup | No | The paper is theoretical and does not include any experimental results or computational evaluations. Therefore, there is no 'Experimental Setup' section with hyperparameter values or training configurations. |