Limite inferior da amostragem agnóstica do PAC

É 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. $\Omega(d/\varepsilon)$ $\varepsilon$ $d$

Sabe-se que exemplos de são necessários no caso agnóstico? $\Omega(d/\varepsilon^2)$

lg.learning machine-learning Aryeh
fonte

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.

m = O (1 / ϵ^{2})

$m = O(1/\epsilon^2)$

ϵ

$\epsilon$

f_{1}

$f_1$

f_{2}

$f_2$

p_{1} = p_{2} + ϵ

$p_1 = p_2 + \epsilon$

O (1 / ϵ)

$O(1/\epsilon)$

Aaron Roth

Nomeadamente, acho que o limite de Hoeffding é apertado em para . Eu acho que o raciocínio acima é geralmente conhecido ...

p = 1 / 2

$p=1/2$

O (1 / ϵ^{2})

$O(1/\epsilon^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:

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