# Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

arXiv: https://arxiv.org/abs/2609.22783 · HTML: https://mlsanity.com/paper/2609.22783/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 9 of its 16 references that are in the map.
- First posted on arXiv 19 Sep 2026.

## Builds on (most cited first, 9 of 9)

- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Practical Differentially Private Top-k Selection with Pay-what-you-get Composition](https://mlsanity.com/paper/1905.04273/) (2019)
- [Fast, Sample-Efficient, Affine-Invariant Private Mean and Covariance Estimation for Subgaussian Distributions](https://mlsanity.com/paper/2301.12250/) (2023)
- [Better and Simpler Lower Bounds for Differentially Private Statistical Estimation](https://mlsanity.com/paper/2310.06289/) (2023)
- [Oneshot Differentially Private Top-k Selection](https://mlsanity.com/paper/2105.08233/) (2021)
- [Differentially Private Covariance Revisited](https://mlsanity.com/paper/2205.14324/) (2022)
- [Differentially Private High Dimensional Sparse Covariance Matrix Estimation](https://mlsanity.com/paper/1901.06413/) (2019)
- [On Purely Private Covariance Estimation](https://mlsanity.com/paper/2510.26717/) (2025)
- [On the Curse of Dimensionality in Private Sparse Covariance Estimation and PCA](https://mlsanity.com/paper/2606.21951/) (2026)

## Abstract (arXiv)

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(k2/α2+k√ 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(k2/α2+k3/2√ d/(αvarepsilon)) citepkumar2026curse upper bound by a factor of √ k, and matches the lower bound of widetildeOmega(k2/α2 + k√d/(α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 √k factor from the privacy-dependent sample complexity.