Private Estimation and Inference in High-
Dimensional Regression with FDR Control

In the era of big data, the significance of data privacy has grown considerably. With the continuous collection, storage, processing, and sharing of vast amounts of personal data (Lane et al., 2014), there is a pressing need to protect sensitive information. Traditional data analytics and statistical inference tools, unfortunately, may fall short in ensuring such protection. However, the concept of differential privacy, initially proposed by theoretical computer scientists (Dwork et al., 2006), has made substantial progress and found widespread use in various large-scale applications. In essence, differentially private algorithms incorporate random noise that is independent of the original database and produce privatized summary statistics or model parameters. The ultimate goal of differentially private analysis is to safeguard individual data while still allowing meaningful statistical analysis of the original database.

In this paper, we develop a novel framework that enables differentially private statistical inference in high-dimensional linear regression. Let $Y\in{\mathbb{R}}$ be the response and $X\in{\mathbb{R}}^{p}$ be the covariates. Assume the linear model

where $e$ denotes the noise term and follows the sub-Gaussian distribution. Assume that $\{\bm{x}_{i},y_{i}\}_{i=1}^{n}$ are independent samples. We are interested in the high-dimensional setting where $p$ may grow exponentially with $n$, and only a small subset of ${\bm{\beta}}$ have non-zero values. We aim to develop practical differentially private estimation and inference methods for the parameter ${\bm{\beta}}$, and a false discovery rate control procedure when multiple testing is concerned.

Numerous approaches have been developed to address the challenge of statistical inference in high-dimensional linear regression, under the typical non-private setting. Wasserman and Roeder (2009) applied sample-splitting for high-dimensional inference, where the estimation and inference are conducted on different samples. Later on, the debiased lasso (Zhang and Zhang, 2014; Javanmard and Montanari, 2014; Van de Geer et al., 2014) emerged as a technique capable of mitigating the potential bias arising from the Lasso estimator, thereby providing asymptotically optimal confidence intervals for regression coefficients. Additionally, Ning and Liu (2017) proposed a method for constructing confidence intervals for high-dimensional penalized M-estimators based on decorrelated score statistics, while Shi et al. (2021) developed a recursive online-score estimation approach. More recently, Wang et al. (2022) introduced the repro framework, which enables the construction of valid confidence intervals for finite samples with high-dimensional covariates.

Besides conducting inference on one parameter, another desired feature in high dimensional linear regression is to control the false discovery rate (FDR) of the selected variables. This objective has led to the development of various FDR control methods in the literature. One such method, proposed by Liu (2013), focuses on the Gaussian graphical model and utilizes the asymptotic normality of the test statistic (Liu, 2013). Another influential approach is the knockoff framework introduced by Barber and Candès (2015), which exploits the symmetry of the statistics under the null hypothesis. Since its inception, the knockoff method has undergone further development and generalization, finding applications in diverse settings (Candes et al., 2018; Barber and Candès, 2019; Romano et al., 2020). Recently, Dai et al. (2022) proposed a method that combines the idea of symmetric mirror statistics and data splitting to control the FDR asymptotically. The power of this method can be further enhanced by implementing a multiple-split approach. Dai et al. (2023) extended this idea to generalized linear models, expanding its applicability.

Addressing privacy concerns in various statistical inference scenarios has gained significant attention in recent literature. Avella-Medina et al. (2023a) put forth the utilization of first-order and second-order optimization algorithms to develop private M-estimators, and they conducted an analysis of the asymptotic normality of these private estimators, accompanied by an evaluation of their privacy error rate. The extension of these methodologies to the high dimensional setting is further discussed in Avella-Medina et al. (2023b), albeit not published yet. Moreover, the multiple testing problem has also been a subject of recent investigation. Dwork et al. (2021) proposed the DP-BH method, while Xia and Cai (2023) introduced the DP-Adapt method, which provides control over the false discovery rate (FDR) while guaranteeing finite sample performance.

Our paper contributes to the differentially private analysis of high-dimensional linear regression in several key aspects.

1. 1.

   We propose a differentially private Bayesian Information Criterion (BIC) to accurately select the unknown sparsity parameter in DP-Lasso proposed by Cai et al. (2021), eliminating the need for prior knowledge of the model sparsity. This advancement enhances the reliability of the DP-Lasso framework and can be used in many downstream tasks.

