ODP filters with sublinear privacy degradation and efficient approximation of the optimal output-DP composition bound

The output differential privacy (ODP) framework of Hartmann, Bindschaedler, Bentkamp, and West (PoPETs 2022) exploits the fact that some outputs of a differentially private mechanism leak less information than the worst case: after each invocation, only the realized, output-dependent budget is subtracted from the remaining privacy budget, yielding significant savings when composing mechanisms such as the Sparse Vector Technique, Propose-Test-Release, or early-stopping iterative algorithms. Two quantitative gaps currently separate ODP accounting from optimal privacy accounting. First, all known ODP composition results rest on simple composition, so the $\varepsilon$-budget degrades linearly in the number $k$ of invoked mechanisms, while advanced composition and privacy filters outside the ODP setting achieve sublinear degradation (rate $O(\varepsilon^2 k + \varepsilon\sqrt{k})$); whether a valid ODP filter that preserves per-output a posteriori budget subtraction while achieving better-than-linear degradation exists is open. Second, the exact optimal ODP composition parameter OptDel admits an exact combinatorial characterization (Theorem 15 of the source), but computing it exactly is exponential and the corresponding classical problem is #P-complete already in the single-stopping-point case, and no efficient approximation algorithm or provably tight relaxation is known. The problem is to close these two gaps: construct (or rule out) an ODP-compatible filter with better-than-linear $\varepsilon$-degradation under fully adaptive adversaries, and provide an efficient, provably guaranteed approximation to OptDel that quantifies its gap to the efficiently computable modular bound.

Background

Differential privacy (DP) is the standard formal notion of privacy for aggregate data releases: a randomized mechanism $M$ is $(\varepsilon,\delta)$-differentially private if for all pairs of neighboring databases $x, x'$ (differing in one record) and all measurable sets $S$ of outputs, $\Pr[M(x)\in S]\le e^{\varepsilon}\Pr[M(x')\in S]+\delta$. A central property is composition: when $k$ mechanisms are invoked, their privacy losses accumulate. The simple composition theorem gives a $(k\varepsilon, k\delta)$ guarantee, while advanced composition theorems improve the $\varepsilon$-part to $O(\varepsilon^2 k + \varepsilon\sqrt{k})$ at the cost of a larger $\delta$. Optimal composition theorems are known for homogeneous composition (Kairouz, Oh, and Viswanath) and heterogeneous adaptive composition (Murtagh and Vadhan). Privacy filters and odometers (Rogers, Roth, Ullman, and Vadhan) extend composition to the fully adaptive setting, where the adversary chooses each next mechanism and even its privacy parameters based on previous outputs, with a filter serving as a stopping rule that prevents a target budget $(\varepsilon_t, \delta_t)$ from being exceeded; filters based on Rényi differential privacy (a relaxation of DP that bounds the Rényi divergence between output distributions of neighboring databases and composes additively) give the best known rates in that setting, and later work achieved advanced-composition rates for fully adaptive and even concurrent composition (Whitehouse et al.; Haney et al.).

Hartmann et al. observed that in many DP mechanisms some outputs leak strictly less information than the worst case: for example, when the Sparse Vector Technique (a mechanism that answers a stream of threshold queries and stops at the first affirmative answer) outputs no affirmative answer, the queries after the first are never even evaluated. To exploit this, they introduced output differential privacy (ODP): a mechanism $M$ is $(\mathcal{P}, E, \delta)$-ODP if $\mathcal{P}$ is a partition of the output space and the DP inequality holds on each block $P_k$ with its own budget $E(P_k)\le\varepsilon$. In their composition experiment the adversary adaptively chooses mechanisms, databases, and ODP parameters, and the accountant subtracts only the realized, output-dependent amount $E(P_k)$ from the remaining budget after each invocation. This yields substantial budget savings for the Sparse Vector Technique, the Propose-Test-Release framework (a mechanism design pattern that privately tests whether a statistic is far from a degenerate boundary before releasing it), for iterative mechanisms that terminate before their maximal number of iterations, and for recovering already-spent budget when a mechanism's output is discarded. However, their composition theorem is based on simple composition, so $\varepsilon$ degrades linearly in the number of invoked mechanisms; the paper explicitly leaves open whether an ODP-compatible filter can combine per-output a posteriori budget subtraction with the sublinear degradation that advanced composition provides outside the ODP setting.

For iterative mechanisms with potential stopping points $k_1<\dots<k_n$, step mechanisms $M_1,\dots,M_{k_n}$ that are $(\varepsilon_k,\delta_k)$-DP, and stopping criteria $h_{k_i}$, the paper defines $\mathrm{OptDel}(\{k_i\}_{i=1}^n, \{(\varepsilon_k,\delta_k)\}_{k=1}^{k_n}, E)$ as the minimal $\delta$ such that the iterative mechanism satisfies the $(\mathcal{P},E,\delta)$-ODP guarantee for every admissible choice of step mechanisms and stopping criteria. Lemma 11 gives an efficiently computable modular bound on this quantity by plugging any existing DP composition theorem into the ODP machinery, while Theorem 15 gives the exact value as a combinatorial maximization over sets of output sequences of randomized response mechanisms (the standard four-output worst-case mechanisms used in optimal-composition analysis). The exact value requires iterating over exponentially many candidate sets, and Murtagh and Vadhan showed that the classical counterpart of this maximization (the case $n=1$) is #P-complete (complete for #P, the complexity class of counting problems, believed strictly harder than NP), so no efficient exact algorithm is expected; the paper explicitly leaves open whether efficient approximation algorithms exist and how large the gap between the modular Lemma 11 bound and the exact optimum is.

