  Learning curves are a measure for how the performance of machine learning
models improves given a certain volume of training data. Over a wide variety of
applications and models it was observed that learning curves follow -- to a
large extent -- a power law behavior. This makes the performance of different
models for a given task somewhat predictable and opens the opportunity to
reduce the training time for practitioners, who are exploring the space of
possible models and hyperparameters for the problem at hand. By estimating the
learning curve of a model from training on small subsets of data only the best
models need to be considered for training on the full dataset. How to choose
subset sizes and how often to sample models on these to obtain estimates is
however not researched. Given that the goal is to reduce overall training time
strategies are needed that sample the performance in a time-efficient way and
yet leads to accurate learning curve estimates. In this paper we formulate the
framework for these strategies and propose several strategies. Further we
evaluate the strategies for simulated learning curves and in experiments with
popular datasets and models for image classification tasks.
