Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests
En palabras de los autores
We study differentially private covariance estimation in operator norm for mean-zero sub-Gaussian distributions with unknown covariance support and at most nonzero entries per row. We develop a multiscale random-threshold algorithm with sample complexity for -differential privacy and error at most , where is the dimension and is a known sub-Gaussian scale. The bound improves the privacy-dependent term of the existing \citep{kumar2026curse} upper bound by a factor of , and matches the lower bound of 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 factor from the privacy-dependent sample complexity.
Apareció: martes, 22 de septiembre. arXiv. Preprint, todavía sin revisión por pares.