Agnostic Membership Query Learning with Nontrivial Savings: New Results, Techniques

Ari Karchmer

(Abridged) Designing computationally efficient algorithms in the agnostic learning model (Haussler, 1992; Kearns et al., 1994) is notoriously difficult. In this work, we consider a…