The Limits of Differential Privacy in Online Learning
Authors: Bo Li, Wei Wang, Peng Ye
NeurIPS 2024 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this work, we investigate the fundamental limits of differential privacy in online learning algorithms and present evidence that separates three types of constraints: no DP, pure DP, and approximate DP. We first describe a hypothesis class that is online learnable under approximate DP but not online learnable under pure DP under the adaptive adversarial setting. We then prove that any private online learner must make an infinite number of mistakes for almost all hypothesis classes. |
| Researcher Affiliation | Academia | Bo Li Wei Wang Peng Ye Department of Computer Science and Engineering The Hong Kong University of Science and Technology Hong Kong SAR, China |
| Pseudocode | Yes | Algorithm 1: Adaptive adversary for POINTd; Algorithm 2: Constructing S0, S1, . . . , Sm and t1, . . . , tm 1; Algorithm 3: Distinguishing S1, . . . , Sm; Algorithm 4: Above Threshold; Algorithm 5: Learning point functions over N; Algorithm 6: Learning threshold functions over [d]; Algorithm 7: DP-OPE against adaptive adversaries; Algorithm 8: Learning complementary hypotheses |
| Open Source Code | No | The paper does not include experiments requiring code. |
| Open Datasets | No | The paper does not include experiments requiring code. |
| Dataset Splits | No | The paper does not include experiments requiring code. |
| Hardware Specification | No | The paper does not include experiments. |
| Software Dependencies | No | The paper does not include experiments. |
| Experiment Setup | No | The paper does not include experiments. |