Differentially Private High-dimensional Variable Selection via Integer Programming

Dear reviewer PKV9,

We sincerely appreciate your feedback on our paper. We would like to address your concerns below.

Effect of sample size on Top-R performance

Thank you for your comment! The performance improves with increasing $n$ due to the decrease in the threshold needed for the identifiability margin $\tau$ to have enough separation between the true support and other supports (Theorem 3 in our paper). We will make sure to update this in our manuscript.

Empirical performance with larger s

In order to evaluate the performance of our methods for larger values of $s$, we ran experiments with $p=100, s=20, \epsilon = 1, SNR= 5,$ and $\rho = 0.1$. For each value of $n$, we ran 10 independent trials, where, for each trial, we drew 100 times from the distribution corresponding to each algorithm, and for MCMC, we used 100 independent Markov chains for each trial. Our choice of $\lambda=80,000$ and MCMC iterations = 1000 resulted in our mistakes method having a considerably smaller average runtime than the MCMC method.

We present our results below. As expected, we observed that for $n$ large enough, our mistakes method outperformed both the Samp-Agg and MCMC methods.

Average # correct supports / number of trials:

Average F1 scores:

MIP extension to general loss functions

A key benefit of our MIP approach is its generalizability across different loss functions. Specifically, the only property that we need to have for the loss function $\rho$ is that it is a convex function of $\beta$. As long as the loss function is convex, our outer approximation approach can be applied to any general loss function. For example, our method works with Huber or quantile loss as well, and the MIP algorithm would remain unchanged.

Support recovery results are limited to the sparse regression setting

We acknowledge that our theoretical support recovery guarantees are currently limited to the sparse regression setting. However, extending these results rigorously to more general loss functions would necessitate a fundamentally different analytical framework and set of assumptions than that used in the least squares setting [1]. Such an extension would be substantial enough to warrant dedicated treatment in future work. Additionally, we emphasize that, to our knowledge, the existing theoretical literature on differentially private sparse variable selection explicitly focuses on linear regression. Therefore, restricting our theoretical support recovery analysis to the sparse regression context aligns naturally with the current state of research and represents a meaningful contribution within this established framework.

Comment regarding notational conflict

Thank you for noticing our notational conflict with the use of $\rho$. We will make sure to adjust this in our manuscript.

References:

[1] Chen, L. Y., & Lee, S. (2023). Sparse quantile regression. Journal of Econometrics, 235(2), 2195–2217.

Dear reviewer vS6c,

We would like to sincerely thank you for your positive feedback on our paper. We would like to address your concerns below.

Theoretical guarantees for support recovery

We would like to clarify that our two methods match the best theoretical guarantees in the literature in complementary privacy regimes, as discussed in the contributions section of our paper and in section 3. Namely, our top-R method matches with the non-private minimax-optimal signal threshold for support recovery in the low privacy regime, and our mistakes method matches the required signal threshold in [1] in the high-privacy regime.

Privacy of mistakes method

We would like to note that while the privacy of our mistakes method relies on an additional assumption that occurs with high probability (as shown in section A.5 in the appendix), providing a privacy guarantee with additional assumptions is not uncommon in the literature. For example, the privacy guarantees of [1], which is the closest competitor to our method, depends on assumptions that hold with high probability. More specifically, the privacy proof of the Markov Chain Monte Carlo (MCMC) algorithm in [1] relies on the assumption that the mixing of the Markov Chain used for sampling with its stationary distribution has happened. However, this mixing can only be guaranteed with high probability, and under additional assumptions on the underlying model—see Theorem 4.3 of [1] for more details. In contrast, our top-R method is always private (assuming $b_x,b_y$ are finite), and our mistakes method is private under assumptions that are similar to the ones in Theorem 4.3 of [1].

As another example, [2] uses the stability of Lasso, to present a DP method for support recovery in sparse linear regression. However, the stability of Lasso only holds under certain assumptions on the data, such as the boundedness of the noise and restricted strong convexity. Such assumptions might only hold with high probability in practice, resulting in privacy guarantees that hold with high probability. For more details, we refer to Theorem 8 of [2].

Presentation and typos

Thank you very much for correcting our typo in regards to the privacy of our top-R method. As you correctly point out, top-R is $(\epsilon’,0)$-DP unless $T=\infty$. Thank you also for noting how our paper presentation could be improved. We will make sure to edit the formulas in the appendix to fit within the page margins, grow the font sizes in the plots, and expand our conclusion section further.

Similar modifications of the exponential mechanism

In regards to your last question, there are no similar modifications to the exponential mechanism in the literature to our knowledge.

References:

[1] Roy, S., Wang, Z., & Tewari, A. (2024). On the computational complexity of private high-dimensional model selection via the exponential mechanism. In Advances in Neural Information Processing Systems (NeurIPS).

