arXiv preprint ·
Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests
- Published
- Source
- arXiv preprint, posted before peer review
- Original
- Read it at arXiv
- Topics
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.
The authors’ abstract, as arXiv lists it. arXiv’s listings, abstracts included, are free for anyone to reuse.
Read it on ReadSearch
Each opens after you create an account, and brings you back to this paper.
More in Machine Learning
SPIBER: Reconstructing Free Energy Landscapes from Short, Unconverged Trajectories with Generative Flow Networks
CTRL: Control-Based Time Series Forecasting with LLM-Guided Residual Learning
Mask-Aware Execution for Efficient JEPA Training
Why Ghost Outputs Teach: A Kernel-Based Understanding of Subliminal Learning
StateMem: Single-State Residual Memory with Adaptive Inference for Vision-Language-Action Policies
Get the few papers worth your time in Machine Learning every morning.
ReadSearch reads the new papers in your field each day and brings you the few worth reading, each with its key finding in a sentence.