What Can We Learn Privately?

Abstract

Learning problems form an important category of computational tasks that generalizes many of the computations researchers apply to large real-life data sets. 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? More precisely, we investigate learning algorithms that satisfy differential privacy, a notion that provides strong confidentiality guarantees in contexts where aggregate information is released about a database containing sensitive information about individuals. We demonstrate that, ignoring computational constraints, it is possible to privately agnostically learn any concept class using a sample size approximately logarithmic in the cardinality of the concept class. Therefore, almost anything learnable is learnable privately: specifically, if a concept class is learnable by a (non-private) algorithm with polynomial sample complexity and output size, then it can be learned privately using a polynomial number of samples. We also present a computationally efficient private PAC learner for the class of parity functions. Local (or randomized response) algorithms are a practical class of private algorithms that have received extensive investigation. We provide a precise characterization of local private learning algorithms. We show that a concept class is learnable by a local algorithm if and only if it is learnable in the statistical query (SQ) model. Finally, we present a separation between the power of interactive and noninteractive local learning algorithms.

35 pages, 2 figures

References in corpus (2)

• Differential Privacy with Compression
• A statistical framework for differential privacy

Cited by in corpus (22)

• Differentially Private Empirical Risk Minimization
• Mutual Information Optimally Local Private Discrete Distribution Estimation
• Collecting and Analyzing Multidimensional Data with Local Differential Privacy
• Improving the utility of locally differentially private protocols for longitudinal and multidimensional frequency estimates
• Differentially Private Spatial Decompositions
• Local Differential Privacy for Evolving Data
• Practical and Private (Deep) Learning without Sampling or Shuffling
• On Sampling, Anonymization, and Differential Privacy: Or, k-Anonymization Meets Differential Privacy
• Collect at Once, Use Effectively: Making Non-interactive Locally Private Learning Possible
• Private Sequential Learning
• Interactive Privacy via the Median Mechanism
• Information Leakage Games: Exploring Information as a Utility Function
• Distributed Private Data Analysis: On Simultaneously Solving How and What
• A statistical framework for differential privacy
• Optimal Lower Bounds for Universal and Differentially Private Steiner Tree and TSP
• Private Selection from Private Candidates
• Universally Optimal Privacy Mechanisms for Minimax Agents
• A Framework for Extracting Semantic Guarantees from Privacy
• Answering Multi-Dimensional Range Queries under Local Differential Privacy
• Differentially Private Combinatorial Optimization
• Large Margin Multiclass Gaussian Classification with Differential Privacy
• Differential Privacy and the Fat-Shattering Dimension of Linear Queries