Sequential Multivariate Change Detection with Calibrated and Memoryless
  False Detection Rates
  Responding appropriately to the detections of a sequential change detector
requires knowledge of the rate at which false positives occur in the absence of
change. Setting detection thresholds to achieve a desired false positive rate
is challenging. Existing works resort to setting time-invariant thresholds that
focus on the expected runtime of the detector in the absence of change, either
bounding it loosely from below or targeting it directly but with asymptotic
arguments that we show cause significant miscalibration in practice. We present
a simulation-based approach to setting time-varying thresholds that allows a
desired expected runtime to be accurately targeted whilst additionally keeping
the false positive rate constant across time steps. Whilst the approach to
threshold setting is metric agnostic, we show how the cost of using the popular
quadratic time MMD estimator can be reduced from $O(N^2B)$ to $O(N^2+NB)$
during configuration and from $O(N^2)$ to $O(N)$ during operation, where $N$
and $B$ are the numbers of reference and bootstrap samples respectively.
