¿Es posible el aprendizaje PAC eficiente con un oráculo que responde 'Sí' o 'No'?

El principio de minimización del riesgo empírico (ERM) ha tenido un gran impacto en el aprendizaje automático, lo que ha llevado tanto a garantías teóricas casi óptimas para algoritmos de aprendizaje basados en ERM como a impulsar muchos de los recientes éxitos empíricos en el aprendizaje profundo. En este artículo, investigamos la pregunta de si la capacidad de realizar ERM, que computa una hipótesis que minimiza el riesgo empírico en un conjunto de datos dado, es necesaria para el aprendizaje eficiente: en particular, ¿existe un oráculo más débil que el ERM que, sin embargo, puede permitir la aprendibilidad? Respondemos afirmativamente a esta pregunta, mostrando que en el entorno realizable del aprendizaje PAC para clasificación binaria, una clase de conceptos puede ser aprendida usando un oráculo que solo devuelve un solo bit que indica si un conjunto de datos dado es realizable por algún concepto en la clase. La complejidad de muestra y la complejidad del oráculo de nuestro algoritmo dependen polinómicamente de la dimensión VC de la clase de hipótesis, mostrando así que solo hay un costo polinómico a pagar por el uso de nuestro oráculo más débil. Nuestros resultados se extienden al entorno de aprendizaje agnóstico con un ligero fortalecimiento del oráculo, así como a los entornos de aprendizaje de concepto parcial, multiclase y de valores reales. En el contexto de las clases de conceptos parciales, antes de nuestro trabajo no se conocían algoritmos eficientes en términos de oráculo, incluso con un oráculo ERM estándar. Por lo tanto, nuestros resultados abordan una pregunta de Alon et al. (2021) que preguntaron si existen principios algorítmicos que permitan la aprendibilidad eficiente en este contexto.