AAA: an Adaptive Mechanism for Locally Differential Private Mean Estimation

• URL: http://arxiv.org/abs/2404.01625v2
• Date: Wed, 3 Apr 2024 06:31:26 GMT
• Title: AAA: an Adaptive Mechanism for Locally Differential Private Mean Estimation
• Authors: Fei Wei, Ergute Bao, Xiaokui Xiao, Yin Yang, Bolin Ding,
• Abstract summary: 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.
• Score: 42.95927712062214
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: Local differential privacy (LDP) is a strong privacy standard that has been adopted by popular software systems. The main idea is that each individual perturbs their own data locally, and only submits the resulting noisy version to a data aggregator. Although much effort has been devoted to computing various types of aggregates and building machine learning applications under LDP, research on fundamental perturbation mechanisms has not achieved significant improvement in recent years. Towards a more refined result utility, existing works mainly focus on improving the worst-case guarantee. However, this approach does not necessarily promise a better average performance given the fact that the data in practice obey a certain distribution, which is not known beforehand. In this paper, we propose the advanced adaptive additive (AAA) mechanism, which is a distribution-aware approach that addresses the average utility and tackles the classical mean estimation problem. AAA is carried out in a two-step approach: first, as the global data distribution is not available beforehand, the data aggregator selects a random subset of individuals to compute a (noisy) quantized data descriptor; then, the data aggregator collects data from the remaining individuals, which are perturbed in a distribution-aware fashion. The perturbation involved in the latter step is obtained by solving an optimization problem, which is formulated with the data descriptor obtained in the former step and the desired properties of task-determined utilities. We provide rigorous privacy proofs, utility analyses, and extensive experiments comparing AAA with state-of-the-art mechanisms. The evaluation results demonstrate that the AAA mechanism consistently outperforms existing solutions with a clear margin in terms of result utility, on a wide range of privacy constraints and real-world and synthetic datasets.

Related papers

• Stratified Prediction-Powered Inference for Hybrid Language Model Evaluation [62.2436697657307]
  Prediction-powered inference (PPI) is a method that improves statistical estimates based on limited human-labeled data. We propose a method called Stratified Prediction-Powered Inference (StratPPI) We show that the basic PPI estimates can be considerably improved by employing simple data stratification strategies.
  arXiv  Detail & Related papers  (2024-06-06T17:37:39Z)
• Multi-Source Conformal Inference Under Distribution Shift [41.701790856201036]
  We consider the problem of obtaining distribution-free prediction intervals for a target population, leveraging multiple potentially biased data sources. We derive the efficient influence functions for the quantiles of unobserved outcomes in the target and source populations. We propose a data-adaptive strategy to upweight informative data sources for efficiency gain and downweight non-informative data sources for bias reduction.
  arXiv  Detail & Related papers  (2024-05-15T13:33:09Z)
• Noise Variance Optimization in Differential Privacy: A Game-Theoretic Approach Through Per-Instance Differential Privacy [7.264378254137811]
  Differential privacy (DP) can measure privacy loss by observing the changes in the distribution caused by the inclusion of individuals in the target dataset. DP has been prominent in safeguarding datasets in machine learning in industry giants like Apple and Google. We propose per-instance DP (pDP) as a constraint, measuring privacy loss for each data instance and optimizing noise tailored to individual instances.
  arXiv  Detail & Related papers  (2024-04-24T06:51:16Z)
• Differentially Private Distributed Convex Optimization [0.0]
  In distributed optimization, multiple agents cooperate to minimize a global objective function, expressed as a sum of local objectives. Locally stored data are not shared with other agents, which could limit the practical usage of DO in applications with sensitive data. We propose a privacy-preserving DO algorithm for constrained convex optimization models.
  arXiv  Detail & Related papers  (2023-02-28T12:07:27Z)
• CADIS: Handling Cluster-skewed Non-IID Data in Federated Learning with Clustered Aggregation and Knowledge DIStilled Regularization [3.3711670942444014]
  Federated learning enables edge devices to train a global model collaboratively without exposing their data. We tackle a new type of Non-IID data, called cluster-skewed non-IID, discovered in actual data sets. We propose an aggregation scheme that guarantees equality between clusters.
  arXiv  Detail & Related papers  (2023-02-21T02:53:37Z)
• 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)
• MAPS: A Noise-Robust Progressive Learning Approach for Source-Free Domain Adaptive Keypoint Detection [76.97324120775475]
  Cross-domain keypoint detection methods always require accessing the source data during adaptation. This paper considers source-free domain adaptive keypoint detection, where only the well-trained source model is provided to the target domain.
  arXiv  Detail & Related papers  (2023-02-09T12:06:08Z)
• DRFLM: Distributionally Robust Federated Learning with Inter-client Noise via Local Mixup [58.894901088797376]
  federated learning has emerged as a promising approach for training a global model using data from multiple organizations without leaking their raw data. We propose a general framework to solve the above two challenges simultaneously. We provide comprehensive theoretical analysis including robustness analysis, convergence analysis, and generalization ability.
  arXiv  Detail & Related papers  (2022-04-16T08:08:29Z)
• Leveraging Unlabeled Data to Predict Out-of-Distribution Performance [63.740181251997306]
  Real-world machine learning deployments are characterized by mismatches between the source (training) and target (test) distributions. In this work, we investigate methods for predicting the target domain accuracy using only labeled source data and unlabeled target data. We propose Average Thresholded Confidence (ATC), a practical method that learns a threshold on the model's confidence, predicting accuracy as the fraction of unlabeled examples.
  arXiv  Detail & Related papers  (2022-01-11T23:01:12Z)
• 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)

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.