# Measuring and analyzing sample complexity

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).