Tight Differential Privacy for Discrete-Valued Mechanisms and for the Subsampled Gaussian Mechanism Using FFT

Introduction

Differential privacy (DP) (Dwork et al.,, 2006) has been established as the standard approach for privacy-preserving machine learning. As DP algorithms have grown increasingly complex, accurately bounding the compound privacy loss has become more challenging as well. The moments accountant (Abadi et al.,, 2016) represented a major breakthrough in the accuracy of bounding the privacy loss in compositions of subsampled Gaussian mechanisms that are commonly used in DP stochastic gradient descent (DP-SGD). This has further been refined through the general development of Rényi differential privacy (RDP) (Mironov,, 2017) as well as tighter RDP bounds for subsampled mechanisms (Balle et al.,, 2018; Wang et al.,, 2019; Zhu and Wang,, 2019; Mironov et al.,, 2019). RDP enables tight analysis for compositions of Gaussian mechanisms, but this may be difficult for other mechanisms. Moreover, conversion of RDP guarantees back to more commonly used $(\varepsilon,\delta)$-guarantees is lossy.

In this work, we focus on an alternative approach based on the privacy loss distribution (PLD) formalism introduced by Sommer et al., (2019). This work directly extends the recent Fourier accountant by Koskela et al., (2020) to discrete mechanisms. We provide a rigorous error analysis which leads to strict $(\varepsilon,\delta)$-bounds. This analysis is further used to obtain strict bounds for the subsampled Gaussian mechanism.

The need to consider discrete mechanisms for rigorous DP on finite-precision computers was first pointed out by Mironov, (2012). Agarwal et al., (2018) implement a communication efficient binomial mechanism cpSGD for neural network training which however cannot handle compositions. Agarwal et al., (2018) and Kairouz et al., (2019) note the need for a privacy accountant for the binomial mechanism as an important open problem, which we solve in this paper for the case where gradients are replaced with a sign approximation.

The outline of the paper is as follows. In Sections 2 and 3 we give the basic definitions and describe the PLD formalism used for our accountant. In Section 4 we describe the algorithm based on the fast Fourier transform (FFT) and in Section 5 we provide an error analysis. Section 6 concludes with experiments illustrating the efficiency and accuracy of the method.

Implementation of the methods is available in Githubhttps://github.com/DPBayes/PLD-Accountant/.

We extend the work by Koskela et al., (2020) which considered an FFT based method for approximating the tight $(\varepsilon,\delta)$-DP guarantees of the subsampled Gaussian mechanism, however without strict lower and upper bounds. The main contributions of this work are:

A framework for computing tight $(\varepsilon,\delta)$-DP guarantees of discrete-valued mechanisms.

An error analysis of the proposed method using moment bounds of the mechanism at hand, which leads to strict lower and $(\varepsilon,\delta)$-upper bounds.

Accurate lower and upper bounds for $(\varepsilon,\delta)$-DP of the subsampled Gaussian mechanism.

Differential Privacy

We first recall some basic definitions of DP (Dwork et al.,, 2006). We use the following notation. An input data set containing $N$ data points is denoted as $X=(x_{1},\ldots,x_{N})\in\mathcal{X}^{N}$, where $x_{i}\in\mathcal{X}$, $1\leq i\leq N$.

We say two data sets $X$ and $Y$ are neighbours in remove/add relation if we get one by removing/adding an element from/to the other and denote this with $\sim_{R}$. We say $X$ and $Y$ are neighbours in substitute relation if we get one by substituting one element in the other. We denote this with $\sim_{S}$.

Let $\varepsilon>0$ and $\delta\in$. Let $\sim$ define a neighbouring relation. Mechanism $\mathcal{M}\,:\,\mathcal{X}^{N}\rightarrow\mathcal{R}$ is $(\varepsilon,\delta,\sim)$-DP if for every $X\sim Y$and every measurable set $E\subset\mathcal{R}$ we have that

When the relation is clear from context or irrelevant, we will abbreviate it as $(\varepsilon,\delta)$-DP. We call $\mathcal{M}$ tightly $(\varepsilon,\delta,\sim)$-DP, if there does not exist $\delta^{\prime}<\delta$ such that $\mathcal{M}$ is $(\varepsilon,\delta^{\prime},\sim)$-DP.

