More Like this

1. Near-Polynomially Competitive Active Logistic Regression

   Zhou, Y; Price, E; Nguyen, T (March 2025, https://doi.org/10.48550/arXiv.2503.05981)

   We address the problem of active logistic regression in the realizable setting. It is well known that active learning can require exponentially fewer label queries compared to passive learning, in some cases using $$\log \frac{1}{\eps}$$ rather than $$\poly(1/\eps)$$ labels to get error $$\eps$$ larger than the optimum. We present the first algorithm that is polynomially competitive with the optimal algorithm on every input instance, up to factors polylogarithmic in the error and domain size. In particular, if any algorithm achieves label complexity polylogarithmic in $$\eps$$, so does ours. Our algorithm is based on efficient sampling and can be extended to learn more general class of functions. We further support our theoretical results with experiments demonstrating performance gains for logistic regression compared to existing active learning algorithms. 

   more » « less
2. Direct Acquisition Optimization for Low-Budget Active Learning

   Zhao, Z; Jiang, Y; Chen, Y (December 2024, Workshop on Bayesian Decision-making and Uncertainty, 38th Conference on Neural Information Processing Systems (NeurIPS 2024))

   Active Learning (AL) has gained prominence in integrating data-intensive machine learning (ML) models into domains with limited labeled data. However, its effectiveness diminishes significantly when the labeling budget is low. In this paper, we first empirically observe the performance degradation of existing AL algorithms in the low-budget settings, and then introduce Direct Acquisition Optimization (DAO), a novel AL algorithm that optimizes sample selections based on expected true loss reduction. Specifically, DAO utilizes influence functions to update model parameters and incorporates an additional acquisition strategy to mitigate bias in loss estimation. This approach facilitates a more accurate estimation of the overall error reduction, without extensive computations or reliance on labeled data. Experiments demonstrate DAO's effectiveness in low budget settings, outperforming state-of-the-arts approaches across seven benchmarks. 

   more » « less
3. Towards Joint Segmentation and Active Learning for Block-Structured Data Streams

   Conrad Holtsclaw, Meet P. (August 2019, The ACM SIGKDD Conference on Knowledge Discovery and Data Mining Workshop on Data Collection, Curation, and Labeling for Mining and Learning)

   Stream-based active learning methods assume that data instances arrive in sequence and the decision must be made to query an instance or not as it arrives. In mobile health and human activity recognition, the data stream is often block-structured where instances in the same block have the same label, but the boundaries between blocks are unobserved. In this paper, we propose an approach to active learning in this setting where we simultaneously learn to segment the stream while learning an instance-level discriminative classifier. We show that by propagating collected labels into inferred segments, we can learn improved predictive models with significantly fewer queries. 

   more » « less
4. Efficient Active Learning with Abstention

   Zhu, Yinglun; Nowak, Robert D (November 2022, Advances in Neural Information Processing Systems)

   The goal of active learning is to achieve the same accuracy achievable by passive learning, while using much fewer labels. Exponential savings in terms of label complexity have been proved in very special cases, but fundamental lower bounds show that such improvements are impossible in general. This suggests a need to explore alternative goals for active learning. Learning with abstention is one such alternative. In this setting, the active learning algorithm may abstain from prediction and incur an error that is marginally smaller than random guessing. We develop the first computationally efficient active learning algorithm with abstention. Our algorithm provably achieves p o l y l o g ( 1 ε ) label complexity, without any low noise conditions. Such performance guarantee reduces the label complexity by an exponential factor, relative to passive learning and active learning that is not allowed to abstain. Furthermore, our algorithm is guaranteed to only abstain on hard examples (where the true label distribution is close to a fair coin), a novel property we term \emph{proper abstention} that also leads to a host of other desirable characteristics (e.g., recovering minimax guarantees in the standard setting, and avoiding the undesirable noise-seeking'' behavior often seen in active learning). We also provide novel extensions of our algorithm that achieve \emph{constant} label complexity and deal with model misspecification. 

   more » « less
5. Learning from Label Proportions by Learning with Label Noise

   Zhang, Jianxin; Wang, Yutong; Scott, Clayton (January 2022, Conference on Neural Information Processing Systems (NeurIPS 2022))

   Learning from label proportions (LLP) is a weakly supervised classification problem where data points are grouped into bags, and the label proportions within each bag are observed instead of the instance-level labels. The task is to learn a classifier to predict the labels of future individual instances. Prior work on LLP for multi-class data has yet to develop a theoretically grounded algorithm. In this work, we propose an approach to LLP based on a reduction to learning with label noise, using the forward correction (FC) loss of Patrini et al. [30]. We establish an excess risk bound and generalization error analysis for our approach, while also extending the theory of the FC loss which may be of independent interest. Our approach demonstrates improved empirical performance in deep learning scenarios across multiple datasets and architectures, compared to the leading methods. 

   more » « less