2. 2.

   We develop a differentially private debiased Lasso procedure which can produce asymptotic normal estimators with privacy. This procedure provides differentially private confidence interval for a single parameter of interest.

3. 3.

   We design a differentially private procedure for controlling FDR in multiple testing scenarios. Our approach allows for FDR control at any user-specified rate $\alpha$ and exhibits asymptotic power approaching 1 under proper conditions.

The structure of this paper is as follows. In Section 2, we present a formulation of the problem of interest and propose a new estimation of DP-Lasso that do not require the knowledge of sparsity. In Section 3, we introduce the differentially private debiased Lasso algorithm and provide its asymptotic distribution and privacy error. Section 4 presents a novel differentially private false discovery rate (FDR) control method that leverages sample splitting and mirror statistics. We also elucidate the reasons why existing FDR techniques are inapplicable in the context of differential privacy. In Section 5, we present extensive simulations and real data analysis to validate the performance of our proposed methods. Finally, in Section 6, we conclude the article with a discussion of our findings and outline potential future research directions. All proofs are provided in the appendix.

Notation: Throughout the paper, we use the following notation. For any $p$-dimensional vector $\bm{x}=(x_{1},\dots,x_{p})^{\top}$, we define the $l_{q}$-norm of $\bm{x}$ as $\|\bm{x}\|_{q}:=(\sum_{i=1}^{p}|x|_{i}^{q})^{1/q}$ for $1\leq q$, with $|\cdot|$ representing the absolute value. The $\text{supp}(\bm{x})=\{i:|x_{i}|>0\}$ is the index set of nonzero elements in $\bm{x}$. We define the $l_{0}$-norm of $\bm{x}$ by $\|\bm{x}\|_{0}=\#\text{supp}(\bm{x})$, which is number of nonzero coordinates of $\bm{x}$. For a positive integer $n$, we use $[n]$ to denote the set $\{1,\dots,n\}$. For a subset $\mathcal{S}\subseteq[k]$ and vector $\bm{x}\in\mathbb{R}^{n}$, we use $\bm{x}_{\mathcal{S}}$ to denote the restriction of vector $\bm{x}$ to the index set $\mathcal{S}$. For a vector $\bm{x}\in\mathbb{R}^{n}$, we use $\Pi_{R}(\bm{x})$ to denote the projection of $\bm{x}$ onto the $l_{2}$-ball $\{\bm{u}\in\mathbb{R}^{p}:\|\bm{u}\|_{2}\leq R\}$. Let $X$ and $\{X_{n}\}_{n=1}^{\infty}$ be random variables. The expression $X_{n}\xrightarrow{D}X$ denotes the convergence of $X_{n}$ to $X$ in distribution. Similarly, the notation $X_{n}=O_{P}(a_{n})$ indicates that the random variable $X_{n}/a_{n}$ is stochastically bounded.

Consider the dataset $D:=\{(\bm{x}_{i},y_{i})\}_{i=1}^{n}\in\mathcal{D}$ that are drawn from the distributions satisfying

where $e_{i}\stackrel{{\scriptstyle i.i.d.}}{{\sim}}N(0,\sigma^{2})$, ${\bm{\beta}}\in{\mathbb{R}}^{p}$ and $\|{\bm{\beta}}\|_{0}\leq s$. In this paper, we are interested in the high-dimensional setting where the dimension $p$ may grow exponentially with the sample size $n$, under the $(\epsilon,\delta)$-differential privacy framework. We begin by introducing the background of differential privacy, with its formal definition as follows.

In the definition, two data sets $D$ and $D^{\prime}$ are treated as fixed, and the probability measures the randomness in the mechanism $M(\cdot)$. The level of privacy against an adversary is controlled by the pre-specified privacy parameters $(\epsilon,\delta)$. When $\epsilon$ and $\delta$ are small, the algorithm offers strong privacy guarantees.

One of the most useful concepts in differential privacy is the sensitivity, which characterizes the magnitude of change in the algorithm when only one single individual in the dataset is replaced by another element.

