Differentially Private Learning of Geometric Concepts
Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer

Thu Jun 13th 09:30 -- 09:35 AM @ Seaside Ballroom

We present differentially private efficient algorithms for learning union of polygons in the plane (which are not necessarily convex). Our algorithms achieve $(\alpha,\beta)$-PAC learning and $(\epsilon,\delta)$-differential privacy using a sample of size $\tilde{O}\left(\frac{1}{\alpha\epsilon}k\log d\right)$, where the domain is $[d]\times[d]$ and $k$ is the number of edges in the union of polygons.

Author Information

Haim Kaplan (Tel Aviv University and Google)
Yishay Mansour (Google and Tel Aviv University)
Yossi Matias (Google)
Uri Stemmer (Ben-Gurion University)

Related Events (a corresponding poster, oral, or spotlight)

More from the Same Authors