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


1 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.

  • $\begingroup$ 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? $\endgroup$ Mar 12, 2019 at 16:22
  • $\begingroup$ 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. $\endgroup$ Mar 12, 2019 at 17:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.