Differentially Private Pairwise Learning Revisited

1 Introduction

As an important family of learning problems, pairwise learning has drawn much attention recently. Since pairwise learning involves loss functions depending on pairs of samples, it shows great advantage in modeling the relative relationship between pairs of samples over traditional pointwise learning (e.g., classification), in which the loss functions only take individual samples as the input. In practice, many learning tasks can be categorized as pairwise learning problems. For instance, metric learning [Huai et al., 2019] aims to learn a distance metric from a given collection of pair of similar/dissimilar samples that preserves the distance relation among the data, which can be formulated as a pairwise learning problem. Apart from metric learning, many other learning tasks, such as AUC maximization [Zhao et al., 2011] and ranking [Tang and Wang, 2018], can also be categorized as pairwise learning.

∗The first two authors contributed equally to this paper. Part of the work was done when Zhiyu Xue and Shaoyang Yang were research interns at KAUST.

Although the importance of pairwise learning has been recognized in many real-world applications, there is still a privacy issue among the current learning algorithms. Among existing privacy-preserving strategies, differential privacy (DP) [Dwork et al., 2006], as a rigorous notion for data privacy, can provide very rigid privacy and utility guarantee. While DP pointwise learning has been extensively studied in the last decade, starting from [Chaudhuri and Monteleoni, 2009; Wang and Xu, 2019a; Wang et al., 2017; Wang et al., 2019; Wang et al., 2020; Wang and Xu, 2019b; Wang and Xu, 2021; Bassily et al., 2014; Bassily et al., 2019; Bassily et al., 2019; Feldman et al., 2020]. DP pairwise learning is still not well understood. [Shang et al., 2014] considered the DP for rank aggregation which combines multiple ranked lists into a single rank, their problem cannot be generalized to all pairwise loss functions. [Li et al., 2020] proposed differential pairwise privacy for secure metric learning but utility (generalization) analysis is not given. Recently, [Huai et al., 2020] first studied the problem under both of the online and offline settings, and provided some preliminary theoretical results, which is extended by [Yang et al., 2021] to the non-smooth case. However, the problem has not been completely understood, yet. As we can see from Table 1, there is still a huge gap between their upper bounds of the population error and their corresponding lower bounds in both of the strongly convex and general convex cases, which means that their utilities are far from optimal. Motivated by this, our question is,

For the problem of differentially private pairwise learning, can we find private estimators whose population errors match their corresponding lower bounds, for strongly convex and general convex loss cases, in (ϵ, δ)/ϵ-DP model?

Here we provide the affirmative answer of the previous question, and we summarize our theoretical results in Table 1. In details, the contributions of this paper can be summarized as follows:

• Firstly, we consider the pairwise learning problem with Lipschitz, smooth and strongly convex loss functions. We propose an algorithm, which is based on the stability of the Projected Gradient Descent method, and show that its output could achieve an expected population error of O( 1n + d log 1 δ n2 ϵ2 ) and O( 1n + d2 n2 ϵ2 ) (if we omit other terms) for (ϵ, δ)-DP and ϵ-DP, respectively, where n is the sample size and d is the dimensionality of the under-

lying space. As we can see from Table 1, these bounds match their corresponding lower bounds, which means they are optimal.

• Then we study the problem with general Lipschitz and smooth convex loss functions. Unlike the strongly convex case, direct using our previous idea of proof to general convex case can only achieve a sub-optimal population error. To overcome the challenge, motivated by [Feldman et al., 2020] and our previous idea, we propose an algorithm whose output could achieve an expected population error of O( 1 √n + √d log 1 δ nϵ ) and O( 1 √n + d nϵ ) for (ϵ, δ)-DP and ϵ-DP, respectively. And these upper bounds are optimal.
• Finally, we conduct comprehensive experiments on metric learning and AUC maximization, with or without ℓ2norm regularization. Experimental results support our theoretical results and also show the priority of our algorithms compared with the previous ones.

Due to the space limit, additional definitions, related work, all the proofs are included in the full version of the paper.

2 Preliminaries

We say that two datasets D, D′ are neighbors if they differ by only one entry, which is denoted as D ∼ D′ .

Definition 1 (Differential Privacy [Dwork et al., 2006]). A randomized algorithm A is (ϵ, δ)-differentially private (DP) if for all neighboring datasets D,D′ and for all events S in the output space of A, we have Pr(A(D) ∈ S) ≤ eϵPr(A(D′ ) ∈ S) + δ. When δ = 0, A is ϵ-differentially private.

Different from the pointwise loss function ℓ : C ×D ↦→ R, a pairwise loss function is a function on pairs of data records, i.e., ℓ : C ×D×D ↦→ R, where D is the data universe. Given a dataset D = {z1, z2, · · · , zn} ⊆ Dn and a loss function ℓ(·; ·, ·), its empirical risk can be defined as:

When the data samples are drawn i.i.d from an unknown underlying distribution P on D, we also have the population risk, which is

Similar to the definition of DP pointwise learning [Bassily et al., 2014], we can define DP pairwise learning as follows.

Definition 2. Let C ⊆ Rd be a convex, closed and bounded constraint set, D be a data universe, and ℓ : C × D × D ↦→ R be a pairwise loss function. Also, let D = {z1 = (x1, y1), z2 = (x2, y2), · · · , zn = (xn, yn)} ⊆ Dn be a dataset with data records {xi}ni=1 ⊂ Rd and labels (responses) {yi}ni=1 ⊂ [-1, 1]n . Differentially private (DP) pairwise learning is to find a private estimator wpriv ∈ Rd so that the algorithm is (ϵ, δ) or ϵ differential privacy and the error is minimized, where the error for an estimator w can be measured by either the optimality gap ErrD(w) = L(w; D) - minw∈C L(w; D) or the population error ErrP (w) = LP (w) - minw∈C LP (w).

In the experiments section we will conduct experiments on metric learning and AUC maximization, with or without ℓ2norm regularization, for strongly convex or general convex case. Next, we will give a brief review on these two problems. Example 1: Metric Learning [Cao et al., 2016] The goal here is to learn a Mahalanobios metric M 2W (x, x′ ) = (x - x′ )T W(x - x′ ) using loss function ℓ(W; z, z′ ) = φ(yy′ (1 - M 2W (x, x′ )), where y, y′ ∈ {-1, +1} and φ(x) is the logistic function i.e., φ(x) = log(1 + e-x ). The constraint set C is C = {W : W ∈ Sd , ‖W‖F ≤ 1}, where Sd is the set of d×d positive symmetric matrices.

Example 2: AUC Maximization [Zhao et al., 2011] The goal here is to maximize the area under the ROC curve for a linear classification problem with the constraint of ‖w‖2 ≤ 1. Here ℓ(w; z, z′ ) = φ((y - y′ )h(w; x, x′ )) and h(w; x, x′ ) = wT (x - x′ ), where y, y′ ∈ {-1, +1}.

3 Strongly Convex Case

Assumption 1: We assume the loss function ℓ(·; z, z′ ) is G-Lipschitz, L-smooth and α-strongly convex.

The idea of our algorithm is motivated by the ℓ2-norm sensitivity of the Projected Gradient Descent (PGD) method for the empirical risk function. For PGD method, its ℓ2-norm sensitivity corresponds to its stability, which has been studied in [Hardt et al., 2016] for pointwise loss functions. Motivated by this, we generalize to pairwise loss functions. Based on its sensitivity and the Gaussian mechanism, we have Algorithm 1. The guarantee of DP is mainly based on the following lemma:

Algorithm 1 DP Gradient Descent-SC (DPGDSC)

Input: D = {zi}ni=1 ⊂ Rd , privacy parameters ϵ, δ, empirical risk L(w;D), initial parameter w0, step size η ≤ 2 L+α and number of iterations T (will be specified later).

• 1: for t = 1, 2, · · · , T do
• 2: Let wt = ΠC(wt-1 - η∇L(w;D)), where ΠC is the projection onto the set C.
• 3: end for
• 4: When δ > 0, return ˜wT = wT + ζ, where ζ ∼ N(0, σ2 Id) and σ = 8√2 ln(1.25/δ)G αnϵ .
• 5: When δ = 0, return ˜wT = wT + ζ, where ζ = (ζ1, · · · , ζd) with ζi ∼ Lap(λ) and λ = 8G√d αnϵ .

Lemma 1. For any D ∼ D′ , if we denote w′t , t ∈ [T] as the parameters which correspond to wt in Algorithm 1 performed on D′ , then under Assumption 1, with η ≤ 2 L+α , we have for all t ∈ [T],

Theorem 1. Under Assumption 1, when the step size η ≤ 2 L+α , Algorithm 1 is (ϵ, δ)-DP when δ > 0 and ϵ-DP otherwise. Moreover, if we let T = ˜O( Lα logn), then when δ > 0, we have

When δ = 0, we have

Where ‖C‖2 is the diameter of the set C and ˜O omits other logarithmic factors, EA,D means that the expectation takes over the randomness of the algorithm A and the data distribution D ∼ P n .

Remark 1. For pointwise loss functions, [Zhang et al., 2017] provided an output perturbation method based on the ℓ2norm sensitivity of the PGD method. Although the ideas of these two algorithms are similar, there are still several differences on the utility guarantees. Firstly, [Zhang et al., 2017] only showed that its output could achieve the optimal rate for optimality gap in the strongly convex case. However, as [Bassily et al., 2019] said, optimal optimality gap of an estimator cannot guarantee its population error is also optimal. In this paper, we propose a new approach to show that our output achieves the optimal rate for the population error, which has not been studied previously. And this approach could might be used to other problems. Second, in the general convex case, as [Zhang et al., 2017] said, their algorithm could only achieve a sub-optimal rate, even for the optimality gap. While in the later section we will use the idea of our approach to design an algorithm whose output could achieve the optimal rate for population error (see Section 4 for details).

For poinwise loss case, there are mainly three approaches on showing the population errors for a given estimator wpriv.

The first approach is to directly transfer the optimality gap to population error via some existing lemmas, such as [Bassily et al., 2014; Chan et al., 2011]. However, as [Bassily et al., 2014] mentioned, this approach could only achieve a sub-optimal rate, see Section F of Appendix in [Bassily et al., 2014] for details. The second approach is based on the online-to-batch method, which has been used in [Huai et al., 2020] for pairwise loss. However, as we said previously, this approach could also only achieve a sub-optimal rate of population error. The third type of approaches is proposed by [Bassily et al., 2019] recently, which is based on the uniform stability of the Differentially Private Batch SGD method. However, [Bassily et al., 2019] only studied the case where the loss function is pointwise and general convex, it is unknown whether their algorithm can be extended to the pairwise loss functions or strongly convex loss functions. Our new method could be seen as an extension of the above third method. Specifically, for the output, its population error can be decomposed into the sum of its generalization error and its optimality gap [Shen et al., 2020; Yang et al., 2021]. Motivated by this, we bound the the optimality gap of the output via the stability of the algorithm, i.e., the the ℓ2-norm sensitivity of the PGD method.

4 General Convex Case

Motivated by the idea in the previous section, one question is whether we can generalize it to the general convex case.

Assumption 2: For any pair z, z′ ∈ D, we assume the loss function ℓ(·; z, z′ ) is convex, G-Lipschitz, and L-smooth.

The most direct problem is that whether we can use the same idea of Algorithm 1, i.e., perturbing the output of PGD method. We show that it is possible. However, the population error of our output is only sub-optimal in the general convex case, which is quite different compared with the strongly convex case.

In the next, we propose a simple method and show that for (ϵ, δ)-DP, instead of perturbing the output of the PGD method, perturbing the gradient by Gaussian noise in each iteration of PGD method could directly achieve the optimal rate of population error. It is notable that although many previous paper also studied Algorithm 2 [Bassily et al., 2014], most of them only considered the optimality gap. However, in this paper we focus on the optimality of population error.

Algorithm 2 DP Gradient Descent (DPGDC2)

Input: D = {zi}ni=1 ⊂ Rd , privacy parameters ϵ, δ > 0; empirical risk L(w;D), initial parameter w0, step size η ≤ 2L and number of iterations T .

• 3: end for

Theorem 2. Under Assumption 2, Algorithm 2 is (ϵ, δ)-DP. Moreover, we have the following by setting T = min{n, n2 ϵ2 d log 1/δ } and η = G ‖C‖2√T if L ≤ ‖C‖2 2G min{n, nϵ √d log 1/δ }

While Algorithm 2 is succinct, there are still many issues. Firstly, Theorem 2 only holds for (ϵ, δ)-DP model, it is unknown whether we can extend to ϵ-DP model. Secondly, we can see that in Algorithm 2 the privacy budget is evenly split across iterations. However, as we know when the iteration number increases, our estimator will be closed to the optimal one and the gradients start to decrease and need to be measured more accurately in order for the optimization to continue making progress. This means that an adaptive privacy budget allocation may has preferable practical performance to a fixed allocation, as long as the total privacy cost is the same.

To address the above two issues, we propose a new method which is based on [Feldman et al., 2020]. The idea is that, for poinwise loss functions in the non-private case, compared with the PGD method, recently some work such as [Hazan and Kale, 2014; Feldman et al., 2020] showed that a variant of PGD, which is called the Epoch PGD method, could achieve an improved bound of generalization error. The basic idea of Epoch PGD is that, we first divide the whole dataset into several disjoint subsets; in each epoch, we run the PGD method for several iterations on one of these subsets; then we take the current parameter as the initial parameter of the next epoch. Motivated by this, we propose a DP version of the Epoch PGD method (for convenience here we assume n = 2k for some positive integer k). We have the following theoretical guarantees.

Theorem 3. Under Assumption 2, when the step size η ≤ 2L , Algorithm 3 is (ϵ, δ)-DP when δ > 0 and ϵ-DP otherwise. Moreover, when δ > 0, we have the following result by setting η = ‖C‖2 G min{ 4 √n , ϵ √d log 1/δ }

When δ = 0, setting η = ‖C‖2 G min{ 4 √n , ϵd } we have

Remark 2. Compared with Algorithm 2, Algorithm 3 could achieve the optimal rate for both (ϵ, δ)-DP and ϵ-DP models. Moreover, since the stepsize in each epoch is varied and the magnitude of the noise depends on the stepsize, the noise we added in each epoch is different and adaptive. More specifically, as we can see from Theorem 3, when the sample size is large enough, the stepsize ηi will be very small and it will be decayed to 4-i η in the i-th epoch, this means that it will be closed to 0, and thus the noise we add will be closed to

Algorithm 3 DP Epoch Gradient Descent (DPEGD)

Input: D = {zi}ni=1 ⊂ Rd , privacy parameters ϵ, δ, empirical risk L(w;D), initial parameter w0, step size η ≤ 2L .

• 1: Let k = log2 n, we divide the dataset D into k disjoint subsets {D1, · · · ,Dk}, where each Di has ni = 2-in samples for i < k, and Dk contains all the left data samples.
• 2: for i = 1, 2, · · · , k do
• 3: Let ηi = 4-i η.
• 4: Run the PGDmethod for L(·;Di) on the constraint set C and we take wi-1 as the initial parameter. Specifically, we set the fixed stepsize as ηi and the iteration number as ni. Let ¯wi be the average parameter after ni iterations.
• 5: When δ > 0, let wi = ¯wi+ζi, where ζi ∼N(0, σ2 Id) and σ = 4√2 ln(1.25/δ)Gηi
• ϵ 6: When δ = 0, let wi = ¯wi+ζi, where ζi = (ζ1, · · · , ζd) with each ζj ∼ Lap(λ) and λ = 4Gηi√d ϵ
• 7: end for
• 8: Return wk

0 when the iteration number increases. This means that the practical performance of Algorithm 3 will be better than Algorithm 2, we will verify this conclusion in the experimental part.

5 Experiments

Datasets. We use two real-world datasets that are widely adopted in pairwise learning tasks. These datasets are the Diabetes dataset and the Diabetic Retinopathy dataset, which have also been used in [Huai et al., 2020].

Performance measures. To evaluate the performance of the proposed algorithms, we use the following measures:

• Classification Accuracy: For metric learning task, we calculate the classification accuracy that is defined as the percentage of the correctly classified samples in the test set. The less the classification accuracy, the worse the performance of the proposed algorithm. In this paper, the KNN classifier is adopted to assign labels to the test samples. For the KNN classifier, we set K to be 3.
• AUC Score: For AUC maximization task, we report the AUC score [Zhao et al., 2011] for each of the proposed algorithms over every adopted dataset. A larger AUC value means that the corresponding AUC maximization algorithm can generate more accurate results.

Baseline methods. As we mentioned before, [Huai et al., 2020] is the only work on DP pairwise learning, thus we use OffPairStrC and OffPairC proposed in [Huai et al., 2020] for strongly convex and convex case as our baselines for private algorithms, respectively. We will also follow [Huai et al., 2020] and use variants of OffPairStrC and OffPairC, which do not add any noise, as non-private baseline methods. In these experiments, we will choose different ϵ. And for (ϵ, δ)- DP model, we will set δ = 1n .

Experimental settings. In this paper we studied both of the strongly convex and general convex cases. To conduct experiments for strongly convex case, we add an additional Frobenius norm or ℓ2-norm regularization term with some λ > 0 to the original problem of metric learning and AUC maximization respectively to make the loss be strongly convex. We set λ = 10-3 for AUC maximization and λ = 10-2 for metric learning.

Metric Learning. In Table 2 we perform the results for different training sample size, with fixed privacy budget ϵ = 1. And in Table 3 we show the results for different privacy budget, with fixed training sample size n = 512. Compared with previous methods, our algorithms show better performance under all the four different settings:

• In the strongly convex case and δ > 0, DPGDSC (Algorithm 1) performs better than OffPairStrC and the difference of accuracy between them increases as the training size increases, and it will be closed to the non-private case. Furthermore, if we fix the training size and change the parameter ϵ, we can see from Table 3 that DPGDSC maintains its advantage over OffPairStrC.
• When the loss function is convex and δ > 0, DPGDC2 (Algorithm 2) shows an improvement in comparison with OffPairC. Especially, it has significant improvement on the Diabetes dataset. In addition, DPEGD (Algorithm 3) has better performance than OffPairC and DPGDC2 on both datasets. Moreover, from Table 3 we can see under different ϵ, DPEGD outperforms other methods.
• In the strongly convex case in the ϵ-DP model, although the improvement is limited, we can still see that our new algorithm is slightly better than the best known method. Moreover, as shown in Table 3, except for some cases, most of the results show that DPGDSC has a better performance than OffPairStrC.
• Finally, we can see that, when the loss function is convex and in the ϵ-DP model, DPEGD outperforms OffPairC under different ϵ or different training sample size.

AUC Maximization. For AUC maximization, Table 4 shows the results on Diabetes and Diabetic Retinopathy datasets for different ϵ with fixed n = 256. Figure 1, 2, 3

and 4 shows the results for different sample size in strongly convex or general convex case, under (ϵ, δ) or ϵ-DP model respectively, with fixed ϵ = 0.8. From these results, we can get almost the same conclusions as in the metric learning case. Moreover, from Figure 1(b) and 3(b), we can see when the loss function is strongly convex, the performance of DPGDSC is much better than OffPairStrC, while the difference of accuracy between these two methods is quite small in the metric learning task.