Efficient and Private Marginal Reconstruction with Local Non-Negativity

• URL: http://arxiv.org/abs/2410.01091v1
• Date: Tue, 1 Oct 2024 21:39:28 GMT
• Title: Efficient and Private Marginal Reconstruction with Local Non-Negativity
• Authors: Brett Mullins, Miguel Fuentes, Yingtai Xiao, Daniel Kifer, Cameron Musco, Daniel Sheldon,
• Abstract summary: We introduce a principled and efficient postprocessing method ReM for reconstructing answers to marginal queries. An extension GReM-LNN reconstructs marginals under Gaussian noise satisfying consistency and non-negativity. We demonstrate the utility of ReM and GReM-LNN by applying them to improve existing private query answering mechanisms.
• Score: 28.968601257521644
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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 measured by the mechanism. Reconstruction is an important subproblem for such mechanisms 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: ResidualPlanner and MWEM.

Related papers

• RE-RAG: Improving Open-Domain QA Performance and Interpretability with Relevance Estimator in Retrieval-Augmented Generation [5.10832476049103]
  We propose a relevance estimator (RE) that provides relative relevance between contexts as previous rerankers did. We show that RE trained with a small generator (sLM) can not only improve the sLM fine-tuned together with RE but also improve previously unreferenced large language models.
  arXiv  Detail & Related papers  (2024-06-09T14:11:19Z)
• UGMAE: A Unified Framework for Graph Masked Autoencoders [67.75493040186859]
  We propose UGMAE, a unified framework for graph masked autoencoders. We first develop an adaptive feature mask generator to account for the unique significance of nodes. We then design a ranking-based structure reconstruction objective joint with feature reconstruction to capture holistic graph information.
  arXiv  Detail & Related papers  (2024-02-12T19:39:26Z)
• Self-RAG: Learning to Retrieve, Generate, and Critique through Self-Reflection [74.51523859064802]
  We introduce a new framework called Self-Reflective Retrieval-Augmented Generation (Self-RAG) Self-RAG enhances an LM's quality and factuality through retrieval and self-reflection. It significantly outperforms state-of-the-art LLMs and retrieval-augmented models on a diverse set of tasks.
  arXiv  Detail & Related papers  (2023-10-17T18:18:32Z)
• Subspace-Guided Feature Reconstruction for Unsupervised Anomaly Localization [5.085309164633571]
  Unsupervised anomaly localization plays a critical role in industrial manufacturing. Most recent methods perform feature matching or reconstruction for the target sample with pre-trained deep neural networks. We propose a novel subspace-guided feature reconstruction framework to pursue adaptive feature approximation for anomaly localization.
  arXiv  Detail & Related papers  (2023-09-25T06:58:57Z)
• Bounding data reconstruction attacks with the hypothesis testing interpretation of differential privacy [78.32404878825845]
  Reconstruction Robustness (ReRo) was recently proposed as an upper bound on the success of data reconstruction attacks against machine learning models. Previous research has demonstrated that differential privacy (DP) mechanisms also provide ReRo, but so far, only Monte Carlo estimates of a tight ReRo bound have been shown.
  arXiv  Detail & Related papers  (2023-07-08T08:02:47Z)
• Private Query Release via the Johnson-Lindenstrauss Transform [93.20051580730234]
  We introduce a new method for releasing answers to statistical queries with differential privacy. The key idea is to randomly project the query answers to a lower dimensional space. We answer the projected queries using a simple noise-adding mechanism, and lift the answers up to the original dimension.
  arXiv  Detail & Related papers  (2022-08-15T19:19:16Z)
• Relaxed Marginal Consistency for Differentially Private Query Answering [19.276819678442532]
  Private-PGM is a recent approach that uses graphical models to represent the data distribution. Private-PGM is highly scalable for sparse measurements, but may fail to run in high dimensions with dense measurements. We overcome the main limitation of Private-PGM through a principled approach that relaxes consistency constraints in the estimation objective.
  arXiv  Detail & Related papers  (2021-09-13T17:47:02Z)
• Differentially Private Query Release Through Adaptive Projection [19.449593001368193]
  We propose, implement, and evaluate a new algorithm for releasing answers to very large numbers of statistical queries like $k$-way marginals. Our algorithm makes adaptive use of a continuous relaxation of the Projection Mechanism, which answers queries on the private dataset using simple perturbation. We find that our method outperforms existing algorithms in many cases, especially when the privacy budget is small or the query class is large.
  arXiv  Detail & Related papers  (2021-03-11T12:43:18Z)
• Regularization-Agnostic Compressed Sensing MRI Reconstruction with Hypernetworks [21.349071909858218]
  We present a novel strategy of using a hypernetwork to generate the parameters of a separate reconstruction network as a function of the regularization weight(s) At test time, for a given under-sampled image, our model can rapidly compute reconstructions with different amounts of regularization. We analyze the variability of these reconstructions, especially in situations when the overall quality is similar.
  arXiv  Detail & Related papers  (2021-01-06T18:55:37Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)
• Modal Regression based Structured Low-rank Matrix Recovery for Multi-view Learning [70.57193072829288]
  Low-rank Multi-view Subspace Learning has shown great potential in cross-view classification in recent years. Existing LMvSL based methods are incapable of well handling view discrepancy and discriminancy simultaneously. We propose Structured Low-rank Matrix Recovery (SLMR), a unique method of effectively removing view discrepancy and improving discriminancy.
  arXiv  Detail & Related papers  (2020-03-22T03:57:38Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.