  We propose Impatient Deep Neural Networks (DNNs) which deal with dynamic time
budgets during application. They allow for individual budgets given a priori
for each test example and for anytime prediction, i.e., a possible interruption
at multiple stages during inference while still providing output estimates. Our
approach can therefore tackle the computational costs and energy demands of
DNNs in an adaptive manner, a property essential for real-time applications.
Our Impatient DNNs are based on a new general framework of learning dynamic
budget predictors using risk minimization, which can be applied to current DNN
architectures by adding early prediction and additional loss layers. A key
aspect of our method is that all of the intermediate predictors are learned
jointly. In experiments, we evaluate our approach for different budget
distributions, architectures, and datasets. Our results show a significant gain
in expected accuracy compared to common baselines.
