Dolna granica dla testowania bliskości w normie ?

11

Zastanawiałem się, czy istnieje jakakolwiek dolna granica (pod względem złożoności próby) znana z następującego problemu:

Biorąc pod uwagę przykładowy dostęp do wyroczni do dwóch nieznanych dystrybucji , w , test (whp) czy $D_1$ $D_2$ $\{1,\dots,n\}$

$D_1=D_2$
lub $\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon$

Batu i in. [BFR + 00] pokazało, że $O\left(\frac{1}{\epsilon^4}\right)$ próbki były wystarczające, ale nie znalazłem żadnej wzmianki o dolnej granicy?

Wydaje mi się, że zawsze można pokazać dolną granicę $\Omega(\frac{1}{\epsilon^2})$ , zmniejszając zadanie rozróżnienia monety bezstronnej kontra $\epsilon$ do tego problemu (symulując rozkład obsługiwany tylko na dwóch wskazuje i odpowiada na pytania testera zgodnie z rzutami monetą iid), ale wciąż pozostawia to kwadratową lukę ...

(Inną kwestią, którą chciałbym się zainteresować, jest dolna granica w szacowaniu (do dodatku $\epsilon$ ) tej odległości $L_2$ - ponownie nie znalazłem odniesienia do takiego wyniku w literaturze)

Dzięki za pomoc,

— Klemens C.
źródło

Ten problem z obietnicą wydaje się bardzo podobny do tego , który Sahai i Vadhan nazywają różnicą statystyczną , co jest kompletnym problemem dla klasy SZK (statystyczna wiedza zerowa); używają odległości . cs.ucla.edu/~sahai/work/web/2003%20Publications/J.ACM2003.pdf . (Edycja: również myślę, że zakładają, że masz obwód obliczający rozkłady, a nie dostęp do Oracle).

L_{1}

$L_1$

— usul

Cześć, jak wspomniano w innym komentarzu, różnica między normą a normą jest tutaj naprawdę kluczowa - ponadto w artykule określają wyraźny (i nie arbitralny) próg (w jednej z uwag wyjaśniają, że próg ten musi spełniać pewne szczególne ograniczenia); i chcesz rozróżnić vs. (który jest bliższy tolerancyjnemu testowaniu / szacowaniu odległości niż „zwykłe testowanie”, gdzie chcesz przetestować vs. (ale dla każdego ustalonego )).

L_{2}

$L_2$

L_{1}

$L_1$

τ = 1 / 3

$\tau=1/3$

d_{1} \leq τ

$d_1 \leq \tau$

d_{2} \geq 1 - τ

$d_2 \geq 1-\tau$

d_{2} = 0

$d_2=0$

d_{2} \geq ϵ

$d_2 \geq \epsilon$

ϵ

$\epsilon$

— Clement C.

6

Wygląda na to, że próbki - jak usul pokazał poniżej - wystarczają do testowania, więc złożoność próbki wynosi dokładnie ; faktycznie okazuje się, że ta liczba próbek wystarcza nam nawet do nauki aż do dodatku wrt normy . $O(1/\epsilon^2)$ $\Theta(1/\epsilon^2)$ $D$ $\epsilon$ $L_2$

Niech jest funkcją gęstości empiryczny otrzymane drogą ciągnięcia IID próbki i ustawienie Następnie gdzie . $\hat{D}$ $m$ $s_1,\dots, s_m\sim D$

\hat{D} (k) \overset{d e f}{=} \frac{1}{m} \sum_{ℓ = 1}^{m} 1_{{s_{ℓ} = k}}, k \in [n]

$\hat{D}(k) \stackrel{\rm{}def}{=} \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}},\qquad k\in[n]$

\begin{aligned} ‖ D - \hat{D} ‖_{2}^{2} & = \sum_{k = 1}^{n} {(\frac{1}{m} \sum_{ℓ = 1}^{m} 1_{{s_{ℓ} = k}} - D (k))}^{2} = \frac{1}{m^{2}} \sum_{k = 1}^{n} {(\sum_{ℓ = 1}^{m} 1_{{s_{ℓ} = k}} - m D (k))}^{2} \\ = \frac{1}{m^{2}} \sum_{k = 1}^{n} {(X_{k} - E X_{k})}^{2} \end{aligned}

