Rates of convergence in active learning

By Steve Hanneke. 2011

162 citations recorded by the source corpus.

We study the rates of convergence in generalization error achievable by active learning under various types of label noise. Additionally, we study the general problem of model selection for active learning with a nested hierarchy of hypothesis classes and propose an algorithm whose error rate provably converges to the best achievable error among classifiers in the hierarchy at a rate adaptive to both the complexity of the optimal classifier and the noise conditions. In particular, we state sufficient conditions for these rates to be dramatically faster than those achievable by passive learning.

Subfields: Artificial Intelligence, Management Science and Operations Research

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Management Science and Operations Research

Citations in the corpus

Deep Active Learning with a Neural Architecture Search (2018, background): “Theo-retically, active learning has a huge potential, especially in cases where exponential speedup in sample complexity can be achieved [12, 29, 11].”
The power of localization for efficiently learning linear separators with noise (2013, background): “Localization [9, 15, 44, 4, 16, 36, 29, 8] refers to the practice of progressively narrowing the focus of a learning algorithm to an increasingly restricted range of possibilities (which are known to be safe given the information up to a certain point in time), thereby improving the stability of…”
Teaching a black-box learner (2019, methodology): “We show bounds on the number of teaching examples needed that depend only on the VC dimension ofH and its disagreement coefficient (Hanneke, 2011).”
A theory of transfer learning with applications to active learning (2012, background): “In particular, Haussler et al. (1992) found that for any concept space of finite VC dimension d , for any prior and data distribution, O(d/ε) random labeled examples are sufficient for the expected error rate of the Bayes classifier produced under the posterior distribution to be at most ε.”
Active and passive learning of linear separators under log-concave distributions (2012, methodology): “, 2005), most of the theoretical developments have focused on the so called disagreement-based active learning paradigm (Hanneke, 2011; Koltchinskii, 2010); methods and analyses developed in this context are often suboptimal, as they take a conservative approach and consider strategies that query ev”
A compression technique for analyzing disagreement-based active learning (2014, background): “Speciﬁcally, the following condition of Mammen and Tsybakov (1999) has been studied for several algorithms (see e.g., Balcan, Broder, and Zhang, 2007; Hanneke, 2011; Koltchinskii, 2010; Han-neke, 2012; Hanneke and Yang, 2012; Hanneke, 2014; Beygelzimer, Hsu, Langford, and Zhang, 2010; Hsu, 2010).”