Local Differential Privacy for Evolving Data
Authors: Matthew Joseph, Aaron Roth, Jonathan Ullman, Bo Waggoner
NeurIPS 2018 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | Our main result is an algorithm that takes data generated according to our model, guarantees a fixed level of local privacy ε that grows (up to a certain point) with the number of distributional changes rather than the number of epochs, and guarantees that the estimates released at the end of each epoch are accurate up to error that scales sublinearly in 1/ℓand only polylogarithmically with the total number of epochs T. Our method improves over the naïve solution of simply recomputing the statistic every epoch... Theorem 1.1 (Protocol for Bernoulli Means, Informal Version of Theorem 4.3). In the above model, there is an ε-differentially private local protocol that achieves the following guarantee: with probability at least 1 δ, while the total number of elapsed epochs t where some subgroup distribution has changed is fewer than ε min( L n ln(m T /δ),ln(T) n ℓ), the protocol outputs estimates pt where pt pt = O ln(T) |
| Researcher Affiliation | Academia | Matthew Joseph Computer and Information Science University of Pennsylvania majos@cis.upenn.edu Aaron Roth Computer and Information Science University of Pennsylvania aaroth@cis.upenn.edu Jonathan Ullman Computer and Information Sciences Northeastern University jullman@ccs.neu.edu Bo Waggoner Computer and Information Science University of Pennsylvania bowaggoner@gmail.com |
| Pseudocode | Yes | Algorithm 1 Global Algorithm: THRESH Algorithm 2 Local Subroutine: VOTE Algorithm 3 Local Subroutine: EST |
| Open Source Code | No | The paper does not provide any concrete access to source code for the methodology described. |
| Open Datasets | No | The paper describes a theoretical probabilistic model ('In the above model, there is an ε-differentially private local protocol...') rather than using publicly available datasets with concrete access information. |
| Dataset Splits | No | The paper does not provide specific dataset split information (exact percentages, sample counts, or detailed splitting methodology) as it focuses on theoretical analysis rather than empirical evaluation. |
| Hardware Specification | No | The paper does not describe any specific hardware used for running experiments. |
| Software Dependencies | No | The paper does not provide specific ancillary software details with version numbers. |
| Experiment Setup | No | The paper does not contain specific experimental setup details such as hyperparameter values or training configurations. |