On the Computational Complexity of Private High-dimensional Model Selection
Authors: Saptarshi Roy
Zehua Wang
Ambuj Tewari
Venue: NeurIPS 2024 poster (2024)
Keywords: Best Subset Selection
Differential Privacy
Exponential Mechanism
Metropolis-Hastings
Model Consistency
Variable Selection.
Primary area: privacy
TL;DR: This paper proposes computationally efficient Metropolis-Hastings algorithm for private best subset selection in high-dimensional sparse regression setup.

Abstract: We consider the problem of model selection in a high-dimensional sparse linear regression model under privacy constraints. We propose a differentially private (DP) best subset selection method with strong statistical utility properties by adopting the well-known exponential mechanism for selecting the best model. To achieve computational expediency, we propose an efficient Metropolis-Hastings algorithm and under certain regularity conditions, we establish that it enjoys polynomial mixing time to its stationary distribution. As a result, we also establish both approximate differential privacy and statistical utility for the estimates of the mixed Metropolis-Hastings chain. Finally, we perform some illustrative experiments on simulated data showing that our algorithm can quickly identify active features under reasonable privacy budget constraints.

On the Computational Complexity of Private High-dimensional Model Selection
Saptarshi Roy
Zehua Wang Ambuj Tewari Department of Statistics
University of Michigan, Ann Arbor froysapta, wangzeh, tewaria)Qumich. edu
Abstract
We consider the problem of model selection in a high nigh-dimensional sparse linear regression model under privacy constraints. We propose differentially private (DP) best subset selection method with strong statistical utility properties by adopting the well-known exponential mechanism for selecting the best model. To achieve computational expediency, we propose an efficient Netropolis-Hastinng algorithm and under certain regularity conditions, we establish that it enjoys polynomial mixing time to its stationary distribution. As result, we also establish both approximate differential privacy and statistical utility for the estimates of the mixed Metropolis- Hastings chain. Finally, we perform some illustrative experiments on simulated data showing that our algorithm can quickly identify active features under reasonable privacy budget constraints.
Introduction
In this paper, consider the problem of private model selection in high-dimensional sparse regres- sion which has been one of the central topics in statistical research over the past decade. Consider n observations {(x, 9:) S X' y following the linear model:
(1) where {Xi]eenn are fixed p-dimensional feature vectors, {wi) i.i.d. mean-zero a-sub- Gaussian noise, i.c., IE exx((Aw;) exp(>2o2/2) for all À E E and [n]. and the signal vector B E RR is unknown but is assumed to have sparse support. In matrix notation, the observations can be represented as
yi = x + wi, i (1.....n).
=x=
= XB+ w,
where y (yI...., Vn TT x (X)...... , XT) and (wi,..., W.,, We consider the standard high-dimensional sparse setup where n < p. and possibly & p. and the vector B is sparse in the sense that ||,3|,, Dm= (3, #
which is much smaller than p. The main goal of variable
selection is to identify the active set 7" == {j * 0}.
For the past two decades, there has been ample work on model selection problem in the non privvite
setting for fi-penalized methods 57 54 46 23 concave regularized methods (55 53 12 16), 60- penalized/ccontrained methods 13
in high-dimensional setting. On the computational side, recent advancements related to mixed integer optimization (MIO) in 5 and (2) have pushed the computational barrier of best subset selection (BSS) in terms of solving problems of large dimensions (large p), and consequently, simulation studies in [19 have revealed the improved performance of BSS over its computational surrogates like LASSO, SCAD, and MCP.
Despite these theoretical and computational advancements related to BSS, to the best of knowledge, there is no computationally efficient private algorithmic framework for BSS for high- dimensional sparse regression setup ( This is especially surprising as private model selection
38th Conference on Neural Information Processing Systems (NcurIPS 2024).

---

is important in many contemporary applications involving sensitive data including genetics [2]] neuroimaging [3]. and computer vision [56]. One major reason for this could be the lack of DP mechanisms for MIO problems which restricts us from exploiting the MIO formulation of BSS introduced in Secondly, the apparent computational burden stemming from the requirement of exponentially large numbers of search queries in private BSS has eluded the majority of the machine learning and statistics community. In this paper, we address the latter issue by mainly focusing on the utility and computational complexity of BSS under privacy constraints. To be specific, we make the following contributions listed below:
1. We adopt the exponential mechanism
31 to design DP BSS algorithm, and we establish its good statistical or utility guarantee under high-privacy regime whenever
Amin == minjer' 1 Z {((s p)g/)/)///
2. Under the low eow-privay regime, we show that accurate model recovery is possible whenever 3min Z o {logg) p)/n) / which is the minimax optimal 8min requirement for model recov- ery under non-private setting. Therefore, this paper points out an inflection phenomenon in the signal strength requirement for the model consistency across different privacy regimes.
3. In addition, we design an MCMC chain that converges to its stationary distribution that matches the sampling distribution in the exponential mechanism. As consequence, the model estimator generated by the MCMC also enjoys (approximate) DP. Furthermore, under certain regularity conditions on the design, show that the MCMC chain enjoys polynomial mixing time in (n1, Jn,P,5 s) to the stationary distribution with good utility guarantee.
In summary, this paper proposes a DP version of BSS that generates a private model estimator of y with strong model recovery property within polynomial time in the problem parameters n. p, 8. In the next section, we will discuss some prior related works on DP model selection and discuss some of their limitations.
1.1 Comparison with Prior Related Works
In the past decades, there has been considerable amount of work studying DP sparse regression problems. However, most of these works focus either on empirical risk minimization 225 44 26 48
which are not directly related the task of model selection. To the best of our knowledge, there are only three works considering the problem of variable selection
or establishing fz-consistency rate [7 6
in sparse regression problems under the DP framework, (2 45), and 229. Table shows clear comparison between those methods and our method. 27 proposed two algorithms under sparse regression setting. One of them is based on the exponential mechanism, which known to be computationally inefficient due to exponentially large numbers of search queries. However, they do not analyze the algorithm under the model selection framework. Moreover, for the privacy analysis, they assume that the loss functions are bounded over the space of sparse vectors, which is rather restrictive in the linear regression setting. In comparison, our paper provides a solid model recovery guarantee (Theorem 3.5) for similar exponential mechanism without using the bounded loss assumption. Furthermore, under a slightly stronger assumption, we design a computationally efficient MCMC algorithm that also enjoys desirable utility similar to the exponential mechanism (Theorem under DP framework. The other algorithm in (27 is based on the resample-and aggregate framework [36]] 42 Although computationally efficient, this method requires sub-optimal 3min condition compared to Theorem 3.5 In [45,, the authors introduced two concepts of stability for LASSO and proposed two PTR-based (propose-test-release)) algorithms for variable selection. However, these methods have nontrivial probabilities of outputting the null (no result), which is undesirable in practice. Also, the support recovery probabilities for these methods do not approach I with a growing sample size even under the strong irrepresentability condition (57) on the design matrix. In [29]. the authors proposed to use the Akaike information criterion or Bayesian information criterion coupled with the exponential mechanism to choose the proper model. However, the runtime of this algorithm is exponential and also requires stronger Bmin condition. As mentioned earlier, in this paper, we show that our proposed MCMC algorithm is both computationally efficient and produces approximate DP estimates y with a strong utility guarantee under a better Syii condition. One may also apply sparse vector techniques (SVT) to choose important features [43]. In this case, each feature can be associated with an appropriate choice of score function, and then apply SVT to choose the relevant features. However, the choice of the score function in high-dimensiooal sparse regression cases remains unclear, and moreover, it is also known that the exponential mechanism enjoys better accuracy compared to SVT [30 under such an offline setting.
2

---

Table 1: Comparison of DP model selection methods.
Paper
Method
Bmin cond.
failure prob.
D runtime
Exp-Mech
NA
NA
exp
Lasso Samp-Agg
#log n/2
yes
poly
45
Lasso Sub-samp. stability
12(
llgg
we
no
poly
Lasso + Pert. stability
( {
s pogg 2//2
no
poly
29
Exp-Mech
( max (1, 2)
yes
exp
This paper
Exp-Mech
Φ( max (1, ; log
yes
exp
Approx. Exp-Mech via MCMC
max (1, 1.23 loK2)
yes
poly
2
Differential Privacy
Differential privacy requires the output randomized procedure to be robust with respect to small perturbation in the input dataset, i.e., an attacker can hardly recover the presence or absence of a particular individual the dataset based on the output only. is important to note that differential privacy is property of the randomized procedure, rather than the output obtained.
2.1 Preliminaries
In this section, we will formalize the notion of differential privacy. Consider dataset D fzi...., 2n E 2 consisting of n datapoints in the sample space 2. A randomized algorithm A maps the dataset D A(D) O, an output space. Thus, A(D) is a random variable on the output space O.
For any two datasets D and D', say they are neighbors if IDDD 1. We introduce the definition of differential privacy.
formally
Definition 2.1 ((e, 5)-P), (9) Given the privacy parameters (E, E R x R+ a randomized algorithm A(-) is said to satisfy the (e, 8)D property if
P(A(D) E KC) S <P((A(D)) KC)
for any measurable event K. range(AA) and for any pair of neighboring datasets D and D'.
In the above definition, the probability only with respect to the randomness of the algorithm A(-). and it does not impose any condition on the distribution of D or D'. If both E and 5 are small, then Definition 2.1 essentially entails that distribution of A(D) and A(D') are almost indistinguishable from each other for any choices of neighboring datasets D and D', This guarantees strong privacy against an attacker by masking the presence or absence of a particular individual in the dataset. special case, when = 0, the notion of DP in Definition 2.1 is known as the pure differential privacy.
2.2 Privacy Mechanisms
For any DP procedure, specific randomized procedure A must be designed that takes database
D E 2" as input and returns an element of the output space O while satisfying the condition in (). Several approaches exist that are generic enough to adaptable different tasks, and which often serve as building blocks for more complex ones. A few popular examples include the Laplace mechanism [T] Gaussian mechanism 10. and Exponential mechanism [31]. We only provide the details of the last technique, since the other two techniques are out-of-scope for the methods and experiments in this paper.
Exponential mechanism: The exponential mechanism is designed for discrete output space, Suppose / = (a; i I) for some index and let y nn R be score function that measures the quality of a E L. Denote by Aux the global sensitivity of the score function i.e.
Aug == max max aE D, D' are neighbors
Iu(a, D) u(a, D')

---

Intuitively, sensitivity quantifies the effect of any individual in the dataset on the outcome of the analysis. The score function -).--) called data monotone if the addition of data record can either increase (decrease) or remain the same with any outcome, e.g., u(ax, D) S u(a, D U (z)). Next, we have the following result.
Lemma 2.2 (8 31)). Exponential mechanism Ag(D) that outputs samples from the probability distribution
P(Ag(D)= = a) & exp Eu(a, D)
(3)
Au
preserves (2e, 0)-differeenii privacy. If u(;,)) is data monotone, then we have (e, --differrentt privacy.
In general, if the y is too large, the sampling from the distribution could be computationally inefficient. However, we show below that the special structure of the linear model ( allows us to design MCMC chain that generate approximate samples efficiently from the distribution for privately solving BSS under an appropriately chosen score function.
3 Best Subset Selection
We briefly review the preliminaries of BSS, one of the most classical variable selection approaches.
For a given sparsity level 8, BSS solves for Brest (8) := arg min
lly X01
1 For model
selection purposes, we can choose the best fitting model to be Tbest (8) = {j : B heat (3)]s ; * 0}. For subset y S [p]. define the matrix X, == (Xj; E 7). Let T. := X, (X, X, X orthogonal projection operator onto the column space of X,, Also, define the corresponding residual sum of squares (RSS) for model 7 (y, X) y (T,, D) With this notation, the Tbest (8) can be alternatively written as
Test (3) arg min, ci XX.
(4)
Let X. be the matrix comprised of only the columns of X with indices in y, and by denotes the orthogonal projection matrix onto the column space of X,. In addition, let Σ == n -1x X be the sample covariance matrix and for any two sets 71, 72 C jp]. Enyi denotes the submatrix of Σ with row indices in "1 and column indices in 72. Finally, define the collection of = { C [p] 7 +
7.7 (. Then, it follows 11 = 3), and for y E d write I(>) En-rorr E S-1 E
that (,)),,( is equal to the residualized signal strength n --' Xx,,X,, 112. Therefore, ",,,,, ( quantifies the separation between and the true model 7" Ideally, a larger value the quantity will help BSS to discriminate between > and any other candidate model y. More details on this can be found in [40]. Now we are ready to introduce the identifiability margin that characterizes the model discriminative power of BSS.
3.1 Identifiability Margin
The discussion in Section 3 motivates us to define the following identifiablity margin:
G 3T,1,1(9)8 by \
m. S min 2E.0
(5)
As mentioned earlier, the quantity m, (3) captures the model discriminative power of BSS. To add more perspective, note that the features are highly correlated among themselves then is expected that m, (3) is very close to O. Hence, any candidate model is practically indistinguishable from the true model 7 which in turn makes the problem of exact model recovery harder. On the contrary, the features are uncorrelated then m, (3) becomes bounded away from 0 making the true model >* easily recoverable. For example, 117 showed that under the knowledge of true sparsity, i.e., when
3 the condition
mlt, (s) 2 logp
(6)
sufficient for BSS to achieve model consistency. One can also view m, (s) as a quantifier of the coupled effect of model correlation and signal strength. If we define the minimum and maximum

---

eigenvalues over all models to be X, = minyeds Amin (T())) and X = maxyesf, Amaz (T())) respectively, then follows that
A min S mn (s) S X X min
Therefore, it suffices to have Smin 2 (log ())(n))) in order to satisfy condition (6). In this case, A. captures the degree model correlation, and Smin is the minimum signal strength. Similar to our previous discussion, if there is high collinearity in the model, A will be typically small, and BSS needs large value of mmin identify the true model 7² On the other hand, if [mmn is too small for a given level of model correlation, i.e, if Smin < o (logp)/((g (mA()))))) 11/2, then also BSS fails to achieve model consistency as it is hard to identify active features under the presence of weak signals in the next section, the DP BSS algorithm also requires margin condition similar to (6) to ensure model recovery, and this is indeed an indispensable condition as it needed even in non-private case.
17 Theorem 2.1] J. As we will
3.2
Differentially Private BSS and Utility Analysis
In order to privatize the optimization problem 4. we will adopt the exponential mechanism discussed in Section 2.2 In particular, for a tuning parameter K > 0, we consider the score function
uk(1: X, ==
min :
Ily X, 0
and for a given privacy budget e > O, we sample E ozzz from the distribution
(ux(T; x, 1(7 1(Y o ul"))
(<) x exp
Auk
As concerned with the exact recovery y", from here
assume š The above algorithm
essentially the same as Algorithm 4 in [27]; however, they do not introduce the extra & ec-onnttain on the parameter space. Instead, their algorithm needs the loss-term (y x 0)² to be bounded by a constant for every possible choice of x, y, and 0. This assumption is not true in general for the squared error loss, and to remedy this issue, introduce the extra & c1-oonstra in the score function. This is a common strategy that is used to guarantee worst-case sensitivity bound and similar methods also have been adopted [29 lemma that shows the data-monotonicity of the proposed score function.
construct private estimators. Next, present the following
Lemma 3.1. The score function uk (7: in data monotone.
Therefore, Lemma 2.2 automatically guarantees that the above procedure (e, 0)-DP. However, in practice, we need explicit form for Auk carry out the sampling method, and it is also needed to analyze the utility guarantee of the exponential mechanism. To provide a concrete upper bound on the global sensitivity of ux(;-), we make the following boundedness assumption on the database:
Assumption 3.2. There exists positive constants r, Tmax such that yayy |v| S T; supxex ||x|| S Tmax-
Under this assumption, the following lemma provides an upper bound on the global sensitivity of the score function along with the DP guarantee.
Lemma 3.3 (Sensitivity bound and DP). Under Assumption 3.2 the global sensitivity Aug is bounded by ÁK := (r x) Therefore, the exponential mechanism (7) with Aug replaced by AK satisfies (e, -)-
The above lemma provides an upper bound on the global sensitivity of the score function rather than finding the exact value of it. However, to guarantee (e, -D- property of exponential mechanism, it suffices to use the upper bound of Aux in 77.. Now we will shift towards the utility analysis of the proposed exponential mechanism. First, require some technical assumptions. Assumption 3.4. We assume the following hold:
(a) There exists positive constants bmax such that ||,31,, < bmax-
(b) There exists positive constants K_, K4 such that
K_ & Amin ( 8//n) & Amax (x, X,,x/n) S K.t,
(8)
for all y s. (T7).
5

---

(c) The true sparsity level follows the inequality s S n (log
Assumption 3.4 tells that the true parameter , lies inside a &b-bll. Similar boundedness as- sumptions are fairly standard in privacy literature 449 29 6]. Assumption b.4 is well-known assumption in the high-dimensional literature [54] 22 32 which is known as the Sparse Riesz Condition (SRC). Finally, Assumption (.4 essentially assumes that the o(n), ie., sparsity grows with a sufficiently small rate compared to the sample size n.
Theorem 3.5 (Utility gurantee). Let the conditions in Assumption 3.2 Assumption 3.4 hold. Set K 2 {(K// / )mmx + (8Imax/K... /-)oo// Then, under the data generative model 1 there exist universal positive constants C12 C1 such that whenever
11,
AK logp 50
ma (s) 2 CiO² max
(9)
7
with probability at least 1 - c.p= we have π ((>))(7))))))) p 1
Cost of privacy. Theorem 3.3 essentially says that whenever the identifiability margin is large enough, the exponential mechanism outputs the true model 7" with high probability. Note that Ak/d (s)). the low privacy regime, i.e., for & Ax/o² we only require (s) Z o² (logp)/n to achieve model consistency and this matches with the optimal rate for model con- sistency of non-private BSS. Note that, the margin condition does not depend at all on E in this regime. In contrast, in high privacy regime, i.c., for Ak/ Ak/o², Condition (9) essentially demands m, (s) Z (s log p)/ (næ) to achieve model consistency. Thus, in a high privacy regime, we pay an extra factor of (s/E) in the margin requirement.
Remark 3.6. The failure probability in Theorem 3.5 can be improved to O(p-M) for any arbitrary integer M > However, we have to pay a cost in the universal constant C₁ in terms of multiplicative constant larger than 1.
Remark 3.7. Under Assumption 3.4(b) it follows that x, 26.. Therefore, it suffices to have (EooK logg in order to hold condition ( Therefore, in high- minjer 83 2 [R] >mammax
(C,o²)
privacy regime, our method requires minjer- 18,1 2 <=((slog))((nek)) ()Enn)))/))))))))))))))/))))>))) 1)1/2 In contrast, under the low-privacy regime, retrieve the optimal requirement minjer |8,| 2 a (logp)/(nk))
4 Efficient Sampling through MCMC
In this section, we will propose an efficient sampling method to generate approximate samples from the distribution (7) One of the challenges of sampling methods in high-dimension their high computational complexity. For example, the distribution in ( places mass on all (?) subsets of [p]. and practically infeasible to sample y from the distribution as we have to essentially explore over an exponentially large space. This motivates us to resort to sampling techniques based on MCMC, through which we aim to obtain approximate samples from the distribution in 7 Past works on MCMC algorithms for Bayesian variable selection can be divided into two main classes Gibbs sampler 15 24 Kd and Metropolis-Hastie
[8 28 In this paper, we focus on a particular form
of Metropolis Hasttonl updates.
In general terms, Metropolis- Hasttnngs (MH) random walk is an iterative and local-mov move based method involving three steps:
1. Given the current state y, construct a neighborhood ((r) of proposal states.
2. Choose new state 7' E (N( according to some proposal distribution F(y.-) over the neighborhood (7).
3. Move to the state 7 with probability R(7, 7'), and stay in the original state y with probability --R( R(?,1'), where the acceptance probability is given by
( (>>)
R(7, 7') = min
where xT-) is same in Equation 7

---

This procedure generates a Markov chain for any choice of the neighborhood structure M(y) with the following transition probability:
F ((7,7)) Ex P PMH(),2"),
if i' EN()) if r = otherwise.
P (7)
0,
The specific form of Metsopolis-Hastings update analyzed in this paper is obtained by following the double swap update scheme update 7,
Double swap update: y E La L {-*} be the initial state. Choose an index pair (k, E) E y x uniformly at random. Construct the new state 7 by setting 7' ( \ {k).
The above scheme can be viewed as a general MH update scheme when M(2) is the collection of all models 7 which can be obtained by swapping two distinet coordinates of and y respectively. Thus, letting d (7; 7/) = h 7 > denote the Hamming distance between and 7/, the neighborhood is given by N6)
( dm 7') 2, 3 (k E y of such that U (f) \ {K]}. With this definition, the transition matrix of the previously described Metropolis-
Hastings scheme can be written follows:
hih min x62), (G) J.
i N()),
PMH PM,(76 (7,7)
M'y PMH(7,n'),
if =n otherwise.
(10)
0,
4.1 Mixing Time and Approximate DP
Let C be Markov chain on the discrete space 9 with a transition probability matrix P E RI with stationary distribution v. Throughout our discussion, we assume that is reversible, i.e., it satisfies the balanced condition v(7) (())
P(7)) (P/n/n) 7) for all y, S Note that the previously described transition matrix PMH in (10) satisfies the reversibility condition. It convenient to identify reversible chain with weighted undirected graph G' on the vertex set Jf, where two vertices 7 and y are connected if and only the edge weight Q( (())") == ((7) 7") strictly positive. For E I and any subset S C S we write P(7, S) = YYES 7'),7') If vy is the initial state of the chain, then the total variation distance to the stationary distribution after iterations is
(t) P'(x.)) - 1000-~()lm =())lTv = max P'( --(S)/
SC
The m--miing time given by
max min A,(1) S for all L' 2'2 22),
(11)
JEy
which measures the number of iterations needed for the chain to be within distance 7) E (0, 1) of the stationary distribution.
Privacy of MCMC estimator: Now, we will show that once the MH chain in 10 has mixed with its stationary distribution (-) defined in (7). the model estimators at each iteration will enjoy approximate DP. To fix the notation, let 76 be the žth iteration of the MH chain in (TO.. Then, we have the following useful lemma:
Lemma 4.1. The model estimator Yr, is (e, 8)- with 5 = 17(1 + cf).
The above lemma shows that smaller 7 entails a better privacy guarantee for a fixed level d decreases with 7). Therefore, allowing more mixing of the chain will provide better privacy protection. However, this raises a concern about how long a practitioner must wait until the chain archives m-mixing. In particular, it is important to understand how T, scales in the difficulty parameters of the problem, for example, the dimension interested in the covariate dimension p. sample size n. sparsity 8, and the privacy parameter e. In the next section, we will show that the chain with transition matrix (10p enjoys rapid mixing, meaning that the mixing time Ty grows at most at polynomial rate p, and the sample size
the parameter space and sample size. In our case, we are
7

---

4.2 Rapid Mixing of MCMC
We now turn to develop sufficient conditions for MH scheme (10) to be rapidly mixing. To this end, we make a technical assumption on the design matrix. Essentially, the following assumption controls the amount of correlation between active features and spurious features.
Assumption 4.2. For every 7 a 17"),, there exists & $ r² U Uf such that
X (Tn $ B )x [(T By X
I b &bmax v (n- 2.02/1222 logp.
max NY
where C1 is the same universal positive constant in Theorem 3.5
First, note that Assumption 4.2 basically controls the length of the projection of the feature X, on the unit vector Ug = (T^- )),))xx [[ xx Therefore, the above inequality restricts the correlation between an active feature X, and the spurious scaled feature u, from being too large. To this end, we emphasize that stronger assumptions on model correlation (on top of the SRC condition) are common in literature for establishing the computational efficiency of Bayesian variable selection methods involving MH algorithm. For example, to show the computational efficiency MH algorithm under Zellner's s g- g-prior, [1 assumes
X, Vyllpp =0
(
n
max 10
(12)
s log
where so (larger than s) is a specific tuning parameter of their algorithm that controls the model size. The assumption in the above display akin to the well-known irrepresentability condition 57] which is a very strong assumption on the design. On a high level, at any given current state 7 Assumption 44. or Condition (12) helps to identify good local move towards the true model y" in the MH algorithm via deletion of the least influential covariate in y. Now, we present our main result for the mixing time of MCMC.
Assumption 3.4 and Assumption 4.2 hold. Then, under the data generative model ( there exists universal constant Ci > such that under the margin condition
Theorem 4.3 (Rapid mixing time). Let the conditions in Assumption 3.2
m. (s) 2 of max {1
AK
log
(13)
(n_ A 1)EO?
n
there exist universal positive constants C22 C2 such that the mixing time Ty of the MCMC chain (TO) enjoys the following with probability at least 1-cpp- 22:
Tn S C2ps² 1 log(1/n))
(14)
where V {r (K=//K_)0maxxmmm mmaxx + (o/Ks))
The main technical innovation in the theorem is the double swap updating scheme in the MCMC that allows us to leverage the canonical peth ensemble construction argument [4] to prove the bound (4) on the mixing time. Essentially, we show that under Assumption 4.2) there exists a canonical path in
specially weighted graph corresponding to the MCMC random walk with low path congestion. The
complete proof can be found in Appendix A.5
Regarding the statement of the theorem, note that the margin condition (3) is slightly stronger than the margin condition in Theorem 3.5 Under that condition, the above theorem shows that the m-mmxxig time of the MCMC algorithm designed for approximate sampling from the distribution (7) grows at a polynomial rate in (n, s)). Recall that according to the previous definition (I]) of the mixing time, Theorem 4.3 characterizes the worst-case mixing time, meaning the number of iterations when starting from the worst possible initialization. If we start with a good initial state for example, the true model > would be an ideal though impractical choice then we can remove the term in the upper bound in (14). Therefore, the bound in (14) can be thought of as the worst-case number of iterations required in the burn-in period of the MCMC algorithm. Furthermore, it is important to point out that Assumption 4.2 is only needed to ensure the "quick" mixing time of the MCMC chain. It is possible to relax this assumption, however, in that case, the MCMC chain not guaranteed to mix under polynomial time. Nonetheless, given enough iterations, the chain will indeed
8

---

converge to the distribution as MH algorithm always generates an ergodic chain that eventually mixes to its stationary distribution.
is interesting to note that Theorem 4.3 suggests that in a large e regime, the chain mixes slower compared to the small regime. The main reason for this is that Theorem 4.. only relies worst-case analysis. The intuition is the following: When E is very large, then the target distribution is essentially fully concentrated on 7 (assuming the score yor is highest). Now, the current analysis of Theorem 4.3 does not assume any condition on the initial state of the MCMC chain. It treats the initial state Tu as if it is chosen in completely random manner, i.e., it is the worst case. From this point of view, it is hard for a completely uninformative distribution to converge to target distribution that is concentrated on a single subset (very informative), and resulting in a longer mixing time. Finally, Theorem 4.3 leads to the following corollary:
Corollary 4.4. Let Ti denote the distribution of the tth iterate "It of the MCMC scheme (T0). Then, under the conditions of Theorem 3.5 and Theorem 4.3 there exists universal constant c3 > O such that for any fixed iteration such that t 2 C2ps" { (neVe-xxklle ((()))2-11)
log(1/n)), we have
with probability at least 1 - ccc
The above corollary is useful in the sense that it provides a quantitative choice of v) that yields high utility of the estimator "/t For example, if we set p=² and 8 O1), then for any I Σ pos(ne + p) the resulting sample " will match y with probability
egp
Remark 4.5. Similar to Remark 3.6 the failure probability in Theorem 4.3 and Corollary 4.4 can be improved to O(p- M) for arbitrary large M > 2, but at the cost of paying higher values for the absolute constants C₁ and Cz.
5 Numerical experiments
In this section, we will conduct some illustrative simulations. To compare the quality of the DP model estimator, we compare F-score [19 of the estimated model with that of the true model y and the BSS estimator. As the actual BSS is computationally infeasible, we use the adaptive best subset selection (ABESS) algorithm (88) as a computational surrogate BSS. Throughout this section, we assume that the true sparsity is known, i.e., we provide the knowledge of s to the algorithm. All codes are available at httpps//gghhu...omooyyaaaammiiie
Uniform design. We consider a random design matrix, formed by choosing each entry from the distribution Uniform(-1, in i.i.d. fashion. In detail, we set n = 9000, p = 2000, and the sparsity level 4. We generate the entries of the noise w independently from Uniform(-O.. 0.1), and consider the linear model (T). We choose the design vector 3 with true sparsity = 4 and the support set 7" Ú j < 4). We set all the signal strength to be equal, taking the following two
forms: (i) Strong signal: 8y 2{(s l)g p)/n) //2 and (ii) Weak signal: 3, 2 (log p)/n) 1/2 for
all j E 7
Under these setups, we consider the privacy parameter& E E {0.5, 1, 5, 10} which are acceptable choices of E 335 Moreover, similar (or larger) choices of E are common in various applications including US census study [14, socio-economic study (38, and industrial applications [3] 52). For the Metropolis- Hastings random walk, we vary K E (0.5,2, 3.55) and initialize 10 independent Markov chains from random initializations and record the F-score of the last iteration. We use the CVXPY package 7 22 for solving the f--constrained optimization problem in the updating step of MCMC. We also track the qualities of the model through its explanatory power for convergence diagnostics. In particular, we calculate the scale factor R. := y y ||> for each model update along the random walk and compare those with Ri to heuristically gauge the quality of mixing. More details and set of comprehensive plots can be found in Appendix [D.]] where we also discuss more about the effect of and K on the utility. For K = 2, Table shows that F-score increases as & increases both in the cases of strong and weak signals. the algorithm is on par with the non non-private BSS. This is consistent with the inflection phenomenon pointed out in Theorem (o5orem3.3Jam a3d Corollary 444 Furthermore, as expected, we see that for a fixed e, the F-score is generally higher in the strong signal case.
fact, for & 2 3, the performance of

---

Table 2: Comparison mean P-score across chains for K under independent Uniform and Gaussian design. (*) denotes that the chain has mixed reasonably well.
Uniform Design
Gaussian Design
Privacy Level
Strong Signal
Weak Signal
Strong Signal
Weak Signal
6 0.5
0.025
0.00
0.00
0.00
8
0.15
0.05
0.00
0.00
3
1.00
0.15
0.025
0.00
1.00
0.40
0.375
0.075
10
1.00
1.00
0.925*
0.025
Non-private
1.00
1.00
1.00
1.00
We also carry out experiments under independent Gaussian design. The details and more compre- hensive discussion of the findings are deferred to Appendix [D.2] In summary, in this case also, our algorithm enjoys greater utility under the strong signal case as shown in Table 2
the experiments were performed Great Lakes cluster with 16 cores and 10 GB RAM. ABESS package is distributed under GNU General Public License, Version 3 CVXPY package distributed under Apache License, Version
Computational resources and license information
Conclusion
In this paper, we study the variable selection performance of BSS under the differential privacy constraint. order to achieve (pure) differential privacy, we adopt the exponential mechanism and establish its high statistical utility guarantee in terms of exact model recovery. Furthermore, for computational efficiency, we design a MH random walk that provably mixes with the stationary distribution within mixing time of the polynomial order in (n, 8). We also show that the samples from the MH random walk enjoy approximate DP while retaining a high utility guarantee with experimental underpinnings. In summary, discussed in Section 1.I establish both high utility and efficient computational guarantee for our model selection algorithm under privacy constraints, which is in sharp contrast with the previous works in DP model selection literature. Moreover, the proposed MCMC method is generic enough to adopt in other models beyond linear structures. For example, can this technique under the setup of generalized linear models with likelihood loss as the utility function. Therefore, our method can be used in diverse domains including medical studies fast- tiscktrack scientific discoveries and promote the practice of responsible AL.
To this end, we also point out some of the open problems and future directions. One limitation, of our main result Theorem 3.5 is that it requires the condition minyey- |3y| = 2(v(s logp)/n) in high-privacy regime. still an open question whether the extra / factor necessary for model selection. Future research along this line could focus solving BSS through DP mixed integer optimization (MIO). This would mcan an important contribution in this field as commercial solvers like GUROBI MOSEK would be capable of solving the BSS problems at an industrial scale with high computational efficiency using a general DP framework.
References
[1] Shuchin Acron, Venkatesh Saligrama, and Manqi Zhao. Information theoretic bounds for compressed sensing. IEEE Transactions on Information Theory, 56(10):5111-5133 2010.
[2] Akshay Agrawal, Robin Verschueren, Steven Diamond, and Stephen Boyd. A rewriting system for convex optimization problems. Journal of Control and Decision, 5(1):42-60. 2018.
[3] Apple. Learning with privacy scale. https://docc-aaseee..do developer apple com/ pdf 2017.
m1 preeseaacc///pppss//aaaaaaa www.aaawwn...ittppprrraaaaaaaaaa wwwp:iithwppaaaaa----eeaaaa
[4] Dimitris Bertsimas, Angela King, and Rahul Mazumder. Best subset selection via a modern
optimization lens. The Annals of Statistics. 44(2):813-852 2016.
10

---

[5] Dimitris Bertsimas and Bart Van Parys. Sparse high-dimensional regression: Exact scalable algorithms and phase transitions. The Annals of Statistics, 48(1):300 323, 2020.
[6] T'ny Cai, Yichen Wang, and Linjun Zhang. The cost of privacy: Optimal rates of convergence for parameter estimation with differential privacy. The Annals of Statistics, 4965):225-22500 2021.
[7] Steven Diamond and Stephen Boyd. CVXPY: A Python-embedded modeling language for convex optimization. Journal of Machine Learning Research, 17(83):1-5, 2016.
[8] David Durfee and Ryan M Rogers. Practical differentially private top-k selection with pay- what-you-get composition. Advances Neural Information Processing Systems, 32, 2019.
[9] Cynthia Dwork. Differential privacy. In International colloquium on automata, languages, and programming, pages 1-12. Springer, 2006.
[10] Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Advances in Cryptology- EUROCRYPT 2006: 24th Annual International Conference on the Theory and Applications of Cryptographic Techniques, St. Petersburg, Russia, May 28-June 1, 2006. Proceedings 25, pages 486-503. Springer, 2006.
[11] Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography: Third Theory of Cryptography Conference, TCC 2006, New York, NY. USA, March 4-7, 2006. Proceedings 3, pages 265-284. Springer, 2006.
[12] Jianqing Fan and Runze Li. Variable selection via nonconcave penalized likelihood and its oracle properties. Journal of the American Statistical Association, (34445)::338-1366 2001.
[13] Alyson K. Fletcher, Sundeep Rangan, and Vivek K Goyal. Necessary and sufficient conditions for sparsity pattern recovery. IEEE Transactions Information Theory, 55(12):575--5772 2009.
[14] Simson Garfinkel. Differential privacy and the 2020 census, https: http/mmittserrreee pubpub hwg::p///ifffeerrraaa--irvaaaa-p wttoo-usscoonuureleeeeeoo/e/eeee 2022.
[15] Edward I George and Robert E McCulloch. Variable selection via gibbs sampling. Journal of the American Statistical Association, 88(423):881-889, 1993.
[16] Xiao Guo, Hai Zhang, Yao Wang, and Jiang-Lun Wu. Model selection and estimation in high dimensional regression models with group SCAD. Statistics Probability Letters, 103:86-99 92,, 2015.
[17] Yongyi Guo, Ziwei Zhu, and Jianqing Fan. Best subset selection is robust against design dependence. arXiv preprint arXiv:2007.01478 2020.
[18] Chris Hans, Adrian Dobra, and Mike West. Shotgun stochastic search for "large p" regression. Journal of the American Statistical Association, 102(478):507-51,, 2007.
[19] Trevor Hastie, Robert Tibshirani, and Ryan Tibshirani. Best subset, forward stepwise or lasso? analysis and recommendations based on extensive comparisons. Statistical Science, 35(4):579-55 592, 2020.
[20] Hussein Hazimeh, Rahul Mazumder, and Ali Saab. Sparse regression scale: Branch-and- bound rooted in first-order optimization. Mathematical Programming, 196(1-2):347-388, 2022.
[21] Qianchuan He and Dan-Yo Yu Lin. A variable selection method for genome-wide association studies. Bioinformatics, 27(1):1-8, 2011.
[22] Jian Huang, Yuling Jiao, Yanyan Liu, and Xiliang Lu. constructive approach to 10 penalized regression. The Journal of Machine Learning Research, 19(1):403-433 439.4993..9,.. 2018.

---

[23] Jian Huang, Shuangge Ma, and Cun-Hui Zhang. Adaptive lasso for sparse high-dimensional regression models. Statistica Sinica, pages 1603-1618, 2008.
[24] Hemant Ishwaran and J. Sunil Rao. Spike and slab variable selection: Frequentist and Bayesian strategies. The Annals of Statistics, 33(2):730- - 2005.
[25] Prateek Jain and Abhradeep Guha Thakurta. (near) dimension independent risk bounds for differentially private learning. In International Conference on Machine Learning, pages 476- 484. PMLR, 2014.
[26] Shiva Prasad Kasiviswanathan and Hongxia Jin. Efficient private empirical risk minimization for high-dimensional learning. International Conference on Machine Learning, pages 488-497. PMLR, 2016.
[27] Daniel Kifer, Adam Smith, and Abhradeep Thakurta. Private convex empirical risk minimization and high-dimensional regression. In Conference on Learning Theory, pages 25-1. JMLR Workshop and Conference Proceedings, 2012.
[28] Demetris Lamnisos, Jim E Griffin, and Mark FJ Steel. Adaptive monte carlo for bayesian variable selection regression models. Journal of Computational and Graphical Statistics, 22(3):729-748, 2013.
[29] Jing Lei, Anne-Sophie Charest, Aleksandra Slavkovic, Adam Smith, and Stephen Fienberg. Differentially private model selection with penalized and constrained likelihood. Journal of the Royal Statistical Society Series A: Statistics in Society, 18 181(3):609-633, 2018.
[30] Min Lyu, Dong Su, and Ninghui Li. Understanding the sparse vector technique for differential privacy. Proceedings of the VLDB Endowment, 10(6))637-648, 2017.
[31] Frank McSherry and Kunal Talwar. Mechanism design via differential privacy. 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS 07), pages 94-103. IEEE, 2007.
[32] Nicolai Meinshausen and Bin Yu. Lasso-type recovery of sparse representations for high- dimensional data. The Annals of Statistics, 37(1):246 270, 2009.
[33] Benson Mwangi, Tian Siva Tian, and Jair Soares. A review of feature reduction techniques in neuroimaging. Neuroinformatics, 12:229-244 2244, 2014.
[34] Naveen N Narisetty, Juan Shen, and Xuming He. Skinny gibbs: A consistent and scalable gibbs sampler for model selection. Journal of the American Statistical Association, 2018
[35] Joseph Near and David Darais. challenges.
Differential privacy: Future work & open htttss//ww..iist..go/bbooggg cybersacurity
mist
2022.
[36] Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith. Smooth sensitivity and sampling in private data analysis. In Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, pages 75-84, 2007.
[37] Kamiar Rahnama Rad. Nearly sharp sufficient conditions on exact sparsity pattern recovery. IEEE Transactions on Information Theory, 57(7))4672 467)-46677667999 2011.
[38] Ryan Rogers, Adrian Rivera Cardoso, Koray Mancuhan, Akash Kaura, Nikhil Gahlawat, Neha Jain, Paul Ko, and Parvez Ahammad. A members first approach to enabling linkedin's 's labor market insights at scale. arXiv preprint arXiv:2010. 13981, 2020.
[39] Saptarshi Roy, Ambuj Tewari, and Ziwei Zhu. High-dimensional variable selection with heterogeneous signals: A precise asymptotic perspective. arXiv preprint arXiv:2201.01555 2022.
[40] Saptarshi Roy, Ambuj Tewari, and Ziwei Zhu. Tale of two (omplex) ities. arXiv preprint arXiv:2301.0625 2023.
[41] Alistair Sinclair. Improved bounds for mixing rates of markov chains and multicommodity flow. Combinatorics, probability and Computing, 1(4):351-370, 1992.
12

