Differentially Private Range Queries with Correlated Input Perturbation

• URL: http://arxiv.org/abs/2402.07066v2
• Date: Wed, 06 Nov 2024 21:48:57 GMT
• Title: Differentially Private Range Queries with Correlated Input Perturbation
• Authors: Prathamesh Dharangutte, Jie Gao, Ruobin Gong, Guanyang Wang,
• Abstract summary: We propose a class of differentially private mechanisms for linear queries that leverage correlated input perturbations to achieve unbiasedness, consistency, statistical transparency, and control over utility requirements. Our theoretical and empirical analysis demonstrates that we achieve near-optimal utility, effectively compete with other methods, and retain all the favorable statistical properties discussed earlier.
• Score: 9.169888822435757
• License:
• Abstract: This work proposes a class of differentially private mechanisms for linear queries, in particular range queries, that leverages correlated input perturbation to simultaneously achieve unbiasedness, consistency, statistical transparency, and control over utility requirements in terms of accuracy targets expressed either in certain query margins or as implied by the hierarchical database structure. The proposed Cascade Sampling algorithm instantiates the mechanism exactly and efficiently. Our theoretical and empirical analysis demonstrates that we achieve near-optimal utility, effectively compete with other methods, and retain all the favorable statistical properties discussed earlier.

Related papers

• Generalization Bounds of Surrogate Policies for Combinatorial Optimization Problems [61.580419063416734]
  A recent stream of structured learning approaches has improved the practical state of the art for a range of optimization problems. The key idea is to exploit the statistical distribution over instances instead of dealing with instances separately. In this article, we investigate methods that smooth the risk by perturbing the policy, which eases optimization and improves the generalization error.
  arXiv  Detail & Related papers  (2024-07-24T12:00:30Z)
• Detecting and Identifying Selection Structure in Sequential Data [53.24493902162797]
  We argue that the selective inclusion of data points based on latent objectives is common in practical situations, such as music sequences. We show that selection structure is identifiable without any parametric assumptions or interventional experiments. We also propose a provably correct algorithm to detect and identify selection structures as well as other types of dependencies.
  arXiv  Detail & Related papers  (2024-06-29T20:56:34Z)
• Deriving Causal Order from Single-Variable Interventions: Guarantees & Algorithm [14.980926991441345]
  We show that datasets containing interventional data can be effectively extracted under realistic assumptions about the data distribution. We introduce interventional faithfulness, which relies on comparisons between the marginal distributions of each variable across observational and interventional settings. We also introduce Intersort, an algorithm designed to infer the causal order from datasets containing large numbers of single-variable interventions.
  arXiv  Detail & Related papers  (2024-05-28T16:07:17Z)
• Borrowing Strength in Distributionally Robust Optimization via Hierarchical Dirichlet Processes [35.53901341372684]
  Our approach unifies regularized estimation, distributionally robust optimization, and hierarchical Bayesian modeling. By employing a hierarchical Dirichlet process (HDP) prior, the method effectively handles multi-source data. Numerical experiments validate the framework's efficacy in improving and stabilizing both prediction and parameter estimation accuracy.
  arXiv  Detail & Related papers  (2024-05-21T19:03:09Z)
• Quantized Hierarchical Federated Learning: A Robust Approach to Statistical Heterogeneity [3.8798345704175534]
  We present a novel hierarchical federated learning algorithm that incorporates quantization for communication-efficiency. We offer a comprehensive analytical framework to evaluate its optimality gap and convergence rate. Our findings reveal that our algorithm consistently achieves high learning accuracy over a range of parameters.
  arXiv  Detail & Related papers  (2024-03-03T15:40:24Z)
• Instance-Specific Asymmetric Sensitivity in Differential Privacy [2.855485723554975]
  We build upon previous work that gives a paradigm for selecting an output through the exponential mechanism. Our framework will slightly modify the closeness metric and instead give a simple and efficient application of the sparse vector technique.
  arXiv  Detail & Related papers  (2023-11-02T05:01:45Z)
• HyperImpute: Generalized Iterative Imputation with Automatic Model Selection [77.86861638371926]
  We propose a generalized iterative imputation framework for adaptively and automatically configuring column-wise models. We provide a concrete implementation with out-of-the-box learners, simulators, and interfaces.
  arXiv  Detail & Related papers  (2022-06-15T19:10:35Z)
• Scalable Intervention Target Estimation in Linear Models [52.60799340056917]
  Current approaches to causal structure learning either work with known intervention targets or use hypothesis testing to discover the unknown intervention targets. This paper proposes a scalable and efficient algorithm that consistently identifies all intervention targets. The proposed algorithm can be used to also update a given observational Markov equivalence class into the interventional Markov equivalence class.
  arXiv  Detail & Related papers  (2021-11-15T03:16:56Z)
• Combining Task Predictors via Enhancing Joint Predictability [53.46348489300652]
  We present a new predictor combination algorithm that improves the target by i) measuring the relevance of references based on their capabilities in predicting the target, and ii) strengthening such estimated relevance. Our algorithm jointly assesses the relevance of all references by adopting a Bayesian framework. Based on experiments on seven real-world datasets from visual attribute ranking and multi-class classification scenarios, we demonstrate that our algorithm offers a significant performance gain and broadens the application range of existing predictor combination approaches.
  arXiv  Detail & Related papers  (2020-07-15T21:58:39Z)
• Causal Feature Selection for Algorithmic Fairness [61.767399505764736]
  We consider fairness in the integration component of data management. We propose an approach to identify a sub-collection of features that ensure the fairness of the dataset.
  arXiv  Detail & Related papers  (2020-06-10T20:20:10Z)

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.