Biorąc pod uwagę

Oto problem o smaku podobnym do nauki junt:

Dane wejściowe: Funkcja , reprezentowana przez wyrocznię członkowską, tzn. Wyrocznię, która dała , zwraca . $f: \{0,1\}^n \rightarrow \{-1,1\}$ $x$ $f(x)$

Cel: Znajdź podmoduł $S$ o wartości $\{0,1\}^n$ o objętości $|S|=2^{n-k}$ takie, że $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.1$ . Zakładamy, że taki podrzędny istnieje.

Łatwo jest uzyskać algorytm działający w czasie $n^{O(k)}$ i zwracający prawidłową odpowiedź z prawdopodobieństwem $\ge 0.99$ , wypróbowując wszystkie $(2n)^k$ sposobów wyboru podmodułu i próbkując średnią w każdym z nich.

Ja interesującego znalezienie algorytm, który działa w czasie $poly(n,2^k)$ . Alternatywnie, dolna granica byłaby świetna. Problem ma podobny smak do nauki junt, ale nie widzę rzeczywistego związku między ich trudnościami obliczeniowymi.

Aktualizacja: @Thomas poniżej pokazuje, że złożoność Próbkę tego problemu jest $poly(2^k,\log n)$ . Ciekawym zagadnieniem jest jednak złożoność obliczeniowa problemu.

Edycja: dla uproszczenia można założyć, że istnieje podmoduł z $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.2$ (zwróć uwagę na lukę: szukamy pod kostki ze średnią $\ge 0.1$ .) Jestem prawie pewien, że każde rozwiązanie problemu z luką rozwiąże problem bez luki.

— pierożek Mobiusa
źródło

Tutaj lepiej wiąże się złożoność próbki. (Chociaż złożoność obliczeniowa jest wciąż .) $n^k$

Twierdzenie. Załóżmy, że istnieje pod kostka o rozmiarze taka że . Za pomocą próbek możemy z dużym prawdopodobieństwem zidentyfikować pod kostkę o wielkości tak, aby $S$ $2^{n-k}$ $|\mathbb{E}_{x \in S}[f(x)]| \geq 0.12$ $O(2^k \cdot k \cdot \log n)$ $S'$ $2^{n-k}$ . $|\mathbb{E}_{x \in S'}[f(x)]| \geq 0.1$

Zwróć uwagę na niewielką utratę parametrów ( jest optymalna w porównaniu z gwarancją ). $0.12$ $0.1$

Dowód. Odbiór punktów równomiernie losowo zapytania w każdym . $m$ $P \subset \{0,1\}^n$ $f$ $x \in P$

Napraw podmoduł o rozmiarze . Mamy . W związku z Chernoffem Również $S$ $2^{n-k}$ $\mathbb{E}[|S \cap P|]=m 2^{-k}$

P. [| S. \cap P. | < m {2)}^{- k - 1}] \leq {2)}^{- Ω (m {2)}^{- k})} .

$\mathbb{P}[|S \cap P| < m 2^{-k-1}] \leq 2^{-\Omega(m 2^{-k})}.$

P. [| {mi}_{x \in S. \cap P.} [fa (x)] - {mi}_{x \in S.} [fa (x)] | > ε] \leq {2)}^{- Ω (| S. \cap P. | ε^{2)})} .

$\mathbb{P}[| \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | > \varepsilon] \leq 2^{-\Omega(|S \cap P| \varepsilon^2)}.$

Związkiem związanym ze wszystkimi wyborów, mamy ${n \choose k}2^k$ $S$ Tak więc przez podniesienie, można zapewnić, że z prawdopodobieństwem co najmniej, można oszacowaćw granicachdla subcubesz rozmiar

P. [\forall S. | {mi}_{x \in S. \cap P.} [fa (x)] - {mi}_{x \in S.} [fa (x)] | \leq ε] \geq 1 - (\binom{n}{k}) {2)}^{k} {2)}^{- Ω (m {2)}^{- k} ε^{2)})} .

$\mathbb{P}[\forall S ~~ | \mathbb{E}_{x \in S \cap P}[f(x)] - \mathbb{E}_{x \in S}[f(x)] | \leq \varepsilon] \geq 1 - {n \choose k} 2^k 2^{-\Omega(m 2^{-k} \varepsilon^2)}.$

m = O (2^{k} / ε^{2} \cdot k \log n)

$m = O(2^k/\varepsilon^2 \cdot k \log n)$

0.99

$0.99$

E_{x \in S} [f (x)]

$\mathbb{E}_{x \in S}[f(x)]$

ε

$\varepsilon$

S

$S$

2^{n - k}

$2^{n-k}$ .

Przy ustawieniu dowodzimy twierdzenia: wybranie podmodułu o największym z dużym prawdopodobieństwem spełni wymagania. CO BYŁO DO OKAZANIA $\varepsilon=0.01$ $| \mathbb{E}_{x \in S \cap P}[f(x)]|$

— Tomasz
źródło

C \cdot 2^{k}

$C \cdot 2^k$

C

$C$

C

$C$

n^{k}

$n^k$

Innym sposobem na zobaczenie tego jest to, że przestrzeń zasięgu, którą opisujesz, ograniczyła wymiar zniszczenia, a zatem ograniczyła wymiar VC, a następnie rzuciłeś na nią twierdzenie o aproksymacji eps.

— Suresh Venkat