Exponential Savings in Agnostic Active Learning through Abstention

Abstract

We show that in pool-based active classification without assumptions on the underlying distribution, if the learner is given the power to abstain from some predictions by paying the price marginally smaller than the average loss $1/2$ of a random guess, exponential savings in the number of label requests are possible whenever they are possible in the corresponding realizable problem. We extend this result to provide a necessary and sufficient condition for exponential savings in pool-based active classification under the model misspecification.

arXiv comment31 pages, IEEE Transactions on Information Theory

References in corpus (15)

• Risk bounds for statistical learning
• Concentration inequalities and asymptotic results for ratio type empirical processes
• Fast learning rates in statistical inference through aggregation
• Generalization bounds for averaged classifiers
• Beyond Disagreement-based Agnostic Active Learning
• Active Learning from Imperfect Labelers
• Rates of convergence in active learning
• Surrogate Losses in Passive and Active Learning
• Active and passive learning of linear separators under log-concave distributions
• Distribution-Free Robust Linear Regression
• Plug-in Approach to Active Learning
• Exponential Savings in Agnostic Active Learning through Abstention
• The Relationship Between Agnostic Selective Classification Active Learning and the Disagreement Coefficient
• Fast Rates for Online Prediction with Abstention
• Adaptivity to Noise Parameters in Nonparametric Active Learning

Cited by in corpus (2)

• Exponential Savings in Agnostic Active Learning through Abstention
• Classification with abstention but without disparities