Sample complexity

In machine learning, the sample complexity of a machine learning algorithm is, roughly speaking, the number of training samples needed for the algorithm to successfully learn a target function. More specifically, the sample complexity is the number of samples needed for the function returned by the algorithm to be within an arbitrarily small error of the best possible function, with probability arbitrarily close to 1.