  Anomaly detection aims at detecting unexpected behaviours in the data.
Because anomaly detection is usually an unsupervised task, traditional anomaly
detectors learn a decision boundary by employing heuristics based on
intuitions, which are hard to verify in practice. This introduces some
uncertainty, especially close to the decision boundary, that may reduce the
user trust in the detector's predictions. A way to combat this is by allowing
the detector to reject examples with high uncertainty (Learning to Reject).
This requires employing a confidence metric that captures the distance to the
decision boundary and setting a rejection threshold to reject low-confidence
predictions. However, selecting a proper metric and setting the rejection
threshold without labels are challenging tasks. In this paper, we solve these
challenges by setting a constant rejection threshold on the stability metric
computed by ExCeeD. Our insight relies on a theoretical analysis of such a
metric. Moreover, setting a constant threshold results in strong guarantees: we
estimate the test rejection rate, and derive a theoretical upper bound for both
the rejection rate and the expected prediction cost. Experimentally, we show
that our method outperforms some metric-based methods.
