Early Time Classification with Accumulated Accuracy Gap Control
Liran Ringel Regev Cohen Daniel Freedman Michael Elad Yaniv Romano
Early time classification algorithms aim to label a stream of features
without processing the full input stream, while maintaining accuracy comparable
to that achieved by applying the classifier to the entire input. In this paper,
we introduce a statistical framework that can be applied to any sequential
classifier, formulating a calibrated stopping rule. This data-driven rule
attains finite-sample, distribution-free control of the accuracy gap between
full and early-time classification. We start by presenting a novel method that
builds on the Learn-then-Test calibration framework to control this gap
marginally, on average over i.i.d. instances. As this algorithm tends to yield
an excessively high accuracy gap for early halt times, our main contribution is
the proposal of a framework that controls a stronger notion of error, where the
accuracy gap is controlled conditionally on the accumulated halt times.
Numerical experiments demonstrate the effectiveness, applicability, and
usefulness of our method. We show that our proposed early stopping mechanism
reduces up to 94% of timesteps used for classification while achieving rigorous
accuracy gap control.