Q: In this task, you are given a part of an article. Your task is to generate headline (title) for this text. Preferred headlines are under fifteen words.
We investigate the direct-sum problem in the context of differentially private PAC learning: What<lb>is the sample complexity of solving k learning tasks simultaneously under differential privacy, and how<lb>does this cost compare to that of solving k learning tasks without privacy? In our setting, an individual<lb>example consists of a domain element x labeled by k unknown concepts (c1, . . . ,<lb>ck). The goal of a<lb>multi-learner is to output k hypotheses (h1, . . . , hk) that generalize the input examples.<lb>Without concern for privacy, the sample complexity needed to simultaneously learn k concepts is<lb>essentially the same as needed for learning a single concept. Under differential privacy, the basic strategy<lb>of learning each hypothesis independently yields sample complexity that grows polynomially with k.<lb>For some concept classes, we give multi-learners that require fewer samples than the basic strategy.<lb>Unfortunately, however, we also give lower bounds showing that even for very simple concept classes,<lb>the sample cost of private multi-learning must grow polynomially in k.
A:
Simultaneous Private Learning of Multiple Concepts