Practical Privacy Filters and Odometers with Rényi Differential Privacy
and Applications to Differentially Private Deep Learning

RDP (Mironov, 2017) is also a relaxation of pure DP that always implies approximate DP, though the converse in not always true.

Complex sequences of interactions with the data, such as the adaptive privacy budget interactions we focus on in this work, can be challenging to express precisely. Following (Rogers et al., 2016), we express them in the form of an algorithm that describes the power and constraints of an analyst, or adversary since it models worst case behavior, interacting with the data. Algorithm 1 shows this interaction setup for a privacy filter.

Specifically, an adversary $A$ will interact for $k$ rounds —$k$ does not appear in the bounds and can be chosen arbitrarily large—, in one of two “neighboring worlds” indexed by $b\in\{0,1\}$. Typically, the two worlds will represent two neighboring datasets with an observation added or removed, but this formulation allows for more flexibility by letting $A$ chose two neighboring datasets at each round, as well as the DP mechanism to use and its RDP parameters. Each decision can be made conditioned on the previous results.

Our RDP filter $\textrm{FILT}_{\alpha,\epsilon_{\textrm{RDP}}}$ of order $\alpha$ can PASS on a computation at any time, setting $\epsilon_{i}=0$ and returning $\perp$ to $A$. Sections 3.2 and 3.3 describe how to instantiate this filter to provide RDP and DP guarantees. The final output of the algorithm is a view $V^{b}=(v_{1},\ldots,v_{k})$ of all results from the computations. With a slight abuse of notation, we call $V^{b}_{i}$ the distribution over possible outcomes for the $i^{th}$ query, and $v_{i}\sim V^{b}_{i}$ an observed realization.

This way, we can explicitly write the dependencies of the $i^{th}$ query’s distribution as $V^{b}_{i}(v_{i}|v_{\leq i-1})$, where $v_{\leq i}$ is the view of all realized outcomes up to, and including, the $i^{th}$ query. Similarly, the joint distribution over possible views is $V^{b}(v_{\leq n})$. The budget of the $i^{th}$ query, $\epsilon_{i}$ depends only on all queries up to the previous one, which we note explicitly as $\epsilon_{i}(v_{\leq i-1})$. DP seeks to bound the information about $b$ that $A$ can learn from the results of its DP computations. Following Equation 1, we want to bound with high probability under $v\sim V^{0}$ the privacy loss incurred by the sequence of computations $|\textrm{Loss}(v)|=\big{|}\log\big{(}\frac{V^{0}(v_{\leq n})}{V^{1}(v_{\leq n})}\big{)}\big{|}$.

We first analyse the filter $\textrm{FILT}_{\alpha,\epsilon_{\textrm{RDP}}}(\epsilon_{1},\ldots,\epsilon_{i},0,\ldots,0)$ that will PASS when:

The filter PASSes when the new query would cause the sum of all budgets used so far to go over $\epsilon_{\textrm{RDP}}$. We next show that this filter ensures that Algorithm 1 is $(\alpha,\epsilon_{\textrm{RDP}})$-RDP.

A powerful feature of RDP is to be able to compose mechanisms over their whole $(\alpha,\epsilon)$ curve. Since for many mechanisms this curve is not linear, it is unclear in advance which $\alpha$ would yield the best final $(\epsilon,\delta)$-DP guarantee through Equation 2. This composition “over all $\alpha$s” is important, as it enables RDP’s strong composition results.

We can extend our privacy filter and Theorem 1 to this case. Consider a (possibly infinite) sequence of $\alpha$ values to track, noted $\Lambda$, and an upper bound $\epsilon_{\textrm{RDP}}(\alpha)$ for each of these values. In Algorithm 1, the mechanism $M_{i}$ is now $\big{(}\alpha,\epsilon_{i}(\alpha)\big{)}$-RDP for $\alpha\in\Lambda$. The filter $\textrm{FILT}_{\alpha,\epsilon_{\textrm{RDP}}(\alpha)}\big{(}\epsilon_{1}(\alpha),\ldots,\epsilon_{i}(\alpha),0,\ldots,0\big{)}$ will now PASS when:

