Quit When You Can: Efficient Evaluation of Ensembles with Ordering
  Optimization
  Given a classifier ensemble and a set of examples to be classified, many
examples may be confidently and accurately classified after only a subset of
the base models in the ensemble are evaluated. This can reduce both mean
latency and CPU while maintaining the high accuracy of the original ensemble.
To achieve such gains, we propose jointly optimizing a fixed evaluation order
of the base models and early-stopping thresholds. Our proposed objective is a
combinatorial optimization problem, but we provide a greedy algorithm that
achieves a 4-approximation of the optimal solution for certain cases. For those
cases, this is also the best achievable polynomial time approximation bound
unless $P = NP$. Experiments on benchmark and real-world problems show that the
proposed Quit When You Can (QWYC) algorithm can speed-up average evaluation
time by $2$x--$4$x, and is around $1.5$x faster than prior work. QWYC's joint
optimization of ordering and thresholds also performed better in experiments
than various fixed orderings, including gradient boosted trees' ordering.