---

[42] Adam Smith. Privacy preserving statistical estimation with optimal convergence rates. In Proceedings of the forty-third annual ACM symposium on Theory of compuring, pages 813-822, 2011.
[43] Ben Stoddard, Yan Chen, and Ashwin Machanavajjhala, Differentially private algorithms for empirical machine learning. arXiv preprint arXiv: 1411.5428, 2014.
[44] Kumal Talwar, Abhradeep Guha Thakurta, and Li Zhang. Nearly optimal private lasso. Advances in Neural Information Processing Systems, 28, 2015.
[45] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature selection via stability arguments, and the robustness of the lasso. In Shai Shalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Annual Conference on Learning Theory, volume 30 of Proceedings of Machine Learning Research, pages
Princeton, NJ, USA, 12 14 Jun 2013. PMLR.
[46] Martin J. Wainwright. Sharp thresholds for high-dimensional and noisy sparsity recovery using I -constrained quadratic programming (lasso). IEEE Transactions on Information Theory, 2009.
[47] Di Wang and Jinhui Xu. On sparse linear regression in the local differential privacy model. In International Conference on Machine Learning, pages 6628-6633 PMLR, 2019.
[48] Di Wang, Minwei Ye, and Jinhui Xu. Differentially private empirical risk minimization revisited: Faster and more general. Advances in Neural Information Processing Systems, 30, 2017.
[49] Yu-Xiang Wang. Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain. arXiv preprint
2018.
[50] Dawn B. Woodard and Jeffrey S. Rosenthal. Convergence rate of Markov chain methods for genomic motif discovery. The Annals of Statistics, 41(1):91 - 124, 2013.
[51] Yun Yang, Martin J. Wainwright, and Michael I. Jordan. On the computational complexity of high-dimensional Bayesian variable selection. The Annals of Statistics, 44(6):2497 2532, 2016.
[52] McGee Young, Mare-Antoine Paré, Harry Bergmann, et al. Differential privacy for expanding access to building energy data. In ACEEE Summer Study Energy Efficiency in Buildings Proceedings, 2020.
[53] Cun-Hui Zhang. Nearly unbiased variable selection under minimax concave penalty. The Annals of Statisties, 38(2):894 942, 2010.
[54] Cun-Hui Zhang and Jian Huang. The sparsity and bias of the lasso selection in high-dimensional linear regression. The Annals of Statistics, 36(4):1567-1594, 2008.
[55] Cun-Hui Zhang and Tong Zhang. A general theory of concave regularization for high- dimensional sparse estimation problems. Statistical Science, 27(4):576-593 2012.
[56] Fan Zhang, Wei Li, Yifan Zhang, and Zhiyong Feng. Data driven feature selection for machine learning algorithms in computer vision. IEEE Internet of Things Journal, 4272 2018.
[57] Peng Zhao and Bin Yu. On model selection consistency of lasso. The Journal of Machine Learning Research, 7:2541-255 2006.
[58] Jin Zhu, Xueqin Wang, Liyuan Hu, Junhao Huang, Kangkang Jiang, Yanhang Zhang, Shiyun Lin, and Junxian Zhu. abess: A fast best-subset selection library in python and Journal of Machine Learning Research, 23(202):1-7, 2022.
13

