2022

Fast Rates in Pool-Based Batch Active Learning

Gentile, Claudio, Wang, Zhilei, Zhang, Tong

Understand

We consider a batch active learning scenario where the learner adaptively issues batches of points to a labeling oracle.

Sampling labels in batches is highly desirable in practice due to the smaller number of interactive rounds with the labeling oracle (often human beings).
However, batch active learning typically pays the price of a reduced adaptivity, leading to suboptimal results.
In this paper we propose a solution which requires a careful trade off between the informativeness of the queried points and their diversity.

Built on

Diverse mini-batch active learning
Original
Zhdanov, F. (2019) · 1901
Earlier work this paper cites.
Batchbald: Efficient and diverse batch acquisition for deep bayesian active learning
Original
Kirsch, A., van Amersfoort, J., and Gal, Y. (2019) · 1906
Earlier work this paper cites.
Submodularity in data subset selection and active learning
Wei, K., Iyer, R., and Bilmes, J. (2015) · 1963
Earlier work this paper cites.
On the density of families of sets
Sauer, N. (1972) · 1972
Earlier work this paper cites.
Smooth discrimination analysis
Mammen, E. and Tsybakov, A. (1999) · 1999
Earlier work this paper cites.
Task-aware variational adversarial active learning
Original
Kim, K., Park, D. Kim, K., and Chun, S. (2020) · 2002
Earlier work this paper cites.
The covering number in learning theory
Original
Zhou, D.-X. (2002) · 2002
Earlier work this paper cites.
Analysis of a greedy active learning strategy
Dasgupta, S. (2004) · 2004
Earlier work this paper cites.
Coarse sample complexity bounds for active learning
Dasgupta, S. (2005) · 2005
Earlier work this paper cites.
Batch mode active learning and its application to medical image classification
Hoi, S., Jin, R., Zhu, J., and Lyu, M. R. (2006) · 2006
Earlier work this paper cites.
Margin based active learning
Balcan, M.-F., Broder, A., and Zhang, T. (2007) · 2007
Earlier work this paper cites.
Minimax bounds for active learning
Castro, R. and Nowak, R. (2008) · 2008
Earlier work this paper cites.
Adaptive rates of convergence in active learning
Hanneke, S. (2009) · 2009
Earlier work this paper cites.
Parametric bandits: The generalized linear case
Filippi, S., Cappe’, O., Garivier, A., and Szepesvari, C. (2010) · 2010
Earlier work this paper cites.
Rademacher complexities and bounding the excess risk of active learning
Koltchinskii, V. (2010) · 2010
Earlier work this paper cites.
The geometry of generalized binary search
Nowak, R. D. (2011) · 2011
Earlier work this paper cites.

Similar

Selective sampling and active learning from single and multiple teachers
Dekel, O., Gentile, C., and Sridharan, K. (2012) · 2012
Cited alongside, same era.
On multilabel classification and ranking with partial feedback
Gentile, C. and Orabona, F. (2012) · 2012
Cited alongside, same era.
Selective labeling via error bound minimization
Gu, Q., Zhang, T., Han, J., and Ding, C. (2012) · 2012
Cited alongside, same era.
Glister: Generalization based data subset selection for efficient and robust learning
Original
Killamsetty, K., Sivasubramanian, D., Ramakrishnan, G., and Iyer, R. (2020) · 2012
Cited alongside, same era.
Active and passive learning of linear separators under log-concave distributions
Balcan, N. and Long, P. (2013) · 2013
Cited alongside, same era.
Near-optimal batch mode active learning and adaptive submodular optimization
Chen, Y. and Krause, A. (2013) · 2013
Cited alongside, same era.
Eluder dimension and the sample complexity of optimistic exploration
Russo, D. and Van Roy, B. (2013) · 2013
Cited alongside, same era.
Batch-mode active learning via error bound minimization
Gu, Q., Zhang, T., and Han, J. (2014) · 2014
Cited alongside, same era.
Theory of disagreement-based active learning
Hanneke, S. (2014) · 2014
Cited alongside, same era.
Sequential information maximization: When is greedy near-optimal?
Chen, Y., Hassani, S. H., Karbasi, A., and Krause, A. (2015) · 2015
Cited alongside, same era.
Near-optimal bayesian active learning with correlated and noisy tests
Chen, Y., Hassani, S. H., and Krause, A. (2017) · 2017
Cited alongside, same era.
Adaptive submodularity: A new approach to active learning and stochastic optimization
Original
Golovin, D. and Krause, A. (2017) · 2017
Cited alongside, same era.

Then

Deep batch active learning by diverse, uncertain gradient lower bounds
Ash, J., Zhang, C., Krishnamurthy, A., Langford, J., and Agarwal, A. (2020) · 2020
Later among the works it cites.
Improved optimistic algorithms for logistic bandits
Faury, L., Abeille, M., Calauzènes, C., and Fercoq, O. (2020) · 2020
Later among the works it cites.
Bandit Algorithms
Lattimore, T. and Szepesvari, C. (2020) · 2020
Later among the works it cites.
Deep active learning: Unified and principled method for query and training
Shui, C., Zhou, F. Gagne, C., and Wang, B. (2020) · 2020
Later among the works it cites.
Data summarization via bilevel optimization
Borsos, Z., Mutny, M., Tagliasacchi, M., and Krause, A. (2021) · 2021
Later among the works it cites.
Batch active learning at scale
Citovsky, G., DeSalvo, G., Gentile, C., Karydas, L., Rajagopalan, A., Rostamizadeh, A., and Kumar, S. (2021) · 2021
Later among the works it cites.
A provably efficient model-free posterior sampling method for episodic reinforcement learning
Dann, C., Mohri, M., Zhang, T., and Zimmert, J. (2021) · 2021
Later among the works it cites.
Adaptivity in adaptive submodularity
Esfandiari, H., Karbasi, A., and Mirrokni, V. (2021) · 2021
Later among the works it cites.
Data shapley valuation for efficient batch active learning
Original
Ghorbani, A., Zou, J., and Esteva, A. (2021) · 2021
Later among the works it cites.
Improved algorithms for agnostic pool-based active classification
Katz-Samuels, J., Zhang, J., Jain, L., and Jamieson, K. (2021) · 2021
Later among the works it cites.
A simple baseline for batch active learning with stochastic acquisition functions
Original
Kirsch, A., Farquhar, S., and Gal, Y. (2021) · 2021
Later among the works it cites.
Similar: Submodular information measures based active learning in realistic scenarios
Kothawade, S., Beck, N., Killamsetty, K., and Iyer, R. (2021) · 2021
Later among the works it cites.
Neural active learning with performance guarantees
Wang, Z., Awasthi, P., Dann, C., and Sekhari, A. Gentile, C. (2021) · 2021
Later among the works it cites.
Improved algorithms for efficient active learning halfspaces with massart and tsybakov noise
Zhang, C. and Li, Y. (2021) · 2021
Later among the works it cites.
Provably optimal algorithms for generalized linear contextual bandits
Li, L., Lu, Y., and Zhou, D. (2017) · 2080
Closest in time.

Beyond the bibliography

alphaXiv searches the wider corpus for related work and actual follow-ups.

Open on alphaXiv

alphaXiv is searching for related work…

Reading the bibliography…