$\begin{align*} \lVert D - \hat{D} \rVert_2^2 &= \sum_{k=1}^n \left( \frac{1}{m}\sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - D(k) \right)^2 = \frac{1}{m^2}\sum_{k=1}^n \left( \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}} - mD(k) \right)^2 \\ &= \frac{1}{m^2}\sum_{k=1}^n \left( X_k - \mathbb{E} X_k \right)^2 \end{align*}$

X_{k} \overset{d e f}{=} \sum_{ℓ = 1}^{m} 1_{{s_{ℓ} = k}} \sim Bin (m, D (k))

$X_k\stackrel{\rm{}def}{=} \sum_{\ell=1}^m \mathbb{1}_{\{s_\ell = k\}}\sim\operatorname{Bin}( m, D(k) )$

X_{k}

$X_k$ (dla ) nie są niezależne, ale możemy napisać , aby , i stosując nierówność Markova

k \in [n]

$k\in[n]$

\begin{aligned} E ‖ D - \hat{D} ‖_{2}^{2} & = \frac{1}{m^{2}} \sum_{k = 1}^{n} E [{(X_{k} - E X_{k})}^{2}] = \frac{1}{m^{2}} \sum_{k = 1}^{n} Var X_{k} \\ = \frac{1}{m^{2}} \sum_{k = 1}^{n} m D (k) (1 - D (k)) \leq \frac{1}{m} \sum_{k = 1}^{n} D (k) \\ = \frac{1}{m} \end{aligned}

$\begin{align*} \mathbb{E}\lVert D - \hat{D} \rVert_2^2 &= \frac{1}{m^2}\sum_{k=1}^n \mathbb{E}\left[ \left( X_k - \mathbb{E} X_k \right)^2 \right] = \frac{1}{m^2}\sum_{k=1}^n \operatorname{Var} X_k \\ &= \frac{1}{m^2}\sum_{k=1}^n mD(k)\left( 1- D(k) \right) \leq \frac{1}{m}\sum_{k=1}^n D(k) \\ &= \frac{1}{m} \end{align*}$

m \geq \frac{3}{ϵ^{2}}

$m\geq \frac{3}{\epsilon^2}$

E ‖ D - \hat{D} ‖_{2}^{2} \leq \frac{ϵ^{2}}{3}

$\begin{equation} \mathbb{E}\lVert D - \hat{D} \rVert_2^2 \leq \frac{\epsilon^2}{3} \end{equation}$

P {‖ D - \hat{D} ‖_{2} \geq ϵ} \leq \frac{1}{3} .

$\begin{equation} \mathbb{P}\left\{ \lVert D - \hat{D} \rVert_2 \geq \epsilon \right\} \leq \frac{1}{3}. \end{equation}$

— Klemens C.
źródło

(Odniosłem się do odpowiedzi na usul zaczynającej się od „Spróbuję odpokutować za mój poprzedni błąd, pokazując coś przeciwnego [...]” - co tak naprawdę jest powyżej tego. Nie spodziewałem się tego :)) Co do nauki w górnej granicy można wykazać, że najbardziej naiwny algorytm (tj. ten, który pobiera próbki i generuje gęstość empiryczną, którą określa), daje rozkład który jest, ze stałym prawdopodobieństwem, -close do w odległości .

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

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

\hat{D}

$\hat{D}$

ϵ

$\epsilon$

D

$D$

L_{2}

$L_2$

— Clement C.

@DW Właśnie edytowałem swoją odpowiedź.

— Klemens C.

3

Spróbuję odpokutować za mój poprzedni błąd, pokazując coś przeciwnego - że próbki są wystarczające (dolna granica jest prawie ciasny)! Zobacz co myślisz .... $\tilde{\Theta}\left(\frac{1}{\epsilon^2}\right)$ $1/\epsilon^2$

