Sobre o status de aprendizagem dentro de

Estou tentando entender a complexidade das funções expressáveis através de portas de limiar e isso me levou a . Em particular, estou interessado no que se sabe atualmente sobre o aprendizado no , pois não sou especialista na área. $\mathsf{TC}^0$ $\mathsf{TC}^0$

O que eu descobri até agora é:

Todos os podem ser aprendidos em tempo quase-polinomial sob a distribuição uniforme via Linial-Mansour-Nisan . $\mathsf{AC}^0$
Seu trabalho também aponta que a existência de um gerador de função pseudo-aleatória impede o aprendizado, e isso, juntamente com um resultado posterior de Naor-Reingold de que admite PRFGs, sugere que representa os limites da capacidade de aprendizagem (pelo menos em um PAC -sentido) $\mathsf{TC}^0$ $\mathsf{TC}^0$
Existe um artigo de 2002 de Jackson / Klivans / Servedio que pode aprender um fragmento de (com, no máximo, portas majoritárias polilogarítmicas). $\mathsf{TC}^0$

Eu fiz a pesquisa usual no Google, mas espero que a sabedoria coletiva da história possa ter uma resposta mais rápida:

É o que descrevi o estado da arte para nossa compreensão da complexidade da aprendizagem (em termos de quais classes imprimem aos alunos eficientes)? E existe uma boa pesquisa / referência que mapeia o estado atual da paisagem?

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

+1 boa pergunta. Lance não tinha um post relacionado há algum tempo?

Kaveh

Você quer dizer este (hóspede post por Ryan O'Donnell): blog.computationalcomplexity.org/2005/08/...

Suresh Venkat

Talvez este: blog.computationalcomplexity.org/2013/08/…

Suresh Venkat 04/04

É plausível que haja geradores pseudo-aleatórios no NC0 .

$\:$ (Em particular, acho muito improvável que um gerador pseudo-aleatório seja conhecido por impedir o aprendizado.)

$\;\;\;$ Por outro lado, a existência dos mapas

x \mapsto F (r, x)

$\: x\mapsto F(r\hspace{-0.03 in},x) \:$ para uma função pseudo-aleatória, a família

impede a aprendizagem.

F

$F$

Linial-Mansour-Nisan mostra que o

pode ser aprendido sob a distribuição uniforme no tempo quase-polinomial . Kharitinov mostrou que, se o quase-polinomial fosse aprimorado para polinomial, produziria um algoritmo de tempo subexponencial para fatorar números inteiros de Blum.

{AC}^{0}

$\text{AC}^0$

precisa saber é o seguinte

Respostas:

A principal coisa que falta na sua lista é o belo artigo de 2006 de Klivans e Sherstov . Eles mostram lá que o aprendizado de PAC, mesmo os circuitos de limiar de profundidade 2, é tão difícil quanto resolver o problema vetorial mais curto aproximado.

Scott Aaronson
fonte

Qual é o tempo de execução mais rápido conhecido por aprender esses circuitos LTF? (ou qualquer coisa dentro de

)

T C^{0}

$TC^0$

gradstudent

A profundidade-2 TC0 provavelmente não pode ser aprendida pelo PAC em tempo subexponencial na distribuição uniforme com um acesso aleatório ao oráculo. Não conheço uma referência para isso, mas eis o meu raciocínio: sabemos que a paridade é apenas dificilmente aprendível, no sentido de que a classe de funções de paridade é aprendida por si só, mas depois que você faz praticamente qualquer coisa a ela (como adicionando um pouco de ruído aleatório), deixa de ser aprendível. Mas a profundidade 2 do TC0 é forte o suficiente para representar todas as funções de paridade e forte o suficiente para representar versões perturbadas das paridades, então acho que é seguro adivinhar que a profundidade 2 do TC0 não pode ser aprendida pelo PAC.

Entretanto, paridades e paridades barulhentas podem ser aprendidas em tempo polinomial se recebermos um oráculo de associação. Portanto, pode ser interessante verificar se a profundidade 2 do TC0 pode ser aprendida usando um oráculo de associação. Eu não ficaria totalmente surpreso se a resposta fosse sim. Por outro lado, duvido que TC0 com profundidade possa ser aprendido com consultas de associação. Pode ser bom começar com AC0 [6] (ou mesmo AC0 [2]) e partir daí. $O(1)$

bolinho de massa mobius
fonte