Minimax analysis of active learning

MaRDI QIDQ2788421zbMATH OpenFDO

Authors Liu Yang, Steve Hanneke

Publication date 19 February 2016

Published in Journal of Machine Learning Research (JMLR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1410.0996, http://jmlr.csail.mit.edu/papers/v16/hanneke15a.html

zbMATH Keywords

active learningadaptive samplingmargin conditionminimax analysissample complexityselective samplingsequential designstatistical learning theoryTsybakov noise

Mathematics Subject Classification ID

Minimax procedures in statistical decision theory (62C20) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Learning and adaptive systems in artificial intelligence (68T05)

Abstract: This work establishes distribution-free upper and lower bounds on the minimax label complexity of active learning with general hypothesis classes, under various noise models. The results reveal a number of surprising facts. In particular, under the noise model of Tsybakov (2004), the minimax label complexity of active learning with a VC class is always asymptotically smaller than that of passive learning, and is typically significantly smaller than the best previously-published upper bounds in the active learning literature. In high-noise regimes, it turns out that all active learning problems of a given VC dimension have roughly the same minimax label complexity, which contrasts with well-known results for bounded noise. In low-noise regimes, we find that the label complexity is well-characterized by a simple combinatorial complexity measure we call the star number. Interestingly, we find that almost all of the complexity measures previously explored in the active learning literature have worst-case values exactly equal to the star number. We also propose new active learning strategies that nearly achieve these minimax label complexities.

Recommendations

• Active Learning in the Non-realizable Case
• Minimax Bounds for Active Learning
• Teaching Dimension and the Complexity of Active Learning
• Minimax Bounds for Active Learning
• Activized Learning: Transforming Passive to Active with Improved Label Complexity

Cited in

(25)

• Cautious active clustering
• When are epsilon-nets small?
• On density of subgraphs of halved cubes
• Nuclear discrepancy for single-shot batch active learning
• Agnostic active learning
• On version space compression
• Refined error bounds for several learning algorithms
• Active Learning for Enumerating Local Minima Based on Gaussian Process Derivatives
• Active Learning in the Non-realizable Case
• Minimax Bounds for Active Learning
• Active nearest-neighbor learning in metric spaces
• Interactive algorithms: pool, stream and precognitive stream
• The relationship between agnostic selective classification, active learning and the disagreement coefficient
• Minimax robust active learning for approximately specified regression models
• Active learning for cost-sensitive classification
• Smoothness, disagreement coefficient, and the label complexity of agnostic active learning
• Minimax Bounds for Active Learning
• Teaching Dimension and the Complexity of Active Learning
• Learning Theory
• A compression technique for analyzing disagreement-based active learning
• Poisson Reweighted Laplacian Uncertainty Sampling for Graph-Based Active Learning
• Realizable learning is all you need
• Recent advances in scaling-down sampling methods in machine learning
• Optimal prediction using expert advice and randomized Littlestone dimension
• Stable sample compression schemes: new applications and an optimal SVM margin bound

This page was built for publication: Minimax analysis of active learning

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2788421)