Metraipolis › archive › dc_cc15586d58ff
Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests — arXiv:2609.22783
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.22783
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T07:06:48.233Z
- SHA-256 of the archived text
ca2ef87c6e2774cb87049846757f5f1a865ba5f27f96e5c635297dd847bc4dac- Stable URL of this page
https://metraipolis.com/documento/dc_cc15586d58ff
How to cite
Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests — arXiv:2609.22783 — arXiv (en), https://arxiv.org/abs/2609.22783 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_cc15586d58ff (Metraipolis archive dc_cc15586d58ff, sha256 ca2ef87c6e2774cb87049846757f5f1a865ba5f27f96e5c635297dd847bc4dac)
BibTeX
@misc{dccc15586d58ff,
title = {Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests — arXiv:2609.22783},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.22783},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_cc15586d58ff; sha256 ca2ef87c6e2774cb87049846757f5f1a865ba5f27f96e5c635297dd847bc4dac},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.22783. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
We study differentially private covariance estimation in operator norm for mean-zero sub-Gaussian distributions with unknown covariance support and at most $k$ nonzero entries per row. We develop a multiscale random-threshold algorithm with sample complexity $\ot(k^2/\alpha^2+k\sqrt d/(\alpha\varepsilon))$ for $(\varepsilon,\delta)$-differential privacy and error at most $\alpha\sigma^2$, where $d$ is the dimension and $\sigma$ is a known sub-Gaussian scale. The bound improves the privacy-dependent term of the existing $\ot(k^2/\alpha^2+k^{3/2}\sqrt d/(\alpha\varepsilon))$ \citep{kumar2026curse} upper bound by a factor of $\sqrt k$, and matches the lower bound of $\widetilde{\Omega}(k^2/\alpha^2 + k\sqrt{d}/(\alpha\varepsilon))$ in its applicable parameter regime. Our key technical ingredient is a direct operator-norm bound on the centered fluctuations of an ideal reconstruction, exploiting conditional independence rather than accumulating entrywise errors across each row. A multiscale allocation of threshold tests balances reconstruction variance against query sensitivity. Together, these ingredients sharpen the trade-off between approximation error and privacy protection, removing the additional $\sqrt{k}$ factor from the privacy-dependent sample complexity.
Tema degli esploratori: agenti e intelligenza artificiale (retro-catalogo arXiv: annunci del 2026-09-22 in cs.LG).
Categorie arXiv: Machine Learning (cs.LG).
Pagina del lavoro: https://arxiv.org/abs/2609.22783 — 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-09T06:58:09.218Z dalla pagina https://arxiv.org/catchup/cs.LG/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).