mlsanityData to 7 Oct 2026

Optimal and Differentially Private Data Acquisition: Central and Local Mechanisms

arXiv 2201.03968 ↗First posted 10 Jan 2022cs.GT cs.CR cs.LGcited by 22

Not on the map. Why?

Abstract (arXiv)

We consider a platform's problem of collecting data from privacy sensitive users to estimate an underlying parameter of interest. We formulate this question as a Bayesian-optimal mechanism design problem, in which an individual can share her (verifiable) data in exchange for a monetary reward or services, but at the same time has a (private) heterogeneous privacy cost which we quantify using differential privacy. We consider two popular differential privacy settings for providing privacy guarantees for the users: central and local. In both settings, we establish minimax lower bounds for the estimation error and derive (near) optimal estimators for given heterogeneous privacy loss levels for users. Building on this characterization, we pose the mechanism design problem as the optimal selection of an estimator and payments that will elicit truthful reporting of users' privacy sensitivities. Under a regularity condition on the distribution of privacy sensitivities we develop efficient algorithmic mechanisms to solve this problem in both privacy settings. Our mechanism in the central setting can be implemented in time O(n log n) where n is the number of users and our mechanism in the local setting admits a Polynomial Time Approximation Scheme (PTAS).

Key facts. Cited by 22 papers in the map (data through 7 Oct 2026). Builds on 23 of its 79 references that are in the map. First posted on arXiv 10 Jan 2022.

Builds on

23 of 79 references.

References · 23

  1. 2014RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Responsecited by 262
  2. 2017Collecting Telemetry Data Privatelycited by 147
  3. 2017Finite Sample Differentially Private Confidence Intervalscited by 103
  4. 2018Privately Learning High-Dimensional Distributionscited by 103
  5. 2020Private Mean Estimation of Heavy-Tailed Distributionscited by 73
  6. 2020Differentially Private Assouad, Fano, and Le Camcited by 54
  7. 2014Differential Privacy: An Economic Method for Choosing Epsiloncited by 34
  8. 2015Heterogeneous Differential Privacycited by 30
  9. 2021Generalized Linear Bandits with Local Differential Privacycited by 29
  10. 2014Optimum Statistical Estimation with Strategic Data Sourcescited by 28
  11. 2020Privacy-Preserving Dynamic Personalized Pricing with Demand Learningcited by 23
  12. 2021Local Differential Privacy Is Equivalent to Contraction of Eγ-Divergencecited by 17
11 more
  1. 2021Differential Privacy in Personalized Pricing with Nonparametric Demand Modelscited by 13
  2. 2017Optimal Data Acquisition for Statistical Estimationcited by 9
  3. 2014Redrawing the Boundaries on Purchasing Data from Privacy-Sensitive Individualscited by 8
  4. 2014Buying Private Data without Verificationcited by 8
  5. 2016Learning to Incentivize: Eliciting Effort via Output Agreementcited by 8
  6. 2016Sequential Peer Prediction: Learning to Elicit Effort using Posted Pricescited by 6
  7. 2018Prior-free Data Acquisition for Accurate Statistical Estimationcited by 5
  8. 2013Privacy and Mechanism Designcited by 4
  9. 2021Buying Data Over Time: Approximately Optimal Strategies for Dynamic Data-Driven Decisionscited by 2
  10. 2020Information Design for Congested Social Services: Optimal Need-Based Persuasioncited by 1
  11. 2021The Privacy Paradox and Optimal Bias-Variance Trade-offs in Data Acquisitioncited by 1

Built on by

Cited by year (2026 to 7 Oct)

Citing papers per year: 2022: 1; 2023: 6; 2024: 5; 2025: 7; 2026: 3.

22 papers.

Sort:

  1. 2023Threshold KNN-Shapley: A Linear-Time and Privacy-Friendly Approach to Data Valuationcited by 19
  2. 2024Incentives in Private Collaborative Machine Learningcited by 10
  3. 2024Noise-Aware Algorithm for Heterogeneous Differentially Private Federated Learningcited by 9
  4. 2024Optimal Federated Learning for Nonparametric Regression with Heterogeneous Distributed Differential Privacy Constraintscited by 7
  5. 2023Mean Estimation Under Heterogeneous Privacy: Some Privacy Can Be Freecited by 6
  6. 2023Mean Estimation Under Heterogeneous Privacy Demandscited by 6
  7. 2023The Fair Value of Data Under Heterogeneous Privacy Constraints in Federated Learningcited by 5
  8. 2025Crowding Out The Noise: Algorithmic Collective Action Under Differential Privacycited by 4
  9. 2023Striking a Balance: An Optimal Mechanism Design for Heterogenous Differentially Private Data Acquisition for Logistic Regressioncited by 3
  10. 2024Personalized Differential Privacy for Ridge Regressioncited by 3
  11. 2024Private Estimation when Data and Privacy Demands are Correlatedcited by 2
  12. 2025Managing Correlations in Data and Privacy Demandcited by 2
10 more
  1. 2022Truthful Generalized Linear Modelscited by 1
  2. 2023Privacy-Aware Data Acquisition under Data Similarity in Regression Marketscited by 1
  3. 2025High-Probability Bounds For Heterogeneous Local Differential Privacycited by 1
  4. 2025A Cram'er-von Mises Approach to Incentivizing Truthful Data Sharingcited by 0
  5. 2025Robust Estimation Under Heterogeneous Corruption Ratescited by 0
  6. 2025Non-Rival Data as Rival Products: An Encapsulation-Forging Approach for Data Synthesiscited by 0
  7. 2025Online Linear Regression with Paid Stochastic Featurescited by 0
  8. 2026Two-Stage Data Synthesization: A Statistics-Driven Restricted Trade-off between Privacy and Predictioncited by 0
  9. 2026Limits of Personalizing Differential Privacy Budgetscited by 0
  10. 2026Performative Privacy: When Differential Privacy Maximizes Utilitycited by 0