Local Privacy and Minimax Bounds: Sharp Rates for Probability Estimation
We provide a detailed study of the estimation of probability distributionsdiscrete and continuous-in a stringent setting in which data is kept private even from the statistician. We give sharp minimax rates of convergence for estimation in these locally private settings, exhibiting fundamental trade-offs between privacy and convergence rate, as well as providing tools to allow movement along the privacy-statistical efficiency continuum. One of the consequences of our results is that Warner's classical work on randomized response is an optimal way to perform survey sampling while maintaining privacy of the respondents.
This paper studies minimax bounds for probability 
      estimation under the constraint that the estimation must preserve privacy 
      of the individual data. The authors consider a privacy definition called 
      local privacy. They study two probability estimation problems, multinomial 
      estimation and density estimation. In both problems, the authors show 
      sharp minimax rates of convergence. They demonstrate that, for the 
      discrete multinomial estimation problem, local privacy causes a reduction 
      in the effective sample size quadratic in the privacy parameter alpha. 
      Since alpha can often be seen as a small constant, the effective sample 
      size is of the same order as the non-private case. For the density 
      estimation problem, the authors demonstrate that the optimal rate for the 
      non-private setting is no longer attainable if local privacy must be 
      preserved. Overall the results are very interesting. As far as I 
      could read, the proofs are correct. To the best of my knowledge, the 
      minimax bound for density estimation under privacy constraint has not been 
      considered before. My main comment is that the minimax bound of 
      the multinomial estimation is closely related to previous works on the 
      noise complexity for differential privacy, but there is a lack of mention. 
      In particular, two papers consider highly relevant problems, 
      Hardt&Talwar, On the geometry of differential privacy, STOC, 2010; and 
      De, Lower bounds in differential privacy, TCC, 2012. These two papers 
      study worst case lower bounds for the error of linear queries under the 
      constraint of differential privacy. The probability estimation problem 
      considered in this paper is actually a special case of the linear counting 
      query studied in those two papers. Also, the measures used for the error 
      are the same L_2 metric. The only difference is that this paper considers 
      local differential privacy while Hardt&Talwar and De consider 
      differential privacy. Local privacy posts stronger constraint than 
      differential privacy, and therefore lower bounds for differential privacy 
      are also lower bounds for local privacy. I am wondering if the bound for 
      local privacy given in this paper improves over previous bounds for 
      differential privacy. For the density estimation problem, the 
      statement of the result is a bit confusing. The authors state that the 
      lower bound in the local privacy setting is higher than the non-private 
      setting. But the minimax bound in this paper is for the special case that 
      the density can be expanded with trigonometric basis. I am wondering if 
      the lower bound for the non-private setting eq.(13) holds for the general 
      Sobolev space as given in definition 1 or for the special case of 
      trigonometric basis. It is a fair comparison only if the non-private lower 
      bound holds for the trigonometric basis. Additional comments to 
      the rebuttal: The feedback partially clarifies the relation to 
      previous worst case lower bounds. But note the work of Nikolov, Talwar, 
      and Zhang, The Geometry of Differential Privacy: The Sparse and 
      Approximate Cases (STOC 2013) also considers Mean Square Error. I suggest 
      the authors add their explanations and missing references to the paper.