Sample complexity bounds on differentially private learning via communication complexity

DOI10.1137/140991844MaRDI QIDQ3454521zbMATH OpenOpenAlexFDO

Authors Vitaly Feldman, David Xiao

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

communication complexitycovering numberdifferentially private learninglower boundssample complexity

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)

Abstract: In this work we analyze the sample complexity of classification by differentially private algorithms. Differential privacy is a strong and well-studied notion of privacy introduced by Dwork et al. (2006) that ensures that the output of an algorithm leaks little information about the data point provided by any of the participating individuals. Sample complexity of private PAC and agnostic learning was studied in a number of prior works starting with (Kasiviswanathan et al., 2008) but a number of basic questions still remain open, most notably whether learning with privacy requires more samples than learning without privacy. We show that the sample complexity of learning with (pure) differential privacy can be arbitrarily higher than the sample complexity of learning without the privacy constraint or the sample complexity of learning with approximate differential privacy. Our second contribution and the main tool is an equivalence between the sample complexity of (pure) differentially private learning of a concept class $C$ (or $SCDP(C)$) and the randomized one-way communication complexity of the evaluation problem for concepts from $C$. Using this equivalence we prove the following bounds: 1. $SCDP(C)=Omega(LDim(C))$, where $LDim(C)$ is the Littlestone's (1987) dimension characterizing the number of mistakes in the online-mistake-bound learning model. Known bounds on $LDim(C)$ then imply that $SCDP(C)$ can be much higher than the VC-dimension of $C$. 2. For any $t$, there exists a class $C$ such that $LDim(C)=2$ but $SCDP(C)geqt$. 3. For any $t$, there exists a class $C$ such that the sample complexity of (pure) $alpha$-differentially private PAC learning is $Omega(t/alpha)$ but the sample complexity of the relaxed $$-differentially private PAC learning is $$. This resolves an open problem of Beimel et al. (2013b).

Recommendations

• scientific article; zbMATH DE number 7164746
• Bounds on the sample complexity for private learning and private data release
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy

Cites work

• A learning theory approach to noninteractive database privacy
• A theory of the learnable
• Algorithms and lower bounds for on-line learning of geometrical concepts
• Answering \(n^{2+o(1)}\) counting queries with differential privacy is hard
• Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques
• Bounds on the sample complexity for private learning and private data release
• Characterizing the sample complexity of private learners
• Decision theoretic generalizations of the PAC model for neural net and other learning applications
• Differential privacy and robust statistics
• Efficient noise-tolerant learning from statistical queries
• scientific article; zbMATH DE number 5485440 (Why is no real title available?)
• scientific article; zbMATH DE number 3385535 (Why is no real title available?)
• Learnability with respect to fixed distributions
• Lower bounds for sparse recovery
• On data structures and asymmetric communication complexity
• On randomized one-round communication complexity
• On the Power of Lower Bound Methods for One-Way Quantum Communication Complexity
• Privacy-preserving statistical estimation with optimal convergence rates
• Private Learning and Sanitization: Pure vs. Approximate Differential Privacy
• Private vs. common random bits in communication complexity
• Queries and concept learning
• The algorithmic foundations of differential privacy
• The reusable holdout: preserving validity in adaptive data analysis
• Theory of Cryptography
• Toward efficient agnostic learning
• What can we learn privately?

Cited in

(17)

• Learning privately with labeled and unlabeled examples
• Bounds on the sample complexity for private learning and private data release
• Order-revealing encryption and the hardness of private learning
• Characterizing the sample complexity of private learners
• Bounds on the sample complexity for private learning and private data release
• Learners that use little information
• Differentially private learning of geometric concepts
• Exponential Separations in Local Differential Privacy
• Private PAC learning implies finite Littlestone dimension
• scientific article; zbMATH DE number 7164746 (Why is no real title available?)
• Tight bounds for communication-assisted agreement distillation
• Private learning and sanitization: pure vs. approximate differential privacy
• Private and Online Learnability Are Equivalent
• Optimal differentially private learning of thresholds and quasi-concave optimization
• Optimal prediction using expert advice and randomized Littlestone dimension
• Not all learnable distribution classes are privately learnable
• Private PAC learning may be harder than online learning

Describes a project that uses

Uses Software

• SuLQ

This page was built for publication: Sample complexity bounds on differentially private learning via communication complexity

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