Differentially Private Learning of Geometric Concepts
[edit]
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:32333241, 2019.
Abstract
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.
Related Material


