Differentially Private Learning of Geometric Concepts
This work addresses privacy-preserving machine learning for geometric data, which is incremental as it extends differential privacy to a specific domain.
The paper tackles the problem of learning geometric concepts, specifically unions of polygons, under differential privacy constraints, achieving PAC learning with a sample complexity of $ ilde{O}\left( rac{1}{\alpha\epsilon}k\log d ight)$.
We present differentially private efficient algorithms for learning union of polygons in the plane (which are not necessarily convex). Our algorithms achieve $(α,β)$-PAC learning and $(ε,δ)$-differential privacy using a sample of size $\tilde{O}\left(\frac{1}{αε}k\log d\right)$, where the domain is $[d]\times[d]$ and $k$ is the number of edges in the union of polygons.