Bounding the Sample Size of a Machine Learning Algorithm

One common problem with machine learning algorithms is that we don't know how much training data we need. A common way around this is the often used strategy: keep training until the training error stops decreasing. However, there are still issues with this. How do we know we're not stuck in a local minimum? What if the training error has strange behavior, sometimes staying flat over training iterations but sometimes decreasing sharply?