Skip to yearly menu bar Skip to main content


Differentially Private Learning of Geometric Concepts

Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer

Pacific Ballroom #124

Keywords: [ Privacy-preserving Statistics and Machine Learning ] [ Computational Learning Theory ]

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.

Live content is unavailable. Log in and register to view live content