So, imagine having access to sufficient data (millions of datapoints for training and testing) of sufficient quality. Please ignore concept drift for now and assume the data static and does not change over time. Does it even make sense to use all of that data in terms of the quality of the model?

Brain and Webb (http://www.csse.monash.edu.au/~webb/Files/BrainWebb99.pdf) have included some results on experimenting with different dataset sizes. Their tested algorithms converge to being somewhat stable after training with 16,000 or 32,000 datapoints. However, since we're living in the big data world we have access to data sets of millions of points, so the paper is somewhat relevant but hugely outdated.

Is there any know more recent research on the impact of dataset sizes on learning algorithms (Naive Bayes, Decision Trees, SVM, neural networks etc).

When does a learning algorithm converge to a certain stable model for which more data does not increase the quality anymore? Can it happen after 50,000 datapoints, or maybe after 200,000 or only after 1,000,000? Is there a rule of thumb? Or maybe there is no way for an algorithm to converge to a stable model, to a certain equilibrium? Why am I asking this? Imagine a system with limited storage and a huge amount of unique models (thousands of models with their own unique dataset) and no way of increasing the storage. So limiting the size of a dataset is important.

Any thoughts or research on this?

  • $\begingroup$ Great question, and one that seems to be ignored. Would be great if someone has references. I frequently see manuscripts based on complex models and <2k observations: ncbi.nlm.nih.gov/pubmed/23364879stacked models $\endgroup$
    – charles
    Commented Sep 5, 2014 at 0:17
  • $\begingroup$ why don't you work through some simple examples to clarify your ideas. eg how many samples do you need to estimate the mean? how does it depend on the dimension? $\endgroup$
    – seanv507
    Commented Oct 18, 2014 at 23:14

3 Answers 3


You are referring to what is known as Sample Complexity in the PAC learning framework. There has been significant amount of research in this area. In summary, in most real world cases, you never know what the true sample complexity is for a given dataset, however, you can bound it. The bounds typically are very loose and do not usually convey anything more than the order of examples required, to reach a particular error with a particular probability.

For instance, to reach a prediction error within epsilon, with a large probability (1 - delta), you may need the number of samples proportional to some function of epsilon and delta. For example, if your sample complexity is O(1/epsilon) you are better off than your complexity being (1/epsilon^2). That is, to reach 1% error rate, in the former case you need O(100) examples, and O(10000) in the second. But remember, these are still O(.) and not exact numbers.

If you look up sample complexity bounds of particular classes of algorithms, you'd get some idea. Some lecture notes here.


It depends both on the complexity of the model (the number of effective parameters) and the signal/noise ratio in the data. The higher the former and the lower the latter, the more data is necessary for convergence. Therefore, all those rules of thumb can't help being tied to a particular domain where some typical models are used and some average signal/noise ratio is assumed.

  • $\begingroup$ This is a valid comment, but that's why included the phrase "data of sufficient quality". Let's assume signal/noise ratio is average... there is noise, but not so much to pollute the data. The complexity of the model can also be regarded as sufficient complex to learn the data but not too complex to make the training to difficult. $\endgroup$ Commented Sep 5, 2014 at 9:09

Note that a dataset of few millions is not that big with respect to many real world use cases:

  • A black/white picture of 256 pixels has 2^256 possibilities.
  • Applying a "People that Like X also liked Y" is quadratic so an item set of 1,000 items already gets you into 1M. In general there are much more items and their distribution is long tail so you will need many samples to cover the rare items.
  • Languages are very sparse. A simple model of bigrams lead to a quadratic factor and here millions are not much too.

Other than that, data is a good way to improve the performance of algorithms. A classical paper on the topic is "The Unreasonable Effectiveness of Data".

For a formal treatment of the question we can use the concept of VC dimension. The VC dimension is a way to model the complexity of the hypothesis class that you are trying to represent. The more complex the class, the more samples you will need.

For example, you will need more samples in order to estimate the distribution of die than for the distribution of a coin.

Sample complexity is linear in the VC dimension. For any data set you will choose, there will be concept classes for which it will be too small.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.