Settling Pure Differentially Private Covariance Estimation

We study the problem of $d$-dimensional covariance matrix release under \textit{pure} differential privacy with error measured in Schatten-$p$ norms, where $p\in [1,\infty].$ We identify two meaningful sample-size regimes with qualitatively different behavior, and give a single efficient algorithm together with matching information-theoretic lower bounds throughout. In the \emph{large-sample} regime $n \gtrsim d^{2}/\varepsilon$, we show that the simple $K$-norm mechanism analyzed by \cite{d2026purely} is simultaneously optimal for all Schatten norms $p\in[1,\infty]$, yielding sharp rates from nuclear to spectral norm. In the \emph{moderate-sample} regime $d/\varepsilon \lesssim n \lesssim d^{2}/\varepsilon$, the problem remains non-trivially solvable, but the $K$-norm mechanism becomes suboptimal. We then design a single improved, efficient, $\varepsilon$-differentially private estimator based on the perturb-and-project framework; this estimator is optimal in all regimes and simultaneously for all Schatten norms. Prior to this work, improvements over the $K$-norm mechanism in this regime were only known for Frobenius loss \cite{nikolov2023private}. A key feature of the moderate-sample regime is an inherent dependency of the error on the nuclear norm of the input, first observed by \cite{dong2022differentially} and further investigated by \cite{d2026purely}. Our mechanism captures this dependence uniformly over $p$, and our lower bounds show it to be unavoidable, establishing optimal rates in all regimes, including the correct dependence on $\|\Sigma\|_*$. %The implications of our approach go beyond covariance release: we obtain optimal guarantees for privately releasing arbitrary matrices under nuclear-norm adjacency, and give partial extensions to higher-order moment estimation under pure differential privacy. These extensions highlight the perturb-and-project framework as a flexible tool for private high-dimensional data release, even beyond second moments. Our results extend and are optimal for the more general problem of privately releasing arbitrary matrices under nuclear-norm adjacency. Finally, our lower-bound techniques further generalize to higher-order tensors, establishing similar limitations for higher-order moment estimation under pure differential privacy.