Fully Adaptive Composition in Differential Privacy

Introduction

Differential privacy (Dwork et al. 2006b) is an algorithmic criterion that provides meaningful guarantees of individual privacy for analyzing sensitive data. Intuitively, an algorithm is differentially private if similar inputs induce similar distributions on outputs. More formally, an algorithm $A:\mathcal{X}\rightarrow\mathcal{Y}$ is differentially private if, for any set of outcomes $G\subset\mathcal{Y}$ and any neighboring inputs $x,x^{\prime}\in\mathcal{X}$,

where $\epsilon$ and $\delta$ are the privacy parameters of the algorithm.

A key property of differential privacy is graceful composition. Suppose $A_{1},\dots,A_{n}$ are algorithms such that each $A_{m}$ is $(\epsilon_{m},\delta_{m})$-differentially private. Advanced composition (Dwork et al. 2010; Kairouz et al. 2015) states that, for any $\delta^{\prime}>0$, the composed sequence of algorithms is $(\epsilon,\delta)$-differentially private, where $\delta=\delta^{\prime}+\sum_{m\leq n}\delta_{m}$, and

When all privacy parameters are the same and small, we roughly have $\epsilon=O(\sqrt{n}\epsilon_{m})$. Hence, analysts can make use of sensitive datasets with a slow degradation of privacy.

However, there is a major disconnect between most existing results on privacy composition and modern data analysis. As analysts view the outputs of algorithms, the future manner in which they interact with the data changes. Advanced composition allows analysts to adaptively select algorithms, but not privacy parameters. In many cases, analysts may wish to choose the subsequent privacy parameters based on the outcomes of the previous private algorithms. For example, if an analyst learns, from past computations, that they only need to run one more computation, they should be able to use the remainder of their privacy budget in the final round. Likewise, if an analyst is having a hard time deriving conclusions, they should be allowed to adjust privacy parameters to extend the allowable number of computations.

This desideratum has motivated the study of fully adaptive composition, wherein one is allowed to adaptively select the privacy parameters of the algorithms. Rogers et al. 2016 define two probabilistic objects which can be used to ensure privacy guarantees in fully adaptive composition. The first, called a privacy filter, is an adaptive stopping condition that ensures an entire interaction between an analyst and a dataset retains a pre-specified target privacy level, even when the privacy parameters are chosen adaptively. The second, called a privacy odometer, provides a sequence of high-probability upper bounds on how much privacy has been lost up to any point in time. While this work took the first steps towards fully adaptive composition, their filters and odometers suffered from large constants and the latter suffered from sub-optimal asymptotic rates.

We show that, as long as a target privacy level is pre-specified, one can obtain the same rate as advanced composition, including constants. We also construct families of privacy odometers that are not only tighter than the originals, but can be optimized for various target levels of privacy. Overall, we show that full adaptivity is not a cost—but rather a feature—of differential privacy.

There is a long line of work on privacy composition. The “basic composition” theorem states that, when composing private algorithms, the privacy parameters (both $\epsilon$ and $\delta$) add up linearly (Dwork et al. 2006b; Dwork et al. 2006a; Dwork and Lei 2009). The “advanced composition” theorem allows the total $\epsilon$ to grow sublinearly with a small degradation on $\delta$ (Dwork et al. 2010). Later work (Kairouz et al. 2015; Murtagh and Vadhan 2016) studies “optimal” composition, a computationally intractable formula that tightly characterizes the overall privacy of composed mechanisms.

More recently, several variants of privacy have been studied including (zero)-concentrated differential privacy (zCDP) (Bun and Steinke 2016; Dwork and Rothblum 2016), Renyi differential privacy (RDP) (Mironov 2017), and $f$-differential privacy ($f$-DP) (Dong et al. 2021). These all exhibit tighter composition results than differential privacy, but for restricted classes of mechanisms. These results do not allow adaptive choices of privacy parameters.

Privacy Filters and Odometers:

Rogers et al. 2016 originally introduced privacy filters and odometers, which allow privacy composition with adaptively selected privacy parameters. While their contributions provide a decent approximation of advanced composition, their bounds suffer from large constants, which prevents practical usage. Our work directly improves over these initial results. First, we construct privacy filters essentially matching advanced composition. We also provide flexible families of privacy odometers that outperform those of Rogers et al. 2016.

Feldman and Zrnic 2021 leverage RDP to construct Rényi filters, where they require individual mechanisms to satisfy RDP. Since our proof establishes a new privacy filter for approximate zCDP (Bun and Steinke 2016), our results also extend to approximate RDP (Papernot and Steinke 2022), which directly generalizes their Rényi filter. Even though it is also possible to obtain a privacy filter for $(\epsilon,\delta)$-DP through Rényi filters (Feldman and Zrnic 2021), this result requires a stronger assumption that algorithms being composed satisfy probabilistic (i.e.​ point-wise) differential privacy (Kasiviswanathan and Smith 2014). Since converting from differential privacy to probabilistic differential privacy can be costly (see Lemma 2), our filters demonstrate an improvement by avoiding the conversion cost.

More recently, Koskela et al. 2022 and Smith and Thakurta 2022 provide privacy filters for Gaussian DP (GDP) (Dong et al. 2021). However, their results do not hold for more general mechanisms under $f$-DP and therefore cannot handle algorithms with rare “catastrophic” privacy failure events, in which the privacy loss goes to infinity. Both of our $(\epsilon,\delta)$-filter and approximate zCDP filters can handle such events.

Feldman and Zrnic 2021 and Lécuyer 2021 construct RDP odometers. The former work sequentially composes Rényi filters and the latter work simultaneously runs multiple Rényi filters and takes a union bound. Neither odometer provides high probability, time-uniform bounds on privacy loss, making these results incomparable to our own. We believe our notion of odometers, which aligns with that of Rogers et al. 2016, is more natural.

To prove our results, we leverage time-uniform concentration results for martingales (Howard et al. 2020; Howard et al. 2021). The bounds in these papers directly improve over related self-normalized concentration results (de la Pena et al. 2004; Chen et al. 2014). These latter bounds were leveraged in Rogers et al. 2016 to construct filters and odometers.

2 Summary of Contributions

In this work, we provide two primary contributions. We present these results in full rigor following a brief discussion of privacy basics and martingale theory in Section 2.

