Near-Polynomially Competitive Active Logistic Regression
cs.LG
Submitted: 2025-03-07
Updated: 2026-10-27
Code: https://github.com/trung6/ActLogReg
License: http://creativecommons.org/publicdomain/zero/1.0/
The gist: We address the problem of active logistic regression in the realizable setting.
Terminology
Abstract
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 1 over rather than (1/) labels to get error larger than the optimum. We present the first algorithm that is polynomially competitive with the optimal algorithm on every input instance, up to a factor d squared and factors polylogarithmic in the error and domain size. In particular, on a simple family of logistic threshold instances with a uniform distribution, our algorithm uses (1/) labels, whereas every passive learner requires Ω(1/ 2) labels. Our algorithm is based on 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.
Related papers
- A Physics-Regulated Neural Framework for Learning 3D Grain Growth Dynamics
- FlexMoE: Learning One-for-All Multi-Budget Expert Pruning for Flexible MoE Deployment
- OptiMind: Improving Small Language Models for Optimization Modeling through Formulation Guidance and Multi-Turn Learning
- Staying in the Sweet Spot: Boost Reasoning Evolution via Responsive Rollout Difficulty Manipulation
- Examining the Impact of Data and Training Methods on Emergent and Subliminal Misalignment
- Rethinking Black-Box On-Policy Distillation: A Rubric-based Analysis