Existem propriedades de distribuição que são "maximamente" difíceis de testar?

Um algoritmo de teste de distribuição para uma propriedade de distribuição P (que é apenas um subconjunto de todas as distribuições acima de [n]) tem acesso permitido às amostras de acordo com alguma distribuição D e é necessário decidir (whp) se ou ( aqui é geralmente a distância ). A medida de complexidade mais comum é o número de amostras usadas pelo algoritmo. $D\in P$ $d(D,P)>\epsilon$ $d$ $\ell_1$

Agora, no teste de propriedades padrão, em que você tem acesso à consulta para algum objeto, um limite inferior linear na complexidade da consulta é obviamente o limite inferior mais forte possível, pois consultas revelariam o objeto inteiro. Também é este o caso dos testes de distribuição? $n$

Até onde eu entendo, o limite superior "trivial" para testar propriedades de distribuições é --- pelos limites de Chernoff, isso é suficiente para "anotar" uma distribuição D 'que esteja próxima de D na distância , e então podemos apenas verificar se existem distribuições próximas a D 'que estão em P (isso pode levar um tempo infinito, mas isso é irrelevante para a complexidade da amostra). $O(n^2\log n)$ $\ell_1$

Existe um teste "trivial" melhor para todas as propriedades de distribuição?
Existem propriedades de distribuição para as quais sabemos que os limites inferiores da amostra são mais fortes que os lineares?

cc.complexity-theory machine-learning query-complexity property-testing Yonatan
fonte

parece semelhante a provar separações de classes de complexidade e como se estivesse perto de algum problema em aberto conhecido ...?

vzn

Acabei de ver isso ... Não tenho muita certeza de como você derivou o

ligado

, mas observe que, na verdade, aprendendo distribuições (sobre domínio de tamanho

O (n^{2} \log n)

$O(n^2\log n)$

) para TV /

distância

com probabilidade

na verdade pode ser feito comamostras de

(e isso é estanque). Portanto, a menos que você esteja observando valores não constantes do parâmetro de proximidade

, não há esperança de obter

n

$n$

ℓ_{1}

$\ell_1$

ε

$\varepsilon$

2 / 3

$2/3$

O (n / ε^{2})

$O(n/\varepsilon^2)$

ε

$\varepsilon$

ω (n)

$\omega(n)$ limites inferiores ...

Clement C.

Respostas:

Desculpe por desenterrar este post - ele é bastante antigo, mas achei que tê-lo respondido pode não ser tão ruim.

Primeiro, parece que você executou seu Chernoff ligado com uma configuração de parâmetros um pouco estranha. Observe que, para executar sua abordagem sugerida de "teste por aprendizado", é suficiente aprender a distribuição na distância total de variação (ou , se preferir, que é o mesmo até o fator 2) para a distância $\ell_1$ . (antes de verificar "offline" se houver alguma distribuiçãocom a propriedadeque, por sua vez, esteja à distância no máximo $\frac{\varepsilon}{2}$ $p'$ $\mathcal{P}_n$ do seu hipótese aprendeu ). Isso levaria ingenuamente a um $\frac{\varepsilon}{2}$ $\hat{p}$ limite superior da complexidade da amostra para esta abordagem; entretanto, sabe-se (e "folclore") que aprender uma distribuição arbitrária em um domínio de tamanhoaté a distância(na distância total da variação) pode ser feito apenas com $O\big(\frac{n\log n}{\varepsilon^2}\big)$ $n$ $\varepsilon$ amostras (e isso é apertado). $O(\frac{n}{\varepsilon^2})$

Portanto, a linha de base deve ser realmente , que já é linear em. Agora, pode-se fazer a próxima pergunta -existem propriedades "naturais" para as quais os testes (digamos, paraconstante) requerem uma dependência linear no tamanho do domínio? $O(\frac{n}{\varepsilon^2})$ $n$ $\varepsilon$ $n$

A resposta é (até onde eu sei) "não exatamente, mas próxima". Ou seja, seguindo uma linha significativa de trabalho na estimativa de propriedades de distribuições (ou equivalentemente, teste de propriedade tolerante), os resultados de Valiant e Valiant implicam (STOCS'11, FOCS'11 e alguns outros) que a propriedade bastante artificial "seja -close to uniform "tem complexidade de amostra $1/10$ $\Theta_\varepsilon(\frac{n}{\log n})$ .

(Observe que é um pouco "trapaceiro", no sentido de que a propriedade é simplesmente uma maneira de tomar uma pergunta de teste tolerante e rotulá-la novamente como teste de um ad hoc propriedade ).

$k$ $k$ $k=n/10$ $\Omega(\frac{n}{\log n})$ $\frac{n}{100}$

Clemente C.
fonte