Metraipolis › archive › dc_a09bec281469
Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion Streams — arXiv:2611.08699
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2611.08699
- License (as archived)
- CC0-1.0
- Archived
- 2026-11-09T22:47:09.259Z
- SHA-256 of the archived text
4198c8e708c4421ae53c311cf960ec9bdedd760e64654aa837295ac580d0764e- Stable URL of this page
https://metraipolis.com/documento/dc_a09bec281469
How to cite
Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion Streams — arXiv:2611.08699 — arXiv (en), https://arxiv.org/abs/2611.08699 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_a09bec281469 (Metraipolis archive dc_a09bec281469, sha256 4198c8e708c4421ae53c311cf960ec9bdedd760e64654aa837295ac580d0764e)
BibTeX
@misc{dca09bec281469,
title = {Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion Streams — arXiv:2611.08699},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2611.08699},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_a09bec281469; sha256 4198c8e708c4421ae53c311cf960ec9bdedd760e64654aa837295ac580d0764e},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2611.08699. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
Classical streaming algorithms and statistical mechanisms frequently fail when future inputs or queries depend adaptively on prior outputs. In this work, we resolve central open questions in both adaptive data analysis (ADA) and adversarially robust turnstile streaming by introducing a unified hierarchical estimator-corrector-learner framework. For adaptive data analysis over an unrestricted domain, we design a randomized mechanism that answers $k$ adaptively chosen statistical queries to within additive error $\alpha$ using $\tilde{O}(\frac{\sqrt{k}}{\alpha} + \frac{1}{\alpha^2})$ samples, nearly matching the lower bounds of Hardt and Ullman [FOCS 2014] and Steinke and Ullman [COLT 2015] while improving upon the classic $\tilde{O}(\frac{\sqrt{k}}{\alpha^2})$ bound of Dwork et al. [STOC 2015] and Bassily et al. [STOC 2016]. For known finite domains $U$, we combine our mechanism with private multiplicative weights to improve the sample complexity to $\tilde{O}\left(\frac{1}{\alpha^2}+ \min\left(\frac{\sqrt{k}}{\alpha}, \frac{\sqrt{\log |U|}}{\alpha^2}\right)\right)$. Building on our ADA mechanism, we construct a fixed linear sketch with a stateful decoder that answers $\tilde{O}(\frac{1}{\epsilon^2})$ adaptive $F_2$ moment estimation queries to within a $(1\pm\epsilon)$-multiplicative factor using $\tilde{O}(\frac{1}{\epsilon^2})$ bits of space. Finally, by embedding this sketch into a binary-tree recursion, we obtain the first nearly space-optimal adversarially robust algorithm for $F_2$ estimation on insertion-deletion streams. Our algorithm uses $\tilde O(\frac{1}{\epsilon^2})$ bits of space, improving upon the $\tilde{O}(\frac{1}{\epsilon^4})$ bound of Gribelyuk et al. [STOC 2026] and matching the insertion-only bound of Woodruff and Zhou [FOCS 2021]. This demonstrates that no asymptotic space overhead in $\epsilon$ is required to achieve adversarial robustness in the turnstile model.
Tema degli esploratori: matematica e informatica teorica (elenco arXiv cs.DS, nuovi lavori del giorno).
Categorie arXiv: Data Structures and Algorithms (cs.DS).
Pagina del lavoro: https://arxiv.org/abs/2611.08699 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-11-09T22:40:29.867Z dalla pagina https://arxiv.org/list/cs.DS/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).