DIFFERENTIALLY PRIVATE LEARNING OF GEOMETRIC CONCEPTS

被引：0

作者：

Kaplan H. ^{[1
,2
]}

Mansour Y. ^{[1
,2
]}

Matias Y. ^{[2
]}

Stemmer U. ^{[1
,2
]}

机构：

[1] Tel Aviv University, Tel Aviv

[2] Google Israel, Tel Aviv

来源：

SIAM Journal on Optimization | 2022年 / 32卷 / 03期

关键词：

differential privacy; PAC learning; polygons;

D O I：

10.1137/21M1427450

中图分类号：

学科分类号：

摘要：

We present efficient differentially private algorithms for learning unions of polygons in the plane (which are not necessarily convex). Our algorithms are (α , β)-probably approximately correct and (ϵ , δ )-differentially private using a sample of size O ( 1 α) , where the domain is [d] × [d] and k is the number of edges in the union of polygons. Our algorithms are obtained by designing a private variant of the classical (nonprivate) learner for conjunctions using the greedy algorithm for set cover. © 2022 Society for Industrial and Applied Mathematics.

引用

页码：952 / 974

页数：22

共 34 条

[1]

Abowd J. M., The Challenge of Scientific Reproducibility and Privacy Protection for Statistical Agencies, (2016)

[2]

Alon N., Beimel A., Moran S., Stemmer U., Closure properties for private classification and online prediction, Proc. Mach. Learn. Res, 125, pp. 119-152, (2020)

[3]

Alon N., Livni R., Malliaris M., Moran S., Private PAC learning implies finite littlestone dimension, CoRR, (2018)

[4]

Bassily R., Thakurta A. G., Thakkar O. D., Model-agnostic private learning, Proceedings of the Conference on Neural Information Processing Systems, pp. 7102-7112, (2018)

[5]

Beimel A., Kasiviswanathan S. P., Nissim K., Bounds on the sample complexity for private learning and private data release, Theory of Cryptography Conference, Lecture Notes in Computer Science, 5978, pp. 437-454, (2010)

[6]

Beimel A., Nissim K., Stemmer U., Characterizing the sample complexity of private learners, Proceedings of the Conference on Innovations in Theoretical Computer Science, pp. 97-110, (2013)

[7]

Beimel A., Nissim K., Stemmer U., Private learning and sanitization: Pure vs. approximate differential privacy, APPROX-RANDOM, Lecture Notes in Computer Science, 8096, pp. 363-378, (2013)

[8]

Beimel A., Nissim K., Stemmer U., Learning privately with labeled and unlabeled examples, Proceedings of the Symposium on Discrete Algorithms, SIAM, pp. 461-477, (2015)

[9]

Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K., Learnability and the Vapnik-Chervonenkis dimension, J. ACM, 36, pp. 929-965, (1989)

[10]

Bun M., Livni R., Moran S., An equivalence between private classification and online prediction, Proceedings of the Symposium on Foundations of Computer Science, pp. 389-402, (2020)

← 1 2 3 4 →