For some hypothesis classes and input distributions, active agnostic learning
needs exponentially fewer samples than passive learning; for other classes and
distributions, it offers little to no improvement. The most popular algorithms
for agnostic active learning express their performance in terms of a parameter
called the disagreement coefficient, but it is known that these algorithms are
inefficient on some inputs.
We take a different approach to agnostic active learning, getting an
algorithm that is competitive with the optimal algorithm for any binary
hypothesis class $H$ and distribution $D_X$ over $X$. In particular, if any
algorithm can use $m^*$ queries to get $O(\eta)$ error, then our algorithm uses
$O(m^* \log |H|)$ queries to get $O(\eta)$ error. Our algorithm lies in the
vein of the splitting-based approach of Dasgupta [2004], which gets a similar
result for the realizable ($\eta = 0$) setting.
We also show that it is NP-hard to do better than our algorithm's $O(\log
|H|)$ overhead in general.

针对给定的二元假设类和分布，该研究提出了一种与最优算法相竞争的无偏主动学习算法，该算法在错误率为 η 的情况下只需要 O (m^* log |H|) 的查询次数，并且证明了超越 O (log |H|) 的开销是 NP 难的。