  We study the accuracy of differentially private mechanisms in the continual
release model. A continual release mechanism receives a sensitive dataset as a
stream of $T$ inputs and produces, after receiving each input, an accurate
output on the obtained inputs. In contrast, a batch algorithm receives the data
as one batch and produces a single output.
  We provide the first strong lower bounds on the error of continual release
mechanisms. In particular, for two fundamental problems that are widely studied
and used in the batch model, we show that the worst case error of every
continual release algorithm is $\tilde \Omega(T^{1/3})$ times larger than that
of the best batch algorithm. Previous work shows only a polylogarithimic (in
$T$) gap between the worst case error achievable in these two models; further,
for many problems, including the summation of binary attributes, the
polylogarithmic gap is tight (Dwork et al., 2010; Chan et al., 2010). Our
results show that problems closely related to summation -- specifically, those
that require selecting the largest of a set of sums -- are fundamentally harder
in the continual release model than in the batch model.
  Our lower bounds assume only that privacy holds for streams fixed in advance
(the "nonadaptive" setting). However, we provide matching upper bounds that
hold in a model where privacy is required even for adaptively selected streams.
This model may be of independent interest.
