Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

Abstract: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.

Machine Learning (cs.LG)

arXiv:2609.22783 [cs.LG]

(or arXiv:2609.22783v1 [cs.LG] for this version)

https://doi.org/10.48550/arXiv.2609.22783 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.