Variational Bayes in Private Settings (VIPS) (Extended Abstract)

1 Introduction

Bayesian inference, which reasons over the uncertainty in model parameters and latent variables given data and prior knowledge, has found widespread use in data science application domains in which privacy is essential, including text analysis [Blei et al., 2003], medical informatics [Husmeier et al., 2006], and MOOCS [Piech et al., 2013]. In these applications, the goals of the analysis must be carefully balanced against the privacy concerns of the individuals whose data are being studied [Daries et al., 2014]. The Differential Privacy (DP) formalism provides a means for analyzing and controlling this trade-off, by quantifying the privacy "cost" of datadriven algorithms [Dwork et al., 2006b]. In this work, we address the challenge of performing Bayesian inference in private settings, by developing an extension of the widely used Variational Bayes (VB) algorithm that preserves differential privacy. Variational Bayes provides an optimisation-based alternative to Markov Chain Monte Carlo (MCMC) simulation methods for Bayesian inference, and as such, frequently has faster convergence properties than MCMC.

∗This paper is an extended abstract of an article in JAIR [Park et al., 2020].

†The first two authors contributed equally.

‡Contact Author.

Iterative algorithms, such as variational Bayes, pose a further challenge when developing a differentially private algorithm: each iteration corresponds to a query to the database which must be privatised, and the number of iterations required to guarantee accurate posterior estimates causes high cumulative privacy loss. To compensate for the loss, one needs to add a significantly higher level of noise to the quantity of interest. We overcome these challenges in the context of variational Bayes by using the following key ideas:

• perturbation of the expected sufficient statistics to make effective use of the per iteration privacy budget,
• a refined composition analysis using the Moments Accountant to increase the per-iteration privacy budget,
• leveraging the privacy amplification effect from subsampling of large-scale data to scale up the algorithm while improving privacy guarantees, and
• data augmentation for non-CE family models to generalize our approach to a broad class of models, which we describe in the full journal paper.

Taken together, these ideas result in an algorithm for privacy-preserving variational Bayesian inference that is both practical and broadly applicable. Our code is available at https://github.com/mijungi/vips code.

2 Background

Differential Privacy (DP) is a formal definition of the privacy properties of data analysis algorithms [Dwork et al., 2006b; Dwork and Roth, 2014]. A randomized algorithmM(D) is said to be (ϵ, δ)-differentially private if

for all measurable subsets S of the range of M and for all datasets D, D′ differing by a single entry. In this paper, we assume that the entry difference incurs by replacing an entry with a different value (the "replace-one" version of DP).

Intuitively, the definition states that the probability of any event does not change very much when a single individual's data is modified, thereby limiting the amount of information that the algorithm reveals about any one individual. There are several standard approaches for designing differentiallyprivate algorithms - see [Dwork and Roth, 2014] and [Sarwate and Chaudhuri, 2013] for surveys. The classical approach is the global sensitivity method by [Dwork et al., 2006b]. The global sensitivity of a function F of a dataset D is defined as the maximum amount (over all datasets D) by which F changes when the private value of a single individual in D changes: ∆F = maxD,D′ : d(D,D′ )≤1 |F(D) - F(D′ )|, where D is allowed to vary over the entire data domain, and |F(·)| can correspond to either the L1 norm ‖F(·)‖1 or the L2 norm ‖F(·)‖2. In this paper, we consider a specific form of the global sensitivity method, called the Gaussian mechanism [Dwork et al., 2006a], where Gaussian noise calibrated to the global sensitivity in the L2 norm (the L2 sensitivity) is added. For a function F with global sensitivity ∆F, we output:

2.1 Composition and Subsampling

An important property of differential privacy which makes it conducive to real applications is composition, which means that the privacy guarantees decay gracefully as the same private dataset is used in multiple releases. This property allows us to easily design private versions of iterative algorithms by making each iteration private, and then accounting for the privacy loss incurred by a fixed number of iterations.

The key privacy tool in this paper is the composition of multiple iterations of the Subsampled Gaussian Mechanism, originally analyzed by [Abadi et al., 2016], and refined by [Wang et al., 2019] (the Analytical Moments Accountant). The Subsampled Gaussian Mechanism, under the analysis of [Wang et al., 2019], works as follows. Given a dataset D with N datapoints and a sampling proportion υ, in each iteration, we draw a fresh independent random sample of υN points from the entire dataset D. These υN points are drawn without replacement and are hence distinct. We then compute a function F (to be specified later) on these υN points, and privatize F using the Gaussian mechanism. The Moments Accountant keeps track of privacy loss under composition based on a quantity called the log-moment function. Theorem 9 of [Wang et al., 2019] provides an analytical expression for computing the log-moment of the Subsampled Gaussian Mechanism as a function of the sampling proportion, and the log-moments of the Gaussian Mechanism. Since all log-moments of the Gaussian Mechanism can be calculated directly by simple algebra [Abadi et al., 2016; Wang et al., 2019], this gives an analytical way to calculate the log-moment of a single iteration of the Subsampled Gaussian Mechanism. Successive iterations are then composed by adding up the log-moments.

