Muestra agnóstica de PAC límite inferior

Es bien sabido que para el aprendizaje PAC clásico, los ejemplos de son necesarios para lograr un límite de error de whp, donde es la dimensión VC de la clase de concepto. $\Omega(d/\varepsilon)$ $\varepsilon$ $d$

¿Se sabe que se necesitan ejemplos de en el caso agnóstico? $\Omega(d/\varepsilon^2)$

lg.learning machine-learning Aria
fuente

No estoy seguro de cómo se ve el límite inferior, uno debería existir si el límite de Hoefding es ajustado (y creo que lo es). Este límite establece que para 1 fn, si la probabilidad de error es p, entonces necesita como máximo

muestras para estimar p dentro del error + -

whp Entonces, considere cualquier clase de concepto con 2 conceptos,

y VC-dimensión 2. Tomar una distribución más ejemplos para que

(o viceversa) - esto es posible porque VC-dimensión es 2. parece que un algoritmo utilizando sólo

m = O (1 / ϵ^{2})

$m = O(1/\epsilon^2)$

ϵ

$\epsilon$

f_{1}

$f_1$

f_{2}

$f_2$

p_{1} = p_{2} + ϵ

$p_1 = p_2 + \epsilon$

ejemplos implicarían un límite Hoefding mejorado.

O (1 / ϵ)

$O(1/\epsilon)$

Aaron Roth

Es decir, creo que el Hoeffding ligados es apretado en

para

. Creo que el razonamiento anterior es generalmente conocido ...

p = 1 / 2

$p=1/2$

O (1 / ϵ^{2})

$O(1/\epsilon^2)$

Lev Reyzin

OK, parece que me hice otro ejercicio para el curso de ML ... :) ¡Gracias por el aporte, Aaron y Lev!

Aryeh

@ Aaron, tal vez esto debería haber sido una respuesta.

Suresh Venkat

Respuestas:

Ahora me doy cuenta de que Anthony y Bartlett han establecido un límite inferior (ver la presentación aquí ).

Edición 24-sep-2018. Esta pregunta me ha mantenido ocupado durante todos estos años, y recientemente, I. Pinelis y yo hemos obtenido la constante óptima exacta en el límite inferior de PAC agnóstico para aparecer en Ann. Stat .

Aria
fuente

En su artículo no cita este trabajo ( jmlr.org/papers/volume17/15-389/15-389.pdf ). ¿La complejidad óptima de la muestra no tiene ninguna conexión con su trabajo en el caso realizable? ¿Son estos límites superiores de complejidad de muestra óptima correspondientes conocidos para el caso agnóstico?

gradstudent

No creo que el caso realizable esté tan relacionado. En el caso realizable, ERM no garantiza tasas óptimas, de ahí todo el trabajo duro que Hanneke y otros tuvieron que gastar para eliminar el factor log, y aún se desconoce si un alumno adecuado puede lograr la tasa óptima. Por el contrario, en el caso agnóstico, se sabe desde hace mucho tiempo que ERM alcanza la tasa óptima.

Aryeh