Differentially Private Correlation Alignment for Domain Adaptation

1 Introduction

Supervised machine learning will encounter poor generalization performance with limited labeled data, while manual labeling of sufficient training data for emerging application domains is labor-intensive and time-consuming. This motivates the development of domain adaptation, a technique that aims to transfer a model from a source domain where sufficient training data are available to a target domain where few or no labeled data are available.

In many settings, the source and target domains do not want to share the raw data or statistics due to privacy concerns. For example, the source and target domains may come from two different medical institutions who hold medical records related to certain types of drugs or procedures. In order to perform domain adaptation without privacy leakage, we adopt the notion of differential privacy [Dwork et al., 2006b], which provides strict and verifiable privacy guarantees, and makes almost no assumptions about the attacker's background knowledge. Recently, LeTien et al. [LeTien et al., 2019] proposed a differentially private optimal transport model for privacy-preserving domain adaptation. However, optimal transport relies on two restrictive assumptions, which are: 1) the target samples are an affine transformation of the source samples; 2) the source and target domains have shared features.

∗Corresponding Author

In contrast to optimal transport which exploits only shared features, correlation alignment [Sun et al., 2016] can use both shared and domain specific features by capturing the feature correlations of source and target domains, which is particularly crucial when the two domains contain few or even no shared features. What's more, compared with the recent deep adaptation approaches [Long et al., 2015; Ganin et al., 2016] which are quite complex and expensive, requiring tuning of many hyperparameters, correlation alignment is more efficient and can achieve better or comparable performance. Without requiring any target labels, correlation alignment first transforms the source distribution to as close as possible to the target one by utilizing the covariance matrix of the target domain. Then a model trained on the transformed source data is applied to the target data. Clearly, the covariance matrix of the target domain utilized by the source domain may leak sensitive information of the target data [Dwork et al., 2014]. Moreover, the model applied by target domain may leak sensitive information of the source data [Abadi et al., 2016].

In this paper, we start from a straightforward approach, which can provide privacy guarantee for correlation alignment based domain adaptation, and allow both the source and target domains to perform domain adaptation without trusting each other. Specifically, to obtain a private covariance matrix of the target domain, we perturb the real covariance matrix by Gaussian noise [Dwork et al., 2014; Ge et al., 2018]. In addition, to obtain a private model, we perturb gradients by Gaussian noise during the gradient based model training [Bassily et al., 2014; Abadi et al.,

2016]. However, such a straightforward approach has two limitations: 1) the upper error bound of the perturbed covariance matrix grows linearly with the dimension [Wang and Xu, 2019], which makes the straightforward approach suffer from poor performance in high-dimensional setting; 2) it is not clear whether the covariance matrix can keep positive semi-definiteness when it is perturbed, a property that is normally expected from a classifier. To address these limitations of the straightforward approach, we propose our differentially PRIvate correlation alignment approach for doMain Adaptation, which is referred to as PRIMA. In PRIMA, to reduce the large error caused by perturbing covariance matrix in high-dimensional setting, we present a random subspace ensemble based covariance estimation method which splits the feature spaces of source and target data into several low dimensional subspaces. In particular, we employ the forward selection strategy to determine the dimension of each subspace. In addition, to tackle the problem that the positive semi-definiteness of the covariance matrix is destroyed, we develop a shrinking based method for the positive semidefinite matrix recovery by computing the nearest positive semi-definite matrix to the perturbed covariance matrix.

Our contributions can be summarized as follows:

• We present a differentially private correlation alignment approach for domain adaptation, call PRIMA, to protect data privacy of both the source and target domains. To our knowledge, PRIMA is the first correlation alignment based approach for differentially private domain adaptation. We prove that PRIMA achieves (ϵ, δ)-differential privacy for the source and target data respectively.
• Based on random subspace ensemble, we propose a differentially private covariance estimation method for the high-dimensional setting, where the forward selection strategy is employed to determine subspace dimension.
• To recover the positive semi-definiteness of the covariance matrix, we develop a shrinking based method. Utility analysis shows that the recovered covariance matrix can provide better utility than the non-recovered one.
• We demonstrate the superiority of PRIMA through two concrete examples: logistic regression (LR) and deep neural network (DNN). Experimental results show that PRIMA outperforms the state-of-the-art methods.

