# The SQ argument in Balazs Szorenyi's paper

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

• 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$$?

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.
• Thanks! I guess this looks like an odd argument style to me because I am not from a traditional CS background! So here it seems that you are letting the adversary choose the $f^*$ after it has seen all the queries sent by the algorithm. But isnt that violating the premise of what a learning algorithm is? Isnt it just a part of the definition of the SQ oracle that it knows/commits to a $f^*$ from the beginning and gives noisy values of its inner-product with the query sent? Isnt it unfair to the learner if you let the oracle choose $f^*$ after seeing all the queries? – gradstudent Mar 12 '19 at 16:22
• It's just a way to identify the worst-case $f^*$ (and worst-case query answers consistent with $f^*$) for every learner by playing a game with the learner. In the game, the adversary controls the oracle. The game is "fair" because at the end of it, the adversary must be able to reveal some $f^*$ consistent with all its query answers. Because of this, if the oracle had committed to this $f^*$ from the beginning, the algorithm would've made the exact same queries and gotten the exact same answers. – Sasho Nikolov Mar 12 '19 at 17:06