Better Private Distribution Testing by Leveraging Unverified Auxiliary Data

• URL: http://arxiv.org/abs/2503.14709v1
• Date: Tue, 18 Mar 2025 20:17:20 GMT
• Title: Better Private Distribution Testing by Leveraging Unverified Auxiliary Data
• Authors: Maryam Aliakbarpour, Arnav Burudgunte, Clément Cannone, Ronitt Rubinfeld,
• Abstract summary: We extend the framework of augmented distribution testing to the differentially private setting.<n>This captures scenarios where a data analyst must perform hypothesis testing tasks on sensitive data.<n>We design private algorithms in this augmented setting for three flagship distribution testing tasks.
• Score: 5.494277056423046
• License: http://creativecommons.org/licenses/by-nc-nd/4.0/
• Abstract: We extend the framework of augmented distribution testing (Aliakbarpour, Indyk, Rubinfeld, and Silwal, NeurIPS 2024) to the differentially private setting. This captures scenarios where a data analyst must perform hypothesis testing tasks on sensitive data, but is able to leverage prior knowledge (public, but possibly erroneous or untrusted) about the data distribution. We design private algorithms in this augmented setting for three flagship distribution testing tasks, uniformity, identity, and closeness testing, whose sample complexity smoothly scales with the claimed quality of the auxiliary information. We complement our algorithms with information-theoretic lower bounds, showing that their sample complexity is optimal (up to logarithmic factors).

Related papers

• Optimal Algorithms for Augmented Testing of Discrete Distributions [25.818433126197036]
  We show that a predictor can indeed reduce the number of samples required for all three property testing tasks.<n>A key advantage of our algorithms is their adaptability to the precision of the prediction.<n>We provide lower bounds to indicate that the improvements in sample complexity achieved by our algorithms are information-theoretically optimal.
  arXiv  Detail & Related papers  (2024-12-01T21:31:22Z)
• Distributed, communication-efficient, and differentially private estimation of KL divergence [15.294136011320433]
  Key task in managing distributed, sensitive data is to measure the extent to which a distribution changes.<n>We describe novel algorithmic approaches for estimating the KL divergence of data across federated models of computation, under differential privacy.
  arXiv  Detail & Related papers  (2024-11-25T15:20:40Z)
• Federated Nonparametric Hypothesis Testing with Differential Privacy Constraints: Optimal Rates and Adaptive Tests [5.3595271893779906]
  Federated learning has attracted significant recent attention due to its applicability across a wide range of settings where data is collected and analyzed across disparate locations. We study federated nonparametric goodness-of-fit testing in the white-noise-with-drift model under distributed differential privacy (DP) constraints.
  arXiv  Detail & Related papers  (2024-06-10T19:25:19Z)
• Differentially Private Synthetic Data with Private Density Estimation [2.209921757303168]
  We adopt the framework of differential privacy, and explore mechanisms for generating an entire dataset. We build upon the work of Boedihardjo et al, which laid the foundations for a new optimization-based algorithm for generating private synthetic data.
  arXiv  Detail & Related papers  (2024-05-06T14:06:12Z)
• Diverse Data Augmentation with Diffusions for Effective Test-time Prompt Tuning [73.75282761503581]
  We propose DiffTPT, which leverages pre-trained diffusion models to generate diverse and informative new data. Our experiments on test datasets with distribution shifts and unseen categories demonstrate that DiffTPT improves the zero-shot accuracy by an average of 5.13%.
  arXiv  Detail & Related papers  (2023-08-11T09:36:31Z)
• 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)
• Private Set Generation with Discriminative Information [63.851085173614]
  Differentially private data generation is a promising solution to the data privacy challenge. Existing private generative models are struggling with the utility of synthetic samples. We introduce a simple yet effective method that greatly improves the sample utility of state-of-the-art approaches.
  arXiv  Detail & Related papers  (2022-11-07T10:02:55Z)
• Assaying Out-Of-Distribution Generalization in Transfer Learning [103.57862972967273]
  We take a unified view of previous work, highlighting message discrepancies that we address empirically. We fine-tune over 31k networks, from nine different architectures in the many- and few-shot setting.
  arXiv  Detail & Related papers  (2022-07-19T12:52:33Z)
• Generalization in the Face of Adaptivity: A Bayesian Perspective [3.0202264016476623]
  Repeated use of a data sample via adaptively chosen queries can rapidly lead to overfitting. It turns out that simple noise unbounded addition algorithms suffice to prevent this issue. We show that the harm of adaptivity results from the covariance between the new query and a Bayes factor-based measure of how much information about the data sample was encoded in the responses given to past queries.
  arXiv  Detail & Related papers  (2021-06-20T22:06:44Z)
• Learning while Respecting Privacy and Robustness to Distributional Uncertainties and Adversarial Data [66.78671826743884]
  The distributionally robust optimization framework is considered for training a parametric model. The objective is to endow the trained model with robustness against adversarially manipulated input data. Proposed algorithms offer robustness with little overhead.
  arXiv  Detail & Related papers  (2020-07-07T18:25:25Z)
• 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.