2 RelatedWork

In the literature of differentially private domain adaptation, the most related work to ours is [LeTien et al., 2019]. Using random projection, LeTien et al. [LeTien et al., 2019] propose a differentially private domain adaptation approach based on optimal transport. However, optimal transport can only work if the target samples are an affine transformation of the source samples. In addition, optimal transport is sensitive to outliers of the source domain that have no correspondence in the target one, and can work only if there exist shared features in both domains. Wang et al. [Wang et al., 2020] propose a differentially private deep domain adaptation approach which uses an adversarial-learning strategy to construct domain-invariant features for classifying the unlabeled target data. However, their approach supposes that the source and target data owners trust each other and is only applicable to deep models. Wang et al. [Wang et al., 2018] propose a differentially private multiple-source hypothesis transfer learning approach. However, their approach needs to have access to a publicly available auxiliary dataset. Yao et al. [Yao et al., 2019] first propose a privacy-preserving logistic regression approach by stacking, then combine the proposed approach with hypothesis transfer learning. However, their approach trains on a fully labeled target data, and cannot be applied to the scenario where no labeled data are available in the target domain.

3 Preliminaries

3.1 Domain Adaptation

Domain adaptation (DA) aims at adapting a model trained in a source domain for use in a target domain, where the source and target domains may be different but related. Let Xs ∈ Rd and Xt ∈ Rd be the feature spaces of source and target data respectively. We denote the source data as: Ds = {(xis , yis )}ns i=1 , where xis ∈ Xs, and yis is the label of xis . Similarly, we denote the target data as: Dt = {(xjt )}nt j=1 , where xjt ∈ Xt. Let P(Xs) and Q(Xt) be the marginal distributions of Xs and Xt, respectively. The key assumption of domain adaptation is that P(Xs) ̸= Q(Xt), but

P(Ys|Xs) = Q(Yt|Xt).

As a simple yet efficient method for domain adaptation, correlation alignment (CORAL) aligns the marginal distributions of the source and target domains by aligning their covariance matrices. To minimize the distance between the covariance matrices of the source and target domains, correlation alignment applies a transformation matrix H to the original source feature space Xs and uses the Frobenius norm as the matrix distance metric:

where Cs and Ct are the covariance matrices of Xs and Xt respectively, C⃗s is the covariance matrix of the transformed source data {XsH, Ys}. After CORAL transforms the source data, a model trained on the transformed source data can be directly applied to target domain.

3.2 Differential Privacy

Definition 1 (Differential privacy (DP) [Dwork et al., 2006a; Dwork et al., 2006b]). A randomized mechanismM : X n → Rd satisfies (ϵ, δ)-differential privacy if for any two datasets D,D′ ∈ X n differing by a single element and for any set of possible output O ⊆ Range(M) :

where ϵ is the privacy budget and δ is the failure probability. Theorem 1 (Gaussian mechanism [Dwork et al., 2006a]). Given a function f : X n → Rd , the Gaussian Mechanism MG(D, f, ϵ) = f(D) + zg, where zg is drawn from Gaussian distribution N(0, σ2 Id), satisfies (ϵ, δ)-DP for some δ > 0, if σ ≥ √2 log(1.25/δ)∆2(f)/ϵ. Here ∆2(f) is the ℓ2-sensitivity of the function f, i.e. ∆2(f) = supD,D′ ||f (D) - f (D′ )||2 .

3.3 Random Subspace Ensemble

Random subspace ensemble (RSE) or simply Random Subspace (RS) [Skurichina and Duin, 2002] is an ensemble learning method which samples from the original feature space and builds one classifier on each subspace. Given training data X = {(xi )}ni=1 , whose rows represent the set of data samples and whose columns represent the set of features. Let F 1:d = {F 1 ,F 2 , ...,F d } be the set of features, where F i is the i-th feature of X. In RSE, one randomly selects p (p ≪ d) features from F 1:d , and obtains a p-dimensional subspace. Assume m is the ensemble size, the i-th subspace is ˆXi = (F i,1 ,F i,2 , ...,F i,p )⊤ (i ∈ [m]), where F i,j (j ∈ [p]) is randomly selected from F 1:d . Then one constructs classifiers ψi ( ˆXi ) in the random subspaces ˆXi and combines m classifiers by simple majority voting.

