  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.
