Differentially Private Iterative Gradient Hard Thresholding for Sparse Learning

1 Introduction

In modern high-dimensional data analytics, where the problem dimension can increase with the number of observations, sparse learning has emerged as a prominent method to alleviate overfitting and provide statistically reliable results. Consequently, many sparse learning algorithms such as ℓ1 convex relaxation based methods [Tibshirani, 1996; Van de Geer and others, 2008; Negahban et al., 2009] have been proposed in the past two decades. Compared with ℓ1 convex relaxation based sparse learning algorithms, ℓ0 constrained sparse learning algorithms [Zhang, 2011; Yuan et al., 2014; Jain et al., 2014; Chen and Gu, 2016] received increasing attention due to its small estimation bias. In specific, the ℓ0 constrained sparse learning is formulated as follows

where S = {z1, z2, . . . , zn} denotes the training dataset with zi = (xi, yi), LS is the empirical loss function, ‖θ‖0 denotes the number of nonzero entries in θ, s is a parameter for tuning the sparsity level of θ, and we assume that the data are generated from some underlying statistical model with sparse parameter vector θ∗ ∈ Rd such that ‖θ∗ ‖0 = s∗ . The goal of sparse learning is to recover θ∗ .

In many applications, the data used for sparse learning are sensitive datasets, such as financial records or genomic data, raising a big concern that the adversaries may be able to infer the private information from the trained model. This privacy concern necessitates the private-preserving algorithms for learning sparse models. The prerequisite for developing such algorithms is a rigorous privacy definition. In recent years, differential privacy [Dwork et al., 2006] has been served as the most widely adopted notion of statistical data privacy and has been applied to many real world applications [Erlingsson et al., 2014; Ding et al., 2017]. The formal definition of differential privacy is as follows.

Definition 1.1 (Differential privacy [Dwork et al., 2006]). A randomized mechanism M : S n → R satisfies (ϵ, δ)- differential privacy if for any two adjacent data sets S, S′ ∈ S n differing by one example, and any output subset O ⊆ R, it holds that

According to the definition, differential privacy requires that datasets differing by one example lead to similar distributions on the output of a randomized algorithm. This implies that an adversary will draw essentially the same conclusions about an individual whether or not that individual's data was used even if many records are known a priori to the adversary.

There exist several studies [Kifer et al., 2012; Thakurta and Smith, 2013; Talwar et al., 2015] trying to develop differentially private algorihthms for solving sparse learning problems. However, they only consider sparse linear regression, and the convergence rates and utility guarantees of these methods are suboptimal. In order to overcome the limitations of existing differentially private sparse learning algorithms, we propose a differentially private iterative gradient hard thresholding (DP-IGHT) algorithm for solving the sparsity constrained learning problem (1.1), which is not only very efficient but also has comparable or even better utility guarantees than the state-of-the-art methods. We summarize the contributions of our work as follows

• Compared with existing work that is limited to sparse linear regression, our differentially private sparse learning algorithm is generic enough that it can be applied to a broad family of loss functions that satisfy the restricted strong convexity and smoothness conditions [Bickel et al., 2009; Negahban et al., 2009], and each component function is Lipschitz continuous. We demonstrate the superiority of our framework through two concrete examples: sparse linear regression and sparse logistic regression.
• We prove the linear convergence rate for our DP-IGHT algorithm, which outperforms the sub-linear convergence rate of Frank-Wolfe based method [Talwar et al., 2015], and does not rely on any computationally intractable support selection algorithm as required by [Kifer et al., 2012].
• We establish strong utility guarantee for our DP-IGHT algorithm. Specifically, it achieves the best known utility guarantee [Kifer et al., 2012] for sparse linear regression while not requiring any extra support selection procedure. Our approach also provides the first utility guarantee for sparse logistic regression.

Notation. For a d-dimensional vector x = [x1, ..., xd]⊤, we use ‖x‖2 = (∑di=1 |xi|2 )1/2 to denote its ℓ2-norm, and use ‖x‖∞ = maxi |xi| to denote its ℓ∞-norm. We let supp(x) be the index set of nonzero entries of x, and supp(x, s) be the index set of the top s entries of x in terms of magnitude. We use S n to denote the input space with n examples and R to denote the output space. Given two sequences {an} and {bn}, if there exists a constant 0 < C < ∞ such that an ≤ Cbn, we write an = O(bn), and we use ˜O(·) to hide the logarithmic factors. We denote the d by d identity matrix by Id. For simplicity, we use ℓi(·) to denote ℓ(·; zi) throughout the paper.

