Benchmarking the Utility of w-event Differential Privacy Mechanisms - When Baselines Become Mighty Competitors

The 𝑤-event framework is the current standard for ensuring differential privacy on continuously monitored data streams. Following the proposition of 𝑤-event differential privacy, various mechanisms to implement the framework were proposed. Their comparability in empirical studies is vital for both practitioners to choose a suitable mechanism and researchers to identify current limitations and propose novel mechanisms. By conducting a literature survey, we observe that the results of existing studies are hardly comparable and partially intrinsically inconsistent. To this end, we formalize an empirical study of 𝑤-event mechanisms by a four-tuple containing re-occurring elements found in our survey. We introduce requirements on these elements that ensure the comparability of experimental results. Moreover, we propose a benchmark that meets all requirements and establishes a new way to evaluate existing and newly proposed mechanisms. Conducting a large-scale empirical study, we gain valuable new insights into the strengths and weaknesses of existing mechanisms. An unexpected -yet explainable -result is a baseline supremacy, i.e., using one of the two baseline mechanisms is expected to deliver good or even the best utility. Finally, we provide guidelines for practitioners to select suitable mechanisms and improvement options for researchers to break the baseline supremacy. Theorem 1 (Composition [20]). Let M be a mechanism processing a stream prefix 𝑆 𝑝 = (𝐷 1 , . . . , 𝐷 𝑝 ), and outputting a transcript of released values 𝑅 = (𝑟 1 , . . . , 𝑟 𝑝 ). Assume that we can decompose M into 𝑝 sub-mechanisms M 1 , . . . , M 𝑝 , s.t. M 𝑡 (𝐷 𝑡 ) = 𝑟 𝑡 , each M 𝑡 has independent randomness and achieves 𝜖 𝑡 -differential privacy. Then, M satisfies 𝑤-event differential privacy if ∀𝑡 ∈ [𝑤, 𝑝] : 𝑡 ∑︁ 𝑘=𝑡 -𝑤+1 𝜖 𝑘 ≤ 𝜖.