[2] Thakurta, A. G., & Smith, A. (2013). Differentially private feature selection via stability arguments, and the robustness of the lasso. In Proceedings of the Conference on Learning Theory (COLT), PMLR.

Dear reviewer JE2d,

We sincerely appreciate your effort in providing detailed feedback on our paper. We address your comments below.

Privacy of mistakes method

We would like to note that while the privacy of our mistakes method relies on an additional assumption that occurs with high probability (as shown in section A.5 in the appendix), providing a privacy guarantee with additional assumptions is not uncommon in the literature. For example, the privacy guarantees of [1], which is the closest competitor to our method, depends on assumptions that hold with high probability. More specifically, the privacy proof of the Markov Chain Monte Carlo (MCMC) algorithm in [1] relies on the assumption that the mixing of the Markov Chain used for sampling with its stationary distribution has happened. However, this mixing can only be guaranteed with high probability, and under additional assumptions on the underlying model—see Theorem 4.3 of [1] for more details. In contrast, our top-R method is always private (assuming $b_x,b_y$ are finite), and our mistakes method is private under assumptions that are similar to the ones in Theorem 4.3 of [1].

As another example, [2] uses the stability of Lasso, to present a DP method for support recovery in sparse linear regression. However, the stability of Lasso only holds under certain assumptions on the data, such as the boundedness of the noise and restricted strong convexity. Such assumptions might only hold with high probability in practice, resulting in privacy guarantees that hold with high probability. For more details, we refer to Theorem 8 of [2].

Comparison with Samp-Agg

We would first like to clarify that in our experiments, we do not compare with Algorithm 3 in [3], which allocates half the privacy budget on feature selection and half on model optimization, but rather, we are comparing with Algorithm 5 which exclusively is aimed at feature selection for the same problem and is itself (ε,0)-DP.

Nevertheless, as you suggested, in an effort to compare prediction accuracy across methods, we did a 70/30 random train test/split and implemented Algorithm 2 in [3] on the train data, wherein we use half the privacy budget (i.e., $\epsilon/2$) for variable selection using the top-R, mistakes, Samp-Agg, or MCMC methods, and the remaining half of the budget for model optimization using objective perturbation (Algorithm 1 in [3]) to obtain the regression coefficients under the privacy budget ($\beta_\text{priv}$). We ran experiments with $p=100, s=5, \epsilon = 2, SNR= 5, \rho = 0.1$, and ran 10 independent trials for each value of $n$, where, for each trial, we drew 50 times from the distribution corresponding to each algorithm, and for MCMC, we used 50 independent Markov chains for each trial. After running objective perturbation over the supports, we thus had 500 distinct coefficient vectors for each method and for each $n$, and we computed the average MSE on the test data for every method. Our choices of $\lambda=120$ and MCMC iterations = 1000 were chosen to make the runtimes comparable, as done in our paper. We summarize our results below, showing that our top-R and mistakes methods outperform the competitor algorithms in terms of prediction accuracy for $n$ large enough.

Average test MSE:

Furthermore, we ran experiments to evaluate the utility loss, or gap between the objective at $\beta_\text{priv}$ and the objective at $\hat{\beta}$ (the optimal BSS solution), with the same parameters as in the experiments above and we present our results below. As with the prediction accuracy, our top-R and mistakes methods outperform the competitor algorithms in terms of utility loss for $n$ large enough.

Average utility loss:

References:

[1] Roy, S., Wang, Z., & Tewari, A. (2024). On the computational complexity of private high-dimensional model selection via the exponential mechanism. In Advances in Neural Information Processing Systems (NeurIPS).

[2] Thakurta, A. G., & Smith, A. (2013). Differentially private feature selection via stability arguments, and the robustness of the lasso. In Proceedings of the Conference on Learning Theory (COLT), PMLR.

[3] Kifer, D., Smith, A., & Thakurta, A. (2012). Private convex empirical risk minimization and high-dimensional regression. In Proceedings of the Conference on Learning Theory (COLT), JMLR Workshop and Conference Proceedings.

Thanks for your response. Overall I feel more positive about the paper after reading the authors' response and will raise my score accordingly.

Re: Privacy of mistakes method - I think [2] is a bit outdated, but I appreciate that [1] is the paper the authors are directly comparing against, and to that end one can reframe this point as "the unconditional privacy of top-K is an improvement over past work" rather than "the conditional privacy of mistakes is a limitation". I'm willing to concede that this alone should not give a negative rating to the paper.

Re: The new experiments. Thanks for adding these and for the clarification. I think these results address my concerns, they are much more compelling and a great addition to the paper.

