Differentially Private $L_2$-Heavy Hitters in the Sliding Window Model
Authors: Jeremiah Blocki, Seunghoon Lee, Tamalika Mukherjee, Samson Zhou
ICLR 2023 | Conference PDF | Archive PDF | Plain Text | LLM Run Details
| Reproducibility Variable | Result | LLM Response |
|---|---|---|
| Research Type | Theoretical | In this paper, we consider the problem of privately releasing the L2-heavy hitters in the sliding window model... To overcome these barriers, we introduce the first differentially private algorithm for L2-heavy hitters in the sliding window model... We then use smooth sensitivity and statistical distance arguments to show that we can add noise proportional to an estimation of the L2 norm. To the best of our knowledge, our techniques are the first to privately release statistics that are related to a sub-additive function in the sliding window model, and may be of independent interest to future differentially private algorithmic design in the sliding window model. Theorem 1.2. For any α (0, 1), c > 0, window parameter W on a stream of length m that induces a frequency vector f Rn in the sliding window model, and privacy parameter ε > 1000 log m W , there exists an algorithm such that: (1) (Privacy) The algorithm is (ε, δ)-differentially private for δ = 1 mc . (2) (Heavy-hitters) With probability at least 1 1 mc , the algorithm outputs a list L such that k L for each k [n] with fk α L2(f) and j / L for each j [n] with fj α (3) (Accuracy) With probability at least 1 1 mc , we simultaneously have |fk efk| α 4 L2(f) for all k L, where efk denotes the noisy approximation of fk output by the algorithm. (4) (Complexity) The algorithm uses O log7 m α6η4 bits of space and O log4 m α3η4 operations per update where η = max{1, ε}. |
| Researcher Affiliation | Academia | Jeremiah Blocki, Seunghoon Lee & Tamalika Mukherjee Purdue University West Lafayette, IN 47906, USA {jblocki,lee2856,tmukherj}@purdue.edu Samson Zhou UC Berkeley and Rice University Houston, TX 77005, USA samsonzhou@gmail.com |
| Pseudocode | Yes | Algorithm 1 Smooth histogram (Braverman & Ostrovsky, 2010) and Algorithm 2 Differentially private sliding window algorithm for L2-heavy hitters |
| Open Source Code | No | The paper does not provide an explicit statement or link to open-source code for the described methodology. |
| Open Datasets | No | The paper is theoretical and does not use or provide concrete access information for any publicly available or open datasets for training or evaluation. |
| Dataset Splits | No | The paper does not describe empirical experiments and therefore does not specify training, validation, or test dataset splits. |
| Hardware Specification | No | The paper does not describe empirical experiments and therefore does not provide any specific hardware specifications. |
| Software Dependencies | No | The paper does not describe empirical experiments and therefore does not provide specific software dependencies with version numbers. |
| Experiment Setup | No | The paper does not describe empirical experiments and therefore does not provide details on experimental setup or hyperparameters. |