On the Computational Complexity of Private High-dimensional Model Selection
Saptarshi Roy, Zehua Wang, Ambuj Tewari
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.
BibTeX
@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}
}