2 RelatedWork

To develop differentially private algorithms, the commonly used methods include output perturbation [Chaudhuri and Monteleoni, 2009], objective perturbation [Chaudhuri and Monteleoni, 2009], and gradient (iterative) perturbation [Bassily et al., 2014]. More specifically, output perturbation adds random noise to the output of a non-private algorithm. Objective perturbation perturbs the objective function of learning algorithms by random noise before learning. And the idea of gradient perturbation is to introduce random noise into the intermediate steps of the learning algorithm. Although these approaches have been extensively studied for empirical risk minimization [Chaudhuri and Monteleoni, 2009; Chaudhuri et al., 2011; Kifer et al., 2012; Bassily et al., 2014; Zhang et al., 2017; Wang et al., 2017; 2018; Jayaraman et al., 2018] in classical setting, their applications to sparse learning in the high-dimensional regime remain understudied.

There exist several ad hoc approaches [Kifer et al., 2012; Thakurta and Smith, 2013; Jain and Thakurta, 2014; Talwar et al., 2015] to solving differentially private (sparse) learning in the high-dimensional setting. For example, [Jain and Thakurta, 2014] proposed a differentially private algorithm with the dimension independent utility guarantee for empirical risk minimization. Nevertheless, their method only works for specific loss functions and the utility guarantee is suboptimal in terms of other parameters. The most relevant studies to ours are [Kifer et al., 2012; Thakurta and Smith, 2013; Talwar et al., 2015], which studied differentially private sparse linear regression. In detail, [Kifer et al., 2012; Thakurta and Smith, 2013] proposed to first perform some differentially private model selection algorithms to estimate the support set of sparse model parameter vector, and then run the objective perturbation algorithm to estimate the parameter vector with its support restricted to the estimated subset. While, their method can achieve O(s∗2 log(2/γ)/(nϵ)2 ) utility guarantee, where ϵ is the privacy budget and γ is the probability that the model selection algorithms can successfully select the true support, the model selection algorithms, such as exponential mechanism, may be computational inefficient or even intractable in practice. In addition, the privacy and utility guarantees of their algorithm only holds for the exact optimal solution to the perturbed optimization problem. Later on, [Talwar et al., 2015] developed a differentially private Frank-Wolfe algorithm, which is based on the gradient perturbation, for sparse learning. They showed that their algorithm can achieve O(ω(C)2/3 log n/(nϵ)3/2 ) utility guarantee, where ω(C) is the Gaussian width of the constraint set C. However, their approach only has a sublinear convergence rate and the Gaussian width ω(C) can only be estimated for some specific convex set such as ℓ1-norm ball.

Different from the aforementioned methods for sparse learning, our proposed DP-IGHT algorithm does not require exactly solving the optimization problem or the extra model selection procedure. Therefore, it is able to attain better empirical performances and more preferable in practice. In addition, our algorithm enjoys a linear convergence rate, which is more efficient than previous methods. The detailed comparisons of different algorithms for sparse linear regression are summarized in Table 1.

3 Preliminaries

In this section, we present some definitions that will be used throughout our paper. We first introduce several classes of functions that we considered in our work.

Definition 3.1 (G-Lipschitz continuous). A function f : Rd → R is G-Lipschitz continuous, if the following inequality holds for all θ1, θ2 ∈ domf

Note that for a differentiable function f, G-Lipschitz continuous implies that the gradient norm is bounded, i.e., ‖∇f(θ)‖2 ≤ G for all θ ∈ domf .

Definition 3.2 (Sparse eigenvalue condition). A twice differentiable function f : Rd → R satisfies sparse eigenvalue condition with parameters µ > 0 and β > 0, if the following holds for the Hessian of f for all θ ∈ domf,

For sparse learning problems, sparse eigenvalue condition [Bickel et al., 2009] implies the restricted strong convexity and smoothness conditions [Negahban et al., 2009; Loh and Wainwright, 2013], which guarantee the objective function behaves like a strongly convex and smooth function over a sparse domain even the function is general convex in its entire domain. In the following discussion, we denote κ by β/µ.

