Differentially Private Stochastic Expectation Propagation
Authors: Margarita Vinaroz
Mijung Park
Venue: Accepted by TMLR ()

Abstract: We are interested in privatizing an approximate posterior inference algorithm, called Expectation
Propagation (EP). EP approximates the posterior distribution by iteratively refining
approximations to the local likelihood terms. By doing so, EP typically provides better posterior
uncertainties than variational inference (VI) which globally approximates the likelihood
term. However, EP needs a large memory to maintain all local approximations associated
with each datapoint in the training data. To overcome this challenge, stochastic expectation
propagation (SEP) considers a single unique local factor that captures the average effect of
each likelihood term to the posterior and refines it in a way analogous to EP. In terms of
privatization, SEP is more tractable than EP. It is because at each factor’s refining step we
fix the remaining factors, where these factors are independent of other datapoints, which is
different from EP. This independence makes the sensitivity analysis straightforward. We
provide a theoretical analysis of the privacy-accuracy trade-off in the posterior distributions
under our method, which we call differentially private stochastic expectation propagation
(DP-SEP). Furthermore, we test the DP-SEP algorithm on both synthetic and real-world
datasets and evaluate the quality of posterior estimates at different levels of guaranteed
privacy.

Published in Transactions on Machine Learning Research (10/2022)
Differentially Private Stochastic Expectation Propagation
Margarita Vinaroz
University of Tübingen
International Max Planck Research School for Intelligent Systems (IMPRS-IS)
Mi Jung Park
mijungpBcs. ubc.ca
University of British Columbia CIFAR AT Chair at AMII
Reviewed on OpenReview:
Abstract
We are interested in privatizing an approximate posterior inference algorithm, called Expec- tation Propagation (EP). EP approximates the posterior distribution by itcratively refining approximations to the local likelihood terms. By doing so, EP typically provides better poste- rior uncertainties than variational inference (VI) which globally approximates the likelihood term. However, EP needs large memory to maintain all local approximations associated with cach datapoint in the training data. To overcome this challenge, stochastic expectation propagalion (SEP) considers single unique local factor that caplures the average effect of each likelihood term to the posterior and refines it in way analogous to EP. In terms of privatization, SEP is more tractable than EP. It is because at each factor's refining step we fix the remaining factors, where these factors are independent of other datapoints, which is different from EP.. This independence makes the sensitivity analysis straightforward. We provide theoretical analysis of the privacy-accuracy trade-off in the posterior distributions under our method, which we call differentially private stochastic expectation propagation (DP-SEP). Furthermore, we test the DP-SEP algorithm on both synthetic and real-world datasets and evaluate the quality of posterior estimates at different levels of guaranteed privacy.
1 Introduction
Bayesian learning provides level of uncertainty about model through the posterior distribution over the parameters. The posterior distribution then provides level of uncertainty about the model's prediction through the posterior ivedictive distribution. Variational inference (VT) [Beal 2003 Jordan et al. 1999 is a popular Bayesian inference method that refines global approximation of the posterior and scales well to applications with large datasets. However, VI often underestimates the variance of the posterior and performs
poorly for models with non-smooth likelihoods (Cunningham et al. 2013 Turner & Sahani 2011
In contrast, expectation propagation (EP) is known to provide better postcrior uncortaintics than VI (Minka 2001; Opper & Winther (205).. EP constructs the approximate posterior by iterating local computations that refine approximating factors, where each factor captures each likelihood's contribution to the posterior. With large datascts, however, using EP imposes challenges maintaining each of the local approximates in memory is costly. Stochastic expectation propagation (SEP) (Li et al.) 2015) overcomes this challenge by iteratively refining a single approximating factor that is repeated as many times as the number of datapoints that are the dataset.
The idea behind SEP is that the unique factor captures the average effect of the likelihoods the posterior. Employing single approximating factor makes the algorithm suitable for large-scale datasets it needs

---

Published in Transactions on Machine Learning Research (10/2022)
to keep the global approximating factor only, opposed to EP that needs to keep all the approximating factors in memory. While SEP is not exactly EP but approximates EP, SEP is known to provide the posterior uncertainties very close to the ones in EP.
Despite EP and SEP's advantage over VI, the standard form of the algorithms unfortunately cannot guarantee privacy for each individual in the dataset. In particular, EP and SEP enables approximate Bayesian inference under a broad class of models such as generalized linear models and mixed models. However, when these models are trained with privacy-sensitive data, the approximate posteriors potentially leak information the training examples.
Differential privacy (DP) Dwork & Roth 2014) has become the gold standard for providing privacy and is widely used in diverse applications from medicine to social science. To apply DP to EP, difficulty arises in sensitivity analysis: at each step of the algorithm, the approximating factor that is being refined depends on the rest of the other factors where these other factors are functions of training data. Hence, the scnsitivity of the approximate posterior depends not only the particular factor that is being refined but also the rest of the factors that contribute to the posterior. Due to this fact, it is challenging to obtain the nice property of sensitivity scaling with /, where N is the number of datapoints in the training data.
On the other hand, in every SEP step it considers single approximating factor at time while all the other factors are fixed to the same values either at the initial step, or at the previous training step. Hence, the sensitivity analysis of the approximate posterior becomes straightforward. In particular, the natural parameters of the approximate posterior under SEP is a linear sum of those corresponding the likelihood factors and prior. Considering that each of the approximating factors and prior parameters are bounded by a constant C (otherwisc of the approximate posterior becomes proportional to C
clip them to have norm C), then the sensitivity of the natural parameters
N (see Sec.
Taken together, we summarize our contribution of this paper.
To the best of our knowledge, provide the first differentialll-priiacce version of the stochastic expectation propagation algorithm, called DP-SEP, which is scalable for large datasets and also privacy-preserving.
We provide theoretical analysis of the privacy-accuracy trade-off by computing the worst-case KL divergence between the private and non-private posterior distributions.
We also provide experimental results applied to synthetic dataset for a mixture-of Gaussian model and several real-world datasets for Bayesian neural network model.
what follows, we provide background information on expectation propagation, stochastic expectation propagation and differential privacy Sec. We then describe our DP-SEP algorithm in Sec. 3 In Sec. analyze the effect of noise added to the natural parameters on the accuracy of the differentially private posterior distributions. We describe related work in Sec. 5 Finally, demonstrate the performance of DP-SEP in relation to other posterior inference methods such VI, EP, and SEP in Sec. G
2
Background
In the following, we describe EP and SEP algorithms, differential privacy and its properties that we will use to develope our algorithm in Sec. 3
2.1 Expectation propagation (EP)
We consider a datasct D {x, I
x=1 containing N i.i.d samples. Given the datasct, we pick a model parameterized by 0. We denote the likelihood of datapoint I, given the model by p(z,,0) and the prior distribution over the parameters by (0) The true (intractable) posterior distribution is proportional to the
2

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm 1 EP
Choose factor fu refine
Compute the cavity distribution
(0) x q(0)/ (0)
3: Compute the tilted distribution
Po (0) & ,, (-)
4: Moment matching
Jn (0) < proj Pn (0))
Inclusion
( (0)
A Algorithm SEP
1: Choose a datapoint In ~ D
2: Compute the cavity distribution
(0) x (0)
Compute the tilted distribution
Pro (0) pl O (0)
Moment matching
(0) pr 00)//-1(0)
5: Implicit update
f(0)= + f00 (0)}
6: Inclusion
( < (-)
product of the prior and the likelihood, given by:
N D x (0 Il p(x,, 10).
(1)
EP is an iterative algorithm that produces a simpler and tractable approximate posterior distribution, g(0), by refining the approximating factors fa (0) associated with each datapoint, given by:
p(0 = (()) (o II (0).
EP refines these factors iteralively, as shown in Algorithu Firstly, we initialize the approximating factors and form the cavity distribution (f) by taking the n-th approximating factor out from the approximated posterior (i.e (0) x ((0)/fx(()) Secondly, we compute the tilted distribution, (n),,, , by including the corresponding likelihood term to the cavity distribution: (0) x g=n(0)p(z,,0)) Thirdly, we update the approximating factor by minimizing the Kullback-Teibles (KT.) divergence between the tilted distribution and (0),,.()) capture the likelihood term's contribution to the posterior. When the approximate dist.rbuttion belongs to the exponential family, the KL mininization reduces to moment matching (Amari & Nagaoka, 2000). denoted by: fx (0) < (r0]/(())))) Finally, add the refined factor (() to the approximate posterior in the inclusion step. We repeat this process until some convergence criterion is satisfied.
2.2 Stochastic EP (SEP)
A major difference between EP and SEP is that SEP constructs an approximate posterior, q(0), by iteratively refining N copics of a unique factor, f()), such that IIN, p(x,,00) x f(0) The intuition behind SEP is that the approximating factor captures the average effect of the likelihood on the posterior distribution, since the updates performed analogously to E.P.
3

---

Published in Transactions on Machine Learning Research (10/2022)
Similar to EP, as shown in Algorithm 2 start by initializing the approximating factor and computing the cavity distributiin by removing the factor from the approximate posterior: q-1(0) x ((0)/((0). Note that unlike EP, where the cavity distribution involve a datapoint's index n, this cavity distribution is independent of a data index, as we obtain it by removing one datapoint's average worth determined by f(0) from the posterior distribution.
We then calculate the tilted distribution in the same way as in EP by (0) x (0)(0)((2 In the third step, we minimize the KL-divergence between the tilted distribution and (.) to find an intermediate factor, (0). In the last step, we update the factor with damping rate r/N: f(0) f(0)'~N/N (O) A common choice for the damping factor is 1/N because it can be seen as minimizing the KL divergence between the tilted distribution and (0)))
In the last step of the algorithm, we include the refined factor in the approximate posterior. We repeat these steps until convergence. The SEP algorithm reduces the storage requirement compared to EP as only maintains the global approximation, where the following holds:
f(0) x (q(0)/po(0))* 9-1 a(0)' (0)
(3)
(4)
2.3 Differential privacy
Given privacy parameters 0, 0 randomized algorithm, M, is said to be (c,5)-DP (Dwork & Roth 2014) if for all possible sets of mechanism's 's outputs S and for all neighboring datasets D, D differing in an only single entry (d(D,D) s 1), the following inequality holds:
Pr[M(D) e Si PP(MM(D +
The definition states that the amount of information revealed by randomized algorithm about any individual's participation is limited. And the amount is determined by and 6.
A common way of constructing a differentially private algorithm is to add a calibrated amount of noise to an output of the algorithm. Suppose we want to privatize a function h 'D - Rd, which takes a dataset as an input and output a d-dimensional real-valued vector. The Gaussian mechanism adds noise such that the output of the mechanism is given by ((D) htD) + n, where n n~ (0, o² IT).). Here, the noise scale depends on the global sensitivity (Dwork et al. 2006a of the function h denoted by An, which is defined the L2-norm [IA(D) h(D') ||2 where D, D' are neighboring datasets differing in only single entry. The Gaussian mechanism is (c, DD and is function that depends on e, 5. For a single application of the mechanism, a 2 /2 log(1 (log(112///8) /5/ for e 2 1. In our algorithm, we will use the Gaussian mechanism to privatize the approximate posterior distribution.
There are two important, properties differential privacy. The first one is post-processing invariance (workk et al. 2006b), which states that the composition of any data-independent mapping with an 5)P algorithm is also (e, 8)- What this means in our context is that no analysis on our privatized approximate posterior can yield more information about the training data than what our choice of and 8 allows.
The second property is composability Dwork et al. (2006a), which states that the strength of privacy guarantee degrades in a measurable way with repeated use of the training data. In this work, we use the subsampled RDP composition (Wang et al.) 2019) as a composition technique, as provides tight bounds on the cumulative privacy loss when we subsample datapoints from the training data. For this, we use the auto-dp package (Lttps://github com httyyyuiiigggauuooou to compute the privacy parameter o given our choice of e, values and the number of times access data while running our algorithm.
4

---

Published in Transactions on Machine Learning Research (10/2022)
Algorithm DP-SEP
Require: Datasct Initial natural parameters for approximating factor ||0y|12 S and those for the prior 1uul2 S C, damping value y, and the privacy parameter o.
Ensure: 8eP natural parameters of the approximate posterior
for t = = do
for n E (1...., N). uniformly random without replacement do
3:
Choose a datapoint En ~
4: Compute cavity distribution: (-1 x (0)/{(())
5:
Compute tilted distribution: (0) x q- q- (0)p(a.)))))))))
Moment matching: (0) < (
Clip the norm of the natural parameters: 10 SC
8:
Update the approximate posterior: neew (0) + (0) f(0)*
Add noise to natural parameters: Onew nnew + n where NV (0000022)) 02 new 1)
Post-process natural parameters corresponding to covariance to ensure positive definiteness 11: Update the approximating factor: f()) x (qnew ((eew(nnw))/l (fnew)/po(0)) +
10:
12: Clip the norm of the natural parameters: |0y|12 S C
13: end for
14:
end for
3 Our algorithm: DP-SEP
Mean parameter of Gaussian distribution Covariance matrix of a Gaussian distribution
Σ
1
Natural parameter for the mean
A
Natural parameter for the covariance matrix
Noise variance of the Gaussian distribution
o
Noise variance of the Gaussian distribution for n
0
Noise variance of the Gaussian distribution for A Expectation with respect to the variable E
Eg
A
Inverse of matrix A
AT
Transposc of matrix A
Tr(A]
Trace of matrix A
A
Determinant of matrix A
(A)
i-th cigenvalue of a matrix A
Amii (A)
Minimum eigenvalue of matrix A
Amax (A)
Maximum eigenvalue of matrix A
In this section, we introduce our proposed algorithm, which we call differentially private stochastic expectation propagation (DP-SEP). The algorithm outputs differentially private approximate posterior distributions by noising up the natural parameters.
3.1 Outline of DP-SEP
Initialization: As shown in Algorithm we first initialize the approximating factor, f(0), such that the norm of its natural parameters 0 and prior natural parameters 6, are bounded by constant C. (i.e. |00ll2 C, ||0b]]2 < C). The norm clipping applied to each natural parameter becomes instrumental in computing the sensitivity of the natural paramcters for the global approximate posterior (()), which is required in the later step in the algorithm. By construction, each local factor fa and the approximating factor f have its own natural parameters 0,, and 0,, respectively. When the exponential distributions have bounded domain, the natural parameters are also norm bounded. However, when they are not norm bounded, e.g., the Gaussian distribution has an unbounded domain, we choose clip the norm of A,, and 0 so that the natural parameters for the global approximate posterior have limited sensitivity.
5

