Research map / Federated learning and privacy / Differential privacy

Private Adaptive Covariance Estimation via Gaussian Graphical Models

NeurIPS 2026 · Federated learning and privacy › Differential privacy · approach: Local-DP and private estimation · 0 citations (OpenAlex)

Read the paperCheck your idea against 108,967 papers

AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.

Proposes PACE-GGM, a zCDP covariance estimator that adaptively selects and privately measures poorly approximated covariance entries and reconstructs the matrix via maximum-entropy PSD reconstruction (Gaussian graphical model structure).

Problem

Differentially private covariance estimation under coordinate-wise bounds, where the full-matrix Gaussian mechanism spreads noise over all d(d+1)/2 entries.

Approach

Select-measure-reconstruct: the exponential mechanism picks the worst-approximated entry, the Gaussian mechanism measures it, and a maximum-entropy PSD reconstruction (covariance selection / GGM with sparse precision) fills in unmeasured entries; budget annealing adapts the number of rounds.

Key results

• PACE-GGM generally achieves lower Frobenius error than SSP across datasets and budgets, and often lower error than AdaptiveCov, especially at low rho and high d (as stated qualitatively).
• At rho=10, PACE-GGM measures 39 of 33,930 off-diagonal entries on madeline (d=260) and 12 of 15 on adult (d=6).
• On linear regression, PACE-GGM-derived sufficient statistics are competitive with AdaSSP, slightly outperforming it in most cases.

Surprising findings

• Diagonal-only baseline is competitive with PACE-GGM on nearly diagonal datasets.
• Projected gradient descent reconstruction is highly sensitive to initialization, while the maximum-entropy IPM is stable.

Limitations

• Assumes continuous data with coordinate-wise l_inf bounds; advantage vanishes if tight l2 bounds are known.
• Selection step is not fully private in the sense that hyperparameters/selection procedure is not fully private-tuned; no fully private hyperparameter selection provided.
• Per-round cost O(d^3) worst case; heavy-tailed data not evaluated.

Experimental setup

Datasets: Adult SeoulBike LifeExpectancy BreastCancerWisconsin CommunitiesAndCrime Parkinsons thyroid_ann ibm pol_reg bank32nh ailerons spambase

Benchmarks: Adult SeoulBike LifeExpectancy Parkinsons thyroid_ann ibm pol_reg BreastCancerWisconsin bank32nh ailerons spambase communities_crime

Metrics: Mahalanobis error Frobenius error runtime MSE (regression)

Baselines: SSP AdaptiveCov diagonal-only baseline AdaSSP

Builds on: AIM covariance selection (Dempster) AdaptiveCov AdaSSP

Closest papers by meaning

• Settling Pure Differentially Private Covariance Estimation (NeurIPS 2026 · similarity 0.91)
• Instance-Specific Asymmetric Sensitivity in Differential Privacy (NeurIPS 2024 · similarity 0.88)
• One-shot Empirical Privacy Estimation for Federated Learning (ICLR 2024 · similarity 0.87)
• Improved Communication-Privacy Trade-offs in $L_2$ Mean Estimation under Streaming Differential Privacy (ICML 2024 · similarity 0.87)
• Sampling-Free Privacy Accounting for Matrix Mechanisms under Random Allocation (NeurIPS 2026 · similarity 0.87)
• 𝑓-Differential Privacy Filters: Validity and Approximate Solutions (NeurIPS 2026 · similarity 0.87)