  SafePredict is a novel meta-algorithm that works with any base prediction
algorithm for online data to guarantee an arbitrarily chosen correctness rate,
$1-\epsilon$, by allowing refusals. Allowing refusals means that the
meta-algorithm may refuse to emit a prediction produced by the base algorithm
on occasion so that the error rate on non-refused predictions does not exceed
$\epsilon$. The SafePredict error bound does not rely on any assumptions on the
data distribution or the base predictor. When the base predictor happens not to
exceed the target error rate $\epsilon$, SafePredict refuses only a finite
number of times. When the error rate of the base predictor changes through time
SafePredict makes use of a weight-shifting heuristic that adapts to these
changes without knowing when the changes occur yet still maintains the
correctness guarantee. Empirical results show that (i) SafePredict compares
favorably with state-of-the art confidence based refusal mechanisms which fail
to offer robust error guarantees; and (ii) combining SafePredict with such
refusal mechanisms can in many cases further reduce the number of refusals. Our
software (currently in Python) is included in the supplementary material.
