Collecting Telemetry Data Privately
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.
The authors propose a more efficient mechanism for local differential privacy. In particular, they propose a 1 bit local differential privacy method that enables mean estimation in a distributed and effective way.  Also a d-bit method is proposed for histogram estimation. It is argued that these two goals are of partical relevance in collection of telemetry data. The main advance is in the communication efficiency - which is key to large scale deployment. The authors also note that this mechanism is indeed deployed at large scale in industry and likely consistutes the largest deployment of differential privacy to date. While this on its own does not add to the value of the scientific contribution - it does reinforce the point of an efficient, effective and practical approach.
The authors submitted another version of their paper as supplementary material that contains the proofs. But it also contains more figures and extended main text. This is borderline. The supplementary material should only contain the additional material - while the main paper should be self-contained and not repeated. It is also weird, that the reviewer has to hunt for proofs in provided text. There should be a clear separation between submission and supplementary material.
Overall, the presentation is clear - partially due to outsourcing parts of the submission to the supplementary. However, alpha-rounding part remains partially unclear. Can the authors please elaborate on the claimed guarantees?
While the experimental study is interesting - there is a question about reproducibility of the results.As it looks this is real user and company data - how would follow up work compare here? It would be beneficial to provide an alternative solution -- potential simulated data -- so that comparison remain open source.
However, the experiments are considered convincing and support the main claim.