Privacy Loss Distribution

We first introduce the basic tool for obtaining tight privacy bounds: the privacy loss distribution (PLD). The results in Subsection 3.1 are reformulations of the results given by Meiser and Mohammadi, (2018) and Sommer et al., (2019). Proofs of the results of this section are given in the supplementary material.

We consider discrete-valued one-dimensional mechanisms $\mathcal{M}$ which can be seen as mappings from $\mathcal{X}^{N}$ to the set of discrete-valued random variables. The generalised probability density functions of $\mathcal{M}(X)$ and $\mathcal{M}(Y)$, denoted $f_{X}(t)$ and $f_{Y}(t)$, respectively, are given by

If $g$ is a function such that $g(X)$ determines a random variable, then

More generally, we define integrals over generalised probability density functions as in (3.2). We prefer using the integral notation as it simplifies the analysis.

We define the privacy loss distribution as follows.

where $s_{i}=\log\left(\tfrac{a_{X,i}}{a_{Y,j}}\right)$.

Evaluating $(\varepsilon,\delta)$-bounds using the PLD formalism is essentially based on a result (Supplements) which states that the mechanism $\mathcal{M}$ is tightly $(\varepsilon,\delta)$-DP with

This relation holds for both continuous and discrete output mechanisms, and a more general version of this result using so called $f$-divergences is given by Barthe and Olmedo, (2013). In case $f_{X}$ and $f_{Y}$ are generalised probability density functions of the form (3.1), i.e.,

For the discrete-valued mechanisms, the relation (3.4) was originally given by Sommer et al., (2019, Lemmas 5 and 10). Assuming the PLD distribution is of the form (3.3), the relation (3.4) directly gives the following representation for $\delta(\varepsilon)$.

$\mathcal{M}$ is tightly $(\varepsilon,\delta)$-DP for

and similarly for $\delta_{Y/X}(\varepsilon)$.

We remark that finding the outputs $\mathcal{M}(X)$ and $\mathcal{M}(Y)$ that give the maximum $\delta(\varepsilon)$ is application specific and has to be carried out individually for each case, similarly as, e.g., in the case of RDP (Mironov,, 2017).

2 Example: The Randomised Response

To illustrate the formalism described above, consider the randomised response mechanism (Warner,, 1965) which is described as follows. Suppose $F$ is a function $F\,:\,\mathcal{X}\rightarrow\{0,1\}$. Define the randomised mechanism $\mathcal{M}$ for input $X\in\mathcal{X}$ by

where $0<p<1$. The mechanism is $\varepsilon$-DP for $\varepsilon=\log\tfrac{p}{1-p}$ (Dwork and Roth,, 2014). Let $X\sim Y$ and let $F(X)=1$ and $F(Y)=0$. As these are the only possible outputs, $X$ and $Y$ represent the worst case in Lemma 2 and give the tight $\delta(\varepsilon)$. We see that the density functions of $\mathcal{M}(X)$ and $\mathcal{M}(Y)$ are given by

where $c_{p}=\log\tfrac{p}{1-p}.$ Assume $\tfrac{1}{2}<p<1$. Then by Lemma 2 we see that

As $\varepsilon\rightarrow^{-}c_{p}$, we see that $\delta\rightarrow 0$ as expected.

3 Tight (ε,δ)𝜀𝛿(\varepsilon,\delta)-Bounds for Compositions

Let $X$ and $Y$ be random variables described by generalised probability density functions $f_{X}$ and $f_{Y}$ of the form (3.1). We define the convolution $f_{X}*f_{Y}$ as

Notice that $f_{X}*f_{Y}$ describes the probability density of the random variable $X+Y$. The following theorem shows that the tight $(\varepsilon,\delta)$-bounds for compositions of non-adaptive mechanisms are obtained using convolutions of PLDs (see also Sommer et al.,, 2019, Thm. 1).

Consider a $k$-fold non-adaptive composition of a mechanism $\mathcal{M}$. The composition is tightly $(\varepsilon,\delta)$-DP for $\delta(\varepsilon)$ given by

where $\delta_{X/Y}(\infty)$ is as defined in (3.5) and $\omega_{X/Y}*^{k}\omega_{X/Y}$ denotes the $k$-fold convolution of the density function $\omega_{X/Y}$ (an analogous expression holds for $\delta_{Y/X}(\varepsilon)$).

