![]() Summary and Contributions: This submission presents an enhanced version of exponential mechanism, to solve the problem of differentially private item selection. With the added details mentioned in the rebuttal and some rephrasing of the text to make it more intuitive, this should be a strong paper. Update after rebuttal: I liked the paper before and I still like it. What I like, though, is that even for high-privacy regimes your approach significantly outperforms the exponential mechanism. In the case of small epsilon, the authors numerically solves the LP and shows that, in the case where epsilon 0.96 is particularly relevant as this is at the upper border of what I'd consider reasonable privacy. The authors show this by writing out the linear program (LP) that describes epsilon-DP constraints and give a dual solution that exactly matches the error of PF. (ii) The authors show that the PF is provably optimal for epsilon >= 2.62 among all regular mechanisms that satisfy "reasonable" properties of symmetry, shift invariants and monotonicity. We then enumerate through each candidate r using this ordering, and we output r with probability exp(epsilon / 2Delta * (q_r(D) - q^*)). Specifically, instead of randomly pick r from R in each step, we randomly permute R beforehand. With this perspective, PF can be viewed as a without-replacement variant of EM. Repeat the following until we output a solution: randomly pick a solution r from R, then with probability exp(epsilon / 2Delta * (q_r(D) - q^*)) output r. To describe a PF, it is useful to first restate EM in the following form. Moreover, in extreme datasets where one solution is really good (high quality score) and all other solutions are really bad (very low quality score), the improvement can be as larger as twice. Second, for the dataset that gives worst case error, PF provably gives a smaller error than EM the improvement depends on n, epsilon, Delta but it is noticeable as long as n, epsilon, Delta are moderate values. First, the expected error PF is never larger than that of EM with respect to any dataset and any scoring function. ![]() (i) The authors propose a mechanism, called Permute-and-Flip (PF) that provably improves on Exponential Mechanism (EM) in the following sense. The main contributions to this paper are as follows. To get an epsilon-DP algorithm, we output each r in R with probability proportional to exp(epsilon * q_r(D) / (2 * Delta)). the maximum change of q_r when changing a single user's input in the dataset D. Let Delta be the sensitivity of q_r, i.e. Many well-studied problems in machine learning can be stated in the selection formulation for example, each r could be a hypothesis and q_r(D) is the empirical error.Ī standard solution to this problem is the so-called Exponential Mechanism (McSherry and Talwar, FOCS'07) which works as follows. Here, we say that the algorithm incurs an error of q^* - Expectation where q^* = min_r q_r(D) in other words, the error is the expected quality loss of the return solution compared to the optimum. The goal is to, given dataset D, select r in R that maximizes q_r(D), while respecting the notion of differential privacy (DP). ![]() For each candidate r in R, there is a quality score function q_r that maps any input dataset D to a real number q_r(D). Summary and Contributions: This paper studies the selection problem, which (in the most general case) can be stated as follows: there is a data-independent set of n candidate solutions R that we would like to select from. Review for NeurIPS paper: Permute-and-Flip: A new mechanism for differentially private selection NeurIPS 2020 Permute-and-Flip: A new mechanism for differentially private selection
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. ArchivesCategories |