In Theorem 2 of Section 3, we construct privacy filters that match the rate of advanced composition, significantly improving over results of Rogers et al. 2016. Our filter follows from a more general approximate zCDP/RDP filter (Bun and Steinke 2016; Papernot and Steinke 2022) presented in Theorem 1. In particular, this approximate zCDP/RDP filter greatly generalizes existing filters from the pure RDP setting (Feldman and Zrnic 2021). This extension allows us to capture a broader class of algorithms and avoids the conversion loss when translating bounds between pure RDP and $(\epsilon,\delta)$-differential privacy. We state an informal version of filter in the case of approximate differential privacy below In Appendix D, we provide an alternative proof for our privacy filter result through reductions to generalized randomized response. While it gives the exact same rates, we believe it could be of independent interest. For example, it may be useful for obtaining filters with rates like the optimal composition (Murtagh and Vadhan 2016; Kairouz et al. 2015), which used a similar reduction to randomized response in their analysis..

Fix target privacy parameters $\epsilon>0$ and $\delta>0$, and suppose $(A_{n})_{n\geq 1}$ is an adaptively selected sequence of algorithms. Assume that $A_{n}$ is $(\epsilon_{n},\delta_{n})$-DP conditioned on the outputs of the first $n-1$ algorithms, where $\epsilon_{n}$ and $\delta_{n}$ may depend on outputs of $A_{1},\dots,A_{n-1}$. If a data analyst stops interacting with the data before $\sqrt{2\log\left(\frac{1}{\delta}\right)\sum_{m\leq n+1}\epsilon_{m}^{2}}+\frac{1}{2}\sum_{m\leq n+1}\epsilon_{m}^{2}>\epsilon$, then the entire interaction is $(\epsilon,\delta)$-DP.

Privacy Odometers:

In Theorem 3 of Section 4, we construct improved privacy odometers — that is, sequences of upper bounds on privacy loss which are all simultaneously valid with high probability. Our three families of odometers theoretically and empirically outperform those of Rogers et al. 2016. See Figure 1(b) for a comparison.

For both results, our key insight is to view adaptive privacy composition as depending not on the number of algorithms being composed, but rather on the sums of squares of privacy parameters, $\sum_{m\leq n}\epsilon_{m}^{2}$. This shift to looking at “intrinsic time” allows us to apply recent advances in time-uniform concentration (Howard et al. 2020; Howard et al. 2021) to privacy loss martingales. Overall, our results show that there is essentially no cost for fully adaptive private data analysis.

Background on Differential Privacy

Throughout, we assume all algorithms map from a space of datasets $\mathcal{X}$ to outputs in a measurable space, typically either denoted $(\mathcal{Y},\mathcal{G})$ or $(\mathcal{Z},\mathcal{H})$. For a sequence of algorithms $(A_{n})_{n\geq 1}$, we often consider the composed algorithm $A_{1:n}:=(A_{1},\dots,A_{n})$. For more background on measure-theoretic matters, as well as on the notion of neighboring datasets, see Appendix A.

We start by formalizing a generalization of differential privacy in which the privacy parameters of an algorithm $A_{n}$ can be functions of the outputs of $A_{1},\dots,A_{n-1}$. In particular, we replace the probabilities in Equation (1) with conditional probabilities given relevant random variables.

For conciseness, we will write either $\epsilon$ or $\epsilon(x)$ for $\epsilon(B(x))$ and likewise $\delta$ or $\delta(x)$ for $\delta(B(x))$.

We will also leverage the notion of zero-concentrated differential privacy (zCDP) (Bun and Steinke 2016), which often provides a cleaner analysis for privacy composition. First, we will recall the definition of Rényi divergence.

The Rényi divergence from $P$ to $Q$ of order $\lambda\geq 1$ is defined as

The notion of zCDP bounds the Rényi divergence from $A(x)$ to $A(x^{\prime})$ for any neighbors $x$ and $x^{\prime}$. We will focus on a conditional version of a more general definition called approximate zCDP (Bun and Steinke 2016; Papernot and Steinke 2022) that permits a small probability of unbounded Rényi divergence. The conditional approximate zCDP definition we provides uses the convex mixture formulation adapted from Papernot and Steinke 2022, since it is more convenient for our proof. In Appendix C.1, we will show that in the case $\delta$ and $\rho$ are constant, this definition is equivalent to the original definition in Bun and Steinke 2016.

where for all $\lambda\geq 1$, $D_{\lambda}(P^{\prime}(\cdot\mid z)\|Q^{\prime}(\cdot\mid z))\leq\rho(z)\lambda$ and $D_{\lambda}(Q^{\prime}(\cdot\mid z)\|P^{\prime}(\cdot\mid z))\leq\rho(z)\lambda$ for all $z\in\mathcal{Z}$.

We will also use the notions of filtration and martingales.

Privacy Filters

We now provide our main results on privacy filter. In general, a privacy filter is a function $N$ that takes the privacy parameters of a sequence of private algorithms as input and decides to stop at some point so that the composition of these algorithms satisfies a pre-specified level of privacy. We will first present a privacy filter for approximate zCDP (Theorem 1), which will immediately imply the privacy filter result for $(\epsilon,\delta)$-DP (Theorem 2). Since approximate zCDP bounds Rényi divergence of all orders $\lambda$, our proof for Theorem 1 also directly implies a privacy fiter for approximate RDP (Papernot and Steinke 2022), which generalizes the RDP filter by Feldman and Zrnic 2021.

Our $(\epsilon,\delta)$-DP filter improves on the rate of the original filter presented in Rogers et al. 2016 and matches the rate of advanced composition that requires pre-fixed choices of privacy parameters. Even though it is also possible to obtain an $(\epsilon,\delta)$-DP filter through the result of Feldman and Zrnic 2021, our privacy filters avoid their conversion costs and provide a tighter bound. Feldman and Zrnic 2021 apply Rényi filters to algorithms which satisfy (conditional) probabilistic differential privacy (pDP). In general, a lossy conversion from $(\epsilon,\delta)$-DP to $(\epsilon,\delta)$-pDP is required to apply their filter.

We can now state our general privacy filter in terms of approximate zCDP.