Zero-concentrated differential privacy. Although the notion of (ϵ, δ)-DP, i.e., Definition 1.1, is widely used for the analysis of the output and objective perturbation methods, it is not suitable for the gradient perturbation method since it will give loose composition results. We propose to use the notion of zero-concentrated differential privacy [Bun and Steinke, 2016], which has a sharp composition result and thus is a better choice for gradient perturbation method.

Definition 3.3 (Zero-concentrated differential privacy). A randomized mechanism M : S n → R satisfies ρ-zeroconcentrated differential privacy (ρ-zCDP) if for any two adjacent datasets S, S′ ∈ S n differing by one example, it holds that for all α ∈ (1,∞)

where Dα(M(S)||M(S′ )) is the α-Renyi divergence 1 between two distributions M(S) and M(S′ ).

Note that ρ-zCDP can be converted to (ϵ, δ)-DP through the following lemma, which is established in [Bun and Steinke, 2016].

Lemma 3.4. If a randomized mechanism M : S n → R satisfies ρ-zCDP, then it satisfies (ρ + 2√ρ log(1/δ), δ)- differential privacy for any δ > 0.

Next, we introduce the definition of ℓ2-sensitivity, which is used to control the variance of the Gaussian Mechanism for ensuring ρ-zCDP.

Definition 3.5 (ℓ2-sensitivity [Dwork et al., 2006]). For two adjacent datasets S, S′ ∈ S n differing by one example, the ℓ2-sensitivity ∆2(q) of a function q : S n → Rd is defined as ∆2(q) = supS,S′ ‖q(S) - q(S′ )‖2.

Based on ℓ2-sensitivity, we can use Gaussian mechanism to make our algorithms satisfy ρ-zCDP.

Lemma 3.6 (Gaussian mechanism [Bun and Steinke, 2016]). Given a function q : S n → Rd , the Gaussian Mechanism M(S) = q(S) + u, where u ∼ N(0, σ2 I), satisfies ∆2(q)2 /(2σ2 )-zCDP.

1 The formal definition can be found in [R´enyi, 1961].

ρ-zCDP has the invariant property of post-processing and the property of composition as follows.

Lemma 3.7 ([Bun and Steinke, 2016]). For two randomized mechanisms M1 : S n → Rd , M2 : S n × Rd → Rd . If M1 satisfies ρ1-zCDP and M2 satisfies ρ2-zCDP, then M2(S,M1(S)) satisfies (ρ1 + ρ2)-zCDP.

4 Algorithmic Framework

In this section, we present our differentially private iterative gradient hard thresholding (DP-IGHT) algorithm, which is illustrated in Algorithm 1, for solving the sparsity constrained optimization problem (1.1).

Algorithm 1 Differentially Private Iterative Gradient Hard Thresholding (DP-IGHT)

Input: loss function LS, thresholding parameters s, step size η, iteration number T, initial estimator θ0, privacy budget ρ, Lipschitz constant G

end for

Output: θT

At the core of our proposed Algorithm 1 is the gradient perturbation procedure at each iteration, which ensures the differential privacy. More specifically, we perturb the gradient with Gaussian noise at each iteration and make use of the composition and post-processing properties of differential privacy to characterize the upper bound on the total privacy loss. Compared with the objective perturbation based approaches [Chaudhuri and Monteleoni, 2009; Chaudhuri et al., 2011; Kifer et al., 2012], our algorithm does not require the optimization problem to be solved exactly in order to achieve the privacy and utility guarantees. In addition, since it is very hard to characterize the sensitivity of the optimization problem with the sparsity constraint [Xu et al., 2012], we do not pursue the output perturbation based approaches [Chaudhuri et al., 2011; Zhang et al., 2017].

According to Algorithm 1, to enforce the sparsity constraint, we use the iterative gradient hard thresholding (IGHT) algorithm, which has been shown to have a linear rate of convergence [Jain et al., 2014; Yuan et al., 2014; Chen and Gu,

2016]. Note that if we set σ2 = 0 in Algorithm 1, it will reduce to the original IGHT algorithm. The hard thresholding operator Hs(·) in Algorithm 1 is defined as follows:

