On the Computational Complexity of Private High-dimensional Model Selection

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.

Strengths

1. The proposed Exponential mechanism for the DP BSS problem improves $\beta_\min$ condition. 2. 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.

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? 2. 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? 3. 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?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

Please check the questions above.

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.

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

Questions

Does the universal constant $C_1$ in theorem 3.5 depend on the exponent of the failure probability?

Rating

5

Confidence

2

Soundness

3

Presentation

3

Contribution

2

Limitations

See weaknesses.

Summary

This papers study the differentially private best subset selection (BSS) of sparse linear model selection.

Strengths

+ It presents an O(s), where s is the sparsity parameter, improvement in the utility-privacy tradeoff. + 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). - The assumptions on both the sensitivity and margin need a better justification. - The algorithm is based on computationally-intensive exponential sampling and it is not clear how practical the proposed MCMC improved version is. - Code is not released and variation of the experimental results are marked.

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. 2. 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? 3. 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.

Rating

4

Confidence

2

Soundness

2

Presentation

2

Contribution

2

Limitations

Please see the above comments.

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: - 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. - Second, devise an efficient MCMC sampling algorithm that still enjoys approximate DP, while having a polynomial mixing time. - Numerical experiments focus on a synthetic example, with a random design matrix, as well as a US census study and another socio-economic study. Finally, the paper points out several open directions that would be plausible for future work.

Strengths

- The paper provides a meticulous study of private BSS, including a detailed comparison of the signal strength needed to achieve the desired rates. - 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. - The identifiablity margin assumption is not clearly explained; the intuition as to while this should be expected is not clear. - 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.

Questions

- What is the main technical innovation of this work as compared to prior work? - 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?

Rating

5

Confidence

3

Soundness

3

Presentation

3

Contribution

3

Limitations

The authors discuss limitations of their work in Section 6.