Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits
Abstract
We study exact support recovery under (ε,δ)-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 (ε,δ)-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 δ: under its recovery conditions, Saturated LASSO is minimax optimal up to logarithmic factors in n and 1/δ uniformly over 0 < δ≤ ε/16; in the broad moderate-δ regime, it further matches the lower-bound δ-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.
Related
- Adaptive Confidence Sets for Nonparametric Density Estimation under Local Differential Privacy
- From Privacy to Generalization: Linear Max-Information Bounds for Differentially Private Learning Algorithms
- Efficient Agnostic Learning of Univariate Densities Under Local Differential Privacy
- Faster Learning under Relaxed Local Differential Privacy
- Projection-Based Federated Learning on Compact Submanifolds with Geometry-Independent Differential Privacy
BibTeX
@misc{gu2026learning,
title = {{Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits}},
author = {Jia Gu and T. Tony Cai},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.05867},
eprint = {2610.05867},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.05867},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits
AU - Jia Gu
AU - T. Tony Cai
PY - 2026
DA - 2026/10/05
PB - arXiv
DO - 10.48550/arxiv.2610.05867
UR - https://arxiv.org/abs/2610.05867
AB - We study exact support recovery under (ε,δ)-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 (ε,δ)-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 δ: under its recovery conditions, Saturated LASSO is minimax optimal up to logarithmic factors in n and 1/δ uniformly over 0 < δ≤ ε/16; in the broad moderate-δ regime, it further matches the lower-bound δ-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.
ER -