Then $A_{1:N(\cdot)}(\cdot)$ is $\delta$-approximate $\rho$-zCDP, where $N(x)=N((A_{n}(x))_{n\geq 1}).$

We note that the argument used to prove the above theorem immediately implies a privacy filter for approximate RDP, and thus Theorem 1 can be viewed as a strict generalization of the work of Feldman and Zrnic 2021. Further, Theorem 1 implies a privacy filter under $(\epsilon,\delta)$-differential privacy. To show this implication, we will use the following conversion results.

If $A$ satisfies $(\epsilon,\delta)$-DP, then $A$ satisfies $\delta$-approximate $\frac{1}{2}\epsilon^{2}$-zCDP. If $A$ satisfies $\delta$-approximate $\rho$-zCDP, then $A$ satisfies $(\rho+2\sqrt{\rho\ln(1/\delta^{\prime})},\delta+(1-\delta)\delta^{\prime})$-DP.

We can now obtain our $(\epsilon,\delta)$-privacy filter by a conversion of individual approximate differential privacy parameters to approximate zCDP ones, application of the approximate zCDP filter, and the conversion of approximate zCDP back to approximate differential privacy.

Then, the algorithm $A_{1:N(\cdot)}(\cdot)$ is $(\rho+2\sqrt{\rho\log(1/\delta)},\delta)$-DP, where $N(x):=N((A_{n}(x))_{n\geq 1}).$

In our proof, we assume that $\sum_{n=1}^{\infty}\delta_{n}(y_{1:n-1})\leq\delta$ for all sequences $(y_{n})_{n\geq 1}$ without loss of generality. Let $P_{1:n}$ and $Q_{1:n}$ denote the joint distributions of $(A_{1},\dots,A_{n})$ with inputs $x$ and $x^{\prime}$, respectively. We overload notation and write $P_{1:n}(y_{1},\dots,y_{n})$ and $Q_{1:n}(y_{1},\dots,y_{n})$ for the likelihood of $y_{1},\dots,y_{n}$ under input $x$ and $x^{\prime}$ respectively. We similarly write $P_{n}(y_{n}\mid y_{1:n-1})$ and $Q_{n}(y_{n}\mid y_{1:n-1})$ for the corresponding conditional densities.

By our assumption of approximate zCDP at each step $n$, we can write the conditional likelihoods of $P_{n}$ and $Q_{n}$ as the following convex combinations:

such that for all $\lambda\geq 1$ and all prior outcomes $y_{1:n-1}$, we have both

Now, from Lemma 7, we can then write these distributions as a convex combination of “good” distributions for which Rényi divergence is small, and “bad” distributions for which the divergence may be unbounded. In more detail, using the assumption that $\sum_{n=1}^{\infty}\delta_{n}(y_{1:n-1})\leq\delta$ for all seqeunces $(y_{n})_{n\geq 1},$ we have, for all $n\geq 1$,

In the above, we notate quantities in terms of “$N$” instead of “$N(x)$” or “$N(x^{\prime})$” since $N$ only depends on the underlying dataset $x$ or $x^{\prime}$ through the observed sequence of iterates $(y_{n})_{n\geq 1}$.

What remains now is to bound the Rényi divergence between $P_{N}^{\prime}$ and $Q_{N}^{\prime}$. We do this using an optional stopping argument for non-negative supermartingales (Lemma 5). Suppose $(Y_{n}^{\prime})_{n\geq 1}$ is a process whose $n$th finite-dimensional distribution is given by $P_{n}^{\prime}$. For any fixed $\lambda\geq 1$, define the process $(M_{n}^{(\lambda)})_{n\geq 0}$ by:

It is clear that $M_{n}^{(\lambda)}$ is a non-negative supermartingale with respect to natural filtration $(\mathcal{F}_{n}^{\prime})_{n\geq 1}$ given by $\mathcal{F}_{n}^{\prime}:=\sigma(Y_{m}^{\prime}:m\leq n)$, a fact that we confirm in Lemma 6. We emphasize that $(\mathcal{F}_{n}^{\prime})_{n\geq 1}$ is not in fact the data generating filtration, but rather a tool used for theoretical analysis. In more detail, we consider this filtration because, heuristically, approximate zCDP aims at bounding the moment generating function of a “good” portion of the joint distribution — the true joint distribution may allow some probability of catastrophic failure (i.e. unbounded privacy loss). We adopt the same convention that $N:=N(y_{1},y_{2},\dots)$ with the explicit values of $(y_{n})_{n\geq 1}$ clear from context. Observe that $N((Y_{n}^{\prime})_{n\geq 1})$ is a stopping time with respect to $(\mathcal{F}_{n}^{\prime})_{n\geq 0}$. We now invoke optional stopping (Lemma 5), which yields

What we have just showed is precisely that

which is precisely the desired result. A symmetric argument yields an identical bound on $D_{\lambda}(Q_{N}^{\prime}\mid P_{N}^{\prime})$. Thus, we have showed the desired result. ∎

Privacy Odometers

Previously, we constructed privacy filters that matched the rate of advanced composition while allowing both algorithms and privacy parameters to be chosen adaptively. While privacy filters require the total level of privacy to be fixed in advance, it is desirable to track the privacy loss at all steps without a pre-fixed budget (Ligett et al. 2017). We now study privacy odometers which provide sequences of upper bounds on accumulated privacy loss that are valid at all points in time simultaneously with high probability.

To formally introduce privacy odometers, we will first revisit the notion of privacy loss, which measures how much information is revealed about the underlying input dataset. For neighbors $x,x^{\prime}\in\mathcal{X}$, let $p^{x}$ and $p^{x^{\prime}}$ be the densities of $A(x)$ and $A(x^{\prime})$ respectively. The privacy loss between $A(x)$ and $A(x^{\prime})$ is defined as

By Equation (8), a negative privacy loss suggests that the input is more likely to be $x^{\prime}$, and likewise a positive privacy loss suggests that the input is more likely to be $x$. We now generalize privacy loss to its conditional counterpart.

Suppose $A_{n}$ is the $n$th algorithm being run and we have already observed $A_{1:n-1}(x)$ for some unknown input $x\in\mathcal{X}$. If we are trying to guess whether $x$ or a neighbor $x^{\prime}$ produced the data, we would consider the privacy loss between $A_{n}(x)$ and $A_{n}(x^{\prime})$ conditioned on $A_{1:n-1}(x)$. It is straightforward to characterize the privacy loss of a composed algorithm $A_{1:n}$ in terms of the privacy loss of each constituent algorithm $A_{1},\cdots,A_{n}$. Namely, from Bayes rule,

