A Minimax Distortion View of Non-Interactive Differential Privacy

Abstract—In this paper, differential privacy in the non-interactive setting is considered, with focus on differentially private mechanisms that generate synthetic databases. As op-posed to the conventional approach that carries out queries as if the synthetic database were the actual database, queries are answered using estimators based on both the released database and the differentially private mechanism. Under this model, the following minimax distortion formulation is used: since the synthetic database is expected to answer all possible queries, the performance of a differentially private mechanism is measured by the worst-case distortion among all queries of interest. Therefore, the smallest distortion at the worst query, which we call the minimax distortion, characterizes the fundamental limit of non-interactive differential privacy. Upper and lower bounds on the minimax distortion are obtained for two classes of queries: statis-tical queries and subset statistical queries. For statistical query, an -differentially mechanism and its companioned estimators are developed, under which the distortion for each statistical query scales as O(1/nα) for any 0 < α < 1/2, where n is the number of entries in the database, namely the size of the database. This finding indicates that all statistical queries can be answered with reasonable accuracy in large databases. I