Simultaneous Private Learning of Multiple Concepts
Simultaneous Private Learning of Multiple Concepts
复制标题
同时私人学习多个概念
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
Uri Stemmer
中科院分区：
文献类型：
--
作者：
Mark Bun;Kobbi Nissim;Uri Stemmer
我们在差异私人PAC学习的背景下研究{em Direct-sum}问题：在差异隐私下同时求解K学习任务的样本复杂性是什么？与解决K学习任务的情况相比，这与无隐私的k学习任务相比如何？在我们的环境中，一个单独的示例由k未知概念（C1，...，CK）标记的域元素X组成。多学习者的目标是输出概括输入示例的K假设（H1，...，HK）。不用担心隐私，同时学习$ k $概念所需的样本复杂性与学习单个概念所需的基本相同。在差异隐私下，学习每个假设的基本策略独立地产生了用k多一项生长的样本复杂性。对于某些概念类别，我们为多学习者提供了比基本策略更少的样本。但是，不幸的是，我们还给出了下限，表明即使对于非常简单的概念类别，私人多学习的样本成本也必须在k中多一项增长。
We investigate the {em direct-sum} problem in the context of differentially private PAC learning: What is the sample complexity of solving k learning tasks simultaneously under differential privacy, and how does this cost compare to that of solving k learning tasks without privacy? In our setting, an individual example consists of a domain element x labeled by k unknown concepts (c1,...,ck). The goal of a multi-learner is to output k hypotheses (h1,...,hk) that generalize the input examples. Without concern for privacy, the sample complexity needed to simultaneously learn $k$ 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 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 k.