Adversarially Robust Streaming Algorithms via Differential Privacy

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.

PDF NeurIPS Semantic Scholar

Cite

Text

Hasidim et al. "Adversarially Robust Streaming Algorithms via Differential Privacy." Neural Information Processing Systems, 2020.

Markdown

[Hasidim et al. "Adversarially Robust Streaming Algorithms via Differential Privacy." Neural Information Processing Systems, 2020.](https://mlanthology.org/neurips/2020/hasidim2020neurips-adversarially/)

BibTeX

@inproceedings{hasidim2020neurips-adversarially,
  title     = {{Adversarially Robust Streaming Algorithms via Differential Privacy}},
  author    = {Hasidim, Avinatan and Kaplan, Haim and Mansour, Yishay and Matias, Yossi and Stemmer, Uri},
  booktitle = {Neural Information Processing Systems},
  year      = {2020},
  url       = {https://mlanthology.org/neurips/2020/hasidim2020neurips-adversarially/}
}