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

<p><b>Theorem.</b> <i>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$.</i></p>

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

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

<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| &lt; 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)] | &gt; \varepsilon] \leq 2^{-\Omega(|S \cap P| \varepsilon^2)}.$$</p>

<p>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}$.</p>

<p>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.</p>

CC BY-SA 3.0
2014-04-29T17:53:07.133Z
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!!
greg
CC BY-SA 3.0
2014-04-29T18:13:07.730Z
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.
Suresh Venkat
CC BY-SA 3.0
2014-04-29T17:41:11.240Z
2014-04-29T18:00:50.917Z
2014-04-29T18:00:50.917Z
Thomas Steinke
<p>Here is a problem with a similar flavor to learning juntas:</p>

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

<p><strong>Goal:</strong> 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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<p>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.</p>

<machine-learning><lg.learning><boolean-functions><sample-complexity>
Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value
greg
# Given $f:\{0,1\}^n \rightarrow \{-1,1\}$, find a subcube with large volume and large average value

(Asked by: username_0 on 2014-04-29)

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.

**Tags:** machine-learning, lg.learning, boolean-functions, sample-complexity

---

## 1 answers

### Answer by username_1 on 2014-04-29. Score: 7

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.

> **Comments:**
> **username_0**: 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!!  
> **username_2**: 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.  

---