We remark that our approach also allows computing tight privacy bounds for a composite mechanism $\mathcal{M}_{1}\circ\ldots\circ\mathcal{M}_{k}$, where the PLDs of the mechanisms $\mathcal{M}_{i}$ vary (see the supplementary material).

4 Subsampling Amplification

The subsampling amplification can be analysed similarly as by Koskela et al., (2020) in the case of the Gaussian mechanism. For example, considering the $\sim_{R}$-neighbouring relation and using the Poisson subsampling with subsampling ratio $0<q<1$ leads to considering the pair of density functions

where the density function $f_{X}$ corresponds to a subsample including the additional data element. Subsampling without and with replacement using $\sim_{S}$-neighbouring relation can be analysed with mixture distributions analogously (Koskela et al.,, 2020).

Fourier Accountant for Discrete-Valued Mechanisms

We next describe the numerical method for computing tight DP guarantees for discrete one-dimensional distributions using the PLD formalism. We will apply the fast Fourier transform to numerically evaluate the PLD convolutions of Theorem 3.

The discrete Fourier transform $\mathcal{F}$ and its inverse $\mathcal{F}^{-1}$ are defined as (Stoer and Bulirsch,, 2013)

For our purposes FFT will be useful as it enables evaluating the discrete convolutions efficiently. The so-called convolution theorem (Stockham Jr,, 1966) states that for periodic discrete convolutions it holds that

where $\odot$ denotes the elementwise product and the summation indices are modulo $n$. Using (4.1), repeated convolutions are evaluated efficiently.

2 Grid Approximation

In order to harness the FFT, we place the PLD on a grid

Suppose the distribution $\omega$ of the PLD is of the form

where $a_{i}\geq 0$ and $-L\leq s_{i}\leq L-\Delta x$, $0\leq i\leq n-1$. We define the grid approximations

i.e., $s_{i}^{L}$ and $s_{i}^{R}$ refer to the closest left and right grid approximation points to $s_{i}$. We note that as $s_{i}$’s correspond to the log ratios of probabilities of individual events, often a moderate $L$ is sufficient for the condition $-L\leq s_{i}\leq L-\Delta x$ to hold for all $i$. In the Supplements we provide analysis also for the case where this assumption does not hold. From (B.3) we have:

Lemma 1 directly generalises to convolutions. The following bounds for the moment generating functions will be used in the error analysis.

3 Truncation of Convolutions and Periodisation

The FFT assumes that inputs are periodic over a finite range. We describe truncation of convolutions and periodisation of distribution functions to meet this assumption. Suppose $\omega$ is defined such that

where $a_{i}\geq 0$ and $s_{i}=i\Delta x$. The convolutions can then be written as

Let $L>0$. We truncate these convolutions to the interval $[-L,L]$ such that

We define $\widetilde{\omega}$ to be a $2L$-periodic extension of $\omega$, i.e., $\widetilde{\omega}$ is of the form

In case the distribution $\omega$ is defined on an equidistant grid, FFT can be used to evaluate $\widetilde{\omega}\circledast\widetilde{\omega}$ as follows:

Let $\omega$ be of the form (B.7), such that $n$ is even, $L>0$, $\Delta x=2L/n$ and $s_{i}=-L+i\Delta x$, $0\leq i\leq n-1$. Define

and ⊙k denotes the elementwise power of vectors.

4 Approximation of the δ​(ε)𝛿𝜀\delta(\varepsilon)-Integral

Finally, using the truncated and periodised convolutions we approximate the integral formula in Lemma 2 for the tight $\delta$-value as

To evaluate $\varepsilon$ as a function of $\delta$, Newton’s method can be used (Koskela et al.,, 2020). Suppose $\omega$ is continuous and $\delta(\varepsilon)$ given by the integral (4.5). Then, $\delta^{\prime}(\varepsilon)=-\int_{\varepsilon}^{\infty}{\rm e}\hskip 1.0pt^{\varepsilon-s}(\omega*^{k}\omega)(s)\,\hskip 1.0pt{\rm d}\hskip 0.5pts$ and Newton’s method applied to the function $\delta(\varepsilon)-\bar{\delta}$ gives the iteration

