@conference {555286,
	title = {Simultaneous private learning of multiple concepts},
	year = {2015},
	abstract = {We investigate the direct-sum problem in the context of differentially private PAC learning: What is the sample complexity of solving\&nbsp;k\&nbsp;learning tasks simultaneously under differential privacy, and how does this cost compare to that of solving\&nbsp;k\&nbsp;learning tasks without privacy? In our setting, an individual example consists of a domain element\&nbsp;x\&nbsp;labeled by\&nbsp;k\&nbsp;unknown concepts\&nbsp;(c1,{\textellipsis},ck). The goal of a multi-learner is to output\&nbsp;k\&nbsp;hypotheses\&nbsp;(h1,{\textellipsis},hk)\&nbsp;that generalize the input examples.\&nbsp;Without concern for privacy, the sample complexity needed to simultaneously learn\&nbsp;k\&nbsp;concepts is essentially the same as needed for learning a single concept. Under differential privacy, the basic strategy of learning each hypothesis independently yields sample complexity that grows polynomially with\&nbsp;k. For some concept classes, we give multi-learners that require fewer samples than the basic strategy. Unfortunately, however, we also give lower bounds showing that even for very simple concept classes, the sample cost of private multi-learning must grow polynomially in\&nbsp;k.},
	author = {Mark Bun and Kobbi Nissim and Uri Stemmer}
}