A key application of Corollary 1 is to build a privacy filter that enforces an $(\epsilon_{\textrm{DP}},\delta)$-DP guarantee, and leverages RDP to ensure strong composition. Intuitively, for each $\alpha$ the corresponding $\epsilon_{\textrm{RDP}}(\alpha)$ is set to the value which, for this $\alpha$, implies the desired $(\epsilon_{\textrm{DP}},\delta)$-DP target. Formally, based on Equation 2 we set the filter from Equation 4 to $\forall\alpha\in\Lambda:\epsilon_{\textrm{RDP}}(\alpha)=\epsilon_{\textrm{DP}}-\frac{\log(1/\delta)}{\alpha-1}$. Applying Corollary 1 followed by Equation 2 shows that under this filter, Algorithm 1 is $(\epsilon_{\textrm{DP}},\delta)$-DP.

This is significant, as this construction yields strong DP composition with a simple additive (RDP) privacy filter. There is no overhead compared to non-adaptive RDP, which yields tighter results than DP strong composition in many practical settings, such as the composition of Gaussian mechanisms ubiquitous in DP deep learning. On the contrary, Theorem 5.1 from (Rogers et al., 2016) is restricted to DP strong composition, and pays a significant multiplicative constant. The result from Theorem 1 already appears in (Feldman & Zrnic, 2020) as a corollary to a more general result. Here we show a proof closer to that of RDP composition, that we will re-use in subsequent results. We also explicitly show how to implement filters over the Rényi curve in §3.3.

Algorithm 2 formalizes our privacy odometer setup. The adversary $A$ can now interact with the data in an unrestricted fashion. For the given RDP order $\alpha$, the odometer returns the view and the RDP parameter $\epsilon_{\textrm{RDP}}^{tot}$, which must be a running upper-bound on $D_{\alpha}\big{(}V^{0}(v_{\leq i})||V^{1}(v_{\leq i})\big{)}$ since the interaction can stop at any time.

Analyzing such an unbounded interaction directly with RDP is challenging, as the very RDP parameters can change at each step based on previous realizations of the random variable, and there is no limit enforced on their sum. We sidestep this challenge by initiating the odometer with a sequence of $\epsilon_{\textrm{RDP}}^{f}$, with $f\in\mathbb{N}_{1}$ a strictly positive integer. After each new RDP computation, we compute the smallest $f$ such that a filter $\textrm{FILT}_{\alpha,\epsilon_{\textrm{RDP}}^{f}}$ initiated with budget $\epsilon_{\textrm{RDP}}^{f}$ would not PASS. We show how to analyse the privacy guarantees of this construct in sections 4.2 and 4.3, before extending it to support RDP accounting over the Rényi curve in section 4.4. Finally, section 4.5 discusses how to instantiate $\epsilon_{\textrm{RDP}}^{f\in\mathbb{N}_{1}}$ to get efficient odometers.

To analyse Algorithm 2, we define a truncation operator $\textrm{trunc}_{\leq f}$, which changes the behavior of an adversary $A$ to match that of a privacy filter of size $\epsilon_{\textrm{RDP}}^{f}$. Intuitively, $\textrm{trunc}_{\leq f}(A)$ follows $A$ exactly until $A$ outputs an RDP mechanism that would cause a switch to the $(f+1)^{th}$ filter. When this happens, $\textrm{trunc}_{\leq f}(A)$ stops interacting until the end of the $k$ queries. More precisely, at round $i$ $\textrm{trunc}_{\leq f}(A)$ outputs the same $D_{i}^{0},D_{i}^{1}$, $\epsilon_{i}$, and $M_{i}$ as $A$ as long as $\arg\min_{g}\{\textrm{FILT}_{\alpha,\epsilon_{\textrm{RDP}}^{g}}(\epsilon_{0},\ldots,\epsilon_{i},0,\ldots,0)\neq\textrm{PASS}\}\leq f$. Otherwise, $\textrm{trunc}_{\leq f}(A)$ returns $\epsilon_{i}=0$ and $M_{i}:x\rightarrow\perp$.

We similarly note $\textrm{trunc}_{\leq f}(V^{b})$ the distribution over possible views when adversary $\textrm{trunc}_{\leq f}(A)$ interacts following Algorithm 2, and $\textrm{trunc}_{\leq f}(v)$ a corresponding truncation of a view generated by adversary $A$. This truncated adversary behaves like a privacy filter, yielding the following result.

We note that the odometer from (Feldman & Zrnic, 2020) (Proposition 5.2) is closer to this truncated odometer than to the odometer from (Rogers et al., 2016). Indeed, the guarantee it gives is for $k$ stacked privacy filters, where $k$ is fixed in advance. If applied with an adaptive $k$ (e.g. early stopping) the result would violate the lower bound proven in (Rogers et al., 2016), Theorem 6.1. We next show how to provide odometer semantics with RDP composition bounds.

