Uncertainty Sampling is Preconditioned Stochastic Gradient Descent on Zero-One Loss
Uncertainty sampling, a popular active learning algorithm, is used to reduce the amount of data required to learn a classifier, but it has been observed in practice to converge to different parameters depending on the initialization and sometimes to even better parameters than standard training on all the data. In this work, we give a theoretical explanation of this phenomenon, showing that uncertainty sampling on a convex (e.g., logistic) loss can be interpreted as performing a preconditioned stochastic gradient step on the population zero-one loss. Experiments on synthetic and real datasets support this connection.
The paper shows that after some reasonable assumptions are made, a modified version of uncertainty sampling could be viewed as optimizing zero-one loss of a binary classification problem. Before reading this paper, I also wondered why some papers report that only looking at a subset of samples could improve the classifier performance. I am glad to see a theoretical paper which tries to answer this mystery. I believe that the results will inspire more people to develop better active learning or optimization algorithms.  Strength: Except the typos, the authors seem to pay attention to subtle details in the proof. Some proving techniques they use are pretty clever, although I did not read enough theoretical papers to know how difficult you can come up with those techniques. It is impressive that the main result (theorem 9) does not require the convex assumption of the model. Except the proposition 11 and 12, which sound true but its proofs involve too advanced calculus concepts, I tried to follow every step in the proof. I think all steps are intuitively correct (after ignoring those typos) and are not redundant, although I did not derive every step by myself again to make sure it is 100% right.  Weakness: The main weakness is its writing. First, the author misses some directly related work such as [1] and [2]. [1] and [2] also show the connections between active learning and gradient descent, although they prove the properties of different algorithms and different models. Second, the paper has too many typos and inconsistent notations. In addition, the authors often use terminologies without citations or explanations. These make the readers hard to follow the math, especially the proofs. Third, the theorem actually requires many assumptions, which might not hold in practice and are not stated very clearly in the abstract and introduction. For example, the abstract does not mention that the theorem only holds when large regularization is applied to the classifier and uncertainty sampling selects the points on the decision boundary (as the pool of samples approach to infinity and the probability mass near decision boundary is not zero).  Typos and revision suggestions In the main paper: 22: At the first time of mentioning pre-condition SGD, providing a citation because I think not all people know what pre-condition means.  76: four parameters? Equation (5): saying that you are using Mean-Value theorem 152: Could you define smooth more clearly? 157 and 168: Theta_{valid} should be Theta_{regular} Equation (14): It took me some time to find what psi(x) is at line 50. Recommend to add the definition again here.  In supplementary materials: Equation (17): There is no n_{seed} in (4) Equation (20): B -> M_l Equation (23): I think n should be removed, but equation (24) is correct Equation (31): Missing ) after theta_{t-1}. Missing gradient sign before l(z^(t),theta_{t-1}) Equation (39): Remove extra ] for E Equation (43): Missing E_{y|x} Equation (47) and (48): phi() -> psi()   [1] Guillory, Andrew, Erick Chastain, and Jeff Bilmes. "Active learning as non-convex optimization." Artificial Intelligence and Statistics. 2009. [2] Ramdas, Aaditya, and Aarti Singh. "Algorithmic connections between active learning and stochastic convex optimization." International Conference on Algorithmic Learning Theory. Springer, Berlin, Heidelberg, 2013.  After rebuttal: I think the authors address the concerns of reviewer 1 effectively. I encourage the authors to add that convergence proof to supplementary material. I keep my original judgment because I think all reviewers did not find significant flaws other than typos in the proof and I think the proposed theorems are significant enough to be published in NIPS.