Timezone: »
The collection and analysis of telemetry data from user's devices is routinely performed by many software companies. Telemetry collection leads to improved user experience but poses significant risks to users' privacy. Locally differentially private (LDP) algorithms have recently emerged as the main tool that allows data collectors to estimate various population statistics, while preserving privacy. The guarantees provided by such algorithms are typically very strong for a single round of telemetry collection, but degrade rapidly when telemetry is collected regularly. In particular, existing LDP algorithms are not suitable for repeated collection of counter data such as daily app usage statistics. In this paper, we develop new LDP mechanisms geared towards repeated collection of counter data, with formal privacy guarantees even after being executed for an arbitrarily long period of time. For two basic analytical tasks, mean estimation and histogram estimation, our LDP mechanisms for repeated data collection provide estimates with comparable or even the same accuracy as existing single-round LDP collection mechanisms. We conduct empirical evaluation on real-world counter datasets to verify our theoretical results. Our mechanisms have been deployed by Microsoft to collect telemetry across millions of devices.
Author Information
Bolin Ding (Microsoft)
Janardhan Kulkarni (Microsoft Research)
Sergey Yekhanin (Microsoft)
More from the Same Authors
-
2021 Spotlight: Private Non-smooth ERM and SCO in Subquadratic Steps »
Janardhan Kulkarni · Yin Tat Lee · Daogao Liu -
2022 Poster: When Does Differentially Private Learning Not Suffer in High Dimensions? »
Xuechen Li · Daogao Liu · Tatsunori Hashimoto · Huseyin A. Inan · Janardhan Kulkarni · Yin-Tat Lee · Abhradeep Guha Thakurta -
2022 Poster: Differentially Private Model Compression »
FatemehSadat Mireshghallah · Arturs Backurs · Huseyin A. Inan · Lukas Wutschitz · Janardhan Kulkarni -
2021 Poster: Private Non-smooth ERM and SCO in Subquadratic Steps »
Janardhan Kulkarni · Yin Tat Lee · Daogao Liu -
2021 Poster: Fast and Memory Efficient Differentially Private-SGD via JL Projections »
Zhiqi Bu · Sivakanth Gopi · Janardhan Kulkarni · Yin Tat Lee · Judy Hanwen Shen · Uthaipon Tantipongpipat -
2021 Poster: Differentially Private n-gram Extraction »
Kunho Kim · Sivakanth Gopi · Janardhan Kulkarni · Sergey Yekhanin -
2019 Poster: An Algorithmic Framework For Differentially Private Data Analysis on Trusted Processors »
Janardhan Kulkarni · Olga Ohrimenko · Bolin Ding · Sergey Yekhanin · Joshua Allen · Harsha Nori -
2019 Poster: Locally Private Gaussian Estimation »
Matthew Joseph · Janardhan Kulkarni · Jieming Mao · Steven Wu -
2017 Poster: Clustering Billions of Reads for DNA Data Storage »
Cyrus Rashtchian · Konstantin Makarychev · Miklos Racz · Siena Ang · Djordje Jevdjic · Sergey Yekhanin · Luis Ceze · Karin Strauss -
2017 Spotlight: Clustering Billions of Reads for DNA Data Storage »
Cyrus Rashtchian · Konstantin Makarychev · Miklos Racz · Siena Ang · Djordje Jevdjic · Sergey Yekhanin · Luis Ceze · Karin Strauss