Differentially Private Learning of Geometric Concepts

Haim Kaplan, Yishay Mansour, Yossi Matias, Uri Stemmer
Proceedings of the 36th International Conference on Machine Learning, PMLR 97:3233-3241, 2019.

Abstract

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 ˜O(1αϵklogd), where the domain is [d]×[d] and k is the number of edges in the union of polygons.

Cite this Paper

BibTeX
@InProceedings{pmlr-v97-kaplan19a, title = {Differentially Private Learning of Geometric Concepts}, author = {Kaplan, Haim and Mansour, Yishay and Matias, Yossi and Stemmer, Uri}, booktitle = {Proceedings of the 36th International Conference on Machine Learning}, pages = {3233--3241}, year = {2019}, editor = {Chaudhuri, Kamalika and Salakhutdinov, Ruslan}, volume = {97}, series = {Proceedings of Machine Learning Research}, month = {09--15 Jun}, publisher = {PMLR}, pdf = {http://proceedings.mlr.press/v97/kaplan19a/kaplan19a.pdf}, url = {https://proceedings.mlr.press/v97/kaplan19a.html}, 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.} }
Endnote
%0 Conference Paper %T Differentially Private Learning of Geometric Concepts %A Haim Kaplan %A Yishay Mansour %A Yossi Matias %A Uri Stemmer %B Proceedings of the 36th International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2019 %E Kamalika Chaudhuri %E Ruslan Salakhutdinov %F pmlr-v97-kaplan19a %I PMLR %P 3233--3241 %U https://proceedings.mlr.press/v97/kaplan19a.html %V 97 %X 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.
APA
Kaplan, H., Mansour, Y., Matias, Y. & Stemmer, U.. (2019). Differentially Private Learning of Geometric Concepts. Proceedings of the 36th International Conference on Machine Learning, in Proceedings of Machine Learning Research 97:3233-3241 Available from https://proceedings.mlr.press/v97/kaplan19a.html.

Related Material