4 Proposed Approach

4.1 Overview

Our approach PRIMA consists of three phases: RSE based covariance estimation, positive semi-definite matrix recovery and model training. In the first phase, target domain employs RSE to split its feature space into several low dimensional subspaces, and perturbs the covariance matrix of each subspace. In particular, to determine the dimension of each subspace, the target domain uses the forward selection strategy in generating subspaces. In the second phase, the target domain modifies each perturbed covariance matrix to make it positive semi-definite via shrinking, and sends the modified matrices to the source domain. In the last phase, the source domain first generates subspaces according to the splitting results of the target domain, and then performs correlation alignment to transform each subspace by exploiting the received covariance matrices. Finally, the source domain trains models on the transformed source subspaces, and perturbs gradients during the gradient-based training. Figure 1 illustrates an overview of our approach.

4.2 RSE based Covariance Estimation

To obtain a private estimation of the covariance matrix of the target domain Ct, we add noise sampled from Gaussian distribution N(0, 2log(1.25/δ)/ϵ2 ) to every element in the real covariance matrix Ct = 1 nt XtX⊤ t , where the sensitivity is at most one [Dwork et al., 2014; Ge et al., 2018; Jiang et al., 2016; Wang and Xu, 2019]. As shown in [Dwork et al., 2014;

Amin et al., 2019], the upper error bound of the perturbed covariance matrix is d√log(1/δ)/ntϵ , where d is the dimension of the target data. Here, the bound d√log(1/δ)/ntϵ represents the Frobenius distance between the perturbed covariance matrix and the real covariance matrix, which is tight. We can see that the upper error bound is quite large in high dimensional setting.

To address the above limitation, we first employ RSE to split the original feature space Xt into m low dimensional subspaces. In particular, to avoid the allocation of privacy budget ϵ which results in much added noise, we leverage the composition property of differential privacy [McSherry, 2009] and split Xt into non-overlapping subspaces ˆX1:m t = { ˆX1 t , ˆX2 t , ..., ˆXm t }. We denote the dimension of ˆXi t by pit and have ∑mi=1 pit = d. Then, we add Gaussian noise to the corresponding covariance matrices ˆC1:m t = {ˆC1t , ˆC2t , ..., ˆCmt } of ˆX1:m t . Finally, we obtainmperturbed covariance matrices ˜C1:m t = {˜C1t , ˜C2t , ..., ˜Cmt }.

Clearly, the choice of the dimension pit of each subspace ˆXi t (i ∈ [m]) is a serious dilemma: a small pit leads to significant information loss of the subspace ˆXi t , while a large pit leads to poor utility of the perturbed covariance matrix ˜Cit . To choose a proper dimension pit of each subspace, we first define an criterion to measure the information loss of ˆXi t and the utility of ˜Cit , then employ the forward selection strategy [Caruana and Freitag, 1994] to determine the dimension pit of each subspace by minimizing such criterion.

The criterion contains two types of errors: reconstruction error and noise error. Specifically, we use the reconstruction error [Farahat et al., 2013] to measure the information loss of the subspace ˆXi t , and use the noise error to measure the utility of the perturbed covariance matrix ˜Cit . The reconstruction error R( ˆXi t ) measures the sum of squared errors between the original data Xt and the reconstructed data based on ˆXi t . In particular, the reconstruction error is defined by: R( ˆXi t ) = ||Xt -P ˆXi t Xt||2F , where P ˆXi t is an nt×nt projection matrix that projects the columns of Xt onto the span of the subspace ˆXi t of columns. The projection matrix P ˆXi t can be calculated as: P ˆXi t = ˆXi t (( ˆXi t )⊤ ˆXi t )-1 ( ˆXi t )⊤. The upper error bound of the perturbed covariance matrix ˜Cit measures the utility of ˜Cit , which can be regarded as the noise error. In particular, the noise error can be defined by: G( ˆXi t ) = pit√log(1/δ) ntϵ . As a result, the criterion is formulated as follows:

To minimize criterion (3), we adopt the forward selection strategy. Specifically, the forward selection strategy begins with an empty set S, and adds features sampled from feature set Ft one by one; meanwhile, deletes the sampled features from Ft. Once the errors (i.e., the sum of reconstruction and noise errors) of current S are larger than the previous one, the forward selection strategy stops the above process. The size of S is the dimension of the generated subspace S ⊤. To determine the dimensions of all the subspaces, we repeat the forward selection strategy until Ft is empty.

