On the Computational Complexity of Private High-dimensional Model Selection

Abstract: We consider the problem of model selection in a high-dimensional sparse linear regression model under privacy constraints. We propose a differentially private best subset selection method with strong utility properties by adopting the well-known exponential mechanism for selecting the best model. We propose an efficient Metropolis-Hastings algorithm and establish that it enjoys polynomial mixing time to its stationary distribution. Furthermore, we also establish approximate differential privacy for the estimates of the mixed Metropolis-Hastings chain. Finally, we perform some illustrative experiments that show the strong utility of our algorithm.

Speaker Bio: I am currently a Postdoc Research Fellow at the University of Texas, Austin with a joint appointment in the Department of Computer Science, Department of Statistics and Data Science, and the Institute for Foundations of Machine Learning. Prior to joining UT Austin, I completed my PhD in Statistics from the University of Michigan, Ann Arbor under the supervision of Prof. Ambuj Tewari. I completed my master's and bachelor's degree in Statistics from ISI, Kolkata. My research interest includes GenAI, high dimensional statistics, privacy, and online bandits.