标题： 关于纯粹隐私协方差估计 显示英文标题

标题： On Purely Private Covariance Estimation

摘要： 我们提出了一种简单的扰动机制，用于在纯差分隐私下释放$d$维协方差矩阵$\Sigma$。 对于至少包含$n\geq d^2/\varepsilon$个元素的大数据集，我们的机制恢复了\cite{nikolov2023private}的可证明最优 Frobenius 范数误差保证，同时实现了所有其他$p$-Schatten 范数的最佳已知误差，具有$p\in [1,\infty]$。 我们的误差在所有$p\ge 2$方面都是信息论最优的，特别是，我们的机制是第一个在谱范数中实现最优误差的纯粹私有协方差估计器。 对于小数据集$n< d^2/\varepsilon$，我们进一步证明，通过将输出投影到适当半径的核范数球上，我们的算法实现了最优的弗罗贝尼乌斯范数误差$O(\sqrt{d\;\text{Tr}(\Sigma) /n})$，优于已知的$O(\sqrt{d/n})$的\cite{nikolov2023private}和${O}\big(d^{3/4}\sqrt{\text{Tr}(\Sigma)/n}\big)$的\cite{dong2022differentially}。 显示英文摘要

摘要： 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}.