Sobre el estado de la capacidad de aprendizaje dentro de

Estoy tratando de entender la complejidad de las funciones que se expresan a través de las puertas de umbral y esto me llevó a . En particular, estoy interesado en lo que se sabe actualmente sobre el aprendizaje dentro de , ya que no soy un experto en el área. $\mathsf{TC}^0$ $\mathsf{TC}^0$

Lo que he descubierto hasta ahora es:

Todo se puede aprender en tiempo cuasipolinomial bajo la distribución uniforme a través de Linial-Mansour-Nisan . $\mathsf{AC}^0$
Su artículo también señala que la existencia de un generador de funciones pseudoaleatorio impide el aprendizaje, y esto, junto con un resultado posterior de Naor-Reingold de que admite PRFG, sugiere que representa los límites de la capacidad de aprendizaje (al menos en un PAC -sentido) $\mathsf{TC}^0$ $\mathsf{TC}^0$
Hay un artículo de 2002 de Jackson / Klivans / Servedio que puede aprender un fragmento de (con, como máximo, puertas de mayoría pollogarítmica). $\mathsf{TC}^0$

Hice la investigación habitual en Google, pero espero que la sabiduría colectiva de cstheory pueda tener una respuesta más rápida:

¿Es lo que describí el estado del arte para nuestra comprensión de la complejidad del aprendizaje (en términos de qué clases emparejan a los estudiantes eficientes)? ¿Y hay una buena encuesta / referencia que traza el estado actual del paisaje?

cc.complexity-theory reference-request cr.crypto-security lg.learning boolean-functions Suresh Venkat
fuente

+1 Buena pregunta. ¿No tenía Lance una publicación de blog relacionada hace algún tiempo?

Kaveh

¿Te refieres a este (post invitado por Ryan O'Donnell): blog.computationalcomplexity.org/2005/08/…

Suresh Venkat

Tal vez este: blog.computationalcomplexity.org/2013/08/…

Suresh Venkat

Es plausible que haya generadores pseudoaleatorios en NC0 .

$\:$ (En particular, me parece muy poco probable que se sepa que un generador pseudoaleatorio impide el aprendizaje).

$\;\;\;$ Por otro lado, la existencia de los mapas.

x \mapsto F (r, x)

$\: x\mapsto F(r\hspace{-0.03 in},x) \:$ para una función pseudoaleatoria, la familia

impide el aprendizaje.

F

$F$

Linial-Mansour-Nisan muestran que

se puede aprender bajo la distribución uniforme en tiempo cuasipolinomial . Kharitinov demostró que si el cuasipolinomio se mejorara a polinomio, produciría un algoritmo de tiempo sub-exponencial para factorizar enteros de Blum.

{AC}^{0}

$\text{AC}^0$

Robin Kothari

Respuestas:

Lo principal que falta en su lista es el hermoso artículo de 2006 de Klivans y Sherstov . Demuestran allí que el aprendizaje PAC, incluso los circuitos de umbral de profundidad 2 es tan difícil como resolver el problema de vector más corto aproximado.

Scott Aaronson
fuente

¿Cuál es el tiempo de ejecución más rápido conocido para aprender tales circuitos LTF? (o cualquier cosa dentro de

)

T C^{0}

$TC^0$

graduado estudiante

Profundidad-2 TC0 probablemente no se puede aprender PAC en tiempo subexponencial sobre la distribución uniforme con un acceso al oráculo aleatorio. No conozco una referencia para esto, pero aquí está mi razonamiento: sabemos que la paridad apenas se puede aprender, en el sentido de que la clase de funciones de paridad se puede aprender en sí misma, pero una vez que le haces casi cualquier cosa (tal como agregar un poco de ruido aleatorio), deja de ser aprendible. Pero la profundidad-2 TC0 es lo suficientemente fuerte como para representar todas las funciones de paridad y lo suficientemente fuerte como para representar versiones perturbadas de paridades, por lo que creo que es seguro adivinar que la profundidad-2 TC0 no se puede aprender PAC.

Sin embargo, las paridades y las paridades ruidosas se pueden aprender en tiempo polinómico si se nos da un oráculo de membresía. Por lo tanto, puede ser interesante comprobar si se puede aprender la profundidad-2 TC0 utilizando un oráculo de membresía. No me sorprendería totalmente si la respuesta es sí. Por otro lado, dudo que -prpth TC0 se pueda aprender con consultas de membresía. Puede ser bueno comenzar con AC0 [6] (o incluso AC0 [2]) e ir desde allí. $O(1)$

bola de masa de mobius
fuente