SOURCE-LINKED INTELLIGENCE

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

arXiv · AI, language, vision and robotics · article · Sep 19, 2026 · UTC

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/α^2+k\sqrt d/(α\varepsilon))$ for $(\varepsilon,δ)$-differential privacy and error at most $ασ^2$, where $d$ is the dimension and $σ$ is a known sub-Gaussian scale. The bound improves the privacy-dependent term of the existing $\ot(k^2/α^2+k^{3/2}\sqrt d/(α\varepsilon))$ \citep{kumar2026curse} upper bound by a factor of $\sqrt k$,

Read original source ↗ Open in workspace

recordType

paper

region

Global