Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life datasets. We ask: what concept classes can be learned privately, namely, by an algorithm whose output does not depend too heavily on any one input or specific training example? Our goal is a complexity-theoretic classification of learning problems efficiently solvable with the privacy restriction, that is, by epsilon-differentially private algorithms. We consider four private learning models: local interactive (LI), learning non-interactive (LNI), centralized interactive (CI), and centralized non-interactive (CNI). We give a characterization of these models with respect to standard learning models, PAC and SQ. We show that for learning problems LNI is a strict subset of LI, and LI is a strict subset of CNI=CI. This characterization takes into account the number of samples required for learning, but not computational efficiency. We also present a partial characterization of these models when efficiency is taken into account.

研究了学习算法的隐私性问题，提出了差分隐私的概念，证明了任何可学习的概念类都可以差分隐私地学习，并提出了基于局部算法的隐私 PAC 学习器。

我们可以通过隐私学到什么？