Kluczowa intuicja rozpoczyna się od dwóch obserwacji. Po pierwsze, aby rozkłady miały odległość , muszą istnieć punkty z dużym prawdopodobieństwem ( ). Na przykład, gdybyśmy mieli punkty prawdopodobieństwa , mielibyśmy . $L_2$ $\epsilon$ $\Omega(\epsilon^2)$ $1/\epsilon^3$ $\epsilon^3$ $\|D_1 - D_2\|_2 \leq \sqrt{\frac{1}{\epsilon^3} (\epsilon^3)^2} = \epsilon^{3/2} < \epsilon$

Po drugie, rozważ jednolite rozkłady o odległości . Gdybyśmy mieli punkty prawdopodobieństwa , wówczas każdy z nich różniłby się i wystarczałyby próbki . Z drugiej strony, gdybyśmy mieli punkty , każdy z nich musiałby różnić się o próbki i ponownie (stała liczba na punkt) wystarczy. Możemy więc mieć nadzieję, że wśród wspomnianych wcześniej punktów o wysokim prawdopodobieństwie zawsze istnieje punkt różniący się „wystarczająco”, aby . $L_2$ $\epsilon$ $O(1)$ $O(1)$ $O(\epsilon)$ $1/\epsilon^2$ $O(1/\epsilon^2)$ $O(\epsilon^2)$ $O(1/\epsilon^2)$ $O(1/\epsilon^2)$

Algorytm. Biorąc pod uwagę i parametr ufności , niech . Narysuj próbki z każdej dystrybucji. Niech będą odpowiednio wyższą, niższą liczbą próbek dla punktu . Jeśli istnieje punkt dla którego i , zadeklaruj różne rozkłady. W przeciwnym razie zadeklaruj je tak samo. $\epsilon$ $M$ $X = M \log(1/\epsilon^2)$ $\frac{X}{\epsilon^2}$ $a_i,b_i$ $i$ $i \in [n]$ $a_i \geq \frac{X}{8}$ $a_i-b_i \geq \sqrt{a_i} \frac{\sqrt{X}}{4}$

Granice poprawności i pewności ( ) zależą od następującego lematu, który mówi, że całe odchylenie w odległości pochodzi od punktów, których prawdopodobieństwo różni się o . $1-e^{-\Omega(M)}$ $L_2$ $\Omega(\epsilon^2)$

Roszczenie. Załóżmy, że . Niech. Niech . Następnie $\|D_1 - D_2\|_2 \geq \epsilon$ $\delta_i = |D_1(i) - D_2(i)|$ $S_k = \{i : \delta_i > \frac{\epsilon^2}{k}\}$
$\sum_{i \in S_{k}} δ_{i}^{2} \geq ϵ^{2} (1 - \frac{2}{k}) .$ $\sum_{i \in S_k} \delta_i^2 \geq \epsilon^2\left(1-\frac{2}{k}\right).$

Dowód . Mamy Ograniczmy drugą sumę; chcemy zmaksymalizować zastrzeżeniem . Ponieważ funkcja jest ściśle wypukła i rośnie, możemy zwiększyć cel, biorąc dowolne i zwiększając o jednocześnie zmniejszając o . Tak więc cel zostanie zmaksymalizowany przy użyciu jak największej liczby terminów przy ich maksymalnych wartościach, a pozostałe przy

\sum_{i \in S_{k}} δ_{i}^{2} + \sum_{i \notin S_{k}} δ_{i}^{2} \geq ϵ^{2} .

$\sum_{i \in S_k} \delta_i^2 ~ + ~ \sum_{i \not\in S_k} \delta_i^2 \geq \epsilon^2.$

\sum_{i \notin S_{k}} δ_{i}^{2}

$\sum_{i \not\in S_k} \delta_i^2$

\sum_{i \notin S_{k}} δ_{i} \leq 2

$\sum_{i \not\in S_k} \delta_i \leq 2$

