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..
Locally Private Learning without Interaction Requires Separation
Authors: Amit Daniely, Vitaly Feldman
NeurIPS 2019 | Venue PDF | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | We prove that only classes that have polynomially small margin complexity can be efficiently PAC learned by a non-interactive LDP algorithm. Our lower bound implies that two natural and well-studied classes of functions: linear separators and decision lists require an exponential number of samples to learn non-interactively. This gives the first example of a natural problem that is significantly harder to solve without interaction and also resolves an open problem of Kasiviswanathan et al. [39]. We complement this lower bound with a new efficient learning algorithm whose complexity is polynomial in the margin complexity of the class. |
| Researcher Affiliation | Collaboration | Amit Daniely Hebrew University and Google Research Vitaly Feldman Google Research |
| Pseudocode | No | The paper does not contain structured pseudocode or algorithm blocks. |
| Open Source Code | No | The paper does not provide concrete access to source code for the methodology described in this paper. |
| Open Datasets | No | The paper does not provide concrete access information for a publicly available or open dataset used for its own experiments. It refers to abstract data distributions (e.g., 'i.i.d. from some unknown distribution P'). |
| Dataset Splits | No | The paper does not provide specific dataset split information needed to reproduce data partitioning, as it is a theoretical paper and does not conduct experiments with specific datasets. |
| Hardware Specification | No | The paper does not provide specific hardware details used for running its experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers needed to replicate the experiment. |
| Experiment Setup | No | The paper does not contain specific experimental setup details, as it is a theoretical paper and does not conduct empirical experiments. |