# Adversarially Robust Distributed Count Tracking via Partial Differential Privacy

arXiv: https://arxiv.org/abs/2311.00346 · HTML: https://mlsanity.com/paper/2311.00346/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 21 of its 41 references that are in the map.
- First posted on arXiv 1 Nov 2023.

## Builds on (most cited first, 21 of 21)

- [Preserving Statistical Validity in Adaptive Data Analysis](https://mlsanity.com/paper/1411.2664/) (2014)
- [Algorithmic Stability for Adaptive Data Analysis](https://mlsanity.com/paper/1511.02513/) (2015)
- [Generalization in Adaptive Data Analysis and Holdout Reuse](https://mlsanity.com/paper/1506.02629/) (2015)
- [A New Analysis of Differential Privacy's Generalization Guarantees](https://mlsanity.com/paper/1909.03577/) (2019)
- [Calibrating Noise to Variance in Adaptive Data Analysis](https://mlsanity.com/paper/1712.07196/) (2017)
- [Generalization for Adaptively-chosen Estimators via Stable Median](https://mlsanity.com/paper/1706.05069/) (2017)
- [A Framework for Adversarially Robust Streaming Algorithms](https://mlsanity.com/paper/2003.14265/) (2020)
- [Adversarially Robust Streaming Algorithms via Differential Privacy](https://mlsanity.com/paper/2004.05975/) (2020)
- [The Adversarial Robustness of Sampling](https://mlsanity.com/paper/1906.11327/) (2019)
- [Dynamic Algorithms Against an Adaptive Adversary: Generic Constructions and Lower Bounds](https://mlsanity.com/paper/2111.03980/) (2021)
- [The Limits of Post-Selection Generalization](https://mlsanity.com/paper/1806.06100/) (2018)
- [Tight Bounds for Adversarially Robust Streams and Sliding Windows via Difference Estimators](https://mlsanity.com/paper/2011.07471/) (2020)
- [Adversarial Robustness of Streaming Algorithms through Importance Sampling](https://mlsanity.com/paper/2106.14952/) (2021)
- [On Adaptive Distance Estimation](https://mlsanity.com/paper/2010.11252/) (2020)
- [A Framework for Adversarial Streaming via Differential Privacy and Difference Estimators](https://mlsanity.com/paper/2107.14527/) (2021)
- [Adversarially Robust Streaming via Dense--Sparse Trade-offs](https://mlsanity.com/paper/2109.03785/) (2021)
- [Optimal Fully Dynamic k-Center Clustering for Adaptive and Oblivious Adversaries](https://mlsanity.com/paper/2303.11843/) (2023)
- [On the Robustness of CountSketch to Adaptive Inputs](https://mlsanity.com/paper/2202.13736/) (2022)
- [Adversarially Robust Coloring for Graph Streams](https://mlsanity.com/paper/2109.11130/) (2021)
- [Optimal Random Sampling from Distributed Streams Revisited](https://mlsanity.com/paper/1903.12065/) (2019)
- [Learning Based Distributed Tracking](https://mlsanity.com/paper/2006.12943/) (2020)

## Abstract (arXiv)

We study the distributed tracking model, also known as distributed functional monitoring. This model involves k sites each receiving a stream of items and communicating with the central server. The server's task is to track a function of all items received thus far continuously, with minimum communication cost. For count tracking, it is known that there is a √k gap in communication between deterministic and randomized algorithms. However, existing randomized algorithms assume an "oblivious adversary" who constructs the entire input streams before the algorithm starts. Here we consider adaptive adversaries who can choose new items based on previous answers from the algorithm. Deterministic algorithms are trivially robust to adaptive adversaries, while randomized ones may not. Therefore, we investigate whether the √k advantage of randomized algorithms is from randomness itself or the oblivious adversary assumption. We provide an affirmative answer to this question by giving a robust algorithm with optimal communication. Existing robustification techniques do not yield optimal bounds due to the inherent challenges of the distributed nature of the problem. To address this, we extend the differential privacy framework by introducing "partial differential privacy" and proving a new generalization theorem. This theorem may have broader applications beyond robust count tracking, making it of independent interest.