x \mapsto x^{2}

$x \mapsto x^2$

δ_{i} \geq δ_{j}

$\delta_i \geq \delta_j$

δ_{i}

$\delta_i$

γ

$\gamma$

δ_{j}

$\delta_j$

γ

$\gamma$

0

$0$ . Maksymalna wartość każdego terminu wynosi , a istnieją najwyżej warunki tej wartości (ponieważ sumują się one maksymalnie do ). Więc

\frac{ϵ^{2}}{k}

$\frac{\epsilon^2}{k}$

\frac{2 k}{ϵ^{2}}

$\frac{2k}{\epsilon^2}$

2

$2$

\sum_{i \notin S_{k}} δ_{i}^{2} \leq \frac{2 k}{ϵ^{2}} {(\frac{ϵ^{2}}{k})}^{2} = \frac{2 ϵ^{2}}{k} . ◻

$\sum_{i \not\in S_k} \delta_i^2 \leq \frac{2k}{\epsilon^2}\left(\frac{\epsilon^2}{k}\right)^2 = \frac{2\epsilon^2}{k} . ~~~~ \square$

Roszczenie . Niech . Jeśli , istnieje co najmniej jeden punkt z i . $p_i = \max\{D_1(i),D_2(i)\}$ $\|D_1 - D_2\|_2 \geq \epsilon$ $i \in [n]$ $p_i > \frac{\epsilon^2}{4}$ $\delta_i \geq \frac{\epsilon \sqrt{p_i}}{2}$

Dowód . Po pierwsze, wszystkie punkty w mają z (a nie może być pusty dla według poprzedniego zastrzeżenia). $S_k$ $p_i \geq \delta_i > \frac{\epsilon^2}{k}$ $S_k$ $k > 2$

Po drugie, ponieważ mamy lub, przestawienie, więc nierówność utrzymuje co najmniej jeden punkt w . Teraz wybierz . $\sum_i p_i \leq 2$

\sum_{i \in S_{k}} δ_{i}^{2} \geq ϵ^{2} (\frac{1}{2} - \frac{1}{k}) \sum_{i \in S_{k}} p_{i},

$\sum_{i \in S_k} \delta_i^2 \geq \epsilon^2 \left(\frac{1}{2} - \frac{1}{k}\right) \sum_{i \in S_k} p_i,$

\sum_{i \in S_{k}} (δ_{i}^{2} - p_{i} ϵ^{2} (\frac{1}{2} - \frac{1}{k})) \geq 0,

$\sum_{i \in S_k} \left( \delta_i^2 - p_i \epsilon^2 \left(\frac{1}{2} - \frac{1}{k}\right)\right) \geq 0 ,$

δ_{i}^{2} \geq p_{i} ϵ^{2} (\frac{1}{2} - \frac{1}{k})

$\delta_i^2 \geq p_i \epsilon^2 \left(\frac{1}{2} - \frac{1}{k}\right)$

S_{k}

$S_k$

k = 4

$k=4$

◻

$\square$

Roszczenie (fałszywie pozytywne) . Jeśli , nasz algorytm deklaruje je inaczej z prawdopodobieństwem co najwyżej . $D_1 = D_2$ $e^{-\Omega(M)}$

Szkic . Rozważ dwa przypadki: i . W pierwszym przypadku liczba próbek nie przekroczy z obu rozkładów: Średnia liczba próbek wynosi a ograniczenie ogona mówi, że z prawdopodobieństwem , „s próbki nie może przekraczać wartości średnich od dodatku ; jeśli staramy się zachować wartość w ograniczeniu ogona, możemy związać z nią związanie bez względu na liczbę takich punktów (intuicyjnie ograniczenie zmniejsza się wykładniczo w liczbie możliwych punktów). $p_i < \epsilon^2/16$ $p_i \geq \epsilon^2/16$ $i$ $X/8$ $< X/16$ $e^{-\Omega(X/p_i)} = \epsilon^2 e^{-\Omega(M/p_i)}$ $i$ $X/16$ $p_i$