Error Analysis

We next give a bound for the error induced by Algorithm 1 which is determined by the parameter $L$. The total error consists of (see the supplementary material)

The tail integral $\int_{L}^{\infty}(\omega*^{k}\omega)(s)\,\hskip 1.0pt{\rm d}\hskip 0.5pts$.

The error arising from periodisation of $\omega$ and truncation of the convolutions.

We obtain bounds for these two error sources using the Chernoff bound (Wainwright,, 2019)

which holds for any random variable $X$ and all $\lambda>0$. Suppose $\omega_{X/Y}$ is of the form

where $s_{i}=\log\left(\tfrac{a_{X,i}}{a_{Y,i}}\right)$ and $a_{X,i},a_{Y,i}>0$. Then, the moment generating function of $\omega_{X/Y}$ is given by

Suppose $f_{X}(t)=\sum_{i}a_{X,i}\cdot\delta_{t_{i}}(t)$, $f_{Y}(t)=\sum_{i}a_{Y,i}\cdot\delta_{t_{i}}(t)$ for some coefficients $a_{X,i},a_{Y,i}$, and suppose $\omega_{X/Y}$ is of the form (5.1). Then, we have that

where $D_{\alpha}$ denotes the Rényi divergence of order $\alpha$ (Mironov,, 2017). Further, defining

we see that $\alpha(\lambda)$ is exactly the logarithm of the moment generating function of the privacy loss function as defined, e.g., by Abadi et al., (2016) and Mironov et al., (2019). Thus existing Rényi differential privacy estimates for $\alpha(\lambda)$ could be used to bound the moment generating function of $\omega_{X/Y}$.

2 Tail Bound

Denote $S_{k}:=\sum_{i=1}^{k}\omega_{i}$, where $\omega_{i}$ denotes the PLD random variable of the $i$th mechanism. If $\omega_{i}$’s are independent, we have that

Then, if $\omega_{i}$’s are i.i.d. and distributed as $\omega$, the Chernoff bound shows that for any $\lambda>0$

3 Total Error

We define $\alpha^{+}(\lambda)$ and $\alpha^{-}(\lambda)$ via the moment generating function of the PLD as

Using the analysis given in the supplementary material, we bound the errors arising from the periodisation of the distribution and truncation of the convolutions. As a result, combining with (5.3), we obtain the following bound for the total error incurred by Algorithm 1.

Let $\omega$ be defined on the grid $X_{n}$ as described above, let $\delta(\varepsilon)$ give the tight $(\varepsilon,\delta)$-bound for $\omega$ and let $\widetilde{\delta}(\varepsilon)$ be the result of Algorithm 1. Then, for all $\lambda>0$

We emphasise that the error analysis is given in terms of the parameter $L$. The parameter $n$ can be increased in case the resulting lower and upper bounds for $\delta(\varepsilon)$ are too far from each other.

Examples

Consider the neighbouring relation $\sim_{R}$. Let $u$ be a counting query, i.e.,

and let $\mathcal{Y}=\{0,1\}$. Denote by $m$ the number of elements in $X$ which equal . Let $Y\in\mathcal{X}^{n-1}$, $X\sim Y$, be such that $m-1$ elements equal . Then, the logarithmic ratio at $y=0$ is given by

2 The Binomial Mechanism

As described in the proof of Thm. 1 of Agarwal et al., (2018), for the privacy analysis of the binomial mechanism it is sufficient to consider the neighbouring binomial distributions centred at 0 and $\Delta$. If, for example, $d=1$, it is sufficient to consider the neighbouring binomial distributions

Then, the privacy loss distribution $\omega_{X/Y}$ is of the form

and determining the privacy loss distribution $\omega_{Y/X}$ can be done analogously.

The $(\varepsilon,\delta)$-analysis of the multivariate binomial mechanism can be carried out via one-dimensional distributions using the following observation.

and thus we can use Algorithm 1 to obtain tight $(\varepsilon,\delta)$-bounds for a single call of $\mathcal{M}(X)$.

