Differentially Private Learning of Geometric Concepts

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 $(ϵ,\delta )$-differential privacy using a sample of size $\tilde{O}\left(\frac{1}{\alpha\epsilon}k\log d\right)$,wherethedomainis$[d]\times[d]$and$k$ is the number of edges in the union of polygons.