Differentially Private Model Selection with Penalized and Constrained Likelihood

Introduction

In data privacy research, the goal of data analysis is to provide accurate and useful statistical inference while preventing individual records being identified. Such privacy protection is crucial in many statistical applications, namely for the analysis of census and survey data, medical and clinical studies, genetics data, and web user data collected on the internet. In statistics, the treatment of confidential data has a long history under the name of “Statistical Disclosure Control” or “Statistical Disclosure Limitation”; see for example Dalenius 1977, Rubin 1993, Willenborg & De Waal 1996, Fienberg & Slavković 2010 and Hundepool et al. 2012. A long lasting challenge is to rigorously quantify the disclosure protection offered by privacy-preserving data analysis procedures.

The notion of differential privacy has been introduced with the same objective in theoretical computer science by Dwork 2006 and Dwork et al. 2006. The general idea of differential privacy is to require for the outcome of a randomized data analysis procedure not to change much for small perturbations of the input data, so that one can not infer from the output the presence or absence of any individual in the input data set, or infer some of the person’s characteristics. This requirement can be rigorously quantified, and does not depend on assumptions regarding the resources of the intruder, including any access to auxiliary information. Thus, differential privacy compares very favorably to measures of disclosure risk commonly used in the statistical disclosure control literature as it is more encompassing and a worst case definition, but at the same time it has been criticized as too stringent from the perspective of achieving needed statistical data utility; e.g., see Fienberg et al. 2010; Karwa & Slavkovic 2012.

Over the last decade, there has been a rapid development of differentially private algorithms and procedures in both the computer science and statistics literature. For example, the main focus in the computer science literature was on designing differentially private mechanisms and efficient algorithms for private data release, e.g., the Laplace noise perturbation mechanism (Dwork et al. 2006), the exponential mechanism (McSherry & Talwar 2007), releasing contingency tables (Barak et al. 2007), and boosting Hardt et al. 2010. On the statistics side, research efforts include designing consistent and efficient differentially private point estimators (Dwork & Lei 2009; Smith 2011; Chaudhuri et al. 2011; Lei 2011; Bassily et al. 2014; Karwa & Slavković 2016), non-parametric density estimation (Wasserman & Zhou 2010), hypothesis testing (Fienberg et al. 2011; Johnson & Shmatikov 2013; Uhler et al. 2013; Yu et al. 2014; Karwa et al. 2014; Solea 2014; Dwork et al. 2015; Sheffet 2015; Wang et al. 2015; Gaboardi et al. 2016), and statistical lower bounds (Chaudhuri & Hsu 2011; Duchi et al. 2013); there is also a large literature on private PAC learning, which echoes the concerns of statistical estimation in the context of classification (Kasiviswanathan et al. 2011; Beimel et al. 2010; Beimel et al. 2014; Beimel et al. 2015; Bun et al. 2015; Karwa et al. 2015).

In this paper we consider statistical model selection under the constraint of differential privacy. Despite the fast development in combining statistical theory and methodology with differential privacy, model selection under privacy constraints has not been well understood. The problem of differentially private model selection is motivated by practical concerns: when private data analysis procedures are needed, it is rarely known which model is most appropriate for the data. When releasing the whole dataset is impractical due to privacy concerns and releasing point estimates for pre-specified models has limited utility, an appropriate compromise is to first identify the best model and then obtain and release consistent point estimates for this model. Both tasks need to be performed under privacy constraints, and thus we need methods for differentially private model selection.

In particular, we focus on the classical linear regression model selection. In particular, we aim to provide insights for the following two questions. (i) Is it theoretically possible to do model selection with differential privacy under the classical conditions? (ii) What new practical concerns arise in model selection when differential privacy is required?

