Differentially private learning of geometric concepts

DOI10.1137/21M1406428MaRDI QIDQ5092508zbMATH OpenOpenAlexWikidataFDO

Authors Haim Kaplan, Yishay Mansour, Y. Matias, Uri Stemmer

Publication date 22 July 2022

Published in SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1902.05017

zbMATH Keywords

polygonsdifferential privacyPAC learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Privacy of data (68P27)

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 $(epsilon,delta)$-differential privacy using a sample of size $ildeOleft(frac1alphaepsilonklogdight)$, where the domain is $[d]imes[d]$ and $k$ is the number of edges in the union of polygons.

Recommendations

• What can we learn privately?
• Simultaneous private learning of multiple concepts
• Simultaneous private learning of multiple concepts
• scientific article; zbMATH DE number 7164746
• Private data release via learning thresholds

Cites work

• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• A theory of the learnable
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Differential privacy and robust statistics
• Differentially private combinatorial optimization
• Efficient noise-tolerant learning from statistical queries
• Learnability and the Vapnik-Chervonenkis dimension
• Learning Privately with Labeled and Unlabeled Examples
• Order-revealing encryption and the hardness of private learning
• Our Data, Ourselves: Privacy Via Distributed Noise Generation
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Private PAC learning implies finite Littlestone dimension
• Sample complexity bounds on differentially private learning via communication complexity
• Sample-efficient proper PAC learning with approximate differential privacy
• Simultaneous private learning of multiple concepts
• The VC dimension of \(k\)-fold union
• The algorithmic foundations of differential privacy
• The complexity of differential privacy
• Theory of Cryptography
• What can we learn privately?

Cited in

(4)

• Simultaneous private learning of multiple concepts
• Differentially-private learning of low dimensional manifolds
• How to Find a Point in the Convex Hull Privately
• Differentially-private learning of low dimensional manifolds

This page was built for publication: Differentially private learning of geometric concepts

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5092508)