On Purely Private Covariance Estimation

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≥ d2/varepsilon elements, our mechanism recovers the provably optimal Frobenius norm error guarantees of citenikolov2023private, while simultaneously achieving best known error for all other p-Schatten norms, with p∈ [1,∞]. Our error is information-theoretically optimal for all p≥ 2, in particular, our mechanism is the first purely private covariance estimator that achieves optimal error in spectral norm. For small datasets n< d2/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(√d;Tr(Sigma) /n), improving over the known bounds of O(√d/n) of citenikolov2023private and Obig(d3/4√Tr(Sigma)/nbig) of citedong2022differentially.