Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

Here is a problem with a similar flavor to learning juntas:

Input: A function $f: \{0,1\}^n \rightarrow \{-1,1\}$, represented by a membership oracle, i.e. an oracle that given $x$, returns $f(x)$.

Goal: Find a subcube $S$ of $\{0,1\}^n$ with volume $|S|=2^{n-k}$ such that $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.1$. We assume such a subcube exists.

It is easy to get an algorithm that runs in time $n^{O(k)}$ and returns a correct answer with probability $\ge 0.99$ by trying all $(2n)^k$ ways to choose a subcube and sampling the average in each one.

I'm interesting in finding an algorithm that runs in time $poly(n,2^k)$. Alternatively, a lower bound would be great. The problem has similar flavor to learning juntas, but I don't see an actual connection between their computational difficulty.

Update: @Thomas below proves that the sample complexity of this problem is $poly(2^k,\log n)$. The interesting issue is, still, the computational complexity of the problem.

Edit: you can assume for simplicity that there exists a subcube with $\left|\mathbb{E}_{x \in S} f(x) \right| \ge 0.2$ (notice the gap: we're looking for a subcube with average $\ge 0.1$.) I'm pretty sure any solution to the problem with the gap will also solve the problem without the gap.

Here is a better bound on the sample complexity. (Although the computational complexity is still $n^k$.)

Theorem. Assume there exists a subcube $S$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S}[f(x)]| \geq 0.12$. With $O(2^k \cdot k \cdot \log n)$ samples we can, with high probability, identify a subcube $S'$ of size $2^{n-k}$ such that $|\mathbb{E}_{x \in S'}[f(x)]| \geq 0.1$.

Note the small loss in parameters ($0.12$ is optimal versus guarantee of $0.1$).

Proof. Pick $m$ points $P \subset \{0,1\}^n$ uniformly at random and query $f$ at each $x \in P$.

Fix a subcube $S$ of size $2^{n-k}$. We have $\mathbb{E}[|S \cap P|]=m 2^{-k}$. By a Chernoff bound, $$\mathbb{P}[|S \cap P| < m 2^{-k-1}] \leq 2^{-\Omega(m 2^{-k})}.$$ Also $$\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)}.$$

By a union bound over all ${n \choose k}2^k$ choices of $S$, we have $$\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)}.$$ So by picking $m = O(2^k/\varepsilon^2 \cdot k \log n)$, we can ensure that, with probability at least $0.99$, we can estimate $\mathbb{E}_{x \in S}[f(x)]$ to within $\varepsilon$ for all subcubes $S$ of size $2^{n-k}$.

Setting $\varepsilon=0.01$, we prove the theorem: picking the subcube with the largest $| \mathbb{E}_{x \in S \cap P}[f(x)]|$ will, with high probability, satisfy the requirements. Q.E.D.

• Oh, whow, how silly of me: yes, the basic idea is that if you sample $C \cdot 2^k$ points, then an expected $C$ of them will be in each subcube, so with a modest value of $C$ that gives a large enough sample size to solve the problem, even after union-bounding over all $n^k$ Chernoff bounds. Also, I'm pretty sure that any solution can be adapted to eliminate the gap between 0.1 and 0.12, so I'll just add this as a comment to the question. Thanks!! Apr 29 '14 at 17:53
• Another way of seeing this is that the range space you describe has bounded shatter dimension and therefore bounded VC dimension, and then you throw the eps-approximation theorem at it. Apr 29 '14 at 18:13