W przypadku możemy użyć granicy Chernoffa: Mówi ona, że gdy pobieramy próbek i rysujemy punkt z prawdopodobieństwem , prawdopodobieństwo różni się od jego średniej o to co najwyżej . Niech , więc prawdopodobieństwo jest ograniczone przez . $p_i \geq \epsilon^2/16$ $m$ $p$ $pm$ $c \sqrt{pm}$ $e^{-\Omega((c\sqrt{pm})^2/pm)} = e^{-\Omega(c^2)}$ $c = \frac{\sqrt{X}}{16}$ $e^{-\Omega(X)} = \epsilon^2 e^{-\Omega(M)}$

Więc z prawdopodobieństwem , (dla obu dystrybucji) liczba próbek mieści się w jego średnia . W ten sposób nasz test nie złapie tych punktów (są one bardzo blisko siebie) i możemy związać się związkiem na wszystkich z nich. $1-\epsilon^2e^{-\Omega(M)}$ $i$ $\sqrt{p_i\frac{X}{\epsilon^2}}\frac{\sqrt{X}}{16}$ $p_i\frac{X}{\epsilon^2}$ $16/\epsilon^2$ $\square$

Roszczenie (fałszywe negatywy) . Jeśli , nasz algorytm deklaruje ich identyczność z prawdopodobieństwem co najwyżej . $\|D_1 - D_2\|_2 \geq \epsilon$ $\epsilon^2 e^{-\Omega(M)}$

Szkic . Jest pewien punkt z i . To samo ograniczenie Chernoffa, co w poprzednim twierdzeniu, mówi, że z prawdopodobieństwem liczba próbek różni się od średniej najwyżej . To jest dla (WLOG) dystrybucji która ma ; ale istnieje jeszcze mniejsze prawdopodobieństwo liczby próbek z rozkładu $i$ $p_i > \epsilon^2/4$ $\delta_i \geq \epsilon \sqrt{p_i}/2$ $1-\epsilon^2 e^{-\Omega(M)}$ $i$ $p_i m$ $\sqrt{p_i m} \frac{\sqrt{X}}{16}$ $1$ $p_i = D_1(i) = D_2(i) + \delta_i$ $i$ $2$ różni się od średniej o tę sumę dodatków (ponieważ średnia i wariancja są niższe).

Tak więc z dużym prawdopodobieństwem liczba próbek z każdego rozkładu mieści się w zakresie jego średniej; ale ich prawdopodobieństwo różni się o , więc ich średnie różnią się o $i$ $\sqrt{\frac{p_i X}{\epsilon^2}} \frac{\sqrt{X}}{16}$ $\delta_i$

\frac{X}{ϵ^{2}} δ_{i} \geq \frac{X \sqrt{p_{i}}}{2 ϵ} = \sqrt{\frac{p_{i} X}{ϵ^{2}}} \frac{\sqrt{X}}{2} .

$\frac{X}{\epsilon^2}\delta_i \geq \frac{X \sqrt{p_i}}{2\epsilon} = \sqrt{\frac{p_i X}{\epsilon^2}} \frac{\sqrt{X}}{2} .$

