Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits

Abstract

We study exact support recovery under $(\epsilon,\delta)$-differential privacy in sparse high-dimensional linear regression. We introduce Saturated Propose-test-release, a general mechanism that privately releases the output of a discrete selector with probability one once its stability certificate reaches a finite threshold. Exploiting the coordinatewise geometry of the LASSO, we construct a computable support-stability score. The resulting computationally efficient Saturated LASSO satisfies worst-case $(\epsilon,\delta)$-differential privacy and achieves exact support recovery with high probability under explicit regularity and beta-min conditions. Maximizing sparsity-indexed certificates yields an adaptive procedure requiring no sparsity knowledge and having exactly the same finite-sample exact-recovery risk as the oracle fixed-sparsity procedure under common public tuning parameters. We also establish a minimax lower bound explicitly tracking $\delta$: under its recovery conditions, Saturated LASSO is minimax optimal up to logarithmic factors in $n$ and $1/\delta$ uniformly over $0<\delta \leq \epsilon/16$; in the broad moderate-$\delta$ regime, it further matches the lower-bound $\delta$-dependence. A complementary information-theoretic construction with known sparsity attains the lower-bound rates up to constant factors under independent Gaussian design, at exponential computational cost. Simulations and a semi-synthetic study using public American Community Survey covariates illustrate the numerical performance of the proposed procedures.