Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

Zihan Zhang

In the authors' words

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 d / (α ε))$ for $(ε, δ)$ -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} d / (α ε))$ \citep{kumar2026curse} upper bound by a factor of $k$ , and matches the lower bound of $Ω (k^{2} / α^{2} + k d / (α ε))$ 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.

Main resultLimitation the authors admit

Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests

In the authors' words

More on Learning theory & optimization that day

Toward a Unified Mathematics of Concepts

Displacement Geometry Captures Platonic Shared Reality Across Models and Modalities

Adversarially Robust PAC Learning with Optimal VC Rates

Conformal Robustness in Prediction-Driven Decision-Making

Whitening Inverts the Hierarchy: What the Norm of a Whitened Embedding Measures