Adversarially Robust Streaming Algorithms via Differential Privacy
Open Access
- 24 November 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 69 (6) , 1-14
Abstract
A streaming algorithm is said to be adversarially robust if its accuracy guarantees are maintained even when the data stream is chosen maliciously, by an adaptive adversary . We establish a connection between adversarial robustness of streaming algorithms and the notion of differential privacy . This connection allows us to design new adversarially robust streaming algorithms that outperform the current state-of-the-art constructions for many interesting regimes of parameters.Keywords
All Related Versions
Funding Information
- Israel Science Foundation (1595/19, 993/17 and 1871/19)
- Blavatnik Family Foundation
- European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation program (882396)
This publication has 27 references indexed in Scilit:
- Algorithmic stability for adaptive data analysis2016
- Differentially Private Release and Learning of Threshold Functions2015
- Preserving Statistical Validity in Adaptive Data Analysis2015
- Preventing False Discovery in Interactive Data Analysis Is Hard2014
- How robust are linear sketches to adaptive inputs?2013
- Private Learning and Sanitization: Pure vs. Approximate Differential PrivacyLecture Notes in Computer Science, 2013
- On the Exact Space Complexity of Sketching and Streaming Small Norms2010
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Counting Distinct Elements in a Data Stream2002
- Finding Frequent Items in Data Streams2002