Differentially Private Permutation Tests: Applications to Kernel Methods

• URL: http://arxiv.org/abs/2310.19043v2
• Date: Mon, 8 Jan 2024 03:57:03 GMT
• Title: Differentially Private Permutation Tests: Applications to Kernel Methods
• Authors: Ilmun Kim and Antonin Schrab
• Abstract summary: differential privacy has emerged as a rigorous framework for privacy protection, gaining widespread recognition in both academic and industrial circles. This paper aims to alleviate concerns in the context of hypothesis testing by introducing differentially private permutation tests. The proposed framework extends classical non-private permutation tests to private settings, maintaining both finite-sample validity and differential privacy in a rigorous manner.
• Score: 7.596498528060537
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Recent years have witnessed growing concerns about the privacy of sensitive data. In response to these concerns, differential privacy has emerged as a rigorous framework for privacy protection, gaining widespread recognition in both academic and industrial circles. While substantial progress has been made in private data analysis, existing methods often suffer from impracticality or a significant loss of statistical efficiency. This paper aims to alleviate these concerns in the context of hypothesis testing by introducing differentially private permutation tests. The proposed framework extends classical non-private permutation tests to private settings, maintaining both finite-sample validity and differential privacy in a rigorous manner. The power of the proposed test depends on the choice of a test statistic, and we establish general conditions for consistency and non-asymptotic uniform power. To demonstrate the utility and practicality of our framework, we focus on reproducing kernel-based test statistics and introduce differentially private kernel tests for two-sample and independence testing: dpMMD and dpHSIC. The proposed kernel tests are straightforward to implement, applicable to various types of data, and attain minimax optimal power across different privacy regimes. Our empirical evaluations further highlight their competitive power under various synthetic and real-world scenarios, emphasizing their practical value. The code is publicly available to facilitate the implementation of our framework.

Related papers

• Minimax Optimal Two-Sample Testing under Local Differential Privacy [3.3317825075368908]
  We explore the trade-off between privacy and statistical utility in private two-sample testing under local differential privacy (LDP) We introduce private permutation tests using practical privacy mechanisms such as Laplace, discrete Laplace, and Google's RAPPOR. We study continuous data via binning and study its uniform separation rates under LDP over H"older and Besov smoothness classes.
  arXiv  Detail & Related papers  (2024-11-13T22:44:25Z)
• Masked Differential Privacy [64.32494202656801]
  We propose an effective approach called masked differential privacy (DP), which allows for controlling sensitive regions where differential privacy is applied. Our method operates selectively on data and allows for defining non-sensitive-temporal regions without DP application or combining differential privacy with other privacy techniques within data samples.
  arXiv  Detail & Related papers  (2024-10-22T15:22:53Z)
• A Statistical Viewpoint on Differential Privacy: Hypothesis Testing, Representation and Blackwell's Theorem [30.365274034429508]
  We argue that differential privacy can be considered a textitpure statistical concept. $f$-differential privacy is a unified framework for analyzing privacy bounds in data analysis and machine learning.
  arXiv  Detail & Related papers  (2024-09-14T23:47:22Z)
• Robust Kernel Hypothesis Testing under Data Corruption [6.430258446597413]
  We propose two general methods for constructing robust permutation tests under data corruption. We prove their consistency in power under minimal conditions. This contributes to the practical deployment of hypothesis tests for real-world applications with potential adversarial attacks.
  arXiv  Detail & Related papers  (2024-05-30T10:23:16Z)
• TernaryVote: Differentially Private, Communication Efficient, and Byzantine Resilient Distributed Optimization on Heterogeneous Data [50.797729676285876]
  We propose TernaryVote, which combines a ternary compressor and the majority vote mechanism to realize differential privacy, gradient compression, and Byzantine resilience simultaneously. We theoretically quantify the privacy guarantee through the lens of the emerging f-differential privacy (DP) and the Byzantine resilience of the proposed algorithm.
  arXiv  Detail & Related papers  (2024-02-16T16:41:14Z)
• Differentially private Bayesian tests [1.3127313002783776]
  We present a novel differentially private Bayesian hypotheses testing framework that arise naturally under a principled data generative mechanism. By focusing on differentially private Bayes factors based on widely used test statistics, we circumvent the need to model the complete data generative mechanism.
  arXiv  Detail & Related papers  (2024-01-27T21:07:11Z)
• Tight Auditing of Differentially Private Machine Learning [77.38590306275877]
  For private machine learning, existing auditing mechanisms are tight. They only give tight estimates under implausible worst-case assumptions. We design an improved auditing scheme that yields tight privacy estimates for natural (not adversarially crafted) datasets.
  arXiv  Detail & Related papers  (2023-02-15T21:40:33Z)
• Enforcing Privacy in Distributed Learning with Performance Guarantees [57.14673504239551]
  We study the privatization of distributed learning and optimization strategies. We show that the popular additive random perturbation scheme degrades performance because it is not well-tuned to the graph structure.
  arXiv  Detail & Related papers  (2023-01-16T13:03:27Z)
• Sequential Kernelized Independence Testing [101.22966794822084]
  We design sequential kernelized independence tests inspired by kernelized dependence measures. We demonstrate the power of our approaches on both simulated and real data.
  arXiv  Detail & Related papers  (2022-12-14T18:08:42Z)
• Private Sequential Hypothesis Testing for Statisticians: Privacy, Error Rates, and Sample Size [24.149533870085175]
  We study the sequential hypothesis testing problem under a slight variant of differential privacy, known as Renyi differential privacy. We present a new private algorithm based on Wald's Sequential Probability Ratio Test (SPRT) that also gives strong theoretical privacy guarantees.
  arXiv  Detail & Related papers  (2022-04-10T04:15:50Z)
• Debugging Differential Privacy: A Case Study for Privacy Auditing [60.87570714269048]
  We show that auditing can also be used to find flaws in (purportedly) differentially private schemes. In this case study, we audit a recent open source implementation of a differentially private deep learning algorithm and find, with 99.99999999% confidence, that the implementation does not satisfy the claimed differential privacy guarantee.
  arXiv  Detail & Related papers  (2022-02-24T17:31:08Z)

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.