On the Computational Complexity of Private High-dimensional Model Selection

2023/10/11 by Saptarshi Roy, Roy, Saptarshi, Wang, Zehua +1 · 1 citation
Computer Science · #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.2310.07852

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.

Cited by

• Differentially Private High-dimensional Variable Selection via Integer Programming

Related

• Differentially Private High-dimensional Variable Selection via Integer Programming
• Private Selection from Private Candidates
• Easy Differentially Private Linear Regression
• SoK: A Review of Differentially Private Linear Models For High-Dimensional Data
• High-Dimensional Differentially-Private EM Algorithm: Methods and Near-Optimal Statistical Guarantees