The Limits of Differential Privacy in Online Learning
This work addresses privacy-utility trade-offs in online learning for data analysts, providing foundational insights but is incremental in generalizing prior results.
The paper investigates the fundamental limits of differential privacy in online learning, showing that approximate DP is necessary for adaptive adversaries and proving that private online learners must make infinite mistakes for most hypothesis classes, unlike non-private settings where finite mistake bounds are attainable.
Differential privacy (DP) is a formal notion that restricts the privacy leakage of an algorithm when running on sensitive data, in which privacy-utility trade-off is one of the central problems in private data analysis. In this work, we investigate the fundamental limits of differential privacy in online learning algorithms and present evidence that separates three types of constraints: no DP, pure DP, and approximate DP. We first describe a hypothesis class that is online learnable under approximate DP but not online learnable under pure DP under the adaptive adversarial setting. This indicates that approximate DP must be adopted when dealing with adaptive adversaries. We then prove that any private online learner must make an infinite number of mistakes for almost all hypothesis classes. This essentially generalizes previous results and shows a strong separation between private and non-private settings since a finite mistake bound is always attainable (as long as the class is online learnable) when there is no privacy requirement.