  We propose a coupled bootstrap estimator for the test error of an arbitrary
algorithm that estimates the mean in a Poisson sequence, often called the
Poisson means problem. The idea behind our method is to generate two
carefully-designed data vectors from the original data vector, by using
synthetic binomial noise. One such vector acts as the training sample and the
second acts as the test sample. To stabilize the test error estimate, we
average this over multiple draws of the synthetic noise. A key property of our
coupled bootstrap estimator is that it is unbiased for the test error in a
problem where the original mean has been shrunken by a small factor, driven by
the success probability $p$ in the binomial noise. Further, in the limit as $p
\to 0$, we show that the proposed estimator recovers a known unbiased estimator
for the test error, under no assumptions on the algorithm at hand (in
particular, no smoothness assumptions). Our methodology applies to two central
loss functions that can be used to a test error metric: Poisson deviance and
squared loss. Through a bias-variance decomposition, for each loss function, we
analyze the effects of the binomial success probability and the number of
bootstrap samples and on the accuracy of the estimator. We also investigate our
method empirically across a variety of settings, using simulated as well as
real data.