Dear reviewer fXeC,

We sincerely thank you for your constructive feedback on our paper. We address your concerns below:

Practicality of assumptions

Assumption 1 regarding the boundedness of the dataset is a common assumption in the high-dimensional statistics and DP literature (we refer to [1,2] and references therein). We also make a note in the paper that, while in practice one may not know the exact values of $b_x,b_y$, or such values might not exist, one can clip the values of $X,y$ to satisfy the assumption. Importantly, the only assumption required to ensure the privacy of the top-R method is Assumption 1, which can always be satisfied using clipping as discussed.

Similarly, assumptions 2-4 regarding the boundedness of the true parameter vector, the Sparse Riesz Condition (SRC), and the growth of the sparsity parameter, are standard assumptions often found in the sparse linear regression literature, and we offer numerous citations in section 3 of the paper.

Experiments on prediction accuracy

In an effort to compare prediction accuracy across methods, we did a 70/30 random train test/split and implemented Algorithm 2 in [3] on the train data, wherein we use half the privacy budget (i.e., $\epsilon/2$) for variable selection using the top-R, mistakes, Samp-Agg, or MCMC methods, and the remaining half of the budget for model optimization using objective perturbation (Algorithm 1 in [3]) to obtain the regression coefficients under the privacy budget. We ran experiments with $p=100, s=5, \epsilon = 2, SNR= 5, \rho = 0.1$, and ran 10 independent trials for each value of $n$, where, for each trial, we drew 50 times from the distribution corresponding to each algorithm, and for MCMC, we used 50 independent Markov chains for each trial. After running objective perturbation over the supports, we thus had 500 distinct coefficient vectors for each method and for each $n$, and we computed the average MSE on the test data for every method. Our choices of $\lambda=120$ and MCMC iterations = 1000 were chosen to make the runtimes comparable, as done in our paper. We summarize our results below, showing that our top-R and mistakes methods outperform the competitor algorithms in terms of prediction accuracy for $n$ large enough.

Average Test MSE:

Ablation study to choose hyperparameters

For more details on how the choice of R was selected for our experiments, we provide additional information in section B of the appendix. In summary, choosing a larger value of R improves the support recovery quality, but increases the computational cost of the method. Our choice of $R=2+(p-s)s$ is designed to encompass the optimal solution, the solutions with the support differing from the optimal by one, and at least a solution with two differences in the support relative to the optimal. This choice seems to result in reasonable runtime, while leading to good model selection accuracy.

In addition, we have performed an ablation study to show the effect of changing $R, \lambda$, and $(b_x, b_y)$ on the fraction of correct supports as well as F1 score, fixing $n=3500, p=100, s=5, \epsilon = 1, SNR= 5$, and $\rho = 0.1$. We ran 10 independent trials and drew 100 times from the distribution corresponding to our algorithms.

• Ablation study of $R$: We present our results below for $R$. Note we used $\lambda=120$ and $(b_x, b_y) = (0.5,0.5)$. As intuitively expected and shown formally in section A.3 in the appendix, increasing $R$ has a positive effect on support recovery.

• Ablation study of $\lambda$: We present our results below for tuning $\lambda$. Note we used $R=2+(p-s)s$ and $(b_x, b_y) = (0.5,0.5)$. We observe that choosing a very large $\lambda$ can have a negative effect on support recovery. However, increasing $\lambda$ is beneficial to the runtime of our outer approximation solver. Therefore, we choose a moderate value for $\lambda$ to ensure the runtime of our method remains comparable to MCMC.

Average F1 scores:

Average # correct supports / number of trials:

• Ablation study of $(b_x,b_y)$: For simplicity, we set $b_x = b_y$. Note we used $R=2+(p-s)s$ and $\lambda = 300$. We present the results below. Our results imply that choosing the clipping constants to be too small or large can have a negative effect on the support recovery quality. In practice, one can tune these hyper parameters via cross-validation.

Average F1 scores:

Average # correct supports / number of trials:

References:

[1] Roy, S., Wang, Z., & Tewari, A. (2024). On the computational complexity of private high-dimensional model selection via the exponential mechanism. In Advances in Neural Information Processing Systems (NeurIPS).

[2] Chen, L. Y., & Lee, S. (2023). Sparse quantile regression. Journal of Econometrics, 235(2), 2195–2217.

[3] Kifer, D., Smith, A., & Thakurta, A. (2012). Private convex empirical risk minimization and high-dimensional regression. In Proceedings of the Conference on Learning Theory (COLT), JMLR Workshop and Conference Proceedings.

We apologize for a typo in the last table, the columns represent the different values of $(b_x,b_y)$ that were tested, not $\lambda$ values. The correct table is shown below.

Average # correct supports / number of trials: