The mean of a population of binary values can be sampled with about 1000 samples at 95% confidence, and 3000 samples at 99% confidence.  Assuming a binary classification problem, why is the 80/20% rule always used, and not the fact that with a few thousand samples the mean accuracy can be estimated with > 95% confidence?
What is the minimum size of the test set?
statistics;cross validation;ab test
This is a great question since it is illuminating to examination the best practices of both about traditional statistics and machine learning as they are brought together.Two Separate Rules/Best Practices -First, the two items that you mentioned should be examined separately and not conflated i.e. they should be carefully combined as you suggest in your question.Significance: You have estimated that you want greater than 1000 cases to have statistical significance and would further benefit from greater than 3000 test cases.Cross validation: Cross validation is performed by splitting the data (often 80% train-20% test) so that tests for bias (~underfitting) and variance (~overfitting) can be assessed.Combining significance with cross validation: Now we know that we want to have significance in our tests so we want greater than 3000 records.  We also want to perform cross validation, so in order for both the testing and training data to return significant results we want both to have a minimum of 3000 records.  The best scenario for this would be to have 15,000 total records. This way, the data can be split 80/20 and the testing set is still significant.Lets assume you only have 4000 records in your data set. In this case, I would opt to make my training data significant while allowing the testing set to drop to lower significance.More rigor: Everything above has been quite hand wavey and lacks statistical rigor. For this, I refer you to a couple of papers referenced in another Stack Exchange question -  Dietterich, Approximate Statistical Tests for ComparingSupervised Classication Learning AlgorithmsSalzberg, Data Mining and Knowledge Discovery, 1, 317327 (1997), On Comparing Classifiers: Pitfalls to Avoid and aRecommended Approach.Hope this helps!