---

Published in Transactions on Machine Learning Research (10/2022)
Step 1 6: The same as in the SEP algorithm in Algorithm 2 each run of the DP-SEP algorithm, we first subsample one datapoint uniformly without replacement from the dataset, D, then compute the cavity distribution (0), the tilted distribution (0) and the intermediate factor fa (0) for Dn, followed by the moment matching step.
Step 7 Once (n) is computed, we need ensure that its natural parameters, f,,, are also norm bounded by C (i.e |00,1l2 I C). Then, the algorithm updates the natural parameters of the approximate posterior by making partial update of the approximating factor and the cavity distribution according to the pre-selected damping value: gnew (0) < (0) f(0)* (0)
As the approximating distribution is in the exponential family, we can express the approximate posterior natural parameters, 0, as linear combination of the natural parameters of the approximating factor and the prior (i.e. , + 0o). From this together with the damping value, we arrive at the following definition:
Onew N No, (N
Y N 00.
Step 11: In the next step, we privatize the natural parameters Onew by adding the Gaussian noise with the scnsitivity Aenew = 2yC (See Prop. [1. After adding Gaussian noise, the perturbed covariance natural parameter might not be posilive definite. In such case, post-processing step, we project the negative cigenvalues to small positive values to maintain positive definiteness of the natural parameters corresponding to the covariance matrix, following (Park et al. 2017 This step does not change the level of privacy guarantee of the natural parameters after the projection, as differential privacy is post- pest-processing invariant. Finally, the last step, we update the unique approximating factor, f(),, by eq. 3 using the new privatized approximate posterior denoted by (Onew). The updated natural parameters of the approximating factor can be then easily computed by the following expression: 0 (Onew 0o)/N. Once we update the natural parameters for the approximating factor, ensure that its norm is also bounded by
N
C.
3.2 Privacy analysis
We use the subsampled Gaussian mechanism together with the analytic moments accountant for computing the total privacy loss incurred in our algorithm. Hence, we input a chosen privacy level e, 6, the number of repetitions T, the number of datapoints N and the clipping norm C to the auto-dp package by (Wang et al. 2019), which returns the corresponding privacy parameter a.
The following propositions state that (1) the sensitivity of the natural parameters is algorithm is differentially private.
2xC and (2) the resulting N
Proposition 1. The sensitivity of the natural parameters, Onew, in Algorithm is given by Aenew 2xC
Proof- Consider two neighboring databases, D,D' D' differing by entry n, and same initial values for 0,, On:
Dnnw = max Inew &eewll2 D.D
max
lI O, + (N - -3) -, 0, 0n)
(2.0% (N 0,),, 0, + 0o) 11.. by eq. 5
= N max 0,,, - -8/, 12. D.D
S
2% max 10,, l12 due to the triangle inequality
N D,D
20y
N due to the norm clipping on natural parameters.
0
Proposition 2. The DP-SEP algorithm produces 5eD approsimate posterior distributions.

---

Published in Transactions on Machine Learning Research (10/2022)
Proof. Due to the Gaussian mechanism, the natural parameters after each perturbation are DP. By composing these with the subsampled RDP composition (Wang et al. 2019), the final natural parameters are (e,6)-DP, where the exact relationship between (e, 6), ""' (how many repetitions SEP runs), N (how many datapoints a dataset has), and a (the privacy parameter) follows the analysis of (Wang et al. 2019).
3.3 A few thoughts on the algorithm
Is this DP-SGD applied to DP-SEP? Clipping then adding Gaussian noise seems to indicate that this algorithm is simply DP-SGD. However, there are two subtle but important differences between DP-SEP and DP-SGD, First, DP-SGD computes the gradients on the datapoints in a batch then clip the gradients. However, DP-SEP computes the global posterior distribution, which is a concatenation of all the factors associated with all the data points in the training data, not just in a selected mini-batch of the data. Hence, the sensitivity is on the order of I/N where N is the number of datapoints in the training data, while the sensitivity of DP-SGD is on the order of 1/B where B is the size of the mini-batch. Hence, DP-SEP can significantly reduce the amount of noise in each privatization step, compared to DP-SGD, as typically N > B.
Second, in DP-SGD, the reason clipping the gradients is because we simply do not know how much one datapoint's 's difference in the neighbouring datasets would change the gradient values (that are computed on a selected mini- batch. On the other hand, in our case we do know the amount of change in the natural parameters of the global approximate posterior, as the natural parameters of the global approximate posterior are the sum of those of each factor associated with the datapoints and that of the prior. However, for the distribut ion with an unbounded domain, the natural parameters also have an unbounded domain. This is the reason we clip the norm of the natural parameters for the approximating factor and the local factor.
Choice of clipping norm. In our algorithm, we treat the clipping norm threshold C' as a hyperparameter, as many other cases of DP algorithms (e.g., (Abadi et al. 2016)). When setting C to a small value, the scnsitivity gets also smaller which is good in terms of the amount of noise to be added. However, the small clipping norm can drastically discard information encoded in the natural parameters after the clipping procedure. Setting C' to large value results in high noise variance. However, most of the information in the natural parameters will be kept after clipping. Hence, finding the right value for the clipping norm is essential to keep the signal-to-noise ratio high. The optimal value for the clipping norm depends on the distribution of the target variables that we apply the clipping procedure. Hence, no one solution fits all.
While privacy analysis for hyperparameter tuning an active rescarch area (Abadi et al., 2016 Jälkö et al., 2017 Andrew et al., 2021 Kurakin et al., 2022), in this paper, we assume selecting the clipping norm does not incur privacy loss, while incorporating this aspect is interesting research question for future work.
Clipping as form of regularizion An interesting finding when applying clipping in SEP is that the clipping procedure to the natural parameters itself improves the performance of SEP, as shown in our experiments Sec. 6 It is widely known that EP frequently encounters numerical instabilities, e.g., due to the accumulation of numerical errors in local updates over the course of training, which hinders the algorithm to converge properly. SEP, on the other hand, seems to be superior to EP in terms of numerical stability, as it updates one factor that represents the average contribution of all factors to the posterior in every training step and thus numerical errors seem to accumulate slower than those in EP. From our experience, using clipping to SEP with well-chosen clipping threshold further improves its stability, resulting in better convergence. We conjecture this is because applying the clipping procedure to the natural parameters helps avoiding any ble jumps in the search space, and thus effectively reduces the search space on which the algorithm focuses.
4 Quantitatively analysis: effect of noise
Here, we would like to analyze the effect of noise added to SEP. In particular, we are interested in analyzing the distance between the posterior distributions, where one is the posterior distribution obtained by SEP (i.c., non-DP) and the other is the posterior distribution obtained by DP-SEP. As distance metric, we use the KL. divergence between them. Thm. 4.7 formally states the effect of noise for privacy on the accuracy of
7

---

Published in Transactions on Machine Learning Research (10/2022)
the posterior. For simplicity, assume the posterior distribution is d-dimensional multivariate Gaussian. We also assume the posterior distributions between SEP and DP-SEP are compared at 7 1, = 1. We denote the posterior distribution of DP-SEP (Algorithm by == (up, Mp) and the posterior distribution of SEP (Algorithm 2 by == (pg. Eg).
Before introducing the theorem, we first define the two quantities we release every DP-SEP step.
Definition 4.1. We express the first natural porameters obtained by DP-SEP as:
Ωp = "/ +
where fl = - Ma is the first natural porometers obtained by SEP and e is üd drawn from (f
Definition 4.2. By following Step 10 in Algorithm 3 we express the second natural porameters obtained by DP-SEP as:
A, +E+A
(6)
where Ag Egg is the second natural porameters by SEP, E is a symmetric matria where the upper triangular entries tid drown from NV,003) and the lower triangular are copied from the upper holf. We construct dingonal matriz A:
(- (-Amin + F) + p)T, when 02 # 0,
1
otherwise
to ensure the resulting Ap to be positive definite by taking the mánimum eigenvalue of Aq + E and adding Note that when there is no noise added to the
small positive constant such that Awin (Aq + E + A) covariance, we sel A = O, as the role of A is to keep the posterior covariance to be posilive definile and there is no need to add this term any longer since Ag is already positive definite. By definition of A, setting A makes p Aminn(A (Ag).
Thcorem 4.1 (Privacy-accurage trado-off given posteriors by Algorithm 2 and Algorithm 3 Following
Def. 4.1 and Def. 4.2, with probability least 1 d exp
M²
for any M 0, the expected KL divergence
2
between SEP and DP-SEP posterior distributions is bounded by:
x Tr(( Pr((-Amat (Am(-)min(Ag) + / 20( (d)()) + ))AT')
Amin (A₂)+ 22 log(d)
h+ H 1
+ of Amaz (Eg)
Ac(Ag)
(8)
hH
Amnn (Ag)+ /2( log(d)
+ H 1
+
02
(.(Ag)
Th A,
T 1-1mm n4
hH
i=1
Amen (A₂) + (B) log(d)
h H1
+ aa (->Xiin(A)) (Ag) (Ag)+ / (2) log(d) + +D)
(r
log
hH
where (A.7 na)i, a = A My: h 1+ 2M (A) and H 2M (Ay)+ (x(Aa)
The matriz variance
).(Ag)
d(d+1)
statislic is denoted by vo v(E) = E1 B&BBB where the norm is spectral norm and E = EE= ar Br. where Thk is a standard normal Gaussian random variable and By is a finite sequence of fized Hermition (symmetric) matrices. \maz denotes the largest eigenvalue of Aq.
See Sec. B in Appendix for detailed proof. The rough proof sketch is as follows. We first consider the closed-form KT. divergence between the private and non-private posterior distributions with respect to the

---

Published in Transactions on Machine Learning Research (10/2022)
truth
EP
SEP
clipped SEP c=1
clipped SEP c=10
clipped SEP c=20
SP-SEP eps=1.0
DP-SEP eps=5.0
SP-SEP eps=50.0
DP-EM 1.0
DP-EM e.s
DP-EM 50.0
Figure 1: Posterior approximation for the mean of the Gaussian components. Black rings indicate 98 % confidence level. The coloured dots indicate the true label (top left) or the inferred cluster assignments (the rest). The top shows EP (middle) and SEP (right). The second row shows the effect of clipping posterior estimate as function of the clipping threshold C. The third row shows the labels for DP-SEP with 8 = 10-5 and at = 1,5, 5, 50. The bottom row shows the the labels for DP-EM at the same levels of privacy. Black rings for DP-EM are not shown as they appear outside the range of the plot.
the
two Gaussian noise distributions. Computing the expectation with respect to NO, is straightforward. However, computing the expectation with respect to (O,0, oz)) is more involved and we need to take into account the minimum and maximum cigenvalues of the second natural parameters (corresponding to the inverse covariance matrix) to find the desired upper bound. To do this, we the concentration bound for Gaussian random matrices.
A few things are worth noting. Recall that each noise variance σ1 = = 2C and 02 o 2C (for damping rate N
N 1) contains the sensitivity of the natural parameters as well as the privacy parameter a which is a function of 5. Also, notice d2 appears in e(E) in the upper bound. This indicates that the divergence between the private posterior and non-private posterior distributions scales with 1/N with fixed 6,
In the limit of infinite amounts of data, limy- T1 = 0 and lim 02 = 0. At this limit, the eigenvalues of the noise matrix also limoz-0 ), 0 for all i. And, for any M 2 0, the probability P[Amax (E) < 2>[E) - 1, as lim e(E) = 0. In this case, the gap ween the private and non-private
M] < 1 - dexp(- M
posterior distributions becomes closed. See Sec. B.1 in Appendix for the detailed discussion of the bound when + cc.
Thm. docs not take explicitly into account the clipped threshold for the natural paramcters. Although, it can be easily taken into account by considering scaling down the q natural parameters by 1/ m1 /I//C)/ inside the p natural parameters definition. These clipping thresholds are not functions of the Gaussian noise addition, and thus, do not affect computing the expectations in the upper bound. For curious readers, we also provide the KL divergence between the posterior distribution by the clipped version of SEP and that by SEP in Sec. in Appendix.
For T> 1 or n > 1, the analysis we made here does not hold, due to the nested structure of SEP updates. However, our analysis can be interpreted as the discrepancy between these two (SEP and DP-SEP) algorithms at single updating step given the same values given from the previous step.
9

---

Published in Transactions on Machine Learning Research (10/2022)
Table 1: Accuracy of the posterior distribution (Mixtureoof-Gausee with Synthetic data)
Method
F-norm on mean
F-norm on covariance
average F-norm
SEP (c=
0.0020
0.0004
0.0012
SEP-clipped C=20
0.0263
0.0004
0.0134
SEP-clipped C=10
1.4950
0.0005
0.7477
SEP-clipped C=1
2.2065
0.0459
1.1262
DP-EM (e 50)
5.3769
1.3189
3.3479
DP-EM (c 5)
10.4548
3.7573
7.1060
DP-EM (c
7.5166
57.8665
32.6916
DP-SEP (6= 50)
2.2411
0.0358
1.1385
DP-SEP (c= 5)
12.1623
1.0655
6.6139
DP-SEP (e=1)
82.9746
5.0777
44.0262
5
Related Work
To the best of our knowledge, no prior work on differentially private expectation propagation or stochastic expectation propagation cxits in the literature.
Remotely related work would be differentially private versions of Bayesian inference methods. This line of research started from (Dimitrakakis et al. 2014), which showed Bayesian posterior sampling becomes differentially private with mild condition
the log likelihood. Then many other differentially private Bayesian inference methods appeared in the literature, which include posterior sampling (e.g.. (Wang et al. 2015 Foulds et al.] 2016 Zhang et al. 2016 Li et al. 2019)), variational inference (Park et al. 2020; Jälkö et al. 2017), and inference for generalized linear models (Kulkarni et al., 2021). In this paper, we compare the performance our method to that of differentialy private VI (Jälkö et al. 2017 and differentially private expectation maximization (Park al. 2017)
6 Experiments
The purpose of this section is to evaluate the performance of DP-SEP on different tasks and datasets. First, we consider a Mixture of Gaussians for clustering problem on a synthetic dataset and test DP-SEP at different. levels of privacy guarantees.
In the second experiment, we consider Baycsian neural network model for regression tasks and quantitatively compare our algorithm with other existing non-privale methods for Bayesian inference. Our code is available at: httpp:://ithhb.... htwp://///h..oomm/////aoo/////
6.1 Mixture of Gaussians for clustering
In this section, consider Mixture of Gaussian model for clustering using synthetic data. Following Li ct al. 2015), we generate synthetic dataset containing N = 1000 datapoints drawn from J = Gaussians of 4-dimensional inputs, where each mean is sampled from a Gaussian distribution p(H;) = W[;; m,
m, /), each mixture component is isotropic p(x(h,) = (xx Ph,, 0.52 and the cluster identity variables are sampled from a categorial uniform distribution p(h, = j) =
We Lest EP, SEP, SEP with different clipping norms (clipped SEP), and DP-SEP to approximate the joint posterion over the cluster means μı and the cluster identity variables h, We also test DP-EM (Park et al. 2017] that adds Gaussian noise to the expected sufficient statistics to ensure the parameters of the mixture of Gaussians model to be differentaally private.
Figure visualizes the posterior means (two input dimensions are chosen for visualization) by each these methods after 100 iterations. For DP-SEP we set the clipping norm to C C=1 1. For SEP and DP-SEP, we
Following (Ld al. 2015 we also assume the the parameters be known.
10

---

Published in Transactions on Machine Learning Research (10/2022)
fixed the damping value, 7 = i..., 7/N = 1/1000. The figure shows that for restrictive privacy regime 1, the clusters obtained by DP-SEP are not well separated. However, as we increase the privacy loss, the performance of DP-SEP gets closer to the non-private ones (SEP and EP) and the ground truth. The posterior from DP-SEP exhibits a higher uncertainty than the other non-private methods due to the clipping threshold and the added noise to the mean and covariance during training.
In Table | we also provide quantitative analysis of the results above in terms of F-norm of the difference between the ground truth parameters (Gaussian parameters fitted by No-U-Turn Sampler (NUTS) (Hoffman & Gelman 2014) and the estimated parameters by each method. F-norm is first used to evaluate the accuracy of the learned posterior in (Li et al.) 2015). It is the L.2 distance between the parameters of the ground truth posterior and those of the learned posterior, when the parameters are flattened into a single long vector. The values reported in Table [ are averages across five independent runs of each method.
As one could expect, as the datasct size is relatively small N 1000 but the number of posterior parameters is relatively large, the privacy-aceuracy trade-off measured in terms of F-norm is poor. However, in the next. experiment with large datasets, this is not the case.
Table 2: Regression datasets. Size, mumber numerical features.
Dataset # samps
# features
Naval
11934
16
Kin8nm
8192
Power
9568
Wine
1599
11
Protein
45730
Year
515345
90
6.2 Bayesian neural networks
We explore the performance of DP-SEP neural network models to handle more complex real-world datasets for regression problems. The datasets used in the experiments are publicly available at the UCI machine learning repository and a brief description can be found in Table 2
We consider a fully-connected neural network model with 1 hidden layer, which consists of input layer that maps inputs to the hidden units and a hiddon layer that maps hidden units' output to the output of the network. Under this neural network model, a mini-batch of the data X, E Rexd propagates through the network by first going through the input layer, then the hidden layer sequentially given by
imput layer's output Zu = (X,Wo, )) network's outpul 2ı Zo T TTT,
(9)
(10)
where a is a element-wise non-lincarity such as sigmoid or rectifying lincar unit (ReLU) and the weight matrix of the imput layer is Wo and and weight vector of the hidden layer w1. Note that the size of Zu is the number of hidden units dy by the input dimension d. The size of the network's output is the mini-batch size s, the output of the network given a datapoint is 1-dimensional in the regression problems we consider here. We set the number of hidden units to 100 for Year and Protein datasets and to 50 for the other four UCI datasets we used. The likelihood of the mini-batch of the data under the neural network model is given by
Wo, Xo, 7) II ((Wllaa,
(11)
where 7 is the noise precision and 21, = w1 (Woo)))
fattpe://archive ice. uci. add/ml/index. php 3 For simplicity nolation, not include the bias term. However, in our code, use the bias term each layer.
11

---

Published in Transactions on Machine Learning Research (10/2022)
Table 3: RMSE on test data at c = 1 and = le-6 (UCI datasets)
Average Test RMSE and Standard deviation
VI
EP
SEP
SEP clipped
DP-SEP
DP-VI
Dataset
Naval
0.005 + 0.0005
0.003 + 0.0002
0.002 + 0.0001
0.002 + 0.0002
0.002 + 0.0003
0.010 0.0016
Kin8nm
0.099 + 0.0009
0.088 = 0.0044
0.089 0.0042
0.078 + 0.0033
0.078 = 0.0022
0.098 0.0085
Power
4.327 = 0.0352
4.098 = 0.1388
4.061 + 0.1356
4.013 = 0.1246
4.032 = 0.1385
4.350 = 0.1274
Wine
0.646 + 0.0081
0.614 = 0.0382
0.623 + 0.0436
0.627 = 0.0411
0.627 = 0.0362
0.734 0.0510
Protein
4.842 + 0.0305
4.654 + 0.0572
4.602 0.0649
4.581 = 0.0599
4.385 0.0589
4.934 0.0532
Year
9.034
8.865+ NA
8.873 + NA
8.862 NA
8.862 + NA
9.971 NA
Table 4: Test log logliielihhodd and 6 = 1e-5 (UCI datasets)
Avgerage Test logllikeldhood and Standard deviation
VI
EP
SEP
SEP clipped
DP-SEP
DP-VI
Dataset
Naval
3.734 + 0.116
4.164 + 0.0556
4.609 + 0.0531
4.710
0.0746
4.686 t 0.1053
3.253 + 0.1248
Kin8nm
0.897 + 0.010
1.007 = 0.0486
0.999 = 0.0479
1.121 + 0.0332
1.125
0.0212
0.928 + 0.0446
Power
-2.890 0.010
-2.830 + 0.0313
-2.821 0.0316
-2.809 + 0.0293
-2.814 = 0.0323
-3.077 = 0.0816
Wine
-0.980 0.013
-0.926 + 0.0487
-0.936
0.0643
-0.938 + 0.0581
-0.938 - 0.0486
-1.213 0.0831
Protein
-2.992 + 0.006
-2.957 + 0.0121
-2.945 + 0.0139
-2.911 + 0.0128
-2.941 = 0.0130
-3.049 = 0.0382
Year
-3.622 + NA
-3.604 + NA
-3.599 + NA
-3.598 + NA
-3.597 + NA
-3.974 + NA
The first comparison method is probabilistic backpropagation (PBP) (Heránndez-Lobato & Adams
2015 an
approximate Bayesian inference framework for neural network models. PBP, each clement of the weight matrices in all layers (input layer and hidden layer if we have ondehidden layer) assumed to Gaussian distributed with scalar precision parameter in the prior distribution. Furthermore, Gamma distribution is imposed on the noise precision parameter prior distribution and the precision parameter hyper-prior distribution:
ha d p(W) = IIII N (wwoss 00, 1,,-1),
(12)
i=1
ha
p(w1) II k=1
N (W1,ee 1, )-
(13)
p(A) = Gam (A / B2),
(14)
p(7) = Gam a (8))
(15)
The approximate posterior is assumed to be factorized for computational tractability, given by
(WW, W1, 7,
IIII
N (Wwosslmy vy)) II 1=1
N (WL ok)
1=1
Gam(Ala 8* Gamm)yaaa
(16)
where {my, Vij, myy U/g ,33 ",0,"'07 are posterior parameters.
PBP uses assumed density filtering (ADF) for estimating the posterior parameters (Maybock 1982. ADF can be viewed as a simpler version of EP. It maintains global approximation only and as a result performs poorer than F.P.
12

---

Published in Transactions on Machine Learning Research (10/2022)
We use the same prior and posterior configurations as in PBP in other comparison method such EP, SEP, SEP with only clipping, scalable VI method for neural networks described in (Graves] 2011] and it's privatized version, DP-VI. We derive the variational inference procedure in Sec. D in Appendix and implement the differentially private version of it in PyTorch.
We consider the 90% of the original dataset randomly subsampled without replacement as a training dataset and the remaining 10% as a test dataset. All the training datasets are normalized to have zero mean and unit variance on their input features and targets.
For SEP, clipped SEP and DP-SEP, we fix the damping factor to 1/N. We also fix the clipping norm to C 1 for DP-SEP. Further experiments on DP-SEP with different clipping norms can be found in Sec. D in Appendix. We set the privacy budget. to e e= 1 and 5 = 10-5 in DP-SEP. In DP-VI experiments we fixed
= 10-5 and set a value to get a final 6 x 1. The detailed dyper-parameter setting for VI and DP-VI experiments can be found in Table and Table in Soc. D.1 in Appendix.
Table 3 and Table shows the average lest RMSE and test log-likelihood after 10 independent runs for each dataset except for Year, where only one split is performed according to the recommendations of the datase
When comparing between non- con-private algorithms, the RMSE and test log- log-iikeihood indicates that EP based methods (EP, SEP and SEP clipped) give better posterior estimates than those obtained by VI. In terms of DP-SEP performance over the different datasets, the results show that our algorithm gives better approximates than those from DP-VI and that it comparable to SEP and even better in some cases as for Kin8nm. In fact, clipping the norm of the natural parameters and the intermediate approximating factor on the SEP algorithm has positive effect the original algorithm and reduces the test averaged RMSE in most cases. This seems to indicate that clipping acts regularizer (or constraint) for the posterior to be well concentrated.
In Table 5 in Sec. C in Appendix, we also show the point estimate (through the usual stochastic gradient descent) which helps gauging how well these approximate inference methods are performing in an absolute sense. The results show that in most of the UCT datasets we considered, DP-SEP outperforms the point. estimate.
7 Conclusions and future work
In this work, we have presented differentially private stochastic expectation propagation (DP-SEP), a novel algorithm to perform private approximate Bayesian inference based on the SEP algorithm. In DP-SEP, we add carefully calibrated noise to natural parameters to obtain differentially private posterior distribution. We provide theoretical analysis on how the noise added for privacy affects the accuracy on the posterior distribution.
The clustering experiments under the Mixture of Gaussians model with a relatively small synthetic dataset shows that DP-SEP produces approximate posterior distributions that present higher uncertainty than those generated by non-private methods due to the poor sensitivity. We also provide quantitative results comparing the ground truth parameters and the posterior parameters by DP-SEP, where relaxing the privacy constraints improves the accuracy of the private posterior distributions. We also test DP-SEP on real-world datascts for regression tasks by implementing DP-SEP for neural network model. The results show that DP-SEP often yields the posterior distributions that are better than those by SEP, thanks to the help of clipping natural parameters and large dataset sizes.
SEP provides better uncertainty estimates than variational inference, which was demonstrated in the experiments we presented as well as in existing literature. We look forward to extending our private SEP more large-scale scenarios such as federated learning settings, which can be done in straightforward way.
4 4See: http://wwwccive.i..iiiiccc... http:///ww............//...////a
13

---

Published in Transactions on Machine Learning Research (10/2022)
Acknowledgments
We thank the support, computational resources, and services provided by the Canada CIFAR AI Chairs program (at AMTT) and the Digital Research Alliance of Canada (Compute Canada). This work was done while M. Vinaroz was a visiting international research student in the department of computer science University of British Columbia. We thank our anonymous reviewers for their constructive feedback. Their leedback helped us improve our manuscript significantly.
References
mathoverflow: Approximating [[[//]], 2019. URL http:://aabboerrtoo...r//ess/ss/ [Online; accessed 20-October-2021]
approximating marrox/lating--athbbbee..x mathbbel-x
M. Abadi, A. Chu, 1. Goodfellow, H. Brendan McMahan, 1. Mironov, K. Talwar, and L. Zhang. Deep learning with differential privacy. ArXiv e-prints, July 2016.
Shun-ichi Amari and Hiroshi Nagaoka. Methods of information geometry. volume 191, 2000.
Galen Andrew, Om Thakkar, Brendan McMahan, and Swaroop Ramaswamy, Differentially private learn- ing with adaptive clipping. In M. Ranzato, A. Beygelzimer, Y. Dauphin, P.S. Liang and J. Wort- man Vaughan (eds.), Advances in Newral Information Processing Systems, volume 34, pp. 17455 17466. Curran Associates, Inc., 2021. URL https://prcceedagg.eenl http://awg....urrrrpoc..pc/////p /0//1///////02// pdf
Matthew James Beal. Variational algorithms for approzimate Bayesian inference. PhD thesis, University of Tondon, 2003.
John P. Cunningham, Philipp Hennig, and Simon Lacoste-Julien. Gaussian probabilities and expectation propagation, 2013.
Christos Dimitrakakis, Blaine Nelson, Aikaterini Mitrokotsa, and Benjamin L.P. Rubinstein. Robust and private Bayesian inforence. In Algorithmic Learning Theory (ALT), pp. 291-305. Springer, 2014.
Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Found. Trends Theor. Comput. Sct., 9:211-407, August 2014. doi: 10.1561/0400000022 URL http://dxx doi www.oo.........1... 1561/ 0400000042
Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Eurocrypt, volume 4004, pp. 486-503. Springer, 2006a.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Shai Halevi and Tal Rabin (eds.), Theory of Cryptography, pp. 265-284, Berlin, Heidelberg, 2006b. Springer Berlin Heidelberg. ISBN 978-3-540-32732-5.
James R. Foulds, Joseph Geumlek, Max Welling, and Kamalika Chaudhuri. On the theory and practice of privacy-preserving Bayesian data analysis. In Proceedings of the 32nd Conference Uncertainty in Artificial Intelligence (UAI), 2016.
Alex Graves. Practical variational inference for neural networks. In J. Shawe- Shawo-Taylor, R. Zemel, P. Bartlett, Pereira, and K. Q. Weinberger (eds.), Advances in Newral Information Processing Systems, vol- ume 24. Curran Associates, Inc., 2011. URL https://proceeednng. htw.ooceeddnnnn.eeuiiiieee Cebccbssdd1SBooraaeeeeerrr622222 .ddf
neurips wwtparrpsscccpppeeee/e cc/paper/2011/f/lee
José Miguel Hernández-Lobato and Ryan P. Adams. Probabilistic backpropagation for scalable Icarning of bayesian neural networks, 2015.
Matthew D. Hoffman and Andrew Gelman. The No-U-Turn Sampler: Adaptively setting path lengths in hamiltonian monte carlo. Journal of Machine Learning Research, 15:1593 -623, April 2014.
14

---

Published in Transactions on Machine Learning Research (10/2022)
J Jälkö, O. Dikmen, and A. Honkela. Differentially Private Variational Inference for Non-conjugate Models. In Uncertainly in Arlificial Intelligence 2017, Proceedings of the 33vd Conference (UAT), 2017.
Michael I. Jordan, Zoubin Ghahramani, Tommi S. Jaakkola, and Lawrence K. Saul. An introduction to variational methods for graphical models. Machine Learning, 37(2):183 233, November 1999. doi: 10.1023/ 0111223/A11000665977777 URL http://dxx... www.ddo..oooooooooo..oo org/ 1561/0400000042
Tejas Kulkarni, Joonas Jälkö, Antti Koskela, Samuel Kaski, and Antti Honkela. Differentially private bayesian inference for generalized linear models. In Marina. Meila and Tong Zhang (eds.), Proceedings of the 38th International Conference on Machine Learning, volume 139 of Proceedings of Machine Learning Research, pp. PMLR, 18 24 Jul 2021. URL https://proceeeingg..i.
bttess/vv39//ul// 21t.htm1
Alexey Kurakin, Shuang Song, Steve Chien, Roxana Geambasu, Andreas Terzis, and Abhradeep Thakurta. Toward Training at Imagenet Scale with Differential Privacy, 2022. URT. https://arxiv/ wrgg aba/ 2201
12328
Bai Li, Changyou Chen, Hao Liu, and Lawrence Carin. On connecting stochastic gradient meme and differential privacy. In Kamalika Chaudhuri and Masashi Sugiyama (eds.), Proceedings of the Twenty- Second International Conference on Artificial Intelligence and Slatislics, volume 89 of Proceedings of Machine Learning Research, pp. 557-566. PMLR, 16-18 Apr 2019. URL https::/procceednng. .mlr press/v89/iii html.
Yingzhen Li, José Miguel Hernández-Lobate, and Richard E. Turner. Stochastic expectation propagation. In Advances in Neural Information Processing Systems 29, 2015.
P.S. Maybeck. Stochastic Models, Estimation, and Control Academic Press, 1982.
Thomas P. Minka. Expectation propagation for approximate bayesian inference. In Uncertainly in Artificial Intelligence, 17:362 369, 2001.
Manfred Opper and Ole Winther. Expectation consistent approximate inference. The Journal of Machine Learning Research, 6:2177-2204, 2005.
Mijung Park, James Foulds, Kamalika Choudhary, and Max Welling. DP-FM: Differentially Private Exxectation Maximization. In Aarti Singh and Jerry Zhu (eds.), Proceedings of the 20th International Conference on Arlificial Intelligence and Stalistics, volume 54 of Proceedings of Machine Learwing Research, pp. PMLR, 22-22/6 Apr 2017. URL https::/prooceeiings mlr Prress/v54/pa//e htttparrr1ccc.11l1111.
Mijung Park, James R. Foulds, Kamalika Chaudhuri, and Max Welling. Variational bayes in private settings (VIPS). J. Artif. Intell. Res., 68:109-157, 2020. doi: 0.16133/jair..11177) URL https://doi.org/// 1613/jair 1. 11766
Joel A. Tropp. An introduction to matrix concentration inequalities. Found. Trends Moch. Learn., 8(1-2): 1-230, 2015. ISSN 1935-8237. doi: 10.1561/220000000 URL http://dd..a11...gg.110.111202.2
Richard Turner and Maneesh Sahani. Probabilistic amplitude and frequency demodulation. In J. Shawe- Taylor, R. Zemel, P. Bartlett, F. Percira, and K. Q. Weinberger (eds.), Advances in Neural Information cc/
Processing Systems, volume 24. Curran Associates, Inc., 2011. URL
pdf
Y.-X. Wang, S. E. Fienberg, and A. Smola. Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo. Proceedings of The 32nd International Conference Machine Learning (TCMT), pp- 2493
2502, 2015.
Yu-Xiang Wang, Borja Balle, and Shiva Prasad Kasiviswanathan. Subsampled rényi differential privacy and analytical moments accountant. volume 89 of Proceedings of Machine Leurning Research, pp. 1226 1235. PMLR, April 2019.
Zuhe Zhang, Benjamin Rubinstein, and Christos Dimitrakakis. On the differential privacy of Bayesian inference. Tn Proceedings of the Thirlieth A AAAT Conference on Artificial Intelligncce (AAAT), 2016.
15

---

Published in Transactions on Machine Learning Research (10/2022)
Appendix
A KL between SEP and clipped SEP
Denote the posterior distribution of SEP by 9 == Mu Egg and the posterior distribution of SEP with clipping threshold C by p == NV Ep) where the following relation for natural parameters holds: Up na/ max 1,, [ and Ap Ag/ max (1, (aglee) Then the KL-divergence between and p can be expressed - c=
in terms of q by:
1
d max (I, [1Aglle)) + 6²/ max (I, [Aglle) C
(A,"na) Tn d + dlog max L }
Dulglpp] =
C
where b b- max (1, ( mmxx (I, |imalle)
Proof. The closed form for the KL-divergence is:
1 Dudll = Tr(Ep Eg) + (Mp Mgy E (Mp Myy d + log
Epp [2ip]]
we can rewrite the KL-divergence in terms of the natural parameters (E=A- and μ A A-1n)
A7711
Dalalle] Tr(ApA71) + (Ap m - An)n)) A np - A - + log
(17)
Ag
We have by definition of Ap that AT Ag// max (1, [Agglle) )1' = max (1, [|Aglle) A, and
|A |max (1, |
|A, so the logarithmic term becomes:
|Ap"
) d log (max (1, |ا
= log (1, |
log
|A,
C
For the trace term we have:
Tr(ApA71) Tr(1/ max (1, (Aglle)) A₂, Tr(1/ max (1, (Ayle) Ia) dmax (1, [lAllle)
(A7 np \1) max (1, 11Allllee max (1, [ 1 A 114 bu ng
Thus the quadratic term can be rewritten
(A, hp na) TT Ap AA' b² max (1, [|
(A,'m0))
(n) TAg -m Ag
b² max (1, (AAllll))) (172
Then the KL-divergence be expressed in terms of the natural parameters of q by:
16

---

Published in Transactions on Machine Learning Research (10/2022)
1 Dalgle) = dmax (1, [1aal=)) + +B2 max (1, (Mallee)) (A, 11""nn)"n - + dlog max
)
(1, | C
)
2
B Proof of Thm. 4.1
Proof. Denote the posterior distribution from SEP by q: (( En) and the posterior distribution of DP-SEP to be p = Nppp, Ep). Mean and moment parameters of q can be expressed in terms of the natural parameters by Σgg A and M4 A-1ng By and the those of p verify the following relations:
7p 14 + where e, (0
Ap Ag + where Ei ~ o()
Here, we define
= (-Amin (Ag E) + p)T
(18)
to ensure that Ap is positive definite by laking the minimum eigenvalue of A, + E and adding a small positive constant P such that Amin + E + A) p.
The KT-divergence is written closed form in terms of natural paramcters:
Eg (Da(alp)))
Ee ET(TT(ApAA + EaBx((A, )7) Ap(A," m1 -, -))")))
log
[Ag] |Apl
+ EE
(19)
In bounding some of these terms, we rely the tail probability of a Gaussian random matrix. First, ro-formulate E as matrix Gaussian series where
E
o
(20)
where is standard normal Gaussian random variable and {Bb] } is a finite sequence of fixed symmetric (Hermitian) matrices. Then, due to Theorem 4.6.1. Tropp (0015).
Eg Amaz [E] < (2u(E)
(21)
where the matrix variance statistic the sum is denoted by vEE) = E B& and by symmetry (since has the same distribution as E),
E Amin E)] = Eg Aman E)].
Eg Amaz E)],
v 22 log(d).
(22)
Furthermore, for all M 2 0:
-M2 P(Amar E M) dexp
(23)
(2(EE)
17

---

Published in Transactions on Machine Learning Research (10/2022)
and
P(Amin (E) 2 -M) 2 - dexp (-M²
(24)
(2x(E)
Now we take look at each term below.
First term:
EB(Tr(ApA71))
(25)
= =RETr(T + EA," + ANT
(26)
=Tr(T) + EE (Tr(EETT EgTr(AA,))
(27)
= =Tr(I)+ +
(28)
due to https: fttps://statian fttps://statpproobbbolt github. io/P /eeemmmanttee tr
(29)
= d (r.
(- (A + E) + ,) ( 1), since ER (E(EA))) O, due to eq- 18
(30)
< d. + Tr (BEE(EEAAAAaaaa (A)) Amin EE) + ,)),,"), by Weyl's inequality
(31)
= d + ((-((mm (Aq) EE (mmn EE) + p)A
(32)
s d Tr((->min (Ag) v 20 log(d) (d) + p)A due eq. 22
(33)
Second term:
E.EE((A, 1/ ng 4, 1/p n1))
E.Eg(( (1p Ap - 111 , (1p - A, A1A1a111) 114))
E. (0 e)) A,
T A ) (1g e) A n1y) 1/
E.EE((M +e A- 1/4 A= [ [g + 0 - Ap 71))
EoEEE(19 A 1
1/6 + T A/' nn + AeAp" e- - TT eAaa'11
11y N_A,"tm--1 -
2 ,,
-
= EE((n - , -
f1 T 1 + M1 A, Ap / ny)
fl
155(Mn Ap1mm) m1)) 11 A, 114 + 0. BE (Tr((A)))) my A f4y
Eg (1gg A Ap mTm
Ex(1, T A m1)
11 A 11 + of EB (T (A-1)))))))))))))) Eg (11 T A AA mpn)
1 (+ (0(E) log(d)
Ar(A,)
-74 T A na
|+
- 2M -m-n (Nol+p) 21(1g)
(1
2M Aman (A,)+o)
1=1
(1,)))
1+ Am)n((,)) log(e)
+ of Amar (ig) Σ
A:(A,)
[+ 11 -2M -Mm- Am (g)+ A:(A.))
2M Amma (g)+t Ac(An))
1
a
(-Amai (Ap) + / (E) log(d) +
(34)
1=1
The inequality in the last step is due to:
1. For bounding Eg EE A,' (g); we first re-write Ap
Ap= = A [ A + A)A #1 A and denote
(E+
b = A 7/
(35)
P(E) = A₂ E A)A
(36)
18

---

Published in Transactions on Machine Learning Research (10/2022)
to simplify the notation in the following steps. Thus, we have:
EE(b' 1 P(E))
(37)
= Eg
Tr([I + P(E)] bb T]
(38)
U + (P())
Re
Σ
(39)
1
Σ BEE
1 + T+X()())))
(40)
where the last line is because the sum and average are linear operation, swap the order. Here (E)) denotes the i-th eigenvalue of P(E).
Now, we are interested in upper bounding EF [PA:( To do so, we use the following (mat
2019): a random variable X is bounded by S X s H, then
H + h E(X) Hh
E
(41)
X
Because we are adding Gaussian noise and the domain Gaussian noise is unbounded, (P())) not strictly bounded. Hence, using the tail bound of random Gaussian matrix, we achieve the bounds with high probability.
Here, we set X = 1 + (P((E)). Recall M(((E)) = A X + (A)) i (1....,d}, (Ag)) Az
because A is a diagonal matrix. We need to identify what and are that satisfy h (+)A(((())) S H.
First, we know that the following holds:
1 + (+((E) S Ama (E) Amaz (A)
M Xmar (A)
51+ Az(Ag)
(42)
>z(Ag)
where the last inequality is due to eq. 23 Now, we find the upper bound for Amaz
Amarr
(43)
Amaul [( Amin (A, + E) + p)4], by defition of given in eq. 18
(44)
Amiin (Ag
E) +
(45)
S --minn (Ag) Amin EE) p: by Weyl's inequality
(46)
< -dmin (g) + Xmaz
(E) + p, -E has the same distribution as E
(47)
< Amin + M + p due to eq. 23
(48)
Hence, we establish the upper bound given by
2M + p Amin (Ag)
(PP() SH:= = 1+
(49)
)r(Ag)
with probability given in eq. 23
19

---

Published in Transactions on Machine Learning Research (10/2022)
(E++
E
Now, it remains to lower bound, + (P(())). First, we know that (.(P(E)) = A
Ag
(E) xx(A)
Amin (E) Aman (A)
Let's find a lower bound for Amin (E) + Amin (A). As before,
)c(A,)
>x(Ag)
Amin (A)
(50)
Aminl (oninl((AAnn Am-in (Aq + E) + p)1},
(51)
Ammin (Ag + E) +
(52)
2 Amina Amiin(A)) - Amaz (E) + p), by Weyl's inequality
(53)
Amin (Ng) + Amsn (E) + P. since -E has the same distribution as E
(54)
Amén (mg) M P, due to eq. 24
(55)
From eq- arrive at:
24 have that Amin E 2 M with probability at least 1 - dexp
-M²2 2n(
Hence,
Amin E + A) = Amin (E) + Amin (A) 2 - Amin 2M +
(56)
Assuming -Amin (Aq) 2M + + p (as we set P be small),
(P((E)) Amin EE) + Amann (A) 22 + p- Am))(Ag)
(57)
)x(A,)
Ac(A,)
Hence, the lower bound is
h : 1+ 2M + p (men(Ag)
< + Amin (P(E) 1 ((((E)))
(58)
A1(Ag)
with probability given in eq. 24 Hence, using the bound in eq.
41
we bound the following:
1
EE
(59)
+ (P(E))
1
22 Aman (Ag)+P Ac(A,)
+1+
2M Am Az(A,)
EE (Pe(P(E)))
(60)
1 + 2M Amenlda)ty Ar(A,)
1
2M 2M-Amin (Mgdte )o(d,))
1 + 2p 1p-22mmn(AA) (Agg {r(A.)
EE (Ap(P(E)))
(61)
1 + -M - Amen )r(A,)
2M Amon(Ag) [
)r
with probability at least d exp
Now, it remains to upper bound the expectation term in -EE(A(P(E))), Following the same trick as before, we lower bound Eg(A((((E)):
M2
2x(E)
Eg|A((((E))
(62)
= A((A))
EEA((A + E), by definition P(E)
(63)
(ERA(AA) EE))
(64)
x;(Ag)
2 Ar
(EEA(()) + Egdmin E)), because Egdmin (E) < Eg)((E) < EgAmar E
(65)
(EEA((A) (x) log(d)) because of eq. 22
(66)
>x(Ag)
(-Amin (Ag) 20( log(d) + p).
(67)
>;(A)))
20

---

Published in Transactions on Machine Learning Research (10/2022)
where
EB [A,(
(68)
EEl Amin (Ag + E) + pl, by definition of Ammin (BB(A, (A + E)) +
(69)
(70)
since Amin is a concave function and Amin is convex. With Jensen's inequality
(71)
mmnn (Ag) + P, since Ep. (E) O.
(72)
As before, we re-write Ap
A [ Ar (E+ (E+ A)A,* A
The inverse
4,
A)A, Ag 1+ Ag (E+ A)A, 1 Az Therefore,
Be(Tr(A77))
[ + A, (E (E+ A)A $1 Ag
= =EE(Tr(AA
(73)
= -EE(Tr( I + An (E + A)A; [] Eg)), due to the Cyclic property Trace and Eg = A
(74)
Ax
< Eg
due to eq. 35
(75)
{c(((E))
Amaz (En)
EF
(76)
1+ (P())
1 2p 2Amin Ar(AA))
(2((E) log(d)+ Ammnn (Aa)-p
Amaz (En)
Σ
Ar(Aog)
duc eq.
(77)
2M Amir (mn) (r,)))
(1
2M Ammnn Arld,)
+ P- Aman (Ag) (2)))(220())) log(d)
< Amaz (Eg)
(r(Ag)
(78)
1+
2M Amain (A,tte) )x(A,)
(1+
2M Ammia (A,)e Ac(Ag)
EE A7 11-AA--
AA 1h)
(79)
= EEe(a Aa), where a = -A,*m
(80)
Eg V
0 1--mmi (Ag + E) + p), due to the definition of A
(81)
a² Eg Bg(-Aman (Amin(Ag E) + p), since expectation linear operation and a is constant E
(82)
(-Xmin(A,)) EF Amin (E)] + p),
(83)
by Weyl's inequality and since expectation preserves inequality
(84)
a
Ammn (Ag) Ess Amar E)] + p), due to the symmetry of E
(85)
d
Σ (-Amin(As)) +
ax
p). duc to eq. 21
(86)
21

---

Published in Transactions on Machine Learning Research (10/2022)
Third term:
Since Ap = Ai [ + Ag (E A)A7" $] A
|Aggl
EE
log
(87)
AAp
Agg
EE
log
(88)
|Ag
+ Ag
2
E + A)A₂ 2
Ag
1
Eg
log
due to eq. 35
(89)
1+ (P((E)
i=1
1
EE log
swapping and E;
(90)
1+ (+((()(E))
Σ log
EE
1 + (P(E))
because log is concave
(91)
d
1 Amen (Ag) / (0(E) log(d)
Ar(A,)
log
(92)
(1+ - Ami (Ag)+
(1 (1
2M Ammm((.)+
((gg)
where the final result due eq.
59
B.1 Discussion of the bound
In the following want to give insight of how the upper bound in Thm. 4.1 becomes 0 when N - From the definition of 02 a 2C
N 0 as N - oc. Recall
Ex Daa(alp)))
$ Tr((- (Ag) + 20(E) log(d) + p)A."))
Term
Amsn (A.) + (E) log(d)-
Hl
1+
+ 0 Maa (Eg)
(r
(93)
hH
Term
Amin (Ag)+ 2e( log(d)- xi(Aa)
h+ H
+
N4 A 1-1m 11
hH
Term
Term
Amin Amin((A))) + 20(E) log(d)
h + 11 +
log(d) + aa (-Xmin (Ag) + (/)(E) log(d)+ + +))
D log
Ar(
hHl
Term 5
Term 6
where b, = (A, no)s, A, ng. h 1 - 2M A and H 1 1+ 2M Am A.(A,)
Ar(A,)
22

---

Published in Transactions on Machine Learning Research (10/2022)
Term 1:
v (x) log(d) p) = (Ag) + ,)A;')) ) due to limoz-+0 u(E) =
(94)
(95)
= O, because A = 0 and p Smin((n)
(96)
.Term 2:
Aman (Ag) 20(E) log(d) Ar(
h H
o Ama (2n)
0, due to 01
(97)
1H
Term 3:
Aman (A,)+ (B) log(d)
h H
(,
(98)
hH
h + H 1
Aman (Ag) -p )r(Ag) hH
0
due to lim v(E) 0
(99)
i=1
h H
b2
because p == Amin (Ag)
(100)
hH
(=1
77 A, 7y:
because H = and the definition of b;
(101)
(102)
Term 5:
aa T
(-Amin(Ag) + (E) log(d) +p)
(103)
(->min (Ag) + p) due to limoz-10 vEE) 0, because p Amin (Agg)
aa
(104)
(105)
Term 6:
h + 1 Amin (Ag) + y (2(EE log(d) -
D log
(r(Ag)
(106)
hH
h H 1+ Amin(A,) Ae(Ag)
log
due to (0
(107)
hH
+ H -1 1 hH )
log
because p Amin (Ag)
(108)
0, because = =
(109)
C
Point estimates
We also show the point estimate (through the usual stochastic gradient descent) in Table 5 which helps gauging how well these approximate inference methods performing in absolute sense.
23

---

Published in Transactions on Machine Learning Research (10/2022)
Table RMSE on test data (UCT datasets)
Arg. Test RMSE and Std.
Dataset
Point Estimate
DP-SEP
Naval
0.001 + 0.0001
0.002 + 0.0003
Kin8mm
0.091 + 0.0015
0.078
0.0022
Power
4.182
0.0402
4.032 0.1385
Wine
0.645
0.0098
0.627
0.0362
Protein
4.539
0.0288
4.585 T 0.0589
Year
8.932 NA
8.862 NA
D Differentially private variational inference under the neural network model
Similar to the idea of DP-VI, we derive the variational lower bound under the neural network model, and then apply DP-SGD to ensure the approximate posterior to be differentially private.
For simplicity, we treat the noise precision y and the prior precision as hyperparameters, and we impose priors only the weights:
ba p(W) ПI N(wo,:10,A-1) ==1 p(w)) 10,
(110)
(111)
(112)
The approximate posterior over the model parameters 0 = {Wo. wi is given by
ha
(0) = <(Wo)a(w)) = II (i) (
(113)
where {m, v., mp, v are posterior parameters. Recall from Sec. 6.2 the likelihood of the mini-batch the data under the neural network model given by
p(DI0) == p<ylWo wT, X.,7) = II N Nwunl=1,n
(114)
x==1
where y is the noise precision and 2 = w (W(Xx.)
The variational lower bound in this case can be written
Ey [log (DD))] Dxzlg(0)lp(())
(115)
Given the factorizing Gaussian prior and posterior pairs, the KL divergence is closed form
Dkzlg(0)[p(() = DEL
+ DDLll((w))lp(v)))
(116)
d-1
d+1
Anj + Am, T m; - (d (d + log (2)
Σ
log (wij)
2
==1
hes
hd
+
Xuf + Am,, mm - has ha log, (A) - 2
log, (2/)
(117)
2
24

---

Published in Transactions on Machine Learning Research (10/2022)
We can further expand the first term in eq. 115
By( [log (D
Σ a (WWo)(( logg)) ( NoWoo/ o((oox)), dWo dw1>
(118)
Σ /a(w))
[f [[N(milm' v) (-2 - wi [.oo))) - 2 log 12 -1-11 |1 dWa,
(119)
Σ
2yn T 20, + Tr((2o,n20.r T)V' + mn mm )m²) 2 (-((vv) ((W)) (uhh
log /
' dWo
(120)
where 20,n = (Wox,) and V a diagonal matrix where diagonal entries are v'. Due to the nonlinearity, the final integral not analytically tractable. We use the Monte Carlo approximation to the integral by using L samples drawn from w ~ ((W):
Un 2y To(( xn) + ( W + an'TTooWW x, x xn) ())")m²)
2
1=1
12 log 12 -.
(121)
Applying DP-SGD to this objective function requires the sample-wise gradient to be limited by a clipping threshold and then adding the Gaussian noise with a noise scale tuned by oC, whore o is the privacy parameter. To compose privacy loss, we use the analytic moments accountant by (Wang el al. 2019
D.1 Bayesian neural networks hyper-parameter settings
Here we give a detailed hyper-parameter setting used for computing the VI method and the privatized version under neural networks experiments on the UCI datasets. Table and Table 7 reflects the number of epochs, batch size, learning rate, noise precision (7). prior precision (A), number of samples used in Monte Carlo approximation, KI-divergence regularizing parameter (3), clipping threshold (C) and the standard deviation for the Gaussian noise (a) used for each dataset.
Table 6: VT hyperparameter settings
epochs
batch size
learning rate
MC samples
Naval
100
100
1-10-4
20
1
10
KinSnm
100
100
1-10-a
10
100
20
0.01
Power
200
100
9-10-4
18
100
10
0.001
Wine
40
1-10-2
200
Protein
100
1-10-5
50
100
Year
40
2000
1 1-10-5
1.5
Table 7: DP-VI hyperparameter settings with a privacy budget e
and 10-5
epochs
batch size
learning rate
À
MC samples
9
C
Naval
100
10
10
5
KinSnm
100
1-10-3
100
20
0.01
1
1.7
Power
200
100
9-10-4
100
20
0.001
1
Wine
40
100
1-10-2
200
20
0.01
5
30
Proteiu
100
200
1 1-10-5
50
100
20
2
1
1.2
Year
40
2000
1-10-5
1.5
1
20
0.1
1
1.1
25

---

Published in Transactions on Machine Learning Research (10/2022)
E
Clipping effect on DP-SEP
We study in this section the effect that the clipping threshold C choice has in DP-SEP posterior ostimates for fixed privacy budget of e = 1 and = 10 Table 8 and Table g shows the averaged results and the standard deviation for the RMSE, and test. log- lig-likelhhod obtained for each dataset on independent runs. As the value of C increases, we are letting the natural parameters to retain more information but at the expense of adding higher variations due to the Gaussian noise addition that also depends on the clipping threshold.
Table 8: RMSE on test data (UCI datasets) from DP-SEP at different C
Avg. Test RMSE and Std.
Naval
Kin8nm
Power
Wine
Pmotein
Year
0.0025
0.0007
0.079 + 0.0020
3.997 + 0.0762
0.600
0.0470
4.601 + 0.0485
9.971 + NA
0,0026
0.0006
0.082 + 0.0045
4.007 + 0.0707
0.605
0.0169
4.660 + 0.0397
10.013 + NA
3
0.0034
0.0010
0.083 + 0.0076
4.014 + 0.0817
0.608
0.0482
4.692 + 0.0517
10.025 + NA
0.0034
0.0007
0.085 + 0.0061
4.057 + 0.0812
0.612
0.0468
4.746 + 0.0872
10.041 t NA
0.0038
0.0005
0.087 = 0.0062
4.081 + 0.0886
0.619
0.0128
4.797 + 0,1122
10.064 1 NA
0.0042 10
0.0005
0.090 + 0.0078
4.153 + 0.0622
0.636
0.0353
4.946 + 0.1312
10.108 + NA
Table 9: Test bogliikelhood (UCI datasets) from DP-SEP different C
Arg. Test log- oiglikelihood and Std.
Naval
KinSnm
Power
Wine
Protein
Year
1
4.545 +: 0.2675
1.116 0.0195
-2.805 + 0.0173
-0.903 = 0.0651
-2.945 + 0.0115
-3.974 + NA
2
4.535 +: 0.2253
1.108
0.0167
-2835 + 0.0289
-0.907 = 0.0651
-2.988 +: 0.0160
-4.01 + NA
3
4.413 +: 0.2373
1.098 - 0.0196
-2.315 : 0.0372
-0.911 = 0.0611
-2.881 : 0.0227
-1015 - NA
4
4.430 + 0.2895
1.093 0.0215
-2.82 + 0.0812
-0.15
0.0621
-3.020
+ 0.0366
-.026 + NA
5
4.360 + 0.2927
0.0237 1.091
-2.886 + 0.0886
-09966
0.0549
-3.064
4: 0.0698
-4.42 +
+: 0.3607
1.069
0.0622
0.0482
-3.96
0.0881
NA
26


Reviews:
[{"review_id": "cHxJsxg6NJ", "reviewer": "Reviewer_m1oy", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: SEP provides better uncertainty estimates than variational inference. Having a private version of SEP is useful for private Bayesian inference. The theoretical results are sound to me. The experimental results provide an extensive comparison with the non-private baseline and other private algorithms. \n\nWeaknesses: I think the novelty of this paper is not significant enough. Although the paper lists a few differences compared to DPSGD. I think the only difference is to not use the batch (which is not from a privacy perspective.) And clipping for statistics that have unbounded domain is widely used in many privacy + statistics papers. The privacy guarantee follows immediately from previous results. The paper even doesn't provide the relation between \\epsilon, \\delta, and \\sigma. Even if they use the auto-dp package, I think proposition 2 should include the explicit expression or at least the order of this relation. As for the accuracy guarantee, Theorem 4.1 is only for per round, and it doesn't provide any formal guarantee for the overall accuracy. Moreover, Theorem 4.1 is not that informative, and more explanation should be discussed. For the experiments, I also have two concerns. 1. In Table 1, it seems that DP-SEP is much worse than DP-EM under a reasonable \\epsilon. 2. The paper claims that ``as we increase the privacy loss, the performance of DP-SEP gets closer to the non-private ones and the ground truth.'' on page 10. However, from Figure 1, it seems that the performance of \\epsilon=50 is almost the same as \\epsilon=5. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "This paper studies private approximate Bayesian inference and proposes a DP-SEP algorithm based on SEP. The privatization method is similar to DPSGD (with some differences). From the theoretical perspective, this paper provides sensitivity analysis, differential privacy guarantee, and accuracy guarantee. The paper also provides experimental studies on two tasks: mixture of Gaussians for clustering and Bayesian neural network.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "1. Include the explicit expression of the relation between \\epsilon, \\delta, and \\sigma in proposition 2.\n2. Discussion Theorem in more detail (like what Theorem 4.1 implies what/where each term is from/from Theorem 4.1, what can we say about the overall accuracy).\n3. Address my concerns about the experiments.\n4. To make this paper stronger, it might be interesting to empirically study the choice of clipping norm and clipping as a form of regularization.", "broader_impact_concerns": "No.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "c0g24ic2hr", "reviewer": "Reviewer_SHsv", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strength: non-trivial utility result and relative complete comparison is made\n\nWeakness: adopting DP to SEP is trivial and the analysis is straightforward. from the experimental result, the clipping threshold C seems to have a big impact on the performance if not chosen appropriately, some discussion which is missing on choosing C seems necessary. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "In general, this paper develops the private version of the stochastic expectation of propagation. For the case of EP, the sensitivity analysis is difficult whereas, for SEP, it is straightforward. This paper gives an algorithm as well as an analysis for its implementation. Most importantly, the theoretical analysis on the utility is given.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I have some questions which are related to the DP-SEP algorithm, 1) in line 7 in alg. 3, why not just add the noise to the clipped result ( it is still DP), will this be any different on the performance? 2) why do you do the clipping in line 12 in alg. 3, if only for ensuring DP, I think it is not necessary.\n\nMaybe due to the nature of SEP, having to pick one data point at one time to do updates, making the algorithm not scalable to large datasets, in contrast, DP-SGD samples a batch of data to do learning, I am wondering if there is a way to circumvent such a challenge\n", "broader_impact_concerns": "None", "additional_comments": "", "extra_scores": {}, "extra_text": {}}, {"review_id": "cgyxVmvE09", "reviewer": "Reviewer_X32H", "summary": "", "questions": "", "limitations": "", "rating": null, "confidence": null, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "\n\nStrengths:\n\n- Novel idea: DP Stochastic Expectation Propagation does not seem to be considered before.\n- Strong experimental evidence, seems to improve upon the results of DP variational inference (Jälkö et al., 2017) and DP expectation maximization (Park et al., 2017).\n\nWeaknesses:\n\n- Clearly the biggest weakness: I think there are issues with the theory part, that part requires corrections. In more detail below:\n\nI have some difficulties reading the theoretical error bound: what is for example $\\sigma_2$ ? If I understand correctly $v(E)$ is of the order $O(d^2)$, and since there is already $d \\log d$ in the last term, the error bound is $O(d^2 log d)$ which sounds quite a lot.\n\nI cannot follow the reasoning with the decomposition of Def. 4.2, I believe it is not mathematically correct: I think you cannot necessarily shift the spectrum of a Hermitian matrix by adding a diagonal matrix as you describe. Now clearly $\\Lambda_q + E$ is Hermitian. Adding a diagonal A as you describe does not necessarily make the matrix non-negative, I think you should have the correct eigenbasis there as well (corresponding to that of $\\Lambda_q + E$).\n\nIn any case: even if you would use some correction matrix this way, you should somehow bound it to have 'a priori' error bound. Now the matrix A appears in the error bound, and since it is 'a posteriori' information the error bound is 'a posteriori' bound that you evaluate after running the algorithm. And due to the pessimistic dependence on dimension, I suspect it would quickly become useless as dimension d grows.\n\nTheorem 4.1 is \"privacy-accuracy trade-off\" bound. But where is the privacy, how is the level of privacy reflected by the bound?\n\nYou write: \"We look forward to extending our private SEP to more large-scale scenarios such as federated learning settings...\" Does large-scale mean high-dimensional as well? I have doubts, whether the approach would work as well in higher dimensions. Isn't this indicated by your KL-divergence error bound as well ( $O(d^2 log d)$ ) ?\n\nAs there does not seem to be prior work on DP expectation propagation or stochastic expectation propagation, and since otherwise (other than the theoretical analysis) I have no reason to doubt the correctness of the paper, I think the paper meets most of the criteria for publication. However the theoretical part should be corrected.\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "paper_topic_and_main_contributions": "", "excitement": null, "reproducibility": null, "ethical_concerns": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "summary_of_contributions": "The proposes a  DP Stochastic Expectation Propagation algorithm for computing a posterior distribution for model parameters in Bayesian learning. There are two existing approaches: DP variational inference (Jälkö et al., 2017) and DP expectation maximization (Park et al., 2017). The experiments indicate that the proposed method often improves upon the baseline methods. A theoretical analysis in terms of KL-distance from the posterior given by the non-DP algorithm is carried out.", "claims_and_evidence_yn": "", "claims_explanation": "", "audience_yn": "", "audience_explanation": "", "requested_changes": "I think the theory part should be reworked carefully (see the comments above). Even if the resulting bound is pessimistic or not even 'a priori' bound (containing some a posteriori quantities), it should be correct. I cannot see how it would be correct now with that diagonal correction matrix A. Thus I would say that the paper requires a major revision.", "broader_impact_concerns": "I have no concerns of ethical implications.", "additional_comments": "", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: The paper improved substantially during the reviewing process and all reviewers are happy with the updated version of the paper. The main remaining criticism is that there isn't an end-to-end utility analysis. I decided that since most Bayesian approaches, even without privacy guarantees, do not have a theoretical performance guarantee, it is acceptable that the current paper evaluates their methods empirically. All reviewers agree that the empirical results are of high quality. Moreover, the new approach for private Bayesian learning (returning an approximate posterior distribution) gives good utility at reasonable DP parameters.

That said, if the authors could still somehow analyze the approximation of the private posterior distribution vs its non-private counterpart (notice that this does not require the non-private version of the algorithm to have theoretical guarantees), it would increase the technical contribution of the work. This could be left as a future work if the authors find it on-trivial to state and prove a utility guarantee of this kind.

The authors should incorporate the reviewer's suggestions and the paper is ready to publish (without having another round of reviews).

Congratulations to the authors!
Decision: Accept (poster)