  Recent advances have enabled "oracle" classifiers that can classify across
many classes and input distributions with high accuracy without retraining.
However, these classifiers are relatively heavyweight, so that applying them to
classify video is costly. We show that day-to-day video exhibits highly skewed
class distributions over the short term, and that these distributions can be
classified by much simpler models. We formulate the problem of detecting the
short-term skews online and exploiting models based on it as a new sequential
decision making problem dubbed the Online Bandit Problem, and present a new
algorithm to solve it. When applied to recognizing faces in TV shows and
movies, we realize end-to-end classification speedups of 2.4-7.8x/2.6-11.2x (on
GPU/CPU) relative to a state-of-the-art convolutional neural network, at
competitive accuracy.
