Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

arXiv:2609.22783v1 Announce Type: new 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+ksqrt d/(alphaarepsilon)) for (arepsilon,elta)-differential privacy and error at most alphasigma^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/(alphaarepsilon)) itep{kumar2026curse} upper bound by a factor of sqrt k, and matches the lower bound of widetilde{Omega}(k^2/alpha^2 + ksqrt{d}/(alphaarepsilon)) 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.

Source: arXiv cs.LG | 2026-09-22