Sample size with respect to prediction in classification and regression With respect to hypothesis testing, estimating samples sizes is done through
power, and it is intuitive that increasing the same size increases
the precision of estimated effects. But what about prediction for both
classification and regression? What aspects of the prediction problem
are influenced by sample size other than estimating the generalization error or
RMSE for regression. 
In sum, properties that contribute to power in the hypothesis-testing setting differ from those that those that enable successful prediction through penalized regression/data mining/algorithmic modeling. How does sample size influence the success of these techniques?
One paper that describes this idea is this one. 
Can anyone provide references for their comments? Thanks.
 A: Basically, I think you ask intuitively how sample size affects machine learning techniques. So, the real factor that affects the required sample sizes is dimensionality of the space that data live in, and its sparseness. I will give you two examples, because I find it hard to summarise everything in one... 


*

*Let's say you have some dense data and you try to fit a model using some regression. If the data follow a polynomial of degree $n$ then you need more that $n$ data so your algorithm can find the correct curve. Otherwise, it will make an over-simplistic model, different than reality. Of course in reality there will be noise, so you need even more data to make a better model.

*Let's say you have some sparse data, i.e., most dimensions are zeros. Such an example is text, like tweets or SMS (forget books for now), where the frequency of each word is a dimension and of course documents don't have the majority of the words in the dictionary (sparse space).
You try to classify tweets based on their topic. Algorithms, like kNN, SVMs etc, work on similarities between samples, e.g. 1-NN will find the tweet in the training set closest to the one that you try to classify and it will assign the corresponding label. However, because of the sparseness... guess what... most similarities are zero! Simply because documents don't share enough words. To be able to make predictions you need enough data so that something in your training set resembles the unknown documents you try to classify. Of course since it is a continuous space you can never fill all the gaps between samples... but the more data you put in, the higher the chance that the unknown sample will find something similar in the training set. 
A: I dont understand the question fully. Generally a bigger sample will yield (for example) a better classification. Unless bigger means bad quality observations. A small sample will make a lot of models useless. For example since tree based models are a sort of "divde and conquer" approach their efficiency depends a lot on the size of the training sample.
On the other hand, if you are interested in statistical learning in high dimensions I think your concern has more to do with the curse of dimensionality. If your sample size is "small" and your feature space is of a "high" dimension your data will behave as if it were sparse and most algorithms will have a terrible time trying to make sense of it. Quoting John A. Richards in Remote Sensing Digital Image Analysis:

Feature Reduction and Separability
Classification cost increases with the number of features used to describe pixel vectors in multispectral space – i.e. with the number of spectral bands associated with a pixel. For classifiers such as the parallelepiped and minimum distance procedures this is
a linear increase with features; however for maximum likelihood classification, the
procedure most often preferred, the cost increase with features is quadratic. Therefore it is sensible economically to ensure that no more features than necessary are utilised when performing a classification. Section 8.2.6 draws attention to the number of training pixels needed to ensure that reliable estimates of class signatues can be obtained. In particular, the number of training pixels required increases with the number of bands or channels in the data. For high dimensionality data, such as that from imaging spectrometers, that requirement presents quite a challenge in practice, so keeping the number of features used in a classification to as few as possible is important if reliable results are to be expected from affordable numbers of training pixels. Features which do not aid discrimination, by contributing little to the separability of spectral classes, should be discarded. Removal of least effective features is referred to as feature selection, this being one form of feature reduction. The other is to transform the pixel vector into a new set of coordinates in which the features that can be removed are made more evident. Both procedures are considered in some detail in this chapter.

Which would mean that the problem is two-fold, finding relevant features and the samp size you mention. As of now you can dowload the book for free if you search for it on google.
Another way to read your question which particularly interests me would be this: in supervised learning you can only really validate your models on test data by cross validation and what not. If the labeled sample from which you obtained your train/test samples doesnt represent your universe well, the validation results might not apply for your universe. How can you measure representativeness of your labeled sample?
