Private Language Models via Truncated Laplacian Mechanism (2024)

Abstract: Recently it has been shown that deep learning models for NLP tasks are prone to attacks that can even reconstruct the verbatim training texts. To prevent privacy leakage, researchers have investigated word-level perturbations, relying on the formal guarantees of differential privacy (DP) in the embedding space. However, many existing approaches either achieve unsatisfactory performance in the high privacy regime when using the Laplacian or Gaussian mechanism, or resort to weaker relaxations of DP that are inferior to the canonical DP in terms of privacy strength. This raises the question of whether a new method for private word embedding can be designed to overcome these limitations. In this paper, we propose a novel private embedding method called the high dimensional truncated Laplacian mechanism. Specifically, we introduce a non-trivial extension of the truncated Laplacian mechanism, which was previously only investigated in one-dimensional space cases. Theoretically, we show that our method has a lower variance compared to the previous private word embedding methods. To further validate its effectiveness, we conduct comprehensive experiments on private embedding and downstream tasks using three datasets. Remarkably, even in the high privacy regime, our approach only incurs a slight decrease in utility compared to the non-private scenario.

## introduction the recent developments of deep learning have led to significant success in various tasks in natural language processing (nlp), from next word prediction in mobile keyboards @xcite , to critical tasks like predicting patient health conditions from clinical records @xcite . however, such applications may always involve user-generated textual data as the training dataset, which contains sensitive information. to address privacy concerns, text anonymization @xcite has been commonly used, which involves identifying sensitive attributes and replacing them with alternative values. nevertheless, such heuristic approaches become ineffective as deep neural networks often tend to memorize training data, making them susceptible to information leakage about the training data @xcite @xcite . one way that takes into account the limitations of existing approaches is designing differentially private (dp) algorithms. differential privacy @xcite is resilient to arbitrary side information that might be available to attackers and has become a de facto method for private data analysis @xcite @xcite @xcite @xcite @xcite . recently, there has been significant research focusing on differentially private (dp) versions of word embedding from various perspectives @xcite @xcite @xcite @xcite . however, there are still some shortcomings in these approaches. on the one hand, several works consider adding laplacian or gaussian noise to the embedding space to ensure dp @xcite @xcite . however, these mechanisms suffer from high noise levels, resulting in low utility, especially in the high privacy regime when the privacy parameter (ϵ) is small. moreover, these mechanisms can even alter the semantics of sentences (see fig. 1 ). on the other hand, there is a growing body of work that focuses on a relaxation of the canonical definition of dp, known as metric dp, which can achieve better performance. however, as a relaxed notion of dp, metric dp cannot provide the same level of strong privacy guarantees as the canonical dp (mattern ## related work recent years have seen substantial advancements in language models within differential privacy (dp) frameworks. due to the space limit, here we only mention the existing literature on private word embedding. we refer the readers to the survey @xcite for more details. current research on private word embeddings can be broadly categorized into two approaches: original dp-based methods and metric dp-based methods. the seminal work in the original dp category by @xcite introduces a framework utilizing the unary encoding mechanism. this approach was subsequently refined by @xcite . further improvements were made by @xcite , who proposed a dropout technique for perturbed embeddings to enhance downstream task fairness. however, @xcite identify a critical privacy issue in @xcite , noting that it requires access to users' raw data for fine-tuning during the training phase. other notable contributions include works by @xcite , @xcite , and @xcite , who explore privatizing word embeddings. @xcite and @xcite propose adept, an auto-encoder-based dp algorithm. unfortunately, @xcite points out that adept is not differentially private by thorough theoretical proof. @xcite address reproducibility by providing source code for dp auto-encoder methods. in this paper, we aim to improve the performance of the mechanisms in @xcite . in the realm of metric dp, @xcite first study this problem and provide a general perturbation-and-projection framework. xu et al. (2020a) reconsider this problem setting, replacing the euclidean distance with the mahalanobis distance to improve the utility. subsequently, xu et al. (2021d) introduce the vickrey mechanism to further refine the utility in the projection step. to address the limitations of the multivariate laplace mechanism, xu et al. (2021b) and carvalho et al. (2021c) propose a truncated gumbel noise method. feyisetan and kasiviswanathan (2021) tackle high-dimensionality issues using random projection. additionally, feyisetan et al. (2019) define hyperbolic embeddings and utilize the metropolis-hastings algorithm for sampling from hyperbolic distributions. more recently, tang et al. (2020) explore differential privacy with varying privacy levels for different words. arnold et al. (2023a) introduce sense embeddings with a sense disambiguation step prior to noise injection, and arnold et al. (2023b) address common semantic context issues in prior private embedding mechanisms. it is crucial to clarify that the objective of this work is the privatization of embedded outputs rather than the embedded methods themselves. the pre-trained initial embedding methods and the corresponding embeddings of all words in the vocabulary are treated as public knowledge. this distinction is significant because it allows us to perform projections without incurring additional privacy costs. by leveraging publicly available pretrained embeddings, our method demonstrates how effective privacy-preserving techniques can be implemented while still utilizing existing resources. ## preliminaries differential privacy is a data post-processing technique designed to ensure data privacy by adding confusion to potential attackers. specifically, suppose there is one dataset noted as d, and we change or delete one data record in this dataset which we call d ′ . if the output distributions of d and d ′ are close enough, then we cannot distinguish these two distributions, i.e., we cannot infer whether the deleted or replaced data sample is really in this dataset. the formal details are given by @xcite . note that in the definition of dp, adjacency is a key notion. one of the commonly used adjacency definitions is that two datasets s and s ′ are adjacent (denoted as s ∼ s ′ ) if s ′ can be obtained by modifying one record in s. definition 1 given a domain of dataset x . a randomized algorithm a : @xmath0, δ)differentially private (dp) if for all adjacent datasets s, s ′ with each sample is in x and for all t ⊆ r, the following holds when δ = 0, we call the algorithm a is ε-dp. in this work, we adopt a similar setting to previous research on private word embedding @xcite @xcite . we consider a scenario where a user inputs a word w from a discrete fixed vocabulary w. our goal is to preserve the user's privacy with respect to her/his word. to achieve this goal, we aim to design an algorithm that accepts w as input and whose distribution of output is close to the case where w ′ ∈ w is the input, with w ′ ̸ = w is any other word. from the attacker's perspective, based on the output, he cannot distinguish whether the user's input word is w or w ′ as their output distributions are almost the same. formally, we have the following definition. definition 2 given a discrete vocabulary w, a randomized algorithm a : @xmath1, δ)-differentially private (dp) if for all pair of words w, w ′ ∈ w and for all t ⊆ r we have p(a(w) ∈ t ) ≤ e ϵ p(a(w ′ ) ∈ t ) + δ. when δ = 0, we call the algorithm a is ϵ-dp. in this paper, we assume the user holds a sentence @xmath2. and we aim to design an (ϵ, δ)-dp algorithm, which is private w.r.t. each word w i . ## private embedding via truncated laplacian mechanism in this section, we will provide details of our method. generally speaking, for each token w i , to achieve dp, our approach consists of three steps. first, each token w i is mapped to an d-dimensional pre-trained word embedding ϕ(w i ). and we perform a clipping step to get a clipped embedding: in the second step, we add some random noise to the clipped embedding vector to make it satisfies dp. finally, we will perform the projection step by finding the nearest word ŵi to the perturbed and clipped embedding vector within the embedding space: it is notable that the goal of clipping is to make the ℓ 2 -norm of embedding vector be bounded so that we can adding noise to ensure dp, such as the laplacian mechanism or gaussian mechanism @xcite . theorem 1 (laplacian mechanism) suppose clipemb(w) ∈ r d denote the clipped embedding vector with threshold c. then the mechanism ## theoretical sensitivity analysis in the last section, we introduce our truncated laplacian mechanism, we will analyze its sensitivity and proof our claim in this section. theorem 3 suppose clipemb(w) ∈ r d is the clipped embedding vector with threshold c. define and each η i has the density function as in (3) with the above parameters. in the following, we will show our mechanism has lower variance than the laplacian and gaussian mechanism, which indicates that our method is superior theoretically. ## experiments in this section, we conduct experiments for our method based on two parts: dp text re-write for fine-tuning (private embedding) and downstream tasks (sentiment analysis). we have open-sourced our code on https://github.com/ kaustpradalab/trlap . ## conclusions we introduce a novel method called the high dimensional truncated laplacian mechanism for private embedding, which extends the one-dimensional case to the high-dimensional case. theoretical analysis demonstrates that our method exhibits lower variance compared to existing private word embedding techniques. experiments show that even in the high privacy regime, our approach incurs only a minimal loss in utility compared to the non-private case, which maintains privacy while preserving the quality of embeddings for promising performance.