The remainder of the paper is organized as follows: In section 2, we review the definition and interpretation of differential privacy, as well as two general methods to create differentially private algorithms. Section 3 details the two proposed differentially private model selection procedures, with proofs of their privacy guarantee, and notes on the choice of the tuning parameters. Statements and proofs of the utility guarantee of the two algorithms are given in section 4. Empirical results, including a simulation study and two real data examples are reported in section 5. Section 6 provides a brief discussion. All proofs and technical details are collected in section 7.

Differential privacy

Differential privacy requires that the output of a procedure is not drastically altered under small perturbations of the input data set, such that an attacker, regardless of his auxiliary information and computing power, can hardly recover the presence/absence of a particular individual in the data set. The notion of differential privacy is a property of that data analysis procedure, rather than of the output obtained.

To formalize, consider a data set $D=\{z_{1},...,z_{n}\}\in\mathcal{Z}^{n}$ consisting of $n$ data points in sample space $\mathcal{Z}$. A data analysis procedure $\mathcal{T}$, possibly randomized, maps the data set $D$, together with a random input $\omega$, to $\mathcal{T}(D)\equiv\mathcal{T}(D,\omega)\in S$, an output space. Here we assume that $(S,\mathcal{S})$ is a measurable space and $\mathcal{T}(D,\cdot):\Omega\mapsto S$ is a measurable function. Whenever it is not confusing, we will use $\mathcal{T}(D)$ to denote the random variable $\mathcal{T}(D,\omega)$.

We can now state formally the property of differential privacy:

Given a privacy parameter, $\epsilon>0$, the procedure $\mathcal{T}$ satisfies $\epsilon$-differential privacy if

where we define $\log\frac{0}{0}=0$ for convenience.

In the above notation, $P_{\omega}$ denotes the probability with respect to $\omega$, which is the source of randomness in the data analysis procedure. Thus, the definition does not impose any conditions on the distribution of $D$ — the privacy is required to hold for all pairs of adjacent data sets. This stringent condition means that procedures which satisfy definition 1 provide very strong privacy guarantees, even against adversaries who have considerable partial information about the data set (Ganta et al. 2008). In order to satisfy this definition, any nonconstant procedure must be randomized.

The $\epsilon$-differential privacy is a strong requirement, as it takes supremum over all possible neighboring data sets of size $n$. A mild relaxation is the $(\epsilon,\delta)$-differential privacy.

Given $\epsilon>0$, $\delta\in(0,1)$, a procedure satisfies $(\epsilon,\delta)$-differential privacy if, for all measurable $A\subseteq\mathcal{S}$ and all neighboring data sets $D$, $D^{\prime}$,

Here the requirement of the original $\epsilon$-differential privacy is relaxed so that the distribution of $\mathcal{T}(D)$ only needs to be dominated by that of $\mathcal{T}(D^{\prime})$ outside of a set with probability no more than $\delta$.

In our discussion of statistical applications we will generally focus on data sets consisting of a sequence of $n$ independent random samples from an underlying distribution, and the corresponding probability will be denoted $P_{D}$. Note that differential privacy definition has no such assumption. We will use $P_{D,\omega}$ to denote the overall randomness due to both the data and random mechanism in the analysis.

2 Statistical interpretation of differential privacy

Privacy protection due to differential privacy can be interpreted from a Bayesian perspective, as in Abowd & Vilhuber 2008; Kasiviswanathan & Smith 2008. Suppose one has a prior distribution of the input data set $D$ and then gets to observe the random output $\mathcal{T}(D,\omega)$. Denote by $P_{i}$ and $Q_{i}$ the marginal prior and posterior of $X_{i}$, for the $i$th entry in $D$. Then if the procedure $\mathcal{T}$ is differentially-private and the prior $P$ is a product measure on the entries of $D$, we have that $e^{-\epsilon}\leq dP_{i}/dQ_{i}\leq e^{\epsilon}$, thus limiting the information regarding $X_{i}$ gained from the output $\mathcal{T}(D,\omega)$. A related hypothesis testing interpretation is given in Theorem 2.4 of Wasserman & Zhou 2010.

