I recently stumbled upon the concept of sample complexity, and was wondering if there are any texts, papers or tutorials that provide:

  1. An introduction to the concept (rigorous or informal)
  2. An analysis of the sample complexity of established and popular classification methods or kernel methods.
  3. Advice or information on how to measure it in practice.

Any help with the topic would be greatly appreciated.


Let's say we want to bound empirical risk of a model. Given an arbitrary $(\epsilon, \delta)$, the sample complexity is $n(\epsilon, \delta)$ such that for $n\geq n(\epsilon, \delta)$ $$ P(|\hat{L}(f) - L(f) | \geq \epsilon ) \leq \delta $$ The function $\delta(n,\epsilon)$ is a bound on the deviation from the main (unknown) risk (loss).

As a higher-level intuition: Sample complexity is the smallest number of samples for which we can make sure that we are close enough to the correct model.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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