Apakah ada properti distribusi yang "maksimal" sulit diuji?

Algoritma pengujian distribusi untuk properti distribusi P (yang hanya sebagian dari semua distribusi di atas [n]) diizinkan mengakses sampel sesuai dengan beberapa distribusi D, dan diperlukan untuk memutuskan (whp) jika atau ( sini biasanya $D\in P$ $d(D,P)>\epsilon$ $d$ jarak ). Ukuran kompleksitas yang paling umum adalah jumlah sampel yang digunakan oleh algoritma. $\ell_1$

Sekarang, dalam pengujian properti standar, di mana Anda memiliki akses kueri ke beberapa objek, batas bawah linear pada kompleksitas kueri jelas merupakan batas bawah terkuat yang mungkin, karena $n$ kueri akan mengungkapkan seluruh objek. Apakah ini juga berlaku untuk pengujian distribusi?

Sejauh yang saya mengerti, batas atas "sepele" untuk menguji properti distribusi adalah --- oleh batas Chernoff, ini cukup untuk "menuliskan" distribusi D 'yang dekat dengan D di jarak, dan kemudian kita bisa memeriksa apakah ada distribusi yang dekat dengan D 'yang ada di P (ini mungkin membutuhkan waktu tak terbatas, tetapi ini tidak relevan dengan kompleksitas sampel). $O(n^2\log n)$ $\ell_1$

Apakah ada tes "trivial" yang lebih baik untuk semua properti distribusi?
Apakah ada properti distribusi yang kita tahu sampel batas bawah lebih kuat dari linier?

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

tampaknya mirip dengan membuktikan pemisahan kelas kompleksitas & seperti itu bisa dekat dengan beberapa masalah terbuka yang diketahui ...?

vzn

Hanya melihat ini ... Saya tidak yakin bagaimana Anda berasal terikat

, tapi catatan yang benar-benar distribusi belajar (lebih domain dari ukuran

) ke TV /

jarak

dengan probabilitas

sebenarnya dapat dilakukan dengan sampel

(dan ini ketat). Jadi, kecuali Anda melihat nilai-nilai non-konstan parameter kedekatan

, tidak ada harapan untuk mendapatkan

batas bawah ...

O (n^{2} \log n)

$O(n^2\log n)$

n

$n$

ℓ_{1}

$\ell_1$

ε

$\varepsilon$

2 / 3

$2/3$

O (n / ε^{2})

$O(n/\varepsilon^2)$

ε

$\varepsilon$

ω (n)

$\omega(n)$

Clement C.

Jawaban:

Maaf telah menemukan postingan ini - ini sudah cukup lama, tapi saya pikir setelah menjawabnya mungkin bukan ide yang buruk.

Pertama, sepertinya Anda melakukan ikatan Chernoff dengan beberapa pengaturan parameter yang agak aneh. Perhatikan bahwa untuk melakukan pendekatan "pengujian dengan pembelajaran" yang disarankan, cukup mempelajari distribusi dalam total variasi jarak (atau , jika Anda suka, yang sama hingga faktor 2) hingga jarak $\ell_1$ . (sebelum memeriksa "offline" jika ada distribusimemiliki propertiyang jaraknya paling jauh $\frac{\varepsilon}{2}$ $p'$ $\mathcal{P}_n$ dari Anda belajar hipotesis ). Ini naif akan mengarah ke $\frac{\varepsilon}{2}$ $\hat{p}$ kompleksitas sampel batas atas untuk pendekatan ini; Namun, diketahui (dan "cerita rakyat") bahwa mempelajari distribusi sewenang-wenang atas domain ukuranhingga jarak(dalam jarak total variasi) dapat dilakukan hanya dengan $O\big(\frac{n\log n}{\varepsilon^2}\big)$ $n$ $\varepsilon$ sampel (dan ini ketat). $O(\frac{n}{\varepsilon^2})$

Jadi baseline sebenarnya harus , yang sudah linear dalam. Sekarang, seseorang dapat mengajukan pertanyaan berikutnya -apakah ada sifat "alami" yang diuji (katakanlah, untukkonstan $O(\frac{n}{\varepsilon^2})$ $n$ $\varepsilon$ ) memerlukan ketergantungan linier dalam ukuran domain $n$ ?

Jawabannya adalah (sejauh yang saya tahu) "tidak cukup, tetapi dekat." Yaitu, mengikuti garis pekerjaan yang signifikan pada memperkirakan properti distribusi (atau ekuivalen, pengujian properti toleran), hasil Valiant dan Valiant menyiratkan (STOCS'11, FOCS'11, dan beberapa lainnya) bahwa properti yang agak dibuat-buat "adalah -cekat dengan seragam "memiliki kompleksitas sampel $1/10$ $\Theta_\varepsilon(\frac{n}{\log n})$ .

(Perhatikan bahwa ini sedikit "curang," dalam arti bahwa properti hanyalah cara untuk mengambil pertanyaan pengujian yang toleran dan memberi label ulang sebagai pengujian ad hoc properti ).

Jika itu tidak sepenuhnya cukup untuk memuaskan dahaga Anda, orang juga dapat menunjukkan bahwa untuk properti (alami?) Dari "menjadi histogram" (apakah distribusi yang konstan pada seperangkat interval tidak diketahui?), Menetapkan misalnya juga menghasilkan $k$ $k$ $k=n/10$ batas bawah(ada di kertas tambang dari 2016; batas bawah mengikuti dari pengurangan yang agak sederhana untuk hasil Valiants '). Sekarang, apakah Anda mempertimbangkan "menjadi $\Omega(\frac{n}{\log n})$ histogram "menjadi properti alami terserah Anda. $\frac{n}{100}$

Clement C.
sumber