More Like this

1. Efficient and Private Marginal Reconstruction with Local Non-Negativity

   Mullins, Brett; Fuentes, Miguel; Xiao, Yingtai; Kifer, Daniel; Musco, Cameron; Sheldon, Daniel (December 2025, 38th Conference on Neural Information Processing Systems (NeurIPS 2024).)

   Differential privacy is the dominant standard for formal and quantifiable privacy and has been used in major deployments that impact millions of people. Many differentially private algorithms for query release and synthetic data contain steps that reconstruct answers to queries from answers to other queries that have been measured privately. Reconstruction is an important subproblem for such mecha- nisms to economize the privacy budget, minimize error on reconstructed answers, and allow for scalability to high-dimensional datasets. In this paper, we introduce a principled and efficient postprocessing method ReM (Residuals-to-Marginals) for reconstructing answers to marginal queries. Our method builds on recent work on efficient mechanisms for marginal query release, based on making measurements using a residual query basis that admits efficient pseudoinversion, which is an important primitive used in reconstruction. An extension GReM-LNN (Gaussian Residuals-to-Marginals with Local Non-negativity) reconstructs marginals under Gaussian noise satisfying consistency and non-negativity, which often reduces error on reconstructed answers. We demonstrate the utility of ReM and GReM-LNN by applying them to improve existing private query answering mechanisms. 

   more » « less
2. ResidualPlanner+: a scalable matrix mechanism for marginals and beyond.

   He, Guanlin; Xiao, Yingtai; Toksoz, Levent; Ding, Zeyu; Zhang, Danfeng; Kifer, Daniel (April 2026, VLDB Journal)

   Noisy marginals are a common form of confi dentiality protecting data release and are useful for many downstream tasks such as contingency table analysis, construction of Bayesian networks, and even synthetic data generation. Matrix mechanisms, an important class of privacy mechanisms that provide unbiased noisy an swers to linear queries, are often used to answer marginal queries. We propose ResidualPlanner and ResidualPlanner+, two highly scalable matrix mechanisms. ResidualPlan ner is both optimal (among matrix mechanisms that use Gaussian noise) and scalable for answering marginal queries, while ResidualPlanner+ provides support for more general workloads, such as combinations of marginals and range queries or prefix-sum queries. ResidualPlanner can optimize for many loss functions that can be written as a convex function of marginal variances (prior work was restricted to just one predefined objective function). ResidualPlanner can optimize the accuracy of marginals in large scale settings in seconds, even when the previ ous state of the art (HDMM) runs out of memory. It even runs on datasets with 100 attributes in a couple of minutes. Furthermore, ResidualPlanner can efficiently compute variance/covariance values for each marginal (prior methods quickly run out of memory, even for relatively small datasets). ResidualPlanner+ provides support for more com plex workloads that combine marginal and range/prefix sum queries (e.g., a marginal on race, a range query on age, and a combined race/age tabulation that an swers age range queries for each race). It even supports custom user-defined workloads on different attributes. With this added flexibility, ResidualPlanner+ is not nec essarily optimal, however it is still extremely scalable and outperforms the prior state-of-the-art (HDMM) on prefix-sum queries both in terms of accuracy and speed. 

   more » « less
3. Differentially private low-dimensional synthetic data from high-dimensional datasets

   https://doi.org/10.1093/imaiai/iaae034  

   He, Yiyun; Strohmer, Thomas; Vershynin, Roman; Zhu, Yizhe (January 2025, Information and Inference: A Journal of the IMA)

   Differentially private synthetic data provide a powerful mechanism to enable data analysis while protecting sensitive information about individuals. However, when the data lie in a high-dimensional space, the accuracy of the synthetic data suffers from the curse of dimensionality. In this paper, we propose a differentially private algorithm to generate low-dimensional synthetic data efficiently from a high-dimensional dataset with a utility guarantee with respect to the Wasserstein distance. A key step of our algorithm is a private principal component analysis (PCA) procedure with a near-optimal accuracy bound that circumvents the curse of dimensionality. Unlike the standard perturbation analysis, our analysis of private PCA works without assuming the spectral gap for the covariance matrix. 

   more » « less
4. Graphical-model based estimation and inference for differential privacy

   McKenna, Ryan; Sheldon, Daniel; Miklau, Gerome (June 2019, Proceedings of Machine Learning Research)

   null (Ed.)

   Many privacy mechanisms reveal high-level information about a data distribution through noisy measurements. It is common to use this information to estimate the answers to new queries. In this work, we provide an approach to solve this estimation problem efficiently using graphical models, which is particularly effective when the distribution is high-dimensional but the measurements are over low-dimensional marginals. We show that our approach is far more efficient than existing estimation techniques from the privacy literature and that it can improve the accuracy and scalability of many state-of-the-art mechanisms. 

   more » « less
5. Recovering Joint PMF from Pairwise Marginals

   https://doi.org/10.1109/IEEECONF51394.2020.9443425  

   Ibrahim, Shahana; Fu, Xiao (November 2020, Asilomar Conference on Signals, Systems, and Computers)

   null (Ed.)

   To overcome the curse of dimensionality in joint probability learning, recent work has proposed to recover the joint probability mass function (PMF) of an arbitrary number of random variables (RVs) from three-dimensional marginals, exploiting the uniqueness of tensor decomposition and the (unknown) dependence among the RVs. Nonetheless, accurately estimating three-dimensional marginals is still costly in terms of sample complexity. Tensor decomposition also poses a computationally intensive optimization problem. This work puts forth a new framework that learns the joint PMF using pairwise marginals that are relatively easy to acquire. The method is built upon nonnegative matrix factorization (NMF) theory, and features a Gram–Schmidt-like economical algorithm that works provably well under realistic conditions. Theoretical analysis of a recently proposed expectation maximization (EM) algorithm for joint PMF recovery is also presented. In particular, the EM algorithm is shown to provably improve upon the proposed pairwise marginal-based approach. Synthetic and real-data experiments are employed to showcase the effectiveness of the proposed approach. 

   more » « less