Figure 4 shows results for an MNIST classification task, where we use a three-layer feedforward network with ReLUs and a hidden layer of width 60. DP-SGD approximation of the gradients is carried out such that for each per example gradient we use a sign approximation: the 200 largest elements (by magnitude) of the input layer are approximated by their sign and the rest are set to zero and similarly the 20 largest of the hidden layer and the largest one of the output layer. Elementwise zero centred binomial noise with parameters $n$ and $p=0.5$ is then added to the averaged gradients. By Thm. 1 and subsampling amplification (Sec. 3.4), the $(\varepsilon,\delta)$-bound can be obtained by running Algorithm 1 for the PLD determined by the distributions

where $f_{X}$ and $f_{Y}$ are the density functions of the random variables

The results of Figure 4 are averages of 5 runs. We set the initial learning rate $\eta=0.02$. We linearly decrease the learning rate $\eta$ after each epoch such that it is zero at the end of the training (when $\left|B\right|=500$ starting from epoch 13, and when $\left|B\right|=300$ starting from epoch 5). We compare this method to cpSGD (Agarwal et al.,, 2018) applied to Infinite MNIST data set which has the same test data set as MNIST. The results for cpSGD are extracted from Agarwal et al., (2018, Fig. 2). For $\varepsilon=2.0$ we extract the result where each element of the gradient requires 8 bits and for $\varepsilon=4.0$ the one requiring 16 bits. We note that when $n=3000$ our method requires 12 bits per element.

3 The Subsampled Gaussian Mechanism

We next show how to compute rigorous DP bounds for the subsampled Gaussian mechanism using the method presented here. We consider the Poisson subsampling and $\sim_{R}$-neighbouring relation. For a subsampling ratio $q$ and noise level $\sigma$, the continuous PLD is given by Koskela et al., (2020)

We find that $\omega$ as defined in (F.1) has one stationary point which we determine numerically. Using this fact, the numerical values of $c^{-}_{i}$ and $c^{+}_{i}$ can be straightforwardly computed.

and $C=\sigma^{2}\log(\frac{1}{2q})-\frac{1}{2}$.

Figure 5 illustrates the convergence of the bound given by Lemma 1 as $n$ grows and $L$ is fixed. For comparison, we also show the numerical values given by Tensorflow moments accountant (Abadi et al.,, 2016).

Conclusions

We have presented a novel approach for computing privacy bounds for discrete-valued mechanisms. The method provides tools for moments-accountant-like techniques for evaluating privacy bounds for discrete output DP-SGD algorithms. More specifically, we have shown how to accurately bound the $\delta(\varepsilon)$-DP for the subsampled binomial mechanism, when the gradients are replaced with a sign approximation. Moreover, as the example of Section 6.3 shows, accurate $(\varepsilon,\delta)$-bounds for continuous mechanisms can also be obtained using the proposed method. Due to the rigorous error analysis the reported $(\varepsilon,\delta)$-bounds are strict lower and upper privacy bounds.

Acknowledgements

This work has been supported by the Academy of Finland [Finnish Center for Artificial Intelligence FCAI and grants 319264, 325572, 325573].

Appendix A Proofs for the Results of Section 3

Throughout this section we denote for neighbouring datasets $X$ and $Y$ the density function of $\mathcal{M}(X)$ with $f_{X}(t)$ and the density function of $\mathcal{M}(Y)$ with $f_{Y}(t)$. The definition of approximate differential privacy is equivalently given as follows.

We call $\mathcal{M}$ tightly $(\varepsilon,\delta)$-DP, if there does not exist $\delta^{\prime}<\delta$ such that $\mathcal{M}$ is $(\varepsilon,\delta^{\prime})$-DP.

The auxiliary lemma 2 is needed for Lemma 3. For discrete valued distributions, it is given in (Meiser and Mohammadi,, 2018, Lemma 1) and another version of this result using so called $f$-divergences is given in Barthe and Olmedo, (2013). We prove it here for for completeness, using our formalism. In the proof, if $f_{X}$ and $f_{Y}$ are discrete valued distributions and if

$\mathcal{M}$ is tightly $(\varepsilon,\delta)$-DP with

We get an analogous bound for $\int_{S}f_{Y}(t)-{\rm e}\hskip 1.0pt^{\varepsilon}f_{X}(t)\,\hskip 1.0pt{\rm d}\hskip 0.5ptt$. Since $\mathcal{M}$ is tightly $(\varepsilon,\delta)$-DP, by Definition 1,

