Minimax Optimal Two-Sample Testing under Local Differential Privacy

• URL: http://arxiv.org/abs/2411.09064v2
• Date: Fri, 22 Nov 2024 07:00:06 GMT
• Title: Minimax Optimal Two-Sample Testing under Local Differential Privacy
• Authors: Jongmin Mun, Seungwoo Kwak, Ilmun Kim,
• Abstract summary: 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.
• Score: 3.3317825075368908
• License:
• Abstract: We explore the trade-off between privacy and statistical utility in private two-sample testing under local differential privacy (LDP) for both multinomial and continuous data. We begin by addressing the multinomial case, where we introduce private permutation tests using practical privacy mechanisms such as Laplace, discrete Laplace, and Google's RAPPOR. We then extend our multinomial approach to continuous data via binning and study its uniform separation rates under LDP over H\"older and Besov smoothness classes. The proposed tests for both discrete and continuous cases rigorously control the type I error for any finite sample size, strictly adhere to LDP constraints, and achieve minimax separation rates under LDP. The attained minimax rates reveal inherent privacy-utility trade-offs that are unavoidable in private testing. To address scenarios with unknown smoothness parameters in density testing, we propose an adaptive test based on a Bonferroni-type approach that ensures robust performance without prior knowledge of the smoothness parameters. We validate our theoretical findings with extensive numerical experiments and demonstrate the practical relevance and effectiveness of our proposed methods.

Related papers

• Pseudo-Probability Unlearning: Towards Efficient and Privacy-Preserving Machine Unlearning [59.29849532966454]
  We propose PseudoProbability Unlearning (PPU), a novel method that enables models to forget data to adhere to privacy-preserving manner. Our method achieves over 20% improvements in forgetting error compared to the state-of-the-art.
  arXiv  Detail & Related papers  (2024-11-04T21:27:06Z)
• Private Language Models via Truncated Laplacian Mechanism [18.77713904999236]
  We propose a novel private embedding method called the high dimensional truncated Laplacian mechanism. We show that our method has a lower variance compared to the previous private word embedding methods. Remarkably, even in the high privacy regime, our approach only incurs a slight decrease in utility compared to the non-private scenario.
  arXiv  Detail & Related papers  (2024-10-10T15:25:02Z)
• 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)
• How Private are DP-SGD Implementations? [61.19794019914523]
  We show that there can be a substantial gap between the privacy analysis when using the two types of batch sampling. Our result shows that there can be a substantial gap between the privacy analysis when using the two types of batch sampling.
  arXiv  Detail & Related papers  (2024-03-26T13:02:43Z)
• Optimal Locally Private Nonparametric Classification with Public Data [2.631955426232593]
  We investigate the problem of public data assisted non-interactive Local Differentially Private (LDP) learning with a focus on non-parametric classification. Under the posterior drift assumption, we derive the mini-max optimal convergence rate with LDP constraint. We present a novel approach, the locally differentially private classification tree, which attains the mini-max optimal convergence rate.
  arXiv  Detail & Related papers  (2023-11-19T16:35:01Z)
• Differentially Private Federated Clustering over Non-IID Data [59.611244450530315]
  clustering clusters (FedC) problem aims to accurately partition unlabeled data samples distributed over massive clients into finite clients under the orchestration of a server. We propose a novel FedC algorithm using differential privacy convergence technique, referred to as DP-Fed, in which partial participation and multiple clients are also considered. Various attributes of the proposed DP-Fed are obtained through theoretical analyses of privacy protection, especially for the case of non-identically and independently distributed (non-i.i.d.) data.
  arXiv  Detail & Related papers  (2023-01-03T05:38:43Z)
• On the Statistical Complexity of Estimation and Testing under Privacy Constraints [17.04261371990489]
  We show how to characterize the power of a statistical test under differential privacy in a plug-and-play fashion. We show that maintaining privacy results in a noticeable reduction in performance only when the level of privacy protection is very high. Finally, we demonstrate that the DP-SGLD algorithm, a private convex solver, can be employed for maximum likelihood estimation with a high degree of confidence.
  arXiv  Detail & Related papers  (2022-10-05T12:55:53Z)
• Individual Privacy Accounting for Differentially Private Stochastic Gradient Descent [69.14164921515949]
  We characterize privacy guarantees for individual examples when releasing models trained by DP-SGD. We find that most examples enjoy stronger privacy guarantees than the worst-case bound. This implies groups that are underserved in terms of model utility simultaneously experience weaker privacy guarantees.
  arXiv  Detail & Related papers  (2022-06-06T13:49:37Z)
• A One-Pass Private Sketch for Most Machine Learning Tasks [48.17461258268463]
  Differential privacy (DP) is a compelling privacy definition that explains the privacy-utility tradeoff via formal, provable guarantees. We propose a private sketch that supports a multitude of machine learning tasks including regression, classification, density estimation, and more. Our sketch consists of randomized contingency tables that are indexed with locality-sensitive hashing and constructed with an efficient one-pass algorithm.
  arXiv  Detail & Related papers  (2020-06-16T17:47:48Z)
• Differentially Private Federated Learning with Laplacian Smoothing [72.85272874099644]
  Federated learning aims to protect data privacy by collaboratively learning a model without sharing private data among users. An adversary may still be able to infer the private training data by attacking the released model. Differential privacy provides a statistical protection against such attacks at the price of significantly degrading the accuracy or utility of the trained models.
  arXiv  Detail & Related papers  (2020-05-01T04:28:38Z)
• Minimax optimal goodness-of-fit testing for densities and multinomials under a local differential privacy constraint [3.265773263570237]
  We consider the consequences of local differential privacy constraints on goodness-of-fit testing. We present a test that is adaptive to the smoothness parameter of the unknown density and remains minimax optimal up to a logarithmic factor.
  arXiv  Detail & Related papers  (2020-02-11T08:41:05Z)

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.