4.3 Positive Semi-definite Matrix Recovery

The positive semi-definiteness, which is a property of the covariance matrix Ct, may be destroyed by the RSE based covariance estimation. Clearly, destroying the positive semidefiniteness will lead to poor performance of domain adaptation. To this end, we present a shrinking based method to recover the positive semi-definiteness of the perturbed covariance matrix ˜Cit (i ∈ [m]).

Shrinking is widely used in statistical estimation [Ledoit and Wolf, 2004; Higham et al., 2016]. Given an indefinite matrix Σ0, and a positive semi-definite (PSD) matrix Σ1, shrinking is to seek the elementwise minimal change to Σ0 in the direction Σ1 - Σ0 by forming a convex linear combination Ω(α) = αΣ1 + (1 - α)Σ0 of Σ0 and Σ1, where α ∈ [0, 1] is the shrinking parameter. Based on the idea of shrinking, our task is to seek the nearest PSDmatrix to ˜Cit by computing Ω(αi ) = αiΣit + (1 - αi ) ˜Cit , and ensure that the recovered covariance matrix Ω(αi ) provide better utility than the perturbed one ˜Cit .

To guarantee Ω(αi ) is PSD, the key is to choose an optimal shrinking parameter αi∗ to satisfy:

The function f is defined by f(αi ) = λmin(Ω(αi )), where λmin denotes the smallest eigenvalue of a matrix. f(αi ) ≥ 0 is due to the fact that a matrix is PSD if and only if its smallest eigenvalue is non-negative. Since f is concave and continuous [Higham et al., 2016], and f(0) < 0, f(1) = λmin(Ω(1)) = λmin(Σit ), it follows that αi∗ is the unique zero of f in (0, 1) if the matrix Σit is PSD. Therefore, we use a bisection method to choose the optimal shrinking parameter, which is to find a zero of function f on a given interval (0, 1). Specifically, we first let αiℓ = 0 and αiγ = 1, then repeatedly bisect the interval [αiℓ , αiγ ] and select the subinterval in which the function f changes sign. The process is continued until the selected subinterval is sufficiently small. The final bisection point is the optimal shrinking parameter αi∗ . Therefore the nearest PSD matrix to ˜Cit is Ω(αi∗ ). For convenience, we denote Ω(αi∗ ) as Ci,+ t .

Moreover, to ensure that the utility of the recovered covariance matrix Ω(αi ) is better than ˜Cit , we should choose the PSD matrix Σit which satisfies ||Σit ||F < || ˜Cit ||F . Since correlation alignment performs domain adaptation by minimizing the distance in the Frobenius norm between the covariance matrices of the source and target domains, the distance in the Frobenius norm between the recovered PSD matrix Ci,+ t and the real covariance matrix Cit determines the utility of Ci,+ t . From Theorem 2, we can see ||Σit ||F used in the procedure of the PSD matrix recovery guarantees the distance between Ci,+ t andCit less than the distance between

˜Cit and Cit , which ensures the recovered covariance matrix Ci,+ t provides better utility than the perturbed matrix ˜Cit .

Theorem 2. Let Z denote the noise matrix introduced by the RSE based Covariance Estimation. For any αi ∈ (0, 1), ||Ci,+ t - Cit ||2F < || ˜Cit - Cit ||2F , if Σit satisfies ||Σit ||F < || ˜Cit ||F .

Proof. If ||Σit ||F < || ˜Cit ||F , we get

where (5) and (6) follow from the triangle inequality of the Frobenius norm.

It is clear that ||Ci,+ t -Cit ||2F -|| ˜Cit -Cit ||2F = (||Ci,+ t - Cit ||F +|| ˜Cit -Cit ||F )(||Ci,+ t -Cit ||F -|| ˜Cit -Cit ||F ), where ||Ci,+ t -Cit ||F+|| ˜Cit -Cit ||F > 0 follows from the definition of the Frobenius norm. Thus, to guarantee ||Ci,+ t -Cit ||2F < || ˜Cit - Cit ||2F , we need to ensure ||Ci,+ t - Cit ||F - || ˜Cit - Cit ||F < 0. Since Ci,+ t = αiΣit + (1 -αi ) ˜Cit , we have

