Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

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 $\text{ot}(k^2/{\alpha }^2+k\sqrt{d}/(\alpha \epsilon ))$ for $(\epsilon ,\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 $\text{ot}(k^2/{\alpha }^2+k^{3/2}\sqrt{d}/(\alpha \epsilon ))$ kumar2026curse upper bound by a factor of $\sqrt{k}$, and matches the lower bound of $\tilde{\Omega }(k^2/{\alpha }^2+k\sqrt{d}/(\alpha \epsilon ))$ 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. Combined with a multiscale test allocation that balances reconstruction variance against query sensitivity, this bound removes the additional $\sqrt{k}$ factor from the privacy-dependent sample complexity.