# On Purely Private Covariance Estimation

arXiv: https://arxiv.org/abs/2510.26717 · HTML: https://mlsanity.com/paper/2510.26717/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- Builds on 5 of its 15 references that are in the map.
- First posted on arXiv 30 Oct 2025.

## Builds on (most cited first, 5 of 5)

- [Privately Learning High-Dimensional Distributions](https://mlsanity.com/paper/1805.00216/) (2018)
- [Efficient Algorithms for Privately Releasing Marginals via Convex Relaxations](https://mlsanity.com/paper/1308.1385/) (2013)
- [Differentially Private Covariance Revisited](https://mlsanity.com/paper/2205.14324/) (2022)
- [Private Query Release via the Johnson-Lindenstrauss Transform](https://mlsanity.com/paper/2208.07410/) (2022)
- [Perturb-and-Project: Differentially Private Similarities and Marginals](https://mlsanity.com/paper/2406.04868/) (2024)

## Built on by (most cited first, 1 of 1)

- [Improved Private Sparse Covariance Estimation with Multiscale Threshold Tests](https://mlsanity.com/paper/2609.22783/) (2026)

## Abstract (arXiv)

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.