Next, we introduce two well-known mechanisms: the Laplace mechanism, which is $(\epsilon,0)$ differential privacy for algorithms with bounded $l_{1}$ sensitivity, and the Gaussian mechanism, which achieves $(\epsilon,\delta)$ differential privacy for algorithms with bounded $l_{2}$ sensitivity.

Differentially private algorithms have other nice properties that will be useful for our analysis, as summarized in the following lemma.

In high-dimensional problems, parameters of interest are often assumed to be sparse. Reporting the entire estimation results can result in a substantial variance. Fortunately, exploiting the sparsity assumption allows us to selectively disclose only the significant nonzero coordinates. The “peeling” algorithm (Dwork et al., 2021) is a differentially private algorithm that addresses this problem by identifying and returning the top-$s$ largest coordinates based on the absolute values. Since its proposal by Dwork et al. (2021), this algorithm has been popular in protecting privacy for high-dimensional data, see for example, applications in Cai et al. (2021) and Xia and Cai (2023).

The estimation of regression parameters in the high-dimensional private setting has been studied in Cai et al. (2021) with optimality guarantees. However, the algorithm in Cai et al. (2021) requires prior knowledge of the sparsity parameter $s$, which are typically unknown in practice. In this section, we propose a differentially private Bayesian Information Criterion (BIC) in Algorithm 2 to accurately select the unknown sparsity parameter, eliminating the need for prior knowledge of the model sparsity. The pipeline of the proposed estimation algorithm is as follows.

The random sample splitting in the proposed algorithm is equivalent to employing the stochastic gradient descent algorithm with one pass of the entire dataset. Moreover, our choice to use the powers of 2 as candidate values of the sparsity parameter accomplishes two critical goals: firstly, it ensures that the candidate set covers the true model by defining an interval where $s$ falls, such that $s^{*}<s<2s^{*}$ where $s^{*}$ is in the candidate set; secondly, it limits the total number of candidate models to $\log n$, which is indeed $o(n)$. The choice of $K=\log_{2}(\sqrt{n}/\log^{2}p)$ aligns with the sparsity requirement for statistical inference, as will be discussed in Section 4.

Condition 3.1 is commonly assumed in the high-dimensional literature; for example, see Javanmard and Montanari (2014). The bound on the infinity norm of the design matrix $c_{x}$ can be relaxed to hold with high probability, which can be easily obtained for sub-Gaussian distributions. Different from the algorithm proposed by Cai et al. (2021), we employ a data-splitting technique in the algorithm to establish independence between $\bm{\beta}^{(t)}$ and the sub-data $\bm{x}_{i}$ utilized in the $t$-th iteration. Notably, our Condition 3.1 is less stringent than the design conditions outlined in Cai et al. (2021). This reduction in conditions comes at the cost of decreasing the effective sample size by a factor of $1/T$. As demonstrated in Theorem 3.1, the number of iterations, denoted as $T$, adheres to $T=O(\log(n))$, resulting in an associated error bound increase of $O(\log(n))$. Condition 3.2 assumes the bound and sparsity for the true parameter ${\bm{\beta}}$. Lemma 3.1 provides the privacy guarantee of Algorithm 2, where we only require condition 3.1.

Now we establish the error bound of the new estimation algorithm.

The upper error bound matches the minimax lower bound presented in Cai et al. (2021) up to a logarithmic factor of $n$, which is considerably small. In comparison to algorithms with a known sparsity level $s$, our proposed algorithm introduces an additional factor of $\log(n)$ in both the statistical error component and the privacy cost component. This arises from our use of data-splitting in the estimation process, along with the output of a total of $K$ estimates and the utilization of the BIC for selecting the “optimal” model.

The selection of candidate models presents a delicate balance. Firstly, we desire the candidate set to encompass the true model, necessitating the inclusion of a sufficient number of potential models. Secondly, privacy constraints impose limitations on the total number of outputs. Consequently, the number of candidate models must be on the order of $o(n)$ for consistent estimation.