To show that the above inequality is tight, consider the set

for $\delta$ given by (A.1). This shows that $\delta$ given by (A.1) is tight. ∎

Recall from the main text that if $f_{X}$ and $f_{Y}$ are of the form (3.1), then the PLD distribution function is given by

The following lemma gives an integral representation for the tight $\delta(\varepsilon)$-bound involving the distribution function of the PLD. For discrete valued distributions, it is originally given in (Sommer et al.,, 2019, Lemma 5).

Let $\mathcal{M}$ be defined as above. $\mathcal{M}$ is tightly $(\varepsilon,\delta)$-DP for

We directly find from the definition of $f_{X}$ and $f_{Y}$ and from the definition (A.4) that

A.2 Privacy Loss Distribution of Compositions

The following theorem shows that the PLD distribution of discrete non-adaptive compositions is obtain using a discrete convolution. We first recall the definition of convolution of two generalised functions as defined in the main text. Suppose the distributions $f_{X}$ and $f_{Y}$ are of the form

The result of the following theorem is originally given in (Sommer et al.,, 2019, Thm. 1). For completeness we give a proof using our notation with generalised probability density functions.

Let $f_{X}(t)$, $f_{Y}(t)$, $f_{X^{\prime}}(t)$ and $f_{Y^{\prime}}(t)$ denote the density functions of $\mathcal{M}(X)$, $\mathcal{M}(Y)$, $\mathcal{M^{\prime}}(X)$ and $\mathcal{M^{\prime}}(Y)$, respectively. Denote by $\omega_{X/Y}$ the PLD distribution of $\mathcal{M}(X)$ over $\mathcal{M}(Y)$ and by $\omega_{X^{\prime}/Y^{\prime}}$ the PLD distribution of $\mathcal{M^{\prime}}(X)$ over $\mathcal{M^{\prime}}(Y)$. Denote by $\widetilde{\omega}_{X/Y}$ the PLD of the non-adaptive composition $\mathcal{M}\circ\mathcal{M^{\prime}}=(\mathcal{M},\mathcal{M^{\prime}})$. The density function of $\widetilde{\omega}_{X/Y}$ is given by

By definition of the privacy loss distribution,

Due to the independence of $\mathcal{M}$ and $\mathcal{M^{\prime}}$,

We see from (A.7) that $\widetilde{\omega}_{X/Y}=\omega_{X/Y}*\omega_{X^{\prime}/Y^{\prime}}$ with convolution defined in (A.5). The expression for $\widetilde{\delta}_{X/Y}(\infty)$ follows directly from its definition and from the independence of the mechanisms (A.6). ∎

Theorem 4 directly gives the following representation for tight $\delta(\varepsilon)$ of compositions.

Consider $k$ consecutive applications of a mechanism $\mathcal{M}$. Let $\varepsilon>0$. The composition is tightly $(\varepsilon,\delta)$-DP for $\delta$ given by

where $(\omega_{X/Y}*^{k}\omega_{X/Y})(s)$ denotes the density function obtained by convolving $\omega_{X/Y}$ by itself $k$ times (an analogous formula holds for $\delta_{Y/X}(\varepsilon)$).

Appendix B Proofs for the Results of Section 4

Suppose the distribution $\omega$ of the PLD is of the form

where $a_{i}\geq 0$ and $-L\leq s_{i}\leq L-\Delta x$, $0\leq i\leq n-1$. We define the grid approximations

The claim follows from the definition (B.3) and from the fact that $(1-{\rm e}\hskip 1.0pt^{\varepsilon-s})$ is a monotonously increasing function of $s$. ∎

Lemma 1 directly generalises to convolutions. Namely, if

The following bounds for the moment generating functions will be used in the error analysis.

Using the Lipschitz continuity of the exponential function, we see that

B.2 FFT Evaluation for Truncated Convolutions of Periodic Distributions

We next prove the lemma showing that the truncated convolutions of periodic distributions can be evaluated using FFT. Suppose $\omega$ is defined on $X_{n}$ such that

where $a_{i}\geq 0$ and $s_{i}=i\Delta x$. The convolutions can then be written as

We define $\widetilde{\omega}$ to be a $2L$-periodic extension of $\omega$ such that

