preprint · arXiv (Cornell University) · 2014

Sample Complexity Bounds on Differentially Private Learning via\n Communication Complexity

Cited by 12Open access

Abstract

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

Cite this paper

APA 7

Feldman, V., & Xiao, D. (2014). Sample Complexity Bounds on Differentially Private Learning via\n Communication Complexity. arXiv (Cornell University). https://doi.org/10.48550/arxiv.1402.6278

MLA 9

Feldman, Vitaly, and David Xiao. “Sample Complexity Bounds on Differentially Private Learning via\n Communication Complexity.” arXiv (Cornell University), 2014, https://doi.org/10.48550/arxiv.1402.6278.

Chicago

Feldman, Vitaly, and David Xiao. 2014. “Sample Complexity Bounds on Differentially Private Learning via\n Communication Complexity.” arXiv (Cornell University). https://doi.org/10.48550/arxiv.1402.6278.

Harvard

Feldman, V. and Xiao, D. (2014) ‘Sample Complexity Bounds on Differentially Private Learning via\n Communication Complexity’, arXiv (Cornell University). Available at: https://doi.org/10.48550/arxiv.1402.6278.

BibTeX

@misc{feldman2014sample,
  title = {{Sample Complexity Bounds on Differentially Private Learning via\n Communication Complexity}},
  author = {Feldman, Vitaly and Xiao, David},
  journal = {arXiv (Cornell University)},
  year = {2014},
  doi = {10.48550/arxiv.1402.6278}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.