Based on (6), to ensure ||Ci,+ t -Cit ||F-|| ˜Cit -Cit ||F < 0, we require ||Σit ||F < || ˜Cit ||F , which completes the proof.

4.4 Model Training

After the PSD matrix recovery phase, the source domain first generates m subspaces ˆX1:m s = { ˆX1 s , ˆX2 s , ..., ˆXm s } by exploiting the results of the forward selection strategy, and then performs correlation alignment on each subspace to get m transformed source subspaces {( ˆX1 s H1 , Ys), ( ˆX2 s H2 , Ys), ..., ( ˆXm s Hm, Ys)}. According to [Jiang et al., 2013], the models trained on the transformed source subspaces may leak sensitive information of the source data. To obtain m private models trained on m transformed source subspaces, we use the differentially private mechanism proposed in [Abadi et al., 2016] to perturb gradients using Gaussian noise during the stochastic gradient descent and use the moments accountant theorem [Abadi et al., 2016] to get a tight bound on the total privacy budget. Specifically, at each iteration, one forms a batch b of ( ˆXisHi , Ys), and clips the gradient g in L2 norm by dividing it by max(1, ||g||2 c ). This ensures that the L2 sensitivity of g is bounded by c. Then one computes the perturbed gradient ˜g = 1/|b| ∑x∈b g + N(0, σ2 c2 Id) using the Gaussian mechanism with variance σ2 . Finally, we obtain m private models W = {wi }mi=1 .

4.5 Privacy Analysis

Theorem 3. PRIMA achieves (ϵ, δ)-DP for the source and target data respectively, for any ϵ, δ > 0 and σ ≥ √2 log(1.25/δ)/ϵ.

Proof. For the target domain, applying Gaussian mechanism to the covariance matrix ˆCit (i ∈ [m]) can satisfy (ϵ, δ)-DP. Since the perturbed covariance matrices ˜C1:m t are estimated on m disjoint subspaces, the parallel composition property of DP [McSherry, 2009] ensures that the RSE based covariance estimation phase satisfies (ϵ, δ)-DP. The positive semidefinite matrix recovery phase depends only on the perturbed covariance matrix ˜Cit , which also satisfies (ϵ, δ)-DP by the post-processing property of DP [Dwork et al., 2006b]. In summary, PRIMA achieves (ϵ, δ)-DP for the target data.

For the source domain, when training each model, we perturb gradients in each iteration, and use the moments accountant theorem [Abadi et al., 2016] to keep track of the privacy parameters ϵ, δ. According to [Abadi et al., 2016] and Theorem 2, the process of training the model wi satisfies (ϵ, δ)-DP. Similarly, the parallel composition property ensures that the model training phase satisfies (ϵ, δ)-DP. In summary, PRIMA achieves (ϵ, δ)-DP for the source data.

5 Experiments

5.1 Benchmark Datasets

We evaluate our approach on two popular domain adaptation benchmark datasets. The first one is Office-Caltech10 dataset [Gong et al., 2012], which contains 10 object categories from an office environment (e.g., keyboard, laptop, etc.) in 4 sources: Webcam (W), DSLR (D), Amazon (A), and Caltech256 (C) with 958, 295, 157 and 1,123 image samples respectively. We follow [LeTien et al., 2019] to encode each source into 4096-dimensional feature vectors. Using each source as a domain, we get four domains leading to 12 domain adaptation tasks: A→D (train on A, test on D, the same below), A→C, and so on. The second one is Amazon review dataset [Blitzer et al., 2006], which contains Amazon reviews on 4 domains, namely Book (BK), DVD (DV), Kitchen (KT) and Electronics (EL). There are 1000 positive and 1000 negative reviews on each domain. We follow [Wang et al., 2020] to encode every review into a 5,000-dimensional feature vector by using the bag-of-word method, and perform domain adaptation under 4 pairs of source and target domains: KT → DV, DV → BK, BK → EL, EL → KT. For data preprocessing, we normalize each feature into the interval [0, 1].

5.2 Experimental Setup

