Optimal differentially private learning of thresholds and quasi-concave optimization

DOI10.1145/3564246.3585148MaRDI QIDQ6499245zbMATH OpenWikidataFDO

Authors Edith Cohen, Xin Lyu, Jelani Nelson, Tamás Sarlos, Uri Stemmer

Publication date 8 May 2024

Full work available at URL https://doi.org/10.1145/3564246.3585148

zbMATH Keywords

differential privacyPAC learningthreshold functions

Mathematics Subject Classification ID

Theory of computing (68Qxx)

Cites work

• A theory of the learnable
• Bounds on the sample complexity for private learning and private data release
• Composable and versatile privacy via truncated CDP
• Differentially Private Approximations of a Convex Hull in Low Dimensions.
• scientific article; zbMATH DE number 7164746 (Why is no real title available?)
• On the Uniform Convergence of Relative Frequencies of Events to Their Probabilities
• Private and Online Learnability Are Equivalent
• 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
• Simultaneous private learning of multiple concepts
• Tail bounds for sums of geometric and exponential variables
• The complexity of computing the optimal composition of differential privacy
• The Composition Theorem for Differential Privacy
• Theory of Cryptography
• What can we learn privately?

Cited in

(2)

• Differentially private medians and interior points for non-pathological data
• Mixtures of Gaussians are privately learnable with a polynomial number of samples

This page was built for publication: Optimal differentially private learning of thresholds and quasi-concave optimization

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