TY - JOUR

T1 - Differentially private data releasing for smooth queries

AU - Wang, Ziteng

AU - Jin, Chi

AU - Fan, Kai

AU - Zhang, Jiaqi

AU - Huang, Junliang

AU - Zhong, Yiqiao

AU - Wang, Liwei

N1 - Funding Information:
This work was supported by National Basic Research Program of China (973 Program)(grant no. 2015CB352502), NSFC(61573026, 61222307), IBM Faculty Award and a grant from Microsoft Research Asia.
Publisher Copyright:
©2016 Ziteng Wang, Chi Jin, Kai Fan, Jiaqi Zhang, Junliang Huang, Yiqiao Zhong and Liwei Wang.

PY - 2016/4/1

Y1 - 2016/4/1

N2 - 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 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 ε-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- K/2d+K /ε). 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∞-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.

AB - 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 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 ε-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- K/2d+K /ε). 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∞-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.

KW - Differential privacy

KW - Smooth queries

KW - Synthetic dataset

UR - http://www.scopus.com/inward/record.url?scp=84979896303&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84979896303&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:84979896303

SN - 1532-4435

VL - 17

JO - Journal of Machine Learning Research

JF - Journal of Machine Learning Research

ER -