Uncertainty Sampling is Preconditioned Stochastic Gradient Descent on Zero-One Loss
This provides a theoretical foundation for a widely used active learning algorithm, addressing its convergence behavior for practitioners in machine learning.
The paper tackles the problem of explaining why uncertainty sampling in active learning can converge to different or better parameters than standard training, showing theoretically that it performs preconditioned stochastic gradient descent on a smoothed population zero-one loss, with experiments supporting this connection.
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 loss can be interpreted as performing a preconditioned stochastic gradient step on a smoothed version of the population zero-one loss that converges to the population zero-one loss. Furthermore, uncertainty sampling moves in a descent direction and converges to stationary points of the smoothed population zero-one loss. Experiments on synthetic and real datasets support this connection.