ICML Poster Differentially Private Learning of Geometric Concepts

Poster

Differentially Private Learning of Geometric Concepts

Haim Kaplan · Yishay Mansour · Yossi Matias · Uri Stemmer

Pacific Ballroom #124

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

[ Abstract ]

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} (\frac{1}{α ϵ} k \log d)

$\tilde{O}\left(\frac{1}{\alpha\epsilon}k\log d\right)$ , where the domain is

[d] \times [d]

$[d]\times[d]$ and

k

$k$ is the number of edges in the union of polygons.

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