Locally Private Learning without Interaction Requires Separation
Authors: Amit Daniely, Vitaly Feldman
NeurIPS 2019 | Conference PDF | Archive PDF | Plain Text | 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. |