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

13

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.DPd(D,P)>ϵd1

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(n2registron)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?
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 ( n 2 log n ) , mas observe que, na verdade, aprendendo distribuições (sobre domínio de tamanhoO(n2registron) ) para TV /1 distância ε com probabilidade 2 / 3 na verdade pode ser feito comamostras de O ( n / ε 2 ) (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 )n1ε2/3O(n/ε2)εω(n) limites inferiores ...
Clement C.

Respostas:

5

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 ε1 . (antes de verificar "offline" se houver alguma distribuiçãopcom a propriedadePnque, por sua vez, esteja à distância no máximoεε2pPn do seu hipótese aprendeu p ). Isso levaria ingenuamente a umO(nlognε2p^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 tamanhonaté a distânciaε(na distância total da variação) pode ser feito apenas comO(nO(nregistronε2)nεamostras (e isso é apertado).O(nε2)

Portanto, a linha de base deve ser realmente , que já é linear emn. Agora, pode-se fazer a próxima pergunta -existem propriedades "naturais" para as quais os testes (digamos, paraεconstante) requerem uma dependência linear no tamanho do domínion?O(nε2)nε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 Θ ε ( n1/10Θε(nregistron) .

(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 ).

kkk=n/10Ω(nregistron)n100

Clemente C.
fonte