Hs(θ) preserves the top s elements in θ in terms of magnitude and set others to be zero. We will show later that the proposed DP-IGHT algorithm also enjoys a linear convergence rate, and therefore is more efficient than existing methods.

5 Main Results

In this section, we first present the main theoretical properties of Algorithm 1 for generic models, and then show its applications to two specific examples: sparse linear regression and sparse logistic regression.

Recall that the goal of sparse learning is to estimate the underlying sparse parameter vector θ∗ of a statistical model. Thus, we impose a high probability upper bound on the gradient of the objective function at θ∗ , which is used to characterize the statistical error of different statistical models.

Condition 5.1. For a given sample size n and tolerance parameter γ ∈ (0, 1), let ε(n, γ) be the smallest scalar such that with probability at least 1 - γ, we have

where ε(n, γ) depends on the sample size n and γ.

Equipped with this condition, we are ready to establish the main theoretical results of Algorithm 1.

5.1 Results for Generic Model

We first present the privacy guarantee of Algorithm 1 for solving sparse learning problem (1.1) under ρ-zCDP.

Theorem 5.2. Suppose each component function ℓi of LS is G-Lipschitz continuous, the output θT of Algorithm 1 satisfies ρ-zCDP after T iterations if σ2 = TG2 /(n2ρ).

Remark 5.3. According to Lemma 3.4, we can also derive that the output θT of Algorithm 1 satisfies (ϵ, δ)-DP if σ2 = TG2 /(n(√log(1/δ) + ϵ - √log(1/δ)))2 . Furthermore, if ϵ ≤ log(1/δ), we can get σ2 ≤ 6TG2 log(1/δ)/(nϵ)2 , which matches the bound of the noise variance for gradient perturbation methods [Wang et al., 2017]. Note that for the Lipschitz parameter G, we can exactly calculate a tight upper bound for sparse linear regression and sparse logistic regression. However, for general loss functions, one practical approach to choose G is to use gradient clipping [Abadi et al., 2016].

Next, we provide the utility guarantee of Algorithm 1 for solving sparse learning problem (1.1).

Theorem 5.4. Suppose the loss function LS satisfies sparse eigenvalue condition with parameters µ, β, and Condition 5.1, and each component function ℓi is G-Lipschitz continuous. There exist constants {Ci}5i=1 such that if σ2 = TG2 /(n2ρ), η = C1/(β + µ), and s ≥ C2κ2 s∗ , then θT converges to θ∗ at a linear rate. In addition, if we choose T = C3κ log (ρn2µ2 ‖θ∗ ‖22 /(κ2G2 s log d)), the following holds with probability at least 1 - γ

where the expectation is taken over the randomness of the Gaussian noises in Algorithm 1.

Remark 5.5. The utility bound in (5.1) consists of two terms: the first one denotes the statistical error, while the second term corresponds to the error introduced by the Gaussian mechanism. It is worth noting that the error term caused by the Gaussian mechanism depends on s∗ log d instead of d comparing with the previous differentially private learning algorithms [Bassily et al., 2014]. According to Lemma 3.4, we can also derive the following utility guarantee under (ϵ, δ)-DP

and we defer such result to the supplemental material.

5.2 Implications for Specific Examples

In this subsection, we demonstrate the implications of the main theory for Algorithm 1 when it is applied to specific examples. Note that here we directly spell out the utility results under (ϵ, δ)-DP for the ease of comparison.

Sparse Linear Regression

The first example we considered is the linear regression problem in the high-dimensional regime yi = 〈xi, θ∗ 〉 + ξi, where y = [y1, . . . , yn] ∈ Rn denotes the response vector, X = [x1, . . . , xn]⊤ ∈ Rn×d is the design matrix, ξ = [ξ1, . . . , ξn] ∈ Rn is a noise vector, and θ∗ ∈ Rd with ‖θ∗ ‖0 = s∗ is the underlying sparse regression coefficient vector that we want to recover. In the high-dimensional regime, we have n ≪ d. In order to estimate the sparse parameter vector θ∗ , according to (1.1), we consider the following sparsity constrained optimization problem, which has been studied in many previous works [Zhang, 2011; Yuan et al., 2014; Jain et al., 2014; Chen and Gu, 2016]

