Shuang Chen, Herbert Freeman
International Journal of Pattern Recognition and Artificial Intelligence
We study the properties of the agnostic learning framework of Haussler (1992) and Kearns, Schapire, and Sellie (1994). In particular, we address the question: is there any situation in which member-ship queries are useful in agnostic learning? Our results show that the answer is negative for distribution-independent agnostic learning and positive for agnostic learning with respect to a specific marginal distribution. Namely, we give a simple proof that any concept class learnable agnostically by a distribution-independent algorithm with access to membership queries is also learnable agnostically without membership queries. This resolves an open problem posed by Kearns et al. (1994). For agnostic learning with respect to the uniform distribution over {0,1} n we show a concept class that is learnable with membership queries but computationally hard to learn from random examples alone (assuming that one-way functions exist).
Shuang Chen, Herbert Freeman
International Journal of Pattern Recognition and Artificial Intelligence
Balaji Ganesan, Arjun Ravikumar, et al.
ICON 2023
Imran Nasim, Melanie Weber
SCML 2024
Vinayak Gupta, Rajmohan C, et al.
ICON 2022