We investigate privacy filters, tools that enable privacy accounting for differentially private (DP) mechanisms whose privacy parameters are chosen adaptively. We show that the worst‑case privacy loss when interacting with any privacy filter is described by a Bellman equation.
Based on this theory we introduce residue filters, which unify existing privacy filters. In particular we construct the Gaussian DP (GDP) residue filter, which strictly outperforms the naïve GDP filter. In the average case the new filter allows as many pure‑DP queries as in the non‑adaptive setting and about $\pi/2$ times more pure‑DP queries than the naïve GDP filter.
Residue filters also capture the natural filter, which leverages exact privacy accounting techniques to use the full privacy profile of each query, thus offering higher utility. Earlier privacy filters considered only simple parameters such as Rényi‑DP or GDP; natural filters account for the entire privacy curve, leading to more efficient use of a given privacy budget.
We further prove that natural privacy filters are not free in general. We provide a characterization: a family of private queries admits free natural filters for any budget only if the mechanisms are totally ordered under composition.
Finally, although the natural approximate‑DP filter can fail against an adaptive adversary, its failure is limited: the output remains approximate‑DP with parameters at most poly‑logarithmically worse than the intended ones.
Review: The paper formalizes worst‑case analysis of privacy filters via a Bellman equation and proposes residue filters that substantially increase query capacity, achieving a $\pi/2$ improvement in the Gaussian DP case. The characterization of when natural filters are free gives a clear structural condition, guiding the design of adaptive‑secure privacy accounting schemes.