Limite inferior da amostragem agnóstica do PAC

10

É sabido que, para a aprendizagem clássica do PAC, exemplos de são necessários para obter um erro vinculado a whp, onde é a dimensão VC da classe conceitual.ε dΩ(d/ε)εd

Sabe-se que exemplos de são necessários no caso agnóstico?Ω(d/ε2)

Aryeh
fonte
3
Não tenho certeza de como o limite inferior se parece, deve existir se o limite de Hoefding estiver apertado (e acho que sim). Esse limite indica que, para 1 fn, se a probabilidade de erro for p, será necessário no máximo amostras para estimar p com erro + - whp Portanto, considere qualquer classe de conceito com 2 conceitos, e e VC-dimensão 2. Faça uma distribuição sobre exemplos para que (ou vice-versa) - isso é possível porque a dimensão VC é 2. Parece que um algoritmo usando apenas exemplos implicariam um limite Hoefding aprimorado. ϵ f 1 f 2 p 1 = p 2 + ϵ O ( 1 / ϵ )m=O(1/ϵ2)ϵf1f2p1=p2+ϵO(1/ϵ)
Aaron Roth
11
Nomeadamente, acho que o limite de Hoeffding é apertado em para . Eu acho que o raciocínio acima é geralmente conhecido ...O ( 1 / ε 2 )p=1/2O(1/ϵ2)
Lev Reyzin
OK - parece que eu tenho outro exercício para o curso de ML ... :) Obrigado pela contribuição, Aaron e Lev!
Aryeh
@ Aaron, talvez isso devesse ter sido uma resposta.
precisa

Respostas:

6

Agora percebo que, de fato, Anthony e Bartlett estabeleceram um limite inferior (veja a apresentação aqui ).

Edit 24-Sep-2018. Essa pergunta me manteve ocupada todos esses anos e, recentemente, eu. Pinelis e eu obtivemos a constante ótima exata no limite inferior agnóstico do PAC para aparecer em Ann. Stat .

Aryeh
fonte
No seu artigo, você não cita este trabalho ( jmlr.org/papers/volume17/15-389/15-389.pdf ). A complexidade ideal da amostra limita-se no caso realizável a nenhuma conexão com seu trabalho? Esses limites superiores correspondentes da complexidade ótima da amostra são conhecidos para o caso agnóstico?
gradstudent
Não acho que o caso realizável esteja relacionado a isso. No caso realizável, o ERM não garante taxas ideais - portanto, todo o trabalho árduo que Hanneke e outros tiveram que gastar para remover o fator de log, e ainda não se sabe se um aluno adequado pode atingir a taxa ideal. Por outro lado, no caso agnóstico, sabe-se há muito tempo que o ERM atinge a taxa ideal.
Aryeh