Problem Statement

Work within the ODP framework as defined by Hartmann et al.: mechanisms carry a partition $\mathcal{P}$ of their output space with per-block budgets $E(P_k)$, and the composition accounting subtracts the realized, output-dependent amount $E(P_k)$ from the remaining budget after each invocation, while the adversary adaptively chooses mechanisms, databases, and ODP guarantees.

(1) ODP filter with sublinear degradation. In the ODP filter experiment of the source (its Algorithm 6 and Definition 19), does there exist a valid ODP filter $F_{\varepsilon_t,\delta_t}$ — a stopping rule that observes the sequence of realized per-output budgets and the adversary's adaptive choices of mechanisms and ODP parameters, and returns HALT or CONT — such that (i) validity holds exactly as in the source's Definition 19: for all adversaries and all sets $\mathcal{V}$ of adversary views, $\Pr[V^0\in\mathcal{V}]\le e^{\varepsilon_t}\Pr[V^1\in\mathcal{V}]+\delta_t$, where $V^0$ and $V^1$ are the adversary's views on neighboring databases, (ii) the per-output a posteriori budget subtraction is preserved (the filter does not revert to worst-case accounting), and (iii) the $\varepsilon$-degradation of the composed mechanism as a function of the number $k$ of invoked mechanisms is asymptotically better than linear, e.g. of advanced-composition type $O(\varepsilon^2 k + \varepsilon\sqrt{k})$? Provide a construction with a full validity proof, or prove that no such filter exists in general within this framework.

(2) Efficient approximation of the optimal ODP composition. The source's Theorem 15 expresses the exact optimal ODP parameter $\mathrm{OptDel}(\{k_i\}_{i=1}^n, \{(\varepsilon_k,\delta_k)\}_{k=1}^{k_n}, E)$ — the minimal $\delta$ for the $(\mathcal{P},E,\cdot)$-ODP guarantee of any iterative mechanism built from $(\varepsilon_k,\delta_k)$-DP steps with potential stopping points $\{k_i\}$ — as a finite combinatorial maximization over sets of randomized-response output sequences, computable exactly only in time exponential in $k_n$, with the classical case $n=1$ #P-complete. Provide a polynomial-time algorithm that approximates $\mathrm{OptDel}$ with a proven additive or relative guarantee (or a polynomial-time relaxation with a proven bound on its distance from the optimum, or a hardness-of-approximation result); in the first two cases, use the resulting approximation to quantify the gap between the exact optimum and the efficiently computable modular bound of the source's Lemma 11.

The two requested results jointly support one objective: an ODP privacy-accounting method that is simultaneously asymptotically tight (no linear-degradation penalty at large composition lengths, part 1) and efficiently computable (tight or provably approximable exact accounting at any composition length, part 2).

References

1. Valentin Hartmann, Vincent Bindschaedler, Alexander Bentkamp, Robert West. Privacy accounting $\varepsilon$conomics: Improving differential privacy composition via a posteriori bounds. Proceedings on Privacy Enhancing Technologies 2022(3):222–246, 2022. DOI: 10.56553/popets-2022-0070, https://doi.org/10.56553/popets-2022-0070 (arXiv:2205.03470, https://arxiv.org/abs/2205.03470)
2. Jack Murtagh, Salil Vadhan. The Complexity of Computing the Optimal Composition of Differential Privacy. arXiv:1507.03113, https://arxiv.org/abs/1507.03113 (TCC 2016)
3. Ryan Rogers, Aaron Roth, Jonathan Ullman, Salil Vadhan. Privacy Odometers and Filters: Pay-as-you-Go Composition. arXiv:1605.08294, https://arxiv.org/abs/1605.08294
4. Peter Kairouz, Sewoong Oh, Pramod Viswanath. The Composition Theorem for Differential Privacy. arXiv:1311.0776, https://arxiv.org/abs/1311.0776
5. Justin Whitehouse, Aaditya Ramdas, Ryan Rogers, Zhiwei Steven Wu. Fully Adaptive Composition in Differential Privacy. arXiv:2203.05481, https://arxiv.org/abs/2203.05481 (ICML 2023)
6. Ryan Rogers, Gennady Samorodnitsky, Zhiwei Steven Wu, Aaditya Ramdas. Adaptive Privacy Composition for Accuracy-first Mechanisms. arXiv:2306.13824, https://arxiv.org/abs/2306.13824
7. Jonathan Lebensold, Doina Precup, Borja Balle. On the Privacy of Selection Mechanisms with Gaussian Noise. arXiv:2402.06137, https://arxiv.org/abs/2402.06137
8. Valentin Hartmann, Vincent Bindschaedler, Robert West. On the Choice of Databases in Differential Privacy Composition. arXiv:2209.13697, https://arxiv.org/abs/2209.13697
9. Samuel Haney, Michael Shoemate, Grace Tian, Salil Vadhan, Andrew Vyrros, Vicki Xu, Wanrong Zhang. Concurrent Composition for Interactive Differential Privacy with Adaptive Privacy-Loss Parameters. Journal of Privacy and Confidentiality, 2025. DOI: 10.29012/jpc.918, https://doi.org/10.29012/jpc.918