Multi-Analyst Differential Privacy for Online Query Answering

• URL: http://arxiv.org/abs/2212.09884v1
• Date: Mon, 19 Dec 2022 22:07:07 GMT
• Title: Multi-Analyst Differential Privacy for Online Query Answering
• Abstract summary: We extend previous work on multi-analyst differentially private query answering to the case of online query answering. We demonstrate that the unknown ordering of queries in the online case results in a fundamental limit in the number of queries that can be answered. In response, we develop two mechanisms, one which satisfies the desiderata in all cases but is subject to the fundamental limitations, and another that randomizes the input order ensuring that existing online query answering mechanisms can satisfy the desiderata.
• Score: 9.958631213800432
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: Most differentially private mechanisms are designed for the use of a single analyst. In reality, however, there are often multiple stakeholders with different and possibly conflicting priorities that must share the same privacy loss budget. This motivates the problem of equitable budget-sharing for multi-analyst differential privacy. Our previous work defined desiderata that any mechanism in this space should satisfy and introduced methods for budget-sharing in the offline case where queries are known in advance. We extend our previous work on multi-analyst differentially private query answering to the case of online query answering, where queries come in one at a time and must be answered without knowledge of the following queries. We demonstrate that the unknown ordering of queries in the online case results in a fundamental limit in the number of queries that can be answered while satisfying the desiderata. In response, we develop two mechanisms, one which satisfies the desiderata in all cases but is subject to the fundamental limitations, and another that randomizes the input order ensuring that existing online query answering mechanisms can satisfy the desiderata.

Related papers

• Multi-tier Differential Private Query Release [57.049084914202275]
  Multiple analysts may issue the same query, while receiving answers generated under different privacy budgets.<n>Existing approaches for such multi-tier DP queries either incur excessive cumulative privacy loss or suffer from suboptimal utility.<n>We propose a framework for multi-tier DP query release that simultaneously bound the cumulative privacy loss by the maximum privacy budget among all queries.
  arXiv  Detail & Related papers  (2026-06-14T02:10:22Z)
• LAPRAS : Learning-Augmented PRivate Answering for linear query Streams [9.706153384025809]
  We present LAPRAS, which assumes access to an oracle that outputs a prediction set of queries likely to appear in the stream.<n>LAPRAS answers predicted queries using the offline-optimal Matrix Mechanism and answers the remaining queries online from a residual budget.<n> Empirically, over two real datasets, we validate the intended consistency--robustness trade-off.
  arXiv  Detail & Related papers  (2026-05-03T16:46:53Z)
• Unified Mechanism-Specific Amplification by Subsampling and Group Privacy Amplification [54.1447806347273]
  Amplification by subsampling is one of the main primitives in machine learning with differential privacy. We propose the first general framework for deriving mechanism-specific guarantees. We analyze how subsampling affects the privacy of groups of multiple users.
  arXiv  Detail & Related papers  (2024-03-07T19:36:05Z)
• Adaptive Privacy Composition for Accuracy-first Mechanisms [55.53725113597539]
  Noise reduction mechanisms produce increasingly accurate answers. Analysts only pay the privacy cost of the least noisy or most accurate answer released. There has yet to be any study on how ex-post private mechanisms compose. We develop privacy filters that allow an analyst to adaptively switch between differentially private and ex-post private mechanisms.
  arXiv  Detail & Related papers  (2023-06-24T00:33:34Z)
• Federated Prompting and Chain-of-Thought Reasoning for Improving LLMs Answering [13.735277588793997]
  We investigate how to enhance answer precision in frequently asked questions posed by distributed users using cloud-based Large Language Models (LLMs) Our study focuses on a typical situations where users ask similar queries that involve identical mathematical reasoning steps and problem-solving procedures. We propose to improve the distributed synonymous questions using Self-Consistency (SC) and Chain-of-Thought (CoT) techniques.
  arXiv  Detail & Related papers  (2023-04-27T01:48:03Z)
• On Differential Privacy and Adaptive Data Analysis with Bounded Space [76.10334958368618]
  We study the space complexity of the two related fields of differential privacy and adaptive data analysis. We show that there exists a problem P that requires exponentially more space to be solved efficiently with differential privacy. The line of work on adaptive data analysis focuses on understanding the number of samples needed for answering a sequence of adaptive queries.
  arXiv  Detail & Related papers  (2023-02-11T14:45:31Z)
• Multi-Tenant Optimization For Few-Shot Task-Oriented FAQ Retrieval [0.0]
  Business-specific Frequently Asked Questions (FAQ) retrieval in task-oriented dialog systems poses unique challenges. We evaluate performance for such Business FAQ using query-Question (q-Q) similarity and few-shot intent detection techniques. We propose a novel approach to scale multi-tenant FAQ applications in real-world context by contrastive fine-tuning of the last layer in sentence Bi-Encoders along with tenant-specific weight switching.
  arXiv  Detail & Related papers  (2023-01-25T10:55:45Z)
• Diverse Multi-Answer Retrieval with Determinantal Point Processes [11.925050407713597]
  We propose a re-ranking based approach using Determinantal point processes utilizing BERT as kernels. Results demonstrate that our re-ranking technique outperforms state-of-the-art method on the AmbigQA dataset.
  arXiv  Detail & Related papers  (2022-11-29T08:54:05Z)
• 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)
• Interpretable by Design: Learning Predictors by Composing Interpretable Queries [8.054701719767293]
  We argue that machine learning algorithms should be interpretable by design. We minimize the expected number of queries needed for accurate prediction. Experiments on vision and NLP tasks demonstrate the efficacy of our approach.
  arXiv  Detail & Related papers  (2022-07-03T02:40:34Z)
• Session-Aware Query Auto-completion using Extreme Multi-label Ranking [61.753713147852125]
  We take the novel approach of modeling session-aware query auto-completion as an e Multi-Xtreme Ranking (XMR) problem. We adapt a popular XMR algorithm for this purpose by proposing several modifications to the key steps in the algorithm. Our approach meets the stringent latency requirements for auto-complete systems while leveraging session information in making suggestions.
  arXiv  Detail & Related papers  (2020-12-09T17:56:22Z)
• Public Bayesian Persuasion: Being Almost Optimal and Almost Persuasive [57.47546090379434]
  We study the public persuasion problem in the general setting with: (i) arbitrary state spaces; (ii) arbitrary action spaces; (iii) arbitrary sender's utility functions. We provide a quasi-polynomial time bi-criteria approximation algorithm for arbitrary public persuasion problems that, in specific settings, yields a QPTAS.
  arXiv  Detail & Related papers  (2020-02-12T18:59:18Z)

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.