We present a simple perturbation mechanism for the release of $d$-dimensional covariance matrices $\Sigma$ under pure differential privacy. For large datasets with at least $n\geq d^2/\varepsilon$ 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/\varepsilon$, 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}(\Sigma) /n})$, improving over the known bounds of $O(\sqrt{ d/n})$ of \cite{ nikolov2023private} and ${ O}\big(d^{ 3/4}\sqrt{ \text{ Tr}(\Sigma)/n}\big)$ of \cite{ dong2022differentially}.
Categories: cs.LG cs.DS