where $\mathcal{L}_{m}(x,x^{\prime})$ is shorthand for the conditional privacy loss between $A_{m}(x)$ and $A_{m}(x^{\prime})$ given $A_{1:m-1}(x)$, per Definition 4. Equation (9) also holds at arbitrary random times $N(x)$ that only depend on the dataset $x\in\mathcal{X}$ through observed algorithm outputs.

Unfortunately, as noted by Kasiviswanathan and Smith 2014 (in which pDP is called point-wise indistinguishability), pDP is a strictly stronger notion than DP. In particular, if an algorithm is $(\epsilon,\delta)$-pDP, it is also $(\epsilon,\delta)$-DP. The converse in general requires a costly conversion.

If $A$ is $(\epsilon,\delta)$-pDP, then $A$ is also $(\epsilon,\delta)$-DP. Conversely, if $A$ is $(\epsilon,\delta)$-DP, then $A$ is $(2\epsilon,\frac{2\delta}{\epsilon e^{\epsilon}})$-pDP.

We note that that Guingona et al. 2023 have recently shown that other possible conversion rates from probabilistic differential privacy to approximate differential privacy are possible. However, we note that these conversions require trading off tightness in the approximation parameter $\epsilon$ and the approximation parameter $\delta$. In particular, a fully tight conversion from probabilistic differenial privacy to approximate differential privacy is not possible. We will work with the conditional counterpart of probabilistic differential privacy (pDP).

While in Theorem 2 we assumed that the algorithms being composed were conditionally differentially private, here, we need to assume conditional probabilistic privacy. This is because our goal is not differential privacy, but rather tight control over privacy loss. We conjecture that a version of our privacy odometer (in Theorem 3) that replaces pDP by DP and leaves all else identical does not hold. Our intuition for this conjecture is that there exist simple examples of algorithms satisfying $(\epsilon,\delta)$-DP that don’t satisfy $(\epsilon,\delta)$-pDP (see Appendix F, for instance). We believe that, by sequentially composing such algorithms and using anti-concentration results, one can show that some odometers fail to be valid. We leave this as potential future work. In sequential composition, we would assume the $n$th algorithm $A_{n}$ is $(\epsilon_{n},\delta_{n})$-pDP conditioned on $A_{1:n-1}$. The privacy parameters would be given as functions of $A_{1:n-1}(x)$. Now we state the definition of privacy odometer, which provides bounds on privacy loss under arbitrary stopping conditions (e.g.​ conditions based on model accuracy).

2 Improved Privacy Odometers

We then extend to the case of $\delta_{n}\geq 0$ via conditioning.

To construct their filters and odometers, Rogers et al. 2016 use self-normalized concentration inequalities (de la Pena et al. 2004; Chen et al. 2014). We instead use advances in time-uniform martingale concentration (Howard et al. 2020; Howard et al. 2021), which yields tighter results.

Filter odometer. For any $\epsilon>0$, let $y^{\ast}:=\left(-\sqrt{2\log\left(\frac{1}{\delta^{\prime}}\right)}+\sqrt{2\log\left(\frac{1}{\delta^{\prime}}\right)+\epsilon}\right)^{2}$. Define functions $(u_{n}^{F})_{n\geq 1}$ by

Mixture odometer. For any $\gamma>0$, define the sequence of functions $(u_{n}^{M})_{n\geq 1}$ by

Stitched odometer. For any $v_{0}>0$, define the sequence of functions $(u_{n}^{S})_{n\geq 1}$ by

Then, any of the sequences $(u_{n}^{F})_{n\geq 1}$, $(u_{n}^{M})_{n\geq 1}$, or $(u_{n}^{S})_{n\geq 1}$ is a $\delta$-privacy odometer.

The proof of Theorem 3 can be found in Appendix E. We now provide intuition for our odometers, which are plotted in Figure 3. Our insight is to view odometers not as functions of the number of algorithms being composed, but rather as functions of the intrinsic time $\sum_{m\leq n}\epsilon_{m}^{2}$. This reframing allows us to leverage the various time-uniform concentration inequalities discussed in Appendix B. The filter odometer is the tightest odometer when the value $\sum_{m\leq n}\epsilon_{m}^{2}$ is close to a fixed accumulated variance $y^{\ast}$, but the tightness drops off precipitously when $\sum_{m\leq n}\epsilon_{m}^{2}$ is far from $y^{\ast}$. The mixture odometer, which is named after the the method of mixtures (Robbins 1970; de la Peña et al. 2007; Howard et al. 2021), sacrifices tightness at any fixed point in time to obtain overall tighter bounds on privacy loss. This odometer can be numerically optimized, in terms of $\rho$, for tightness at a predetermined value $\sum_{m\leq n}\epsilon_{m}^{2}$. The stitched odometer, whose name derives from Theorem 6, is similarly tight across time. This odometer requires that $\sum_{m\leq n}\epsilon_{m}^{2}$ exceed some pre-selected “variance” $v_{0}$ before becoming nontrivial (i.e. finite). Larger values of $v_{0}$ will yield tighter odometers, albeit at the cost of losing bound validity when accumulated variance is small. With this intuition, we can compare our odometers to the original presented in Rogers et al. 2016.

Assume the same setup as Theorem 3, and fix $\delta=\delta^{\prime}+\delta^{\prime\prime}$, where $\frac{1}{e}\geq\delta^{\prime}>0$ and $\delta^{\prime\prime}\geq 0$. Define the sequence of functions $(u_{n}^{R})_{n\geq 1}$ by

where $|x|$ denotes the number of elements in dataset $x$. Then, $(u_{n}^{R})_{n\geq 1}$ is a $\delta$-privacy odometer.

Our new odometers improve over the one presented in Lemma 3. First, the above odometer has an explicit dependence on dataset size. In learning settings, datasets are large, degrading the quality of the odometer. Secondly, the tightness of the odometer drops off outside of the interval $\left[\frac{1}{|x|^{2}},1\right]$. If any privacy parameter of an algorithm being composed exceeds $1$, the bound becomes significantly looser. Lastly, and perhaps most simply, the form of the odometer is complicated. Our odometers all have relatively straightforward dependence on the intrinsic time $\sum_{m\leq n}\epsilon_{m}^{2}$.

