Uncertainty Sampling is Preconditioned Stochastic Gradient Descent on\n Zero-One Loss

2018/12/04 by Stephen Mussmann, Percy Liang, Mussmann, Stephen +1
Computer Science · Engineering · #FOS: Computer and information sciences #Gaussian Processes and Bayesian Inference #Machine Learning (cs.LG) #Machine Learning (stat.ML) #Machine Learning and Algorithms #Machine Learning and Data Classification #Sparse and Compressive Sensing Techniques #Stochastic Gradient Optimization Techniques

paper · pdf · doi:10.48550/arxiv.1812.01815

openalex publication_date 2018/12/04 · openalex created_date 2019/06/27 · openalex updated_date 2026/07/28

Abstract

Uncertainty sampling, a popular active learning algorithm, is used to reduce\nthe amount of data required to learn a classifier, but it has been observed in\npractice to converge to different parameters depending on the initialization\nand sometimes to even better parameters than standard training on all the data.\nIn this work, we give a theoretical explanation of this phenomenon, showing\nthat uncertainty sampling on a convex loss can be interpreted as performing a\npreconditioned stochastic gradient step on a smoothed version of the population\nzero-one loss that converges to the population zero-one loss. Furthermore,\nuncertainty sampling moves in a descent direction and converges to stationary\npoints of the smoothed population zero-one loss. Experiments on synthetic and\nreal datasets support this connection.\n

Related

• Understanding Uncertainty Sampling
• On the Convergence of Loss and Uncertainty-based Active Learning Algorithms
• On the Relationship between Data Efficiency and Error for Uncertainty Sampling
• Exploiting Uncertainty of Loss Landscape for Stochastic Optimization
• Active Bias: Training More Accurate Neural Networks by Emphasizing High Variance Samples