One may also intuitively interpret differential privacy as a specific notion of robustness. It requires that the distribution of $\mathcal{T}(D)$ is not changed too much if $D$ is perturbed in only one entry. However, the definition of differential privacy is also a worst case definition, where the probability ratio needs to be uniformly bounded over all pairs of adjacent input data sets. A key ingredient to designing differentially private statistical procedures is to bridge the gap between worst case privacy guarantee and the average case statistical utility. It turns out that robustness and regularization are the most relevant structures to explore, as in Dwork & Lei 2009, Chaudhuri et al. 2011 and Smith & Thakurta 2013.

3 Designing differentially private algorithms

For any statistical task which we want to carry, a specific randomized procedure $\mathcal{T}$ must be designed to take as input a database $D\in\mathcal{Z}^{n}$ and return an element of the output space $\mathcal{S}$ while satisfying differential privacy. There exists a few approaches which are generic enough to be adaptable to various tasks, and which are often used as building blocks for more complicated procedures. We present two of these methods, which we use later in the construction of our procedure. The first adds random noise to a non-private output and the second samples randomly from a set of candidate outputs.

If $G_{T}<\infty$, then it is easy to check (Dwork et al. 2006) that

satisfies $\epsilon$-differential privacy, where $\zeta$ is a standard double exponential random variable with density function $0.5\exp(-|\zeta|)$ (also known as the Laplace distribution).

Then $\mathcal{T}$ satisfies $\epsilon$-differential privacy.

When $S$ is finite, one may also use additive noise to approximately maximize $q(D,s)$ over $s$. Let

be the privatized score, where $\zeta$ is an independent draw from the standard double exponential distribution. Then

satisfies $\epsilon$-differential privacy and usually offers similar performance as the exponential mechanism.

In many statistical problems the sample space is not compact and hence $G_{T}=\infty$ for many statistics $T$ such as the sample mean. A general strategy is to show that one can add much less noise for most average case data sets with ($\epsilon$, $\delta$)-differential privacy (Dwork & Lei 2009). These methods often involves the notion of local sensitivity of a deterministic procedure $T$:

If $G_{T}(D)$ is finite and public, then one can show that adding noise to $T(D)$ as in (2) with $G_{T}$ replaced by $G_{T}(D)$ also gives $\epsilon$-differential privacy. Unfortunately, $G_{T}(D)$ depends on the data set and may contain sensitive information. However, there is a generic scheme based on this idea with valid privacy guarantee under the following two general conditions on the deterministic procedure $T$.

For all $\epsilon>0$ there exists a real-valued function $G^{*}(D)$ and a randomized procedure $\mathcal{T}_{\epsilon}(D,g)$, which is $\epsilon$-differentially private if $g\geq G^{*}(D)$ and is assumed to be non-private.

Given $\epsilon>0$ and $\delta\in(0,1)$, there exists an $\epsilon$-differentially private mapping $G_{\epsilon,\delta}(D)$ satisfying $P_{\omega}[G_{\epsilon,\delta}(D)\geq G^{*}(D)]\geq 1-\delta$ for all $D$.

An example of $G^{*}(D)$ is the local sensitivity of some procedure $T(D)$, and $\mathcal{T}$ is the noisy version as in (2) calibrated to a upper bound of the local sensitivity.

Under the above two assumptions, for any $\epsilon_{1}+\epsilon_{2}=\epsilon$, and $\delta\in(0,1)$, $\mathcal{T}_{\epsilon_{2}}(D,G_{\epsilon_{1},\delta}(D))$ satisfies $(\epsilon,\delta)$-differential privacy.

Differentially Private Model Selection Procedures

