Convergence Rates of Active Learning for Maximum Likelihood Estimation
An active learner is given a class of models, a large set of unlabeled examples, and the ability to interactively query labels of a subset of these examples; the goal of the learner is to learn a model in the class that fits the data well. Previous theoretical work has rigorously characterized label complexity of active learning, but most of this work has focused on the PAC or the agnostic PAC model. In this paper, we shift our attention to a more general setting -maximum likelihood estimation. Provided certain conditions hold on the model class, we provide a two-stage active learning algorithm for this problem. The conditions we require are fairly general, and cover the widely popular class of Generalized Linear Models, which in turn, include models for binary and multi-class classification, regression, and conditional random fields. We provide an upper bound on the label requirement of our algorithm, and a lower bound that matches it up to lower order terms. Our analysis shows that unlike binary classification in the realizable case, just a single extra round of interaction is sufficient to achieve near-optimal performance in maximum likelihood estimation. On the empirical side, the recent work in [12] and [13] (on active linear and logistic regression) shows the promise of this approach.
The paper addresses the problem of active learning by trying to find the MLE from a parametrized class of models. It shows that under certain conditions an expression of the Fisher information is a suitable surrogate objective function. Optimizing this surrogate objective helps find a \emph{good} sampling strategy. However, this expression entails the optimal parameter \theta^* whose approximation is the ultimate goal of the algorithm. To overcome this issue the paper takes a two step approach. In the first step a fraction of the budgeted queries is used to get a rough estimate of \theta^* which is subsequently used to optimize the surrogate objective function and obtain a good sampling distribution. The paper shows that using this two step approach one can achieve an asymptotically optimal error given a fixed budget on number of queries for certain classes of models which include GLMs. The quality and presentation of the paper is good. The result is significant, at least from a theoretical perspective, albeit being slightly disappointing since it shows that a two step batch sampling is asymptotically as good as one can get with a full fledged active learning on these classes of models. This aspect brings to mind the question of applicability of the result to practical settings and strongly begs some numerical demonstration and comparison which is unfortunately missing in the paper.comments: 1. diameter(\Theta) in Theorem 1 is not defined. 2. The big O notation has in itself an implicit inequality and there is no proper definition of f > O(g) that I am aware of. Hence the author(s) should clarify the condition in Theorem 1 which states that m > O(...). 3. It would be informative to see what are the practical implication of Assumption 1 vis-ae-vis the result of Theorem 1. For example, if the set U was randomly chosen from \mathcal{X} with some reasonable distribution what is the scaling of \sigma_min in part 3 of Assumption 1 and what would be the implication for m_1. At its current form the paper does not give any idea under what regime this is an applicable method. The lack of any numerical demonstration even in the supplementary section is not helpful. While the theoretical contribution is certainly valuable demonstration of the applicability of the result makes it many folds more interesting. Furthermore, if it is possible to demonstrate the method in practical scenarios this type of result strongly begs some comparison with other methods.