A workload-adaptive mechanism for linear queries under local differential privacy
This work addresses the challenge of improving query accuracy in privacy-preserving data analysis for applications like surveys or analytics, representing an incremental advance over prior LDP methods.
The paper tackles the problem of accurately answering user-provided linear counting queries under local differential privacy by proposing a workload-adaptive mechanism that minimizes expected total squared error through optimization, demonstrating it outperforms existing mechanisms in various settings.
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.