We now examine the rates of all odometers. For simplicity, let $v:=\sum_{m\leq n}\epsilon_{m}^{2}$. The stitched odometer has a rate of $O(\sqrt{v\log\log(v)})$ in its leading term, asymptotically matching the law of the iterated logarithm (Robbins 1970) up to constants. Both the original privacy odometer and the mixture odometer have a rate of $O(\sqrt{v\log\left(v\right)})$, demonstrating worse asymptotic performance. The filter odometer has the worst asymptotic performance, growing linearly as $O\left(v\right)$. This does not mean the stitched odometer is the best odometer, since target levels of privacy are often kept small.

To empirically compare odometers, it suffices to consider the setting of pure differential privacy, as the odometers identically depend on $(\delta_{n})_{n\geq 1}$. Each presented odometer can be viewed as a function of $v$, allowing us to compare odometers by plotting their values for a continuum of $v$. Figure 3(a) shows that there is no clearly tightest odometer. All odometers, barring the original, dominate for some window of values of $v$. While the stitched odometer is asymptotically best, the mixture odometer is tighter for small values of $v$. Likewise, if one knows an approximate target privacy level, the filter odometer is tightest. This behavior is expected from our understanding of martingale concentration (Howard et al. 2020; Howard et al. 2021): there is no uniformly tightest boundary containing (with probability $1-\delta$) the entire path of a martingale; boundaries that are tight early must be looser later, and vice versa. In fact, we conjecture that our bounds are essentially unimprovable in general — this conjecture stems from the fact that the time-uniform martingale boundaries employed have error probability essentially equal to $\delta$, which in turn stems from the deep fact that for continuous-path (and thus continuous-time) martingales, Ville’s inequality (Fact 4)—that underlies the derivation of these boundaries—holds with exact equality. Since we operate in discrete-time, the only looseness in Ville’s inequality stems from lower-order terms that reflect the possibility that at the stopping time, the value of the stopped martingale may not be exactly the value at the boundary.

In Figure 3(b), we compare our odometers with advanced composition optimized in a point-wise sense for all values of $v$ simultaneously. This boundary is not a valid odometer, as advanced composition only holds at a prespecified point in intrinsic time $v$. Our odometers are almost tight with advanced composition for the values of $v$ plotted. Our filter odometer lies tangent to the advanced composition curve, as expected from Section 5.2 of Howard et al. 2020.

Future Directions

There are many open problems related to fully adaptive composition. For example, even though privacy filters have been studied under the notion of Gaussian DP (Smith and Thakurta 2022; Koskela et al. 2022), privacy filters and odometers have not been studied for general $f$-DP (Dong et al. 2021). It also has not been investigated whether adaptivity in privacy parameter selection improves the performance of iterative algorithms such as private SGD. Intuitively, it should be beneficial to let the iterates of an algorithm guide future choices of privacy parameters. Optimal composition results (Kairouz et al. 2015; Murtagh and Vadhan 2016; Zhu et al. 2022) have yet to be considered in a setting where privacy parameters are adaptively selected. In Appendix D, we provide another proof of Theorem 2, which leverages a reduction of private algorithms to generalized randomized response. Since such a reduction was used in the proofs of Kairouz et al. 2015 and Murtagh and Vadhan 2016, we believe this proof can be useful for optimal composition with adaptively chosen privacy parameters.

AR acknowledges support from NSF DMS 1916320 and an ARL IoBT CRA grant. Research reported in this paper was sponsored in part by the DEVCOM Army Research Laboratory under Cooperative Agreement W911NF-17-2-0196 (ARL IoBT CRA). The views and conclusions contained in this document are those of the authors and should not be interpreted as representing the official policies, either expressed or implied, of the Army Research Laboratory or the U.S. Government. The U.S. Government is authorized to reproduce and distribute reprints for Government purposes notwithstanding any copyright notation herein. ZSW and JW were supported in part by the NSF CNS2120667, NSF Award #2120667, a CyLab 2021 grant, a Google Faculty Research Award, and a Mozilla Research Grant. JW acknowledges support from NSF GRFP grants DGE1745016 and DGE2140739.

References

Appendix A Measure-Theoretic Formalism

Below, we provide some measure-theoretic formalisms and details regarding datasets and neighboring relations.

Roughly speaking, an algorithm is differentially private if it difficult to distinguish between output distributions when the algorithm is run on similar inputs. In general, this notion of similarity amongst inputs is defined as a neighboring relation $\sim$ between elements on the input space $\mathcal{X}$. In particular, if two inputs (also referred to as datasets or databases) $x,x^{\prime}\in\mathcal{X}$ satisfy the neighboring relation $x\sim x^{\prime}$, the we say $x$ and $x^{\prime}$ are neighbors.

Algorithms and Random Variables:

We will consider algorithms as randomized mappings $A:\mathcal{X}\rightarrow\mathcal{Y}$ taking inputs from $\mathcal{X}$ to some output space $\mathcal{Y}$. To be fully formal, we consider the output space $\mathcal{Y}$ as a measurable space $(\mathcal{Y},\mathcal{G})$, where $\mathcal{G}$ is some $\sigma$-algebra denoting possible events. Recall that a $\sigma$-algebra $\mathcal{S}$ for a set $S$ is simply a subset of $2^{S}$ containing $S$ and $\emptyset$ that is closed under countable union, intersection, and complements. When we say $A$ is an algorithm having inputs in some space $\mathcal{X}$, we really mean $A(x)$ is a $\mathcal{Y}$-valued random variable for any $x\in\mathcal{X}$. The space $\mathcal{X}$ need not have an associated $\sigma$-algebra, as algorithm inputs are essentially just indexing devices. Given a sequence of algorithms $(A_{n})_{n\geq 1}$, $(A_{n}(x))_{n\geq 1}$ is a sequence of $\mathcal{Y}$-valued random variables, for any $x\in\mathcal{X}$. Even if algorithms have different types of outputs (maybe some algorithms have categorical outputs while others output real-valued vectors), $\mathcal{Y}$ can still be made appropriately large to contain all possible outcomes.

