Source: https://projecteuclid.org/euclid.aos/1291388378
Timestamp: 2019-04-22 08:03:05+00:00

Document:
Volume 39, Number 1 (2011), 333-361.
We study the rates of convergence in generalization error achievable by active learning under various types of label noise. Additionally, we study the general problem of model selection for active learning with a nested hierarchy of hypothesis classes and propose an algorithm whose error rate provably converges to the best achievable error among classifiers in the hierarchy at a rate adaptive to both the complexity of the optimal classifier and the noise conditions. In particular, we state sufficient conditions for these rates to be dramatically faster than those achievable by passive learning.
Ann. Statist., Volume 39, Number 1 (2011), 333-361.
 Alexander, K. S. (1984). Probability inequalities for empirical processes and a law of the iterated logarithm. Ann. Probab. 12 1041–1067.
 Alexander, K. S. (1985). Rates of growth for weighted empirical processes. In Proceedings of the Berkeley Conference in Honor of Jerzy Neyman and Jack Kiefer II 475–493. Wadsworth, Belmont, CA.
 Alexander, K. S. (1986). Sample moduli for set-indexed gaussian processes. Ann. Probab. 14 598–611.
 Alexander, K. S. (1987). Rates of growth and sample moduli for weighted empirical processes indexed by sets. Probab. Theory Related Fields 75 379–423.
 Anthony, M. and Bartlett, P. L. (1999). Neural Network Learning: Theoretical Foundations. Cambridge Univ. Press, Cambridge.
 Balcan, M.-F., Beygelzimer, A. and Langford, J. (2006). Agnostic active learning. In Proceedings of the 23rd International Conference on Machine Learning. ACM, New York.
 Balcan, M.-F., Broder, A. and Zhang, T. (2007). Margin based active learning. In Proceedings of the 20th Conference on Learning Theory. Lecture Notes in Computer Science 4539 35–50. Springer, Berlin.
 Balcan, M.-F., Hanneke, S. and Wortman, J. (2008). The true sample complexity of active learning. In Proceedings of the 21st Conference on Learning Theory. Omnipress, Madison, WI.
 Balcan, M.-F., Beygelzimer, A. and Langford, J. (2009). Agnostic active learning. J. Comput. System Sci. 75 78–89.
 Beygelzimer, A., Dasgupta, S. and Langford, J. (2009). Importance weighted active learning. In International Conference on Machine Learning. ACM, New York.
 Blumer, A., Ehrenfeucht, A., Haussler, D. and Warmuth, M. (1989). Learnability and the Vapnik-Chervonenkis dimension. J. Assoc. Comput. Mach. 36 929–965.
 Castro, R. and Nowak, R. (2008). Minimax bounds for active learning. IEEE Trans. Inform. Theory 54 2339–2353.
 Cohn, D., Atlas, L. and Ladner, R. (1994). Improving generalization with active learning. Machine Learning 15 201–221.
 Dasgupta, S., Hsu, D. and Monteleoni, C. (2007). A general agnostic active learning algorithm. In Advances in Neural Information Processing Systems. MIT Press, Cambridge, MA.
 Friedman, E. (2009). Active learning for smooth problems. In Proceedings of the 22nd Conference on Learning Theory. Montreal, Qebec.
 Giné, E. and Koltchinskii, V. (2006). Concentration inequalities and asymptotic results for ratio type empirical processes. Ann. Probab. 34 1143–1216.
 Giné, E., Koltchinskii, V. and Wellner, J. (2003). Ratio limit theorems for empirical processes. In Stochastic Inequalities (E. Giné, C. Houdré and D. Nualrt, eds.) 249–278. Birkhäuser, Basel.
 Hanneke, S. (2007). A bound on the label complexity of agnostic active learning. In Proceedings of the 24th International Conference on Machine Learning (Z. Ghahramani, ed.) 353–360. ACM, New York.
 Hanneke, S. (2010). Proofs and supplements to “Rates of convergence in active learning.” DOI: 10.1214/10-AOS843SUPP.
 Kääriäinen, M. (2006). Active learning in the non-realizable case. In Proceedings of the 17th International Conference on Algorithmic Learning Theory. Springer, Berlin.
 Kearns, M. J., Schapire, R. E. and Sellie, L. M. (1994). Toward efficient agnostic learning. Mach. Learn. 17 115–141.
 Koltchinskii, V. (2006). Local rademacher complexities and oracle inequalities in risk minimization. Ann. Statist. 34 2593–2656.
 Koltchinskii, V. (2008). Oracle inequalities in empirical risk minimization and sparse recovery problems: Lecture notes. Technical report, Ecole d’ete de Probabilités de Saint-Flour.
 Li, Y. and Long, P. M. (2007). Learnability and the doubling dimension. In Advances in Neural Information Processing. MIT Press, Cambridge, MA.
 Mammen, E. and Tsybakov, A. (1999). Smooth discrimination analysis. Ann. Statist. 27 1808–1829.
 Massart, P. and Nédélec, E. (2006). Risk bounds for statistical learning. Ann. Statist. 34 2326–2366.
 Tsybakov, A. B. (2004). Optimal aggregation of classifiers in statistical learning. Ann. Statist. 32 135–166.
 Vapnik, V. (1982). Estimation of Dependencies Based on Empirical Data. Springer, New York. Translated from the Russian by Samuel Kotz.
 Vapnik, V. (1998). Statistical Learning Theory. Wiley, New York.
 Vapnik, V. and Chervonenkis, A. (1971). On the uniform convergence of relative frequencies of events to their probabilities. Theory Probab. Appl. 16 264–280.
 Wang, L. (2009). Sufficient conditions for agnostic active learnable. In Advances in Neural Information Processing Systems 22. MIT Press, Cambridge, MA.
Supplementary material: Proofs and Supplements for “Rates of Convergence in Active Learning”. The supplementary material contains three additional Appendices, namely, Appendices B, C and D. Specifically, Appendix B provides detailed proofs of Theorems 5–9, as well as several abstract lemmas from which these results are derived. Appendix C discusses the use of estimators in Algorithm 1. Finally, Appendix D includes a proof of a general minimax lower bound ∝ n^(−κ ∕ (2κ − 2)) for any nontrivial hypothesis class, generalizing a result of Castro and Nowak .

References: V. 
 V. 
 V. 
 V. 
 V. 
 V. 
 V.