# Differential Privacy for Growing Databases

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

## Key facts

- Cited by 8 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 16 Mar 2018.

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

- [Differential Privacy in Natural Language Processing: The Story So Far](https://mlsanity.com/paper/2208.08140/) (2022)
- [Dynamic Privacy Budget Allocation Improves Data Efficiency of Differentially Private Gradient Descent](https://mlsanity.com/paper/2101.07413/) (2021)
- [Privacy Budget Scheduling](https://mlsanity.com/paper/2106.15335/) (2021)
- [Online Differentially Private Synthetic Data Generation](https://mlsanity.com/paper/2402.08012/) (2024)
- [On the Privacy of Selection Mechanisms with Gaussian Noise](https://mlsanity.com/paper/2402.06137/) (2024)
- [DPack: Efficiency-Oriented Privacy Budget Scheduling](https://mlsanity.com/paper/2212.13228/) (2022)
- [Adaptive Data Analysis for Growing Data](https://mlsanity.com/paper/2405.13375/) (2024)
- [Continual and Sliding Window Release for Private Empirical Risk Minimization](https://mlsanity.com/paper/2203.03594/) (2022)

## Abstract (arXiv)

We study the design of differentially private algorithms for adaptive analysis of dynamically growing databases, where a database accumulates new data entries while the analysis is ongoing. We provide a collection of tools for machine learning and other types of data analysis that guarantee differential privacy and accuracy as the underlying databases grow arbitrarily large. We give both a general technique and a specific algorithm for adaptive analysis of dynamically growing databases. Our general technique is illustrated by two algorithms that schedule black box access to some algorithm that operates on a fixed database to generically transform private and accurate algorithms for static databases into private and accurate algorithms for dynamically growing databases. These results show that almost any private and accurate algorithm can be rerun at appropriate points of data growth with minimal loss of accuracy, even when data growth is unbounded. Our specific algorithm directly adapts the private multiplicative weights algorithm to the dynamic setting, maintaining the accuracy guarantee of the static setting through unbounded data growth. Along the way, we develop extensions of several other differentially private algorithms to the dynamic setting, which may be of independent interest for future work on the design of differentially private algorithms for growing databases.