Private Release of Text Embedding Vectors (2021)

Abstract: Ensuring strong theoretical privacy guarantees on text data is a challenging problem which is usually attained at the expense of utility. However, to improve the practicality of privacy preserving text analyses, it is essential to design algorithms that better optimize this tradeoff. To address this challenge, we propose a release mechanism that takes any (text) embedding vector as input and releases a corresponding private vector. The mechanism satisfies an extension of differential privacy to metric spaces. Our idea based on first randomly projecting the vectors to a lower-dimensional space and then adding noise in this projected space generates private vectors that achieve strong theoretical guarantees on its utility. We support our theoretical proofs with empirical experiments on multiple word embedding models and NLP datasets, achieving in some cases more than 10% gains over the existing state-of-the-art privatization techniques.

## introduction privacy has emerged as a topic of strategic consequence across all computational fields. differential privacy (dp) is a mathematical definition of privacy proposed by @xcite . ever since its introduction, dp has been widely adopted and as of today, it has become the de facto privacy definition in the academic world with also wide adoption in industry, e.g., @xcite @xcite . dp provides provable protection against adversaries with arbitrary side information and computational power, allows clear quantification of privacy losses, and satisfies graceful composition over multiple access to the same data. in dp, two parameters and δ control the level of privacy. very roughly, is an upper bound on the amount of influence a single data point has on the information released and δ is the probability that this bound fails to hold, so the definition becomes more stringent as , δ → 0. the definition with δ = 0 is referred to as pure differential privacy, and with δ > 0 is referred to as approximate differential privacy. within the field of natural language processing (nlp), the traditional approach for privacy was to apply anonymization techniques such as kanonymity @xcite and its variants. while this offers an intuitive way of expressing privacy guarantees as a function of an aggregation parameter k, all such methods are provably non-private @xcite . given the sheer increase in data gathering occurring across a multiplicity of connected platforms -a great number of which is being done via user generated voice conversations, text queries, or other language based metadata (e.g., user annotations), it is imperative to advance the development of dp techniques in nlp. vector embeddings are a popular approach for capturing the "meaning" of text and a form of unsupervised learning useful for downstream tasks. word embeddings were popularized via embedding schemes such as word2vec @xcite , glove @xcite , and fast-text @xcite . there is also a growing literature on creating embeddings for sentences, documents, and other textual entities, in addition to embeddings in other domains such as in computer vision @xcite . recent works such as @xcite @xcite have attempted to directly adapt the methods of dp to word embeddings by borrowing ideas from the privacy methods used for map location data @xcite . in the dp literature, one standard way of achieving privacy is by adding properly calibrated noise to the output of a function @xcite . this is also the premise behind these previously proposed dp for text techniques, which are based on adding noise to the vector representation of words in a high dimensional embedding space and additional post-processing steps. the privacy guarantees of applying such a method is quite straightforward. however, the main issue is that the magnitude of the dp privacy noise scales with dimensionality of the vector, which leads to a considerable degradation to the utility when these techniques are applied to vectors produced through popular embedding techniques. in this paper, we seek to overcome this curse of dimensionality arising through the differential privacy requirement. also unlike previous results which were focused on word embeddings, we focus on the general problem of privately releasing vector embeddings, thus making our scheme more widely applicable. ## preliminaries we denote [n] = {1, . . . , n}. vectors are in column-wise fashion. we measure the distance between embeddings through the euclidean metric. for a vector x, we set x to denote the euclidean (l 2 -) norm and x 1 denotes its l 1 -norm. for sets s, t , the minkowski sum s + @xmath0: @xmath1, @xmath2. n (0, σ 2 ) denotes the gaussian distribution with mean 0 and variance σ 2 . ## our approach the main issue arising in constructing differentially private vector embeddings is that a direct noise addition to the vectors (such as in (feyisetan et al., 2020)) would require that the l 2 -norm of the noise vector scales almost linearly with the dimensionality of the vector. to overcome this dimension dependence, our mechanism is based on the idea of performing a dimensionality reduction and then adding noise to the projected vector. by carefully balancing the dimensionality of the vectors with the magnitude of the noise needed for dp, the mechanism achieves a superior performance overall. we will add noise calibrated to the sensitivity of the dimensionality reduction function. the noise is sampled from a d-dimensional distribution with density p(z) ∝ exp(-z /∆ f ). sampling from this distribution is simple as noted in @xcite . 1 . the following simple claim (that holds for all functions f ) shows that this mechanism satisfies definition 1. all the missing proofs from this section are collected in appendix c. let φ be an m × d matrix with i.i.d. entries from n (0, 1/m). consider an embedding model m . let dom(m ) denote the domain and ran(m ) ⊂ r d denote the range of m . define a function let us first investigate the global sensitivity of f φ using theorem 1. instead of considering a fixed bound on global sensitivity, we provide a probabilistic upper bound. lemma 4. let φ be an m × d matrix with i.i.d. entries from n (0, 1/m). let β ∈ (0, 1). if @xmath3, then with probability, at least 1 -δ, ∆ f φ ≤ 1 + β. let β ∈ (0, 1) be a fixed constant. consider the mechanism which publishes a(x) = f φ (x) + κ where κ is drawn from the distribution with density p(z) ∝ exp(-z /(1 + β)). given a set of sensitive words (x 1 , . . . , x n ), we can apply a(x i ) to each word x i , to release a(x 1 ), . . . , a(x n ) ∈ r m . algorithm privemb summarizes the mechanism. since each vector is perturbed independently, the algorithm can be invoked locally. we now establish the privacy guarantee of privemb. the δ factor comes in from lemma 4 because we only have a probabilistic bound on the global sensitivity, i.e., there exists pairs of x, x for whom the bound on global sensitivity of 1 + β could fail. for example, imagine a situation where there are n users each having a sensitive word (embedding). given access to a common φ, they can perturb their word locally and transmit only the perturbed vector. algorithm 1: privemb input: x1, . . . , @xmath4, privacy parameters , δ > 0, and dimensionality reduction parameter β ∈ (0, 1) output: private vector embeddings w1, . . . , wn using claim 3 and lemma 4, we now establish that privacy proof for algorithm privemb. proposition 5. algorithm privemb is ( , δ)-lipschitz private. let β ∈ (0, 1), δ > 0, > 0, and @xmath5. let φ be an m × d matrix with i.i.d. entries from n (0, 1/m). then publishing a(x) = f φ (x) + κ where κ is drawn from the distribution in r m with density p(z) ∝ exp(-z /(1 + β)) is ( , δ)-lipschitz private. it is important to note that the β does not affect the privacy analysis, i.e., for any input parameter β, algorithm privemb is ( , δ)-lipschitz private. while the idea behind algorithm privemb is simple, it is widely applicable and effective. as an example consider vector representation of text such as through bag-of-k-grams, which creates representations that are sparse in some very highdimensional space (say c-sparse vectors). in this case, even though d could be extremely large, we can project these vectors to ≈ c log(d/c)dimensional space (due to their low gaussian width) and add noise in the projected space for achieving privacy. on the other hand, the privacy mechanism of @xcite , with noise magnitude proportional to d will completely destroy the information in these vectors. ## utility analysis of alg. privemb we now provide utility performance bounds for algorithm privemb. as mentioned earlier these are the first theoretical analysis for any private vector embedding scheme. we start with two important properties of interest based on distances and innerproducts that commonly arise when dealing with text embeddings. our next result compares the loss of a linear model trained on these private vector embeddings to loss of a similar model trained on the original vector embeddings. all our error bounds depend on m ≈ ω(ran(m )) 2 . we start with a simple observation about the magnitude of the noise vector. consider κ drawn from the noise distribution with density p(z) ∝ exp(-z /(1 + β)). the euclidean norm of κ is distributed according to the gamma distribution γ(m, (1 + β)/ ) @xcite and satisfies the following bound. claim 6 ( @xcite ). for the noise vector κ, we have that with probability at least 1 -γ, κ ≤ (m ln(m/γ)(1 + β))/ . since β < 1, we can simplify the right hand side of the above claim to (2m ln(m/γ))/ . let τ be the maximum euclidean norm of the vectors x 1 , . . . , x n , i.e., ∀@xmath6, x @xmath7. ## experimental evaluations we carry out four experiments to demonstrate the improvement of our approach (algorithm privemb), denoted as m2, over ( , 0)-lipschitz privacy mechanism proposed in (feyisetan et al., 2020) (denoted by m1). 2 the first three map to the theoretical guarantees described section 4, i.e., (1) distance approximation guarantee, (2) inner-product approximation guarantee, and (3) performance on linear models. the final experiment provides further evidence for performance of using these private vectors for downstream classification tasks. all our experiments are on embeddings generated by glove @xcite and fasttext @xcite . the dimensionality of the embedding @xmath8. due to space constraints, we present the fasttext results in appendix b. the value of δ is kept constant for all experiments (involving our scheme) at 1e -6. we set ω(ran(m )) = √ log d. the parameter β only affects the utility guarantee, and algorithm privemb is always ( , δ)-lipschitz private for any value of β. in our experiments, corroborating our theoretical guarantees, we do vary β to illustrate the effect of β on the guarantees. remember that higher values of β results in lowerdimensional vectors, so setting β appropriately lets one trade-off between the loss of utility due to dimension reduction vs. the gain in the utility due to lesser noise needed for lower-dimensional vectors. we also vary the privacy parameter in our experiments. while lower values are certainly desirable, it is widely known that differentially private algorithms for certain problems (such as those arising in complex domains such as nlp) require slightly larger values to provide reasonable utility in practice @xcite @xcite . for example, the related work on differential privately releasing text embeddings from fernandes et al. @xcite and feyisetan et al. @xcite report values of of up to 20 and 30 depending on the dimensionality of the space. ## concluding remarks in this paper, we introduced an ( , δ)-lipschitz private algorithm for generating real valued embedding vectors. our mechanism works by first reducing the dimensionality of the vectors though a random projection, then adding noise calibrated to the sensitivity of the dimensionality reduction function. the mechanism can be utilized for any welldefined embedding model including but not limited to word, sentence, and document embeddings. we prove theoretical bounds that show how various properties of interest important for vector embeddings are well-approximated through the private vectors, and our empirical results across multiple embedding models and nlp datasets demonstrate the superior utility guarantees.