<p><strong>Setting:</strong></p>

<p>Let <span class="math-container">$X$</span> be a finite set and <span class="math-container">$C = \{0, 1\}^X$</span> a finite family of classifiers on <span class="math-container">$X$</span>. Fix an <span class="math-container">$f \in \{0, 1\}^X$</span> not in <span class="math-container">$C$</span>, a (possibly randomized and adaptive) learner <span class="math-container">$A$</span> has access to a membership query oracle <span class="math-container">$EX(f)$</span>, that on input <span class="math-container">$x$</span> reply with <span class="math-container">$f(x)$</span>. For any <span class="math-container">$h \in C$</span>, define <span class="math-container">$R(h) = \frac{1}{|X|}\sum_{x \in X}\mathbb{I}(h(x) \neq f(x))$</span>. </p>

<p>The learner goal is for any <span class="math-container">$f \notin C$</span> and any <span class="math-container">$\epsilon \in (0, 1)$</span> to output a classifier <span class="math-container">$h_A \in C$</span>, such that <span class="math-container">$\mathbb{E}[R(h_A)] \le \min_{c \in C} R(c) + \epsilon$</span> provided that it can ask enough queries to <span class="math-container">$EX(f)$</span>. Here  the randomization is with respect to the internal coind flip of <span class="math-container">$A$</span>.</p>

<p><strong>Question:</strong>
Is there any known lower bound to the number of queries needed by any algorithm to achive the above <span class="math-container">$\epsilon$</span> approximation? (Even a reference to such a similar results would be very helpful!) </p>

<p>This setting resembles classical agnostic PAC learning where there are lower bound of the form <span class="math-container">$\Omega(d/\epsilon^2)$</span> with <span class="math-container">$d$</span> beign the VC dimension of <span class="math-container">$C$</span>, but it differs in not having a distribution on <span class="math-container">$X$</span> and in allowing the algorithms to freely choose the queries, even in an adaptive fashion. Another setting that came to my mind is that of exact learning with membership queries (e.g. <a href="https://www.sciencedirect.com/science/article/pii/S030439750300608X" rel="nofollow noreferrer">Queries revisited by Angluin</a>) but here the difference is in that <span class="math-container">$f\in C$</span>.</p>

CC BY-SA 4.0
2019-05-16T18:43:30.797Z
To clarify: are you asking if there exists a general PAC-style lower bound, e.g., phrased in terms of some combinatorial quantity depdening on $C$? Or are you asking for examples of $C$ for which such lower bounds are known? Or are you asking for examples of $C$ for which such lower bounds are known *and are strictly larger than the  non-agnostic counterpart*?
Clement C.
CC BY-SA 4.0
2019-05-17T08:22:41.567Z
Either a general lower bound based on some combinatorial quantity related to $C$, or even an example of $C$ for which a lower bound is known would be useful.
Andrea
CC BY-SA 4.0
2019-05-18T16:39:21.800Z
It's known e.g. for the class $\mathcal{C}$ of *monotone* Boolean functions -- under the uniform distribution, with membership queries, even non-agnostically, one needs $2^{\Omega(\sqrt{n}/\varepsilon)}$ queries. Is that the kind of results you are looking for?
Clement C.
CC BY-SA 4.0
2019-05-18T19:55:38.907Z
This result does not apply to the setting I'm considering, because I do not assume any distribution over $X$. The algorithms can freely choose the istances for which they want the label, even adaptively (i.e. choosing the next $x$ based on the labels of the previously queried istances).
Andrea
CC BY-SA 4.0
2019-05-18T21:40:46.380Z
So... lower bounds against the uniform distribution apply then. Lower bounds against an "easier" model apply to the stronger.
Clement C.
CC BY-SA 4.0
2019-05-19T09:12:06.877Z
I'm not sure that assuming a distribution over $X$ makes the model "easier". To make things concrete, an algorithm that learns $C$ under the uniform distribution, also learn $C$ in the above setting (since the risk w.r.t. $f$ and the uniform distribution over $X$ will be the same as $R$ defined above). While, it is not necessary true that the reverse hold. Allowing the algorithm to freely choose the $x$s should not make the problem not harder.
Andrea
CC BY-SA 4.0
2019-05-19T16:35:17.017Z
Sorry, I somehow got the impression there was an unknown distribution there. In that case, your setting is equivalent to "PAC-learning under the uniform distribution with membership queries" (in both the agnostic and non-agnostic case, respectively). The distance is with regard to the uniform distribution, you get membership queries, and you can simulate uniform labelled samples if you want.
Clement C.
<machine-learning><lg.learning>
Lower bound to agnostic learning with membership queries
Andrea
# Lower bound to agnostic learning with membership queries

