Differentially Private Learning of Geometric Concepts

2019/02/13 by Kaplan, Haim, Mansour, Yishay, Matias, Yossi +1
#FOS: Computer and information sciences #Machine Learning (cs.LG) #Machine Learning (stat.ML)

paper · doi:10.48550/arxiv.1902.05017

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)/(αε)klog d), where the domain is [d]×[d] and k is the number of edges in the union of polygons.

Related

• On the Sample Complexity of Privately Learning Axis-Aligned Rectangles
• Private Center Points and Learning of Halfspaces
• Private Learning of Halfspaces: Simplifying the Construction and Reducing the Sample Complexity
• An Optimal Differentially Private Learner for Concept Classes with VC Dimension 1
• Sample-efficient proper PAC learning with approximate differential\n privacy