A workload-adaptive mechanism for linear queries under local differential privacy
Authors:
Open Access
- 1 August 2020
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Proceedings of the VLDB Endowment
- Vol. 13 (12) , 1905-1918
Abstract
We propose a new mechanism to accurately answer a user-provided set of linear counting queries under local differential privacy (LDP). Given a set of linear counting queries (the workload) our mechanism automatically adapts to provide accuracy on the workload queries. We define a parametric class of mechanisms that produce unbiased estimates of the workload, and formulate a constrained optimization problem to select a mechanism from this class that minimizes expected total squared error. We solve this optimization problem numerically using projected gradient descent and provide an efficient implementation that scales to large workloads. We demonstrate the effectiveness of our optimization-based approach in a wide variety of settings, showing that it outperforms many competitors, even outperforming existing mechanisms on the workloads for which they were intended.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Principled Evaluation of Differentially Private Algorithms using DPBench2016
- The matrix mechanism: optimizing linear counting queries under differential privacyThe VLDB Journal, 2015
- Local, Private, Efficient Protocols for Succinct Histograms2015
- Lower Bounds on the Error of Query Sets Under the Differentially-Private Matrix MechanismTheory of Computing Systems, 2015
- Low-rank mechanismProceedings of the VLDB Endowment, 2012
- Unconditional differentially private mechanisms for linear queries2012
- An adaptive mechanism for accurate query answering under differential privacyProceedings of the VLDB Endowment, 2012
- Boosting the accuracy of differentially private histograms through consistencyProceedings of the VLDB Endowment, 2010
- Calibrating Noise to Sensitivity in Private Data Analysis2006
- Randomized Response: A Survey Technique for Eliminating Evasive Answer BiasJournal of the American Statistical Association, 1965