Popular methods of model selection for linear regression include information criteria such as AIC (Akaike 1974) and BIC (Schwarz et al. 1978), cross-validation (Picard & Cook 1984), and the more recent penalized least squares (Tibshirani 1996; Fan & Li 2001, e.g.,). In this paper we focus on penalized least squares and penalized profile likelihood estimators, both being variants of the classical approach based on information criteria.

Given a parameter $(\beta,\sigma^{2})$ and an observed data set, the log likelihood is, ignoring constant terms,

When $\sigma^{2}$ is known, we aim to find the $\beta$ that maximizes the log likelihood, which leads to model selection with the least squares. Without loss of generality, we assume $\sigma^{2}=1$. We then define

In the more realistic setting that $\sigma^{2}$ is unknown, we can maximize over the nuisance parameter $\sigma^{2}$ to perform model selection with the profile likelihood. Ignoring constant terms, we obtain the profile log-likelihood for $\beta$:

Maximizing this over all $\beta$ in $\Theta_{M}$, we get

where $\phi_{n}$ is the amount of penalty on the model complexity. The best known and most widely used examples are the AIC ($\phi_{n}=2$), and BIC ($\phi_{n}=\log n$).

In the case of known $\sigma^{2}$, the penalized minimization becomes

It is worth noting that the penalized least square estimator, with appropriate choice of $\phi_{n}$, can also be used in the case of unknown $\sigma^{2}$.

2 Towards Differentially Private Model Selection

To perform model selection in a differentially-private manner, we propose to apply the exponential mechanism or noisy minimization to the minimization problems (10) and (11), with $q(D,M)$ (here $s$ in the general definition is replaced by $M$) given by the penalized likelihood

in the case of penalized log profile likelihood (10), or

in the case of penalized least squares (11).

A key step in this approach is to evaluate and control the sensitivities of $L(M;D)$ and $L^{*}(M;D)$ as functions of $D$ for any $M\in\mathcal{M}$.

To simplify the notation and concentrate on the main idea, we will assume in the sequel that the data entries are bounded or standardized:

where $r$ is a known number that can grow with $n$. Boundedness is typically required for differentially private data analysis. Standard methods for finding the range of the data set in a privacy-preserving manner include those given in Dwork & Lei 2009 and Smith 2011.

To bound the sensitivity of either of them, we must bound the possible parameter vectors we consider. We thus consider constrained versions of the two score functions. Given $R>0$, we define

The sensitivity of the least squares loss is now easy to bound:

The proof is both short and elementary, and hence omitted.

In the case of the constrained profile likelihood, we can not bound the global sensitivity, but we can find a bound on the local sensitivity:

2.2 Algorithms

Lemma 3.1 implies that the penalized constrained lease squares

can easily be minimized in an $\epsilon$-differentially private manner. The complete algorithm is given below.

Next, Lemma 3.2 gives an upper bound of the local sensitivity of $L_{R}^{*}(M;D)$. Now we apply the generic scheme of designing $(\epsilon,\delta)$-differentially private algorithms described in section 2.3.

where $Z_{G}$ is a standard Laplace random variable.

Then we can construct the final estimators using either exponential mechanism or the noisy minimization, both satisfying $(2\epsilon,\delta)$-differential privacy. The complete algorithm is given in Algorithm 2.

3 Choosing the tuning parameters

However, our numerical experiments in section 5 show that the performance of our proposed algorithms is sensitive to the choice of these tuning parameters. We acknowledge that fully data-driven and privacy-preserving methods for choosing these tuning parameters remain a challenging and important open problem, and is beyond the scope of this paper. Data-driven choice of penalty parameter is a hard problem even without privacy constraint. Here we provide some heuristics on potential solutions.

Utility Analysis

In privacy-preserving data analysis, the privacy shall be protected for any possible input data set. In other words, the privacy guarantee needs to cover the worst case and must be established with no distributional conditions on the data set. In the previous sections, our differentially private procedure only requires the data to be bounded, which can be verified or enforced easily in practice. On the other hand, the statistical utility (for example, consistency, rate of convergence) is usually based on common statistical assumptions on the data. To facilitate discussion, we first introduce some notation and assumptions.

