Sur l'état de l'apprentissage dans

J'essaie de comprendre la complexité des fonctions exprimables via les portes de seuil et cela m'a conduit à . En particulier, je suis intéressé par ce que l'on sait actuellement sur l'apprentissage dans , car je ne suis pas un expert dans le domaine. $\mathsf{TC}^0$ $\mathsf{TC}^0$

Ce que j'ai découvert jusqu'à présent, c'est:

Tout peut être appris en temps quasi-polynomial sous la distribution uniforme via Linial-Mansour-Nisan . $\mathsf{AC}^0$
Leur article souligne également que l'existence d'un générateur de fonction pseudo-aléatoire empêche l'apprentissage, et cela, couplé à un résultat ultérieur de Naor-Reingold selon lequel admet les PRFG, suggère que représente les limites d'apprentissage (au moins dans un sens PAC) $\mathsf{TC}^0$ $\mathsf{TC}^0$
Il y a un article de 2002 de Jackson / Klivans / Servedio qui peut apprendre un fragment de (avec au plus des portes à majorité polylogarithmique). $\mathsf{TC}^0$

J'ai fait la recherche Google habituelle, mais j'espère que la sagesse collective de cstheory pourrait avoir une réponse plus rapide:

Est-ce que j'ai décrit l'état de l'art pour notre compréhension de la complexité de l'apprentissage (en termes de quelles classes prennent en sandwich des apprenants efficaces)? Et y a-t-il une bonne enquête / référence qui cartographie l'état actuel du paysage?

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

+1 Belle question. Lance n'avait-il pas un article de blog connexe il y a quelque temps?

Kaveh

Voulez-vous dire celui-ci (article invité de Ryan O'Donnell): blog.computationalcomplexity.org/2005/08/…

Suresh Venkat

Peut-être celui-ci: blog.computationalcomplexity.org/2013/08/…

Suresh Venkat

Il est plausible qu'il existe des générateurs pseudo-aléatoires dans NC0 . (En particulier, je trouve très peu probable qu'un générateur pseudo-aléatoire soit connu pour empêcher l'apprentissage.)En revanche, l'existence des cartes pour une famille de fonctions pseudo-aléatoires empêche l'apprentissage.

$\:$

$\;\;\;$

x \mapsto F (r, x)

$\: x\mapsto F(r\hspace{-0.03 in},x) \:$

F

$F$

Linial-Mansour-Nisan montre que peut être appris sous la distribution uniforme en temps quasipolynomial . Kharitinov a montré que si le quasipolynôme était amélioré en polynôme, cela produirait un algorithme de temps sous-exponentiel pour factoriser les entiers de Blum.

{AC}^{0}

$\text{AC}^0$

Robin Kothari

Réponses:

La principale chose qui manque à votre liste est le magnifique papier 2006 de Klivans et Sherstov . Ils y montrent que l'apprentissage par PAC même des circuits de seuil de profondeur 2 est aussi difficile que de résoudre le problème de vecteur le plus court approximatif.

Scott Aaronson
la source

Quel est le temps d'exécution le plus rapide connu pour l'apprentissage de tels circuits LTF? (ou quoi que ce soit à l'intérieur de

)

T C^{0}

$TC^0$

étudiant diplômé le

La profondeur-2 TC0 ne peut probablement pas être apprise par PAC en temps sous-exponentiel sur la distribution uniforme avec un accès aléatoire à l'oracle. Je ne connais pas de référence pour cela, mais voici mon raisonnement: nous savons que la parité est à peine apprenable, dans le sens où la classe des fonctions de parité est apprenable en soi, mais une fois que vous faites à peu près tout ( comme ajoutant un peu de bruit aléatoire), il cesse d'être apprenable. Mais la profondeur-2 TC0 est assez forte pour représenter toutes les fonctions de parité et assez forte pour représenter les versions perturbées des parités, donc je pense qu'il est sûr de deviner que la profondeur-2 TC0 ne peut pas être apprise par PAC.

$O(1)$

boulette de Mobius
la source