Private Adaptive Covariance Estimation via Gaussian Graphical Models
Cecilia Ferrando, Miguel Fuentes, Brett Mullins, Cameron Musco, Daniel Sheldon · 2026
Read Private Adaptive Covariance Estimation via Gaussian Graphical Models by Cecilia Ferrando, Miguel Fuentes, Brett Mullins, Cameron Musco, Daniel Sheldon (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-24295.txt.
Introduction
Ferrando and four co-authors present PACE-GGM, a data-adaptive private method for covariance estimation. It spends its privacy budget on top entries rather than perturbing all entries. The setting assumes separate bounds per variable, so single entries can be measured with less noise. Each round selects a poorly approximated entry, measures it with the Gaussian mechanism, then rebuilds a full matrix through a maximum-entropy objective, yielding a Gaussian graphical model. Tests on datasets show steady error improvements over the Gaussian mechanism and other baselines.
Catalog record
| CREATOR | Cecilia Ferrando, Miguel Fuentes, Brett Mullins, Cameron Musco, Daniel Sheldon |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 62678 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.24295
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Private Adaptive Covariance Estimation via Gaussian Graphical Models Cecilia Ferrando, Miguel Fuentes, Brett Mullins, Cameron Musco, Daniel Sheldon Abstract 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. 1 Introduction Covariance estimation is a fundamental primitive in statistics and machine learning, underpinning tasks such as regression, principal component analysis, and multivariate modeling. In settings involving sensitive data, differential privacy (DP) provides a rigorous framework for releasing covariance estimates while protecting individual-level information. A canonical approach to private covariance estimation is to use the Gaussian mechanism to add noise to each of the d(d+1)/2 distinct entries of the empirical covariance matrix of d -dimensional data records, with sensitivity computed from an assumed bound on the \ell_{2} norm of a data record. This approach was pioneered in [ 13 ] and is used as a core routine in many other algorithms [ 26 , 29 , 1 , 4 , 18 ] . However, in many applications it is more natural to assume coordinate-wise bounds rather than an a priori bound on the \ell_{2} norm of a full data record, and in this setting measuring individual entries can be substantially cheaper, from a privacy perspective, than perturbing the entire matrix. For example, assuming the i th coordinate of each data record has magnitude at most 1 , the sensitivity of an invidual entry of the covariance matrix is a factor of d/\sqrt{2} smaller than that of the full matrix, so it can be measured more precisely than the full matrix for the same privacy budget. This observation raises a natural question: can we design an algorithm that selectively measures a subset of entries of the empirical covariance matrix and uses them to reconstruct a full matrix? Selective measurement methods are widely used in differential privacy for query answering and synthetic data generation and often give state-of-the-art performance at realistic privacy budgets [ 20 , 19 , 2 , 33 , 8 , 21 , 14 ] . Applying this principle to covariance estimation requires both an adaptive selection procedure and a principled reconstruction method. We propose private adaptive covariance estimation via Gaussian graphical models ( PACE-GGM ) which iteratively selects the worst approximated entries, privately measures them via the Gaussian mechanism, and reconstructs the full covariance matrix using a new maximum-entropy reconstruction method. This connects to the classical covariance selection problem of 11 , yielding estimates with sparse precision matrices. Empirically, PACE-GGM outperforms the Gaussian mechanism and other existing methods, with gains most pronounced in the high-dimensional or low-to-moderate privacy budget regime. 2 Related Work Differentially private covariance estimation The canonical approach to private covariance estimation is the Gaussian mechanism, introduced by 13 : a symmetric Gaussian noise matrix is added to the empirical covariance, with noise applied to all entries and noise scale calibrated to the data only through global sensitivity. The same method is often called “sufficient statistic perturbation” ( SSP ) in private parametric statistical estimation, especially for linear regression [ 29 ] , and we often use this name for brevity. While simple and computationally efficient, SSP is fundamentally data-independent: the same noise scale is used to perturb every entry regardless of its magnitude or importance, and the output is not guaranteed to be positive semidefinite (PSD). 4 propose CoinPress, which builds on [ 16 ] and assumes a conservative prior spectral bound on the population covariance and iteratively clips data and shrinks this bound to reduce sensitivity, but still privatizes the full d\times d matrix each iteration via the Gaussian mechanism. 28 study the high-dimensional sparse setting and propose DP-Thresholding: Gaussian noise is added to all entries of the empirical covariance, and a deterministic hard-thresholding step is applied in post-processing to exploit the assumed sparsity of the true covariance. The privacy budget is spent on the full matrix, with sparsity used only to reduce estimation error. 12 propose SeparateCov and AdaptiveCov, which improve over SSP in the high-dimensional regime by decoupling eigenvalue and eigenvector estimation. AdaptiveCov further selects the best between two different estimators. Despite the structural decomposition, both algorithms still involve a step that privatizes the full covariance matrix, and the adaptivity operates at the level of estimator selection, not entry measurement. In contrast, PACE-GGM is the first method to privately and adaptively select which entries to measure based on the data. By concentrating the privacy budget on the entries that are most poorly approximated by the current estimate, and recovering the remaining entries through maximum-entropy reconstruction, PACE-GGM avoids spending budget on entries that cannot be measured informatively. Gaussian graphical models and covariance selection The maximum-entropy reconstruction at the heart of PACE-GGM is directly connected to the classical theory of Gaussian graphical models [ 17 ] . 11 showed that the maximum likelihood estimator of a Gaussian distribution subject to a fixed sparsity pattern S on the precision matrix K=\Sigma^{-1} is equivalent to the maximum-entropy PSD completion of the observed entries in S , with K_{jk}=0 automatically for all (j,k)\notin S . This is the covariance selection problem, and the solution is known to be a Gaussian graphical model with independence graph determined by S [ 17 ] . PACE-GGM extends this classical framework to the private adaptive measurements setting where the algorithm selects S privately and iteratively using the exponential mechanism, and observes entries with Gaussian noise rather than exactly. 3 Background We work under zero-concentrated differential privacy (zCDP) [ 6 ] in the bounded DP model, where X\in\mathcal{X}^{n} denotes a dataset of n records from the data universe \mathcal{X} . Definition 3.1 (Neighboring datasets) . Two datasets X,X^{\prime}\in\mathcal{X}^{n} are neighboring ( X\sim X^{\prime} ) if they differ in a single record. Definition 3.2 ( \rho -zCDP [ 6 ] ) . A randomized mechanism \mathcal{M} satisfies \rho -zCDP if for all X\sim X^{\prime} and all \gamma>1 , D_{\gamma}(\mathcal{M}(X)\|\mathcal{M}(X^{\prime}))\leq\rho\gamma, where D_{\gamma}(\mathcal{M}(X)\|\mathcal{M}(X^{\prime})) is the \gamma -Rényi divergence between the distributions of \mathcal{M}(X) and \mathcal{M}(X^{\prime}) . Definition 3.3 ( \ell_{2} sensitivity) . The \ell_{2} sensitivity of f:\mathcal{X}^{n}\to\mathbb{R}^{d} is \Delta(f)=\max_{X\sim X^{\prime}}\|f(X)-f(X^{\prime})\|_{2} . Proposition 3.4 (Gaussian mechanism [ 6 ] ) . Let f:\mathcal{X}^{n}\to\mathbb{R}^{d} be a function with \ell_{2} sensitivity \Delta(f) . The mechanism \mathcal{M}(X)=f(X)+\mathcal{N}(0,\sigma^{2}I_{d}) satisfies \frac{\Delta(f)^{2}}{2\sigma^{2}} -zCDP. Proposition 3.5 (Exponential mechanism [ 22 , 6 ] ) . Let \text{score}_{r}(X) be a quality score with sensitivity \Delta . The mechanism that selects r with probability proportional to \exp\!\bigl(\frac{\epsilon}{2\Delta}\text{score}_{r}(X)\bigr) satisfies \frac{\epsilon^{2}}{8} -zCDP. Proposition 3.6 (Composition and post-processing [ 6 , 30 ] ) . If \mathcal{M}_{1} satisfies \rho_{1} -zCDP and \mathcal{M}_{2} satisfies \rho_{2} -zCDP, their (possibly adaptive) composition satisfies (\rho_{1}+\rho_{2}) -zCDP. Any post-processing of a