# On the Computational Complexity of Private High-dimensional Model Selection

arXiv: https://arxiv.org/abs/2310.07852 · HTML: https://mlsanity.com/paper/2310.07852/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 26 of its 92 references that are in the map.
- First posted on arXiv 11 Oct 2023.

## Builds on (most cited first, 26 of 26)

- [CVXPY: A Python-Embedded Modeling Language for Convex Optimization](https://mlsanity.com/paper/1603.00943/) (2016)
- [A Rewriting System for Convex Optimization Problems](https://mlsanity.com/paper/1709.04494/) (2017)
- [Differentially Private Empirical Risk Minimization Revisited: Faster and More General](https://mlsanity.com/paper/1802.05251/) (2018)
- [Best Subset Selection via a Modern Optimization Lens](https://mlsanity.com/paper/1507.03133/) (2015)
- [Private PAC learning implies finite Littlestone dimension](https://mlsanity.com/paper/1806.00949/) (2018)
- [Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain](https://mlsanity.com/paper/1803.02596/) (2018)
- [Sparse Regression at Scale: Branch-and-Bound rooted in First-Order Optimization](https://mlsanity.com/paper/2004.06152/) (2020)
- [Sparse High-Dimensional Regression: Exact Scalable Algorithms and Phase Transitions](https://mlsanity.com/paper/1709.10029/) (2017)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Tight Lower Bounds for Differentially Private Selection](https://mlsanity.com/paper/1704.03024/) (2017)
- [Understanding the Sparse Vector Technique for Differential Privacy](https://mlsanity.com/paper/1603.01699/) (2016)
- [Differentially Private Chi-Squared Hypothesis Testing: Goodness of Fit and Independence Testing](https://mlsanity.com/paper/1602.03090/) (2016)
- [Score Attack: A Lower Bound Technique for Optimal Differentially Private Learning](https://mlsanity.com/paper/2303.07152/) (2023)
- [On the Computational Complexity of High-Dimensional Bayesian Variable Selection](https://mlsanity.com/paper/1505.07925/) (2015)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [abess: A Fast Best Subset Selection Library in Python and R](https://mlsanity.com/paper/2110.09697/) (2021)
- [Differentially Private Histograms under Continual Observation: Streaming Selection into the Unknown](https://mlsanity.com/paper/2103.16787/) (2021)
- [Locally Private Hypothesis Testing](https://mlsanity.com/paper/1802.03441/) (2018)
- [Local Private Hypothesis Testing: Chi-Square Tests](https://mlsanity.com/paper/1709.07155/) (2017)
- [Differentially Private Algorithms for Empirical Machine Learning](https://mlsanity.com/paper/1411.5428/) (2014)
- [Differentially Private Model Selection with Penalized and Constrained Likelihood](https://mlsanity.com/paper/1607.04204/) (2016)
- [Best subset selection is robust against design dependence](https://mlsanity.com/paper/2007.01478/) (2020)
- [Private False Discovery Rate Control](https://mlsanity.com/paper/1511.03803/) (2015)
- [High dimensional thresholded regression and shrinkage effect](https://mlsanity.com/paper/1605.03306/) (2016)
- [A Members First Approach to Enabling LinkedIn's Labor Market Insights at Scale](https://mlsanity.com/paper/2010.13981/) (2020)
- [Majority Vote for Distributed Differentially Private Sign Selection](https://mlsanity.com/paper/2209.04419/) (2022)

## Built on by (most cited first, 1 of 1)

- [Differentially Private High-dimensional Variable Selection via Integer Programming](https://mlsanity.com/paper/2510.22062/) (2025)

## Abstract (arXiv)

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.