首个多项式竞争的主动逻辑回归算法，显著降低标签需求。
Near-Polynomially Competitive Active Logistic Regression
- 基于高效采样设计新算法，实现多项式竞争力
- 在可实现设置下，标签复杂度仅需polylog(1/ε)
- 适用于更广函数类，实测优于现有主动学习方法
我们研究可实现设定下的主动逻辑回归问题。已知主动学习在某些情况下可将标签查询数从被动学习的多项式量级降至对数量级，即达到误差ε时仅需$\log \frac{1}{\eps}$而非$\poly(1/\eps)$次查询。本文提出首个在所有输入实例上与最优算法多项式竞争的算法，仅含多对数因子（关于误差和域大小）。特别地，若任一算法能以$\polylog(1/\eps)$标签复杂度达成目标，则本算法亦然。该算法基于高效采样，可扩展至学习更广函数类。实验验证了其在逻辑回归上相较现有主动学习算法的性能提升。
原文摘要 · Abstract (English)
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.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。