Sample Complexity Bounds on Differentially Private Learning via Communication Complexity

DOI10.1137/140991844zbMath1331.68104arXiv1402.6278OpenAlexW3023250268MaRDI QIDQ3454521

David Xiao, Vitaly Feldman

Publication date: 25 November 2015

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

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

zbMATH Keywords

lower boundscovering numbercommunication complexitysample complexitydifferentially private learning

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Learning and adaptive systems in artificial intelligence (68T05) Cryptography (94A60) Authentication, digital signatures and secret sharing (94A62)

Related Items

Unnamed Item ⋮ Differentially Private Learning of Geometric Concepts ⋮ Learning privately with labeled and unlabeled examples ⋮ Order-Revealing Encryption and the Hardness of Private Learning

Uses Software

• SuLQ

Cites Work

• Unnamed Item
• Unnamed Item
• Learnability with respect to fixed distributions
• Private vs. common random bits in communication complexity
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• On data structures and asymmetric communication complexity
• On randomized one-round communication complexity
• Algorithms and lower bounds for on-line learning of geometrical concepts
• Toward efficient agnostic learning
• Queries and concept learning
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Privately Releasing Conjunctions and the Statistical Query Barrier
• The reusable holdout: Preserving validity in adaptive data analysis
• Characterizing the sample complexity of private learners
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• What Can We Learn Privately?
• Efficient noise-tolerant learning from statistical queries
• The Algorithmic Foundations of Differential Privacy
• Bounds on the Sample Complexity for Private Learning and Private Data Release
• A theory of the learnable
• Differential privacy and robust statistics
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• A learning theory approach to noninteractive database privacy
• Lower Bounds for Sparse Recovery
• Privacy-preserving statistical estimation with optimal convergence rates
• Answering n _{2+o(1)} counting queries with differential privacy is hard
• Theory of Cryptography

This page was built for publication: Sample Complexity Bounds on Differentially Private Learning via Communication Complexity