On Improving the Composition Privacy Loss in Differential Privacy for Fixed Estimation Error

• URL: http://arxiv.org/abs/2405.06261v4
• Date: Tue, 25 Mar 2025 06:08:30 GMT
• Title: On Improving the Composition Privacy Loss in Differential Privacy for Fixed Estimation Error
• Authors: V. Arvind Rameshwar, Anshoo Tandon,
• Abstract summary: We consider the private release of statistics of disjoint subsets of a dataset, where users could contribute more than one sample.<n>In particular, we focus on the $epsilon$-differentially private release of sample means and variances of sample values in disjoint subsets of a dataset.<n>Our main contribution is an iterative algorithm, based on suppressing user contributions, which seeks to reduce the overall privacy loss degradation.
• Score: 4.809236881780709
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: This paper considers the private release of statistics of disjoint subsets of a dataset, in the setting of data heterogeneity, where users could contribute more than one sample, with different users contributing potentially different numbers of samples. In particular, we focus on the $\epsilon$-differentially private release of sample means and variances of sample values in disjoint subsets of a dataset, under the assumption that the numbers of contributions of each user in each subset is publicly known. Our main contribution is an iterative algorithm, based on suppressing user contributions, which seeks to reduce the overall privacy loss degradation under a canonical Laplace mechanism, while not increasing the worst estimation error among the subsets. Important components of this analysis are our exact, analytical characterizations of the sensitivities and the worst-case bias errors of estimators of the sample mean and variance, which are obtained by clipping or suppressing user contributions. We test the performance of our algorithm on real-world and synthetic datasets and demonstrate clear improvements in the privacy loss degradation, for fixed worst-case estimation error.

Related papers

• Privacy for Free: Leveraging Local Differential Privacy Perturbed Data from Multiple Services [10.822843258077997]
  Local Differential Privacy (LDP) has emerged as a widely adopted privacy-preserving technique in modern data analytics. This paper proposes a framework for collecting and aggregating data based on perturbed information from multiple services.
  arXiv  Detail & Related papers  (2025-03-11T11:10:03Z)
• Improved subsample-and-aggregate via the private modified winsorized mean [0.0]
  We show that the modified winsorized mean is minimax optimal for several, large classes of distributions. We consider the modified winsorized mean as the aggregator in subsample-and-aggregate.
  arXiv  Detail & Related papers  (2025-01-23T21:03:40Z)
• Error Feedback under $(L_0,L_1)$-Smoothness: Normalization and Momentum [56.37522020675243]
  We provide the first proof of convergence for normalized error feedback algorithms across a wide range of machine learning problems. We show that due to their larger allowable stepsizes, our new normalized error feedback algorithms outperform their non-normalized counterparts on various tasks.
  arXiv  Detail & Related papers  (2024-10-22T10:19:27Z)
• Empirical Mean and Frequency Estimation Under Heterogeneous Privacy: A Worst-Case Analysis [5.755004576310333]
  Differential Privacy (DP) is the current gold-standard for measuring privacy. We consider the problems of empirical mean estimation for univariate data and frequency estimation for categorical data, subject to heterogeneous privacy constraints. We prove some optimality results, under both PAC error and mean-squared error, for our proposed algorithms and demonstrate superior performance over other baseline techniques experimentally.
  arXiv  Detail & Related papers  (2024-07-15T22:46:02Z)
• AAA: an Adaptive Mechanism for Locally Differential Private Mean Estimation [42.95927712062214]
  Local differential privacy (LDP) is a strong privacy standard that has been adopted by popular software systems. We propose the advanced adaptive additive (AAA) mechanism, which is a distribution-aware approach that addresses the average utility. We provide rigorous privacy proofs, utility analyses, and extensive experiments comparing AAA with state-of-the-art mechanisms.
  arXiv  Detail & Related papers  (2024-04-02T04:22:07Z)
• Bounded and Unbiased Composite Differential Privacy [25.427802467876248]
  The objective of differential privacy (DP) is to protect privacy by producing an output distribution that is indistinguishable between two neighboring databases. Existing solutions attempt to address this issue by employing post-processing or truncation techniques. We propose a novel differentially private mechanism which uses a composite probability density function to generate bounded and unbiased outputs.
  arXiv  Detail & Related papers  (2023-11-04T04:43:47Z)
