Privacy in general, and differential privacy (DP) in particular, have become important topics in data mining and machine learning. Digital advertising is a critical component of the internet and is powered by large-scale data analytics and machine learning models; privacy concerns around these are on the rise. Despite the central importance of private ad analytics and training privacy-preserving ad prediction models, there has been relatively little exposure of this subject to the broader KDD community. In the past three years, the interest in privacy and the interest in online advertising have been steadily growing in KDD. The aim of this tutorial is to provide KDD researchers with an introduction to the problems that arise in private analytics and modeling in advertising, survey recent results, and describe the main research challenges in the space.

We study synthetic data release for answering multiple linear queries over a set of database tables in a differentially private way. Two special cases have been considered in the literature: how to release a synthetic dataset for answering multiple linear queries over a single table, and how to release the answer for a single counting (join size) query over a set of database tables. Compared to the single-table case, the join operator makes query answering challenging, since the sensitivity (i.e., by how much an individual data record can affect the answer) could be heavily amplified by complex join relationships. We present an algorithm for the general problem, and prove a lower bound illustrating that our general algorithm achieves parameterized optimality (up to logarithmic factors) on some simple queries (e.g., two-table join queries) in the most commonly-used privacy parameter regimes. For the case of hierarchical joins, we present a data partition procedure that exploits the concept of uniformized sensitivities to further improve the utility.

Maximum bipartite matching is a fundamental algorithmic problem which can be solved in polynomial time. We consider a natural variant in which there is a separation constraint: the vertices on one side lie on a path or a grid, and two vertices that are close to each other are not allowed to be matched simultaneously. We show that the problem is hard to approximate even for paths, and provide constant-factor approximation algorithms for both paths and grids.