On the Convergence of Loss and Uncertainty-based Active Learning Algorithms
This work addresses active learning and data subset selection problems for machine learning practitioners, but it is incremental as it builds on existing SGD and sampling methods.
The paper tackles the problem of convergence rates and data sample sizes for SGD-based training with loss or uncertainty-based sampling in active learning, proposing an Adaptive-Weight Sampling (AWS) algorithm that achieves stochastic Polyak's step size in expectation and demonstrating its efficiency on various datasets.
We investigate the convergence rates and data sample sizes required for training a machine learning model using a stochastic gradient descent (SGD) algorithm, where data points are sampled based on either their loss value or uncertainty value. These training methods are particularly relevant for active learning and data subset selection problems. For SGD with a constant step size update, we present convergence results for linear classifiers and linearly separable datasets using squared hinge loss and similar training loss functions. Additionally, we extend our analysis to more general classifiers and datasets, considering a wide range of loss-based sampling strategies and smooth convex training loss functions. We propose a novel algorithm called Adaptive-Weight Sampling (AWS) that utilizes SGD with an adaptive step size that achieves stochastic Polyak's step size in expectation. We establish convergence rate results for AWS for smooth convex training loss functions. Our numerical experiments demonstrate the efficiency of AWS on various datasets by using either exact or estimated loss values.