• Mean Estimation with User-level Privacy under Data Heterogeneity [54.07947274508013]
  Different users may possess vastly different numbers of data points. It cannot be assumed that all users sample from the same underlying distribution. We propose a simple model of heterogeneous user data that allows user data to differ in both distribution and quantity of data.
  arXiv  Detail & Related papers  (2023-07-28T23:02:39Z)
• Data Analytics with Differential Privacy [0.0]
  We develop differentially private algorithms to analyze distributed and streaming data. In the distributed model, we consider the particular problem of learning -- in a distributed fashion -- a global model of the data. We offer one of the strongest privacy guarantees for the streaming model, user-level pan-privacy.
  arXiv  Detail & Related papers  (2023-07-20T17:43:29Z)
• Correcting Underrepresentation and Intersectional Bias for Classification [49.1574468325115]
  We consider the problem of learning from data corrupted by underrepresentation bias. We show that with a small amount of unbiased data, we can efficiently estimate the group-wise drop-out rates. We show that our algorithm permits efficient learning for model classes of finite VC dimension.
  arXiv  Detail & Related papers  (2023-06-19T18:25:44Z)
• On the Privacy-Robustness-Utility Trilemma in Distributed Learning [7.778461949427662]
  We present the first tight analysis of the error incurred by any algorithm ensuring robustness against a fraction of adversarial machines. Our analysis exhibits a fundamental trade-off between privacy, robustness, and utility.
  arXiv  Detail & Related papers  (2023-02-09T17:24:18Z)
• Post-processing of Differentially Private Data: A Fairness Perspective [53.29035917495491]
  This paper shows that post-processing causes disparate impacts on individuals or groups. It analyzes two critical settings: the release of differentially private datasets and the use of such private datasets for downstream decisions. It proposes a novel post-processing mechanism that is (approximately) optimal under different fairness metrics.
  arXiv  Detail & Related papers  (2022-01-24T02:45:03Z)
• Calibrated Feature Decomposition for Generalizable Person Re-Identification [82.64133819313186]
  Calibrated Feature Decomposition (CFD) module focuses on improving the generalization capacity for person re-identification. A calibrated-and-standardized Batch normalization (CSBN) is designed to learn calibrated person representation.
  arXiv  Detail & Related papers  (2021-11-27T17:12:43Z)
• Private Alternating Least Squares: Practical Private Matrix Completion with Tighter Rates [34.023599653814415]
  We study the problem of differentially private (DP) matrix completion under user-level privacy. We design a joint differentially private variant of the popular Alternating-Least-Squares (ALS) method.
  arXiv  Detail & Related papers  (2021-07-20T23:19:11Z)
• Exploiting Sample Uncertainty for Domain Adaptive Person Re-Identification [137.9939571408506]
  We estimate and exploit the credibility of the assigned pseudo-label of each sample to alleviate the influence of noisy labels. Our uncertainty-guided optimization brings significant improvement and achieves the state-of-the-art performance on benchmark datasets.
  arXiv  Detail & Related papers  (2020-12-16T04:09:04Z)
• Graph-Homomorphic Perturbations for Private Decentralized Learning [64.26238893241322]
  Local exchange of estimates allows inference of data based on private data. perturbations chosen independently at every agent, resulting in a significant performance loss. We propose an alternative scheme, which constructs perturbations according to a particular nullspace condition, allowing them to be invisible.
  arXiv  Detail & Related papers  (2020-10-23T10:35:35Z)
• Accounting for Unobserved Confounding in Domain Generalization [107.0464488046289]
  This paper investigates the problem of learning robust, generalizable prediction models from a combination of datasets. Part of the challenge of learning robust models lies in the influence of unobserved confounders. We demonstrate the empirical performance of our approach on healthcare data from different modalities.
  arXiv  Detail & Related papers  (2020-07-21T08:18:06Z)
• Asymptotic Analysis of an Ensemble of Randomly Projected Linear Discriminants [94.46276668068327]
  In [1], an ensemble of randomly projected linear discriminants is used to classify datasets. We develop a consistent estimator of the misclassification probability as an alternative to the computationally-costly cross-validation estimator. We also demonstrate the use of our estimator for tuning the projection dimension on both real and synthetic data.
  arXiv  Detail & Related papers  (2020-04-17T12:47:04Z)

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.