Sample Complexity Bounds on Differentially Private Learning via Communication Complexity

By Vitaly Feldman, David Xiao. 2014

85 citations recorded by the source corpus.

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) \geq t$. 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 $(\alpha,\beta)$-differentially private PAC learning is $O(\log(1/\beta)/\alpha)$. This resolves an open problem of Beimel et al. (2013b).

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

The power of synergy in differential privacy: Combining a small curator with local randomizers (2019, methodology): “Speciﬁcally, we use lower bounds for ε -di ﬀ erential private learning of the threshold functions in the cura-tor model [11, 30]; these lower bounds do not hold for ( ε,δ )-di ﬀ erential private learning of the threshold functions [12, 17].”
The structure of optimal private tests for simple hypotheses (2018, background): “There are also several rich lines of work attempting to give tight instance-specific characterizations of the sample complexities of various differentially private computations, most notably linear query release [11, 43, 48, 57, 58] and PAC and agnostic learning [10, 39, 46].”
Simultaneous Private Learning of Multiple Concepts (2015, background): “[18] V. Feldman and D. Xiao.”
Differentially Private Release and Learning of Threshold Functions (2015, background): “Hardt and Rothblum [HR10] improved this bound to Õ(log |Q| · √ log |X|), which was recently shown to be optimal for some families”
The Complexity of Differential Privacy (2017, background): “For (ε, 0)differentially private learners, the sample complexity was recently shown to be Ω(d) by Feldman and Xiao [50].”
Privacy-preserving Prediction (2018, background): “While the class is very simple, learning it with privacy has proved to be rather challenging and some basic questions are still not fully resolved [BKN10; CH11; BNS13; FX15; BNSV15].”
When is memorization of irrelevant training data necessary for high-accuracy learning? (2020, methodology): “Another closely related concept is probabilistic representation complexity [7, 19].”