where we have each component function as ℓi(θ) = (〈xi, θ〉 - yi )2 /2. The next corollary provides the privacy and utility guarantees of Algorithm 1 for solving (5.2).

Corollary 5.6. Suppose each row of the design matrix xi is an independent sub-Gaussian random vector with ‖xi‖2 ≤ K, and the noise vector ξ ∼ N(0, ν 2 In). For a given privacy budget ϵ > 0 and a constant δ ∈ (0, 1), there exist constants {Ci}3i=1 such that if n ≥ C1s log d, and we choose σ2 = 2λTK2 (√2s‖θ∗ ‖2 + ν logn)2 log(1/δ)/(n2 ϵ2 ), appropriate η, large enough s, then for T = C2κ log (n2 ϵ2 /(sK2 log d log(1/δ))), the output θT of Algorithm 1 satisfies (ϵ, δ)-DP. In addition, with probability at least 1 - exp(-C3n), we have

where C4,C5 are some constants depending on log terms, which are small constants.

Remark 5.7. Corollary 5.6 implies that our algorithm achieves O(s∗ log d/n + s∗2 log d log(1/δ)/(n2 ϵ2 )) utility guarantee in the setting of (ϵ, δ)-DP. The term O(s∗ log d/n) denotes the statistical error for sparse vector estimation, which matches the minimax lower bound [Raskutti et al., 2011]. The term O(s∗2 log d log(1/δ)/(n2 ϵ2 )) corresponds to the error introduced by the Gaussian mechanism, which matches the best known result [Kifer et al., 2012].

Sparse Logistic Regression

For logistic regression, we assume that each observation yi is drawn from the following Bernoulli distribution P(yi = 1|xi, θ∗ ) = exp (〈θ∗ , xi〉 - log (1 + exp(〈θ∗ , xi〉))), where xi ∈ Rd is the predictive vector, θ∗ ∈ Rd with ‖θ∗ ‖0 = s∗ is the underlying parameter vector we want to recover. According to (1.1), we propose to solve the following sparsity constrained maximum likelihood estimation problem [Yuan et al., 2014; Li et al., 2016; Chen and Gu, 2016]

where we have each component function as ℓi(θ) = log (1 + exp(〈θ, xi〉)) - yi〈θ, xi〉. We have the following theoretical guarantees for sparse logistic regression.

Corollary 5.8. Suppose each row of the design matrix xi is independent sub-Gaussian random vector and ‖xi‖2 ≤ K. For a given privacy budget ϵ > 0 and a constant δ ∈ (0, 1), there exist constants {Ci}4i=1 such that if n ≥ C1s log d, and we choose σ2 = TK2 log(1/δ)/(n2 ϵ2 ), appropriate η, large enough s, then for T = C2κ log (n2 ϵ2 /(sK2 log d log(1/δ))), the output θT of Algorithm 1 is (ϵ, δ)-DP. In addition, with probability at least 1 - exp(-C3n) - C4/d, we have

where C5,C6 are some constants depending on log terms, which are small constants.

Remark 5.9. In the setting of (ϵ, δ)-DP, our proposed algorithm can achieve O(s∗ log d/n + s∗ log d log(1/δ)/(n2 ϵ2 )) utility guarantee after T = O(log (n2 ϵ2 /s)) iterations. In particular, the termO(s∗ log d/n) corresponds to the statistical error, while the term O(s∗ log d log(1/δ)/(n2 ϵ2 )) denotes the error caused by the Gaussian mechanism. To the best of our knowledge, this is the first utility guarantee for sparse logistic regression.

6 Numerical Experiments

In this section, we present experimental results of our proposed algorithm on both synthetic and real datasets. We compare our algorithm with Two stage [Kifer et al., 2012] and Frank-Wolfe [Talwar et al., 2015] methods. Although these two approaches were originally proposed for sparse linear regression, and have no theoretical guarantees for sparse logistic regression, they can still be applied to sparse logistic regression and produce reasonable empirical results. Thus we also include them as two baselines for sparse logistic regression. For all the experiments, we choose the variance of the random noise of different methods as suggested by their theoretical guarantees, and select other parameters, such as the step size, iteration number, and thresholding parameter by five-fold cross-validation. Note that we use the non-private iterative gradient hard thresholding method as the non-private baseline. In contrast to DP-IGHT, the non-private IGHT does not add any noise in the gradient step.

