On the measurement complexity of differentially private query answering  

作　　者：WANG LiWei ZHANG JiaPeng 

机构地区：[1]Key Laboratory of Machine Perception (MOE),School of Electronics Engineering and Computer Science,Peking University [2]Computer Science and Engineering Department, University of California

出　　处：《Science China(Information Sciences)》2015年第9期146-156,共11页中国科学（信息科学）（英文版）

基　　金：supported by National Natural Science Foundation of China(Grant No.61222307);National Key Basic Research Program of China(973 Program)(Grant No.2015CB352502);a grant from Microsoft Research Asia,and a joint project with IBM

摘　　要：Differentially private query answering is an important problem in machine learning and data anal- ysis. As an example, the users may want to know the empirical errors of some classifiers on a training data set which contains sensitive information. In this case, the answers returned by the database holder must preserve privacy. Previous results show that answering large number of queries with differential privacy is computational- ly expensive. However, almost all the hardness results are conditional, which means that they rely on unproved conjectures. One exception is the hardness for stateless mechanisms, in which the sanitizer is assumed to have very limited memory and can only answer the queries separately. In this work, we explore the hardness for differentially private query answering mechanisms beyond the stateless restriction. Specifically, we investigate the measurement complexity of a natural class of stateful sanitizer. Here, measurement refers to the evaluation of a query （a Boolean function） on a data point. Measurement complexity is a lower bound for the running time. We prove unconditional subexponential lower bound for the measurement complexity of the class of sanitizer with e-differential privacy. Possible generalization of the results is also discussed.Differentially private query answering is an important problem in machine learning and data anal- ysis. As an example, the users may want to know the empirical errors of some classifiers on a training data set which contains sensitive information. In this case, the answers returned by the database holder must preserve privacy. Previous results show that answering large number of queries with differential privacy is computational- ly expensive. However, almost all the hardness results are conditional, which means that they rely on unproved conjectures. One exception is the hardness for stateless mechanisms, in which the sanitizer is assumed to have very limited memory and can only answer the queries separately. In this work, we explore the hardness for differentially private query answering mechanisms beyond the stateless restriction. Specifically, we investigate the measurement complexity of a natural class of stateful sanitizer. Here, measurement refers to the evaluation of a query （a Boolean function） on a data point. Measurement complexity is a lower bound for the running time. We prove unconditional subexponential lower bound for the measurement complexity of the class of sanitizer with e-differential privacy. Possible generalization of the results is also discussed.

关 键 词：PRIVACY differential privacy QUERY measurement complexity learning 

分 类 号：TP309[自动化与计算机技术—计算机系统结构] TP181[自动化与计算机技术—计算机科学与技术]