Znajdź przybliżony argmax, używając tylko przybliżonych maksymalnych zapytań

Rozważ następujący problem.

$n$$v_1, \cdots, v_n \in \mathbb{R}$$S \subseteq \{1,\cdots,n\}$$\max_{i \in S} v_i$

Ten problem jest prosty: możemy użyć wyszukiwania binarnego, aby znaleźć argmax z zapytaniami . tj. Zbuduj kompletne drzewo binarne z liści odpowiadających indeksom. Zacznij od korzenia i zejdź do liścia w następujący sposób. W każdym węźle zapytaj o maksymalną wartość w prawym i lewym poddrzewie, a następnie przejdź do strony podrzędnej z większą odpowiedzią. Po osiągnięciu liścia wypisz jego indeks.$O(\log n)$$n$

W moich badaniach pojawiła się następująca głośna wersja tego problemu.

Istnieje nieznanych wartości . Można do nich uzyskać dostęp za pomocą zapytań, w których określono zestaw i próbkę z . Celem jest zidentyfikowanie taki sposób, aby przy użyciu jak najmniejszej liczby zapytań. (Oczekiwanie jest niż wybór , który zależy zarówno od monet algorytmu, jak i od hałaśliwych odpowiedzi na zapytania).$n$$v_1, \cdots, v_n$$S \subseteq \{1, \cdots, n\}$$\mathcal{N}(\max_{i \in S} v_i,1)$$i_* \in \{1, \cdots, n\}$$\mathbb{E}[v_{i_*}] \geq \max_i v_i - 1$$i_*$

Załóżmy, że próbujemy rozwiązać ten problem przy użyciu tej samej strategii wyszukiwania binarnego, co wcześniej (ale z głośnymi odpowiedziami). łatwo można wykazać, że osiąga to i że jest to w najgorszym przypadku. Możemy zredukować błąd do pożądanego , powtarzając każde zapytanie razy i używając średniej (która zmniejsza wariancję). Daje to algorytm wykorzystujący zapytania .$\mathbb{E}[v_{i_*}] \geq \max_i v_i - O(\log n)$$1$$O(\log^2 n)$$O(\log^3 n)$

Czy istnieje lepszy algorytm? Przypuszczam, że zapytania wystarczające. I wierzę, że mogę udowodnić dolną granicę . Problem staje się również łatwy - tzn. Zapytania poprzez wyszukiwanie binarne - pod obietnicą, że istnieje różnica między największą wartością a drugą co do wielkości wartością. Jeśli to pomoże, możesz założyć, że wszystkie wartości mieszczą się w zakresie od do .$O(\log^2 n)$$\Omega(\log^2 n)$$\tilde{O}(\log n)$$\Omega(1)$$0$$O(\log n)$

Rozszerzony komentarz pomysłu lub dwóch w kierunku dolnej granicy. Niech , powiedzmy (chociaż najlepszy wybór może być inny) i niech . Rozważ narysowanie danych wejściowych, wybierając losowo permutację tych wartości.$B = \Theta(\log n)$$\{v_1,\dots,v_n\} = \{\frac{1}{n}B, \dots, \frac{n-1}{n}B, B\}$

Pomysł powinien polegać na tym, że jeśli naprawimy wskaźniki wszystkich wartości z wyjątkiem wartości i , wówczas powinniśmy być w stanie pokazać różnicę w prawdopodobieństwie wyboru jednego algorytmu względem drugiego bardzo mała: odległość wariancji między wynikami zapytań algorytmów jest bardzo mała, biorąc pod uwagę rozkład 50-50 przypisań tych wartości do dwóch dostępnych wskaźników oraz wyniki dowolnej sekwencji zapytań.$B$$\frac{n-1}{n}B$

Ten argument dotyczy każdej pary sąsiednich wartości, więc otrzymujemy łańcuch ograniczeń prawdopodobieństwa, że ​​algorytm wybierze najwyższe, drugie co do wielkości, ... wartości. Daje to górną granicę oczekiwanej wartości algorytmu, więc ustawiamy tę górną granicę na i sprawdzamy, jaka liczba zapytań musi być.$B-1$

Nie mogłem jeszcze ulepszyć z powyższym podejściem, ale myślę, że możesz dostać jeśli możesz wykorzystać fakt, że zapytania nie mogą pomóc w wielu krokach na raz. To znaczy, jeśli zapytanie zmienia się, gdy przenosimy najwyższą wartość do innego indeksu, to jeden z tych przypadków nie zmienia się, gdy przenosimy dowolną inną wartość do innego indeksu.$\log n$$(\log n)^2$

Różnicowa prywatność może być pomocna w jednym z tych kroków, np. Jeśli pomyślimy tylko o przypadku, w którym zamienimy lokalizację dwóch najwyższych wartości, „czułość” tego zapytania jest po prostu a następnie zaawansowana kompozycja może być pomocna.$\frac{B}{n}$

Przykro mi, ale jest na wpół upieczony, ale mam nadzieję, że może się przydać!