In case the distribution $\omega$ is defined on an equidistant grid, FFT can be used to evaluate the approximation $\widetilde{\omega}\circledast\widetilde{\omega}$:

Let $\omega$ be of the form (B.7), such that $n$ is even and $s_{i}=-L+i\Delta x$, $0\leq i\leq n-1$. Define

and ⊙k denotes the elementwise power of vectors.

Assume $n$ is even and $s_{i}=-L+i\Delta x$, $0\leq i\leq n-1$. From the the truncation and periodisation it follows that $\widetilde{\omega}\circledast\widetilde{\omega}$ is of the form

Denoting $\boldsymbol{\widetilde{a}}=D\boldsymbol{a}$, we see that the coefficients $b_{i}$ in (B.8) are given by the expression

to which we can apply DFT and the convolution theorem Stockham Jr, (1966). I.e., when $0\leq i\leq n-1$,

where $\odot$ denotes the elementwise product of vectors. From (B.9) we find that

By induction this generalises to $k$-fold compositions and we arrive at the claim. ∎

Appendix C Proof of Theorem 10

We next prove step by step the main theorem, i.e., Theorem 10 of the main text. We start by splitting the error induced by Algorithm 1 into three terms.

Let $\omega$ be a generalised distribution and denote by $\widetilde{\delta}(\varepsilon)$ the result of Algorithm 1. Total error of the approximation can be split as follows:

where, for a generalised density function of the form $\sum\nolimits_{i}a_{i}\cdot\delta_{s_{i}}(s)$, the absolute value denotes

By adding and subtracting terms and using the triangle inequality, we get

Since $0\leq(1-{\rm e}\hskip 1.0pt^{\varepsilon-s})<1$ for all $s\geq\varepsilon$, we have for the first term on the right hand side of (C.1):

Similarly, adding and subtracting $\int\limits_{\varepsilon}^{L}(1-{\rm e}\hskip 1.0pt^{\varepsilon-s})(\omega\circledast^{k}\omega)(s)\,\hskip 1.0pt{\rm d}\hskip 0.5pts$ the second term on the right hand side of (C.1), we find that

We next consider separately each of the three terms stated in Theorem 1. Each of them are bounded using the Chernoff bound Wainwright, (2019)

which holds for any random variable $X$ and for all $\lambda>0$. If $\omega$ is of the form

C.2 Error Arising from the Periodisation

We define $\alpha^{+}(\lambda)$ and $\alpha^{-}(\lambda)$ via the moment generating function of the PLD as

Using the Chernoff bound, the required error bounds can be obtained using $\alpha^{+}(\lambda)$ and $\alpha^{-}(\lambda)$.

Let $\omega$ be defined as above and suppose $s_{i}\in[-L,L]$ for all $0\leq i\leq n-1$. Then,

Let $\omega$ and its $2L$-periodic continuation $\widetilde{\omega}(s)$ be of the form

for some $a_{i},\widetilde{a}_{i}\geq 0$, $s_{i}=i\Delta x$. By definition of the truncated convolution $\circledast$ (see the main text),

since $\widetilde{a}_{i}=a_{i}$ for all $i$ such that $-L\leq s_{i}<L$. Furthermore,

Using the bounds (C.8), (C.9) and the Chernoff bound (C.4), we find that for all $\lambda>0$

C.3 Error Arising from the Truncation of the Convolution Integrals

Next, assume that the generalised distribution $\omega$ of the PLD is of the form

where $a_{i}\geq 0$ and $s_{i}=i\Delta x$.

The following lemma gives a bound for the truncation error $\int\limits_{\varepsilon}^{L}\left|(\omega*^{k}\omega-\omega\circledast^{k}\omega)(s)\right|\,\hskip 1.0pt{\rm d}\hskip 0.5pts$ in terms of the moment generating function of $\omega$. Notice that this result applies also for the case where the support of the PLD distribution are outside of the interval $[-L,L]$.

Let $\omega$ be defined as above. For all $\lambda>0$,

By adding and subtracting $(\omega*^{k}\omega)\circledast\omega$ , we may write

for some $\widetilde{c}_{i}\geq 0$, $s_{i}=i\Delta x$. Then

Using (C.10), (C.11) and (C.12), we see that for all $\lambda>0$,

Using (C.13) recursively, we see that for all $\lambda>0$,

