Differentially Private Learning of Geometric Concepts

We present a differentially private efficient algorithm for learning union of polygons in the plane (which are not necessarily convex).  Our work is motivated by the task of analyzing GPS navigation data, or the task of learning the shape of a flood or a fire based on users' location reports. Our learner is obtained by designing a private variant for the classical (non-private) learner for conjunctions using the greedy algorithm for set-cover.

Joint work with Haim Kaplan, Yishay Mansour, and Yossi Matias.