# Lower bound to agnostic learning with membership queries

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) but here the difference is in that $$f\in C$$.

• 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. May 16 at 18:43
• 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 May 17 at 8:22
• 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. May 18 at 16:39
• 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 May 18 at 19:55
• So... lower bounds against the uniform distribution apply then. Lower bounds against an "easier" model apply to the stronger. – Clement C. May 18 at 21:40