Private Adaptive Covariance Estimation via Gaussian Graphical Models
For practitioners needing differentially private covariance estimation, PACE-GGM offers a data-adaptive method that outperforms standard approaches, though it is an incremental improvement.
PACE-GGM adaptively allocates privacy budget to the most informative entries of the empirical covariance matrix, achieving consistent improvements in estimation error over baselines, especially in high-dimensional settings with low-to-moderate privacy.
We propose PACE-GGM, a data-adaptive differentially private method for covariance estimation that concentrates its privacy budget on the most informative entries of the empirical covariance matrix, rather than perturbing all entries. This applies in the natural setting where the modeler supplies separate bounds for each variable, so that individual entries can be measured with less noise than the full matrix. In each round, our method selects a poorly approximated entry, measures it using the Gaussian mechanism, and then reconstructs a full covariance matrix using a maximum-entropy reconstruction objective, leading to a Gaussian graphical model structure. Experiments on diverse real-world datasets demonstrate consistent improvements in estimation error with respect to the Gaussian mechanism and other baselines, particularly in high-dimensional and low-to-moderate privacy regimes.