Notice: 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. Full accuracy metrics and methodology are described in Coakley et alK. L. Coakley, T. Snelleman, H. Hoos, and O. E. Gundersen, "The embrace of open science: An analysis of a decade of AI research and 56 800 conference papers," Under Review, 2026..
Characterizing the Sample Complexity of Pure Private Learners
Authors: Amos Beimel, Kobbi Nissim, Uri Stemmer
JMLR 2019 | Venue PDF | 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. |