We showcase the application of our approach in LR and DNN classifiers. For LR, since the Office-Caltech10 dataset is multiclass classification, we need to construct multiple binary models (one for each class), and split the privacy budget across sub-models. We use the simplest composition property [McSherry, 2009], and divide the privacy budget evenly. For DNN, we follow the standard of [LeTien et al., 2019] that all methods are written with the same model architecture (a 3-layer neural network) for fair comparison.

There are 5 prime parameters in PRIMA. Among them, ϵ, δ, σ are privacy parameters, batch size b, clipping bound c are model training parameters. We follow the experimental protocol used in [Abadi et al., 2016] by setting σ = 4, δ = 10-5 , and compute the value of ϵ as a function of the training epochs E. We follow the experimental protocol of [Abadi et al., 2016] again by setting c as the median of the unclipped gradients over the course of training. Empirically, batch size b is set to 25. For both datasets, our experiments are repeated for 20 times, and average accuracy is presented.

5.3 Experimental Results

Performance of Our Approach

In this part, we compare our approach PRIMA against two privacy-preserving domain adaptation approaches: DPDA [LeTien et al., 2019], GDPDA [Wang et al., 2020], as well as four non-private domain adaptation methods CORAL [Sun et al., 2016], SA [Fernando et al., 2013], OTDA [Courty et al., 2016] and DANN [Ganin et al., 2016]. The private approaches DPDA and GDPDA are implemented based on the non-private methods OTDA and DANN respectively. We do not compare with DPDA-Target which is also proposed by [Wang et al., 2020], as it can only protect the privacy of the target data. Besides, since the covariance matrix used in PRIMA is widely used as a fundamental ingredient for subspace based domain adaptation [Fernando et al., 2013; Cui et al., 2014], PRIMA can be extended to subspace based domain adaptation. Therefore, we show the results on one PRIMA variant, which has the same settings as PRIMA, except that it replaces CORAL by SA [Fernando et al., 2013]. We denote such variant as PRISA.

Tables 1, 2, 3 and 4 show results on both datasets with ϵ = 2. Figure 2 gives the results of varying privacy budget ϵ on pair C → A. As can be seen, PRIMA and PRISA achieve better performance than the competitors DPDA and GDPDA in almost all cases. Specifically, when fixing ϵ = 2, the accuracy of PRIMA and PRISA drop around 1% over non-private methods while DPDA and GDPDA drop by 3% - 5% over non-private methods. This is because, compared with DPDA and GDPDA, PRIMA and PRISA can guarantee the source and target domains have much closer distributions by improving the utility of the perturbed covariance matrix. From Figure 2, we can observe that PRIMA and PRISA achieve competitive accuracies on a wide range of values for ϵ. By contrast, DPDA and GDPDA show an unstable behavior. For example, when ϵ varies from 4 to 1, the accuracy drops from 0.90 to 0.79 for the LR classifier of DPDA.

Ablation Study

In order to analyze the effects of the RSE based covariance estimation and PSD matrix recovery methods, the following methods are compared: 1) Basic, which first perturbs the covariance matrix of the target domain, and then perturbs the gradients during model training; 2) RSE+Basic, which uses RSE to split the source and target feature spaces into several subspaces respectively, then applies the Basic method to each subspace; 3) RSE+Basic+FS, which applies the forward selection strategy to RSE+Basic; 4) Basic+Shrinking, which applies the shrinking based PSD matrix recovery method to Basic. We compare PRIMA with these four methods by performing LR on pair C → A.

Figures 3(a) and 3(b) give the results of varying privacy budget ϵ. From the results, we observe that: 1) RSE+Basic achieves a higher accuracy than Basic, which indicates that the RSE based covariance estimation can significantly improve the utility of the perturbed covariance matrix by decreasing dimension; 2) RSE+Basic+FS outperforms RSE+Basic, from which we can conclude that the forward selection strategy can effectively generate subspaces; 3) Basic+Shrinking achieves better performance comparing with Basic, which shows that the PSD matrix recovery method can further improve the utility of the perturbed covariance matrix.

6 Conclusion

In this paper, we propose the first differentially private approach for correlation alignment based domain adaptation.

We show that our approach guarantees (ϵ, δ)-differential privacy. Experimental results on real world data demonstrate the superiority of our approach.

Acknowledgments

We sincerely thank the anonymous reviewers for their helpful comments. This work was supported by the National Natural Science Foundation of China (Grant No. 61872045), the Innovation Research Group Project of NSFC (61921003).