  Multiple lines of evidence suggest that predictive models may benefit from
algorithmic triage. Under algorithmic triage, a predictive model does not
predict all instances but instead defers some of them to human experts.
However, the interplay between the prediction accuracy of the model and the
human experts under algorithmic triage is not well understood. In this work, we
start by formally characterizing under which circumstances a predictive model
may benefit from algorithmic triage. In doing so, we also demonstrate that
models trained for full automation may be suboptimal under triage. Then, given
any model and desired level of triage, we show that the optimal triage policy
is a deterministic threshold rule in which triage decisions are derived
deterministically by thresholding the difference between the model and human
errors on a per-instance level. Building upon these results, we introduce a
practical gradient-based algorithm that is guaranteed to find a sequence of
triage policies and predictive models of increasing performance. Experiments on
a wide variety of supervised learning tasks using synthetic and real data from
two important applications -- content moderation and scientific discovery --
illustrate our theoretical results and show that the models and triage policies
provided by our gradient-based algorithm outperform those provided by several
competitive baselines.
