As far as I know, much of the statistical and machine learning literature where modeling algorithms are compared for their generalization error performance as a function of sample size (think of Andrew Ng's famous graph of model performance as a function of size comparing "classical" statistical methods to neural networks) suffers from a critical error. Either training samples of varying size are taken from the exact same dataset or samples of varying size across varying study domains are used to make a claim about the performance of one algorithm or another.
Yet when we compare model performance by sample size using samples of varying size from the same dataset, we assume that the quality of data is constant across sample sizes. When we compare model performance across samples of varying size that come from separate study domains, our assessment of model performance as a function of sample size is confounded potentially by the signal-to-noise ratio of the study domain.
This is problematic because data quality is most likely dependent on sample size. For example, large samples mined from the web or a company's data warehouse have unknown biases that, in my experience, few analysts adequately account for, especially analysts trained in programs that focus heavily on data mining, model-fitting, and cross-validation techniques at the expense of sampling and measurement theory.
So are there any studies that address these issues in their comparison of various algorithms of varying computational sophistication and complexity? Am I mischaracterizing the literature when I say much of it is flawed in the way I've described?