In this section, we construct the confidence interval for a particular regression coefficient $\beta_{j}$, $j\in[p]$ under $(\epsilon,\delta)$-differential privacy. Following the debiased Lasso framework (Zhang and Zhang, 2014; Van de Geer et al., 2014; Javanmard and Montanari, 2014), we first estimate the precision matrix $\bm{\Omega}:=\bm{\Sigma}^{-1}$ with differential privacy. Note that for $\bm{w}_{j}=\{\bm{\Sigma}^{-1}\}_{.,j}$, it satisfies the linear equation $\bm{e}_{j}=\bm{\Sigma}\bm{w}_{j}$. Thus it is the unique minimizer of the following convex quadratic function:

In addition, we assume the $\bm{w}_{j}$ is sparse.

Given a pre-specified sparsity level $s_{j}$, the differentially private estimation of $\bm{w}_{j}$ algorithm is presented in Algorithm 7.

Theoretical properties of Algorithm 7 are outlined in Lemma 8.1. Similar to Algorithm 2, we once again employ the data-splitting technique to relax design-related conditions. Our approach shares similarities with the concept of node-wide regression introduced in Van de Geer et al. (2014). What sets our approach apart is its simultaneous estimation of the entire vector. This confers the advantage of privacy cost reduction by avoiding the separate estimation of node-wise regression parameters and error variance.

This condition is necessary to facilitate differentially private estimation of the precision matrix. We proposed to use a BIC criterion to select the optimal model following a similar approach when the sparsity level $s_{j}$ is unknown. The algorithm for estimating $\bm{w}_{j}$ is summarized in Algorithm 4. Based on the sparsity assumption, we can follow a similar approach as in Algorithm 2 to utilize the DP-BIC to select the unknown sparsity parameters $s_{j}$. Lemma 4.2 shows that under certain regularity conditions, Algorithm 4 is $(\epsilon,\delta)$-differentially private.

The theoretical property of $\hat{\bm{w}}_{j}$ by Algorithm 4 is shown in Lemma 4.3. Compared to the case when the sparsity level is known, the proposed algorithm introduces an additional factor of $\log(n)$ in the privacy cost component of the error bound due to the DP-BIC selection. Using the “tracing attack” technique developed in Cai et al. (2021), one can easily show that the error bound in Lemma 4.3 matches the minimax lower bound up to a logarithmic factor of $n$.

After obtaining the private estimator $\hat{\bm{w}}_{j}$, we propose the following de-biased estimator to facilitate private inference:

where $z_{j}\sim N(0,\{\frac{4R^{2}}{n}\}^{2}\cdot\frac{2\log(1.25/\delta)}{\epsilon^{2}})$. Different from the non-private debiased estimator in Van de Geer et al. (2014), additional random noise $z_{j}$ is to guarantee the $(\epsilon,\delta)$-differentially private by the Gaussian mechanism. Due to the privacy constraints, the variance analysis of $\hat{\beta}_{j}^{(db)}$ turns out to be different from Van de Geer et al. (2014). Specifically, we could write The following lemma provides theoretical insights for the decomposition of the private debiased estimator $\hat{\beta}^{(db)}_{j}$.

Therefore, to obtain a differentially private confidence interval, we need to estimate the variance privately. Note that the estimate of $\Omega_{j,j}$ can be obtained directly from $\hat{w}_{j,j}$. Therefore, it suffices to estimate $\sigma^{2}$. We propose the following differentially private estimation of $\sigma^{2}$:

where $Z\sim N(0,\{\frac{2(2R)^{2}}{n}\}^{2}\cdot\frac{2\log(1.25/\delta)}{\epsilon^{2}})$.

For the reader’s convenience, we summarize the entire algorithm for obtaining differentially private confidence interval for $\beta_{j}$ in the high-dimensional setting. Specifically, the algorithm consists of four steps, and we allocate $(\epsilon/4,\delta/4)$ privacy budget for each step: (1) estimating the regression parameters $\hat{\bm{\beta}}$; (2) estimating the precision matrix column $\hat{\bm{w}}_{j}$; (3) estimating the debiased estimator $\hat{\beta}_{j}^{(db)}$; and (4) estimating the standard error of the debiased estimator. Our algorithm ensures that each of the four steps are $(\epsilon/4,\delta/4)$- differentially private, thus Algorithm 5 itself is $(\epsilon,\delta)$-DP. The privacy guarantee together with the nominal coverage of the confidence interval is summarized in Theorem 4.1.

