Reviews: Uncertainty Sampling is Preconditioned Stochastic Gradient Descent on Zero-One Loss

This paper provides theoretical analysis and empirical examples for two phenomenon in active learning. The first is it could be possible that the 0-1 loss on subset of the entire dataset generated uncertainty sampling is smaller than learning using the whole dataset. The second is uncertainty sampling could "converge" to different models and predictive results. In the analysis, it is shown that the reason for these is the expected gradient of the "surrogate" loss of the most uncertain point is in the direction of the gradient of the current 0-1 loss. This result is based on the setup that the most uncertain point is sampled from a minipool that is a subset sampled without replacement randomly from the entire set.