Medición y análisis de la complejidad de las muestras

Question

Hace poco me topé con el concepto de complejidad de la muestra y me preguntaba si existe algún texto, documento o tutorial que proporcione:

1. Una introducción al concepto (rigurosa o informal)
2. Un análisis de la complejidad muestral de los métodos de clasificación establecidos y populares o métodos kernel.
3. Consejos o información sobre cómo medirlo en la práctica.

Cualquier ayuda sobre el tema será muy apreciada.

Answer 1

Supongamos que queremos acotar el riesgo empírico de un modelo. Dado un $(\epsilon, \delta)$ la complejidad de la muestra es $n(\epsilon, \delta)$ tal que para $n\geq n(\epsilon, \delta)$ $$ P(|\hat{L}(f) - L(f) | \geq \epsilon ) \leq \delta $$ La función $\delta(n,\epsilon)$ es un límite a la desviación del riesgo (pérdida) principal (desconocido).

Como intuición de nivel superior: La complejidad de la muestra es el menor número de muestras para el que podemos estar seguros de que nos acercamos lo suficiente al modelo correcto.