Plug-in Approach to Active Learning

Stas Minsker, Math, (mentor: Vladimir Koltchinskii, Math) - The project makes an attempt to answer some open questions related to the binary classification problem in the active learning framework. Let (X,Y) be a random couple with unknown distribution P, X being an observation and Y - a binary label to be predicted. While in passive learning the sequence of iid observations X_i is given together with corresponding labels Y_i as an input, the active learner receives only the sequence of observations X_i and decides if the label has to be requested or not based on previously collected data. If we measure the performance of a learning algorithm in terms of the number of requested labels, active procedures are often more effective than passive. Our main goal is to design active learning algorithms that adapt to the parameters of the underlying distribution P(such as smoothness of the regression function and noise level) and are computationally tractable at the same time(while previously known algorithms do not possess both desired properties simultaneously). We are also interested in obtaining minimax lower bounds for the excess risk of an active classifier in our framework. This will answer the question about the optimality of proposed learning algorithms.