These labels were automatically added by AI and may be inaccurate. For details, see About Literature Database.
Abstract
Privately counting distinct elements in a stream is a fundamental data
analysis problem with many applications in machine learning. In the turnstile
model, Jain et al. [NeurIPS2023] initiated the study of this problem
parameterized by the maximum flippancy of any element, i.e., the number of
times that the count of an element changes from 0 to above 0 or vice versa.
They give an item-level $(\epsilon,\delta)$-differentially private algorithm
whose additive error is tight with respect to that parameterization. In this
work, we show that a very simple algorithm based on the sparse vector technique
achieves a tight additive error for item-level $(\epsilon,\delta)$-differential
privacy and item-level $\epsilon$-differential privacy with regards to a
different parameterization, namely the sum of all flippancies. Our second
result is a bound which shows that for a large class of algorithms, including
all existing differentially private algorithms for this problem, the lower
bound from item-level differential privacy extends to event-level differential
privacy. This partially answers an open question by Jain et al. [NeurIPS2023].