  Machine learning, already at the core of increasingly many systems and
applications, is set to become even more ubiquitous with the rapid rise of
wearable devices and the Internet of Things. In most machine learning
applications, the main focus is on the quality of the results achieved (e.g.,
prediction accuracy), and hence vast amounts of data are being collected,
requiring significant computational resources to build models. In many
scenarios, however, it is infeasible or impractical to set up large centralized
data repositories. In personal health, for instance, privacy issues may inhibit
the sharing of detailed personal data. In such cases, machine learning should
ideally be performed on wearable devices themselves, which raises major
computational limitations such as the battery capacity of smartwatches. This
paper thus investigates frugal learning, aimed to build the most accurate
possible models using the least amount of resources. A wide range of learning
algorithms is examined through a frugal lens, analyzing their accuracy/runtime
performance on a wide range of data sets. The most promising algorithms are
thereafter assessed in a real-world scenario by implementing them in a
smartwatch and letting them learn activity recognition models on the watch
itself.
