Explaining Two Strange Learning Curves

Learning curves illustrate how generalization performance of a learner evolves with more training data. While this is a useful tool to characterize learners, not all learning curve behavior is well understood. For instance, it is sometimes assumed that the more training data provided, the better the learner performs. However, counter-examples exist for both classical machine learning algorithms and deep neural networks, where errors do not monotonically decrease with training set size. Loog et al. [12] describe this monotonicity problem, and present several regression examples where simple empirical risk minimizers display unexpected learning curve behaviors. In this paper, we will study two of these proposed problems in detail and explain what caused the odd learning curves. For the first, we use a bias-variance decomposition to show that the monotonic increase in the learning curve is caused by an increase in the variance, which we explain by a mismatch between the model and the data generating process. For the second problem, we explain the recurring increases in the learning curve by showing only two solutions are attainable by the learner. The probability of obtaining a configuration of training objects that leads to the high risk solution typically decreases as the training set size increases. However, for particular training set sizes, additional configurations that produce the high risk solution become possible. We prove that these additional configurations increase the probability of the high risk solution and therefore explain the unusual learning curve. These examples contribute to a more complete understanding of learning curves and the possibilities and reasons behind their various behaviors.