Efficient Algorithm for Privately Releasing Smooth Queries
We study differentially private mechanisms for answering smooth queries on databases consisting of data points in R d . A K-smooth query is specified by a function whose partial derivatives up to order K are all bounded. We develop an -differentially private mechanism which for the class of K-smooth queries has accuracy O(n
The mechanism first outputs a summary of the database. To obtain an answer of a query, the user runs a public evaluation algorithm which contains no information of the database. Outputting the summary runs in time O(n 1+ d 2d+K ), and the evaluation algorithm for answering a query runs in timẽ
Our mechanism is based on L ∞ -approximation of (transformed) smooth functions by low degree even trigonometric polynomials with small and efficiently computable coefficients.
NOTE: Due to the number of papers to review and the 
      short reviewing time, to maintain consistency I did not seek to verify the 
      correctness of the results. As a result, I generally ignored any proofs or 
      additional details in the supplementary material. This review should be 
      considered as a review of the main paper alone. SUMMARY: The 
      authors propose a new method for approximating a database in a 
      differentially private manner when the database will be used to answer 
      queries with certain smoothness properties. The method appears to be 
      correct but is unclear if it is primarily theoretical interest or if it is 
      practically relevant. STRENGTHS: - This is a new approach to 
      database approximation for real data, a topic which has not received as 
      much attention in the differential privacy literature. - The 
      application of polynomial approximation is novel with respect to this 
      problem (although similar ideas for related problems have been proposed 
      before). WEAKNESSES: - It is unclear if the proposed method 
      actually "works" in any meaningful sense. The authors are not very clear 
      on this point. Since there is no experimental verification, it should be 
      more clear that this is a primarily theoretical investigation. - It is 
      not clear from the statement of the results if bounds are surprising, to 
      be expected, or if there is a hope of matching lower bounds. This makes it 
      hard to evaluate the "impact" of the result. COMMENTS: - 
      Does it make sense that the smoothness of the function should depend on 
      the data dimension? In particular, the fact that $K/d$ is the relevant 
      quantity is not very intuitive. - The authors seem to want to make a 
      big deal out of the fact that their approach allows "infinite number of 
      queries," but this is pretty obvious because they are not really looking 
      at a query model but instead a differentially private approximation of the 
      data. In the discrete setting, if one makes a differentially private 
      histogram, one gets the same thing. - I was hoping for more of a 
      comparison with [18], which (as I recall) also looks at real-valued data 
      and derives estimators based on a quantization approach. The authors cite 
      this paper but do not provide any context. - Indeed, the whole "name 
      of the game" here is density estimation, which is a well-studied area in 
      statistics and machine learning. What does this literature have to say 
      about the approach suggested by the authors? - Experiments, 
      evaluation? This seems like a nice recipe for approximation but it is a 
      little hard to see if, e.g. it will work at all for d of "practical" 
      interest. Indeed some examples of useful smooth queries could be nice. Is 
      this an interesting sub-class of problems that could be used as an 
      example? UPDATE AFTER REBUTTAL: * After the response and 
      discussion I remain sanguine about this paper. However, I would like many 
      of the details from the author's rebuttal to appear in the manuscript -- 
      this will help clarify the presentation and might actually facilitate some 
      discussion at NIPS. * The authors did not really address many of my 
      comments, which is somewhat disappointing. I think an example of 
      interesting smooth queries (e.g. in the introduction) will help ground the 
      theory. Otherwise many of the more applied folks interested in privacy 
      will say "oh, the authors show an algorithm for some version of smoothness 
      for which they give no interesting examples except references to [23] and 
      [28]." A concrete example of an interesting smooth query that is relevant 
      to the NIPS audience will make this paper more accessible.