DIFFERENTIALLY PRIVATE LEARNING OF GEOMETRIC CONCEPTS

被引：0

作者：

Kaplan, Haim ^{[1
,2
]}

Mansour, Yishay ^{[1
,2
]}

Matias, Yossi ^{[2
]}

Stemmer, Uri ^{[1
,2
]}

机构：

[1] Tel Aviv Univ, Tel Aviv, Israel

[2] Google Israel, Tel Aviv, Israel

来源：

SIAM JOURNAL ON COMPUTING | 2022年 / 51卷 / 04期

关键词：

differential privacy; PAC learning; polygons; SAMPLE COMPLEXITY; NOISE; BOUNDS;

D O I：

10.1137/21M1406428

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We present efficient differentially private algorithms for learning unions of polygons in the plane (which are not necessarily convex). Our algorithms are (alpha , beta)-probably approximately correct and (epsilon, delta)-differentially privacy using a sample of size O(1/alpha?klogd), where the domain is [d]x[d] and k is the number of edges in the union of polygons

引用

页码：952 / 974

页数：23

共 34 条

[1]

ABOWD J. M., 2016, Technical report

[2]

ALON N., 2018, ABS180600949 CORR

[3]

Alon Noga, 2020, P MACHINE LEARNING R, P119

[4]

Bassily R, 2018, ADV NEUR IN, V31

[5]

Beimel Amos, 2013, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques. Algorithms and Techniques. 16th International Workshop, APPROX 2013 and 17th International Workshop, RANDOM 2013. Proceedings: LNCS 8096, P363, DOI 10.1007/978-3-642-40328-6_26

[6]

Beimel A, 2010, LECT NOTES COMPUT SC, V5978, P437, DOI 10.1007/978-3-642-11799-2_26

[7]

Beimel Amos, 2013, ITCS, P97, DOI DOI 10.1145/2422436.2422450

[8]

Beimel Amos, 2015, P 26 ANN ACM SIAM S, P461

[9] LEARNABILITY AND THE VAPNIK-CHERVONENKIS DIMENSION [J].

BLUMER, A ;

EHRENFEUCHT, A ;

HAUSSLER, D ;

WARMUTH, MK .

JOURNAL OF THE ACM, 1989, 36 (04) :929-965

[10] An Equivalence Between Private Classification and Online Prediction [J].

Bun, Mark ;

Livni, Roi ;

Moran, Shay .

2020 IEEE 61ST ANNUAL SYMPOSIUM ON FOUNDATIONS OF COMPUTER SCIENCE (FOCS 2020), 2020, :389-402

← 1 2 3 4 →