  In many recent applications, data is plentiful. By now, we have a rather
clear understanding of how more data can be used to improve the accuracy of
learning algorithms. Recently, there has been a growing interest in
understanding how more data can be leveraged to reduce the required training
runtime. In this paper, we study the runtime of learning as a function of the
number of available training examples, and underscore the main high-level
techniques. We provide some initial positive results showing that the runtime
can decrease exponentially while only requiring a polynomial growth of the
number of examples, and spell-out several interesting open problems.
