{"ID":2848167,"CreatedAt":"2026-06-01T04:54:23.091178241Z","UpdatedAt":"2026-06-01T04:54:23.091178241Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2510.26717","arxiv_id":"2510.26717","title":"On Purely Private Covariance Estimation","abstract":"We present a simple perturbation mechanism for the release of $d$-dimensional covariance matrices $Σ$ 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\u003c 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}(Σ) /n})$, improving over the known bounds of $O(\\sqrt{d/n})$ of \\cite{nikolov2023private} and ${O}\\big(d^{3/4}\\sqrt{\\text{Tr}(Σ)/n}\\big)$ of \\cite{dong2022differentially}.","short_abstract":"We present a simple perturbation mechanism for the release of $d$-dimensional covariance matrices $Σ$ 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 simult...","url_abs":"https://arxiv.org/abs/2510.26717","url_pdf":"https://arxiv.org/pdf/2510.26717v2","authors":"[\"Tommaso d'Orsi\",\"Gleb Novikov\"]","published":"2025-10-30T17:18:53Z","proceeding":"cs.LG","tasks":"[\"cs.LG\",\"cs.DS\"]","methods":"[]","has_code":false}