C.4 Proof of Theorem 10 (Total Error)

Proof of Theorem 10. Let $\alpha^{+}(\lambda)$ and $\alpha^{-}(\lambda)$ be defined as in (C.5). Combining the bound (C.4) and the bounds given by Lemmas 2 and 3, we find that

Appendix D Theorem 11: Tight Bound for Multidimensional Mechanisms via One Dimensional Distributions

The following results shows that the tight $(\varepsilon,\delta)$-bound for a multidimensional mechanism $\mathcal{M}$ can be obtained by analysis of one dimensional distributions, in case the neighbouring datasets $X$ and $Y$ leading to the maximal $\delta(\varepsilon)$ are known.

The claim can be shown simply by observing that the privacy loss distribution generated by $\mathcal{M}(X)$ and $\mathcal{M}(Y)$ and the privacy loss distribution generated by compositions $(\Delta_{1}+Z_{1},\ldots,\Delta_{d}+Z_{d})$ and $(Z_{1},\ldots,Z_{d})$ are the same. ∎

Appendix E Experiments of Section 6.2

We next show how to use the Fourier accountant for obtaining the $(\varepsilon,\delta)$-bound of Figure 4. Essentially, we show how to obtain the PLD for a subsampled multivariate mechanism, where the neighbouring distributions are known and fixed (i.e., $\Delta=f(X)-f(Y)$ is fixed and $f(X)$ is sampled with probability $q$ and $f(Y)$ with probability $1-q$).

Now denote the density functions for one-dimensional mechanisms $\mathcal{M}(X)$ and $\mathcal{M}(Y)$ by

the density functions are given by the convolutions

By definition, the PLD generated by the distributions

for all $i$. Thus, if we have the distributions

we can form the PLD $\widetilde{\omega}$ by the change of variable

and summing the coefficients as in (E.1). On the other hand, we can obtain $\omega_{1}$ and $\omega_{2}$ by using the Fourier accountant to the $d$-fold convolutions of the distributions

Also, the $\delta(\infty)$-probabilities can be evaluated straightforwardly for $q\cdot\widetilde{f}_{X}+(1-q)\cdot\widetilde{f}_{Y}$ and $\widetilde{f}_{Y}$.

Appendix F Section 6.3: The Subsampled Gaussian Mechanism

In this Section we give an error analysis for the approximations given in Section 6.3. Recall first the form of the PLD for the subsampled Gaussian mechanism. For a subsampling ratio $0<q<1$ and noise level $\sigma>0$, the continuous PLD distribution is given by

where $c^{-}_{i}$ and $c^{+}_{i}$ are as defined in (F.3). We find that $\omega$ as defined in (F.1) has one stationary point which we determine numerically. Using this, the numerical values of $c^{-}_{i}$ and $c^{+}_{i}$ are obtained.

Lemma 1 directly generalises to convolutions:

goes analogously. Inductively, bounding as in (F.5), we also see that

For all $s\geq 1$ and $0<q\leq\tfrac{1}{2}$:

where $C=\sigma^{2}\log(\frac{1}{2q})-\frac{1}{2}$.

where $\widetilde{C}=\sigma^{2}\log(\tfrac{1}{2q})+\tfrac{1}{2}$. We see that when $0<q\leq\tfrac{1}{2}$, we have $g(s)\geq\tfrac{1}{2}$. From (F.2) we see that

Furthermore, when $s\geq 1$, from (F.6) it follows that

where $C=\sigma^{2}\log(\tfrac{1}{2q})-\tfrac{1}{2}$. ∎

where $C=\sigma^{2}\log(\frac{1}{2q})-\frac{1}{2}$, $s_{i}=i\Delta x$. Thus

Assuming $\sigma\geq 1$ and $\lambda\leq L$, $\Delta x\leq c\cdot L$, we further see that

Appendix G Description of Learning Rate Cooling Used for Experiments of Figure 2b.

When running the feedforward network experiment of Figure 2b, we set the initial learning rate $\eta=0.02$. When $n=2400$ and $\left|B\right|=500$, starting from epoch 13, and when $n=3000$ and $\left|B\right|=300$, starting from epoch 5, the learning rate $\eta$ is linearly decreased after each epoch such that it is zero at the end of the training.