(Asked by: username_0 on 2019-05-16)

**Setting:**

Let $X$ be a finite set and $C = \{0, 1\}^X$ a finite family of classifiers on $X$. Fix an $f \in \{0, 1\}^X$ not in $C$, a (possibly randomized and adaptive) learner $A$ has access to a membership query oracle $EX(f)$, that on input $x$ reply with $f(x)$. For any $h \in C$, define $R(h) = \frac{1}{|X|}\sum\_{x \in X}\mathbb{I}(h(x) \neq f(x))$.

The learner goal is for any $f \notin C$ and any $\epsilon \in (0, 1)$ to output a classifier $h\_A \in C$, such that $\mathbb{E}[R(h\_A)] \le \min\_{c \in C} R(c) + \epsilon$ provided that it can ask enough queries to $EX(f)$. Here the randomization is with respect to the internal coind flip of $A$.

**Question:**
Is there any known lower bound to the number of queries needed by any algorithm to achive the above $\epsilon$ approximation? (Even a reference to such a similar results would be very helpful!)

This setting resembles classical agnostic PAC learning where there are lower bound of the form $\Omega(d/\epsilon^2)$ with $d$ beign the VC dimension of $C$, but it differs in not having a distribution on $X$ and in allowing the algorithms to freely choose the queries, even in an adaptive fashion. Another setting that came to my mind is that of exact learning with membership queries (e.g. [Queries revisited by Angluin](https://www.sciencedirect.com/science/article/pii/S030439750300608X)) but here the difference is in that $f\in C$.

**Tags:** machine-learning, lg.learning

> **Comments:**
> **username_1**: To clarify: are you asking if there exists a general PAC-style lower bound, e.g., phrased in terms of some combinatorial quantity depdening on $C$? Or are you asking for examples of $C$ for which such lower bounds are known? Or are you asking for examples of $C$ for which such lower bounds are known *and are strictly larger than the  non-agnostic counterpart*?  
> **username_0**: Either a general lower bound based on some combinatorial quantity related to $C$, or even an example of $C$ for which a lower bound is known would be useful.  
> **username_1**: It's known e.g. for the class $\mathcal{C}$ of *monotone* Boolean functions -- under the uniform distribution, with membership queries, even non-agnostically, one needs $2^{\Omega(\sqrt{n}/\varepsilon)}$ queries. Is that the kind of results you are looking for?  
> **username_0**: This result does not apply to the setting I'm considering, because I do not assume any distribution over $X$. The algorithms can freely choose the istances for which they want the label, even adaptively (i.e. choosing the next $x$ based on the labels of the previously queried istances).  
> **username_1**: So... lower bounds against the uniform distribution apply then. Lower bounds against an "easier" model apply to the stronger.  
> **username_0**: I'm not sure that assuming a distribution over $X$ makes the model "easier". To make things concrete, an algorithm that learns $C$ under the uniform distribution, also learn $C$ in the above setting (since the risk w.r.t. $f$ and the uniform distribution over $X$ will be the same as $R$ defined above). While, it is not necessary true that the reverse hold. Allowing the algorithm to freely choose the $x$s should not make the problem not harder.  
> **username_1**: Sorry, I somehow got the impression there was an unknown distribution there. In that case, your setting is equivalent to "PAC-learning under the uniform distribution with membership queries" (in both the agnostic and non-agnostic case, respectively). The distance is with regard to the uniform distribution, you get membership queries, and you can simulate uniform labelled samples if you want.  

---

## 0 answers