Let $\mathbf{X}$ be the $n\times d$ design matrix, and $\mathbf{Y}$ the $n\times 1$ vector of $Y$’s. For any $M\in\mathcal{M}$, let $\mathbf{X}_{M}$ be the $n\times|M|$ design matrix consisting of the columns in $M$. Then $\widehat{\beta}_{M}$ is a $d\times 1$ vector that is $(\mathbf{X}_{M}^{T}\mathbf{X}_{M})^{-1}\mathbf{X}_{M}^{T}\mathbf{Y}$ on the entries in $M$ and zero elsewhere. It is the ordinary least square estimate under model $M$. The sample covariance is $\widehat{\Sigma}=n^{-1}\mathbf{X}^{T}\mathbf{X}$.

We state below five assumptions required for our utility results, and discuss their practical significance.

Our first assumption is a sparse linear model with Gaussian noise.

(Linear model with Gaussian noise) The data entries $(X_{i},Y_{i})_{i=1}^{n}$ are generated from the linear regression model (4) with a regression coefficient vector $\beta_{0}$ with $d_{0}=\|\beta_{0}\|_{0}$ and $b_{0}\equiv\min_{j:\beta_{0}(j)\neq 0}|\beta_{0}(j)|$. The noise $W_{i}$ are iid Gaussian with mean zero and variance $\sigma^{2}$.

Next we assume that the number of candidate models grows polynomially with sample size $n$. This is usually the case when we only search over sparse models and the total number of variables grows polynomially in $n$.

(Candidate models) The set of candidate models $\mathcal{M}$ contains the true model $M_{0}=\{j:\beta_{0}(j)\neq 0\}$, and has cardinality no more than $n^{\alpha}$ for some positive number $\alpha$ which is allowed to grow with $n$. The largest candidate model has $\bar{d}$ variables.

The worst-case sensitivity of the log likelihood is hard to control because the design matrix $\mathbf{X}$ may be poorly conditioned. Thus we need to add some singular value condition on the design matrix.

(Design matrix) The design matrix $\mathbf{X}$ is fixed, and the sample covariance satisfies the sparse eigenvalue condition:

Assumption A2 excludes the situation of linear dependence between columns of $\mathbf{X}_{M_{0}}$ and $\mathbf{X}_{M_{0}^{c}}$. A similar condition has been considered in the literature on model selection consistency using information criteria (Nishii 1984). The condition stated here is for fixed design matrix $\mathbf{X}$, but it holds with high probability for many random designs. Assumption A2 also implies an upper bound of the range of $\widehat{\beta}_{M}$. Such a boundedness property will help control the sensitivity of the log likelihood.

Moreover, as we did in section 3, we assume boundedness of the data entries, which are typically needed for developing differentially private procedures.

(Boundedness) Each entry of $\mathbf{Y}$ is bounded by $r$, and each entry of $\mathbf{X}$ is bounded by $1$.

Finally, we assume that the sample size is large enough, when compared to other quantities in the analysis such as the noise variance, and the inverse of privacy parameter $\epsilon$.

(Sample size) The sample size $n$ is large enough so that equations (18), (19), and (20) hold.

1 Utility of Penalized Constrained Least Squares

We first give a utility result for the noisy penalized constrained least squares estimator (Algorithm 1).

Assume A0-A4 hold. If $\phi_{n}$ satisfies

where $A=2(\alpha+c)$ for some $c>0$, and

then the PCLS estimator $\widehat{M}$ given by Algorithm 1 with privacy parameter $\epsilon$ and penalty parameter $\phi_{n}$ satisfies

Recall that $P_{D,\omega}$ stands for taking probability over both the randomness in $D$ and in the generation of Laplace random variables (denoted by $\omega$) in the algorithm. Here we are assuming a fixed design matrix, so the randomness in $D$ is equivalent to the randomness of the additive noise $W$.

