# Privacy-Preserving Monotonicity of Differential Privacy Mechanisms
## 2 Related Works
[50] described an approach to distributed search logs collection, storage, and mining, which the dual goals preservedprivacy and made the mined information broadly available. This method had the trade-off between the strength of the guarantees of privacy loss and the utility of the released data, but this method did not generalize to the feasibility of realistic settings. [PERSON] et al. [21] proposed a sanitization framework to perfectly tackle the trade-off in the context of search logs in a distributed manner. This framework significantly preserved the utility of the sanitized search logs, but this framework was not an effective approach to publish search logs with the correlation between users' query-url pairs. [PERSON] et al. [51] precisely characterized the trade-off between privacy and threshold used for publishing a query. They proposed a solution to release the search logs by an algorithm for releasing queries and clicks on a manner that guaranteed user privacy according to a rigorous privacy definition, but it could not best generate a search log from perturbed data. [PERSON] et al. [52] introduced a framework of anonymous query logs by differential privacy. This framework was able to achieve a good balance between retrieval utility and privacy; however, the framework was only empirically evaluated against multiple search algorithms on their retrieval utility. [PERSON] et al. [53] proposed a privacy-preserving method of query logs that joined the flexibility and convenience of privacy-preserving data releasing with the strong privacy guarantees of differential privacy. Although this method produced query logs with differential privacy that was useful for data analysis, the major challenge was that the microaggregation algorithm did adapt to the lack of structure of query logs. In addition, query logs with differential privacy do not provide a way to measure the trade-off. This problem has been addressed based on the definition of privacy-preserving monotonicity. Differential privacy can ensure the trade-off of statistics analysis. [PERSON] et al. [54] studied the theoretical and empirical performance of differential privacy approximations to principal components analysis. They proposed a new method which explicitly optimized the utility of the output; however, developing a framework of analyzing general approximations to principal components analysis might be a challenge to machine learning. [PERSON] et al. [55] gave the details of two differential privacy policy evaluation algorithms based on first visit Monte Carlo estimation. This algorithm came with utility guarantees showing that the cost of privacy diminished as training batches get larger but extending the algorithm to other applications was a challenge. [PERSON] et al. [56] studied a suite of mechanisms how to communicate findings of Bayesian inference to third parties of the strong guarantee of differential privacy. These mechanisms showed the trade-off between privacy and utility. Within Bayesian inference based on differential privacy under certain conditions on the prior, [PERSON] et al. [22] presented that the sampling from the posterior distribution could lead to a desired level of privacy and utility. Although they had shown how Bayesian inference could already be differential privacy by appropriately setting the prior, they had not examined how this affects learning. Furthermore, the measurement method of the trade-off was not provided for statistics analysis with differential privacy. Thus, we proposed the definition of privacy-preserving monotonicity to measure the trade-off. Data aggregation using differential privacy can get the trade-off. [PERSON] et al. [57] proposed a method of composing an aggregate classifier satisfying differential privacy from classifiers locally trained by multiple untrusted parties.