Differential Private Data Stream Analytics in the Local and Shuffle Models

We study online data analytics with differential privacy (DP) in decentralized settings. Specifically, online data analytics with local DP protection is widely adopted in real-world applications. Despite numerous endeavors in this field, significant gaps in utility and functionality remain when compared to its offline counterpart. We present an optimal, streamable mechanism: <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ExSub</monospace>, for local DP sparse vector estimation. The mechanism enables a range of online analytics on streaming binary vectors, including multi-dimensional binary, categorical, or set-valued data. By leveraging the negative correlation of occurrence events in the sparse vector, we attain an optimal error rate under local privacy constraints, only requiring streamable computations. To surpass the error barrier of local privacy, we also study <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ExSub</monospace> randomizer in the newly emerging (single-message) shuffle model of DP, and provide nearly-tight privacy amplification bounds therein. Additionally, we leverage the online shuffle model that independently permutes users' messages at each timestamp, to design a simplified randomization strategy that can approximately reach Gaussian accuracy in central DP. Through experiments with both synthetic and real-world datasets, <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ExSub</monospace> mechanism in the local model have been shown to reduce error by <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$40\%-60\%$</tex-math></inline-formula> compared to SOTA approaches. The <monospace xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">ExSub</monospace> in the shuffle model can further reduce over <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$85\%$</tex-math></inline-formula> error, and the online shuffle protocol reduces over <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$99.7\%$</tex-math></inline-formula> error.