  Classification systems are often deployed in resource-constrained settings
where labels must be assigned to inputs on a budget of time, memory, etc.
Budgeted, sequential classifiers (BSCs) address these scenarios by processing
inputs through a sequence of partial feature acquisition and evaluation steps
with early-exit options. This allows for an efficient evaluation of inputs that
prevents unneeded feature acquisition. To approximate an intractable
combinatorial problem, current approaches to budgeted classification rely on
well-behaved loss functions that account for two primary objectives (processing
cost and error). These approaches offer improved efficiency over traditional
classifiers but are limited by analytic constraints in formulation and do not
manage additional performance objectives. Notably, such methods do not
explicitly account for an important aspect of real-time detection systems --
the fraction of "accepted" predictions satisfying a confidence criterion
imposed by a risk-averse monitor.
  We propose a problem-specific genetic algorithm to build budgeted, sequential
classifiers with confidence-based reject options. Three objectives -- accuracy,
processing time/cost, and coverage -- are considered. The algorithm emphasizes
Pareto efficiency while accounting for a notion of aggregate performance via a
unique scalarization. Experiments show our method can quickly find globally
Pareto optimal solutions in very large search spaces and is competitive with
existing approaches while offering advantages for selective, budgeted
deployment scenarios.
