Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms

Abstract

This paper studies the relationship between generalization and privacy preservation in iterative learning algorithms by two sequential steps. We first establish an alignment between generalization and privacy preservation for any learning algorithm. We prove that $(\epsilon ,\delta )$-differential privacy implies an on-average generalization bound for multi-database learning algorithms which further leads to a high-probability bound for any learning algorithm. This high-probability bound also implies a PAC-learnable guarantee for differentially private learning algorithms. We then investigate how the iterative nature shared by most learning algorithms influence privacy preservation and further generalization. Three composition theorems are proposed to approximate the differential privacy of any iterative algorithm through the differential privacy of its every iteration. By integrating the above two steps, we eventually deliver generalization bounds for iterative learning algorithms, which suggest one can simultaneously enhance privacy preservation and generalization. Our results are strictly tighter than the existing works. Particularly, our generalization bounds do not rely on the model size which is prohibitively large in deep learning. This sheds light to understanding the generalizability of deep learning. These results apply to a wide spectrum of learning algorithms. In this paper, we apply them to stochastic gradient Langevin dynamics and agnostic federated learning as examples.

References in corpus (16)

• Deep Learning with Differential Privacy
• Communication-Efficient Learning of Deep Networks from Decentralized Data
• Federated Learning: Strategies for Improving Communication Efficiency
• Normalizing Flows: An Introduction and Review of Current Methods
• Renyi Differential Privacy
• Differentially Private Federated Learning: A Client Level Perspective
• Multiplicative Normalizing Flows for Variational Bayesian Neural Networks
• Nearly-tight VC-dimension and pseudodimension bounds for piecewise linear neural networks
• Differential Privacy as a Mutual Information Constraint
• Non-convex learning via Stochastic Gradient Langevin Dynamics: a nonasymptotic analysis
• Privacy for Free: Posterior Sampling and Stochastic Gradient Monte Carlo
• Optimizing regularized Cholesky score for order-based learning of Bayesian networks
• Small nonlinearities in activation functions create bad local minima in neural networks
• On the Generalization Properties of Differential Privacy
• Piecewise linear activations substantially shape the loss surfaces of neural networks
• Capacity Bounded Differential Privacy

Cited by in corpus (4)

• Recent advances in deep learning theory
• Bayesian Inference Forgetting
• Robustness, Privacy, and Generalization of Adversarial Training
• Towards Prior-Free Approximately Truthful One-Shot Auction Learning via Differential Privacy