Improved method for private sparse covariance estimation in high dimensions
Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests
Machine Learning
Summary
Understanding relationships between many variables often involves calculating a covariance matrix. Doing this while protecting individual data privacy is tricky, especially when the matrix is large and mostly filled with zeros. The authors developed a new algorithm that better balances accuracy and privacy by using a smart way of setting thresholds and analyzing data patterns. This method needs fewer data samples than previous techniques and matches the known theoretical limits, making it more efficient and private.
What this means in practice
- •For data privacy engineers: Build privacy-preserving analytics tools that estimate relationships between variables in high-dimensional sparse data more efficiently with less data.
- •For machine learning developers: Develop models that require covariance estimates under differential privacy guarantees, improving model reliability on sensitive high-dimensional data.
Authors
Zihan Zhang
Abstract
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$, and matches the lower bound of $\widetildeΩ(k^2/α^2 + k\sqrt{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 $\sqrt{k}$ factor from the privacy-dependent sample complexity.