Differentially Private Data Releasing for Smooth Queries

Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong, Liwei Wang

TL;DR

This paper introduces novel methods for releasing continuous data while preserving differential privacy, specifically addressing "smooth queries" (functions with bounded derivatives). They propose two mechanisms: one that outputs a database summary and another that generates a synthetic database, both achieving strong accuracy guarantees and running in polynomial time.

What Problem Does This Paper Address?

The field of differential privacy has seen significant progress in protecting sensitive data when answering queries. However, most existing work focuses on discrete data (like binary attributes) and queries based on Boolean functions. In real-world applications, continuous data (e.g., measurements, sensor readings) are prevalent, and queries often involve continuous functions. This paper bridges this gap by developing differentially private mechanisms for answering linear queries induced by "smooth" continuous functions on continuous data. Smoothness, defined by bounded partial derivatives up to a certain order $K$, is a natural property for many real-world functions.

Methods

The core of the proposed mechanisms relies on approximating smooth functions using low-degree trigonometric polynomials. The authors transform the original smooth function $f$ into a related function $g_f$ defined on the hypercube $[- \pi, \pi]^d$. They then use an $L_\infty$-approximation technique to find a trigonometric polynomial $p$ that closely approximates $g_f$.

Two main mechanisms are presented:

  1. Query Answering Mechanism: This mechanism first computes a summary of the database by adding Laplace noise to the answers of queries based on the trigonometric polynomial basis functions. To answer a specific smooth query, it approximates the query function with a trigonometric polynomial and uses the pre-computed summary to provide a differentially private answer.
  2. Synthetic Database Mechanism: This mechanism goes a step further by generating an entirely synthetic database. It learns a probability distribution over a discretized version of the data universe such that queries on this synthetic data are close to the noisy answers from the original data. This is achieved by solving a linear programming problem to find the optimal distribution.

Both mechanisms leverage the properties of trigonometric polynomials and the Laplace mechanism for differential privacy. They also develop practically efficient variants.

Datasets

The paper uses three real-world datasets for experimental evaluation:

  • NOM
  • NUR
  • CTG

These datasets are from the UCI repository and are normalized to have attributes within the range $[-1, 1]^d$.

Key Insights and Ideas

  • Smoothness is Key: The paper highlights that the "smoothness" property of continuous functions (bounded derivatives) is crucial for developing efficient and accurate differentially private mechanisms.
  • Trigonometric Polynomials as a Bridge: Transforming continuous functions into trigonometric polynomials provides a powerful framework for approximation and analysis within the differential privacy context.
  • Synthetic Data for Broader Utility: Generating a synthetic database offers greater flexibility for downstream tasks like machine learning, as it allows users to answer arbitrary smooth queries without direct interaction with the original sensitive data.
  • Trade-off Between Accuracy and Smoothness: The accuracy of the mechanisms improves significantly as the order of smoothness ($K$) increases, demonstrating a direct benefit from the functional properties of the queries.

Key Results

  • Accuracy: Both proposed mechanisms achieve an accuracy of $O(n^{-\frac{K}{2d+K}}/\epsilon)$ for $K$-smooth queries, which is a significant improvement over existing methods for discrete data and general queries, especially for high $K$.
  • Differential Privacy: Both mechanisms are proven to be $\epsilon$-differentially private.
  • Running Time: The query answering mechanism has a running time of $O(n^{2d+K})$ for outputting the summary and $O(n^{\frac{2d+K}{d+K}} \cdot \text{polylog}(n))$ for answering a query. The synthetic database mechanism runs in $O(n^{4d+2K})$ time. Practical variants are significantly faster.
  • Synthetic Database Size: The size of the output synthetic database is $O(n^{\frac{2d+K}{d+K}})$.
  • Experimental Validation: Experiments on real-world datasets show that the mechanisms achieve good accuracy and that accuracy improves with higher smoothness ($K$) and decreases with increasing privacy parameter ($\epsilon$).

Limitations and Future Work

  • Dimensionality Dependence: The performance of the mechanisms degrades exponentially with the data dimension $d$. The current algorithms are practical only for relatively low dimensions (e.g., up to a few hundred). Studying the general case where $d$ is not a constant is identified as future work.
  • Smoothness Assumption: The mechanisms are designed for smooth queries. Extending them to handle queries that are not smooth, or a combination of smooth and non-smooth queries, is an open research direction.
  • Practical Efficiency: While polynomial time, the running times for the synthetic database mechanism can still be substantial for high dimensions and smoothness. Developing more practically efficient variants is an ongoing effort.

Summary updated

Abstract

In the past few years, differential privacy has become a standard concept in the area of privacy. One of the most important problems in this field is to answer queries while preserving differential privacy. In spite of extensive studies, most existing work on differentially private query answering assumes the data are discrete (i.e., in $\{0,1\}^d$) and focuses on queries induced by \emph{Boolean} functions. In real applications however, continuous data are at least as common as binary data. Thus, in this work we explore a less studied topic, namely, differential privately query answering for continuous data with continuous function. As a first step towards the continuous case, we study a natural class of linear queries on continuous data which we refer to as smooth queries. A linear query is said to be $K$-smooth if it is specified by a function defined on $[-1,1]^d$ whose partial derivatives up to order $K$ are all bounded. We develop two $\epsilon$-differentially private mechanisms which are able to answer all smooth queries. The first mechanism outputs a summary of the database and can then give answers to the queries. The second mechanism is an improvement of the first one and it outputs a synthetic database. The two mechanisms both achieve an accuracy of $O (n^{-\frac{K}{2d+K}}/\epsilon )$. Here we assume that the dimension $d$ is a constant. It turns out that even in this parameter setting (which is almost trivial in the discrete case), using existing discrete mechanisms to answer the smooth queries is difficult and requires more noise. Our mechanisms are based on $L_{\infty}$-approximation of (transformed) smooth functions by low-degree even trigonometric polynomials with uniformly bounded coefficients. We also develop practically efficient variants of the mechanisms with promising experimental results.
BibTeX
@article{wang2016differentially,
  author = {Ziteng Wang and Chi Jin and Kai Fan and Jiaqi Zhang and Junliang Huang and Yiqiao Zhong and Liwei Wang},
  title = {{Differentially Private Data Releasing for Smooth Queries}},
  journal = {J. Mach. Learn. Res.},
  year = {2016},
  url = {https://openreview.net/forum?id=2-UU-b9jNDV},
}
Figure