<p>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 <a href="http://jeffe.cs.illinois.edu/teaching/algorithms/notes/13-adversary.pdf" rel="nofollow noreferrer">these notes</a> by Jeff Erickson. </p>

<p>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 <span class="math-container">$f^*$</span>. Instead, the adversary always makes sure that <em>some</em> <span class="math-container">$f^*$</span> is consistent with the oracle answers. In Szorenyi's paper, the adversary will make sure that there is always some <span class="math-container">$f_i$</span> which is consistent with all of the query answers. More precisely, let <span class="math-container">$\cal G$</span> be the set of all <span class="math-container">$f_i$</span> which are consistent with answering <span class="math-container">$0$</span> to all queries so far. If no queries have been answered yet, then <span class="math-container">$\mathcal{G} = \{f_1, \ldots, f_d\}$</span>. Szorenyi shows that answering a new query by <span class="math-container">$0$</span> decreases <span class="math-container">$|\cal G|$</span> by at most <span class="math-container">$2d/(d\tau^2 - 1)$</span>, so as long as <span class="math-container">$|\mathcal{G}| &gt; 2d / (d\tau^2-1)$</span>, the adversary can keep answering queries by <span class="math-container">$0$</span> and <span class="math-container">$\cal G$</span> 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 <span class="math-container">$\tau$</span> with <span class="math-container">$|\mathcal{G}| - d / (d\tau^2-1)&gt; 0$</span> many concepts in <span class="math-container">$\mathcal{G}$</span>. But any concept in <span class="math-container">$\mathcal{G}$</span> could be <span class="math-container">$f^*$</span>, and the algorithm would output the wrong answer for at least one such possible <span class="math-container">$f^*$</span>.</p>

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

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

CC BY-SA 4.0
2019-03-12T16:22:09.627Z
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
CC BY-SA 4.0
2019-03-12T17:06:04.427Z
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
CC BY-SA 4.0
2019-03-12T00:34:52.093Z
2019-03-12T22:18:35.090Z
2019-03-12T22:18:35.090Z
Sasho Nikolov
<p>I am asking about the proof in Theorem 5 (page 6) of this paper,
<a href="http://www.inf.u-szeged.hu/%7Eszorenyi/Cikkek/sq_d0_ext.pdf" rel="nofollow noreferrer">http://www.inf.u-szeged.hu/~szorenyi/Cikkek/sq_d0_ext.pdf</a></p>
<p>Quite a few things about this short argument seem unclear to me,</p>
<ul>
<li><p>Towards the bottom of page 3 when the SQ oracle was defined it seemed that for a tolerance parameter of <span class="math-container">$\tau$</span> and the true concept being <span class="math-container">$f^*$</span> and a query concept of <span class="math-container">$h$</span> the SQ oracle is guaranteed to return a <span class="math-container">$c$</span> s.t <span class="math-container">$\vert c - \langle f^*,h \rangle \vert \leq \tau$</span>. Now in the proof of Theorem 5 (page 6) there is no <span class="math-container">$f^*$</span> that has been mentioned! So is there an implicit assumption about what this <span class="math-container">$f^*$</span> is?</p>
<p>Are we assuming that this <span class="math-container">$f^*$</span> is a part of this uncorrelated set, <span class="math-container">$\{f_1,f_2,..,f_d\}$</span>?</p>
</li>
<li><p>The argument in Theorem 5 seems to assume that the adversarial oracle can return <span class="math-container">$c=0$</span> always. But why should this be a consistent option given that the oracle is forced to satisfy the condition, <span class="math-container">$\vert c - \langle f^*,h \rangle \vert \leq \tau$</span>. If <span class="math-container">$c=0$</span> has to always be a consistent oracle reply then we need it to be true that all queries <span class="math-container">$h$</span> being made are such that it satisfies the equation, <span class="math-container">$\vert\langle f^*,h \rangle \vert \leq \tau$</span>. But now this is a new constraint that the queries <span class="math-container">$h$</span> have to be of somewhat low correlation with the truth <span class="math-container">$f^*$</span>!. But this wasnt specified anywhere!</p>
<p>At this point it seems that the algorithm could be lucky and it could send to the Oracle the query <span class="math-container">$h = f^*$</span> and then if <span class="math-container">$c=0$</span> has to be a valid adversarial reply we need <span class="math-container">$\tau \geq 1$</span> and that doesnt make sense!</p>
</li>
<li><p>Lastly what else is the SQ algorithm allowed to do apart from making <span class="math-container">$(h,\tau)$</span> SQ-queries? Are we forcing it to work s.t after it receives <span class="math-container">$c=0$</span> as the Oracle reply all its allowed to do is to eliminate from its set of probable outputs those functions in the set <span class="math-container">$\{f_1,..,f_d\}$</span> which are more than <span class="math-container">$\tau$</span> correlated? Why is it that the SQ algorithm never seems to consider that there could be functions in <span class="math-container">${\cal F}$</span> outside this uncorrelated set which are also more than <span class="math-container">$\tau$</span> correlated to the query <span class="math-container">$h$</span>?</p>
</li>
</ul>

<ds.algorithms><lower-bounds><query-complexity><stochastic-process>
The SQ argument in Balazs Szorenyi's paper
gradstudent
# The SQ argument in Balazs Szorenyi's paper

(Asked by: username_0 on 2019-03-11)

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](http://www.inf.u-szeged.hu/%7Eszorenyi/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$?

**Tags:** ds.algorithms, lower-bounds, query-complexity, stochastic-process


---

## 1 answers

### Answer by username_1 on 2019-03-12. Score: 4 | Accepted answer

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](http://jeffe.cs.illinois.edu/teaching/algorithms/notes/13-adversary.pdf) 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.

> **Comments:**
> **username_0**: 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?  
> **username_1**: 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.  

---