Theorem 4.1 demonstrates that the proposed confidence interval provides asymptotic nominal coverage while ensuring privacy. Nevertheless, in finite samples, we suggest incorporating a minor correction to the confidence interval to enhance the finite-sample performance of our method. A similar approach was previously discussed by Avella-Medina et al. (2023a) in the context of low-dimensional noisy gradient descent and noisy Newton’s method algorithms. Note that the proposed debiased estimator (4.1) incorporates additional noise, denoted as $z_{j}$, which is generated from a Gaussian distribution with a known variance. The confidence interval, with finite-sample correction, is defined by accounting for the variance of $z_{j}$ as follows:

where $V_{c}=16\{\frac{4R^{2}}{n}\}^{2}\cdot\frac{2\log(4*1.25/\delta)}{\epsilon^{2}}$ represents the variance of $z_{j}$. It’s worth noting that the additional variance term $V_{c}$ is $O(n^{-2})$, which diminishes as $n$ approaches infinity. Consequently, the corrected confidence interval remains asymptotically efficient compared to the debiased lasso.

False Discovery Rate (FDR) control with privacy under the high-dimensional linear model is a difficult problem. Current approaches to achieving differentially private FDR control (Dwork et al., 2021; Xia and Cai, 2023) require the mutual independence of $p$-values under the null hypotheses, and this assumption does not necessarily hold in the context of linear regression problems. The differentially private knockoff method introduced by Pournaderi and Xiang (2021) has two severe limitations: firstly, it requires the dimension $p$ to be smaller than the sample size $n$; secondly, the introduced noise for privacy preservation overwhelms the signal. To generate differentially private knockoff features, Pournaderi and Xiang (2021) proposed adding noise with a standard error proportional to the upper bound of the signal. Consequently, even when $p$ remains fixed and $n$ approaches infinity, the added noise dominates the signal. The effectiveness of Pournaderi and Xiang (2021)’s method is severely limited. The question of how to construct differentially private knockoff features with a reasonably small amount of added noise remains an open challenge.

Our approach draws inspiration from the recent advancements in mirror statistics, as demonstrated in the works of (Dai et al., 2022, 2023). In particular, the utilization of sample splitting and post-selection techniques allows us to effectively reduce the dimensionality of the model from high to relatively low dimensions. This reduction in dimensionality enables us to manage the scale of noise required for privacy preservation more effectively. Our approach shares similarities with the peeling algorithm proposed by (Dwork et al., 2021) and the mirror peeling algorithm introduced by (Xia and Cai, 2023). Specifically, we divide the data into two parts, denoted as $\mathcal{D}_{1}$ and $\mathcal{D}_{2}$. Initially, we employ the high-dimensional differentially private sparse linear regression algorithm (Algorithm 2) using $\mathcal{D}_{1}$. The resulting estimator is denoted as $\tilde{{\bm{\beta}}}{(1)}$, with its support represented by $\mathcal{A}:=\{i\in[p]:\tilde{\beta}_{(1)i}\neq 0\}$. Subsequently, we utilize $\mathcal{D}_{2}$ to fit a differentially private ordinary least squares algorithm, employing the estimated active support $\mathcal{A}$, and denote the resulting estimator as $\tilde{{\bm{\beta}}}_{(2)}$. For all $j\in\mathcal{A}$, we define mirror statistic $M_{j}$ by

Similar as in Dai et al. (2022), $f(u,v)$ can take different choices such as

The data-driven cutoff $\tau_{q}$ is defined as

where $q$ is the desired FDR level. We select the subset of variables $\mathcal{A}_{\tau_{q}}=\{i\in\mathcal{A}:M_{j}>\tau_{q}\}$ as the important variables. Define $\mathcal{S}:=\{i\in[p]:\beta_{i}\neq 0\}$ as the true support set and $\bar{\mathcal{S}}=[p]-\mathcal{S}$ as the complementary set of $\mathcal{S}$. The false discovery proportion (FDP), FDR and power of proposed selection procedure are defined as following:

We summarize the details of the algorithm in Algorithm 6. The privacy guarantee of the proposed procedure is provided in Lemma 5.1.

Under regularized conditions, the proposed method controls the FDR asymptotically at user-specified level $q$ and power goes to $1$. We summarize those results in Theorem 5.1.