2 Utility of Penalized Constrained Profile Likelihood

Now we provide utility result for the noisy penalized profile likelihood estimator.

Assume A0-A4 hold. If $\phi_{n}$ satisfies

where $A=2(\alpha+c)$ for some $c>0$, and

then for any constant $c>0$ and $n$ large enough as quantified in Equations 18, 19 and 20, the selected model $\widehat{M}$ given by the noisy penalized constrained profile likelihood (Algorithm 2) satisfies

Empirical Results

We have shown in the last section that the two proposed differentially-private model selection procedures are consistent under similar conditions as the corresponding non-private algorithms. We now provide some empirical results for model selection via penalized constrained least squares, to illustrate both the utility of the algorithms and impact of tuning parameter selection as discussed in section 3.3.

In the simulations, we consider a small sample size ($n=100$) and a moderately large sample size ($n=1000$), as well as $R\in\{1,2.5,3.5,10\}$, $\epsilon\in\{0.1,1,5,10\}$ and $\phi\in[0,n/2]$. For each set of parameters, we sample $500$ data sets from the true model, apply Algorithm 1 to each of them, and note the proportion of times we correctly identify the correct model. We set $r$ to be the maximum observed value of $Y$ in the data set.

Figure 2 shows the results for case where $\beta_{0}=c(1.5,1,0.5,0,0,0)$. The effect of $n$, $R$, $\phi$ and $\epsilon$ are very similar in this case, but the choice of $R$ and $\phi$ are more important to achieve good utility. The sensitivity of the procedure to choices of $R$ and $\phi$ thus depends on the structure of the true parameter $\beta_{0}$. Note however that for $n=1000$ a proper choice for the parameters leads to completely accurate model selection with $\epsilon=5$, and even very accurate for $\epsilon=1$ with $R=2.5$.

2 Application to Real Data Sets

We first illustrate the results of model selection via penalized constrained least squares on a small data set of $97$ observations, then on a much larger one with hundreds of thousands observations.

The prostate data set contains several clinical measures for $97$ men with prostate cancer. In this paper, our goal is to predict the level of a prostate specific antigen using five continuous variables: the volume of the cancer, the weight of the prostate, the age of the patient, the capsular penetration and the benign prostatic hyperplasia amount. Except for age, all variables are taken on the $log$ scale. We also rescale all of the variables to take values between $-1$ and $1$, which could be done in a differentially private way.

We consider all possible main effects models for the model selection procedure, for a total of $63$ models to choose from. Model selection based on the penalized maximum likelihood, without the constraint of differential privacy, selects the model with only two variables in addition to the intercept: the volume of the cancer, and the weight of the prostate. Model selection is then performed using Algorithm 1 for various choices of $R$, $\phi$ and $\epsilon$. We set $R=5.68$, obtained with the non-private algorithm, and we set $r$ to the maximum value of $Y$.

Figure 3 shows the proportion of times that the private and non-private procedures identify the correct model, for $5000$ independent replications. With such a small data set, the choice of $R$ and $\phi$ are crucial: even without differential privacy, using too large a value of $\phi$ does not identify the correct model. Due to the small sample size, the utility of the private procedure also decreases quite rapidly with decreasing $\epsilon$ which should offer more privacy.

Since the constrained optimization can be implemented based only on sufficient statistics, the private procedure scales very well for much larger data sets. The housing data set contains several variables measured on $348,189$ houses sold in San Francisco Bay Area between 2003 and 2006. In addition to the price of the sale, the data include the year of the transaction (an ordinal variable with 4 levels), the latitude and longitude of the house, the county in which it is located (a categorical variable with 9 levels), and a continuous measure of its size. We preprocess the data to remove houses with price outside the range $105$ to $905$ thousand dollars, and size larger than $3000$ sqft. We also combine some of the small counties into a new indicator variable. All predictors are also scaled so that they take values in $$. The resulting data set contains$235,760$with$13$ variables.

