Research map / Federated learning and privacy / Differential privacy

Differentially Private High-dimensional Variable Selection via Integer Programming

NeurIPS 2025 · Federated learning and privacy › Differential privacy · approach: Private data analysis frameworks · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes two pure-DP variable selection estimators (top-R and mistakes) that modify the exponential mechanism to sample from a small set of MIP-computed candidate supports, giving support recovery guarantees for best subset selection and scaling to p=10^4.

Problem

Differentially private sparse variable selection (best subset selection) is hard because the exponential mechanism requires enumerating all (p choose s) supports, limiting scalability.

Approach

Truncate the exponential mechanism: only the top-R (or s+1 mistake-partition representatives) supports are computed via mixed integer programming and the remaining mass is handled by uniform sampling or a lower-bound substitution, preserving pure DP while avoiding full enumeration.

Key results

• Top-R and mistakes methods outperform MCMC and Samp-Agg in support recovery for large enough n in simulations with p=10,000, s=5, SNR=5, rho=0.1, epsilon=1.
• Top-R requires beta_min of order sqrt(max{1,s^2/eps} log p / n); mistakes method requires milder sqrt(max{1,1/eps} s log p / n) under a separation assumption.
• Mistakes method numerically outperforms top-R in the experiments, consistent with its weaker identifiability condition.

Measured effects reported in the paper

Surprising findings

• The privacy loss of the top-R method increases with R, so larger R improves accuracy but weakens privacy at fixed epsilon.

Limitations

• Mistakes method privacy holds only under an additional separation assumption that holds with high probability.
• Support recovery theory is only for best subset selection; general loss results lack statistical guarantees.
• Necessary conditions for support recovery are not established.

Experimental setup

Datasets: synthetic Gaussian design with AR(1) covariance

Benchmarks: synthetic sparse regression simulations (p=10,000)

Metrics: proportion of correct support recovery

Baselines: MCMC approximate DP BSS Samp-Agg with Lasso

Builds on: exponential mechanism best subset selection outer approximation MCMC-based DP variable selection resample-and-aggregate

Closest papers by meaning

• On the Computational Complexity of Private High-dimensional Model Selection (NeurIPS 2024 · similarity 0.91)
• Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.89)
• Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.89)
• Adapting to Linear Separable Subsets with Large-Margin in Differentially Private Learning (ICML 2025 · similarity 0.88)
• Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.87)
• Private Gradient Descent for Linear Regression: Tighter Error Bounds and Instance-Specific Uncertainty Estimation (ICML 2024 · similarity 0.87)