@inproceedings{
roy2024on,
title={On the Computational Complexity of Private High-dimensional Model Selection},
author={Saptarshi Roy and Zehua Wang and Ambuj Tewari},
booktitle={The Thirty-eighth Annual Conference on Neural Information Processing Systems},
year={2024},
url={https://openreview.net/forum?id=PzG7xVlYqm}
}
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