6.1 Synthetic Data Experiments

We first investigate the performances of different methods on synthetic datasets for sparse linear and logistic regression.

Sparse Linear Regression. For sparse linear regression, the underlying sparse vector θ∗ has s∗ nonzero entries that are drawn independently from a uniform distribution over the interval (-1, 1). We generate the design matrix X ∈ Rn×d such that each element of X follows i.i.d. uniform distribution over the interval (-2, 2), then we scale each row xi such that ‖xi‖2 ≤ 2s∗ . The observation is generated according to y = X⊤θ∗ + ξ, where the noise vector ξ ∼ N(0, ν 2 I) with ν 2 = 0.1. We consider the following settings: (i) n = d = 1000, s∗ = 10; (ii) n = d = 5000, s∗ = 30. We set δ = 0.01 and vary the privacy budget ϵ from 2 to 10. Note that due to the hardness of the problem itself, we choose relatively large privacy budgets compared with the low-dimensional problem to ensure meaningful results. Figure 1(a) and 1(b) illustrate the relative estimation error ‖̂ θ - θ∗ ‖2/‖θ∗ ‖2 versus privacy budget of different methods over 10 trails. We can see that the relative estimation errors of our method are close to the non-private baseline (IGHT), and are better than existing private methods.

Sparse Logistic Regression. For sparse logistic regression, we generate the underlying sparse vector θ∗ and the design matrix X ∈ Rn×d in the same way as sparse linear regression. Each observation yi is generated from the following logistic distribution

We also consider the following two settings: (i) n = 1000, d = 1000, s∗ = 10; (ii) n = 5000, d = 5000, s∗ = 30. In addition, we choose the privacy budget ϵ from 2 to 10, and set δ = 0.01. We demonstrate the relative estimation error ‖̂ θ - θ∗ ‖2/‖θ∗ ‖2 versus privacy budget ϵ of different methods in Figure 1(c) and 1(d). The results show that our method can output accurate estimators when we have relative large privacy budget. In addition, it consistently outperforms the baseline algorithms under different privacy budget.

6.2 Real Data Experiments

In this experiment, we use two real datasets, E2006-TFIDF dataset [Kogan et al., 2009] and RCV1 dataset [Lewis et al., 2004], for the evaluation of sparse linear regression and sparse logistic regression, respectively.

E2006-TFIDF Data. For sparse linear regression problem, we use E2006-TFIDF dataset, which consists of financial risk data from thousands of U.S. companies. In detail, it contains 16087 training examples, 3308 testing examples, and we randomly sample 50000 features for this experiment. In addition, we set s∗ = 2000, δ = 0.01, ϵ ∈ [2, 10]. Table 2 reports the mean square error (MSE) on the test data of different methods for various privacy budgets over 10 trails. In specific, MSE on the test data is defined as follows: ‖X⊤test ̂ θ - ytest‖22 /(2ntest), where {Xtest, ytest} are the test data, ntest is the number of test examples, and ̂ θ is the estimator learned on the training data. The results in Table 2 show that the performance of our algorithm is close to the non-private baseline (i.e., IGHT), and is much better than Frank-Wolfe and Two stage.

RCV1 Data. In order to compare different algorithms for sparse logistic regression, we use RCV1 dataset, which is a Reuters Corpus Volume I data set for text categorization research. More specifically, RCV1 is an archive of over 800000 manually categorized newswire stories made available by Reuters, Ltd. for research purposes. It contains 20242 training examples, 677399 testing examples and 47236 features. We use the whole training dataset and a subset of the test dataset, which contains 20000 testing examples for our experiment. In detail, we set s∗ = 500, δ = 0.01, ϵ ∈ [2, 10]. We compare all algorithms in terms of their classification error on the test set over 10 replications, which is summarized in Table 3. It is obvious that our algorithm achieves the lowest test error among private algorithms on RCV1 dataset, which demonstrates the superiority of our algorithm.

7 Conclusions

In this paper, we proposed a privacy preserving iterative gradient hard thresholding algorithm for sparse learning. We establish a linear convergence rate and strong utility guarantee of our algorithm. Experiments on both synthetic and real world data demonstrate the superiority of our algorithm.

Acknowledgements

This research was sponsored in part by the National Science Foundation SaTC-1717950.