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?