2.2 Variational Bayes

Consider a generative model that produces a dataset D = {Dn}Nn=1 consisting of N (conditionally) independent identically distributed (i.i.d.) items (Dn denotes the nth input/output pair {xn, yn} for supervised learning and the nth Algorithm 1 (Stochastic) Variational Bayes for CE family distributions Input: Data D. Define ρt = (τ0 + t)-κ and mini-batch size S.

Output: Expected natural parameters ¯n and expected sufficient statistics ¯s.

Draw a minibatch of S datapoints, without replacement.

(1) E-step: Given the expected natural parameters ¯n, compute q(ln) for n = 1, . . . , S. Output the expected sufficient statistics ¯s = 1S ∑Sn=1 〈s(Dn, ln)〉q(ln).

(2) M-step: Given ¯s, compute q(m) by ˜ ν (t) = ν +N¯s. Set ˜ ν (t) ←[(1-ρt)˜ ν (t-1) +ρt ˜ ν (t) . Output the expected natural parameters ¯n = 〈n(m)〉q(m).

end for

vector output yn for unsupervised learning), generated using a set of latent variables l = {ln}Nn=1 . The generative model provides p(Dn|ln,m), where m are the model parameters. Variational Bayes recasts the task of approximating the posterior p(l ,m|D) as an optimisation problem: making an approximating distribution q(l ,m), which is called the variational distribution, as similar as possible to the posterior, by minimising some distance (or divergence) between them, typically the KL-divergence. The standard mean field assumption is that q is a fully factorized distribution, q(l ,m) = q(l)q(m) = q(m) ∏Nn=1 q(ln). Mean-field VB simplifies to a two-step procedure when the model falls in the Conjugate-Exponential (CE) class of models [Beal, 2003]:

1. The complete-data likelihood is in the exponential family:

1. The prior on model parameters m is conjugate to the complete-data likelihood:

where the natural parameters (to be inferred) and sufficient statistics (a function of the data and the latent variables to be inferred) of the complete-data likelihood are denoted by n(m) and s(Dn, ln), respectively, and g, f, h are some known functions. The hyperparameters (that need to be tuned) are denoted by τ (a scalar) and ν (a vector).

For more efficient learning, we adopt stochastic variational inference, which uses stochastic optimisation to fit the variational distribution over the parameters. The stochastic variational Bayes algorithm is summarised in Algorithm 1.

3 Variational Bayes In Private Settings (VIPS) for the CE Family

A naive way to privatise the VB algorithm is by perturbing both q(l) and q(m). Unfortunately, this is impractical, due to the excessive amounts of additive noise (we typically have as many latent variables as the number of datapoints). We instead propose to perturb the expected sufficient statistics

Algorithm 2 Private VIPS for CE family distributions

Input: Data D. Define ρt = (τ0 + t)-κ , noise variance σ2 , mini-batch size S, and maximum iterations J.

Output: Perturb expected natural parameters ˜¯n and expected sufficient statistics ˜¯s.

Compute the L2-sensitivity ∆ of the expected sufficient statistics.

for t = 1, . . . , J do

Draw a minibatch of S datapoints, without replacement.

(1) E-step: Given the expected natural parameters ¯n, compute q(ln) for n = 1, . . . , S. Perturb each coordinate of ¯s = 1S ∑Sn=1 〈s(Dn, ln)〉q(ln) by adding N(0, σ2∆2 I) noise, and output ˜¯s.

(2) M-step: Given ˜¯s, compute q(m) by ˜ ν (t) = ν + N˜¯s. Set ˜ ν (t) ←[(1-ρt)˜ ν (t-1) +ρt ˜ ν (t) . Output the expected natural parameters ˜¯n = 〈n(m)〉q(m).

end for

Compute the privacy loss (ϵtot, δtot) using the analytical moments account method [Wang et al., 2019].

only. We provide a schematic of our overall procedure for Variational Bayes in private settings (VIPS) in Fig. 1.

Algorithm 2 provides pseudocode of our algorithm for differentially private stochastic variational Bayes for CE family models. In the full paper we develop a method to address the non-CE family case, which we apply to Bayesian logistic regression and sigmoid belief networks.

4 VIPS for Latent Dirichlet Allocation

In the LDA topic model, we observe a corpus of D documents Dd, where each observed word is represented by an indicator vector wdn (nth word in the dth document) of length V , and where V is the number of terms in a fixed vocabulary set. Given the corpus, the model infers K latent topics βk, which are discrete distributions over the vocabulary, and discrete distributions over topics θd for each document Dd. Each word wdn is given a topic assignment latent variable zdn, represented by an indicator vector of length K. Let 1L be a vector of ones of length L, for any integer L. The LDA model posits that the generative process for the corpus is:

• Draw topics βk ∼Dirichlet (η1V ), for k = {1, . . . ,K}, where η is a scalar hyperparameter.
• For each document Dd, d ∈ {1, . . . ,D}
• Draw topic proportions θd ∼ Dirichlet (α1K), where α is a scalar hyperparameter.
• For each word n ∈ {1, . . . ,N}
• ∗ Draw topic assignments zdn ∼ Discrete(θd)
• ∗ Drawword wdn ∼Discrete(βzdn ) .

The LDA model falls in the CE family, viewing zd,1:N and θd as two types of latent variables: ld = {zd,1:N, θd}, and β as model parameters m = β. We follow the general framework of VIPS for differentially private LDA, with the addition of several LDA-specific heuristics which are important for good performance. First, while each document originally has a different document length Nd, in order to bound the sensitivity, and to ensure that the signal-to-noise ratio remains reasonable for very short documents, we preprocess all documents to have the same fixed length N. We accomplish this by sampling N words with replacement from each document's bag of words. In our experiments, we use N = 500. Note that since privacy is preserved at the level of documents rather than at the level of words, this step does not directly impact the degree of privacy achieved, but it can reduce the relative amount of noise compared to the amount of data.

To perturb the expected sufficient statistics ¯s, which is a matrix of size K ×V , we add Gaussian noise to each component of this matrix:

¯svk = 1S ∑d ∑n φkdnwvdn , and ∆¯s is the sensitivity. We then map the perturbed components to 0 if they become negative. For LDA, with a mini-batch of S documents we show with simple algebra that the the worst-case sensitivity is given by

In our practical implementation, we improve the sensitivity by exploiting the fact that for most typical documents, the document's contribution's norm |¯sd | will be smaller than the worst case norm NS . Specifically, inspired by [Abadi et al., 2016], we apply a norm clipping strategy, in which the perdocument contributions ¯sd are clipped (or projected) such that |¯sd | ≤ a NS , for a user-specified a ∈ (0, 1]. Note that when a = 1, no clipping is applied. For each document in the minibatch, if this criterion is not satisfied, we project the expected sufficient statistics ¯sd down to the required norm via

For example, consider a scenario where N = V = K = 2, S = 1, a = 0.1, and ¯sd = [1 0 1 0]. The worst-case norm is NS = 2, the clipping threshold is calculated as a NS = 0.2, and the norm of ¯sd is |¯sd | = √2 ≈ 1.41 > 0.2. The document's expected sufficient statistics hence are clipped to

These clipped sufficient statistics have a norm of |¯sd | = 0.2, as required. Intuitively, for a fixed N and S, the L1 norm of ¯sd is always N/S, but its L2 norm can become arbitrarily small as the dimensionality of ¯sd increases. After this procedure, the sensitivity of the clipped expected sufficient statistics matrix becomes a∆¯s (i.e., a NS ), and we add noise on this scale to the clipped expected sufficient statistics. We set a = 0.1 in our experiments, which empirically resulted in clipping being applied to around 3/4 of the documents, while improving the sensitivity by an order of magnitude.

4.1 Experiments usingWikipedia Data

We downloaded a random D = 400, 000 documents from Wikipedia to test our VIPS algorithm. We used 50 topics and a vocabulary set of approximately 8000 terms. The algorithm was run for one epoch in each experiment. We compared our moments accountant approach with a baseline method using the strong composition (Theorem 3.20 of [Dwork and Roth, 2014]) and a baseline where the clipping step was not performed. Figure 2 shows the trade-off between ϵ and per-word perplexity on the Wikipedia dataset for the different methods under a variety of conditions. Our proposed method outperformed the baselines. In Table 1 we show the top 10 words in terms of assigned probabilities for an example topic.

5 Conclusion

We have developed a practical privacy-preserving VB algorithm and illustrated its performance for topic modeling. In the full paper, we generalize our approach to non-CE models, including Bayesian logistic regression and sigmoid belief networks. Our broader vision is that practical private ML algorithms will have a transformative impact on the practice of data science in many real-world applications.

Acknowledgments

M. Park and J. Foulds contributed equally. A significant amount of work of M. Park and M. Welling was supported by the QUVA lab at the University of Amsterdam. The later work of M. Park was supported by the Max Planck Society, as well as the Gibs Sch¨ule Foundation and the Institutional Strategy of the University of T¨ubingen (ZUK63). K. Chaudhuri was partially supported by ONR under N0001416-1-261, UC Lab Fees under LFR 18-548554 and a Google Faculty Fellowship.