We consider again models with main effects only, for a total $8191$ models to choose the best model from. Since the optimal model is not as clear as with the previous example, we do not directly compare the private procedure with a gold standard, but rather with its non-private counterpart. An algorithm which offers differential privacy but recovers the results of a non-private algorithm is successful. As above, we apply the model selection procedures with various values of $R$, $\phi$ and $\epsilon$, and use the maximum value of $Y$ as $r$.

Figure 4 shows the agreement between the private and non-private procedure for various tuning parameters. With this large data set, the results are very positive: even for $\epsilon=1$ we recover the same model with the differentially-private procedure as without the privacy requirement for $\phi$ chosen large enough. Note also that, as expected, the scale of $\phi$ is much larger than for the smaller Housing example.

Discussion

With modern data acquisition and storage techniques allowing the collection and analysis of huge amounts of personal information in a multitude of formats, protecting individual privacy inevitably becomes of crucial concern for modern data analysis. Although differential privacy offers mathematically strong and elegant privacy guarantee, the nature of such a conservative constraint in the context of everyday statistical analysis remains unclear. Previous works on statistical analysis with differential privacy mainly focused on simple statistical queries, such as location and scale statistics, regression coefficients, and simple hypothesis testing, and network analysis. In this paper we considered the more challenging problem of model selection in the classical setting. We showed that standard techniques for differentially private data analysis can be combined with known statistical tools such as penalized least square or information criteria to construct privacy-preserving model selection procedures with strong utility. We proposed two algorithms for this task, and proved privacy and utility results for each of them.

Our procedures feature a double-regularization, as they include both constrained estimation in the fitting step, and penalization in the model comparison step. Thus the method involves two tuning parameters. A key observation, illustrated in section 5, is that although we have proven good large-sample properties for a wide range of penalty parameter $\phi_{n}$ and $R$, the practical performance is sensitive to the particular choices for these parameters. In other words, these tuning parameters play a very important and unique role in designing differentially private procedure with good practical performance. While in low-dimensional settings, the regularization parameter is not needed for statistical inference without privacy constraints, when privacy is a concern, a carefully chosen amount of regularization can lead to stable, low-sensitivity estimators even in the worst case. Appropriate choice of both tuning parameters thus reflects the need for some additional information in the data that will be useful for differentially private procedures, but not necessary in traditional inference methods. It will be an interesting future topic to give a general characterization of such privacy related quantities, and to develop differentially private methods to estimate these quantities.

Appendix: Proof details

Given a candidate model $M$, the log likelihood is, ignoring constant terms,

Let $\widehat{\beta}^{\prime}_{R,M}$ be the constrained least square estimator with input data set $D^{\prime}$. By boundedness of $Y_{i}$, $X_{i}$ and $\widehat{\beta}_{R,M}$ we have $(Y_{i}-X_{i}^{T}\beta)^{2}\leq(r+R)^{2}$ for all $\beta$ such that $\|\beta\|_{1}\leq R$. Then using the fact that $\log(x/y)\leq(x-y)/y$ for $x\geq y$, we have

Next we prove our main utility theorems. The proofs of Theorem 4.1 and Theorem 4.2 rely on the following result, which is a consequence of simple linear algebra.

We prove for noisy minimization. The argument can be adapted simply to cover the exponential mechanism.

Then according to Proposition 7.1, we can work directly with the unconstrained version.

For $M^{\prime}\supset M_{0}$, using Claim 2 in Section 7 we have $\sup_{M^{\prime}:M^{\prime}\supset M_{0}}\Delta_{M^{\prime}}\geq-A\sigma^{2}(|M^{\prime}|-|M_{0}|)\log n$ with probability at least $1-\frac{\bar{d}-d_{0}}{\sqrt{2\pi A\log n}}n^{-c}$. Thus with same probability we have

