The SQ argument in Balazs Szorenyi's paper

Question

I am asking about the proof in Theorem 5 (page 6) of this paper, http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf

Quite a few things about this short argument seem unclear to me,

• Towards the bottom of page 3 when the SQ oracle was defined it seemed that for a tolerance parameter of $\tau$ and the true concept being $f^*$ and a query concept of $h$ the SQ oracle is guaranteed to return a $c$ s.t $\vert c - \langle f^*,h \rangle \vert \leq \tau$. Now in the proof of Theorem 5 (page 6) there is no $f^*$ that has been mentioned! So is there an implicit assumption about what this $f^*$ is?

  Are we assuming that this $f^*$ is a part of this uncorrelated set, $\{f_1,f_2,..,f_d\}$?

• The argument in Theorem 5 seems to assume that the adversarial oracle can return $c=0$ always. But why should this be a consistent option given that the oracle is forced to satisfy the condition, $\vert c - \langle f^*,h \rangle \vert \leq \tau$. If $c=0$ has to always be a consistent oracle reply then we need it to be true that all queries $h$ being made are such that it satisfies the equation, $\vert\langle f^*,h \rangle \vert \leq \tau$. But now this is a new constraint that the queries $h$ have to be of somewhat low correlation with the truth $f^*$!. But this wasnt specified anywhere!

  At this point it seems that the algorithm could be lucky and it could send to the Oracle the query $h = f^*$ and then if $c=0$ has to be a valid adversarial reply we need $\tau \geq 1$ and that doesnt make sense!

• Lastly what else is the SQ algorithm allowed to do apart from making $(h,\tau)$ SQ-queries? Are we forcing it to work s.t after it receives $c=0$ as the Oracle reply all its allowed to do is to eliminate from its set of probable outputs those functions in the set $\{f_1,..,f_d\}$ which are more than $\tau$ correlated? Why is it that the SQ algorithm never seems to consider that there could be functions in ${\cal F}$ outside this uncorrelated set which are also more than $\tau$ correlated to the query $h$?

Answer 1

This is a standard adversary argument, not very different from adversary arguments taught in undergraduate algorithms courses. If you are unfamiliar with such arguments, then you can check out these notes by Jeff Erickson.

The idea for the proof is that the SQ oracle is controlled by an adversary, and the adversary does not have to initially commit to a specific $f^*$. Instead, the adversary always makes sure that some $f^*$ is consistent with the oracle answers. In Szorenyi's paper, the adversary will make sure that there is always some $f_i$ which is consistent with all of the query answers. More precisely, let $\cal G$ be the set of all $f_i$ which are consistent with answering $0$ to all queries so far. If no queries have been answered yet, then $\mathcal{G} = \{f_1, \ldots, f_d\}$. Szorenyi shows that answering a new query by $0$ decreases $|\cal G|$ by at most $2d/(d\tau^2 - 1)$, so as long as $|\mathcal{G}| > 2d / (d\tau^2-1)$, the adversary can keep answering queries by $0$ and $\cal G$ will remain non-empty. Moreover, while this is true, the algorithm cannot stop and output an answer, because any possible concept it outputs will have correlation less than $\tau$ with $|\mathcal{G}| - d / (d\tau^2-1)> 0$ many concepts in $\mathcal{G}$. But any concept in $\mathcal{G}$ could be $f^*$, and the algorithm would output the wrong answer for at least one such possible $f^*$.

Another way to see the last point is the following. Suppose that the algorithm outputs something while $|\mathcal{G}| > 2d / (d\tau^2-1)$. Then take an element of $\cal G$ that has correlation less than $\tau$ with the algorithm's output, and call it $f^*$. Rerun the whole process again with the oracle always outputting $0$: all the oracle answers are consistent with $f^*$ (by the construction of $\cal G$) and the algorithm would produce the same output, but that output would be incorrect for $f^*$. Note that this assumes that the algorithm is deterministic.

One detail he doesn't mention is that once $|\mathcal{G}| \le 2d / (d\tau^2-1)$, the adversary can pick some $f^* \in \mathcal{G}$ and answer new queries in any way consistent with $f^*$. This doesn't matter much in the proof because it can only happen once $(d\tau^2 - 1)/2$ queries have been made.