On Purely Private Covariance Estimation

Abstract

We present a simple perturbation mechanism for the release of $d$-dimensional covariance matrices $\hat{I}\pounds$ under pure differential privacy. For large datasets with at least $n\ge d^2/\epsilon$ elements, our mechanism recovers the provably optimal Frobenius norm error guarantees of \cite{nikolov2023private}, while simultaneously achieving best known error for all other $p$-Schatten norms, with $p\in [1,\infty ]$. Our error is information-theoretically optimal for all $p\ge 2$, in particular, our mechanism is the first purely private covariance estimator that achieves optimal error in spectral norm. For small datasets $n<d^2/\epsilon$, we further show that by projecting the output onto the nuclear norm ball of appropriate radius, our algorithm achieves the optimal Frobenius norm error $O(\sqrt{d\text{Tr}(\hat{I}\pounds )/n})$, improving over the known bounds of $O(\sqrt{d/n})$ of \cite{nikolov2023private} and $O\left(d^{3/4}\sqrt{\text{Tr}(\hat{I}\pounds )/n}\right)$ of \cite{dong2022differentially}.

ALT 2026; equal contribution