For $M^{\prime}\nsubseteq M_{0}$, we have by Claim 3 in Section 7, with probability at least $1-\frac{1+\bar{d}}{\sqrt{2\pi A\log n}}n^{-c}$,

Thus conditioning on $E_{2}^{c}\cap E_{3}^{c}$, which has probability at least $1-\frac{1+2\bar{d}}{\sqrt{2\pi A\log n}}n^{-c}$, we have

Consider events $E_{1}$–$E_{5}$ as defined in Section 7. We focus on the event $\left(\bigcup_{k=0}^{5}E_{k}\right)^{c}$, which has probability at least $1-3n^{-A/2}-2\bar{d}n^{-c}$.

In the case of $M\supset M_{0}$, applying the fact that $-\log(1-x)\leq x/(1-x)$ for $x\in(0,1)$ to

where the last step follows from the fact that we are not in the event $E_{0}\cup E_{1}\cup E_{2}$ defined in Section 7.

On the event considered, we also have $G(D)\leq 4(R+r)^{2}\sigma^{-2}$ by Claim 5. Then we can bound the error probability by

2 Further proof details

Here we give details and summarize the multiple “with high probability” statements in the utility analysis. Recall that

We define the following events and give the corresponding probability bounds.

Claim 2. $P_{D}(E_{2})\leq\frac{\bar{d}-d_{0}}{\sqrt{2\pi A\log n}}n^{-c}\,.$

Because $M_{0}\subset M$, $P_{\Pi_{M}}-P_{\Pi_{0}}$ is a projection operator of dimension $|M|-|M_{0}|$. Using a tail probability bound for Gaussian random variables, we have, for all $A=2(\alpha+c)>0$,

The desired result follows from union bound. ∎

For $M\nsupseteq M_{0}$, let $M_{1}=M_{0}\backslash M$, $M_{2}=M_{0}\cap M$, $J_{M}^{*}=\sqrt{n\kappa_{0}b_{0}^{2}|M_{1}|}$. Define

Denote $\beta_{0,M}$ the vector that agrees with $\beta_{0}$ on $M$ and 0 elsewhere.

where $\Pi_{0,M}$ is the linear subspace spanned by $X_{M_{0}\cup M}$.

Let $J=\|P_{\Pi_{M}^{\bot}}(\mathbf{X}_{M_{1}}\beta_{0,M_{1}})\|_{2}$. Then the second term in the above equation is distributed as $N(0,\sigma^{2}J^{2})$. By the eigenvalue condition, we have $J^{2}\geq\kappa_{0}nb_{0}^{2}|M_{1}|$, where $\kappa_{0}$ is the minimum sparse eigenvalue and $b_{0}$ is a lower bound of the signal level. To see this, observe that $M\cap M_{1}=\emptyset$ and

where the first inequality uses the sparse eigenvalue condition.

Note that the dimension of $\Pi_{M}\cap\Pi_{0}^{\bot}$ is at most $|M|-|M_{2}|$. Let $J^{*}\coloneqq\sqrt{\kappa_{0}nb_{0}^{2}}$. Using (18) we know that $J\geq J^{*}\geq 4\sqrt{A\log n}$. Then with probability at least $1-(1+|M|-|M_{2}|)n^{-A/2}/\sqrt{2\pi A\log n}\leq 1-\frac{1+\bar{d}}{\sqrt{2\pi A\log n}}n^{A/2}$, we have

where the last inequality uses eq. (18). The claim follows from union bound. ∎

Claim 4. $E_{4}\subseteq E_{1}\cup E_{2}\cup E_{3}\,.$

Claim 5. $P_{\omega}(E_{5})=\frac{1}{2}n^{-A/2}\leq n^{-A/2}$. On $E_{4}^{c}\cap E_{5}^{c}$, we have, using eq. (18)–(20),

References