Metraipolis › archive › dc_f8ca15c4dc35

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

Source
arXiv (en)
Original
https://arxiv.org/abs/2610.05867
License (as archived)
CC0-1.0
Archived
2026-10-06T13:40:01.399Z
SHA-256 of the archived text
05a350f457ae4fe6c6c7dcd46bd94c89dbd7981018a70ef31773535d6187d959
Stable URL of this page
https://metraipolis.com/documento/dc_f8ca15c4dc35

How to cite

Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits — arXiv:2610.05867 — arXiv (en), https://arxiv.org/abs/2610.05867 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_f8ca15c4dc35 (Metraipolis archive dc_f8ca15c4dc35, sha256 05a350f457ae4fe6c6c7dcd46bd94c89dbd7981018a70ef31773535d6187d959)
BibTeX
@misc{dcf8ca15c4dc35,
  title = {Learning Sparse Support under Differential Privacy: Adaptive Algorithms and Minimax Limits — arXiv:2610.05867},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.05867},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_f8ca15c4dc35; sha256 05a350f457ae4fe6c6c7dcd46bd94c89dbd7981018a70ef31773535d6187d959},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.05867. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.ST, nuovi lavori del giorno).
Categorie arXiv: Statistics Theory (math.ST).
Pagina del lavoro: https://arxiv.org/abs/2610.05867 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-06T11:56:32.034Z dalla pagina https://arxiv.org/list/math.ST/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).