Research map / Federated learning and privacy / Differential privacy
On the Computational Complexity of Private High-dimensional Model Selection
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 a differentially private best subset selection method using the exponential mechanism, made computationally tractable via a Metropolis-Hastings sampler with double-swap moves, with utility and mixing-time guarantees in high-dimensional sparse linear regression.
Problem
Private model selection (best subset selection) in high-dimensional sparse linear regression is statistically useful under DP but computationally hard to solve exactly.
Approach
Use the exponential mechanism over size-s subsets, sample it with a Metropolis-Hastings chain using double-swap updates, and analyze the chain's mixing time; the rebuttal indicates the privacy proof was revised to use an l1-ball-constrained utility giving worst-case sensitivity.
Key results
- Theorem 3.4 gives (epsilon,0)-DP after revision via l1-ball constrained utility with worst-case sensitivity (r + R x_max)^2.
- Margin condition requires m_*(s) gtrsim (s/epsilon) log p / n in high-privacy regime and log p / n in low-privacy regime.
- Mixing time bound of the MCMC chain grows quadratically in s (Theorem 4.2).
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Increase ε (ablation) | Proposed MCMC · Simulation experiments | utility | Helped |
| Increase K (ablation) | Proposed MCMC · Simulation experiments | utility | Hurt |
| Decrease ε (ablation) | Proposed MCMC · Simulation experiments | performance | Hurt |
| Choose favorable ε and K (ablation) | Proposed MCMC · Simulation experiments | mixing time | Helped |
Surprising findings
- The original privacy proof relied on a high-probability sensitivity bound using the SRC assumption, which was invalid for worst-case DP; the authors corrected it in rebuttal.
Limitations
- Requires known sparsity level s as domain knowledge.
- Mixing-time analysis is worst-case and assumes bounded design and spurious-correlation conditions.
- Code not released during review.
Experimental setup
Metrics: model selection consistency mixing time
Builds on: exponential mechanism best subset selection
Closest papers by meaning
- Differentially Private High-dimensional Variable Selection via Integer Programming (NeurIPS 2025 · similarity 0.91)
- On Inherent Privacy of Posterior Sampling: A Unified R\'enyi-Divergence Framework (NeurIPS 2026 · similarity 0.88)
- Improved Analysis of Sparse Linear Regression in Local Differential Privacy Model (ICLR 2024 · similarity 0.88)
- Differentially Private Optimization with Sparse Gradients (NeurIPS 2024 · similarity 0.88)
- Public-data Assisted Private Stochastic Optimization: Power and Limitations (NeurIPS 2024 · similarity 0.87)
- Better Locally Private Sparse Estimation Given Multiple Samples Per User (ICML 2024 · similarity 0.87)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.