# Tighter Generalization Bounds for Iterative Differentially Private Learning Algorithms

arXiv: https://arxiv.org/abs/2007.09371 · HTML: https://mlsanity.com/paper/2007.09371/

## Key facts

- Cited by 14 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 18 Jul 2020.

## Built on by (most cited first, 14 of 14)

- [DisPFL: Towards Communication-Efficient Personalized Federated Learning via Decentralized Sparse Training](https://mlsanity.com/paper/2206.00187/) (2022)
- [A Survey on Gradient Inversion: Attacks, Defenses and Future Directions](https://mlsanity.com/paper/2206.07284/) (2022)
- [Rethinking Portrait Matting with Privacy Preserving](https://mlsanity.com/paper/2203.16828/) (2022)
- [Generalization Bounds for Noisy Iterative Algorithms Using Properties of Additive Noise Channels](https://mlsanity.com/paper/2102.02976/) (2021)
- [Synthetic Text Generation for Training Large Language Models via Gradient Matching](https://mlsanity.com/paper/2502.17607/) (2025)
- [SpaFL: Communication-Efficient Federated Learning with Sparse Models and Low computational Overhead](https://mlsanity.com/paper/2406.00431/) (2024)
- [DP-FedPGN: Finding Global Flat Minima for Differentially Private Federated Learning via Penalizing Gradient Norm](https://mlsanity.com/paper/2510.27504/) (2025)
- [Bayesian Inference Forgetting](https://mlsanity.com/paper/2101.06417/) (2021)
- [Towards the Flatter Landscape and Better Generalization in Federated Learning under Client-level Differential Privacy](https://mlsanity.com/paper/2305.00873/) (2023)
- [OmniForce: On Human-Centered, Large Model Empowered and Cloud-Edge Collaborative AutoML System](https://mlsanity.com/paper/2303.00501/) (2023)
- [Towards Prior-Free Approximately Truthful One-Shot Auction Learning via Differential Privacy](https://mlsanity.com/paper/2104.00159/) (2021)
- [Spatial-Temporal-Fusion BNN: Variational Bayesian Feature Layer](https://mlsanity.com/paper/2112.06281/) (2021)
- [Black-Box Generalization: Stability of Zeroth-Order Learning](https://mlsanity.com/paper/2202.06880/) (2022)
- [A Theoretical Survey on Foundation Models](https://mlsanity.com/paper/2410.11444/) (2024)

## Abstract (arXiv)

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 (varepsilon, δ)-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.