---

A Proof of Main results
A.1 Proof of Lemma 3.1
Recall that ug( (7; x,y) = -In, (X. where = Ei= 3). There-
fore, it suffices to show that L, (1. is data monotone. Let D D U (x++1 1 1n We define
{(xi, Di) and D
Bnn = arg B:l|@ll min
y) 33),
<K
B nn 1,7 arg p:llil, SK
(y/ x 3)2
Therefore, have the following inequalities:
n+1 Ui - 3
n
Ty (D')
Σ (y - x
(y: - x 3T, _Iy, (D). Σ
(=1
The above inequalities conclude the proof.
A.2 Proof of Sensitivity Bound (Lemma 3.3
Let y) and (X,y two neighboring datasets with n and n + observation respectively. For subset y E L. U {,"), consider the OLS estimators follows:
B 3y == arg ming: | lyy x, 01 and By. := arg ming; 011, 3 - xx
From the definition of the score function u(?; X, y), we have
u(1:X,y] Σ
(ys B.,
1=1
u(>; x) = Σ
(y) - B,,Bk, - (fn+1 - -xIT,1,
1=1
By the property of the OLS estimators, we have
u(>; X, y) u(1;X,5))
(y: xT, (#n+1 - xT 3,.kk
Σ
(H) By,B,,K)²
1=1
i=1
> (y)s 3T,
(Un+1 - X B,,kk)
(y) 33,
i=1
i=1
(in+1 - x 1,7 By,k)
< (r Fmax KY²
Similarly, we have u(y; X. u(>; X, I (r + 2). Next, the (s, (D follows from Lemma 2.2 This finishes the proof.
A.3 Proof of Utility Guarantee (Theorem 3.5
Consider the notation in Section B.I and recall the event EK Nnmeaa 18 = -T,ole) We will For notational brevity, we use L,, to denote yX. Now, we restrict ourselves to the event Ex- therefore we have T. T.,, for all 7. To establish lower bound ()")), we make use of specific form, thereby obtaining the following inequality:
14

---

(>-))
c(be))-by Au
1 Exe,, exp
Now we fix & E [s]] and and consider any 7 E Ha,k. For any vj E [0, 11, note that
n (Ly Lay-)) n 1 (I, Φydy y b
=n (x7.1113..15 ww) Tw((L, (4, - 11,-) (X, (17 + w) ww (U1n py-)w)
,1 +2- 1n)_m))33_ ,,,)),, (,)) - 22 D 1n (-w)
+1 "( -n (Φ) -B,-)) jw.
Consider the random variable Following the analysis of Theorem 2.1 in 17 we have
P
max yEar,
2n 1 [[I,
D2 (n w 2 2- - ,, S 2c 6k logp
and,
w ( D..-) )w 2 (1- m)) ,,, |
I
max n nE
4e 2h log
whenever
mingeds NT T(x) 2 Co² log
nn(1 - 17)
for large enough universal constant C > 0. Setting = 1/2, we note that whenever m, (s) 2 (Cogg p)/n). we get
n (L, - byy 3 (1)) 2 km (s)
for all y E ss.
2
with probability at least we have
2p 4p-2. Also, note that B T [()) S s Hence,
16Au
0² Poog
(s) 2 max 2C,
EO2
the following are true:
E(L,, Laye)
Σ exp
Au
nkam, (s)
Σ exp
2Au
Eedd
p
nkem, (8)
exp
k
2Au
k=1
2k p
4k
<p
k=1
Therefore, we have
min (<)) 2 uffr)
1+p-2 2 p-p--2
7E
with probability 1 - 2p 4p
Now by the discussion in Section B.1 we have P(Ex) 2 1 -2
++ Imax for K 2 Vā
)o This finishes the proof.
15

---

A.4 Proof of Lemma 4.1
For clarity, we first specify some notations. Let 7f denote the model update of MH chain run over dataset D. Let oy be the corresponding 7-mixing tim. Let D and D' be two neighboring datasets, and x0 and n D' be the corresponding probability mass functions for the exponential mechanism. Then, we have the following:
P( D
=) (7) +1
S <x (7) +1
$ e PPpp D' = 7 + +
This finishes the proof.
A.5 Proof of Mixing Time (Theorem 4.3
We again restrict ourselves to the event Ex with K 2 Vol v=(( mmax + ( 1k=)ommas For the proof,
let P denote the transition matrix of the original Metropolis- HasttpllisHHastins sampler (1O). In this case, the state space is / = s U {?"}. Now consider the transition matrix P= P/2 + /2, corresponding to the lazy version of the random walk that stays in its current position with probability of least 1/2. Due to the construction, the smallest eigenvalue of P is always non- non-neg negative, and the mixing time of the chain is completely determined by the second largest eigenvalue A2 of P. To this end, we define the spectral gap Gap(P) = A2, and for any lazy Markov chain, we have the following
sandwich relation 41 50
(1 -1- Gap(P)
1og[1/ min π(>)] + log(1/1)
S
(15)
2
Gap(P)
(P)
Lower Bound on (
To establish a lower bound on the target distribution in we make of its specific form, thereby obtaining the following inequality:
x()) (T>"). a())
T(**)
1
E(LY - Lyg))
1 Exed, exp
c(I.,1-b,n)) Au
exp
Au
Now we fix &s E [s). and and consider any ? E Ask.
Similar to the proof of Section A.3 note that whenever (s) 2Co² ((lgg)//)) (Co2((logp) for large
enough universal constant C' U, we get
3 / ( 2n (L.y L.p))
1
km, (s)
5 3, (
for all E ss,
2
with probability at least we have
2p 4p Also, note that 3,, ((7) S n. sl Hence,
16Au
a² log
m. (s) 2 max 20,
202
16

---

the following are true:
-(Ly'_Ly')
E(Ly' -
Lige)
Σ
exp
Au
E'Eak
nkkem (8)
exp
2Au
8 p
nkem, (s)
exp
k
k
2Au
kml
p PP
1k
-2
k=
and,
e(Ly 8(by-L Lige)
3nsB yo (1)8
exp
2 exp
Au
2Au
3NSER b
exp
2
Combining these two facts we have
min (7>) 2 1 yEaLU(("
3nsEki max
b
3nsEKi b
exp
exp
(16)
p-
2Au
2Au
with probability 1 2p 4p 2
Lower Bound on Spectral Gap:
Now it remains to prove lower bound on the spectral gap Gap(P), and we do so via the canonical path argument 41 We begin by describing the idea of canonical path ensemble associated with Markov chain. Given a Markov chain C with state space F, consider the weighted directed graph G(C) = (V, E) with vertex set V f and the edge set E in which a ordered pair (7, is included as edge with weight Q(e) = Q77,7')
π ((r) 7") iff P(y,n') > 0. A canonical path ensemble T corresponding to a collection of paths that contains, for each ordered pair (717)) of distinct vertices, unique simple path T,,y' connecting and y. We refer to any path in the ensemble T as a canonical path.
41 shows that for any reversible Markov chain and nay choice of canonical path ensemble T, the spectral gap of lower bounded as
Gap(P) ((T)((T))
(17)
where E(T) corresponds the length of the longest path in the ensemble Т, and the quantity p(T) = maX.cE Q(e) (e nT (T7)=(7'') is known as the path congestion parameter.
Thus, it boils down the construction of suitable canonical path ensemble T. Before going into further details, we introduce some working notations. For any two given paths Tj and T2:
Their intersection Ti T2 denotes the collection of overlapping edges.
If T2 Ti, then Ti Ts denotes the path obtained by removing all the edges of T2 from Ti.
We use T, denote the reverse of Ti.
If the endpoint of Tj is same the starting point of T2, then Tj T2 denotes the path obtained by joining Ti and T2 at that point.
We will now shift focus toward the construction of the canonical path ensemble. high level, our construction follows the same scheme in (51).
17

---

Canonical path ensemble construction:
First, we need to construct the canonical path T from any 7 E J to the true model y", To this end, we introduce the concept memoryless paths. We call a set Ta of canonical paths memoryless with respect to the central state y" if
1. for any state E I satisfying 7 + y², there exists a unique simple path Ty in Ths connecting 7 and y";
2. for any intermediate state 7 9 on any path T E TMs the unique path connecting and 7d is the sub-path of To,y" starting from ÿ and ending at y"
Intuitively, this memoryless property tells that for any intermediate step in any canonical path, the next step towards the central state does not depend on history. Specifically, the memoryless canonical path ensemble has the property that in order to specify the canonical path connecting any state 7 E y and the central state y", we only need to specify the next state from y E y \ {>") i.e., need transition function 9 : yf {Λ*} - y that maps the current state y to the next state. For simplicity, define ((>") = y to make y the domain of G. For more detailed discussion,
point the readers to Section 4 of [51]. We now state a useful lemma that is pivotal to the construction of the canonical path ensemble.
Lemma A.1 ((5I). If function G 9 {r"} du 7") for any state E (7"), then G is a valid transition map.
- I satisfies the condition du (g())))))))
Using the above lemma, we will now construct the memoryless set of canonical paths from any state f to by explicitly specifying a transition map G. In particular, we consider the following transition function:
If 7 # y", define G(7) to be 7 wheh is formed by replacing the least influential covariate in with most influential covariate in 7" \ y. In notations, we have 7/- = 9 for all
j $ (ix, ) 1// = and th = 0. where jy = arg max je>""> - >00
X- 3- || and
k, == arg = c X
X- 112 3-- Thus, the transition
step involves double flip which entails that du (9()),))) = du dx()")))
Due to Lemma A. it follows that the above transition map G is valid and gives rise to a unique memoryless set TM of canonical paths connecting any y E 9 and 7
Based on this, we are now ready to construct the canonical path ensemble T. Specifically, due to memoryless property, two simple paths T T, and Ty'... share an identical subpath to y starting from their first common intermediate state. Let Tyny denote the common sub-path Tynn n Tyymys and Tayy' Typ \ Tyny denotes the remaining path of T,,y- after removing the segment Tyny' The path Ty is defined in a similar way. Then follows that Taxy' and Tyyn have the same endpoint. Therefore, it is allowed to consider the path I Ta U.
We call 7 precedent 7 if o is on the canonical path Ty, E T, and a pair of states y, are adjacent if the canonical path T is Gxyy' the edge connecting y and y/. Next, for y E I, define
A()) = (7 1
(18)
denote the set of all precedents. We denote by IT'| the length of the path T. The following lemma provides some important properties of the previously constructed canonical path ensemble.
Lemma A.2. For any distinct pair (7,r') E Ef x I::
(a) We have
[T S du d2( and [Ta I (du(1) 7²) (0 < 2s.
(b) If and o are adjacent and y is precedent of of r. then
{(5,7) Gnpy E TT A(7) x G
18

---

Proof. For the first claim, let us first assume that [T,,-= = k, i.e., (7) = for the appropriate transition map G. Also, recall that hy| =>>*= =s. Hence, due an elementary iterative argument, follows that
2s 2 du(,,)") dd(((()), = =d (7)) +4
2k.
Also, note that [Tayl |T [Tyrr] Hence, the claim follows using the previous inequality.
For the second claim, note that for any pair (5, 5') such that Ta,3 3 Eayy's we have two possible options (i) ey,y Tayy,, (ii) e E Ty As y is precedent of y', the only possibility that have is C,py T Toy. This shows that y belongs to the path T and A(y).
According to Lemma A.2 b) the path congestion parameter p(T') satisfies
(f))=(5') = max [A(c))] (nte)rr Q()r())
P(T) < max
Σ FEA
(19)
(at')r. Q(),
where the set r. := ((%+7) E 9 y Ty,y' e 7 A(y)). Here we used the fact that the weight function Q satisfies the reversibility condition Q(7, Q(?', .)) in order to restrict the range of the maximum to pairs (7, 7') where y E A(7)).
For the lazy form of the Metringlls-Hastings walk 10
we have
Q( = (7>))(())))
{1,
7(>') x<>)
2 n (7) min
2 min ((())=
ps
Substituting this bound in 19 we get
x(A()))
p(T) S ps
(my')rr, min (=(7), x ((²))
max
(20)
T(7)
+(A(7)) )
ps max (r.r))r.
max
(n))
In order to prove that P(T) = (ps) with high probability, it is sufficient prove that the two terms inside the maximum are (1)) To this end, we introduce two useful lemmas.
Lemma A.3. Consider the event
An
max w ( xute Φ.)w S 1202 log PEV,EET
Then we have PP(A.) 2-
Proof. First note that w ( (uff))) & D,)w- = (h for an appropriate unit vector h,,, depending only upon X, and X₁. By Sub-gaussian tail inequality, we have
P [(hT.w)²
2e -
Setting t 12o2s log p and applying union bound we get
IP
max > 12o2s log p
(hT,o)²
< 2
(p
s)p 6s
1E ,849
2p 30
5 p
19

---

Lemma A.4. Suppose that, in addition to the conditions in Theorem 4.3 for all y + Y, we have
the event An holds. Then
T (
(g())) S Sp
Moreover, for all %
17 x(A())]
2.
π (>))
Therefore, both Lemma A.3 and Lemma A.4 give (( S 2ps with probability - p-= Lemma
A.2
suggests that ((T) 2s. Therefore, Equation 11 shows that Gap(P) 2 aps" with probability
Finally, combining (66] and 15 we get the following with 1 - 8p-
nEK+ 1
To C2ps?
max
log(1/n)
mma
where C2 > O is a universal constant. Finally, the proof is concluded by arguing that (P( s 2p-2
B Proof of Auxiliary Results
B.1 Constrained problem to unconstrained OLS problem
Now we are ready to bound |By ll1- Define the OLS estimator corresponding to the model as X X x, Byy
X w
Gyo =
Y2
Y2
In this section, we will show that there exists a choice for K such that the event EK Oyda== (3 ols = [, holds with high probability. By Holder's inequality we have || 2l S
[X, X, //nn) 1l.p X x, /n Il ||, ll2 I
) Hence, an application of Cauchy-
Schwarz inequality directly yields that ||ill
S /sbmaxx Next, note that
| <
X. w
X
w
V
X
w
n
n
Therefore, we get ||u2||1 S
X w/ llx In order to upper bound the last term in the previous inequality, define Dr. = X(i,j Juy for all (i.j) E [s] [n). Using the sub-Gaussian property of Wy, we have E(erws)) S x²²² >=m=n
o² 12, Therefore, due to Hoeffding's 's inequality, we have
log 2p
Σ
DaS 80xmax V n
72
jE(n)
Note that || follows that
X
w/ w/nllao maxie(s) n
EjE[n) D Hence, by simple union-bound argument,
X w
log n
P
max 7///=
2 80.Tmax
< 2p < 2p
n
Thus, Assumption
3.4 c)
yields that || k 1|2 < 8 Umax + ( J
2
Therefore, if K >
5 [++ )mma
+
8 Do max then P(Ex) 2 1 - 2p -2
B.2 Proof of Corollary 4.4
Based on Theorem 4.3 we have ||TT
S eta with probability at least 1 c2p- whenever t
is sufficiently large. Also, by Theorem 3.5 we know x(>*) 2 p= with probability cpp-2
Therefore, we have (T()") 2 1 - 7) p with probability at least (a + 2 This finishes the proof.
20

---

C Proof of Lemma A.4
part (a):
Let jr: ky be the indices defined in the construction of (()). The we have = +0 ( [ky) Let
V1 = ( ( ,- By. and V2 (Φh (u((d) 4, X 3y. Then Lemma C.1
guarantees
that
v 2 nn (s),, and ||v2l2 I nx (s)/2.
(21)
By the form in 7). we have
(1) = exp y (D. $ (>²)
(Au/E) S
To show that the above ration O(1), it suffices to show that y T (B.. byyy is large. By simple algebra, it follows that
( D, = y ( (BrUfs+) 1, y
y ( - D,
1|vill2 + 2v, w + w (
T (BuUddT) - b,,) - {11v2l1 + +v2 w w ( - )w lIvill2 + 2v, (Pru(i)) / w T ( (Pqu(in) w
{Ilvall 112 + 2v2 o (u(()) $ |w + w ( (BrU(i) )
2 || (1lv 112 - -2 ( (B - $ (b))wll) - ||22|22 (1/vall2 + 2 [ - D (wlp)
|| [| (0(ي) - Py wll
(22)
Now, we recall the event
max T TT (Byu() 2,)w S 1202s 1202slogr A, FET
Let A n1 M. (8) 2 K_ K_ Coo logp. Then for Co large enough that Co 2 (128 x 12)s,
Equation (22) leads to the following inequality under event A,;
y ( - 1, 2 A(A - A/4) - (A/V2) A/4) A2/16 A/8.
This readily yields that
(7))
nK_m. (s) } sp (16Au/E)
S exp
(23)
((7")
under the margin condition of Theorem
4.3
Part (b):
From the previous part, the bound (33 implies that x(7)//(9(1)) S p-3 For each 7. E M(2), we Tkk where h: [Tg is the
have that y T7py T Let the path Ts be nt 7 length of the path, and fo = 7 and " = y are the two endpoints. Now note that (yeesk-1 C P
and (23 ensures that
r (5)
((7-11) (Te))
S 3k
(T))
Also, by Lemma A.2 a) we have l E [s]. Now, we count the total number of sets in A(y) for each E [s]. Recall that by the construction of the canonical path, we update the current state by adding a new influential covariate and deleting one unimportant one. Hence any state in I has at most sp adjacent precedents, implying that there could be most s distinct paths length This entails that
क (A(1)) T(7)
Σ BEA())
I(5) ((7)
(ps)*p
34
<
1
22
1
1/p
1=1
k=1
21

---

C.1 Supporting lemmas
Recall the definition of jy and ky, The first result in the following lemma shows that the gain in adding J, to the current model y is at least m. (s). The second result shows that the loss incurred by removing ky from the model y {i>] is most nk_m, (s)
As result, it follows that it is favorable to replace Xs, with the more influential feature Xj, in the current model 7.
Lemma C.1. Under Assumption 3.4 b) and Assumption 4.2 the following hold for all y E Ae
(a) o (r00, X B 1
Φ x, By-111 2 nn (s), and
(b) @ (Pul)))) x p 1
nx (s)/2
Proof. For each 9² 7 we have
_ Puue x,, 8, 1 2 X By
11
B.. T p {u(E) - -.,)
B X. (In (b,)) X (In -D,)
X, (hn 41)X1
B 1/ y2 (In $ X (In - -,,, 2,)
XT XT
n
where the second equality simply follows from Gram-Schmidt orthogonal decomposition. By summing the preceding inequality over E y" 7, we get
S ,T X (Ln
7' (In - 2,)X, 1,)
Putee 3y- 1
Σ
| Br. 11
n
2 k BT x,,, x - 2 xy))xri
2 nk_ r 7" (s)
nk_ h > (s).
The last inequality follows from the fact that hy = |7|| Since j, maximizes
x,-
over all l E 7" \ 7, the preceding inequality implies that
( X 33 11 - | By 11 2 nk ns__, (s).
Similarly, to prove the second claim, first note that for any l: E 7 70" we have
② (k) X,- 3r- 1| 1 Br- 112 = BT XT
y- / 1 rU()) D ) 1 B Byrbo
B Byer
7 b (In $x X,X, (In, pxy) )x Ny
X (In 22)Xi
=(c,,
(In $ $,x)x,
(L. D Xx,) x 7-/00 [1
< 11 11
X X (In, B )x+
(1 4xyr) {x
X 7 (In - p.y X
< 6
[1 + X 2/
Since k. minimizes | (rru() X,, By, 112 - -I. 11: over all possible A E E 7 by As-
sumption 4.2 we have
- nk (
22

---

D More simulation details
D.1 Independent Uniform design
Under the setup of Section 5 we consider the privacy parameter E {0.5, 3, 5, 10). For the Cetropolis-Hastting random walk, we vary K E {0.5, 3.5} and initialize 10 independent Markov chains from random initializations and record the F-score of the last iteration. We also track the qualities of the model through its explanatory power. In particular, we calculate the scale factor R. : y / |yy 11 for each model 7 E (1)221 along the random walks. Typically, high value of R. will indicate the superior quality of the model 7, Note that - |lyl (1 R.)) is proportional to the log of the probability mass function function of 7. Thus, tracking Ry equivalent to tracking the log- log-likelihood of ry along the random walks.
Strong signal: Under this setup, note that the model estimate of ABESS exactly matches the true I shows that all the chains have identified reasonably good estimate of the true model 7 within 50p iterations. This empirical phenomenon validates theoretical findings in Theorem 4.3 However, for larger values of K the performance is worse as the noise level also large. On the other hand, for the case of K 0.5, the performance is also worse due to too much shrinkage that results in a bad estimate of B. The mean F-score's 's also suggest the same phenomenon. For smaller values of e, the performance is generally bad due to increased noise level. This is expected as higher privacy usually entails a worse performance in terms of utility.
model. For e 2 3 and K 2 2, Sigur
Weak signal: We perform the same experiments under a weak signal regime. As expected, both Figure Fig and Table][]how that the performance of the proposed algorithm is generally inferior to that in the strong signal regime for K 2 2. However, note that our algorithm enjoys a better utility for K 0.5. In fact, performance is as good as the non-private BSS for 2 3. This is not surprising as K = 0.5 closer to |اه||, x 0.7 in the weak signal case and results in better estimation for B. On the contrary, larger values of K inject more noise into the algorithm and the utility deteriorates.
D.2 Independent Gaussian Design
We consider an independent Gaussian design matrix, formed by sampling entries from identical independent standard normal distributions and normalized by the loo norm. Specifically, we set n = 900, p = 2000 with the sparsity level s = 4. Similar to the setup in Section we generate entries with independent Uniform(-De (-0.1, 0.1) noise w following the linear model ( We choose the design vector (3 with true sparsity s = 4 and the support set y = {( 1 1 I 4}. All the signal strengths are set to be equal, taking the following two forms: (i) Strong signal: B, = 2{(s log p)/n))/n///)) 1/2, and (ii) Weak signal: By = 2 (log /m/n for all j E >²h We consider the privacy parameter E (0.5, 1,3,5, 5, 10). For the Metropolis-Hastiine initialize 10 independent Markov chains from random initialization and record the F-score of the last iteration.
random walk, vary K E (0.5, 3, 3.5) and
Strong signal: Under this setup, note that the model estimate of ABESS exactly matches the true model with F-score 1. For the case of K 0.5, Figure 3 shows the performance is better compared with settings K 2 2 when & < 5. However, when & = 10, the performance is worse due to shrinkage of the estimate of B3 while the estimations in other settings are easier due to lower privacy requirements. For higher values of e, the performance is generally strong because of the reduced noise level. This is expected since lower privacy typically leads to better utility performance. Notice that for e = 10 and K 2, we have a fairly accurate estimate of the true model y within 50p iterations.
Weak signal: We conduct the same experiments under weak signal regime. As expected, Figure 4 shows that the performance of the proposed algorithm generally inferior to that in the strong signal regime for K 2 2. However, note that our algorithm enjoys a better utility for K = 0.5 when
E $ 3. In fact, performance is as good as the non-private BSS for ε = 10. This is not surprising as K = 0.5 closer to || x 0.7 in the weak signal case, leading to better estimation for B. In contrast, larger values of K introduce more noise into the algorithm and weaken the utility.
23

---

toit
0.5, K 0.5
(b) 0.5, K
(c) 0.5, K 3
(d) 0.5, K 3.5
CW14
Av
PatroD
8 1, K = 0.5
= 1,
=
(h) 8 = 1, K 3.5
E = 3, K 0.5
( E = K,
(k) 6 = 3, =3
() E 3, 3.5
Nuwe plaM
(m) 5, K 0.5
5, K ==
5, K
(p) 5, K 3.5
Criil
50
(q) 10, K 0.5
(r) 10, K =
(8) 10, K= =
(1) 10, K 3.5
Figure 1: Cetropolis-Hasting random walk under different privacy budgets and E regularization. (Strong signal)
24

---

0.5, K 0.5
(b) 0.5, K
(c) E 0.5, K 3
(d) 0.5, K 3.5
PatroD
(e) 8 1, = 0.5
61) = 16=1
= 1, K 3
(h) 5 = 1, K = 3.5
(i) E = 3, K 0.5
( =0 3, K
(k) 6 = 3, K 3
() E 3, 3.5
Nuter plaM
Pauim wlol
(m) 5, K 0.5
5, K = 2
(0) K 3
(p) 5, 3.5
Crill
50
(g) 10, K 0.5
(r) =
(8) 10, K 3
(1) 10, K 3.5
Figure 2: Eetropolis-Hssting random walk under different privacy budgets and E regularization. (Weak signal)
25

---

EB
0.5, K 0.5
(b) 8 0.5, K
(c) 0.5, K 3
(d) 0.5, K 3.5
Av AydraD
PatroD
(e) E = 1, K = 0.5
()) = 1, 1,=21
= 1, =
(h) 8 = 1, K= 3.5
(1) E = 3, K 0.5
( E = 3, K==
(k) E = 3, K=3
() E 3, 3.5
Suter plad
(m) 5, K 0.5
5, K
(0) 5, K 33
(p) 5, 3.5
50
(g) 10, K = 0.5
(r) K0
(8) = 10, K =
(1 10, K 3.5
Figure 3: Gaussian setting Metropolis- -aastings random walk under different privacy budgets and L regularization. (Strong signal)
26

---

EB
(a) 0.5, K 0.5
(b) 0.5, K
(c) 0.5, K 3
(d) 0.5, K 3.5
A
PydroD
(e) = 1, 0.5
(1) 6 = =
K, =
(h) 8 = 1, K 3.5
(i) E = 3, K 0.5
1 E = 3, K=
(k) E = 3, K
() E 3, 3.5
plad
(m) 5, K 0.5
5, K 2
5, K
(p) 5, 3.5
50
(g) 10, K 0.5
(r) K
(8) = 10, K. =
(1 10, K 3.5
Figure 4: Gaussian setting Metropolis- -Hattings random walk under different privacy budgets and L regularization. (Weak signal)
27

---

NeurIPS Paper Checklist
The checklist is designed encourage best practices for responsible machine learning research, addressing issues of reproducibility, transparency, research ethics, and societal impact. Do not remove the checklist: The papers not including the checklist will be desk rejected. The checklist should follow the references and precede the (optional) supplemental material. The checklist does NOT count towards the page limit.
Please read the checklist guidelines carefully for information on how to answer these questions. For each question in the checklist:
You should answer [Yes], [No] or [NA].
[NA] means either that the question is Not Applicable for that particular paper or the
relevant information is Not Available.
Please provide short (1-2 sentence) justificatin right after your answer (even for NA).
The checklist answers are an integral part of your paper submission. They are visible to the reviewers, area chairs, senior area chairs, and ethics reviewers. You will be asked to also include (after eventual revisions) with the final version of your paper, and its final version will be published with the paper.
The reviewers of your paper will be asked to use the checklist as one of the factors in their evaluation.
While "[Yes] " is generally preferable to "[No]" ", is perfectly acceptable to answer "[No] "provided proper justification is given (c.g., "error bars are not reported because it would be too computationally expensive" or "we were unable to find the license for the dataset we used"). ). general, answering "[No] or "[NA] is not grounds for rejection. While the questions are phrased in binary way, we acknowledge that the true answer often more nuanced, so please just use your best judgment and write justification to elaborate. All supporting evidence can appear either in the main paper or the supplemental material, provided in appendix. If you answer [Yes] to a question, in the justification please point to the section(s) where related material for the question can be found.
IMPORTANT, please:
Delete this instruction block, but keep the section heading "NeurIPS paper checklist",
Keep the checklist subsection headings, questions/answers and guidelines below.
Do not modify the questions and only the provided macros for your answers.
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification: In the abstract and introduction we claim that our our method provides a DP model estimator while enjoying computational efficiency. This matches with the theoretical and experimental demonstrations in the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims made the paper.
The abstract and/or introduction should clearly state the claims made, including the contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results be expected to generalize other settings.
is fine include aspirational goals as motivation long is clear that these goals are not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors? Answer: [Yes]
28

---

Justification: We point out some of the limitations of the work and possible future directions in the Conclusion section.
Guidelines:
The answer NA means that the paper has no limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create a separate "Limitations" section their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g.. independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested on a few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should be articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution low or images are taken in low lighting. Or speech-to-ten system might not be used reliably to provide closed captions for online lectures because it fails to handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and fairness.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged in the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play an impor- tant role in developing norms that preserve the integrity of the community. Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory Assumptions and Proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and a complete (and correct) proof?
Answer: [Yes]
Justification: We explicitly mention all the assumptions in the statement of the theorems and lemmas. The proofs of these results can be found in the appendix sections.
Guidelines:
The answer NA means that the paper does not include theoretical results. the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented by formal proofs provided in appendix supplemental material.x
Theorems and Lemmas that the proof relies upon should be properly referenced.
4. Experimental Result Reproducibility
Question: Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Answer: [Yes]
Justification: We clearly state all of the key parameters of the simulation experiments the simulation section.
29

---

Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
If the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel urchitecture, describing the architecture fully might suffice, or if the contribution a specific model and empirical evaluation, may be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access to a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurIPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm. (b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either be way to access this model for reproducing the results or a way to reproduce the model (e.g., with an open-source dataset instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, may be that access to the model limited in some way (e.g., registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Question: Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, described in supplemental material?
Answer: [Yes]
Justification:
The Github Link is provided in the footnote of Page 9,
Guidelines:
The answer NA means that paper does not include experiments requiring code.
Please see the NeurIPS code and data submission guidelines (https://nips.co
for more details.
While we encourage the release of code and data, we understand that this might not be possible, so "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (e.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https
hhipss.c//ublic/uuddds wttpee///oooeSeeeeeoeoeoooo
www.obiiiiiiioooooooiiooo for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
30

---

At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information as possible in supplemental material (appended to the paper) recommended, but including URLs to data and code is permitted.
6. Experimental Setting/Details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary to understand the results?
Answer: [Yes]
Justification: We do the experiments on simulated data. Therefore, technically, we just have the testing step. We do specify clearly about this step the simulation section.
Guidelines:
The answer NA means that the paper does include experiments.
The experimental setting should be presented the core the paper to level of detail that is necessary to appreciate the results and make sense of them.
The full details can be provided either with the code, in appendix, supplemental material.
7. Experiment Statistical Significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: We do not include the error bar for the F-scores as the results are pretty robust across different repetitions.
Guidelines:
The answer NA means that the paper does include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars are capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, overall
run with given experimental conditions).
The method for calculating the error bars should be explained (closed form formula, call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
It should be clear whether the error bar is the standard deviation the standard error of the mean.
is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables or figures symmetric error bars that would yield results that are out range (e.g. negative error rates).
If error bars reported in tables plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments Compute Resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification: We have added the information about the computational resources in Section 5.
31

---

Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount of compute required for each of the individual experimental runs as well as estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported the paper (e.g., preliminary or failed experiments that didn't I make it into the paper).
9. Code Of Ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurlPS Code of Ethics httpppp//aaarrss...cppp.../..ato
Answer: [Yes]
Justification:
This research work does not violate any NeurlPS Code of ethics.
Guidelines:
The answer NA means that the authors have reviewed the NeurIPS Code of Ethics.
If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there special consid- eration due to laws or regulations in their jurisdiction).
10. Broader Impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: We point toward the potential positive impacts of our work the conclusion sections. To the best of our knowledge, could not think of any negative societal impact of our work.
Guidelines:
The answer NA means that there is no societal impact of the work performed.
If the authors answer NA or No. they should explain why their work has no societal impact or why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deployment of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out that a generic algorithm for optimizing neural networks could enable people to train models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used as intended and functioning correctly, harms that could arise when the technology being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative societal impacts, the authors could also discuss possible mitigation strategies (e.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of MI.).
11. Safeguards
32

---

Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [NA]
Justification:
This paper poses no such risks.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors should describe how they avoided releasing unsafe images.
We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g., code, data, models), used in the paper, properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We clearly cite the main webpage information and relevant papers regarding the used packages in the paper along with the license information.
Guidelines:
The answer NA means that the paper does not existing assets.
The authors should cite the original paper that produced the code package dataset.
The authors should state which version asset used and, possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset.
For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, wwwpsswieeesseeeeeeeeee thcode com datasets has curated licenses for some datasets. Their licensing guide can help determine the license dataset.
For existing datasets that are re-packaged, both the original license and the license of the derived asset (if has changed) should provided.
If this information is not available online, the authors are encouraged to reach out to the asset's creators.
13. New Assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer:
[Yes]
Justification:
The Github Link to code is provided in the footnote of Page
Guidelines:
The answer NA means that the paper does not release new assets.
Researchers should communicate the details of the dataset/code/moodl part of their submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose asset is used.
33

---

At submission time, remember to anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and Research with Human Subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given to participants and screenshots, if applicable, as well details about compensation (if any)?
Answer: [NA]
Justification:
The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Including this information in the supplemental material is fine, but if the main contribu- tion of the paper involves human subjects, then as much detail as possible should be included in the main paper.
According the NeurIPS Code of Ethics, workers involved in data collection, curation, or other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional Review Board (IRB) Approvals or Equivalent for Research with Human Subjects
Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or an equivalent approval/review based on the requirements of your country or institution) were obtained?
Question:
Answer: [NA]
Justification: The paper does not involve crowdsourcing nor research with human subjects.
Guidelines:
The answer NA means that the paper does involve crowdsourcing nor research with human subjects.
Depending the country in which research is conducted, IRB approval (or equivalent) may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and we expect authors to adhere to the NeurlPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such as the institution conducting the review.
34


Reviews:
[{"review_id": "NcPs2zQjJ8", "reviewer": "Reviewer_QExW", "summary": "This paper studies the best subset selection (BSS) problem in high-dimensional sparse linear regression. The results of this paper are roughly as follows:\n- First, adopt the exponential mechanism to design a DP BSS algorithm. The statistical/privacy guarantee of this approach can be derived based on standard techniques.\n- Second, devise an efficient MCMC sampling algorithm that still enjoys approximate DP, while having a polynomial mixing time.\n- Numerical experiments focus on a synthetic example, with a random design matrix, as well as a US census study and another socio-economic study.\nFinally, the paper points out several open directions that would be plausible for future work.", "questions": "- What is the main technical innovation of this work as compared to prior work?\n- I understand that this paper is focused on BSS in high-dimensional linear regression. What are the practical takeaways of the results beyond this setup? Could you discuss it in this context?", "limitations": "The authors discuss limitations of their work in Section 6.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "- The paper provides a meticulous study of private BSS, including a detailed comparison of the signal strength needed to achieve the desired rates.\n- The analysis involving rapid mixing of MCMC appears to be technically interesting, which could be a useful tool for future work.", "weaknesses": "- The simulation set up is somewhat restricted. Also, the main takeaways are not clear.\n\n- The identifiablity margin assumption is not clearly explained; the intuition as to while this should be expected is not clear.\n\n- In section 4, a comparison from the technical aspects is currently missing, and needs to be more clear to distinguish this work from prior works.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for handling our paper and providing constructive comments. Below we provide point-by-point responses to your concerns:\n\n**(P1)** We will add more plots for the auto-regressive design to improve the experiment section. Current experiments show similar results as presented in the current paper. This establishes robustness in the performance of our proposed method. The main takeaway of the experiments is that large $\\varepsilon$ generally improves the utility of our proposed method. However, the choice of $K$ also plays a key role in influencing the performance of the algorithm (discussed in Appendix A). Large $K$ usually entails that a large amount of noise is being injected into the algorithm, hence performance is generally poor for large $K$. Therefore, one needs to carefully choose $\\varepsilon, K$ to get the best results. Also, under good choices of $\\varepsilon$ and $K$, the plots do show that the chains mix very fast, which corroborates the results of Theorem 4.3.\n\n**(P2)** As discussed in Section 3.1, the margin $m_*(s)$ tries to capture both the degree of feature correlation and minimum signal strength simultaneously. If $m_*(s)$ is large, it essentially means that true features are easily distinguishable from the spurious features, and also the minimum signal strength is potentially very high. This is a general requirement for any method (including non-private methods) to achieve model consistency. Therefore, the condition Equation (9) is required to establish a model consistency result. The condition is not an assumption, but rather Theorem 3.5 says that if the condition holds then the exponential mechanism achieves model consistency. For example, under i.i.d. design, if the minimum signal strength is $\\tilde{\\Omega}(\\sqrt{\\log(p)/n})$ ($\\tilde{\\Omega}$ ignores some other terms) then Equation (9) is satisfied. See Remark 3.7 for a more detailed discussion. \n\n**(P3)** Thank you for your suggestion regarding adding comments on technical innovation. The main technical innovation in Section 4 of this paper is to design a **smart** MCMC chain that  **quickly** converges to the target distribution $\\pi$. Moreover, the proposed algorithm achieves the best of three worlds: privacy, utility, and computation, which was not seen in prior works. We will add relevant discussions on this in Section 4 of the revised manuscript.\n\n**(P4)** The proposed method provides us with a framework for solving similar optimization problems involving discrete variables. For example, our method can be adopted in model selection problems in the generalized linear model (GLM). In this case, the objective function will just change, and essentially the same procedure can be used to privately solve the BSS problem in GLM setup. In these cases, the discrete variable is the support set $\\hat{S}$. Therefore, our method can be used in a wide variety of other problems to obtain private solutions.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "GcS8MCUkER", "reviewer": "Reviewer_2aDP", "summary": "This papers study the differentially private best subset selection (BSS) of sparse linear model selection.", "questions": "1. As partially mentioned by the authors in the introduction, there are many existing more computationally-efficient sparse optimizations. So compared to privately select a subset of coordinates in the first place, one may also apply L_1-norm restriction or applying sparse vector techniques as alternative solutions.  I am wondering whether the authors could give a more comprehensive studies on those existing works with a more clear motivation on the advantage of BSS. \n\n2. Is it possible to remove the data-dependent assumption for bounded sensitivity (Assumption 3.2) but instead through clipping or truncation give an data-independent sensitivity bound? \n\n3. I think the MCMC of exponential sampling could be an independent and possibly more important contribution of this paper, which may provide an efficient version of exponential sampling methods. I am wondering whether there is any prior work on this topic and more rigorously how to determine the constant in Theorem 4.3 and Corollary 4.4.", "limitations": "Please see the above comments.", "rating": 4, "confidence": 2, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "+ It presents an O(s), where s is the sparsity parameter, improvement in the utility-privacy tradeoff. \n\n+ The MCMC implementation of exponential sampling seems a promising direction which may have some other independent applications. (I am not aware of the state-of-the-art results of exponential sampling and the MCMC study looks new to me and it seems that the authors claim it as a novel contribution of this paper).", "weaknesses": "- The comparisons with existing works are not comprehensive (see the comments below). \n\n- The assumptions on both the sensitivity and margin need a better justification. \n\n- The algorithm is based on computationally-intensive exponential sampling and it is not clear how practical the proposed MCMC improved version is. \n\n- Code is not released and variation of the experimental results are marked.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We thank you for your constructive comments. We will address all your concerns in the following points:\n\n**(P1)** ``***The assumptions on both the sensitivity and margin need a better justification***'' -- We did not make any assumption on the sensitivity. It is a consequence of Assumption 3.2. Please refer to point **(P3)** for a more detailed discussion.\n\n  We will add more discussion on the margin condition in the revised manuscript. The margin condition is rather necessary for BSS to achieve model consistency even in the non-private setting. Please refer to point **(P2)** in the response to reviewer QxEW for a more detailed discussion on this.\n\n**(P2)** ``***The algorithm is based on computationally intensive exponential sampling and it is not clear how practical the proposed MCMC improved version is.***''-- The exponential mechanism is a private algorithm and MCMC tries to mimic it in a computationally efficient way. Although the exponential mechanism has no advantage over the proposed MCMC, it is extremely important to understand its behavior to guarantee good performance of MCMC. The main proposed algorithm in the paper is the MCMC algorithm and to guarantee its good properties, a complete understanding of the exponential mechanism is required.\n\n**(P3)** ***Code is not released and variations of the experimental results are marked.*** - We did not release codes to maintain anonymity. We will definitely add a GitHub repository once the paper gets accepted.\n\n**(P4)** We would like to clarify that in this paper we specifically focus on subset selection rather than any generic sparse optimization.\n    You are right about the fact that we have mentioned a few prior existing subset selection algorithms that are computationally efficient. However, we have mentioned that they either demand very stringent $\\beta_{min}$ conditions or have inferior utility guarantee. In contrast, our method achieves the best of three worlds: privacy, utility, and computation. [1] considered private $L_1$-constrained problem (LASSO) for model selection (discussed in Section 1.1), however, their utility guarantee is far worse compared to our algorithm. However, it is not entirely clear how one can use the sparse vector technique to solve subset selection problems in a sparse regression setting. One straightforward way to apply sparse vector technique (SVT) could be to first estimate  $\\hat{\\beta}$ using some non-private technique and then use SVT to select the active features. \n    However, this would potentially demand far stricter assumptions on design to guarantee control on $\\Vert\\hat{\\beta} - \\beta\\Vert_\\infty$. We can add a few relevant discussions in the revised version.\n\n**(P5)** The assumption on $y$ can be easily removed by considering truncation at level $R$. In this case, $R$ will be a tuning parameter of the algorithm and one needs to choose $R$ intelligently to achieve good utility.\n\nOn the other hand, the boundedness assumption on $\\boldsymbol{x}$ is very mild as one can always scale the design matrix.\n\n**(P6)** Thank you for recognizing the importance of the proposed MCMC algorithm. There has not been any prior work on exponential mechanisms in the model selection context that also studies the computation cost of the method. Also, the constants in Theorem 4.3 and Corollary 4.4 can be pinned down exactly by keeping track of the constants in the tail inequalities in the relevant proofs. We did not keep track of those because in high-dimensional literature it is more important to understand the effect of $n,p,s$.\n\n\n[1] Abhradeep Guha Thakurta and Adam Smith. Differentially private feature\nselection via stability arguments, and the robustness of the lasso. In Shai\nShalev-Shwartz and Ingo Steinwart, editors, Proceedings of the 26th Annual\nConference on Learning Theory, volume 30 of Proceedings of Machine Learning\nResearch, pages 819–850, Princeton, NJ, USA, 12–14 Jun 2013. PMLR.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "xrbZj9Ttv0", "reviewer": "Reviewer_QHbD", "summary": "The paper addresses the model selection problem in sparse linear regression, proposing a differentially private version of the best subset selection algorithm using the exponential mechanism. The authors prove that the proposed private algorithm requires $O(\\sigma^2 s\\log p/n\\epsilon)$ samples to identify the correct features with high probability. Additionally, they demonstrate that when spurious features have low correlation with true features, sampling through MCMC converges rapidly to the stationary distribution.", "questions": "Does the universal constant $C_1$ in theorem 3.5 depend on the exponent of the failure probability?", "limitations": "See weaknesses.", "rating": 5, "confidence": 2, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "- The paper is clearly written, and the proposed private algorithm is simple. The proposed method only requires common assumptions found in privacy and sparse linear regression literature. Based on these assumptions, the authors provide theoretical guarantees on both privacy and utility.\n- The proposed private algorithm is of practical relevance as it can be implemented through MCMC. The authors also provide conditions under which MCMC achieves rapid convergence.", "weaknesses": "The rapid convergence of MCMC is achievable only when spurious features have low correlation with true features. However, practitioners typically do not know which features are true in advance, making it difficult to assess the strength of this correlation. Therefore, assumption 4.2 cannot be tested in practice.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "We greatly appreciate your encouraging words about our paper. Below we address your concerns point by point:\n\n**(P1)** We want to just briefly touch upon your comment regarding the weakness of the paper. You are absolutely right about the limitations of the correlation assumption (Assumption 4.2). Although the assumption needs the knowledge of the true support, similar assumptions are common in non-private high-dimensional model selection literature. For example, LASSO requires an irrepresentability condition which also controls the correlation between true and spurious features.\n\n**(P2)** To address your concern about $C_1$ and the exponent of failure probability, we would like to point you to Remark 3.6 of our paper. Essentially, to make the failure probability $O(p^{-M})$ for $M>2$, one needs to choose a larger constant $C_2 >C_1$.", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}, {"review_id": "85te3jVVgO", "reviewer": "Reviewer_piCf", "summary": "This paper addresses the challenge of model selection in high-dimensional sparse linear regression models under privacy constraints. It proposes a differentially private algorithm for best subset selection using the exponential mechanism, providing strong statistical utility guarantees under high-privacy regimes. The authors demonstrate that accurate model recovery is possible in low-privacy regimes, achieving minimax optimal conditions similar to non-private settings. To tackle computational complexity, the paper introduces a Metropolis-Hastings algorithm with polynomial mixing time under certain conditions, ensuring approximate differential privacy and good statistical utility. Experiments on simulated data illustrate the algorithm's effectiveness in identifying active features under reasonable privacy budgets.", "questions": "1. Theorem 3.5, Theorem 4.3, and Corollary 4.4 are high-probability statements. Is it possible to simplify them by including the high probability (success probability) $1 - c_i p^{-2}$ into the conclusion? For example, can the failure probability $1 - c_2 p^{-2}$ be included in the total variation distance to the stationary distribution in the mixing time?\n2. In the proof of the utility guarantee (Theorem 3.5), the authors cite the analysis of Guo et al. (2020) titled \"Best subset selection is robust against design dependence.\" Could the authors cite the specific theorems?\n3. What is the disadvantage of output perturbation to address the DP BSS problem compared to the exponential mechanism (the authors propose)? Can output perturbation achieve pure DP with a good utility guarantee?", "limitations": "Please check the questions above.", "rating": 5, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 3, "strengths": "1. The proposed Exponential mechanism for the DP BSS problem improves $\\beta_\\min$ condition.\n2. The proposed Metropolis-Hastings algorithm achieves approximate differential privacy with polynomial mixing time. The double swap update ensures that the proposed state maintains sparsity $s$.", "weaknesses": "1. The high-probability events in Theorem 3.5, Theorem 4.3, and Corollary 4.4 could be further clarified. See question 1.", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "Thank you very much for recognizing the novelty and significance of the work. Below, we address all your concerns:\n\n**(P1)** To address Question 1, we first point out that both $\\pi(\\cdot)$ and $\\pi_t(\\cdot)$ are data-dependent distributions, i.e., these distributions depend on the data, and hence there is inherent randomness (due to noise $\\boldsymbol{w}$) in them. Therefore, any statement on $\\pi$ or $\\pi_t$ can only be stated with a high success (or low failure) probability. One straightforward way to absorb the success/ failure probability in the conclusion is to consider the average performance. For example, Let $E:=\\{\\pi(\\gamma^*) \\ge 1- p^{-2}\\}$. Then we have \n   $\n    \\mathbb{E} [1-\\pi(\\gamma^*)] =\\mathbb{E} [\\{1 - \\pi(\\gamma^*)\\} 1_E ] +  \\mathbb{E}[ \\{1 - \\pi(\\gamma^*)\\} 1_{E^c}]= O (p^{-2}).\n$\n    Here we used the fact that $E^c$ has a small probability (Theorem 3.5).\n    This shows that $\\mathbb{E}\\{\\pi(\\gamma^*)\\} \\ge 1 - cp^{-2}$.\n    We can also present a similar argument to claim that $\\mathbb{E} \\{\\mathrm{TV}(\\pi_t, \\pi)\\} \\le \\eta + c_1 p^{-2}$ for large enough choices of $t$. However, we refrained from using these versions because the high-probability statements are easier to interpret.\n\n**(P2)** We would like to thank you for pointing out the lack of clarification in the proof of Theorem 3.5. We will add the particular theorem number of [1] in the revised version. Just to be clear, we were referring to Theorem 2.1 of [1].\n\n**(P3)** Recall that BSS outputs a model $\\hat{S} \\subseteq [p]$. One can also think of $\\hat{S}$ as a binary vector $\\hat{v}$ such that $\\hat{v}_j = \\mathbf{1}(j \\in \\hat{S})$. The main challenge lies here in the fact that $\\hat{v}$ is discrete and the perturbed $\\hat{v}$ should also remain in $\\{0,1\\}^p$. It seems very challenging to come up with a noise random variable $N$ that will ensure $\\hat{v} + N \\in \\{0,1\\}^p$ while maintaining $(\\varepsilon, 0)$-DP. Moreover, it is crucial to study the stability of $\\hat{S}$ for neighboring datasets to analyze the sensitivity $\\hat{v}$, and this is challenging in general. Even if we figure out the sensitivity, we can not just use Laplace or Gaussian noise because it will destroy the sparsity structure in $\\hat{v}$, and more importantly the perturbed vector will not be a binary vector anymore (i.e., loses its interpretability). \n\n  Another alternative way could be to just solve for $\\hat{\\beta}$ and then apply private top-k selection on $\\hat{\\beta}$. However, a good utility guarantee will require far worse assumptions like the minimal separation between the non-zero components of $\\hat{\\beta} = \\Omega(s)$ (See Theorem 2.3 of [2] and the discussion afterward). This is definitely not true when all the non-zero components of $\\hat{\\beta}$ are of the order $ O(\\sqrt{(\\log p)/n})$. However, our method still achieves model consistency in such cases.\n\n[1] Yongyi Guo, Ziwei Zhu, and Jianqing Fan. Best subset selection is robust\nagainst design dependence. arXiv preprint arXiv:2007.01478, 2020\n\n[2] Gang Qiao, Weijie Su, and Li Zhang. Oneshot differentially private top-k se-\nlection. In International Conference on Machine Learning, pages 8672–8681.\nPMLR, 2021", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "extra_scores": {}}]

Author rebuttal:

Meta-review: The paper addresses the model selection problem in sparse linear regression, proposing a differentially private version of the best subset selection algorithm using the exponential mechanism. The authors show that their algorithm has a better privacy-utility (in terms of minimum value of coefficients required for identifiability) tradeoff than existing approaches. Additionally, they demonstrate that a simple MCMC algorithm for the problem converges efficiently under an additional condition (intuitively saying that spurious features have low correlation with true features). The main issue with the work is the required condition cannot be verified (without knowledge of true features) and privacy guarantees of the algorithm depend on it (since they depend on convergence). In addition, the empirical evaluation does not compare with any baselines. Overall, I recommend acceptance with some reservations.
Decision: Accept (poster)