Active and passive learning of linear separators under log-concave distributions

By Maria-Florina Balcan, Philip M. Long. 2012

157 citations recorded by the source corpus.

We provide new results concerning label efficient, polynomial time, passive and active learning of linear separators. We prove that active learning provides an exponential improvement over PAC (passive) learning of homogeneous linear separators under nearly log-concave distributions. Building on this, we provide a computationally efficient PAC algorithm with optimal (up to a constant factor) sample complexity for such problems. This resolves an open question concerning the sample complexity of efficient PAC algorithms under the uniform distribution in the unit ball. Moreover, it provides the first bound for a polynomial-time PAC algorithm that is tight for an interesting infinite class of hypothesis functions under a general and natural class of data-distributions, providing significant progress towards a longstanding open question. We also provide new bounds for active and passive learning in the case that the data might not be linearly separable, both in the agnostic case and and under the Tsybakov low-noise condition. To derive our results, we provide new structural results for (nearly) log-concave distributions, which might be of independent interest as well.

How researchers see this paper

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

Citations in the corpus

Deep Active Learning with a Neural Architecture Search (2018, background): “The literature on active learning in the context of classical models such as SVMs is extensive [3, 6, 27, 2, 1, 15], and clearly beyond the scope of this paper.”
Efficient Representations for Lifelong Learning and Autoencoding (2014, background): “In this case the sample complexity would be Ω(mn/ ) even under log-concave distributions [5].”
A compression technique for analyzing disagreement-based active learning (2014, background): “…respect to P as θ ( r 0 ) (cid:44) sup The disagreement coefﬁcient was originally introduced to the active learning literature by Han-neke (2007a), and has been studied and bounded by a number of authors (see e.g., Hanneke, 2007a; Friedman, 2009; Wang, 2011; Hanneke, 2014; Balcan and Long, 2013).”
Efficient and Parsimonious Agnostic Active Learning (2015, methodology): “…the monograph of Hanneke [2014] for an overview of the existing literature, including alternative settings where additional assumptions are placed on the data source (e.g., separability) as is common in other works [Dasgupta, 2005, Balcan et al., 2007, Balcan and Long, 2013]. ar X iv :1 50 6.”
The power of localization for efficiently learning linear separators with noise (2013, methodology): “[8] For any c 3 > 0 , there is a c 4 > 0 such that, for all d ≥ 4 , the following holds.”