Efficient Active Learning Halfspaces with Tsybakov Noise: A Non-convex Optimization Approach
This work addresses label-efficient learning for structured data with noise, offering an incremental improvement over prior efficient algorithms in active learning theory.
The paper tackles the problem of active learning halfspaces with Tsybakov noise by proving that approximate stationary points of a nonconvex loss yield low error, and designs an algorithm achieving a label complexity of ˜O(d (1/ε)^((8-6α)/(3α-1))) for α in (1/3, 1], narrowing the gap to the information-theoretic lower bound.
We study the problem of computationally and label efficient PAC active learning $d$-dimensional halfspaces with Tsybakov Noise~\citep{tsybakov2004optimal} under structured unlabeled data distributions. Inspired by~\cite{diakonikolas2020learning}, we prove that any approximate first-order stationary point of a smooth nonconvex loss function yields a halfspace with a low excess error guarantee. In light of the above structural result, we design a nonconvex optimization-based algorithm with a label complexity of $\tilde{O}(d (\frac{1}ε)^{\frac{8-6α}{3α-1}})$, under the assumption that the Tsybakov noise parameter $α\in (\frac13, 1]$, which narrows down the gap between the label complexities of the previously known efficient passive or active algorithms~\citep{diakonikolas2020polynomial,zhang2021improved} and the information-theoretic lower bound in this setting.