Bounds on the sample complexity for private learning and private data release (Q2251471)

The paper is very opportune in the current context of needing to protect privacy when mining data. The authors had previously designated the concept of private learning by combining probably approximately correct learning with differential privacy. This implies learning while preserving confidentiality on the sensitive information. Nevertheless, the current study moves one step further by giving tight bounds on the sample complexity in private learning, as opposed to the non-private one. Sample complexities of proper and improper private learners are strongly separated, as well as those for efficient and inefficient proper private learning. Finally, the article investigates the relationship (as bounds are concerned) between private learning and sanitized data (privacy protection besides useful information).