Constant Matters: Fine-grained Error Bound on Differentially Private Continual Observation
Authors: Hendrik Fichtenberger, Monika Henzinger, Jalaj Upadhyay
ICML 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Experimental | We empirically evaluated algorithms for two problems, namely continual counting and continual top-1 statistic, i.e. the frequency of the most-frequent element in the histogram. As the focus of this paper is on specifying the exact constants beyond the asymptotic error bound on differentially private counting, we do not make any assumption on the data or perform no post-processing on the output. The main goal of our experiments is to compare the additive error of (1) our mechanism and (2) the binary mechanism instantiated with Gaussian noise (i.e., the binary mechanism that achieves (ϵ, δ)-differential privacy). |
| Researcher Affiliation | Collaboration | 1Google Zurich, Switzerland 2Institute of Science and Technology Austria (ISTA), Klosterneuburg, Austria 3Rutgers University, USA. |
| Pseudocode | Yes | Algorithm 1 FACTORIZATION(Mcount) |
| Open Source Code | No | The paper does not provide any explicit statement or link indicating that the source code for the described methodology is open-source or publicly available. |
| Open Datasets | No | The paper describes generating its own data streams for experiments ('We generated a stream of T = 2^16 Bernoulli random variables Ber(p)', 'We generated a stream of 2048 elements from a universe of 20 items using Zipf’s law (Zipf, 2016)'). It does not use or provide access information for a pre-existing publicly available dataset. |
| Dataset Splits | No | The paper evaluates an algorithm rather than training a machine learning model, and thus does not describe training, validation, or test dataset splits in the typical sense of a machine learning pipeline. It describes running repetitions for confidence but not data partitioning for model tuning or evaluation. |
| Hardware Specification | No | The paper does not provide specific details about the hardware used to run the experiments, such as CPU/GPU models, memory, or cloud computing specifications. |
| Software Dependencies | No | The paper does not provide specific software dependencies, including their version numbers, that are needed to replicate the experiment. |
| Experiment Setup | Yes | We ran both the binary tree mechanism and our matrix mechanism for 10^6 repetitions and took the average of the outputs of these executions. ... For 8 different values of p, namely for every p ∈ {2^-4, 2^-5, 2^-6, 2^-7, 2^-8, 2^-9, 2^-10, 0}, we generated a stream of T = 2^16 Bernoulli random variables Ber(p). ... We generated a stream of 2048 elements from a universe of 20 items using Zipf’s law (Zipf, 2016). ... for ϵ = 0.5, δ = 10^-10 and ϵ = 0.1, δ = 10^-10. |