← 研踪 PaperTrailarXiv:2611.08699 · v1
Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion Streams
首次提交 2026-11-06 04:56
版本更新 2026-11-06 04:56
雷达观测 2026-11-09 10:16
摘要
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 $α$ using $\tilde{O}(\frac{\sqrt{k}}α + \frac{1}{α^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}}{α^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}{α^2}+ \min\left(\frac{\sqrt{k}}α, \frac{\sqrt{\log |U|}}{α^2}\right)\right)$. Building on our ADA mechanism, we construct a fixed linear sketch with a stateful decoder that answers $\tilde{O}(\frac{1}{ε^2})$ adaptive $F_2$ moment estimation queries to within a $(1\pmε)$-multiplicative factor using $\tilde{O}(\frac{1}{ε^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}{ε^2})$ bits of space, improving upon the $\tilde{O}(\frac{1}{ε^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 $ε$ is required to achieve adversarial robustness in the turnstile model.
观测到的版本
相邻记录可能跳过中间版本；首次发现 v2 及以上也会标为版本更新。
v1 · 2026-11-06 04:56 · 最新观测版本
Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion Streams
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 $α$ using $\tilde{O}(\frac{\sqrt{k}}α + \frac{1}{α^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}}{α^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}{α^2}+ \min\left(\frac{\sqrt{k}}α, \frac{\sqrt{\log |U|}}{α^2}\right)\right)$. Building on our ADA mechanism, we construct a fixed linear sketch with a stateful decoder that answers $\tilde{O}(\frac{1}{ε^2})$ adaptive $F_2$ moment estimation queries to within a $(1\pmε)$-multiplicative factor using $\tilde{O}(\frac{1}{ε^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}{ε^2})$ bits of space, improving upon the $\tilde{O}(\frac{1}{ε^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 $ε$ is required to achieve adversarial robustness in the turnstile model.
查看此版本解读 →查看此版本原文 ↗