On the Computational Complexity of Private High-dimensional Model Selection

Thank you very much for recognizing the novelty and significance of the work. Below, we address all your concerns:

(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 $\mathbb{E} [1-\pi(\gamma^*)] =\mathbb{E} [\{1 - \pi(\gamma^*)\} 1_E ] + \mathbb{E}[ \{1 - \pi(\gamma^*)\} 1_{E^c}]= O (p^{-2}).$ Here we used the fact that $E^c$ has a small probability (Theorem 3.5). This shows that $\mathbb{E}\{\pi(\gamma^*)\} \ge 1 - cp^{-2}$. 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.

(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].

(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).

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.

[1] Yongyi Guo, Ziwei Zhu, and Jianqing Fan. Best subset selection is robust against design dependence. arXiv preprint arXiv:2007.01478, 2020

[2] Gang Qiao, Weijie Su, and Li Zhang. Oneshot differentially private top-k se- lection. In International Conference on Machine Learning, pages 8672–8681. PMLR, 2021

We greatly appreciate your encouraging words about our paper. Below we address your concerns point by point:

(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.

(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$.

We thank you for your constructive comments. We will address all your concerns in the following points:

(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.

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.

(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.

(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.

(P4) We would like to clarify that in this paper we specifically focus on subset selection rather than any generic sparse optimization. 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. 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.

(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.

On the other hand, the boundedness assumption on $\boldsymbol{x}$ is very mild as one can always scale the design matrix.

(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$.

[1] 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 819–850, Princeton, NJ, USA, 12–14 Jun 2013. PMLR.

We thank you for handling our paper and providing constructive comments. Below we provide point-by-point responses to your concerns:

(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.

(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.

(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.

(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.