Private Adaptive Covariance Estimation via Gaussian Graphical Models

# Private Adaptive Covariance Estimation via Gaussian Graphical Models
Source: [https://arxiv.org/html/2605.24295](https://arxiv.org/html/2605.24295)
Cecilia Ferrando Miguel Fuentes Brett Mullins Cameron Musco Daniel Sheldon Manning College of Information and Computer Sciences University of Massachusetts Amherst

###### Abstract

We proposePACE\-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\.

## 1Introduction

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 thed​\(d\+1\)/2d\(d\+1\)/2distinct entries of the empirical covariance matrix ofdd\-dimensional data records, with sensitivity computed from an assumed bound on theℓ2\\ell\_\{2\}norm of a data record\. This approach was pioneered in\[[13](https://arxiv.org/html/2605.24295#bib.bib3)\]and is used as a core routine in many other algorithms\[[26](https://arxiv.org/html/2605.24295#bib.bib123),[29](https://arxiv.org/html/2605.24295#bib.bib83),[1](https://arxiv.org/html/2605.24295#bib.bib16),[4](https://arxiv.org/html/2605.24295#bib.bib166),[18](https://arxiv.org/html/2605.24295#bib.bib26)\]\.

However, in many applications it is more natural to assume*coordinate\-wise*bounds rather than an a priori bound on theℓ2\\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 theiith coordinate of each data record has magnitude at most11, the sensitivity of an invidual entry of the covariance matrix is a factor ofd/2d/\\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](https://arxiv.org/html/2605.24295#bib.bib144),[19](https://arxiv.org/html/2605.24295#bib.bib64),[2](https://arxiv.org/html/2605.24295#bib.bib65),[33](https://arxiv.org/html/2605.24295#bib.bib61),[8](https://arxiv.org/html/2605.24295#bib.bib62),[21](https://arxiv.org/html/2605.24295#bib.bib58),[14](https://arxiv.org/html/2605.24295#bib.bib210)\]\. 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 ofDempster \[[11](https://arxiv.org/html/2605.24295#bib.bib154)\], yielding estimates with sparse precision matrices\. Empirically,PACE\-GGMoutperforms the Gaussian mechanism and other existing methods, with gains most pronounced in the high\-dimensional or low\-to\-moderate privacy budget regime\.

## 2Related Work

#### Differentially private covariance estimation

The canonical approach to private covariance estimation is the Gaussian mechanism, introduced byDworket al\.\[[13](https://arxiv.org/html/2605.24295#bib.bib3)\]: 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](https://arxiv.org/html/2605.24295#bib.bib83)\], and we often use this name for brevity\. While simple and computationally efficient,SSPis 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\)\.

Biswaset al\.\[[4](https://arxiv.org/html/2605.24295#bib.bib166)\]propose CoinPress, which builds on\[[16](https://arxiv.org/html/2605.24295#bib.bib165)\]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 fulld×dd\\times dmatrix each iteration via the Gaussian mechanism\.Wang and Xu \[[28](https://arxiv.org/html/2605.24295#bib.bib164)\]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\.Donget al\.\[[12](https://arxiv.org/html/2605.24295#bib.bib12)\]propose SeparateCov and AdaptiveCov, which improve overSSPin 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\-GGMis 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\-GGMavoids spending budget on entries that cannot be measured informatively\.

#### Gaussian graphical models and covariance selection

The maximum\-entropy reconstruction at the heart ofPACE\-GGMis directly connected to the classical theory of Gaussian graphical models\[[17](https://arxiv.org/html/2605.24295#bib.bib151)\]\.Dempster \[[11](https://arxiv.org/html/2605.24295#bib.bib154)\]showed that the maximum likelihood estimator of a Gaussian distribution subject to a fixed sparsity patternSSon the precision matrixK=Σ−1K=\\Sigma^\{\-1\}is equivalent to the maximum\-entropy PSD completion of the observed entries inSS, withKj​k=0K\_\{jk\}=0automatically for all\(j,k\)∉S\(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 bySS\[[17](https://arxiv.org/html/2605.24295#bib.bib151)\]\.PACE\-GGMextends this classical framework to the private adaptive measurements setting where the algorithm selectsSSprivately and iteratively using the exponential mechanism, and observes entries with Gaussian noise rather than exactly\.

## 3Background

We work under zero\-concentrated differential privacy \(zCDP\)\[[6](https://arxiv.org/html/2605.24295#bib.bib150)\]in the bounded DP model, whereX∈𝒳nX\\in\\mathcal\{X\}^\{n\}denotes a dataset ofnnrecords from the data universe𝒳\\mathcal\{X\}\.

###### Definition 3\.1\(Neighboring datasets\)\.

Two datasetsX,X′∈𝒳nX,X^\{\\prime\}\\in\\mathcal\{X\}^\{n\}are*neighboring*\(X∼X′X\\sim X^\{\\prime\}\) if they differ in a single record\.

###### Definition 3\.2\(ρ\\rho\-zCDP\[[6](https://arxiv.org/html/2605.24295#bib.bib150)\]\)\.

A randomized mechanismℳ\\mathcal\{M\}satisfiesρ\\rho\-zCDP if for allX∼X′X\\sim X^\{\\prime\}and allγ\>1\\gamma\>1,

Dγ​\(ℳ​\(X\)∥ℳ​\(X′\)\)≤ρ​γ,D\_\{\\gamma\}\(\\mathcal\{M\}\(X\)\\\|\\mathcal\{M\}\(X^\{\\prime\}\)\)\\leq\\rho\\gamma,whereDγ​\(ℳ​\(X\)∥ℳ​\(X′\)\)D\_\{\\gamma\}\(\\mathcal\{M\}\(X\)\\\|\\mathcal\{M\}\(X^\{\\prime\}\)\)is theγ\\gamma\-Rényi divergence between the distributions ofℳ​\(X\)\\mathcal\{M\}\(X\)andℳ​\(X′\)\\mathcal\{M\}\(X^\{\\prime\}\)\.

###### Definition 3\.3\(ℓ2\\ell\_\{2\}sensitivity\)\.

Theℓ2\\ell\_\{2\}sensitivity off:𝒳n→ℝdf:\\mathcal\{X\}^\{n\}\\to\\mathbb\{R\}^\{d\}isΔ​\(f\)=maxX∼X′⁡‖f​\(X\)−f​\(X′\)‖2\\Delta\(f\)=\\max\_\{X\\sim X^\{\\prime\}\}\\\|f\(X\)\-f\(X^\{\\prime\}\)\\\|\_\{2\}\.

###### Proposition 3\.4\(Gaussian mechanism\[[6](https://arxiv.org/html/2605.24295#bib.bib150)\]\)\.

Letf:𝒳n→ℝdf:\\mathcal\{X\}^\{n\}\\to\\mathbb\{R\}^\{d\}be a function withℓ2\\ell\_\{2\}sensitivityΔ​\(f\)\\Delta\(f\)\. The mechanismℳ​\(X\)=f​\(X\)\+𝒩​\(0,σ2​Id\)\\mathcal\{M\}\(X\)=f\(X\)\+\\mathcal\{N\}\(0,\\sigma^\{2\}I\_\{d\}\)satisfiesΔ​\(f\)22​σ2\\frac\{\\Delta\(f\)^\{2\}\}\{2\\sigma^\{2\}\}\-zCDP\.

###### Proposition 3\.5\(Exponential mechanism\[[22](https://arxiv.org/html/2605.24295#bib.bib8),[6](https://arxiv.org/html/2605.24295#bib.bib150)\]\)\.

Letscorer​\(X\)\\text\{score\}\_\{r\}\(X\)be a quality score with sensitivityΔ\\Delta\. The mechanism that selectsrrwith probability proportional toexp⁡\(ϵ2​Δ​scorer​\(X\)\)\\exp\\\!\\bigl\(\\frac\{\\epsilon\}\{2\\Delta\}\\text\{score\}\_\{r\}\(X\)\\bigr\)satisfiesϵ28\\frac\{\\epsilon^\{2\}\}\{8\}\-zCDP\.

###### Proposition 3\.6\(Composition and post\-processing\[[6](https://arxiv.org/html/2605.24295#bib.bib150),[30](https://arxiv.org/html/2605.24295#bib.bib9)\]\)\.

Ifℳ1\\mathcal\{M\}\_\{1\}satisfiesρ1\\rho\_\{1\}\-zCDP andℳ2\\mathcal\{M\}\_\{2\}satisfiesρ2\\rho\_\{2\}\-zCDP, their \(possibly adaptive\) composition satisfies\(ρ1\+ρ2\)\(\\rho\_\{1\}\+\\rho\_\{2\}\)\-zCDP\. Any post\-processing of aρ\\rho\-zCDP mechanism satisfiesρ\\rho\-zCDP\.

###### Lemma 3\.7\(zCDP to approximate DP\[[6](https://arxiv.org/html/2605.24295#bib.bib150)\]\)\.

Ifℳ\\mathcal\{M\}satisfiesρ\\rho\-zCDP, then for anyδ\>0\\delta\>0it satisfies\(ρ\+2​ρ​ln⁡\(1/δ\),δ\)\\bigl\(\\rho\+2\\sqrt\{\\rho\\ln\(1/\\delta\)\},\\,\\delta\\bigr\)\-DP\.

## 4Method

### 4\.1Problem setup and motivation

#### Setup

Assume we have a datasetX∈ℝn×dX\\in\\mathbb\{R\}^\{n\\times d\}with rowsx\(1\),…,x\(n\)x^\{\(1\)\},\\ldots,x^\{\(n\)\}corresponding to individual records and a user\-supplied coordinate\-wise bound\|xj\|≤B\|x\_\{j\}\|\\leq Bfor each possible data recordxxand coordinatejj\. The user must guarantee these bounds either using domain knowledge or by clipping the data or discarding records that violate them\. If different bounds are supplied for each coordinate, the columns ofXXcan be rescaled to use a common boundBB\. We focus on estimating the empirical second\-moment matrixΣ​\(X\)=1n​X⊤​X\\Sigma\(X\)=\\frac\{1\}\{n\}X^\{\\top\}Xunderρ\\rho\-zCDP\. Throughout this work we assume the data is centered \(or equivalently that the population mean is zero\), so thatΣ​\(X\)\\Sigma\(X\)coincides with the empirical covariance matrix\. More generally, one could privately estimate the mean and use the plug\-in covariance estimator1n​X⊤​X−μ​μ⊤,\\frac\{1\}\{n\}X^\{\\top\}X\-\\mu\\mu^\{\\top\},but we omit this step for simplicity\. While we focus on estimating the empirical covariance, such a routine is also useful for estimating the population covariance under a statistical model in the many cases whereΣ​\(X\)\\Sigma\(X\)is a natural estimator of the population covariance\.

#### Motivation for selective measurement

Our coordinate\-wise bounding assumption is equivalent to theℓ∞\\ell\_\{\\infty\}bound‖x‖∞≤B\\\|x\\\|\_\{\\infty\}\\leq B\. This is natural whenever features are independently bounded, e\.g\., tabular datasets with clipped or normalized attributes, measurements with known reference ranges, or any setting where each feature is pre\-processed to lie within a fixed interval \(which after rescaling maps to\[−B,B\]\[\-B,B\]\)\. In this setting, the sensitivity of a single entry ofΣ​\(X\)\\Sigma\(X\)is2​B2/n2B^\{2\}/n, while the sensitivity of the full matrix is2​d​B2/n\\sqrt\{2\}dB^\{2\}/n\(see Appendix[A](https://arxiv.org/html/2605.24295#A1)\), so a single entry can be measured with noise standard deviation a factor ofd/2d/\\sqrt\{2\}smaller than that required to measure the full matrix for the same privacy budget\. This motivates the idea of selectively measuring a subset of entries that are most important\.

Most prior covariance estimation methods assume anℓ2\\ell\_\{2\}bound‖x‖2≤C\\\|x\\\|\_\{2\}\\leq Con the data\. In this case, the sensitivity of a single entry is about the same as the full matrix\(C2/n\(C^\{2\}/nvs\.2​C2/n\\sqrt\{2\}C^\{2\}/n\), so it does not appear helpful to measure a subset of entries\. To understand the apparent discrepancy, suppose the modeler knows only‖x‖∞≤B\\\|x\\\|\_\{\\infty\}\\leq Band needs to derive anℓ2\\ell\_\{2\}bound\. Since each entry ofxxcould have magnitudeBB, the tightest bound is‖x‖2≤C=d​B\\\|x\\\|\_\{2\}\\leq C=\\sqrt\{d\}B: this yields the same sensitivity of2​d​B2/n\\sqrt\{2\}dB^\{2\}/nfor the full matrix but a now loose bound ofd​B2/ndB^\{2\}/nfor a single entry\.

To summarize, if the user starts by knowing only coordinate\-wise bounds, which is a very natural setting, then measuring individual entries can save privacy budget relative to measuring the full matrix\. However, this possibility may be obscured if the user uses theℓ∞\\ell\_\{\\infty\}bound to convert to anℓ2\\ell\_\{2\}bound\. On the other hand, if the user truly knows a tightℓ2\\ell\_\{2\}bound, e\.g\.,‖x‖2≤C\\\|x\\\|\_\{2\}\\leq CwhereCCis not much bigger than theℓ∞\\ell\_\{\\infty\}bound‖x‖∞≤B\\\|x\\\|\_\{\\infty\}\\leq B—informally, this requires prior knowledge that not too many entries ofxxcan be large simultaneously—then measuring individual entries is not likely to be helpful compared to measuring the full matrix\.

### 4\.2ThePACE\-GGMalgorithm

Our proposed method for*private adaptive covariance estimation via Gaussian graphical models*\(PACE\-GGM\) is shown in Algorithm[1](https://arxiv.org/html/2605.24295#alg1)\.PACE\-GGMis based on the*select\-measure\-reconstruct*paradigm used throughout the adaptive query release and synthetic data generation literature\[[20](https://arxiv.org/html/2605.24295#bib.bib144),[19](https://arxiv.org/html/2605.24295#bib.bib64),[2](https://arxiv.org/html/2605.24295#bib.bib65),[33](https://arxiv.org/html/2605.24295#bib.bib61),[8](https://arxiv.org/html/2605.24295#bib.bib62),[21](https://arxiv.org/html/2605.24295#bib.bib58),[14](https://arxiv.org/html/2605.24295#bib.bib210)\], and in particular on AIM \(*adaptive iterative mechanism*\), a state\-of\-the\-art method for synthetic data and marginal query answering\[[21](https://arxiv.org/html/2605.24295#bib.bib58)\]\.PACE\-GGMinitially uses a portion of the privacy budget to measure all diagonal elements ofΣ\\Sigmaand form an initial estimateΣ^\(0\)\\hat\{\\Sigma\}^\{\(0\)\}\(Algorithm[2](https://arxiv.org/html/2605.24295#alg2)\)\. Throughout the algorithm, it maintains a set of noisy measurements\{yj​k\}\\\{y\_\{jk\}\\\}of matrix entries together with the values\{λj​k\}\\\{\\lambda\_\{jk\}\\\}representing the precision \(inverse variance\) of eachyj​ky\_\{jk\}\. It then iteratively follows the select\-measure\-reconstruct framework\. In each iteration, it firstselectsan entryΣj​k\\Sigma\_\{jk\}that is poorly approximated by the current estimate using the exponential mechanism\. It thenmeasuresthe selected entry with the Gaussian mechanism and updates the precision\-weighted average measurementyj​ky\_\{jk\}and precisionλj​k\\lambda\_\{jk\}for that entry\. Finally, itreconstructsa new covariance estimateΣ^\(t\)\\hat\{\\Sigma\}^\{\(t\)\}by solving an optimization problem to find the maximum entropy PSD matrix among all minimizers of a reconstruction error that is equivalent to the negative log\-likelihood of the observed measurements\.

The sensitive dataXXis only accessed in the select and measure steps\. These steps use the exponential and Gaussian mechanisms together with a zCDP composition analysis similar to the one in AIM\[[21](https://arxiv.org/html/2605.24295#bib.bib58)\]to prove that the whole procedure satisfiesρ\\rho\-zCDP\. We return to the details in Section[4\.6](https://arxiv.org/html/2605.24295#S4.SS6)after describing our maximum entropy reconstruction method, which is a key innovation to enable adaptive covariance estimation\.

Algorithm 1PACE\-GGM1:Data

X∈ℝn×dX\\in\\mathbb\{R\}^\{n\\times d\}, max rounds

TT, budget

ρ\\rho, coordinate\-wise bound

BB, parameters

α,β\\alpha,\\beta
2:Private covariance estimate

Σ^\\hat\{\\Sigma\}
3:Per\-entry sensitivity

Δ←2​B2/n\\Delta\\leftarrow 2B^\{2\}/n
4:Initialize measurements

\{yj​k\}\\\{y\_\{jk\}\\\}, precisions

\{λj​k\}\\\{\\lambda\_\{jk\}\\\}, estimate

Σ^\(0\)\\hat\{\\Sigma\}^\{\(0\)\}using Algorithm[2](https://arxiv.org/html/2605.24295#alg2)with budget

ρdiag=α​ρ\\rho\_\{\\text\{diag\}\}=\\alpha\\rho\.

5:

ρused←ρdiag\\rho\_\{\\text\{used\}\}\\leftarrow\\rho\_\{\\text\{diag\}\}ρper\-round←\(ρ−ρused\)/T\\rho\_\{\\text\{per\-round\}\}\\leftarrow\(\\rho\-\\rho\_\{\\text\{used\}\}\)/Tρsel←β​ρper\-round\\rho\_\{\\text\{sel\}\}\\leftarrow\\beta\\rho\_\{\\text\{per\-round\}\}ρmeas←\(1−β\)​ρper\-round\\rho\_\{\\text\{meas\}\}\\leftarrow\(1\-\\beta\)\\rho\_\{\\text\{per\-round\}\}
6:

t←0t\\leftarrow 0
7:while

ρused<ρ\\rho\_\{\\text\{used\}\}<\\rhodo

8:

t←t\+1t\\leftarrow t\+1
9:Selectentry

\(j,k\)\(j,k\)via exponential mechanism with

ρsel\\rho\_\{\\text\{sel\}\}and worst\-approx\. score function:

Pr⁡\(select​\(j,k\)\)∝exp⁡\(ϵ2​Δ⋅err​\(j,k\)\),ϵ=8​ρsel,err​\(j,k\)=\|Σj​k​\(X\)−Σ^j​k\(t−1\)\|\\Pr\(\\text\{select\\ \}\(j,k\)\)\\propto\\exp\\left\(\\frac\{\\epsilon\}\{2\\Delta\}\\cdot\\text\{err\}\(j,k\)\\right\),\\quad\\epsilon=\\sqrt\{8\\rho\_\{\\text\{sel\}\}\},\\quad\\text\{err\}\(j,k\)=\|\\Sigma\_\{jk\}\(X\)\-\\hat\{\\Sigma\}^\{\(t\-1\)\}\_\{jk\}\|
10:Measure

Σj​k\\Sigma\_\{jk\}with budget

ρmeas\\rho\_\{\\text\{meas\}\}and update precision\-weighted average measurement:

zj​k←Σj​k​\(X\)\+𝒩​\(0,σt2\),σt2=Δ2/\(2​ρmeas\)z\_\{jk\}\\leftarrow\\Sigma\_\{jk\}\(X\)\+\\mathcal\{N\}\(0,\\sigma^\{2\}\_\{t\}\),\\quad\\sigma^\{2\}\_\{t\}=\\Delta^\{2\}/\(2\\rho\_\{\\text\{meas\}\}\)yj​k←\(λj​k​yj​k\+σt−2​zj​k\)/\(λj​k\+σt−2\),λj​k←λj​k\+σt−2y\_\{jk\}\\leftarrow\(\\lambda\_\{jk\}\\,y\_\{jk\}\+\\sigma^\{\-2\}\_\{t\}\\,z\_\{jk\}\)/\(\\lambda\_\{jk\}\+\\sigma^\{\-2\}\_\{t\}\),\\qquad\\lambda\_\{jk\}\\leftarrow\\lambda\_\{jk\}\+\\sigma^\{\-2\}\_\{t\}
11:Reconstructcovariance matrix via maximum\-entropy reconstruction:

Σ^\(t\)←argmax\{log⁡\|Σ\|:Σ∈arg⁡minW⪰0​∑j≥kλj​k​\(Wj​k−yj​k\)2\}\\hat\{\\Sigma\}^\{\(t\)\}\\leftarrow\\operatorname\*\{argmax\}\\\{\\log\|\\Sigma\|:\\Sigma\\in\\arg\\min\_\{W\\succeq 0\}\\sum\_\{j\\geq k\}\\lambda\_\{jk\}\\,\(W\_\{jk\}\-y\_\{jk\}\)^\{2\}\\\}
12:

ρused←ρused\+ρsel\+ρmeas\\rho\_\{\\text\{used\}\}\\leftarrow\\rho\_\{\\text\{used\}\}\+\\rho\_\{\\text\{sel\}\}\+\\rho\_\{\\text\{meas\}\}
13:Anneal budgets using Algorithm[3](https://arxiv.org/html/2605.24295#alg3)\.

14:endwhile

15:return

Σ^\(t\)\\hat\{\\Sigma\}^\{\(t\)\}

Algorithm 2Initialization1:

λj​k←0\\lambda\_\{jk\}\\leftarrow 0,

yj​k←0y\_\{jk\}\\leftarrow 0for all

j≥kj\\geq k
2:

σ2=Δ2/\(2​ρdiag/d\)\\sigma^\{2\}=\\Delta^\{2\}/\(2\\rho\_\{\\text\{diag\}\}/d\)
3:for

j=1j=1to

dddo

4:

yj​j←Σj​j​\(X\)\+𝒩​\(0,σ2\)y\_\{jj\}\\leftarrow\\Sigma\_\{jj\}\(X\)\+\\mathcal\{N\}\(0,\\sigma^\{2\}\)
5:

λj​j←σ−2\\lambda\_\{jj\}\\leftarrow\\sigma^\{\-2\}
6:endfor

7:

Σ^\(0\)←diag⁡\(y11∨0,…,yd​d∨0\)\\hat\{\\Sigma\}^\{\(0\)\}\\leftarrow\\operatorname\{diag\}\(y\_\{11\}\\vee 0,\\ldots,y\_\{dd\}\\vee 0\)
8:return

\{yj​k\}\\\{y\_\{jk\}\\\},

\{λj​k\}\\\{\\lambda\_\{jk\}\\\},

Σ^\(0\)\\hat\{\\Sigma\}^\{\(0\)\}

Algorithm 3Budget annealing1:if

\|Σ^j​k\(t\)−Σ^j​k\(t−1\)\|≤2/π​σt\|\\hat\{\\Sigma\}\_\{jk\}^\{\(t\)\}\-\\hat\{\\Sigma\}^\{\(t\-1\)\}\_\{jk\}\|\\leq\\sqrt\{2/\\pi\}\\,\\sigma\_\{t\}then

2:

ρsel←2​ρsel\\rho\_\{\\text\{sel\}\}\\leftarrow 2\\,\\rho\_\{\\text\{sel\}\}ρmeas←4​ρmeas\\rho\_\{\\text\{meas\}\}\\leftarrow 4\\,\\rho\_\{\\text\{meas\}\}
3:endif

4:if

\(ρ−ρused\)<2​\(ρsel\+ρmeas\)\(\\rho\-\\rho\_\{\\text\{used\}\}\)<2\(\\rho\_\{\\text\{sel\}\}\+\\rho\_\{\\text\{meas\}\}\)then

5:

ρsel←β​\(ρ−ρused\)\\rho\_\{\\text\{sel\}\}\\leftarrow\\beta\(\\rho\-\\rho\_\{\\text\{used\}\}\)ρmeas←\(1−β\)​\(ρ−ρused\)\\rho\_\{\\text\{meas\}\}\\leftarrow\(1\-\\beta\)\(\\rho\-\\rho\_\{\\text\{used\}\}\)
6:endif

### 4\.3Maximum\-entropy covariance reconstruction

General problemSuppose we are given noisy observations of some entries of a PSD matrixΣ\\Sigma, including all of the diagonal entries:

yj​k=Σj​k\+𝒩​\(0,τj​k2\),\(j,k\)∈Sy\_\{jk\}=\\Sigma\_\{jk\}\+\\mathcal\{N\}\(0,\\tau\_\{jk\}^\{2\}\),\\quad\(j,k\)\\in S\(1\)whereSSis a set of ordered pairs\(j,k\)\(j,k\)withj≥kj\\geq kand\(j,j\)∈S\(j,j\)\\in Sfor alljj\. This setup assumes that the diagonal entries are always observed, and additionally some entries in the lower triangle are observed; the upper triangle is determined by symmetry\. We further assume that each entry is measured at most once; we show below that this is without loss of generality\.

Our reconstruction objective is to solve the following bilevel optimization problem:

max⁡log⁡\|Σ\|s\.t\.Σ∈arg⁡minW⪰0⁡ℒ​\(W\),ℒ​\(W\)=∑\(j,k\)∈S12​τj​k2​\(Wj​k−yj​k\)2\.\\displaystyle\\max\\log\|\\Sigma\|\\quad\\text\{s\.t\.\}\\quad\\Sigma\\in\\arg\\min\_\{W\\succeq 0\}\\mathcal\{L\}\(W\),\\quad\\mathcal\{L\}\(W\)=\\sum\_\{\(j,k\)\\in S\}\\frac\{1\}\{2\\tau\_\{jk\}^\{2\}\}\(W\_\{jk\}\-y\_\{jk\}\)^\{2\}\.\(2\)The inner objectiveℒ​\(W\)\\mathcal\{L\}\(W\)is the negative log\-likelihood of the observations\{yj​k\}\(j,k\)∈S\\\{y\_\{jk\}\\\}\_\{\(j,k\)\\in S\}under covariance matrixWWplus a constant\. Thus, the inner optimization seeks the PSD matrix that maximizes the log\-likelihood of the measurements\. The outer objective selects the minimizer ofℒ​\(W\)\\mathcal\{L\}\(W\)with the largest log\-determinant\. This is equivalent to finding the maximum\-entropy distribution whose covariance matrix minimizesℒ​\(W\)\\mathcal\{L\}\(W\): for anyW⪰0W\\succeq 0, the distribution𝒩​\(0,W\)\\mathcal\{N\}\(0,W\)has maximum differential entropy over all distributions onℝd\\mathbb\{R\}^\{d\}with the same covariance, and its entropy is12​log⁡\|W\|\\frac\{1\}\{2\}\\log\|W\|plus a constant\[[9](https://arxiv.org/html/2605.24295#bib.bib218)\]\. Entropy is a measure of smoothness of a distribution and is often used to select the simplest explanation matching a set of observations\[[11](https://arxiv.org/html/2605.24295#bib.bib154)\]\.

Our problem is closely connected to Dempster’s*covariance selection*framework\[[11](https://arxiv.org/html/2605.24295#bib.bib154)\]and Gaussian graphical models \(GGMs\)\[[17](https://arxiv.org/html/2605.24295#bib.bib151)\]\. Ifτj​k→0\\tau\_\{jk\}\\to 0for all\(j,k\)∈S\(j,k\)\\in Sthe inner objective requiresWj​k→yj​kW\_\{jk\}\\to y\_\{jk\}and the problem becomes the covariance selection problem, which is to find the maximum entropy completion of a partially specified covariance matrix\. Our problem is a generalization where observations are noisy, so the inner optimization seeks to maximize likelihood rather than constrainWWto exactly match observations\. Dempster showed that the covariance selection problem has a unique solution with a sparse inverse\. Our problem shares this structure:

###### Proposition 4\.1\.

Supposearg⁡minW⪰0⁡ℒ​\(W\)\\arg\\min\_\{W\\succeq 0\}\\mathcal\{L\}\(W\)contains a positive definite matrix\. Then Problem[2](https://arxiv.org/html/2605.24295#S4.E2)has a unique solutionΣ∗\\Sigma^\{\*\}andK∗=\(Σ∗\)−1K^\{\*\}=\(\\Sigma^\{\*\}\)^\{\-1\}satisfiesKj​k∗=0K^\{\*\}\_\{jk\}=0for\(j,k\),\(k,j\)∉S\(j,k\),\(k,j\)\\notin S\.

###### Proof sketch\.

It can be shown that there are unique values\(aj​k\)\(j,k\)∈S\(a\_\{jk\}\)\_\{\(j,k\)\\in S\}such thatWWminimizesℒ​\(W\)\\mathcal\{L\}\(W\)if and only ifWj​k=aj​kW\_\{jk\}=a\_\{jk\}for all\(j,k\)∈S\(j,k\)\\in S\. The result then follows from\[[11](https://arxiv.org/html/2605.24295#bib.bib154)\]\. ∎

The full proof is given in Appendix[B\.1](https://arxiv.org/html/2605.24295#A2.SS1)\. Ifarg⁡minW⪰0⁡ℒ​\(W\)\\arg\\min\_\{W\\succeq 0\}\\mathcal\{L\}\(W\)does not contain a positive definite matrix, the problem is ill posed and the optimal value is−∞\-\\infty; we discuss further below and in[B\.2](https://arxiv.org/html/2605.24295#A2.SS2)\.

Proposition[4\.1](https://arxiv.org/html/2605.24295#S4.Thmtheorem1)is a useful structural property and says that the solution is the covariance matrix of a Gaussian graphical model, which satisfies certain conditional independence properties\[[17](https://arxiv.org/html/2605.24295#bib.bib151)\]\. For example, ifX∼𝒩​\(0,Σ∗\)X\\sim\\mathcal\{N\}\(0,\\Sigma^\{\*\}\), thenXjX\_\{j\}andXkX\_\{k\}are conditionally indpendent given the other variables wheneverKj​k∗=0K^\{\*\}\_\{jk\}=0, i\.e\., whenever the entries\(j,k\)\(j,k\)and\(k,j\)\(k,j\)are not observed\. In practice, our optimizer will solve Problem[2](https://arxiv.org/html/2605.24295#S4.E2)to within a numerical tolerance such that the inverse is not exactly sparse, though it is likely possible to design optimizers that enforce sparsity exactly\.

#### Application toPACE\-GGM

It is easy to see that wheneverPACE\-GGMmeasures each entry at most once, the measurements\{yj​k\}\\\{y\_\{jk\}\\\}fit the model in Equation \([1](https://arxiv.org/html/2605.24295#S4.E1)\) withτj​k2=λj​k−1\\tau\_\{jk\}^\{2\}=\\lambda\_\{jk\}^\{\-1\}andS=\{\(j,k\):λj​k\>0\}S=\\\{\(j,k\):\\lambda\_\{jk\}\>0\\\}, giving the objective in the algorithm:

ℒ​\(W\)=∑\(j,k\)∈Sλj​k​\(Wj​k−yj​k\)2,S=\{\(j,k\):λj​k\>0\}\.\\mathcal\{L\}\(W\)=\\sum\_\{\(j,k\)\\in S\}\\lambda\_\{jk\}\\,\(W\_\{jk\}\-y\_\{jk\}\)^\{2\},\\quad S=\\\{\(j,k\):\\lambda\_\{jk\}\>0\\\}\.Now we will show that this objective is also correct whenyj​ky\_\{jk\}is the inverse\-variance weighted average of multiple measurements andλj​k\\lambda\_\{jk\}is the combined precision\.

###### Proposition 4\.2\.

Letℒ​\(W\)=∑t=1T12​σt2​\(Wjt​kt−zt\)2\\mathcal\{L\}\(W\)=\\sum\_\{t=1\}^\{T\}\\frac\{1\}\{2\\sigma\_\{t\}^\{2\}\}\(W\_\{j\_\{t\}k\_\{t\}\}\-z\_\{t\}\)^\{2\}be the log\-likelihood of a sequence of noisy measurementszt=Σjt​kt\+𝒩​\(0,σt2\)z\_\{t\}=\\Sigma\_\{j\_\{t\}k\_\{t\}\}\+\\mathcal\{N\}\(0,\\sigma^\{2\}\_\{t\}\)fort=1,…,Tt=1,\\ldots,T\. This can be rewritten as

ℒ​\(W\)=∑\(j,k\)∈Sλj​k​\(Wj​k−yj​k\)2\+C,\\mathcal\{L\}\(W\)=\\sum\_\{\(j,k\)\\in S\}\\lambda\_\{jk\}\\,\(W\_\{jk\}\-y\_\{jk\}\)^\{2\}\+C,where𝕋j​k=\{t:\(jt,kt\)=\(j,k\)\}\\mathbb\{T\}\_\{jk\}=\\\{t:\(j\_\{t\},k\_\{t\}\)=\(j,k\)\\\},λj​k=∑t∈𝕋j​kσt−2\\lambda\_\{jk\}=\\sum\_\{t\\in\\mathbb\{T\}\_\{jk\}\}\\sigma\_\{t\}^\{\-2\},yj​k=λj​k−1​∑t∈𝕋j​kσt−2​zty\_\{jk\}=\\lambda\_\{jk\}^\{\-1\}\\sum\_\{t\\in\\mathbb\{T\}\_\{jk\}\}\\sigma\_\{t\}^\{\-2\}z\_\{t\},S=\{\(j,k\):𝕋j​k≠∅\}S=\\\{\(j,k\):\\mathbb\{T\}\_\{jk\}\\neq\\emptyset\\\}, andCCis a constant independent ofWW\.

The proof is in Appendix[B\.3](https://arxiv.org/html/2605.24295#A2.SS3)\.PACE\-GGMmaintains the precision\-weighted averageyj​ky\_\{jk\}and combined precisionλj​k\\lambda\_\{jk\}for each entry and updates them with each new measurement\.

### 4\.4Solving the reconstruction problem

#### Optimization approach

There are multiple possible approaches to solve Problem[2](https://arxiv.org/html/2605.24295#S4.E2)\. One option is a two\-stage approach suggested by the proof of Proposition[4\.1](https://arxiv.org/html/2605.24295#S4.Thmtheorem1): first solve the inner problem to find any minimizerW∗W^\{\*\}, extract the unique valuesaj​k=Wj​k∗a\_\{jk\}=W^\{\*\}\_\{jk\}for\(j,k\)∈S\(j,k\)\\in S, and then solve the covariance selection problem with\(aj​k\)\(j,k\)∈S\(a\_\{jk\}\)\_\{\(j,k\)\\in S\}as the observed entries\. However, we found this to be unstable in practice: with noisy enough observations, it is often the case that*every*matrix inargminW⪰0ℒ​\(W\)\\operatorname\*\{argmin\}\_\{W\\succeq 0\}\\mathcal\{L\}\(W\)is singular and therefore the covariance selection problem is ill posed \(for details, see the discussion in Appendix[B\.2](https://arxiv.org/html/2605.24295#A2.SS2)\)\.

Instead, we propose an interior point method whereΣ\\Sigmais parameterized by a Cholesky factor \(IPM\-Cholesky\)\. The interior point method solves a sequence of strictly convex barrier\-penalized problems and provides a clean way to handle ill posed problems\. Forμ\>0\\mu\>0, define

Σμ∗=argminW⪰0\(ℒ​\(W\)−μ​log⁡\|W\|\)\.\\Sigma^\{\*\}\_\{\\mu\}=\\operatorname\*\{argmin\}\_\{W\\succeq 0\}\(\\mathcal\{L\}\(W\)\-\\mu\\log\|W\|\)\.\(3\)It can be shown thatΣμ∗\\Sigma^\{\*\}\_\{\\mu\}is uniquely determined for eachμ\>0\\mu\>0and converges to a uniqueΣ∗∈argminW⪰0ℒ​\(W\)\\Sigma^\{\*\}\\in\\operatorname\*\{argmin\}\_\{W\\succeq 0\}\\mathcal\{L\}\(W\)asμ→0\\mu\\to 0\[[5](https://arxiv.org/html/2605.24295#bib.bib219)\]\. When the condition of Proposition[4\.1](https://arxiv.org/html/2605.24295#S4.Thmtheorem1)holds,Σ∗\\Sigma^\{\*\}is the unique positive definite solution to Problem[2](https://arxiv.org/html/2605.24295#S4.E2)\. When the condition does not hold, all minimizers have entropy of−∞\-\\infty; selectingΣ∗\\Sigma^\{\*\}is well motivated as it is the limit of a sequence of entropy regularized solutions\.

It remains to solve the barrier\-penalized problem \([3](https://arxiv.org/html/2605.24295#S4.E3)\)\. To handle the PSD constraint, we parameterizeΣ\\Sigmavia its Cholesky decompositionΣ=L​L⊤\\Sigma=LL^\{\\top\}, whereLLis lower triangular with nonnegative diagonal entries\. The log\-determinant becomeslog⁡\|Σ\|=2​∑j=1dlog⁡Lj​j\\log\|\\Sigma\|=2\\sum\_\{j=1\}^\{d\}\\log L\_\{jj\}\. Then, for a sequence of geometrically decreasing values ofμ\\mu, we minimize the barrier\-penalized objective

φμ​\(L\)=∑\(j,k\)∈S\(\(L​L⊤\)j​k−yj​k\)22​τj​k2−2​μ​∑j=1dlog⁡Lj​j\\displaystyle\\varphi\_\{\\mu\}\(L\)=\\sum\_\{\(j,k\)\\in S\}\\frac\{\(\(LL^\{\\top\}\)\_\{jk\}\-y\_\{jk\}\)^\{2\}\}\{2\\tau\_\{jk\}^\{2\}\}\-2\\mu\\sum\_\{j=1\}^\{d\}\\log L\_\{jj\}\(4\)via L\-BFGS\-B onφμ\\varphi\_\{\\mu\}with bound constraintsLj​j≥0L\_\{jj\}\\geq 0\. A downside is thatφμ​\(L\)\\varphi\_\{\\mu\}\(L\)is not convex inLL, so global convergence is not guaranteed\. However, we found performance to be excellent in practice, and this method is closely related to Burer\-Monteiro methods for semidefinite programming\[[7](https://arxiv.org/html/2605.24295#bib.bib220)\], which are widely reported to perform well in practice and provably converge under certain conditions\[[15](https://arxiv.org/html/2605.24295#bib.bib221)\]\. Notably, the per\-iteration cost to computeφμ​\(L\)\\varphi\_\{\\mu\}\(L\)and its gradient is onlyO​\(\|S\|​d\)O\(\|S\|\\,d\)—dominated by the time to compute\(L​L⊤\)j​k\(LL^\{\\top\}\)\_\{jk\}for each\(j,k\)∈S\(j,k\)\\in S—and, ifSSis sparse, avoids the typicalΘ​\(d3\)\\Theta\(d^\{3\}\)per\-iteration cost for dealing with PSD matrices\.

#### Sparsity\-aware optimization

The setSSdetermines a graphGGon the vertex set\{1,…,d\}\\\{1,\\ldots,d\\\}with an edge\(j,k\)\(j,k\)whenever\(j,k\)∈S\(j,k\)\\in S\. Problem[2](https://arxiv.org/html/2605.24295#S4.E2)is closely related to sparse matrix nearness\[[27](https://arxiv.org/html/2605.24295#bib.bib222)\]and covariance selection\[[10](https://arxiv.org/html/2605.24295#bib.bib223)\]problems\. By embeddingGGin a chordal graph with maximal cliques of sized1,…,dmd\_\{1\},\\ldots,d\_\{m\}, relevant linear algebraic operations can be performed in timeO​\(∑i=1mdi3\)O\(\\sum\_\{i=1\}^\{m\}d\_\{i\}^\{3\}\)via clique trees rather thanO​\(d3\)O\(d^\{3\}\)time needed for dense matrices, which is beneficial when the cliques are small\. We explored such methods and found them promising for very large problems, but they required non\-trivial adaptations and yielded at most modest gains at the scales considered here \(d≤260d\\leq 260\), so we leave further exploration to future work\.

On the other hand, sincePACE\-GGMstarts with only diagonal measurements and then adds a single entry per round, the measurement setsSSare often extremely sparse, and we found that a simple decomposition based on connected components yielded significant gains\. SupposeGGhas connected componentsV1,…,VKV\_\{1\},\\ldots,V\_\{K\}\. SinceSScontains no edges between components,ℒ​\(W\)\\mathcal\{L\}\(W\)depends only on the diagonal blocksWVi,ViW\_\{V\_\{i\},V\_\{i\}\}\. Among feasibleWW, Fischer’s inequality\|W\|≤∏i\|WVi,Vi\|\|W\|\\leq\\prod\_\{i\}\|W\_\{V\_\{i\},V\_\{i\}\}\|\(with equality iffWWis block diagonal\) implies the maximum oflog⁡\|W\|\\log\|W\|is attained at a block\-diagonal matrix\. HenceΣ∗\\Sigma^\{\*\}is block diagonal and each block solves an independent instance of Problem[2](https://arxiv.org/html/2605.24295#S4.E2)onViV\_\{i\}\. In the extreme case whereSScontains only the diagonal entries, each block is a single vertex, so the solution is simply the diagonal matrix with entriesyj​j∨0y\_\{jj\}\\vee 0\(cf\.Σ^\(0\)\\hat\{\\Sigma\}^\{\(0\)\}in Algorithm[2](https://arxiv.org/html/2605.24295#alg2)\)\.

### 4\.5Budget annealing

A key challenge in adaptive measurement algorithms is deciding how many measurements to make vs\. relying on reconstruction to fill in unmeasured quantities\. A good choice typically depends on the privacy budget, the problem size, and data properties\. A key contribution of AIM was to introduce a budget annealing strategy to address this challenge\[[21](https://arxiv.org/html/2605.24295#bib.bib58)\], which we adapt here \(Algorithm[3](https://arxiv.org/html/2605.24295#alg3)\)\. We start with a per\-round budget that would allow running for up toTTrounds, whereTTis a generous bound set by the user\. Then, in Line 1 of Algorithm[3](https://arxiv.org/html/2605.24295#alg3), the procedure checks how much the estimateΣ^j​k\\hat\{\\Sigma\}\_\{jk\}changes compared to the previous round afterΣj​k\\Sigma\_\{jk\}is measured\. If the change is small relative to the noise standard deviationσt\\sigma\_\{t\}\(the quantity2/π​σt\\sqrt\{2/\\pi\}\\,\\sigma\_\{t\}is𝔼​\[\|ξ\|\]\\mathbb\{E\}\[\|\\xi\|\]forξ∼𝒩\(0,σt2\\xi\\sim\\mathcal\{N\}\(0,\\sigma\_\{t\}^\{2\}\)\), it indicates the current noise is too large to provide informative measurements, so the per\-round privacy budgets are increased \(Line 2\)\. This will lead to fewer but more informative future measurements\. Lines 4–6 of Algorithm[3](https://arxiv.org/html/2605.24295#alg3)are a simple measure to ensure the privacy budget is fully exhausted in the final round\.

### 4\.6Privacy guarantee

###### Theorem 4\.3\(Privacy of Algorithm[1](https://arxiv.org/html/2605.24295#alg1)\)\.

Algorithm[1](https://arxiv.org/html/2605.24295#alg1)satisfiesρ\\rho\-zCDP\.

###### Proof\.

We analyze each phase separately and apply zCDP composition \(Proposition[3\.6](https://arxiv.org/html/2605.24295#S3.Thmtheorem6)\)\. Recall that the sensitivity of each entry ofΣ\\SigmaisΔ=2​B2/n\\Delta=2B^\{2\}/n\(Appendix[A](https://arxiv.org/html/2605.24295#A1)\)\.

Phase 1\.Each diagonal entry is released via the Gaussian mechanism with sensitivityΔ\\Deltaand per\-entry budgetρdiag/d\\rho\_\{\\mathrm\{diag\}\}/d, satisfying\(ρdiag/d\)\(\\rho\_\{\\mathrm\{diag\}\}/d\)\-zCDP per entry\. By composition overddindependent releases, Phase 1 satisfiesρdiag\\rho\_\{\\mathrm\{diag\}\}\-zCDP whereρdiag=α​ρ\\rho\_\{\\mathrm\{diag\}\}=\\alpha\\rho\.

Phase 2\.Each roundttconsists of \(i\) an exponential mechanism selection step satisfyingρsel\(t\)\\rho\_\{\\mathrm\{sel\}\}^\{\(t\)\}\-zCDP and \(ii\) a Gaussian mechanism measurement step satisfyingρmeas\(t\)\\rho\_\{\\mathrm\{meas\}\}^\{\(t\)\}\-zCDP\. Since the selection at roundt\+1t\{\+\}1depends on the output of roundtt, this is an adaptive composition; byWhitehouseet al\.\[[30](https://arxiv.org/html/2605.24295#bib.bib9)\], each round satisfies\(ρsel\(t\)\+ρmeas\(t\)\)\(\\rho\_\{\\mathrm\{sel\}\}^\{\(t\)\}\+\\rho\_\{\\mathrm\{meas\}\}^\{\(t\)\}\)\-zCDP\. The algorithm tracks cumulative expenditureρused\\rho\_\{\\mathrm\{used\}\}and enforces∑t\(ρsel\(t\)\+ρmeas\(t\)\)≤\(1−α\)​ρ\\sum\_\{t\}\(\\rho\_\{\\mathrm\{sel\}\}^\{\(t\)\}\+\\rho\_\{\\mathrm\{meas\}\}^\{\(t\)\}\)\\leq\(1\-\\alpha\)\\rho\.

Therefore the total privacy cost across both phases is at mostρ\\rho\. The maximum entropy reconstruction step is post\-processing and incurs no additional privacy cost \(Proposition[3\.6](https://arxiv.org/html/2605.24295#S3.Thmtheorem6)\)\. ∎

## 5Experiments

We evaluatePACE\-GGMon real\-world datasets to assess its ability to accurately estimate covariance matrices under zCDP across a range of privacy budgets compared to non\-adaptive baselines\. We work with diverse datasets with dimensionality ranging fromd=6d=6tod=260d=260\. Appendix[D](https://arxiv.org/html/2605.24295#A4)provides detailed dataset descriptions, including key structural properties in Table[3](https://arxiv.org/html/2605.24295#A4.T3)\. For each dataset, we remove rows with missing values, and rescale all features to\[−1,1\]\[\-1,1\]coordinate\-wise, so that theℓ∞\\ell\_\{\\infty\}\-ball constraint‖x‖∞≤B=1\\\|x\\\|\_\{\\infty\}\\leq B=1holds\. To isolate the covariance estimation component, we assume the mean is known and use it to center the data\. In practice, part of the privacy budget would be allocated to mean estimation\. The datasets have a wide range of empirical covariance structures: the fraction of the squared Frobenius norm ofΣ\\Sigmathat comes from off\-diagonal entries \(eoffe\_\{\\mathrm\{off\}\}\) varies from near\-zero foradult\(0\.0180\.018\) andthyroid\_ann\(0\.0260\.026\), which are approximately diagonal, to0\.890\.89forcommunities\_crime, where off\-diagonal structure dominates\. This diversity helps investigate estimation under varying underlying structure\.

We evaluatePACE\-GGMover privacy budgetsρ∈\{10−4,10−3,10−2,10−1,1,2,10\}\\rho\\in\\\{10^\{\-4\},10^\{\-3\},10^\{\-2\},10^\{\-1\},1,2,10\\\}\. We setα=0\.3\\alpha=0\.3\(fraction of budget for diagonal initialization\) andβ=0\.5\\beta=0\.5\(fraction of per\-round budget for entry selection\)\. An ablation study is included in Appendix[I](https://arxiv.org/html/2605.24295#A9)\. The maximum number of rounds is set toT=⌊2⋅d​\(d−1\)/2⌋T=\\lfloor 2\\cdot d\(d\-1\)/2\\rfloor, allowing up to twice as many measurements as there are off\-diagonal entries\. Remeasurement of previously measured entries, including the diagonal entries, is allowed\. All experiments use theIPM\-Choleskysolver \(Algorithm[4](https://arxiv.org/html/2605.24295#alg4), Appendix[C](https://arxiv.org/html/2605.24295#A3)\)\. Each configuration is repeated for 10 independent trials using pre\-specified random seeds\.

#### Error metrics

We report two complementary metrics: \(i\)Mahalanobis error‖Σ−1/2​Σ^​Σ−1/2−I‖F\\\|\\Sigma^\{\-1/2\}\\hat\{\\Sigma\}\\Sigma^\{\-1/2\}\-I\\\|\_\{F\}, which measures shape accuracy by normalizing entry\-wise error relative to the true covariance structure and is invariant to affine transformations; and \(ii\)Frobenius error‖Σ^−Σ‖F\\\|\\hat\{\\Sigma\}\-\\Sigma\\\|\_\{F\}, which measures entry\-wise accuracy directly\.

#### Baselines

We comparePACE\-GGMagainst several baselines\.SSP\(Sufficient Statistic Perturbation\) applies the Gaussian mechanism to alld​\(d\+1\)/2d\(d\+1\)/2entries ofΣ\\Sigmausing the full budgetρ\\rhoand full\-matrix sensitivity\[[13](https://arxiv.org/html/2605.24295#bib.bib3)\]\.AdaptiveCov\[[12](https://arxiv.org/html/2605.24295#bib.bib12)\]selects between anSSPestimator \(GaussCov\) and a spectral approach \(SeparateCov\) that privatizes eigenvalues and eigenvectors via Gaussian mechanisms and reconstructs the covariance; here, adaptivity refers to mechanism selection rather than entry\-wise selection\. Finally, adiagonal\-only baselineallocates the entire budget to thedddiagonal entries \(withρ/d\\rho/dper entry\), sets off\-diagonal entries to zero, and projects the result to the PSD cone, illustrating the cost of ignoring correlations \(Appendix[E](https://arxiv.org/html/2605.24295#A5)\)111CoinPress\[[4](https://arxiv.org/html/2605.24295#bib.bib166)\]is another well known private covariance estimator, where the main idea is to iteratively refine bounds on the scale of covariance matrix when only a coarse upper bound is available, so the empirical covariance can be measured \(usingSSP\) with less noise\. In preliminary experiments, CoinPress performed poorly in our setup\. However, it is essentially solving an orthogonal problem to ours \(finding the right scale for clipping data\), which may be less relevant in our setting where we already provide tightℓ∞\\ell\_\{\\infty\}bounds on the data, so we do not include it in our empirical comparisons\.\.

### 5\.1Results

Figure[1](https://arxiv.org/html/2605.24295#S5.F1)shows results for 5 of the 14 datasets acrossdd\. Appendix[E](https://arxiv.org/html/2605.24295#A5)includes results for all datasets\.PACE\-GGMoverall outperformsSSPand often achieves lower error than AdaptiveCov on both metrics\. This illustrates thatPACE\-GGMis competitive with state\-of\-the\-art DP covariance estimators, often with the lowest error in the high\-privacy \(lowρ\\rho\) regime, and as dimension increases\.

Two additional findings are reported in Appendix[F](https://arxiv.org/html/2605.24295#A6)\. First, we show that the maximum\-entropy criterion consistently selects a high quality solution among all optimizers of the reconstruction objectiveℒ​\(W\)\\mathcal\{L\}\(W\), while simply minimizing the objective via projected gradient descent \(PGD\) yields a solution that is sensitive to initialization and may be much worse than the maximum\-entropy solution\. Second, we show that exploiting sparsity in the measurement graph via connected components accelerates optimization without affecting estimation accuracy\.

Table[1](https://arxiv.org/html/2605.24295#S5.T1)reports the average number of off\-diagonal entries measured \(lower triangle\) across datasets andρ\\rhovalues\. Three patterns emerge:

Measurements grow withρ\\rho\.As privacy budget increases,PACE\-GGMmeasures more off\-diagonal entries across all datasets\. Atρ=10−4\\rho=10^\{\-4\}, essentially only the diagonal and a handful of off\-diagonal entries are ever selected; asρ\\rhoincreases, the algorithm makes progressively more measurements\.

Sparsity grows withdd\.Asddincreases,PACE\-GGMmeasures a very small fraction of available off\-diagonal entries\. Atρ=10\\rho=10, the fraction ranges from87%87\\%foradult\(d=6d=6, 12 out of 15 off\-diagonal pairs\) down to0\.1%0\.1\\%formadeline\(d=260d=260, 39 out of 33,930\)\. This sparsity shows howPACE\-GGMconcentrates the privacy budget on the entries that both carry significant information and can be measured informatively\. The largerdd, the more this selective allocation matters, which explains why the advantage overSSPgrows with dimensionality\.

Measurements concentrate where covariance is denser\.The number of selected entries is also governed by the density of the underlying covariance\. We quantify density viaeoff=‖Σoff‖F2/‖Σ‖F2e\_\{\\mathrm\{off\}\}=\\\|\\Sigma\_\{\\mathrm\{off\}\}\\\|\_\{F\}^\{2\}/\\\|\\Sigma\\\|\_\{F\}^\{2\}, the fraction of squared Frobenius norm from off\-diagonal entries\. Atρ=10\\rho=10,communities\_crime\(d=102d=102,eoff=89\.5%e\_\{\\mathrm\{off\}\}=89\.5\\%\) requires 255 off\-diagonal measurements, more than six times as many asmadeline\(d=260d=260,eoff=24\.8%e\_\{\\mathrm\{off\}\}=24\.8\\%\) despite having less than half the dimension\.PACE\-GGMallocates more measurements whereeoffe\_\{\\mathrm\{off\}\}is higher, which demonstrates that it adapts to covariance structure and not just dimension\. Appendix[E](https://arxiv.org/html/2605.24295#A5)comparesPACE\-GGMto a diagonal\-only \(independent\) baselines that only privatizes the diagonal, ignoring off\-diagonal correlations: as expected, it is competitive withPACE\-GGMonly on datasets with nearly diagonal covariance\.

Together, these results show thatPACE\-GGMoften improves upon data\-independent methods by measuring entries adaptively with respect to the dimension, budget, and underlying covariance structure\.

![Refer to caption](https://arxiv.org/html/2605.24295v1/x1.png)Figure 1:Mahalanobis error \(top row\) and Frobenius error \(bottom row\) for a selection of datasets acrossdd\.PACE\-GGMand baselines across privacy budgetsρ\\rho, withα=0\.3\\alpha=0\.3,β=0\.5\\beta=0\.5\. Datasets are ordered by dimensionalityddacross three groups\.Table 1:Mean number of measurements per trial \(diagonal\+\+off\-diagonal\)\. The columnd​\(d\+1\)/2d\(d\+1\)/2gives the total number of unique entries in the covariance matrix\.

## 6Discussion

#### Limitations

PACE\-GGMassumes continuous data with coordinate\-wise bounds‖x‖∞≤B\\\|x\\\|\_\{\\infty\}\\leq B\. As discussed earlier, if the modeler knows tightℓ2\\ell\_\{2\}bounds that are not much bigger thanBB, there may be little advantage of measuring indvidual entries\. Performance on heavy\-tailed or strongly non\-Gaussian data has not been evaluated\. The per\-round cost isO​\(d3\)O\(d^\{3\}\)in the worst case, which may become limiting for very largedd\. The two hyperparametersα\\alphaandβ\\betahave robust defaults \(α=0\.3\\alpha\{=\}0\.3,β=0\.5\\beta\{=\}0\.5\) and the method is empirically insensitive to their exact values in\[0\.1,0\.5\]×\[0\.1,0\.5\]\[0\.1,0\.5\]\\times\[0\.1,0\.5\]\(see Appendix[I](https://arxiv.org/html/2605.24295#A9)\), but no fully private selection procedure is provided\. Finally, our experimental evaluation focuses onSSPand AdaptiveCov; comparisons to additional baselines are left for future work\.

#### Future directions

Directions for future work include investigating theoretical bounds on the error of the adaptive selection procedure and its performance for estimating of population parameters of different statistical models\. Computationally, a promising avenue is to develop a solver that uses chordal embeddings of the sparsity graph to reduce running times relative to the dense solver; this could allow scaling to very largeddwith sparse measurements\.

## 7Conclusion

We introducedPACE\-GGM, a differentially private empirical covariance estimator that adaptively selects which entries to measure based on the data\. By combining the exponential mechanism for entry selection, the Gaussian mechanism for measurement, inverse\-variance weighting for repeated measurements, and maximum\-entropy PSD reconstruction,PACE\-GGMconcentrates its privacy budget where most needed rather than spreading noise uniformly across alld​\(d\+1\)/2d\(d\+1\)/2entries\. Theℓ∞\\ell\_\{\\infty\}\-ball assumption is natural for tabular data with clipped or normalized features and enables our adaptive approach, since under this assumption the single\-entry sensitivity is a factor ofd/2d/\\sqrt\{2\}smaller than full\-matrix methods, allowing a method to measure a subset of entries much more accurately than the full matrix\. We proved that the algorithm satisfiesρ\\rho\-zCDP via adaptive composition and demonstrated consistent improvements over non\-adaptive baselines across fourteen real\-world datasets spanningd∈\[6,260\]d\\in\[6,260\], with gains most pronounced in the high\-dimensional, low\-to\-moderate budget regime that is most demanding in practice\.PACE\-GGMis suitable as a building block for continuous synthetic data generation, filling a gap left by marginal\-based methods that target discrete or discretized variables\.

## References

- \[1\]D\. Alabi, A\. McMillan, J\. Sarathy, and A\. Smith\(2020\)Differentially private simple linear regression\.arXiv preprint arXiv:2009\.xxxx\.External Links:[Link](https://arxiv.org/abs/2009.xxxx)Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p1.3)\.
- \[2\]S\. Aydore, W\. Brown, M\. Kearns, K\. Kenthapadi, L\. Melis, A\. Roth, and A\. Siva\(2021\)Differentially private query release through adaptive projection\.InInternational Conference on Machine Learning,pp\. 457–467\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p2.4),[§4\.2](https://arxiv.org/html/2605.24295#S4.SS2.p1.9)\.
- \[3\]B\. Becker and R\. Kohavi\(1996\)Adult\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5XW20Cited by:[1st item](https://arxiv.org/html/2605.24295#A4.I1.i1.p1.1)\.
- \[4\]S\. Biswas, Y\. Dong, G\. Kamath, and J\. Ullman\(2020\)Coinpress: practical private mean and covariance estimation\.Advances in Neural Information Processing Systems33,pp\. 14475–14485\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p1.3),[§2](https://arxiv.org/html/2605.24295#S2.SS0.SSS0.Px1.p2.1),[footnote 1](https://arxiv.org/html/2605.24295#footnote1)\.
- \[5\]S\. Boyd and L\. Vandenberghe\(2004\)Convex optimization\.Cambridge university press\.Cited by:[§4\.4](https://arxiv.org/html/2605.24295#S4.SS4.SSS0.Px1.p2.9)\.
- \[6\]M\. Bun and T\. Steinke\(2016\)Concentrated differential privacy: simplifications, extensions, and lower bounds\.InTheory of Cryptography Conference,pp\. 635–658\.Cited by:[Definition 3\.2](https://arxiv.org/html/2605.24295#S3.Thmtheorem2),[Proposition 3\.4](https://arxiv.org/html/2605.24295#S3.Thmtheorem4),[Proposition 3\.5](https://arxiv.org/html/2605.24295#S3.Thmtheorem5),[Proposition 3\.6](https://arxiv.org/html/2605.24295#S3.Thmtheorem6),[Lemma 3\.7](https://arxiv.org/html/2605.24295#S3.Thmtheorem7),[§3](https://arxiv.org/html/2605.24295#S3.p1.3)\.
- \[7\]S\. Burer and R\. D\. Monteiro\(2003\)A nonlinear programming algorithm for solving semidefinite programs via low\-rank factorization\.Mathematical programming95\(2\),pp\. 329–357\.Cited by:[§4\.4](https://arxiv.org/html/2605.24295#S4.SS4.SSS0.Px1.p3.15)\.
- \[8\]K\. Cai, X\. Lei, J\. Wei, and X\. Xiao\(2021\)Data synthesis via differentially private markov random fields\.Proceedings of the VLDB Endowment14\(11\),pp\. 2190–2202\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p2.4),[§4\.2](https://arxiv.org/html/2605.24295#S4.SS2.p1.9)\.
- \[9\]T\. M\. Cover and J\. A\. Thomas\(1991\)Elements of information theory\.Wiley\-Interscience,New York\.Cited by:[§4\.3](https://arxiv.org/html/2605.24295#S4.SS3.p2.9)\.
- \[10\]J\. Dahl, L\. Vandenberghe, and V\. Roychowdhury\(2008\)Covariance selection for nonchordal graphs via chordal embedding\.Optimization Methods and Software23\(4\),pp\. 501–520\.Cited by:[§4\.4](https://arxiv.org/html/2605.24295#S4.SS4.SSS0.Px2.p1.10)\.
- \[11\]A\. P\. Dempster\(1972\)Covariance selection\.Biometrics,pp\. 157–175\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p3.1),[§2](https://arxiv.org/html/2605.24295#S2.SS0.SSS0.Px2.p1.7),[§4\.3](https://arxiv.org/html/2605.24295#S4.SS3.1.p1.5),[§4\.3](https://arxiv.org/html/2605.24295#S4.SS3.p2.9),[§4\.3](https://arxiv.org/html/2605.24295#S4.SS3.p3.4)\.
- \[12\]W\. Dong, Y\. Liang, and K\. Yi\(2022\)Differentially private covariance revisited\.Advances in Neural Information Processing Systems35,pp\. 850–861\.Cited by:[§2](https://arxiv.org/html/2605.24295#S2.SS0.SSS0.Px1.p2.1),[§5](https://arxiv.org/html/2605.24295#S5.SS0.SSS0.Px2.p1.5)\.
- \[13\]C\. Dwork, K\. Talwar, A\. Thakurta, and L\. Zhang\(2014\)Analyze gauss: optimal bounds for privacy\-preserving principal component analysis\.InProceedings of the forty\-sixth annual ACM symposium on Theory of computing,pp\. 11–20\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p1.3),[§2](https://arxiv.org/html/2605.24295#S2.SS0.SSS0.Px1.p1.1),[§5](https://arxiv.org/html/2605.24295#S5.SS0.SSS0.Px2.p1.5)\.
- \[14\]M\. Fuentes, B\. Mullins, Y\. Xiao, D\. Kifer, C\. Musco, and D\. Sheldon\(2026\)Fast private adaptive query answering for large data domains\.arXiv preprint arXiv:2602\.05674\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p2.4),[§4\.2](https://arxiv.org/html/2605.24295#S4.SS2.p1.9)\.
- \[15\]M\. Journée, F\. Bach, P\. Absil, and R\. Sepulchre\(2010\)Low\-rank optimization on the cone of positive semidefinite matrices\.SIAM Journal on Optimization20\(5\),pp\. 2327–2351\.Cited by:[§4\.4](https://arxiv.org/html/2605.24295#S4.SS4.SSS0.Px1.p3.15)\.
- \[16\]G\. Kamath, J\. Li, V\. Singhal, and J\. Ullman\(2019\)Privately learning high\-dimensional distributions\.InConference on Learning Theory,pp\. 1853–1902\.Cited by:[§2](https://arxiv.org/html/2605.24295#S2.SS0.SSS0.Px1.p2.1)\.
- \[17\]S\. L\. Lauritzen\(1996\)Graphical models\.Vol\.17,Clarendon Press\.Cited by:[§2](https://arxiv.org/html/2605.24295#S2.SS0.SSS0.Px2.p1.7),[§4\.3](https://arxiv.org/html/2605.24295#S4.SS3.p3.4),[§4\.3](https://arxiv.org/html/2605.24295#S4.SS3.p5.6)\.
- \[18\]S\. Lin, E\. Paquette, and E\. D\. Kolaczyk\(2024\)Differentially private linear regression with linked data\.Harvard Data Science Review6\(3\)\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p1.3)\.
- \[19\]T\. Liu, G\. Vietri, and S\. Z\. Wu\(2021\)Iterative methods for private synthetic data: unifying framework and new methods\.Advances in Neural Information Processing Systems34,pp\. 690–702\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p2.4),[§4\.2](https://arxiv.org/html/2605.24295#S4.SS2.p1.9)\.
- \[20\]R\. McKenna, G\. Miklau, M\. Hay, and A\. Machanavajjhala\(2021\)Hdmm: optimizing error of high\-dimensional statistical queries under differential privacy\.arXiv preprint arXiv:2106\.12118\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p2.4),[§4\.2](https://arxiv.org/html/2605.24295#S4.SS2.p1.9)\.
- \[21\]R\. McKenna, B\. Mullins, D\. Sheldon, and G\. Miklau\(2022\)AIM: an adaptive and iterative mechanism for differentially private synthetic data\.arXiv preprint arXiv:2201\.12677\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p2.4),[§4\.2](https://arxiv.org/html/2605.24295#S4.SS2.p1.9),[§4\.2](https://arxiv.org/html/2605.24295#S4.SS2.p2.2),[§4\.5](https://arxiv.org/html/2605.24295#S4.SS5.p1.8)\.
- \[22\]F\. McSherry and K\. Talwar\(2007\)Mechanism design via differential privacy\.InProceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science \(FOCS ’07\),pp\. 94–103\.External Links:[Document](https://dx.doi.org/10.1109/FOCS.2007.41)Cited by:[Proposition 3\.5](https://arxiv.org/html/2605.24295#S3.Thmtheorem5)\.
- \[23\]K\. Rajarshi\(2018\)Life expectancy \(who\)\.Kaggle\.Note:[https://www\.kaggle\.com/datasets/kumarajarshi/life\-expectancy\-who](https://www.kaggle.com/datasets/kumarajarshi/life-expectancy-who)Accessed: 2025\-01\-16Cited by:[3rd item](https://arxiv.org/html/2605.24295#A4.I1.i3.p1.1)\.
- \[24\]M\. Redmond\(2002\)Communities and Crime\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C53W3XCited by:[5th item](https://arxiv.org/html/2605.24295#A4.I1.i5.p1.1)\.
- \[25\]\(2020\)Seoul Bike Sharing Demand\.Note:UCI Machine Learning RepositoryDOI: https://doi\.org/10\.24432/C5F62RCited by:[2nd item](https://arxiv.org/html/2605.24295#A4.I1.i2.p1.1)\.
- \[26\]O\. Sheffet\(2017\)Differentially private ordinary least squares\.InInternational Conference on Machine Learning,pp\. 3105–3114\.Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p1.3)\.
- \[27\]Y\. Sun and L\. Vandenberghe\(2015\)Decomposition methods for sparse matrix nearness problems\.SIAM Journal on Matrix Analysis and Applications36\(4\),pp\. 1691–1717\.Cited by:[§B\.2](https://arxiv.org/html/2605.24295#A2.SS2.p2.20),[§4\.4](https://arxiv.org/html/2605.24295#S4.SS4.SSS0.Px2.p1.10)\.
- \[28\]D\. Wang and J\. Xu\(2021\)Differentially private high dimensional sparse covariance matrix estimation\.Theoretical Computer Science865,pp\. 119–130\.Cited by:[§2](https://arxiv.org/html/2605.24295#S2.SS0.SSS0.Px1.p2.1)\.
- \[29\]Y\. Wang\(2018\)Revisiting differentially private linear regression: optimal and adaptive prediction & estimation in unbounded domain\.arXiv preprint arXiv:1803\.02596\.Cited by:[Appendix G](https://arxiv.org/html/2605.24295#A7.p1.2),[§1](https://arxiv.org/html/2605.24295#S1.p1.3),[§2](https://arxiv.org/html/2605.24295#S2.SS0.SSS0.Px1.p1.1)\.
- \[30\]J\. Whitehouse, A\. Ramdas, R\. Rogers, and S\. Wu\(2023\)Fully\-adaptive composition in differential privacy\.InInternational conference on machine learning,pp\. 36990–37007\.Cited by:[Proposition 3\.6](https://arxiv.org/html/2605.24295#S3.Thmtheorem6),[§4\.6](https://arxiv.org/html/2605.24295#S4.SS6.3.p3.8)\.
- \[31\]W\. Wolberg, O\. Mangasarian, N\. Street, and W\. Street\(1993\)Breast Cancer Wisconsin \(Diagnostic\)\.Note:UCI Machine Learning RepositoryExternal Links:[Document](https://dx.doi.org/10.24432/C5DW2B)Cited by:[4th item](https://arxiv.org/html/2605.24295#A4.I1.i4.p1.1)\.
- \[32\]H\. Ye, S\. Liu, H\. Cai, Q\. Zhou, and D\. Zhan\(2024\)A closer look at deep learning on tabular data\.arXiv preprint arXiv:2407\.00956\.Cited by:[6th item](https://arxiv.org/html/2605.24295#A4.I1.i6.p1.9)\.
- \[33\]Z\. Zhang, T\. Wang, J\. Honorio, N\. Li, M\. Backes, S\. He, J\. Chen, and Y\. Zhang\(2021\)PrivSyn: differentially private data synthesis\.Note:arXiv preprint, available at[https://arxiv\.org/abs/2107\.10874](https://arxiv.org/abs/2107.10874)Cited by:[§1](https://arxiv.org/html/2605.24295#S1.p2.4),[§4\.2](https://arxiv.org/html/2605.24295#S4.SS2.p1.9)\.

## Appendix ASensitivity analysis

In this Appendix, we derive the sensitivity bounds for the matrixΣ​\(X\)=1n​∑i=1nx\(i\)​x\(i\)​T\\Sigma\(X\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}x^\{\(i\)\}x^\{\(i\)T\}underℓ2\\ell\_\{2\}andℓ∞\\ell\_\{\\infty\}ball bounding assumptions\. We consider separartely the sensitivity of the full matrix, and a single entry\. Table[2](https://arxiv.org/html/2605.24295#A1.T2)summarizes the sensitivity bounds\.

Table 2:Sensitivity bounds for the matrixΣ​\(X\)=1n​∑i=1nx\(i\)​x\(i\)​T\\Sigma\(X\)=\\frac\{1\}\{n\}\\sum\_\{i=1\}^\{n\}x^\{\(i\)\}x^\{\(i\)T\}assuming either𝒳=\{x∈ℝd:‖x‖∞≤B\}\\mathcal\{X\}=\\\{x\\in\\mathbb\{R\}^\{d\}:\\\|x\\\|\_\{\\infty\}\\leq B\\\}\(i\.e\.,ℓ∞\\ell\_\{\\infty\}bound\) or𝒳=\{x∈ℝd:‖x‖2≤C\}\\mathcal\{X\}=\\\{x\\in\\mathbb\{R\}^\{d\}:\\\|x\\\|\_\{2\}\\leq C\\\}\(i\.e\.,ℓ2\\ell\_\{2\}bound\)\.### A\.1Sensitivity of full matrix

The sensitivity is

ΔΣ\\displaystyle\\Delta\_\{\\Sigma\}=supX∼X′‖Σ​\(X′\)−Σ​\(X\)‖F=supv,u∈𝒳‖1n​\(v​vT−u​uT\)‖F\\displaystyle=\\sup\_\{X\\sim X^\{\\prime\}\}\\\|\\Sigma\(X^\{\\prime\}\)\-\\Sigma\(X\)\\\|\_\{F\}=\\sup\_\{v,u\\in\\mathcal\{X\}\}\\bigg\\\|\\frac\{1\}\{n\}\(vv^\{T\}\-uu^\{T\}\)\\bigg\\\|\_\{F\}whereX′X^\{\\prime\}is obtained fromXXby adding recordvvand removinguu\.

Expanding the Frobenius norm and rearranging, we have

ΔΣ\\displaystyle\\Delta\_\{\\Sigma\}=1n​supv,u∈𝒳∑i,j\(vi​vj−ui​uj\)2\\displaystyle=\\frac\{1\}\{n\}\\sup\_\{v,u\\in\\mathcal\{X\}\}\\sqrt\{\\sum\_\{i,j\}\(v\_\{i\}v\_\{j\}\-u\_\{i\}u\_\{j\}\)^\{2\}\}=1n​supv,u∈𝒳∑i,j\(vi2​vj2\+ui2​uj2−2​vi​vj​ui​uj\)\\displaystyle=\\frac\{1\}\{n\}\\sup\_\{v,u\\in\\mathcal\{X\}\}\\sqrt\{\\sum\_\{i,j\}\\left\(v\_\{i\}^\{2\}v\_\{j\}^\{2\}\+u\_\{i\}^\{2\}u\_\{j\}^\{2\}\-2\\,v\_\{i\}v\_\{j\}\\,u\_\{i\}u\_\{j\}\\right\)\}=1n​supv,u∈𝒳\(∑ivi2\)2\+\(∑iui2\)2−2​\(∑ivi​ui\)2\\displaystyle=\\frac\{1\}\{n\}\\sup\_\{v,u\\in\\mathcal\{X\}\}\\sqrt\{\\Big\(\\sum\_\{i\}v\_\{i\}^\{2\}\\Big\)^\{2\}\+\\Big\(\\sum\_\{i\}u\_\{i\}^\{2\}\\Big\)^\{2\}\-2\\Big\(\\sum\_\{i\}v\_\{i\}u\_\{i\}\\Big\)^\{2\}\}=1n​supv,u∈𝒳‖v‖24\+‖u‖24−2​\(v⋅u\)2\\displaystyle=\\frac\{1\}\{n\}\\sup\_\{v,u\\in\\mathcal\{X\}\}\\sqrt\{\\\|v\\\|\_\{2\}^\{4\}\+\\\|u\\\|\_\{2\}^\{4\}\-2\\,\(v\\cdot u\)^\{2\}\}≤1n​supv,u∈𝒳‖v‖24\+‖u‖24\.\\displaystyle\\leq\\frac\{1\}\{n\}\\sup\_\{v,u\\in\\mathcal\{X\}\}\\sqrt\{\\\|v\\\|\_\{2\}^\{4\}\+\\\|u\\\|\_\{2\}^\{4\}\}\.
- •ℓ2\\ell\_\{2\}\-ball assumption\.If we assume‖v‖2,‖u‖2≤C\\\|v\\\|\_\{2\},\\\|u\\\|\_\{2\}\\leq C, then‖v‖24\+‖u‖24≤C4\+C4=2​C2\\sqrt\{\\\|v\\\|\_\{2\}^\{4\}\+\\\|u\\\|\_\{2\}^\{4\}\}\\leq\\sqrt\{C^\{4\}\+C^\{4\}\}=\\sqrt\{2\}\\,C^\{2\}, soΔΣ≤2​C2n\\Delta\_\{\\Sigma\}\\leq\\frac\{\\sqrt\{2\}\\,C^\{2\}\}\{n\}\. Further, assumingd≥2d\\geq 2all inequalities above are tight and the bound is achieved whenv=C​eiv=Ce\_\{i\}andu=C​eju=Ce\_\{j\}fori≠ji\\neq j, whereei,eje\_\{i\},e\_\{j\}are standard basic vectors\. Thus ΔΣ\\displaystyle\\Delta\_\{\\Sigma\}=2​C2n\.\\displaystyle=\\frac\{\\sqrt\{2\}\\,C^\{2\}\}\{n\}\.
- •ℓ∞\\ell\_\{\\infty\}\-ball assumption\.If we assume‖v‖∞,‖u‖∞≤B\\\|v\\\|\_\{\\infty\},\\\|u\\\|\_\{\\infty\}\\leq Bthen‖v‖2,‖u‖2≤C:=d​B\\\|v\\\|\_\{2\},\\\|u\\\|\_\{2\}\\leq C:=\\sqrt\{d\}\\,B, so by the case above we have ΔΣ≤2​d​B2n\.\\displaystyle\\Delta\_\{\\Sigma\}\\leq\\frac\{\\sqrt\{2\}\\,d\\,B^\{2\}\}\{n\}\.This bound is tight whenddis even andv=\(B,B,…,B,B\)v=\(B,B,\\ldots,B,B\)andu=\(B,B,…,−B,−B\)u=\(B,B,\\ldots,\-B,\-B\)withd/2d/2entries ofBBandd/2d/2entries of−B\-B, so that‖u\|2=‖v‖2=d​B\\\|u\|\_\{2\}=\\\|v\\\|\_\{2\}=\\sqrt\{d\}Bandv⋅u=0v\\cdot u=0, making all inequalities tight\.

### A\.2Sensitivity of a single entry

The sensitivity of a single entryΣj​k​\(X\)\\Sigma\_\{jk\}\(X\)forj≠kj\\neq kcan be written as

ΔΣj​k=supX∼X′\|Σj​k​\(X′\)−Σj​k​\(X\)\|=1n​supv,u∈𝒳\|vj​vk−uj​uk\|\\displaystyle\\Delta\_\{\\Sigma\_\{jk\}\}=\\sup\_\{X\\sim X^\{\\prime\}\}\\big\|\\Sigma\_\{jk\}\(X^\{\\prime\}\)\-\\Sigma\_\{jk\}\(X\)\\big\|=\\frac\{1\}\{n\}\\sup\_\{v,u\\in\\mathcal\{X\}\}\\big\|v\_\{j\}v\_\{k\}\-u\_\{j\}u\_\{k\}\\big\|where againX′X^\{\\prime\}is obtained fromXXby adding recordvvand removing recorduu\.

- •ℓ2\\ell\_\{2\}\-ball assumption\.If we assume‖v‖2≤C\\\|v\\\|\_\{2\}\\leq Cand‖u‖2≤C\\\|u\\\|\_\{2\}\\leq C, then forj≠kj\\neq k, \|vj​vk−uj​uk\|≤\|vj​vk\|\+\|uj​uk\|≤C22\+C22=C2,\|v\_\{j\}v\_\{k\}\-u\_\{j\}u\_\{k\}\|\\leq\|v\_\{j\}v\_\{k\}\|\+\|u\_\{j\}u\_\{k\}\|\\leq\\frac\{C^\{2\}\}\{2\}\+\\frac\{C^\{2\}\}\{2\}=C^\{2\},where the bound is tight, for example, whenvj=vk=uj=−uk=C/2v\_\{j\}=v\_\{k\}=u\_\{j\}=\-u\_\{k\}=C/\\sqrt\{2\}\. For diagonal entriesj=kj=k, we instead have \|vj2−uj2\|≤C2,\|v\_\{j\}^\{2\}\-u\_\{j\}^\{2\}\|\\leq C^\{2\},sincevj2,uj2∈\[0,C2\]v\_\{j\}^\{2\},u\_\{j\}^\{2\}\\in\[0,C^\{2\}\]\. Therefore, for all entries, ΔΣj​k=C2n\.\\Delta\_\{\\Sigma\_\{jk\}\}=\\frac\{C^\{2\}\}\{n\}\.
- •ℓ∞\\ell\_\{\\infty\}\-ball assumption\.If we assume‖v‖∞≤B\\\|v\\\|\_\{\\infty\}\\leq Band‖u‖∞≤B\\\|u\\\|\_\{\\infty\}\\leq B, then \|vj​vk−uj​uk\|≤\|vj​vk\|\+\|uj​uk\|≤B2\+B2=2​B2,\|v\_\{j\}v\_\{k\}\-u\_\{j\}u\_\{k\}\|\\leq\|v\_\{j\}v\_\{k\}\|\+\|u\_\{j\}u\_\{k\}\|\\leq B^\{2\}\+B^\{2\}=2B^\{2\},and the inequalities are tight whenvj=vk=uj=−uk=Bv\_\{j\}=v\_\{k\}=u\_\{j\}=\-u\_\{k\}=B, so ΔΣj​k=2​B2n\.\\Delta\_\{\\Sigma\_\{jk\}\}=\\frac\{2B^\{2\}\}\{n\}\.

## Appendix BProofs and analysis for the reconstruction problem

### B\.1Properties of the maximum\-entropy reconstruction

###### Proof of Proposition[4\.1](https://arxiv.org/html/2605.24295#S4.Thmtheorem1)\.

Because the objectiveℒ​\(W\)\\mathcal\{L\}\(W\)depends onlyWj​kW\_\{jk\}for\(j,k\)∈S\(j,k\)\\in S, we can reformulate it asℒ​\(W\)=f​\(πS​\(W\)\)\\mathcal\{L\}\(W\)=f\(\\pi\_\{S\}\(W\)\)whereπS​\(W\)=\(Wj​k\)\(j,k\)∈S\\pi\_\{S\}\(W\)=\(W\_\{jk\}\)\_\{\(j,k\)\\in S\}extracts the entries indexed bySSandf​\(z\)=∑\(j,k\)∈S\(zj​k−yj​k\)22​τj​k2f\(z\)=\\sum\_\{\(j,k\)\\in S\}\\frac\{\(z\_\{jk\}\-y\_\{jk\}\)^\{2\}\}\{2\\tau\_\{jk\}^\{2\}\}for a vectorzzindexed bySS\. Then, by construction,

W^∈argminW⪰0ℒ\(W\)⇔πS\(W^\)∈argminz∈Zf\(z\),Z:=\{πS\(W\):W⪰0\}\.\\hat\{W\}\\in\\operatorname\*\{argmin\}\_\{W\\succeq 0\}\\mathcal\{L\}\(W\)\\quad\\iff\\pi\_\{S\}\(\\hat\{W\}\)\\in\\operatorname\*\{argmin\}\_\{z\\in Z\}f\(z\),\\quad Z:=\\\{\\pi\_\{S\}\(W\):W\\succeq 0\\\}\.The problem on the right\-hand side has a unique minimizeraabecausef​\(z\)f\(z\)is strictly convex andZZis convex\. ThereforeW^∈argminW⪰0ℒ​\(W\)\\hat\{W\}\\in\\operatorname\*\{argmin\}\_\{W\\succeq 0\}\\mathcal\{L\}\(W\)if and only ifπS​\(W^\)=a\\pi\_\{S\}\(\\hat\{W\}\)=a\. In other words, the set of minimizers ofℒ​\(W\)\\mathcal\{L\}\(W\)is exactly the set of PSD matrices whose entries inSSare equal toaa\.

The outer problem now becomes exactly Dempster’s covariance selection problem: find the PSD matrixΣ\\Sigmawith maximum entropy such thatΣj​k=aj​k\\Sigma\_\{jk\}=a\_\{jk\}for all\(j,k\)∈S\(j,k\)\\in S\. The result follows directly from Dempster’s*existence and uniqueness*property; the required condition that there is a positive definite matrixΣ\\SigmawithπS​\(Σ\)=a\\pi\_\{S\}\(\\Sigma\)=ais satisfied by our assumption thatargminWℒ​\(W\)\\operatorname\*\{argmin\}\_\{W\}\\mathcal\{L\}\(W\)contains a positive definite matrix and our characterization of this set\. ∎

### B\.2Discussion of ill posedness

In most literature on covariance selection there is little discussion of the problem being ill posed\. As Dempster showed, as long as there is*some*positive definite matrix matching the specified entries, the covariance selection problem has a unique solution\. Since the original empirical covariance matrix matches the specified entries, as long as this matrix is positive definite, the problem is well posed\.

The situation is significantly different with noisy observations\. To understand why, it is useful to consider the alternate characterization of the minimizers ofℒ​\(W\)\\mathcal\{L\}\(W\)in the proof of Proposition[4\.1](https://arxiv.org/html/2605.24295#S4.Thmtheorem1)\. The feasible setZ=\{πS​\(W\):W⪰0\}Z=\\\{\\pi\_\{S\}\(W\):W\\succeq 0\\\}is the set of all "PSD\-completable" vectorszz, i\.e\., those such that there is a PSD matrixWWwithπS​\(W\)=z\\pi\_\{S\}\(W\)=z\. This is a slice of the PSD cone and is also a convex cone\. \(See the closely related discussion of PSD\-completable matrices in\[[27](https://arxiv.org/html/2605.24295#bib.bib222)\]\.\) From the form of the objectiveff, we see that the operationa=argminz∈Zf​\(z\)a=\\operatorname\*\{argmin\}\_\{z\\in Z\}f\(z\)computes a coordinate\-scaledℓ2\\ell\_\{2\}projection ofyyontoZZ, wherey=πS​\(Σ\)\+noisey=\\pi\_\{S\}\(\\Sigma\)\+\\text\{noise\}\. If the noise scale is large enough, it is very likely thatyyfalls outsideZZ, in which case the projectionaawill lie on the boundary ofZZ\. A pointaaon the boundary is such that*every*WWwithπS​\(W\)=a\\pi\_\{S\}\(W\)=ais singular, meaning that every minimizer ofℒ​\(W\)\\mathcal\{L\}\(W\)is singular\. Thus, the reconstruction problem is ill posed: there is no unique solution, and all minimizers have entropy−∞\-\\infty\.

As a simple example, consider the case whenSScontains only indices of diagonal entries\. Thenaj​j=yj​j∨0a\_\{jj\}=y\_\{jj\}\\vee 0for alljj\. If anyyj​jy\_\{jj\}is negative we haveaj​j=0a\_\{jj\}=0, and every PSD matrix with this diagonal is singular\.

These considerations are largely resolved by our convention in Section[4\.4](https://arxiv.org/html/2605.24295#S4.SS4)of defining the solution as the limit of a sequence of entropy\-regularized solutions\. This gives the unique maximum\-entropy solution when the problem is well posed, and otherwise defines the desired solution in a princpled way through the sequence of regularized problems\.

### B\.3Inverse\-variance weighting for repeated measurements

###### Proof of Proposition[4\.2](https://arxiv.org/html/2605.24295#S4.Thmtheorem2)\.

The result follow from manipulating the obective to group terms by entry and then applying Lemma[B\.1](https://arxiv.org/html/2605.24295#A2.Thmtheorem1)below\.

ℒ​\(W\)\\displaystyle\\mathcal\{L\}\(W\)=∑t=1Tσt−2​\(Wjt​kt−zt\)2\\displaystyle=\\sum\_\{t=1\}^\{T\}\\sigma\_\{t\}^\{\-2\}\(W\_\{j\_\{t\}k\_\{t\}\}\-z\_\{t\}\)^\{2\}=∑\(j,k\)∑t∈𝕋j​kσt−2​\(Wj​k−zt\)2\\displaystyle=\\sum\_\{\(j,k\)\}\\sum\_\{t\\in\\mathbb\{T\}\_\{jk\}\}\\sigma\_\{t\}^\{\-2\}\(W\_\{jk\}\-z\_\{t\}\)^\{2\}=∑\(j,k\)λj​k​\(Wj​k−yj​k\)2\+C\\displaystyle=\\sum\_\{\(j,k\)\}\\lambda\_\{jk\}\(W\_\{jk\}\-y\_\{jk\}\)^\{2\}\+Cwhereλj​k=∑t∈𝕋j​kσt−2\\lambda\_\{jk\}=\\sum\_\{t\\in\\mathbb\{T\}\_\{jk\}\}\\sigma\_\{t\}^\{\-2\}andyj​k=1λj​k​∑t∈𝕋j​kσt−2​zty\_\{jk\}=\\frac\{1\}\{\\lambda\_\{jk\}\}\\sum\_\{t\\in\\mathbb\{T\}\_\{jk\}\}\\sigma\_\{t\}^\{\-2\}z\_\{t\}\. The final line uses Lemma[B\.1](https://arxiv.org/html/2605.24295#A2.Thmtheorem1)\. ∎

###### Lemma B\.1\.

∑qwq​\(x−aq\)2=\(∑qwq\)​\(x−a¯\)2\+C\\sum\_\{q\}w\_\{q\}\(x\-a\_\{q\}\)^\{2\}=\\big\(\\sum\_\{q\}w\_\{q\}\\big\)\(x\-\\bar\{a\}\)^\{2\}\+Cwherea¯:=∑qwq​aq∑qwq\\bar\{a\}:=\\frac\{\\sum\_\{q\}w\_\{q\}a\_\{q\}\}\{\\sum\_\{q\}w\_\{q\}\}andCCis constant with respect toxx\.

###### Proof\.

Expanding the left\-hand side:

∑qwq​\(x−aq\)2\\displaystyle\\sum\_\{q\}w\_\{q\}\(x\-a\_\{q\}\)^\{2\}=∑qwq​\(x2−2​x​aq\+aq2\)\\displaystyle=\\sum\_\{q\}w\_\{q\}\(x^\{2\}\-2xa\_\{q\}\+a\_\{q\}^\{2\}\)=x2​∑qwq−2​x​∑qwq​aq\+∑qwq​aq2\\displaystyle=x^\{2\}\\sum\_\{q\}w\_\{q\}\-2x\\sum\_\{q\}w\_\{q\}a\_\{q\}\+\\sum\_\{q\}w\_\{q\}a\_\{q\}^\{2\}=\(∑qwq\)​\(x2−2​x​∑qwq​aq∑qwq\+\(∑qwq​aq∑qwq\)2\)\\displaystyle=\\left\(\\sum\_\{q\}w\_\{q\}\\right\)\\left\(x^\{2\}\-2x\\frac\{\\sum\_\{q\}w\_\{q\}a\_\{q\}\}\{\\sum\_\{q\}w\_\{q\}\}\+\\left\(\\frac\{\\sum\_\{q\}w\_\{q\}a\_\{q\}\}\{\\sum\_\{q\}w\_\{q\}\}\\right\)^\{2\}\\right\)\+∑qwq​aq2−\(∑qwq​aq\)2∑qwq\\displaystyle\\quad\+\\sum\_\{q\}w\_\{q\}a\_\{q\}^\{2\}\-\\frac\{\(\\sum\_\{q\}w\_\{q\}a\_\{q\}\)^\{2\}\}\{\\sum\_\{q\}w\_\{q\}\}=\(∑qwq\)​\(x−a¯\)2\+C\\displaystyle=\\left\(\\sum\_\{q\}w\_\{q\}\\right\)\(x\-\\bar\{a\}\)^\{2\}\+Cwhere the constantC=∑qwq​aq2−\(∑qwq​aq\)2∑qwq=∑qwq​\(aq−a¯\)2C=\\sum\_\{q\}w\_\{q\}a\_\{q\}^\{2\}\-\\frac\{\(\\sum\_\{q\}w\_\{q\}a\_\{q\}\)^\{2\}\}\{\\sum\_\{q\}w\_\{q\}\}=\\sum\_\{q\}w\_\{q\}\(a\_\{q\}\-\\bar\{a\}\)^\{2\}is independent ofxx\. ∎

## Appendix CSolver

TheIPM\-Choleskysolver is outline in Algorithm[4](https://arxiv.org/html/2605.24295#alg4)\.

Algorithm 4IPM\-Cholesky1:Observations

Obs\\mathrm\{Obs\}, variances

Var\\mathrm\{Var\}, initial barrier

μ0\\mu\_\{0\}, reduction factor

cμc\_\{\\mu\}, minimum barrier

μmin\\mu\_\{\\min\}, initial

L0L\_\{0\}and

μ0\\mu\_\{0\}
2:Maximum\-entropy covariance estimate

Σ^\\hat\{\\Sigma\}
3:

μ←μ0\\mu\\leftarrow\\mu\_\{0\}
4:while

μ\>μmin\\mu\>\\mu\_\{\\min\}do

5:Set tolerance

tol​\(μ\)\\text\{tol\}\(\\mu\)⊳\\trianglerightCoarser early, finer nearμmin\\mu\_\{\\min\}

6:

L←L\-BFGS\-B​\(φμ,L\)L\\leftarrow\\textsc\{L\-BFGS\-B\}\\left\(\\varphi\_\{\\mu\},\\,L\\right\)with tolerance

tol​\(μ\)\\text\{tol\}\(\\mu\)
7:

μ←cμ⋅μ\\mu\\leftarrow c\_\{\\mu\}\\cdot\\mu
8:endwhile

9:return

Σ^←L​L⊤\\hat\{\\Sigma\}\\leftarrow LL^\{\\top\}

## Appendix DDatasets

We evaluatePACE\-GGMon fourteen real\-world tabular numerical datasets spanning a wide range of dimensions and correlation structures:

- •Adult\(d=6d=6\)\[[3](https://arxiv.org/html/2605.24295#bib.bib212)\]
- •SeoulBike\(d=10d=10\)\[[25](https://arxiv.org/html/2605.24295#bib.bib214)\]
- •LifeExpectancy\(d=15d=15\)\[[23](https://arxiv.org/html/2605.24295#bib.bib215)\]
- •BreastCancerWisconsin\(d=32d=32\)\[[31](https://arxiv.org/html/2605.24295#bib.bib213)\]
- •CommunitiesAndCrime\(d=102d=102\)\[[24](https://arxiv.org/html/2605.24295#bib.bib216)\]
- •From the TALENT benchmark\[[32](https://arxiv.org/html/2605.24295#bib.bib217)\]:Parkinsons\(d=16d=16\),thyroid\_ann\(d=21d=21\),ibm\(d=23d=23\),pol\_reg\(d=26d=26\),bank32nh\(d=32d=32\),ailerons\(d=33d=33\),spambase\(d=57d=57\),indian\_pines\(d=187d=187\),madeline\(d=260d=260\)

Table 3:Dataset properties\.\|r\|¯\\bar\{\|r\|\}: mean absolute pairwise correlation\.max⁡\|r\|\\max\|r\|: maximum absolute pairwise correlation\.eoff=‖Σoff‖F2/‖Σ‖F2e\_\{\\mathrm\{off\}\}=\\\|\\Sigma\_\{\\mathrm\{off\}\}\\\|\_\{F\}^\{2\}/\\\|\\Sigma\\\|\_\{F\}^\{2\}: fraction of covariance energy contained in the off\-diagonal entries\.rankeff\\mathrm\{rank\}\_\{\\mathrm\{eff\}\}: effective rankexp⁡\(−∑ipi​log⁡pi\)\\exp\\\!\\left\(\-\\sum\_\{i\}p\_\{i\}\\log p\_\{i\}\\right\)ofΣ\\Sigma, wherepi=νi/∑jνjp\_\{i\}=\\nu\_\{i\}/\\sum\_\{j\}\\nu\_\{j\}and\{νi\}\\\{\\nu\_\{i\}\\\}are the eigenvalues ofΣ\\Sigma\.
## Appendix EComplete results

In this Section, we show results for add datasets, and include comparison to an independent baseline that spends all privacy budget to release the diagonal but ignores off\-diagonal correlations\. This baseline tends to perform well only in cases where the covariance is nearly diagonal, without dense off\-diagonal structure\.

![Refer to caption](https://arxiv.org/html/2605.24295v1/x2.png)

![Refer to caption](https://arxiv.org/html/2605.24295v1/x3.png)

![Refer to caption](https://arxiv.org/html/2605.24295v1/x4.png)

Figure 2:Mahalanobis error \(top row\) and Frobenius error \(bottom row\) for all datasets\.PACE\-GGMand baselines across privacy budgetsρ\\rho, withα=0\.3\\alpha=0\.3,β=0\.5\\beta=0\.5\. Datasets are ordered by dimensionalityddacross three groups\.### E\.1Number of measurements

Table[4](https://arxiv.org/html/2605.24295#A5.T4)shows the average number of measured entries for all datasets andρ\\rhovalues\.

Table 4:Mean number of measurements per trial \(diagonal\+\+off\-diagonal\)\. The columnd​\(d\+1\)/2d\(d\+1\)/2gives the total number of unique entries in the covariance matrix \(the maximum possible number of measurements\)\.

## Appendix FSolver Findings

At each round, the privacy budget is allocated over a subset of variable pairs, defining a*measurement graph*with one node per variable and one edge per observed covariance entryΣj​k\\Sigma\_\{jk\}\. The PSD reconstruction is then solved over this graph\.

We study two aspects of the solver: \(i\) the choice of optimization method, and \(ii\) the use of sparsity via connected components\.

#### IPM vs\. PGD\.

We compare our maximum\-entropy formulation, solved via an interior\-point method \(IPM\), to projected gradient descent \(PGD\) applied directly to the PSD projection problem\. PGD requires initialization for unobserved entries of the precision matrix; we consider two simple strategies: filling these entries with0or11\.

Figure[3](https://arxiv.org/html/2605.24295#A6.F3)shows that PGD is highly sensitive to initialization\. While zero\-initialization yields performance comparable to IPM, one\-initialization overall leads to increased error and runtime, particularly in higher dimensions\. In contrast, IPM consistently converges to a stable solution without requiring initialization tuning\. This supports our use of the maximum\-entropy objective as a principled and robust reconstruction method\.

#### Connected components\.

When the measurement graph is disconnected, the PSD reconstruction decomposes exactly across connected components\. If the graph consists of components of sizes\{di\}\\\{d\_\{i\}\\\}, the computational cost reduces fromO​\(d3\)O\(d^\{3\}\)toO​\(∑idi3\)O\\\!\\left\(\\sum\_\{i\}d\_\{i\}^\{3\}\\right\), without approximation\.

Figure[4](https://arxiv.org/html/2605.24295#A6.F4)shows that leveraging connected components yields identical estimation error while consistently reducing runtime\.

Based on these findings, we use IPM with connected components as the default solver in all experiments\.

![Refer to caption](https://arxiv.org/html/2605.24295v1/x5.png)Figure 3:Solver: IPM vs\. PGD across five datasets\. Each column is a dataset ordered by dimension \(d=6d=6tod=102d=102\)\.Top two rows: Mahalanobis and Frobenius covariance estimation error \(mean±\\pmstd over 10 trials\) as a function of the privacy budgetρ\\rho\. PGD’s performance is dependent on initialization, while IPM’s maximum\-entropy approach converges reliably without need for initialization tuning\.Bottom row: total solver time per run \(seconds\)\. IPM is consistently fast and stable across all budgets and dimensions, and we use it as the default solver throughout\.![Refer to caption](https://arxiv.org/html/2605.24295v1/x6.png)Figure 4:Solver: IPM without connected components \(no CC\) vs\. IPM with connected components \(CC\) across five datasets\. Each column is a dataset ordered by dimension \(d=6d=6tod=102d=102\)\.Top two rows: Mahalanobis and Frobenius covariance estimation error \(mean±\\pmstd over 10 trials\) as a function of the privacy budgetρ\\rho\. The two approaches yield the same performance, with the connected components feature allowing runtime speedup by leveraging sparsity of the measurement graph\.

## Appendix GRegression

As an application, we evaluatePACE\-GGMfor linear regression\. We compare againstAdaSSP\[[29](https://arxiv.org/html/2605.24295#bib.bib83)\], a widely used baseline that appliesSSPto privately estimate the sufficient statisticsX⊤​XX^\{\\top\}XandX⊤​yX^\{\\top\}y, and allocates part of the privacy budget to estimating the minimum eigenvalue for regularization\. To ensure a fair comparison, we follow the same budget allocation strategy, reserving one third of the budget for regularization\. However, instead of estimating sufficient statistics viaSSP, we derive them from the covariance matrix produced byPACE\-GGM\. A 80/20 train\-test split is adopted for evaluation\. Figure[5](https://arxiv.org/html/2605.24295#A7.F5)reports results on eight regression datasets\.PACE\-GGMachieves competitive performance withAdaSSP, in most cases slightly outperforming it, while remaining a more general\-purpose method, as it targets covariance estimation rather than a specific downstream task\.

![Refer to caption](https://arxiv.org/html/2605.24295v1/x7.png)Figure 5:Mean square error \(MSE\) ofPACE\-GGMandAdaSSP, acrossρ\\rhovalues ranging from10−410^\{\-4\}to1010\. Standard error bars are computed across 10 independent trials\.
## Appendix HRuntime

Table[5](https://arxiv.org/html/2605.24295#A8.T5)reports mean total runtime per trial across all datasets and privacy budgets\. For low\-to\-medium dimensional datasets \(d≤57d\\leq 57\), runtimes are well under 3 seconds even atρ=10\\rho=10, confirming thatPACE\-GGMis practical across the full budget range\. Runtime grows with bothddandρ\\rho: largerρ\\rhomeans more budget to spend, so the algorithm runs more rounds and measures more entries before terminating\. This interaction betweenddandρ\\rhois not monotone inddalone —madeline\(d=260d=260\) is paradoxically fast because its covariance is nearly diagonal \(mean\|r\|=0\.016\|r\|=0\.016, effective rankrankeff=201\\text\{rank\}\_\{\\mathrm\{eff\}\}=201\), and the algorithm terminates after very few rounds\.indian\_pines\(d=187d=187\), by contrast, is highly correlated \(rankeff=2\.6\\text\{rank\}\_\{\\mathrm\{eff\}\}=2\.6\), driving runtimes of thousands of seconds at highρ\\rhoas many pairs remain informative across many rounds\. All experiments were run on a machine with an Apple M\-series processor \(10\-core CPU, 10\-core GPU, 16\-core Neural Engine\), 32 GB of unified memory, and 256 GB SSD storage\.

Table 5:Mean total trial time \(seconds\)±\\pmSE across 10 trials for selectedρ\\rhovalues\.
## Appendix IHyperparametersα\\alphaandβ\\beta

In this Section we study hyperparametersα∈\(0,1\)\\alpha\\in\(0,1\), the fraction ofρ\\rhoreserved for diagonal initialization, andβ∈\(0,1\)\\beta\\in\(0,1\), the fraction of the per\-round budget allocated to the exponential\-mechanism selection step\. We evaluate all nine combinations\(α,β\)∈\{0\.1,0\.3,0\.5\}2\(\\alpha,\\beta\)\\in\\\{0\.1,0\.3,0\.5\\\}^\{2\}on five datasets \(Adult,LifeExpectancy,IBM,Bank32nh,Spambase\) acrossρ∈\{10−4,10−3,10−2,0\.1,1,2,10\}\\rho\\in\\\{10^\{\-4\},10^\{\-3\},10^\{\-2\},0\.1,1,2,10\\\}with five trials per setting\. Results are in Tables[6](https://arxiv.org/html/2605.24295#A9.T6)–[7](https://arxiv.org/html/2605.24295#A9.T7)\.

Effect ofα\\alpha\.The optimal diagonal budget fraction exhibits interpretable dependence onρ\\rho, consistent with the theoretical role of each phase\. At low budgets \(ρ≤10−3\\rho\\leq 10^\{\-3\}\),α=0\.5\\alpha=0\.5wins in 8/10 cells: when measurements are highly noisy, a well\-conditioned diagonal initialization prevents wasted budget on near\-zero off\-diagonal entries\. At higher budgets \(ρ≥0\.1\\rho\\geq 0\.1\),α=0\.3\\alpha=0\.3dominates for Mahalanobis error, reflecting that off\-diagonal structure becomes resolvable and warrants more investment\. This budget\-regime dependence is exactly what one would expect from the algorithm’s design\. We setα=0\.3\\alpha=0\.3as the default, as Mahalanobis error better captures accuracy for downstream inference\.

Effect ofβ\\beta\.The results confirm the core design intuition: accurate entry selection is critical\.β=0\.5\\beta=0\.5achieves the lowest Frobenius error in 25/35 dataset×ρ\\times\\rhocells and 14/20 in the high\-budget regimeρ∈\{0\.1,1,2,10\}\\rho\\in\\\{0\.1,1,2,10\\\};\(α=0\.3,β=0\.5\)\(\\alpha\{=\}0\.3,\\,\\beta\{=\}0\.5\)is the single most frequent Mahalanobis winner with 13/35 cells\. Investing half the per\-round budget in selection consistently pays off\. We fixβ=0\.5\\beta=0\.5for all main experiments\.

Robustness to hyperparameter choice\.Crucially, performance is not sensitive to the exact choice of\(α,β\)\(\\alpha,\\beta\): all combinations in\(α,β\)∈\{0\.1,0\.3,0\.5\}2\(\\alpha,\\beta\)\\in\\\{0\.1,0\.3,0\.5\\\}^\{2\}remain competitive across datasets and privacy budgets\. Figure[6](https://arxiv.org/html/2605.24295#A9.F6)showsPACE\-GGM’s performance under all combinations of hyperparametersα\\alphaandβ\\beta, highlighting only a modest change in performance across datasets andρ\\rho\. This robustness is practically significant — it means the algorithm does not require careful tuning or dedicated hyperparameter search privacy budget\. The default\(α=0\.3,β=0\.5\)\(\\alpha\{=\}0\.3,\\,\\beta\{=\}0\.5\)is a reliable choice across diverse settings\.

Table 6:Frobenius error\. Best\(α,β\)\(\\alpha,\\beta\)pair per dataset andρ\\rho\(5 trials each\)\. Top winning combinations by count:\(0\.1,0\.5\)\(0\.1,0\.5\): 12;\(0\.5,0\.5\)\(0\.5,0\.5\): 7;\(0\.3,0\.5\)\(0\.3,0\.5\): 6\.Table 7:Mahalanobis error\. Best\(α,β\)\(\\alpha,\\beta\)pair per dataset andρ\\rho\(5 trials each\)\. Top winning combinations by count:\(0\.3,0\.5\)\(0\.3,0\.5\): 13;\(0\.5,0\.3\)\(0\.5,0\.3\): 4;\(0\.5,0\.1\)\(0\.5,0\.1\): 4\.![Refer to caption](https://arxiv.org/html/2605.24295v1/x8.png)Figure 6:PACE\-GGMerror under all nine combinations of\(α,β\)∈\{0\.1,0\.3,0\.5\}2\(\\alpha,\\beta\)\\in\\\{0\.1,0\.3,0\.5\\\}^\{2\}\.SSPis included as a baseline for reference\. The performance is robust to the choice ofα\\alphaandβ\\beta, with minimal performance changes\.