Coarse sample complexity bounds for active learning

By Sanjoy Dasgupta. Neural Information Processing Systems, 2005

331 citations recorded by the source corpus.

View Paper: https://www.semanticscholar.org/paper/d14830a497faeb7ff245d4cf918fde48eca95729

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

Efficient and Parsimonious Agnostic Active Learning (2015, result): “…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.”
Optimal Value of Information in Graphical Models (2009, background): “While sample complexity bounds have been derived for some active learning problems ( c.f., Dasgupta, 2005; Balcan, Beygelzimer, & Langford, 2006), we are not aware of any active learning algorithms that perform provably optimal (even for restricted classes of problem instances).”
A theory of transfer learning with applications to active learning (2012, background): “…) (always); for instance, threshold classiﬁers have this property under any D , homogeneous linear separators have this property under a uniform D on the unit sphere in k dimensions, and intervals with positive width on X = [0 , 1] have this property under D = Uniform([0 , 1]) (see e.g., [Das05]).”
Analysis of Perceptron-Based Active Learning (2009, background): “In our sequential framework, we can bound |v̂t · xt||xt · u| away from 0 in expectation, under the uniform distribution, and hence the choice of α = 2 is most convenient, but α = 1 would work as well.”
Theory of Disagreement-Based Active Learning (2014, background): “Readers completely unfamiliar with active learning may also find the brief survey of Dasgupta [2011] helpful, as it provides a concise and lucid description of the main themes, without getting into as much technical detail as the present article. As mentioned, the focus of much of this article is on”
The power of localization for efficiently learning linear separators with noise (2013, background): “…active learning, and several general characterizations have been developed for describing when active learning could have an advantage over the classic passive supervised learning paradigm both in the noise free settings and in the agnostic case [24, 20, 3, 4, 28, 22, 17, 7, 36, 11, 43, 21, 38, 6].”
Active and passive learning of linear separators under log-concave distributions (2012, background): “…many modern applications (Dasgupta, 2011), with many exciting developments on understanding its underlying principles as well (Freund et al., 1997; Dasgupta, 2005; Balcan et al., 2006, 2007; Hanneke, 2007; Dasgupta et al., 2007; Castro and Nowak, 2007; Balcan et al., 2008; Koltchinskii, 2010;…”
Margin Based Active Learning (2007, background): “Margin-based Active Learning (with low-dimensional approximation) Using a more refined ratio VC-bound, one can easily improve the choice of m k = C −2 k (d k +ln(k/δ)) to m k = C −1 k (d k ln −1 +ln(k/δ) in Theorem 4.”
Two faces of active learning (2011, background): “There are now several learning algorithms which, on a variety of canonical examples, provably yield signiﬁcantly lower label complexity than supervised learning [9, 13, 10, 2, 3, 7, 15, 16, 12].”
Loss Minimization and Parameter Estimation with Heavy Tails (2013, methodology): “ses where the loss is classiﬁ- cation error, the rates can be improved to O˜(log(1/L⋆)) by using active learning, i.e., allowing the estimator to adaptively sample Y|X for values of X of its choosing [11, 3, 7]. We note that in our setting, the cases that are hardest for our (or any) estimator, are ”
APRIL: Active Preference-learning based Reinforcement Learning (2012, unknown): “The artificial active ranking problem used to investigate AEUS robustness is inspired from the active learning frame studied by [8], varying the dimension d of the space in 10, 20, 50, 100 (Fig.”
Agnostic active learning (2006, background): “There are simple examples where active learning does not help at all, even if there is no noise (see, for example, (Dasgupta, 2005)).”
Hierarchical sampling for active learning (2008, background): “Indeed, there are canonical examples in which active learning provably yields exponentially lower label complexity than supervised learning (Cohn et al., 1994; Freund et al., 1997; Dasgupta, 2005; Balcan et al., 2006; Balcan et al., 2007; Castro & Nowak, 2007; Hanneke, 2007; Dasgupta et al., 2007).”
Mixed-Initiative Active Learning (2012, methodology): “An xample of empirically optimal teaching outperforming A ti Learning: fi ding a decisio b undary in R1 (Dasgupta, 2006).”
The true sample complexity of active learning (2010, methodology): “However, in addition to these known positive results, there are simple (almost trivial) examples, such as learning intervals or non-homogeneous linear separators, where these analyses of sample complexity have indicated that perhaps active learning does not help at all (Dasgupta 2005; Hanneke 2007b)”
Understanding classifier errors by examining influential neighbors (2015, background): “For active learning, the example on which this set of classifiers disagree the most is considered most informative [26, 5, 21, 7, 1, 25].”