Sample Complexity of Classification

We discuss basic sample complexity theory and it's impact on classification success evaluation, implications for learning algorithm design, and uses in learning algorithm execution. There are a two important implications of the results presented here: (1) Common practices for reporting results in classification should change to us the test set bound. (2) Train set bounds can sometimes be used to directly motivate learning algorithms