Filtrations and Stopping Times:

Appendix B Martingale Inequalities

In this appendix, we provide a thorough exposition into the concentration inequalities leveraged in this paper. First, at the heart of supermartingale concentration is Ville’s inequality [Ville 1939], which can be viewed as a time-uniform version of Markov’s inequality.

We do not directly leverage Ville’s inequality in this work, but all inequalities we use can be directly proven from Lemma 4 [Howard et al. 2020, Howard et al. 2021]. In short, each inequality in this supplement is proved by carefully massaging a martingale of interest into a non-negative supermartingale.

Another useful tool we will leverage is Doob’s optional stopping theorem.

For our alternative proof of the privacy filter (in Section D), we leverage the following special case of a recent advance in time-uniform martingale concentration [Howard et al. 2020]. The following Theorem 4 is just a special case of the main result in Howard et al. 2020, and we include the proof for completeness. When we say a random variable $X$ is $\sigma^{2}$-subGaussian conditioned on some sigma-algebra $\mathcal{G}$, we mean that, for all $\lambda\geq 0$,

In particular, if $X$ is $\sigma^{2}$-subGaussian as above, this does not imply that $-X$ is $\sigma$-subGaussian (because the condition is only assumed for $\lambda\geq 0$). In general, $X$ can have different behaviors in its left and right tail, see for example the discussion of the differing tails of the empirical variance of Gaussians in Howard et al. 2021.

is a non-negative supermartingale. As such, applying Ville’s inequality (Lemma 4) yields

Now, on such event, taking logs and rearranging yields

Multiplying both sides by $\frac{a}{b}$ finishes the proof.∎

We also leverage the following martingale inequalities from Howard et al. 2021 in Section 4, where we construct various families of time-uniform bounds on privacy loss in fully-adaptive composition. These inequalities take on a more complicated form than Theorem 4, but we explain the intuition behind them in the sequel. The first bound we present relies on the method of mixtures for martingale concentration, which stems back to Robbins’ work in the 1970s [Robbins 1970]. There are many good resources providing an introduction to the method of mixtures [de la Peña et al. 2007, Kaufmann and Koolen 2021, Howard et al. 2021].

Note that the original version of Theorem 6 as found in Howard et al. 2021 has more free parameters to optimize over, but we have already simplified the expression to make the result more readable. The free parameter $v_{0}>0$ in the above boundary gives the intrinsic time at which the boundary becomes non-trivial (i.e., the tightest available upper bound before $V_{n}\geq v_{0}$ is $\infty$).

We qualitatively compare these bounds in Section 4, wherein we construct various time-uniform bounds on privacy loss processes. For now, Theorem 4 can be thought of as providing a tight upper bound on a martingale at a single point in intrinsic time, providing loose guarantees elsewhere. On the other hand, Theorems 5 and 6 provide decently tight control over a martingale at all points in intrinsic time simultaneously, although at the cost of sacrificing tightness at any given fixed point.

Appendix C Details in Proof of Approx-zCDP Filter

We will show that our definition of approximate zCDP is equivalent to the original definition of approximate zCDP due to Bun and Steinke 2016. Let us first restate their definition as a condition on a private algorithm $A$.

For any neighboring datasets $x,x^{\prime}$, there exist events $E$ and $E^{\prime}$ such that for all $\lambda\geq 1$,

Our definition is adapted from the approximate Rényi differential privacy definition due to Papernot and Steinke 2022. We restate the (unconditional) definition below.

For any neighboring datasets $x,x^{\prime}$, there exist distributions $P^{\prime},P^{\prime\prime},Q^{\prime},Q^{\prime\prime}$ such that the outputs are distributed according to the following mixture distributions:

with $\text{for all }\lambda\geq 1,\penalty\ D_{\lambda}(P^{\prime}\|Q^{\prime})\leq\rho\lambda$ and $D_{\lambda}(P^{\prime}\|Q^{\prime})\leq\rho\lambda$.

Then $A(x)$ is distributed according to the mixture $(1-\delta)P^{\prime}+\delta P^{\prime\prime}$, and $A(x^{\prime})$ is distributed according to the mixture $(1-\delta)Q^{\prime}+\delta Q^{\prime\prime}$. Thus, $A$ also satisfies condition 2 given that $D_{\lambda}(P^{\prime}\|Q^{\prime})\leq\lambda\rho$ and $D_{\lambda}(Q^{\prime}\|P^{\prime})\leq\lambda\rho$ by our assumption of Condition 1.

Now suppose $A$ satisfies Condition 2 for some pairs of distributions $(P^{\prime},P^{\prime\prime})$ and $(Q^{\prime},Q^{\prime\prime})$. Then we can view the output distribution of $A(x)$ as generating a Bernoulli random variable $C$ such that with probability $(1-\delta)$, $C=1$ and $A(x)$ draws an outcome from $P^{\prime}$ and with probability $C=0$ and $A(x)$ draws an outcome from $P^{\prime\prime}$. Similarly, we can view $A(x^{\prime})$ as flipping a coin $C^{\prime}$ such that $A(x^{\prime})$ draws an outcome from $Q^{\prime}$ when $C^{\prime}=1$. Then letting the events $E$ be all the randomness of $A(x)$ such that $C=1$ and $E^{\prime}$ be all the randomness of $A(x^{\prime})$ such that $C^{\prime}=1$ satisfies condition 1. ∎

C.2 Missing Proofs

The following proof technique was used in prior works, including Cesar and Rogers 2021, Feldman and Zrnic 2021

Let $(M_{n}^{(\lambda)})_{n\geq 1}$ be as defied in Equation (7). Then, $(M_{n}^{(\lambda)})_{n\geq 1}$ is a non-negative supermartingale with respect to its natural filtration $(\mathcal{F}^{\prime}_{n})_{n\geq 1}$ given by $\mathcal{F}_{n}:=\sigma(Y_{m}^{\prime}:m\leq n)$.