We are now ready to bound the privacy loss of Algorithm 2.

Theorem 2 gives us an RDP based bound on the privacy loss, with a penalty for providing a running upper-bound over the sequence of $\epsilon_{\textrm{RDP}}^{f}$. To fully leverage RDP strong composition, we once again need to track the RDP budget over the Rényi curve. Applying a union bound shows that, for all $\alpha\in\Lambda$:

Concretely, we track the budget spent by $A$ in Algorithm 2 over a set of RDP orders $\alpha\in\Lambda$, denoted $\epsilon_{\textrm{RDP}}(\alpha)$. When mapping this RDP consumption to a DP bound, for each $\alpha$ we find $f$ such that $\epsilon_{\textrm{RDP}}(\alpha)\leq\epsilon_{\textrm{RDP}}^{f}+\frac{\log(|\Lambda|2f^{2}/\delta)}{\alpha-1}$. The minimum value on the right hand side over all orders is our upper-bound on the privacy loss.

There are two main choices to make when instantiating our privacy odometer. The first choice is that of $\epsilon_{\textrm{RDP}}^{f}(\alpha)$. At a given order $\alpha$, the best DP guarantee we can hope for is $\epsilon=\frac{\log(|\Lambda|2/\delta)}{\alpha-1}$. We set $\epsilon_{\textrm{RDP}}^{1}(\alpha)=\frac{\log(|\Lambda|2/\delta)}{\alpha-1}$, ensuring that we can always yield a DP guarantee within a factor two of the lowest possible one when $f=1$. We then preserve this factor two upper-bound by doubling the filter at every $f$, yielding:

Note that the final DP guarantee will not be a step function doubling at every step, as we can choose the best DP guarantee over all $\alpha$s a posteriori.

We then need to choose the set $\Lambda$ of RDP orders to track, with multiple considerations to balance. First, the final DP guarantee implied by Equation 5 has a dependency on $\sqrt{\log(|\Lambda|)}$, so $|\Lambda|$ cannot grow too large. Second, the largest $\alpha$ will constrain the lowest possible DP guarantee possible. (Rogers et al., 2016) suggests that a minimum DP guarantee of $\epsilon_{\textrm{DP}}=\frac{1}{n^{2}}$, where $n$ is the size of the dataset, is always sufficient. This is because the result of a DP interaction has to be almost independent of the data at such an $\epsilon_{\textrm{DP}}$, rendering accounting at lower granularity meaningless. In this case, setting $\big{\{}\Lambda=2^{i},i\in\{1,\log_{2}(n^{2})\}\big{\}}$ yields the same optimal dependency on $n$ as (Rogers et al., 2016), Theorems 6.1 and 6.3. In contrast to the result from (Rogers et al., 2016), the resulting odometer does not degrade for values $\epsilon_{\textrm{DP}}$ larger $1$, making it more practical in situations where large budgets are expected.

In practice, many applications have high DP cost for which the minimal granularity of $\frac{1}{n^{2}}$ is too extreme. Such applications can gain from a higher resolution of RDP orders in the relevant range, yielding a tighter RDP bound. This effect is particularly important due to our exponential discretisation of the RDP budget spent at each order. By choosing the range of RDP orders $\Lambda$, we can thus trade-off the $\log(|\Lambda|)$ cost with the RDP order resolution and the minimum budget granularity. This ease of adaptation, combined with efficient RDP accounting, make our privacy odometer the first to be practical enough to apply to DP deep learning. In the rest of this paper, we use $\alpha=\{1.25,1.5,1.75,\ldots,9.75,10,16,32\}$ for all results. These are typical values used in RDP accounting for deep learning, with a slightly higher resolution than the one given as example in (Mironov, 2017).

Intuitively, adaptivity can be used to save budget during training to perform more steps in total, increasing accuracy under a fixed total privacy loss. By far the most common method to train deep learning models with DP is DP Stochastic Gradient Descent (DP-SGD) (Abadi et al., 2016), which clips the gradients of individual data points to bound their influence on each SGD step, and adds Gaussian noise to the mini-batch’s gradients to ensure that each parameter update is DP. Composition is then used to compute the total privacy loss incurred when training the model.

A natural application of privacy odometers is fine-tuning an existing model with DP, so that the privacy of the fine-tuning dataset in preserved. In this setup, we expect to reach good performance in a small but unknown number of epochs. We would like to stop when the model reaches satisfactory accuracy on the new dataset (or stops improving), without incurring more privacy loss than necessary.