On the Computational Complexity of Private High-dimensional Model Selection
Lists
Only you see this
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{roy2024computational,
author = {Saptarshi Roy and Zehua Wang and Ambuj Tewari},
title = {{On the Computational Complexity of Private High-dimensional Model Selection}},
booktitle = {Advances in Neural Information Processing Systems},
year = {2024},
url = {https://openreview.net/forum?id=PzG7xVlYqm},
}