Z dużym prawdopodobieństwem dla punktu liczba próbek różni się co najmniej o . $i$ $\sqrt{\# samples(1)} \frac{\sqrt{X}}{4}$ $\square$

Aby ukończyć szkice, musielibyśmy bardziej rygorystycznie wykazać, że dla wystarczająco dużego liczba próbek jest wystarczająco bliska jego średniej, że gdy algorytm używa zamiast nic to nie zmienia (co powinno być proste, pozostawiając trochę stałego miejsca w stałych). $M$ $i$ $\sqrt{\# samples}$ $\sqrt{mean}$

— usul
źródło

Cześć, dziękuję za to - mam kilka pytań na temat algorytmu i analizy (dotyczących kilku punktów, których nie jestem pewien): zakładając, że chcę na końcu tylko stałe prawdopodobieństwo sukcesu, co oznacza, że Stała , jeśli dobrze rozumiem (chyba że nie dostałam tego, co było )? Zatem w tym przypadku przejście do : zgodnie z algorytmem staje się - czy to prawda?

2 / 3

$2/3$

M

$M$

M

$M$

X

$X$

Θ (\log \frac{1}{ϵ})

$\Theta(\log\frac{1}{\epsilon})$

— Clement C.,

@ClementC. Przepraszam, nie byłem bardzo jasny! Twierdzenie jest takie, że jeśli narysujemy próbki , wówczas prawdopodobieństwo pomyłki wynosi , więc dla stałe prawdopodobieństwo błędu, jego próbki.

\frac{1}{ϵ^{2}} M \log (1 / ϵ^{2})

$\frac{1}{\epsilon^2} M \log(1/\epsilon^2)$

O (e^{- M})

$O(e^{-M})$

O (\frac{1}{ϵ^{2}} \log (1 / ϵ^{2}))

$O\left(\frac{1}{\epsilon^2} \log(1/\epsilon^2)\right)$

— usul

OK, właśnie to zebrałem. Mając to na uwadze, przejdę przez dowód - jeszcze raz dziękuję za poświęcony na to czas!

— Clement C.,

1

Możesz zacząć od rozwiązania tego problemu dla przypadku . Jestem pewien, że próbki będą w tym przypadku konieczne i wystarczające. $n=2$ $\Theta(1/\epsilon^2)$

Możliwe, że może okazać się pomocne sprawdzenie konwersji między odległością a odległością (całkowita odległość zmiany). $L_2$ $L_1$

Wiadomo, że w przypadku jednej próbki, jeśli rozkłady są znane, całkowity dystans zmiany doskonale charakteryzuje przewagę, z jaką można odróżnić od . Tak więc, jeśli całkowity dystans zmiany jest duży, a rozkłady są znane, można zbudować test, który jest poprawny z dużym prawdopodobieństwem; jeśli całkowita odległość zmiany jest mała, nie można. Nie wiem, co można powiedzieć o przypadku, w którym całkowita odległość zmiany jest duża, ale rozkłady są nieznane. $D_1$ $D_2$
Następnie spójrz na dystrybucje produktów, i . Stosując całkowitą odległość zmiany (odległość ), wydaje się, że nie ma żadnych dobrych granic, które dotyczą do . Jednak korzystając z odległości , uważam, że istnieją dobre oszacowania jako funkcji . (Niestety, nie mogę wydobyć konkretnego odniesienia do tych oszacowań / granic, więc mam nadzieję, że nie pomylę się.) Znane są również granice, które pozwalają oszacować odległość jako funkcję odległości . $D_1^n$ $D_2^n$ $L_1$ $||D_1^n - D_2^n||_1$ $||D_1 - D_2||_1$ $L_2$ $||D_1^n - D_2^n||_2$ $||D_1 - D_2||_2$ $L_1$ $L_2$
Dlatego jednym z podejść, które możesz wypróbować, byłoby związanie , a następnie powiązanie . $||D_1^n - D_2^n||_2$ $||D_1^n - D_2^n||_1$

Nie wiem, czy to doprowadzi gdziekolwiek dobrze, czy nie; to tylko pomysł. Prawdopodobnie autorzy cytowanego przez ciebie artykułu już próbowali lub rozważali coś takiego.

Ewentualnie pomocne referencje:

— DW
źródło

Cześć, dziękuję za odpowiedź! Interesuje mnie jednak asymptotyczna dolna granica, kiedy . W szczególności związek między i obejmuje czynnik - co oznacza, że są one rzeczywiście równoważne stałej, ale asymptotycznie bardzo różne; użycie L_1 jako proxy nie jest opcją, o ile mogę stwierdzić (jeśli chodzi o testowanie bliskości w odległości , dokładna złożoność to [BFR + 10 , Val11 ]

n \to \infty

$n\to\infty$

L_{2}

$L_2$

L_{1}

$L_1$

\sqrt{n}

$\sqrt{n}$

n

$n$

L_{1}

$L_1$

L_{1}

$L_1$

Θ (n^{2 / 3} / p o l y (ϵ))

$\Theta(n^{2/3}/{\rm{}poly}(\epsilon))$

— Clement C.

0

EDYCJA: to jest nieprawidłowe! Zobacz dyskusję w komentarzach - zwrócę uwagę na wadę poniżej.

Myślę, że możemy powiedzieć, że są wymagane. $\frac{1}{\epsilon^4}$

Ustaw . Niech będzie rozkładem równomiernym (prawdopodobieństwo każdego punktu ) i niech różni się od jednolitego sumą addytywną w każdym punkcie. Sprawdź, odległość wynosi . $n = \Theta\left(\frac{1}{\epsilon^2}\right)$ $D_1$ $= \Theta(\epsilon^2)$ $D_2$ $\pm \Theta\left(\epsilon^2\right)$ $L_2$ $\epsilon$

Więc musimy odróżnić -sided uczciwą monetę z -sided -biased monety. Myślę, że powinno to być co najmniej tak trudne, jak odróżnienie stronnej uczciwej monety od stronnej -obojętnej monety, która wymagałaby próbek. Edycja: to jest nieprawidłowe! Moneta jest dodatkowa , ale jest stronnicza mnożona przez stały czynnik. Jak zauważa DW, oznacza to, że stała liczba próbek na punkt odróżnia od . $n$ $n$ $\Theta(\epsilon^2)$ $2$ $2$ $\Theta(\epsilon^2)$ $\Theta\left(\frac{1}{(\epsilon^2)^2}\right) = \Theta\left(\frac{1}{\epsilon^4}\right)$ $\epsilon^2$ $D_1$ $D_2$

Zauważ, że jest tak daleko, jak to tylko możliwe. Konkretnie, załóżmy, że próbowaliśmy zwiększyć do, powiedzmy, . W rozkładzie równomiernym każdy punkt ma prawdopodobieństwo . Ale w każdy punkt musiałby różnić się od munduru o . Nie jest to możliwe, ponieważ . $\frac{1}{\epsilon^4}$ $n$ $\frac{1}{\epsilon^3}$ $\epsilon^3$ $D_2$ $\epsilon^{2.5}$ $\epsilon^{2.5} \gg \epsilon^3$

Bardziej abstrakcyjnie, załóżmy, że chcemy, aby każdy punkt różnił się od jednolitego o . Zatem największą wartością, jaką możemy ustawić na byłoby . Aby uzyskać odległość , musimy upewnić się, że pierwiastek kwadratowy sumy odległości wynosi , więc , więc więc , i otrzymujemy . $\epsilon^k$ $n$ $\frac{1}{\epsilon^k}$ $L_2$ $\epsilon$ $\epsilon$ $\sqrt{n(\epsilon^k)^2} = \epsilon$ $\epsilon^{k/2} = \epsilon$ $k = 2$ $n = \frac{1}{\epsilon^2}$

Myślę też, że ten sam argument mówi, że jeśli interesuje odległość przy , potrzebujemy , więc wybralibyśmy , więc liczba próbek wynosiłaby . Myślę, że ma to sens jako granica niezależna od . Zbliża się do nieskończoności jako . Jeśli próbujesz rozróżnić dwie rozkłady w odległości bez ograniczenia na , zrobiłbym ograniczeń i rozłożyłbym różnicę dowolnie cienką, abyś nigdy nie mógł ich rozróżnić ( $L_p$ $p > 1$ $k = \frac{p}{p-1}$ $n = 1/\epsilon^{\frac{p}{p-1}}$ $1 / \epsilon^{2\frac{p}{p-1}}$ $n$ $p \to 1$ $L_1$ $\epsilon$ $n$ $n$ tzn. brak wystarczającej liczby próbek dla wszystkich ). Podchodzi także do jako ; ma to sens jako ograniczenie, ponieważ dla normy możemy ustawić i pozwolić, aby każdy punkt różnił się o ; musimy próbować kilka punktów razy, aby upewnić się, że różni się od jednolitego, który pobierze próbki . $n$ $\frac{1}{\epsilon^3}$ $p \to \infty$ $L_{\infty}$ $n = \frac{1}{\epsilon}$ $\Theta(\epsilon)$ $\frac{1}{\epsilon^2}$ $\frac{1}{\epsilon^3}$

— usul
źródło

1. Czy naprawdę masz na myśli, że różni się od munduru przez w każdym punkcie? Podejrzewam, że to literówka, a miałeś na myśli .

D_{2}

$D_2$

\pm 1 / ϵ^{2}

$\pm 1/\epsilon^2$

\pm ϵ^{2}

$\pm \epsilon^2$

— DW

1

2. Nie kupuję tego, że odróżnienie od wymaga próbek. Wygląda mi na to, że wystarczą próbki . Objaśnienie (intuicja): załóżmy, że zbieramy próbki i liczymy, ile razy występuje każda możliwa wartość. Jeśli pochodzą z , każdy powinien pojawić się 100 razy (z std dev 10). Jeśli pochodzą z , każdy powinien wystąpić 200 razy (std dev 14) dla połowy z nich, / 0 razy (std dev 0) dla drugiej połowy. Łatwo to rozróżnić, jeśli wiesz, że masz do czynienia z lub .

D_{1}

$D_1$

D_{2}

$D_2$

1 / ϵ^{4}

$1/\epsilon^4$

Θ (1 / ϵ^{2})

$\Theta(1/\epsilon^2)$

m = 100 / ϵ^{2}

$m=100/\epsilon^2$

D_{1}

$D_1$

D_{2}

$D_2$

D_{1}

$D_1$

D_{2}

$D_2$

— DW

@DW (1) masz rację! Naprawiony. (2) Jak to ująłeś, zgadzam się, ale myślę, że przy różnych wyborach stałych jest trudniej. Wyobrażam sobie coś takiego: , więc stawia prawdopodobieństwo w każdym punkcie. Wtedy różni się o w każdym punkcie (sprawdź, odległość wynosi ), więc stawia prawdopodobieństwo lub w każdym punkcie.

n = 1 / 100 ϵ^{2}

$n = 1/100\epsilon^2$

D_{1}

$D_1$

100 ϵ^{2}

$100\epsilon^2$

D_{2}

$D_2$

10 ϵ^{2}

$10\epsilon^2$

L_{2}

$L_2$

ϵ

$\epsilon$

90 ϵ^{2}

$90\epsilon^2$

110 ϵ^{2}

$110\epsilon^2$

— usul

1

Myślę, że próbki wciąż wystarczają. Zbierz próbek i policz, ile razy występuje każda możliwa wartość. Dla każdy powinien wystąpić 1 000 000 razy (std dev ). Dla każdy powinien wystąpić 900 000 razy (std dev ) lub 1100000 razy (std dev ). Wystarczy to łatwo rozróżnić między nimi, jeśli wiemy, że mamy do czynienia z lub , ponieważ różnica między 1 000 000 a 1 100 000 to 100 odchyleń standardowych, tj. Ogromna.

O (1 / ϵ^{2})

$O(1/\epsilon^2)$

m = 10^{6} n

$m=10^6n$

D_{1}

$D_1$

1000

$1000$

D_{2}

$D_2$

\approx 1000

$\approx 1000$

\approx 1000

$\approx 1000$

D_{1}

$D_1$

D_{2}

$D_2$

— DW

@DW Myślałem o tym więcej - masz rację. Jeżeli ich średnie wartości różnią się stałym współczynnikiem multiplikatywnym, wówczas powinna je rozróżniać stała liczba próbek na punkt. Liczy się mnożący, a nie addytywny czynnik. Takie podejście daje jedynie dolną granicę .

1 / ϵ^{2}

$1/\epsilon^2$

— usul