where the last inequality follows from the R[́enyi divergence bound due to approximate zCDP. ∎

Let the distributions $P_{1:n},Q_{1:n},P^{\prime}_{1:n},Q^{\prime}_{1:n}$ be defined in (5), (6) for any $n\geq 1$. Then there exists distributions $P^{\prime\prime}_{1:n}$ and $Q^{\prime\prime}_{1:n}$ such that

We will show the decomposition for $P_{1:n}$, and the proof follows identically for the decomposition of $Q_{1:n}$. First, we can express $P_{1:n}(y_{1},\cdots,y_{n})$ for any $y_{1},\cdots y_{n}$ as follows:

It suffices to show that $w_{\emptyset}(y_{1:m})\geq 1-\delta$ for all $y_{1:m}$. To see this, we have the following by assumption

Appendix D An Alternative Proof for Theorem 2

We begin by providing an alternative statement to Theorem 2, which is fully stated in terms of $\epsilon$’s and $\delta$’s. Straightforward calculations can confirm the equivalence of the two statements.

Then, the algorithm $A_{1:N(\cdot)}(\cdot):\mathcal{X}\rightarrow\mathcal{Y}^{\infty}$ is $(\epsilon,\delta)$-DP, where $N(x):=N((\epsilon_{n}(x))_{n\geq 1},(\delta_{n}(x))_{n\geq 1})$. In other words, $N$ is an $(\epsilon,\delta)$-privacy filter.

We first prove Theorem 8 under a stronger assumption on the algorithms being composed.

Theorem 8 holds under the stronger assumption that, for any $n\geq 1$, $A_{n}$ is $(\epsilon_{n},\delta_{n})$-pDP conditioned on $A_{1:n-1}$.

To prove Lemma 8, we need to following bound on the conditional expectation of privacy loss, which can be immediately obtained from the bound on expected privacy loss presented in Bun and Steinke 2016.

Suppose $A$ and $B$ are algorithms such that $A$ is $\epsilon$-differentially private conditioned on $B$. Then, for any input dataset $x\in\mathcal{X}$ and neighboring dataset $x^{\prime}\sim x$, we have that

Thus, by Theorem 4, we know that, for any $b,a>0$, we have

Clearly, $f$ is a quadratic polynomial in $\sqrt{y}$ which is strictly increasing. In particular, one can readily check that

solves the equation $f(y)=\epsilon$, where $\epsilon>0$ is the target privacy parameter.

As such, setting $a:=y^{\ast}$ and $b:=\sqrt{2\log\left(\frac{1}{\delta^{\prime}}\right)y^{\ast}}$ yields

Thus, we have proven the desired result in the case where all algorithms have $\delta_{n}=0$.

Now, we show how to generalize our result to the case where the approximation parameters $\delta_{n}$ are not identically zero. Define the events

Thus, we have have proven the desired result in the general case.∎

Our key insight above is to view filters as functions of the “intrinsic time” determined by privacy parameters, $\sum_{m\leq n}\epsilon_{m}^{2}$. Lemma 8 can also be obtained leveraging the analysis for Rényi filters [Feldman and Zrnic 2021]. However, our approach to proving Lemma 8 has the advantage that it does not require reductions between different modes of privacy. While Lemma 9, which bounds expected privacy loss, does require some complicated analysis, we only ever need to apply Lemma 8 to instances of randomized response, in which case computing the privacy loss bound is trivial.

We now use Lemma 8 to prove Theorem 8. Recall that Lemma 2 shows that algorithms that satisfy pDP also satisfy DP, but the converse is not true and may require a conversion cost. To avoid this cost, we define following generalization of randomized response.

Let $\mathcal{R}:=\{0,1,\top,\bot\}$ and $2^{\mathcal{R}}$ be the corresponding power set of $\mathcal{R}$. Then, $R$ taking inputs in $\{0,1\}$ to outputs in the measurable space $(\mathcal{R},2^{\mathcal{R}})$ is an instance of $(\epsilon,\delta)$-randomized response if, for $b\in\{0,1\}$, $R(b)$ outputs the following:

Conditional $(\epsilon,\delta)$-randomized response satisfies both conditional $(\epsilon,\delta)$-DP and conditional $(\epsilon,\delta)$-pDP. We will leverage the fact that it satisfies both privacy definitions with the same parameters. A surprising result in the nonadaptive setting is that any $(\epsilon,\delta)$-DP algorithm can be viewed as a randomized post-processing of $(\epsilon,\delta)$-randomized response [Kairouz et al. 2015]. We generalize this result to the adaptive conditional setting below. In the language of Blackwell’s comparison of experiments [Blackwell 1953], instances of randomized response are “sufficient” for instances of arbitrary DP algorithms, and we prove that the same is true for conditional randomized response and conditionally DP algorithms. In what follows, by a transition kernel $\nu$, we mean that for any $b\in\mathcal{Z}$ and $r\in\mathcal{R}$, $\nu(\cdot,r\mid b)$ is a probability measure on $(\mathcal{Y},\mathcal{G})$.

Lemma 10 tells us that the conditional distribution obtained by averaging the kernel $\nu(\cdot,R(b)\mid B^{\prime}(b^{\prime}))$ over the randomness in $R(b)$ matches the conditional distribution of $A(x_{b})$. To prove Lemma 10, first recall the important fact that any differentially private algorithm can be viewed as a post-processing of randomized response [Kairouz et al. 2015], as stated in Lemma 11 below.

In Lemma 10 of Section 3, we generalized Lemma 11 to the case of conditional differential privacy. To do this, we introduced conditional randomized response in Definition 7. In conditional randomized response, on the event $\{B=z\}$, the conditional laws of $R(0)$ and $R(1)$ just become that of regular randomized response with some known privacy parameters $\epsilon(z)$ and $\delta(z)$. We now prove Lemma 10.

where the conditionally averaged measure is as described in Footnote 7 in the main body of the paper. This proves the desired result. ∎

Lastly, before proving Theorem 8, we need the following lemma. This lemma essentially tells us that if $A$ is $(\epsilon,\delta)$-pDP conditioned on $B$, and $A^{\prime}$ is a randomized post-processing algorithm, then releasing the vector $(A,A^{\prime})$ is also $(\epsilon,\delta)$-pDP conditioned on $B$. Note that this is not in contradiction with the converse direction of Lemma 2, as releasing the output of $A^{\prime}$ alone may not satisfy conditional $(\epsilon,\delta)$-pDP. But once we observe $A$, since $A^{\prime}$ is a post-processing, we can gleam no more information about the true underlying dataset.

Suppose $A,B$ are algorithms with inputs in $\mathcal{X}$ and outputs in measurable spaces $(\mathcal{Y},\mathcal{G})$ and $(\mathcal{Z},\mathcal{H})$ respectively. Assume $A$ is $(\epsilon,\delta)$-pDP conditioned on $B$. Let $(S,\mathcal{S})$ be a measurable space and suppose $\mu:\mathcal{S}\times\mathcal{Y}\times\mathcal{Z}\rightarrow$ is a conditional transition kernel. Suppose $A^{\prime}:\mathcal{X}\rightarrow S$ is an algorithm satisfying

for all $y\in\mathcal{Y},z\in\mathcal{Z}$, and $x,x^{\prime}\in\mathcal{X}$. Then, the joint algorithm $(A,A^{\prime}):\mathcal{X}\rightarrow\mathcal{Y}\times S$ is also $(\epsilon,\delta)$-pDP conditioned on $B$.

Let $x,x^{\prime}\in\mathcal{X}$ be arbitrary neighboring datasets. Let $q^{x}_{B},q^{x^{\prime}}_{B}$ be the corresponding conditional joint densities of $(A(x),A^{\prime}(x))$ and $(A(x^{\prime}),A^{\prime}(x^{\prime}))$ given $B(x)$ respectively. Likewise, let $p^{x}_{B},p^{x^{\prime}}_{B}$ be the corresponding conditional densities of $A(x)$ and $A(x^{\prime})$ respectively conditioned on $B(x)$, and $q^{x}_{B,A},q^{x^{\prime}}_{B,A}$ the conditional densities of $A^{\prime}(x)$ and $A^{\prime}(x^{\prime})$ given $A(x)$ and $B(x)$. Let $\mathcal{L}_{B}^{(A,A^{\prime})}(x,x^{\prime})$ denote the joint privacy loss between $(A(x),A^{\prime}(x))$ and $(A(x^{\prime}),A^{\prime}(x^{\prime}))$ given $B(x)$, while $\mathcal{L}_{B}^{A}(x,x^{\prime})$ denotes the privacy loss between $A(x)$ and $A(x^{\prime})$ given $B(x)$. We have, using Bayes rule,

The first equality on the second line follows from the assumption outlined in Equation (12). More specifically, since we have

it follows that the conditional densities $q^{x}_{B,A}$ and $q^{x^{\prime}}_{B,A}$ are equal almost surely. Since $A$ is $(\epsilon,\delta)$-pDP conditioned on $B$, the result now follows. ∎

We now can prove Theorem 8 using these tools.

Now, for any $n\geq 1$, since $R_{n}$ is an instance of $(\epsilon_{n},\delta_{n})$-randomized response conditioned on $A^{\prime}_{1:n-1}$, it follows that $R_{n}$ is in fact $(\epsilon_{n},\delta_{n})$-pDP conditioned on $A^{\prime}_{1:n-1}$. Moreover, this also implies that $R_{n}$ is $(\epsilon_{n},\delta_{n})$-pDP conditioned on $(A^{\prime}_{1:n-1},R_{1:n-1})$, since, by definition, $\epsilon_{n}$ and $\delta_{n}$ only depend on the realizations of $R_{1:n-1}$ through the outputs of $A^{\prime}_{1:n-1}$. By Lemma 12, it follows that for all $n\geq 1$, the algorithm $(R_{n},A^{\prime}_{n})$ is $(\epsilon_{n},\delta_{n})$-pDP conditioned on $(R_{1:n-1},A^{\prime}_{1:n-1})$. Thus, by Lemma 8, it follows that the composed algorithm $(R_{1:N^{\prime}(\cdot)}(\cdot),A^{\prime}_{1:N^{\prime}(\cdot)}(\cdot))$ is $(\epsilon,\delta)$-DP, where $N^{\prime}(b):=N(x_{b})$ and $\epsilon,\delta$ and $N$, are as outlined in the statement of Theorem 2.

Lastly, since differential privacy is closed under arbitrary post-processing [Dwork and Roth 2014], it follows that $A^{\prime}_{1:N^{\prime}(\cdot)}(\cdot)$ is $(\epsilon,\delta)$-differentially private. Since $x_{0}$ and $x_{1}$ were arbitrary neighboring inputs, the result follows, i.e. $A_{1:N(\cdot)}(\cdot):\mathcal{X}\rightarrow\mathcal{Y}^{\infty}$ is $(\epsilon,\delta)$-differentially private. ∎

Appendix E Proof for Privacy Odometers in Theorem 3

We now show the formal proof for our privacy odometers presented in Theorem 3 in Section 4.

where $(\mathcal{F}_{n}(x))_{n\geq 1}$ is again the natural filtration generated by $(A_{n}(x))_{n\geq 1}$. Thus, since $x\sim x^{\prime}$ were arbitrary, we have shown that $(u_{n})_{n\geq 1}$ is a $\delta$-privacy odometer in the case $\delta_{n}=0$ for all $n\geq 1$.

To generalize to the case where $\delta_{n}$ may be nonzero, we can apply precisely the same argument used in the second part of the proof of Lemma 8, thus proving the general result. ∎

Appendix F An Algorithm Satisfying (ϵ,δ)(\epsilon,\delta)-DP but not (ϵ,δ)(\epsilon,\delta)-pDP

In this appendix, we construct a simple algorithm taking binary inputs that satisfies $(\epsilon,\delta)$-DP but not $(\epsilon,\delta)$-pDP. In particular, this provides intuition as to why we conjecture our odometers constructed in Section 4 would not hold under the assumption that the algorithms being composed satisfy $(\epsilon,\delta)$-DP in general.

To this end, fix a privacy parameter $\epsilon>0$ and an approximation parameter $\delta\in(0,1)$. Let $A:\{0,1\}\rightarrow\{0,1,\top,\bot\}$ be an instance of $(\epsilon,\delta)$-randomized response, and let $B:\{0,1\}\rightarrow\{0,1\}$ be defined by

Since differential privacy is closed under arbitrary post-processing, it follows that the constructed algorithm $B$ is $(\epsilon,\delta)$-differentially private. On the other hand, setting $x=1$, $x^{\prime}=0$, we note that on the event $\left\{B(1)=1\right\}$,

we see that $B$ does not satisfy $(\epsilon,\delta)$-pDP.