  From scientific experiments to online A/B testing, the previously observed
data often affects how future experiments are performed, which in turn affects
which data will be collected. Such adaptivity introduces complex correlations
between the data and the collection procedure. In this paper, we prove that
when the data collection procedure satisfies natural conditions, then sample
means of the data have systematic \emph{negative} biases. As an example,
consider an adaptive clinical trial where additional data points are more
likely to be tested for treatments that show initial promise. Our surprising
result implies that the average observed treatment effects would underestimate
the true effects of each treatment. We quantitatively analyze the magnitude and
behavior of this negative bias in a variety of settings. We also propose a
novel debiasing algorithm based on selective inference techniques. In
experiments, our method can effectively reduce bias and estimation error.
